梯度下降法推导

什么是梯度？

梯度的本意是一个向量（矢量），表示某一函数在该点处的方向导数沿着该方向取得最大值，即函数在该点处沿着该方向（此梯度的方向）变化最快，变化率最大（为该梯度的模）。

通俗来说，梯度就是表示某一函数在该点处的方向导数沿着该方向取得（模）较大值，即函数在当前位置的导数。笔者理解：在高维空间中参数 $\boldsymbol{\theta}$ 和 $f(\boldsymbol{\theta})$ 形成超曲面上，当 $\boldsymbol{\theta}$ 移动相同的 $\lVert\nabla\boldsymbol{\theta}\lVert$ 模值（超距离）时，沿着梯度的方向，可以使得 $f(\boldsymbol{\theta})$ 变化量（增加）最大。梯度表示为如下： $$ \nabla f(\boldsymbol{\theta})=\frac{\partial f(\boldsymbol{\theta})}{\partial \boldsymbol{\theta}} $$ 其中，$\boldsymbol{\theta}$为矢量（向量），大小为 $1 \times n$；$f(\boldsymbol{\theta})$为标量，该函数称为目标函数，也叫做损失函数，有时候也用 $L$ 或者 $J$ 表示；$\nabla f(\boldsymbol{\theta})$ 为矢量，大小为 $n \times 1$。

如果函数 $f(\boldsymbol{\theta})$ 是凸函数，那么就可以使用梯度下降算法进行优化。 $$ \boldsymbol{\theta} = \boldsymbol{\theta_0} - \eta \cdot \nabla f(\boldsymbol{\theta_0}) $$ 其中，$\boldsymbol{\theta_0}$ 是自变量参数，代表当前参数位置坐标；$\eta$ 是学习因子（学习率），用来调整下降时步进长度；$\boldsymbol{\theta}$ 是更新后的参数值，即通过一次梯度下降法之后的参数坐标位置。

推导梯度下降法公式

我们对 $f(\boldsymbol{\theta})$ 进行一阶泰勒展开，如下： $$ f(\boldsymbol{\theta}) = f\left(\boldsymbol{\theta_{0}}\right)+\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right) \cdot \nabla f\left(\boldsymbol{\theta_{0}}\right) + o\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right) $$ 注意，上面等式当 $f(\boldsymbol{\theta})$ 在 $\boldsymbol{\theta_{0}}$ 可导时，恒成立；其中，$ o\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right) $ 为余项（或者称为线性近似误差）。而且，这里只有 $\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right) \rightarrow 0$时，$o\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right)$ 才为无穷小量，此时，可以用前两项近似 $f(\boldsymbol{\theta})$ 值，所以如果 $\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right)$ 太大，误差会比较大。

那么，当我们使用 $f\left(\boldsymbol{\theta_{0}}\right)+\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right) \cdot \nabla f\left(\boldsymbol{\theta_{0}}\right)$ 来近似 $f(\boldsymbol{\theta})$时，我们需要计算 $\nabla f\left(\boldsymbol{\theta_{0}}\right)$，即为目标函数在当前参数位置 $f(\boldsymbol{\theta_{0}})$ 处的梯度。 $$ f(\boldsymbol{\theta}) \approx f\left(\boldsymbol{\theta_{0}}\right)+\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right) \cdot \nabla f\left(\boldsymbol{\theta_{0}}\right) $$ 这里，$\boldsymbol{\theta}-\boldsymbol{\theta_{0}}$ 是一个微小量，我们令 $\lVert\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\lVert$ 为 $\eta$，$\eta$ 为标量，令单位向量 $\frac{\boldsymbol{\theta}-\boldsymbol{\theta_{0}}}{\lVert\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\rVert}$ 为 $\boldsymbol{v}$ 表示，则 $$ \boldsymbol{\theta}-\boldsymbol{\theta_{0}} = \eta \boldsymbol{v} $$ 代入到上面的表达式后： $$ f(\boldsymbol{\theta}) \approx f\left(\boldsymbol{\theta_{0}}\right)+\eta \boldsymbol{v} \cdot \nabla f\left(\boldsymbol{\theta_{0}}\right) $$ 此处是重点！！! 局部下降的目的是希望每次 $\boldsymbol{\theta}$ 更新，都能让函数值 $f(\boldsymbol{\theta})$ 变小。也就是说，希望上式 $f(\boldsymbol{\theta})<f\left(\boldsymbol{\theta_{0}}\right)$。那么，希望下面式子每次更新都可以成立： $$ f(\boldsymbol{\theta})-f\left(\boldsymbol{\theta_{0}}\right) \approx \eta \boldsymbol{v} \cdot \nabla f\left(\boldsymbol{\theta_{0}}\right)<0 $$ 因为 $\eta$ 为标量，且一般设定为正值，所以可以忽略，不等式等价于： $$ \boldsymbol{v} \cdot \nabla f\left(\boldsymbol{\theta_{0}}\right)<0 $$ 其中，$\boldsymbol{v}$ 和 $\nabla f\left(\boldsymbol{\theta_{0}}\right)$ 都是向量，$\nabla f\left(\boldsymbol{\theta_{0}}\right)$ 是当前位置的梯度，$\boldsymbol{v}$ 表示下一步前进的单位向量，是需要求解的, 从而就能根据 $\boldsymbol{\theta}-\boldsymbol{\theta_{0}}=\eta \boldsymbol{v}$ 确定 $\boldsymbol{\theta}$ 的值了。

