「最速下降」梯度下降法和最速下降法区别

最速下降

1. 前言：

细微之处，彰显本质；不求甚解，难以理解。

一直以来，我都认为，梯度下降法就是最速下降法，反之亦然，老师是这么叫的，百度百科上是这么写的,wiki百科也是这么说的，这么说，必然会导致大家认为，梯度的反方向就是下降最快的方向，然而最近在读Stephen Boyd 的凸优化的书，才发现事实并非如此，梯度下降和最速下降并不相同，梯度方向也不一定总是下降最快的方向。

2. 梯度下降法

梯度下降法是一种优化方法，用来求解目标函数的极小值。梯度下降法认为梯度的反方向就是下降最快的方向，所以每次将变量沿着梯度的反方向移动一定距离，目标函数便会逐渐减小，最终达到最小。

$f(x)=f(x_{0})+\bigtriangledown f(x)(x-x_{0})+\frac{1}{2}(x-x_{0})^{T}\bigtriangledown ^{2}f(x)(x-x_{0})+...$

$f(x)\approx f(x_{0})+\bigtriangledown f(x)(x-x_{0})$

所以如果x-x_0和∇f(x)的方向相反，那么相同距离的移动，f(x)的减小最大。

所以梯度下降法的核心步骤就是

$x_{k+1}=x_{k}-a\bigtriangledown f(x)$ 其中，a是步长，可以通过精准线性查找或非精准线性查找确定。

3. 最速下降法

最速下降法在选取x的变化方向时与梯度下降法有细微的差别。

$\Delta_{nsd}=argmin_{v}(\bigtriangledown f(x)^{T}v\mid ||v||<=1)$ $\Delta {_{nsd}}$ 表示下降最快的方位方向（normalized sleepest descent direction）。

4. 差异

看到这里，可能觉得最速下降的方向和梯度下降法的方向并没有差别，都是移动单位步长，下降最多的方向。而差别就在单位步长这里，如果 $\Delta _{nsd}=argmin_{v}(\bigtriangledown f(x)^{T}v\mid \parallel v\parallel )<=1$ 中‖v‖是欧式范数，那么最速下降法就是梯度下降法，也就是说梯度下降法是最速下降法使用欧式范数的特殊情况。

5. 为什么会有不用欧式范数的情况

原因其实很简单，因为使用欧式范数的最速下降法（也就是梯度下降法）得到下降方向并非永远都是下降最快的方向。读到这里，你可能有些吃惊，可能会问，难道梯度的反方向是下降最快的方向吗？如果你有这样的疑问和思考，那么恭喜你，你对梯度有着一定的理解。

然而实际情况是这样的：梯度是变化的，而梯度下降在一次迭代的过程中假设梯度是固定不变的，所谓的梯度方向只是起始点（xk）的梯度方向，并不一定是起始点和终点之间其他点的梯度方向 $(ax{_{k}}+(1-a)x_{k+1},0<a<=1)$ ，所以梯度方向不一定是下降最快的方向，所以为了得到更快的下降方向，我们有时并不适用欧式范数。

这里写图片描述

图片来自Stephen Boyd的凸优化。

6. 什么时候会不用欧式范数？

我们知道梯度是函数对每个因子求偏导得到的列向量，表示着函数的变化趋势，

$\bigtriangledown f(x)=(\frac{\delta f}{\delta _{x1}},\frac{\delta f}{\delta _{x2}},...,\frac{\delta f}{\delta _{xn}})$ （如果你是一名程序员，你也可选择从0开始编号），向量中元素的相对大小决定了梯度的方向。我们前面提到，梯度下降的方向不是最快的方向的原因正是由于梯度方向的变化，那的梯度的方向变化由什么来决定呢？

提到梯度的变化，很自然的想到了函数的二阶导数，对于多变量函数，也就是函数的Hessian矩阵。

$\begin{vmatrix} \frac{\delta ^{^{2}}f}{\delta _{x1\delta _{x1}}} & \frac{\delta ^{^{2}}f}{\delta _{x1\delta _{x2}}}& ...&\frac{\delta ^{^{2}}f}{\delta _{x1\delta _{xn}}} \\ \frac{\delta ^{^{2}}f}{\delta _{x2\delta _{x1}}}& \frac{\delta ^{^{2}}f}{\delta _{x2\delta _{x2}}} & ...& \frac{\delta ^{^{2}}f}{\delta _{x2\delta _{xn}}}\\ ...& ...& ...&... \\ \frac{\delta ^{^{2}}f}{\delta _{xn\delta _{x1}}}& \frac{\delta ^{^{2}}f}{\delta _{xn\delta _{x2}}} & ...& \frac{\delta ^{^{2}}f}{\delta _{xn\delta _{xn}}} \end{vmatrix}$

这里首先讨论一个简单的情况，就是f(x)的各个变量相互独立，此时Hessian矩阵是一个对角阵，

$\begin{vmatrix} \frac{\delta ^{^{2}}f}{\delta _{x1\delta _{x1}}} & & & \\ & \frac{\delta ^{^{2}}f}{\delta _{x2\delta _{x2}}} && \\ & & \ddots &\\ & & & \frac{\delta ^{^{2}}f}{\delta _{xn\delta _{xn}}} \end{vmatrix}$

如果 $\frac{\delta ^{2}f}{\delta _{xi}\delta _{xi}} i=1,2,...n$ 相差不多，也就是f(x)f(x)梯度在各个方向的变化基本一致，那么梯度方向基本不会发生变化，此时梯度下降法会得到很好的结果，想法如果如果 $\frac{\delta ^{2}f}{\delta _{xi}\delta _{xi}} i=1,2,...n$ 相差很大，那么梯度方向变化就会较大，当然梯度下降的方向便不再是最好的方向。

这里写图片描述

如果，Hessian矩阵不是对角阵，那么我们需要求出矩阵的特征值，最大特征值和最小的特征值之比（这个值叫做condition number）如果不大，则梯度下降法会有很好的效果。

6. 不用欧式范数用什么范数？

使用Hessian范数，牛顿法正是使用Hessian范数的最速下降法，所以牛顿法会比梯度下降法收敛更快！

hessian 范数为

$||x||\bigtriangledown ^{2}f(x)=x^{T}\bigtriangledown ^{^{2}}f(x)x$ ，此处不再展开。

（求解 $\Delta _{nsd}=argmin_{v}(\bigtriangledown f(x)^{T}v\mid ||v||<=1)$ 便会得到 $\Delta _{nsd}=H^{-1}\bigtriangledown f(x)$

梯度下降法和最速下降法区别

最速下降

相关阅读

栏目导航

推荐阅读

热门阅读