数值优化算法【3】– 动量法及其变种

一、问题的提出

上节提到的批量梯度下降(BGD)、随机梯度下降(SGD)和小批量梯度下降法(MBGD)，基础完全一致，区别仅在于批大小（batch size）的不同。虽然由于批大小不同带来了很多不同的特性，但它们均避免不了一个问题，即模型参数的更新方向依赖于当前batch计算出的梯度，这可能会带来一些问题。

让我们考虑一个输入为二维向量 $\boldsymbol{x} = [x_1, x_2]^\top$ 、输出为标量的目标函数$f(\boldsymbol{x})=0.1x_1^2+2x_2^2$。 下图为基于该目标函数的梯度下降，学习率为 $0.4$ 时的自变量迭代轨迹。可以看到，同一位置上，目标函数在竖直方向（$x_2$轴方向）比在水平方向（$x_1$轴方向）的斜率的绝对值更大。因此，给定学习率，梯度下降迭代自变量时会使自变量在竖直方向比在水平方向移动幅度更大。那么，我们需要一个较小的学习率从而避免自变量在竖直方向上越过目标函数最优解。然而，这会造成自变量在水平方向上朝最优解移动变慢。

如果试着将学习率调得稍大一点，此时自变量在竖直方向不断越过最优解并逐渐发散。

二、动量法的提出

（1）动量法的思路

动量法的提出是为了解决梯度下降的上述问题。由于小批量随机梯度下降比梯度下降更为广义，本章后续讨论将沿用小批量随机梯度下降法中时间步 $t$ 的小批量平均梯度 $\boldsymbol{g}_t$ 的定义。设时间步 $t$ 的自变量为 $\boldsymbol{x}_t$ ，学习率为 $\eta_t$ 。

在时间步 $0$ ，动量法创建速度变量 $\boldsymbol{v}_0$ ，并将其元素初始化成 0 。在时间步 $t>0$ ，动量法对每次迭代的步骤做如下修改：
$$
\begin{aligned}
\boldsymbol{v}t &\leftarrow \gamma \boldsymbol{v}{t-1} + \eta_t \boldsymbol{g}_t, \
\boldsymbol{x}t &\leftarrow \boldsymbol{x}{t-1} - \boldsymbol{v}_t,
\end{aligned}
$$

其中，动量超参数 $\gamma$ 满足 $0 \leq \gamma < 1$ 。当 $\gamma=0$ 时，动量法等价于小批量随机梯度下降。

在解释动量法的数学原理前，让我们先从实验中观察梯度下降在使用动量法后的迭代轨迹。动量（Momentum）法借用物理动量思想，模拟物体运动惯性，在更新模型参数时，不仅依赖于当前的梯度方向（下图中黑色箭头所指方向），还依赖于更新的大方向（红色曲线的整体前进方向，即动量方向）。

如果把梯度下降法想象成一个小球从山坡到山谷的过程，那么前面几种方法的小球是这样移动的：从 A 点开始，计算当前 A 点的坡度，沿着坡度最大的方向走一段路，停下到 B 。在 B 点再看一看周围坡度最大的地方，沿着这个坡度方向走一段路，再停下。确切的来说，这并不像一个球，更像是一个正在下山的盲人，每走一步都要停下来，用拐杖来来探探四周的路，再走一步停下来，周而复始，直到走到山谷。而一个真正的小球要比这聪明多了，从 A 点滚动到 B 点的时候，小球带有一定的初速度，在当前初速度下继续加速下降，小球会越滚越快，更快的奔向谷底。momentum动量法就是模拟这一过程来加速神经网络的优化的。

img

（2）几何解释

上图直观的解释了动量法的全部内容。

（3）公式推导

$A$ 为起始点，首先计算 $A$ 点的梯度 $\nabla a$ ， 然后下降到 B 点， 此时模型参数更新为：
$$
\begin{equation}
\theta_{new} = \boldsymbol{\theta} − \eta \boldsymbol{\nabla} \theta, \boldsymbol{\quad \theta} 为参数, \eta为学习率。
\end{equation}
$$
到了 B 点需要加上 A 点的梯度，这里梯度需要有一个衰减值 $ \gamma$（推荐值为0.9）。该做法可让早期梯度对当前梯度的影响越来越小，如果没有衰减值，模型往往会震荡难以收敛，甚至发散。所以 B 点的参数更新公式为：

