坐标上升/下降算法

坐标下降（上升）法原理

假设要求解下面的优化问题：

$\overset{max}{\alpha }W(\alpha _{1},\alpha _{2},...,\alpha _{m})$

在这里，我们需要求解m个变量αi，一般来说是通过梯度下降（这里是求最大值，所以应该叫上升）等算法来求解，每一次迭代对

所有m个变量αi也就是α向量进行一次性优化。（这里指的是一个向量的所有分量）

。通过每次迭代中的误差调整α向量中每个元素的值。而坐标上升法（坐标上升与坐标下降可以看做是一对，坐标上升是用来求解max最优化问题，坐标下降用于求min最优化问题）的思想是每次迭代只

调整一个变量αi的值，其他变量的值在这次迭代中固定不变。(这里指的是一个向量中的一个分量)。

最里面语句的意思是固定除αi之外的所有αj(i不等于j)，这时W可看作只是关于αi的函数，那么直接对αi求导优化即可。

这里我们进行最大化求导的顺序i是从1到m，可以通过更改优化顺序来使W能够更快地增加并收敛。

如果W在内循环中能够很快地达到最优，那么坐标上升法会是一个很高效的求极值方法。

用个二维的例子来说明下坐标下降法：我们需要寻找f(x,y)=x2+xy+y2的最小值处的(x*, y*)，也就是下图的F*点的地方.

这里写图片描述

假设我们初始的点是A（图是函数投影到xoy平面的等高线图，颜色越深值越小），我们需要达到F*的地方。那最快的方法就是图中黄色线的路径，一次性就到达了，其实这个是牛顿优化法，但如果是高维的话，这个方法就不太高效了（因为需要求解矩阵的逆，这个不在这里讨论）。我们也可以按照红色所指示的路径来走。从A开始，先固定x，沿着y轴往让f(x, y)值减小的方向走到B点，然后固定y，沿着x轴往让f(x, y)值减小的方向走到C点，不断循环，直到到达F*。反正每次只要我们都往让f(x, y)值小的地方走就行了，这样脚踏实地，一步步走，每一步都使f(x, y)慢慢变小，总有一天，皇天不负有心人的。到达F*也是时间问题。

到这里你可能会说，这红色线比黄色线贫富差距也太严重了吧。因为这里是二维的简单的情况嘛。如果是高维的情况，而且目标函数很复杂的话，再加上样本集很多，那么在梯度下降中，目标函数对所有αi求梯度或者在牛顿法中对矩阵求逆，都是很耗时的。这时候，如果W只对单个αi优化很快的时候，坐标下降法可能会更加高效。

数学例题讲解

下面以如下的优化问题为例：

$f(x1,x2)=-x_{1}^{2}-3x_{2}^{2}+2x_{1}x_{2}+6$

在迭代的过程中，每次固定x2更新x1，在确定了x1的条件下，固定x1，更新x2。即每次迭代求解：
$arg \: \: \underset{x_{i}}{max}f(x_{1},x_{2},x_{3})$
也即求解：
$x_{i}\: \: \: s.t.\frac{\partial f}{x_{i}}=0$
，假设我们首先固定x2,来更新x1：

$\frac{\partial f}{\partial x_1}=-2x_1+2x_2$

令其为0，得到：

$x_1 = x_2$

再固定x1，得到：

$\frac{\partial f}{\partial x_2}=-6x_2+2x_1$

令其为0，得到：

$x_2 = \frac{1}{3}x_1$

不断按照上述的过程，直到算法收敛。

讨论区

该算法最初始值的选取不是很敏感，对有些问题的求解非常合适。（梯度法对初始值的选取使比较敏感的）。
对于没有极大值和极小值的函数，本算法肯定计算不出来。但是，实际问题中，如果没有极大值或极小值，说明建立的模型是错误的。
函数有多个极大值和多个极小值的情况，或称为局部最小值（最大值），此时，算法的计算结果与初始值的选取有很大的关系，初始值离哪个局部最优值近，得到的结果就是这个局部最优值。为了尽可能地找到全局最优值，可以随机选多组初始值进行迭代，然后再从中选取最优解。

Python 代码实现

# -*- encoding:utf-8 -*-

import matplotlib
import numpy as np
import matplotlib.cm as pcm
import matplotlib.mlab as pmlab
import matplotlib.pyplot as plt

delta=0.025
x=np.arange(-3.0,3.0,delta)
y=np.arange(-3.0,3.0,delta)
X,Y=np.meshgrid(x,y)
Z1=-(X**2)
Z2=-(Y**2)
Z=1.0 * (Z1 + 3 * Z2 + 2 * X * Y)+6.0

plt.figure()
CS=plt.contour(X,Y,Z)#画等高线

#初始化权重
a = []
b = []
a.append(2.0)
b.append(2.0)

j = 1

for i in xrange(200):
    a_tmp = b[j-1]
    a.append(a_tmp)
    b.append(b[j-1])

    j = j+1

    b_tmp = a[j-1] / 3
    a.append(a[j-1])
    b.append(b_tmp)

plt.plot(a,b)
max_x1=a[-1]
max_x2=b[-1]

print '当取最大值的时候，x1的取值为：', max_x1
print '当取最大值的时候，x2的取值为：', max_x2

print 'max f:',-(max_x1**2)-3*(max_x2**2)+2*max_x1*max_x2+6

plt.title('Coordinate Ascent')
plt.xlabel('x')
plt.ylabel('y')
plt.show()

实验结果：

当取最大值的时候，x1的取值为： 0.666666666667
当取最大值的时候，x2的取值为： 0.222222222222
max f: 5.7037037037

整个思路过程还是非常好理解的，就类似于高中我们学过的求函数的最大值和最小值问题。

《完》

所谓的不平凡就是平凡的N次幂。
                    ------By Ada

原文链接：https://blog.csdn.net/u010626937/article/details/75044343

坐标下降（上升）法原理

数学例题讲解

讨论区

Python 代码实现

你可能也喜欢