让我们来分析，当 $\boldsymbol{v}$ 和 $\nabla f\left(\boldsymbol{\theta_{0}}\right)$ 互为反向，即 $\boldsymbol{v}$ 为当前梯度方向的负方向的时候，能让 $\lvert \boldsymbol{v} \cdot \nabla f\left(\boldsymbol{\theta_{0}}\right) \rvert$ 最大，从而使得 $f(\boldsymbol{\theta})$ 最大程度地减小，也就保证了 $\boldsymbol{v}$ 的方向是局部最大程度下降的方向。那么： $$ \boldsymbol{v}=-\frac{\left(\nabla f\left(\boldsymbol{\theta_{0}}\right)\right)^{T}}{\lVert\nabla f\left(\boldsymbol{\theta_{0}}\right)\lVert} $$ 再根据 $\boldsymbol{\theta}-\boldsymbol{\theta_{0}} = \eta \boldsymbol{v}$ 得到： $$ \boldsymbol{\theta} = \boldsymbol{\theta_{0}} - \eta \frac{\left(\nabla f\left(\boldsymbol{\theta_{0}}\right)\right)^{T}}{\lVert\nabla f\left(\boldsymbol{\theta_{0}}\right)\lVert} $$ 一般地，因为 $\lVert\nabla f\left(\boldsymbol{\theta_{0}}\right)\lVert$ 是标量，可以并入到因子 $\eta$ 中，即简化为 $$ \boldsymbol{\theta} = \boldsymbol{\theta_{0}} - \eta^{\prime} \left(\nabla f\left(\boldsymbol{\theta_{0}}\right)\right)^{T} $$ 一般 $\eta^{\prime}$ 为学习率，是一个微小常量，通常取0.01，0.001，0.0001等值。

梯度下降法分析

如果将 $f(\boldsymbol{\theta})$ 在 $\boldsymbol{\theta_{0}}$ 处进行二阶泰勒展开： $$ f(\boldsymbol{\theta}) = f\left(\boldsymbol{\theta_{0}}\right)+\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right) \cdot \nabla f\left(\boldsymbol{\theta_{0}}\right) + \frac{1}{2}\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right)\boldsymbol{H}\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right)^{T} + o\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right) $$ 其中，$\boldsymbol{H}$ 为Hessian矩阵，其展开形式为：

$$ H=\left(\begin{array}{cccc} \frac{\partial^{2}}{\partial \theta_{1} \partial \theta_{1}} f(\boldsymbol{\theta}) & \frac{\partial^{2}}{\partial \theta_{1} \partial \theta_{2}} f(\boldsymbol{\theta}) & \cdots & \frac{\partial^{2}}{\partial \theta_{1} \partial \theta_{n}} f(\boldsymbol{\theta}) \\ \frac{\partial^{2}}{\partial \theta_{2} \partial \theta_{1}} f(\boldsymbol{\theta}) & \frac{\partial^{2}}{\partial \theta_{2} \partial \theta_{2}} f(\boldsymbol{\theta}) & \cdots & \frac{\partial^{2}}{\partial \theta_{2} \partial \theta_{n}} f(\boldsymbol{\theta}) \\ \vdots & \vdots & & \vdots \\ \frac{\partial^{2}}{\partial \theta_{n} \partial \theta_{1}} f(\boldsymbol{\theta}) & \frac{\partial^{2}}{\partial \theta_{n} \partial \theta_{2}} f(\boldsymbol{\theta}) & \cdots & \frac{\partial^{2}}{\partial \theta_{n} \partial \theta_{n}} f(\boldsymbol{\theta}) \end{array}\right) $$

