目录
经过前一篇博客的简单介绍,我们对导数、方向导数、梯度应该有一个较为清晰的认识。在知道梯度之后,我们就可以通过一些无约束的优化方法来求极值。
梯度下降法
梯度下降法(Gradient descent),顾名思义,就是自变量沿着梯度向量的反方向进行移动。
对于一个 \\(R^m \\to R\\) 的函数 \\(y = f(\\bm x)\\),初始时 \\(\\bm x = \\bm x_0\\),我们想要得到函数 \\(y = f(\\bm x)\\) 的极小值点 \\(\\bm x^*\\),如果能够求得 $ f(\\bm x)$ 的梯度 \\(\\nabla f(\\bm x)\\),那么我们就可以用梯度下降法进行迭代求极小值的近似解。(还有不能求梯度的情况吗?还真有,机器学习中如果输入的数据有缺失,那么 loss function 求出的梯度中仍然会含有未知数,这个时候可以用 EM 算法求解)
记自变量 \\(\\bm x\\) 在第 \\(t\\) 迭代后的值为 \\(\\bm x_{t}\\),则自变量的更新公式为:
\\[ \\bm x_{t+1} = \\bm x_{t} - \\alpha \\cdot \\nabla f(\\bm x_{t}) \\tag{1} \\]
式(1)中,\\(\\alpha\\) 为步长,在深度学习中被称为学习率(learning rate),控制了梯度下降速度的快慢。
机器学习中的梯度下降法
梯度下降法和反向传播算法是深度学习的基石,我们用梯度下降法更新神经网络的参数,用反向传播算法一层一层地将误差由后向前传播(就是用链式法则对 cost function 求偏导)。
如果我们定义 loss function 为
\\[ L(\\bm w) = g(\\bm w; (\\bm x, y)) = (y - \\bm w^{\\top} \\bm x)^2 \\tag{2} \\]
那么 cost function 就应该为
\\[ C(\\bm w) = \\frac{1}{n}\\sum_{i = 1}^n L(\\bm w) = \\frac{1}{n} \\sum_{i = 1}^n (y_i - \\bm w^{\\top} \\bm x_i)^2 \\tag{3} \\]
其中 \\(n\\) 为一次性计算 loss 的样本个数,在深度学习中常常就是一个 batch 的大小。(也有人把 cost function 中的 \\(\\frac{1}{n}\\) 改为 \\(\\frac{1}{n-1}\\),这就是有偏估计和无偏估计,影响不大。)
cost function/loss function 中,自变量是神经网络的权重,而我们的输入数据是已知的,这个时候我们就可以用用式(4)更新参数了:
\\[ \\bm w_{t+1} = \\bm w_{t} - \\alpha \\cdot \\nabla C(\\bm w_{t}) \\tag{4} \\]
如果输入样本 \\((\\bm x_i, y_i)\\) 中含有未知数怎么办?数据缺失了怎么办,在深度学习中,我们可能会选择剔除或者补全数据,然后再输入到神经网络中。如果不补全缺失值,对式(3)算梯度,梯度中会含有未知数,这样式(4)没法更新参数。
假设训练集中含有 \\(N\\) 个数据样本,我们对式(3)中的 \\(n\\) 取不同值(即一次性计算 loss 的样本个数取不同值),会有不同的影响。如果 \\(n = 1\\),这就是 stochastic gradient descent;如果 \\(1 <n< N\\),这就是 mini-batch gradient descent;如果 \\(n = N\\),这就是 (batch) gradient descent。
最速下降法
最速下降法(Steepest descent)是梯度下降法的一种更具体实现形式,其理念为在每次迭代中选择合适的步长 \\(\\alpha_t\\),使得目标函数值能够得到最大程度的减少。
每一次迭代,沿梯度的反方向,我们总可以找到一个 \\(\\bm x_{t+1}^* = \\bm x_{t} - \\alpha_t \\nabla f(\\bm x_{t})\\),使得在这个方向上 \\(f(\\bm x_{t+1}^*)\\) 取最小值。即
\\[ \\alpha_t = \\mathop{\\arg\\min}_{\\alpha \\ge 0} f(\\bm x_{t} - \\alpha \\nabla f(\\bm x_{t})) \\tag{5} \\]
有意思的是,最速下降法每次更新的轨迹都和上一次垂直。而且只要梯度 \\(\\nabla f(\\bm x_{t}) \\not = 0\\),则 \\(f(\\bm x_{t+1}) < f(\\bm x_{t})\\)。(即梯度不等于 0 时,肯定会下降。)具体证明参见《最优化导论》 第8.2节。
图 1 steepest descent
牛顿法
在确定搜索方向时,梯度下降和最速下降只用到了目标函数的一阶导数(梯度),而牛顿法(Newton\'s method)用到了二阶(偏)导数。
Newton\'s method (sometimes called the Newton-Raphson method) uses first and second derivatives and indeed does perform better than the steepest descent method if the initial point is close to the minimizer.
图 2 Newton\'s method
牛顿法自变量 \\(\\bm x\\) 的更新公式为:
\\[ \\bm x_{t+1} = \\bm x_{t} - F(\\bm x_{t})^{-1}\\nabla f(\\bm x_{t}) \\tag{6} \\]
其中 \\(F(x_{t})^{-1}\\) 为二阶偏导数矩阵的逆(即 Hessian 矩阵的逆)。
Newton\'s method has superior convergence properties if the starting point is near the solution. However, the method is not guaranteed to converge to the solution if we start far away from it (in fact, it may not even be well-defined because the Hessian may be singular).
当起始点 \\(\\bm x_0\\) 离极值点 \\(\\bm x^*\\) 足够近的时候,式(6)的更新公式没有问题。但是,当 \\(\\bm x_0\\) 离极值点 \\(\\bm x^*\\) 较远时,我们并不能保证牛顿法能收敛到极值点。甚至,牛顿法可能都不是一个 descent 的方法,即可能 \\(f(\\bm x_{t+1}) \\ge f(\\bm x_{t})\\)。幸运的是可以做一点修改,确保牛顿法是一个 descent 的方法。(Hession 如果不是正定的,那么就没救了,牛顿法并不适合)
如果 Hessian 矩阵正定(\\(F(\\bm x_{t}) > 0\\) ),并且 \\(\\nabla f(\\bm x_{t}) \\not = 0\\),那么我们的搜索的方向为
\\[ \\bm d_t = - F(\\bm x_{t})^{-1}\\nabla f(\\bm x_{t}) = \\bm x_{t+1} - \\bm x_{t} \\tag{7} \\]
要想从 \\(\\bm x_{t}\\) 到 \\(\\bm x_{t+1}\\) 是 descent direction,只要存在一个 \\(\\overline \\alpha > 0\\),使得所有 \\(\\alpha \\in (0, \\overline \\alpha)\\),满足 \\(f(\\bm x_{t} + \\alpha \\bm d_t) < f(\\bm x_{t})\\)。
此时牛顿法的更新公式为:
\\[ \\bm x_{t+1} = \\bm x_{t} - \\alpha_tF(\\bm x_{t})^{-1}\\nabla f(\\bm x_{t}) \\tag{8} \\]
对于 \\(\\alpha_t\\),我们也可以在方向 \\(\\bm d_t\\) 上进行线性搜索,使得 \\(\\alpha_t = \\mathop{\\arg\\min}_{\\alpha \\ge 0} f(\\bm x_{t} - \\alpha F(\\bm x_{t})^{-1}\\nabla f(\\bm x_{t}))\\)。
这个时候,梯度下降法和牛顿法除了一个 Hessian 矩阵外,是不是超级像了。如果 Hessian 不是正定的,牛顿法就没法用。当自变量维数很大时,Hessian 矩阵的计算也很费事,而且还得求逆。
共轭方向法
updating。。。
伪牛顿法
updating。。。
系列
【机器学习之数学】01 导数、偏导数、方向导数、梯度
【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法
References
Edwin K. P. Chong, Stanislaw H. Zak-An Introduction to Optimization, 4th Edition