机器学习系列之坐标下降。
坐标上升&坐标下降
和梯度下降法不同，坐标下降不是求整个变量的梯度，然后下降，而是循环地沿着变量的每一维进行单变量优化。所谓”坐标”，指的是坐标轴。算法在每次迭代中，在当前点处沿一个坐标轴方向进行一维搜索以求得一个函数的局部极小值。在整个过程中循环使用不同的坐标方向。对于不可拆分的函数而言，算法可能无法在较小的迭代步数中求得最优解。为了加速收敛，可以采用一个适当的坐标系，例如通过主成分分析获得一个坐标间尽可能不相互关联的新坐标系。对于一个凸函数,变量个数为n,也即坐标轴有n个,那么在固定n-1个轴,只在其中一个轴上求解极值,这个极值对应的也是全局极值,将所有的坐标轴循环一遍,就可以求得最优解,很多大规模的问题用这种方法都能够快速解决。
二维坐标系下的例子
例如下图：
假设我们初始的点是A（图是函数投影到xoy平面的等高线图，颜色越深值越小），我们需要达到F的地方。那最快的方法就是图中黄色线的路径，一次性就到达了，但如果是高维的话，这个方法就不太高效了（因为需要求解矩阵的逆，这个不在这里讨论）。我们也可以按照红色所指示的路径来走。从A开始，先固定x，沿着y轴往让f(x, y)值减小的方向走到B点，然后固定y，沿着x轴往让f(x, y)值减小的方向走到C点，不断循环，直到到达F。反正每次只要我们都往让f(x, y)值小的地方走，每一步都使f(x, y)慢慢变小。在二维情况下红色线比黄色线快了很多，如果是高维的情况，而且目标函数很复杂的话，再加上样本集很多，那么在梯度下降中，目标函数对所有αi求梯度或者在牛顿法中对矩阵求逆，都很耗时。这时候，如果W只对单个αi优化很快的时候，坐标下降法可能会更加高效。
算法步骤
假设我们的问题是在n维下，对于一个点，我们表示为x=(x1, x2, x3,…, xn)
- 1.选择一个合适的初始点
- 2.开始迭代，先选取一个维度(坐标轴)，固定除了这个维度以外的所有其他维度，以这个维度为自变量，求使得函数取得最小(最大)的坐标
- 3.循环执行步骤2,直到函数的值不再变化或变化很小(1e-10)
注意：
- 1.该算法最初始值的选取不是很敏感，对有些问题的求解非常合适。（梯度法对初始值的选取使比较敏感的）。
- 2.对于没有极大值和极小值的函数，本算法肯定计算不出来。但是，实际问题中，如果没有极大值或极小值，说明建立的模型是错误的。
- 3.函数有多个极大值和多个极小值的情况，或称为局部最小值（最大值），此时，算法的计算结果与初始值的选取有很大的关系，初始值离哪个局部最优值近，得到的结果就是这个局部最优值。为了尽可能地找到全局最优值，可以随机选多组初始值进行迭代，然后再从中选取最优解。
Python实现
以下面优化问题为例：f(x1, x2)=-x1x1-3x2x2+2x1*x2+6
import matplotlib
import numpy as np
import matplotlib.cm as pcm
import matplotlib.mlab as pmlab
import matplotlib.pyplot as plt
def f(x, y):
return (1.0)*((-1)*(x**2)+(-3)*(y**2)+2*x*y)+6.0
if __name__ == "__main__":
# 设置点间距
delta = 0.025
# x, y都是numpy.ndarray类型的
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)
for i in range(200):
# 先更新a
a_tmp = b[-1]
a.append(a_tmp)
b.append(b[-1])
print(str(i+1) + ": " + str(a[-1]) + " " + str(b[-1]))
# 再更新b
b_tmp = a[-1] / 3
a.append(a[-1])
b.append(b_tmp)
print(str(i+1) + ": " + str(a[-1]) + " " + str(b[-1]))
# 收敛条件
if(i > 50):
if(abs(f(a[-1], b[-1])-f(a[-2], b[-2])) < 1e-10):
break
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()
运行结果为：
1: 2.0 2.0
1: 2.0 0.6666666666666666
2: 0.6666666666666666 0.6666666666666666
2: 0.6666666666666666 0.2222222222222222
3: 0.2222222222222222 0.2222222222222222
3: 0.2222222222222222 0.07407407407407407
4: 0.07407407407407407 0.07407407407407407
4: 0.07407407407407407 0.024691358024691357
5: 0.024691358024691357 0.024691358024691357
5: 0.024691358024691357 0.008230452674897118
...
50: 8.35773341459123e-24 8.35773341459123e-24
50: 8.35773341459123e-24 2.785911138197077e-24
51: 2.785911138197077e-24 2.785911138197077e-24
51: 2.785911138197077e-24 9.286370460656922e-25
52: 9.286370460656922e-25 9.286370460656922e-25
52: 9.286370460656922e-25 3.095456820218974e-25
当取最大值的时候，x1的取值为： 9.286370460656922e-25
当取最大值的时候，x2的取值为： 3.095456820218974e-25
max f: 6.0
总结
总结来说，当问题是光滑且凸的时候，坐标下降算法一定可以收敛，当问题不光滑的时候，当不光滑的部分是可分的，那么坐标下降算法也可以收敛。坐标下降算法的优点是容易计算，同时收敛很快；缺点是当loss比较复杂时，会很明显的降低速度。
坐标下降的优化
未完待续