我们将梯度下降法的迭代公式 $\boldsymbol{\theta} = \boldsymbol{\theta_{0}} - \eta^{\prime} \left(\nabla f\left(\boldsymbol{\theta_{0}}\right)\right)^{T}$ 代入到二阶泰勒展开式中，并且忽略二阶余项误差，得到： $$ f(\boldsymbol{\theta})-f\left(\boldsymbol{\theta_{0}}\right) \approx -\eta^{\prime}\left(\nabla f\left(\boldsymbol{\theta_{0}}\right)\right)^{T} \nabla f\left(\boldsymbol{\theta_{0}}\right)+\frac{1}{2} \eta^{\prime2} \left(\nabla f\left(\boldsymbol{\theta_{0}}\right)\right)^{T} \boldsymbol{H}\nabla f\left(\boldsymbol{\theta_{0}}\right) $$ 上面式子右边是梯度下降法一步迭代后引起目标函数 $f(\boldsymbol{\theta})$ 的变化量，每次迭代的变化量其实不一定是负的，使得 $f(\boldsymbol{\theta})$ 减小，也可能引起 $f(\boldsymbol{\theta})$ 增加。

原因分析：

1. 理论分析来讲，当 $\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right) \rightarrow 0$时候，即当学习率 $\eta^{\prime}$ 足够小时，一阶展开余项 $o\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right)$ 趋近于0，不会使得上式右边为负，也就可以保证迭代可以成功下降，但是，这样会导致达到极小值需要的迭代次数增加，使得学习过慢，增加计算和时间成本。
2. 如果Hessian矩阵是负定的，可以保证 $\frac{1}{2} \eta^{\prime2} \nabla f\left(\boldsymbol{\theta_{0}}\right)^{T} \boldsymbol{H}\nabla f\left(\boldsymbol{\theta_{0}}\right)$ 项为负，那么也可以保证一次梯度下降迭代后，使得目标函数下降，关于Hessian矩阵的理解，可以参考Hessian矩阵和极值判断。
3. 当学习率 $\eta^{\prime}$过大时，二阶余项误差变大，二阶泰勒展开的准确性也就不高了，因此可以用启发式寻找合适的学习率。【延伸阅读】

下面对于 $\frac{1}{2} \eta^{\prime2} \nabla f\left(\boldsymbol{\theta_{0}}\right)^{T} \boldsymbol{H}\nabla f\left(\boldsymbol{\theta_{0}}\right)$ 为正进行分析讨论。

如果我们使上面式子右边小于0，即： $$ -\eta^{\prime}\left(\nabla f\left(\boldsymbol{\theta_{0}}\right)\right)^{T} \nabla f\left(\boldsymbol{\theta_{0}}\right)+\frac{1}{2} \eta^{\prime2} \left(\nabla f\left(\boldsymbol{\theta_{0}}\right)\right)^{T} \boldsymbol{H}\nabla f\left(\boldsymbol{\theta_{0}}\right) < 0 $$ 整理 $\eta^{\prime}$ 得到： $$ \eta^{\prime} < \frac{\left(\nabla f\left(\boldsymbol{\theta_{0}}\right)\right)^{T} \nabla f\left(\boldsymbol{\theta_{0}}\right)}{\left(\nabla f\left(\boldsymbol{\theta_{0}}\right)\right)^{T} \boldsymbol{H} \nabla f\left(\boldsymbol{\theta_{0}}\right)} $$ 那么，当学习率满足上面式子时（足够小），总可以梯度下降。不过上面式子也是在泰勒二阶展开下的近似分析。

下面使用参数只有一维情况下的特例情况下，画图说明上面的情况：

牛顿迭代法推导

通过上面泰勒展开式分析梯度下降法，我们可以知道梯度下降法仅使用梯度信息进行迭代下降，在大多数情况下效果还可以，并且由于目前神经网络中反向传播算法可以高效求解梯度，所以当前对于神经网络的优化普通采用梯度下降法。关于反向传播算法可以在我的神经网络之反向传播算法文章中了解。

牛顿法迭代公式

二阶泰勒展开近似公式为： $$ f(\boldsymbol{\theta}) \approx f\left(\boldsymbol{\theta_{0}}\right)+\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right) \cdot \nabla f\left(\boldsymbol{\theta_{0}}\right) + \frac{1}{2}\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right)\boldsymbol{H}\left(\boldsymbol{\theta}-\boldsymbol{\theta_{0}}\right)^{T} $$ 我们对式子右边求极值点，则可以得到：

深度学习中常见的优化器

SGD

Adam

参考

梯度下降法的推导
相信我你没真明白牛顿法与梯度下降法
优化理论——梯度下降法与牛顿法
线性代数笔记12：二次型与函数极值
牛顿法
应用于最优化的牛顿法
Hessian矩阵和极值判断

延伸阅读

论文

• 《A stochastic quasi-Newton method for large-scale optimization 》
• 《A Linearly-Convergent Stochastic L-BFGS Algorithm》
• 《A Multi-Batch L-BFGS Method for Machine Learning》
• 《Fast Exact Multiplication by the Hessian》

疑问

为什么神经网络每一层的学习率一样，应该是前面层学习率小，后面层学习率大。