$$
\begin{equation}
\left {
\begin{split}
&\boldsymbol{v}{t} = \gamma \boldsymbol{v}{t-1}+\eta \boldsymbol{\nabla}{b} \\
&\boldsymbol{\theta}{new} = \boldsymbol{\theta}-\boldsymbol{v}{t} \\
&其中: \boldsymbol{v}{t-1} 表示之前时间步累积的动量和。
\end{split}
\right .
\end{equation}
$$

这样一步一步下去，带着初速度的小球就会极速的奔向谷底。

（4）数学描述

如果设初速度为 $v_0=0$ ，时间步为 $t$ ， $t$ 时间步的梯度为 $g_t$ ，模型参数为 $\theta$ ，衰减值为 $\gamma$ ，学习率为 $\eta$ ，则上述过程可以表达为：

$$
\begin{equation}
\left {
\begin{split}
& \boldsymbol{v}{0}=\mathbf{0}\\
& \boldsymbol{v}{t}=\gamma \boldsymbol{v}{t-1}+\eta \boldsymbol{g}{t} \\
& \boldsymbol{\theta}{t+1}=\boldsymbol{\theta}{t}-\boldsymbol{v}_{t} \\

\end{split}
\right .
\end{equation}
$$

物理上可以解释为： $ γ $ 可视为空气阻力，如果把一个球推下山，球在下坡时积聚动量，若动量方向与梯度方向一致，则在途中变得越来越快；若球的方向发生变化，则动量会衰减，速度变慢或方向改变。

（5）实验

下面两图为动量法和梯度下降法（均采用全部样本批量），其中：

  • 上图为动量法示意图，学习率 $ \eta = 0.01 $，衰减率 $\gamma = 0.9$ 。

  • 下图为批量梯度下降法示意图，学习率$ \eta = 0.01 $ 。

    这里写图片描述 这里写图片描述

仔细看右上角的等高线图就可以看见，momentum方法每一步走的都要更远一些。由于累加了动量，会带着之前的速度向前方冲去。比如一开始loss冲入了山谷，由于有之前的动量，继续朝着对面的山坡冲了上去。随着动量的更新，慢慢地最终收敛到了最小值。

注：对比图可能看起来 GD 算法要好于 momentum 方法，这仅仅是由于数据集比较简单。本文旨在从理论和实际实验中去学习 momentum 方法，不对结果对比做太多讨论。实验的结果往往和数据集、参数选择有很大关系。

此处实验代码见：https://github.com/tsycnh/mlbasic/blob/master/p4 momentum.py

三、Nesterov加速梯度法

（1）原理图

动量法每下降一步都是由前面下降方向的一个累积和当前点的梯度方向组合而成。于是Nesterov就开始思考，既然每一步都要将两个梯度方向（历史梯度、当前梯度）做一个合并再下降，那为什么不先按照历史梯度往前走那么一小步，按照前面一小步位置的“超前梯度”来做梯度合并呢？如此一来，小球就可以不管三七二十一先往前走一步，在靠前一点的位置看到梯度，然后按照那个位置再来修正这一步的梯度方向。如此一来，有了超前的眼光，小球就会更加”聪明“，这种方法被命名为 Nesterov accelerated gradient ， 简称 NAG 。由图可知Nesterov动量加速梯度法和经典动量法的差别就在B点和C点梯度的不同。
这里写图片描述

NAG加速梯度下降法示意图

（2）公式推导

记初速度为 $v_0$ ，$v_t$ 为第时间步 $t$ 的速度，写成向量形式为：
$$
\begin{equation}
\begin{aligned}
&\boldsymbol{v}{0}=0\
&\boldsymbol{v}{1}=\eta \nabla_\theta \boldsymbol{J}(\boldsymbol{\theta})\
&\boldsymbol{v}{2}=\gamma \boldsymbol{v}{1}+\eta \nabla_{\theta} \boldsymbol{J}\left(\boldsymbol{\theta}-\gamma v_{1}\right)\
&\downarrow\
&\boldsymbol{v}{t}=\gamma \boldsymbol{v}{t-1}+\eta \nabla_{\theta} \boldsymbol{J}\left(\boldsymbol{\theta}-\gamma \boldsymbol{v}{t-1}\right)\\
&\boldsymbol{\theta}{new} = \boldsymbol{\theta} - v_t
\end{aligned}
\end{equation}
$$
模型参数的更新公式为：

公式中 $−\gamma \boldsymbol{v}{t-1}$ 就是图中 B 到 C 的那一段向量， $\boldsymbol{\theta}-\gamma \boldsymbol{v}{t-1}$ 就是C点的坐标（参数）。 $\gamma$ 代表衰减率， $ \eta$ 代表学习率。

（3）试验

下面两图为动量法和梯度下降法（均采用全部样本批量），其中：

  • 第一张图为Nesterov示意图，学习率 $ \eta = 0.01 $，衰减率 $\gamma = 0.9$ 。
  • 第二张图为动量法实验图，学习率 $ \eta = 0.01 $，衰减率 $\gamma = 0.9$ 。

这里写图片描述

Nesterov方法
动量法（momentum)

由图可知，NAG方法收敛速度明显加快。波动也小。实际上NAG方法用到了二阶信息，才会有这么好的结果。

此处实验源码见： https://github.com/tsycnh/mlbasic/blob/master/p5 Nesterov momentum.py

四、AdaGrad优化算法

（1）原理

上述动量优化算法有一个共同的特点，就是对于每一个参数都采用相同的学习率进行更新。但是在实际应用中各个参数的重要性有可能不一样，如果对不同参数动态地采取不同学习率，或许会让目标函数更快的收敛。AdaGrad方法即采用上述思想，在每一次迭代中，将每一个参数的梯度取平方累加再开方（即取二阶动量），用基础学习率除以该数来构造新的学习率，从而使得每一次迭代不仅动态更新模型参数，同时更新学习率。

（2）公式推导

$∇_{θ_i}J(θ)$ 表示第 $i$ 个参数的梯度，对于经典的SGD优化函数我们可以这样表示：

$$
\begin{equation}
\theta_{i,t+1}=\theta_{i,t} - \eta\nabla_{\theta_{i,t}} J(\theta)
\end{equation}
$$
而AdaGrad则引入了二阶动量，表示为下式：
$$
\begin{equation}
\theta_{i,t+1}=\theta_{i,t}- \frac{\eta}{\sqrt{G_{i,t}+\epsilon}} \nabla_{\theta_{i,t}} J(\theta)
\end{equation}
$$
其中， $\nabla_{\theta_{i,t}} J(\theta)$ 为第 $i$ 个自变量在 $t$ 时间步的梯度， $t$ 代表时间步， $\epsilon$ 一般是一个极小值，作用是防止分母为 0 。$G_{i,t}$ 表示了前 $t$ 步二阶动量的状态变量，为参数 $\theta_i$ 的梯度平方和之累加，由式可知，可见 $G$ 值是在不断累积变大的。

$$
\begin{equation}
G_{i,t} = G_{i,t-1}+ \nabla_{\theta_{i,t}} J(\theta) \odot \nabla_{\theta_{i,t}} J(\theta)
\end{equation}
$$
写成向量形式，另 $g_t = \nabla_{t} J(\theta)$ 为目标函数 $J$ 关于模型参数 $\theta$ 在第 $t$ 步的梯度向量：
$$
\begin{equation}
\begin{split}
& G_t=G_{t-1}+g_t \odot g_t\\
& \theta_{t+1}=\theta_t- \frac{\eta}{\sqrt{G_t+\epsilon}} g_t
\end{split}
\end{equation}
$$

容易看出，随着算法不断的迭代， $G_t$ 会越来越大，整体的学习率会越来越小。所以一般来说AdaGrad算法一开始是激励收敛，到了后面就慢慢变成惩罚收敛，速度越来越慢。

（3）试验

实验取 $ \eta = 0.2, \epsilon=1e-8 $ 。可以看出收敛速度的确是特别慢（在该数据集下），最重要的原因就是动态学习率处于一个单向的减小状态，最后减到近乎为0的状态。

此处实验源码见：[https://github.com/tsycnh/mlbasic/blob/master/p6AdaGrad.py](https://github.com/tsycnh/mlbasic/blob/master/p6 AdaGrad.py)

这里写图片描述

（4）特点

  • 由公式可以看出，仍依赖于人工设置一个全局学习率 $\eta$
  • $\eta$ 设置过大的话，会使正则项过于敏感，对梯度的调节太大
  • 中后期，分母上梯度平方的累加将会越来越大，即 $gradient \to 0$，使得训练提前结束

五、 RMSProp 与 AdaDelta

（1）原理

AdaGrad面临两个放方面的问题：

  • 一是由于分母中对历史梯度一直累加，学习率将逐渐下降至0，收敛速度过慢；特别是如果初始梯度很大的话，会导致整个训练过程的学习率一直很小，从而导致学习时间变长。
  • 二是需要手动指定初始学习率

为此有学者提出了 RMSProp 优化算法，以及 AdaDelta 算法，两者同年发布，具有相近之处。

其中：

  • RMSProp 采用Accumulate Over Window的基本思路，动量不再做全程累积，而是在一个设定的窗口 $w$ 中对梯度进行求和。该方法解决了第一个问题，但仍然需要手动指定初始学习率；
  • AdaDelta 采用Correct Units with Hessian Approximation的基本思路， 采用拟牛顿法，通过求解二阶近似解析解来自动计算和更新学习率。

（2） RMSProp 公式推导

  • Accumulate Over Window

AdaGrad会累加之前所有的梯度平方，而 RMSProp 只累加固定大小窗口的项，其近似计算对应的平均值（见下式），其中， $\nu$ 可视为窗口，向量表达式为：
$$
\begin{equation}
\begin{split}
&G_t = \nu G_{t-1}+(1-\nu)g_t \odot g_t \\
&\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{G_t+\epsilon}}g_t
\end{split}
\end{equation}
$$

上式中， $\eta$ 为全局学习率， $\epsilon$ 是为了维持数值稳定性而添加的常数，如$10^{-6}$。由于 RMSProp 算法的状态变量 $\boldsymbol{G}t$ 是对平方项 $\nabla{t} J(\theta) \odot \nabla_{t}J(\theta)$ 的加权移动平均，而不是全程累计，模型参数中每个元素的学习率在迭代过程中就不再一直降低。根据公式可知，Accumulate Over Window 中 AdaDelta 还是依赖于超参数全局学习率 $\eta$ 的。但由于 $G_t$ 不再全程累积，避免了分母无限制的增长，从而保证了学习率。

RMSProp 在 Tensorflow 的说明书中，被解释为比较适合循环神经网络的一种数值优化解法。

让我们先观察 RMSProp 算法对目标函数 $f(\boldsymbol{x})=0.1x_1^2+2x_2^2$ 中自变量的迭代轨迹。回忆学习率为 $0.4$ 的AdaGrad算法，自变量在迭代后期的移动幅度较小。但在同样的学习率下， RMSProp 算法可以更快逼近最优解。

（3） AdaDelta 公式推导

在 RMSProp 基础上， AdaDelta 进一步处理，经过拟牛顿法之后，给出了学习率的自动计算和更新公式 $\eta = \sqrt{\sum\limits_{r=1}^{t-1}\Delta \theta_r}$ 。

AdaDelta 的完整数学公式如下：

$$
\begin{equation}
\begin{split}
&G_t = \nu G_{t-1}+(1-\nu)g_t \odot g_t \\
&\Delta\theta_t=\frac{\sqrt{\sum\limits_{r=1}^{t-1}\Delta \theta_r}}{\sqrt{G_t+\epsilon}}g_t\\
&\theta_{t+1}=\theta_t-\Delta\theta_t
\end{split}
\end{equation}
$$

可见， AdaDelta 已经不用依赖于全局学习率了。

特点：

  • 动量累积都在时间窗口 $w$ 进行
  • 自动计算学习率，无需人工指定超参数
  • 由于 $\frac{\sqrt{\sum\limits_{r=1}^{t-1}\Delta x_r}}{\sqrt{G_t+\epsilon}}$ 永远为正，所以能保证更新的方向一直为梯度的负方向
  • 分子是加速项，且和动量同步在时间窗口 $w$ 上进行梯度积累，避免了AdaGrad学习率一直下降的问题