目录

经过前一篇博客的简单介绍,我们对导数、方向导数、梯度应该有一个较为清晰的认识。在知道梯度之后,我们就可以通过一些无约束的优化方法来求极值。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

梯度下降法

梯度下降法(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;(mini-batch 的 batch size 一般不会很大。)如果 \(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节。

【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法 人工智能 第1张
图 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.

【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法 人工智能 第2张
图 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 矩阵的逆)。(为什么更新公式是这样的?可以将 \(f(\bm x)\)\(\bm x_{t}\) 附近进行二阶泰勒展开,然后求导。)

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 的方法。(Hessian 如果不是正定的,那么就没救了,牛顿法并不适合)

如果 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 矩阵的计算也很费事,而且还得求逆。

可能会有一个疑问,梯度下降法中梯度的反方向不是当前点下降最快的方向吗,为什么牛顿法会收敛更快,牛顿法的更新方向更好吗?牛顿法是二阶收敛,梯度下降法是一阶收敛,所以牛顿法就更快。更通俗地,梯度下降法只从当前位置选择一个坡度最大的方向走一步,而牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑走了一步后,坡度是否会变得更大。从几何上说,牛顿法就是用一个二次曲面去拟合当前位置的的局部曲面,而梯度下降法用的是一个平面去拟合,通常情况下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最优下降路径。详情参见 最优化问题中,牛顿法为什么比梯度下降法求解需要的迭代次数更少? -- 大饼土博

【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法 人工智能 第3张
图 3 A comparison of gradient descent (green) and Newton's method (red) for minimizing a function (with small step sizes). Newton's method uses curvature information (i.e. the second derivative) to take a more direct route.

以下两种方法都是对牛顿法的修改!!!

共轭方向法

updating。。。

伪牛顿法

updating。。。

系列
【机器学习之数学】01 导数、偏导数、方向导数、梯度
【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法

References

Edwin K. P. Chong, Stanislaw H. Zak-An Introduction to Optimization, 4th Edition
最优化问题中,牛顿法为什么比梯度下降法求解需要的迭代次数更少? -- 大饼土博
Newton's method in optimization - Wikipedia

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