深度学习笔记之优化算法(四)Nesterov动量方法的简单认识

引言

上一节对动量法进行了简单认识，本节将介绍$\text{Nesterov}$动量方法。

回顾：梯度下降法与动量法

关于梯度下降法的迭代步骤描述如下：
$$\theta \Leftarrow \theta -\eta \cdot {\nabla }_{\theta }\mathcal{J}(\theta )$$
以标准二次型$f(x)=x^T\mathcal{Q}x,\mathcal{Q}=\left(\begin{array}{c}0.50\\ 020\end{array}\right),x=(x_1,x_2{)}^T$为目标函数，使用梯度下降法求解目标函数$f(x)$最小值的迭代过程如下：

很明显，由于$\mathcal{Q}$的原因，导致在算法迭代过程中，迭代更新点对应的$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(\cdot )$中的条件数都较大，从而使梯度下降法在该凸二次函数中的收敛速度沿着次线性收敛的方向退化，这也是图像中迭代路径震荡、折叠严重的主要原因。

这里仅观察少量几次迭代步骤，见下面局部图：

其中红色线表示梯度下降法在迭代过程中的更新方向；以第一次迭代的更新方向为例，将该方向进行分解，可以得到上述两个方向分量。
由于目标函数$f(x)$中$x$是一个二维向量，因而在上图中的蓝色箭头分别描述了该方向在$x_1,x_2$正交基上的分量。

从上述两个分量可以看出：

• 关于横轴分量，它一直指向前方，也就是最优解的方向；
• 而造成迭代过程震荡、折叠的是纵轴分量。

综上，从观察的角度描述迭代路径震荡折叠现象严重的原因在于：横轴上的分量向前跨越的步幅很小；相比之下，纵轴上的分量上下的波动很大。针对该现象，可以得到相应的优化思路：
具体效果见下图绿色实心箭头,其中第一步红色与绿色实线箭头重合,因为在初始化过程中通常将动量向量初始化为零向量导致,这里以第二次迭代为例进行描述。图中的红色虚线表示梯度下降法当前迭代步骤在横轴、纵轴上的分量;绿色虚线则表示优化思路在当前步骤在横轴、纵轴上的分量。

• 压缩纵轴分量上的波动幅度；
• 拉伸/延长横轴分量上的步幅，从而使其更快地达到极值点；

如何从数学角度达到这样的效果：利用过去迭代步骤中的梯度数据，对当前迭代步骤的梯度信息进行修正。继续观察第二次迭代步骤：

在第一次迭代步骤结束后，我们得到了一个历史梯度的分量信息，即图中的蓝色虚线；在执行第二次迭代步骤时，我们需要将该步骤的梯度分量与相应的历史梯度分量执行加权运算：

• 观察纵轴分量：由于历史纵轴分量与当前纵轴分量方向相反(红色、蓝色虚线垂直箭头)，这势必会缩减当前迭代步骤的纵轴分量；
• 相反，观察横轴分量：历史横轴分量与当前横轴分量方向相同(红色、蓝色虚线横向箭头)，这必然会扩张当前迭代步骤的横轴分量；

如何对历史梯度信息进行描述，我们需要引入一个新的变量$m$，用于累积历史梯度信息：
$$\{\begin{array}{l}{m}_t=m_{t-1}+{\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1})\\ {\theta }_t={\theta }_{t-1}-\eta \cdot m_t\end{array}$$

上式的$m_t$确实达到了历史迭代步骤梯度累积的作用，但同样衍生出了新的问题：上面步骤仅是将历史梯度信息完整地存储进来，如果迭代步骤较多的情况下，由于历史信息在累积过程中没有任何的丢失，最终可能导致：迭代步骤较深时，初始迭代步骤的历史梯度信息对当前时刻梯度的更新没有参考价值。相反，有可能会给当前迭代步骤引向错误的方向。因而关于$m_t$的调整方式表示如下：
$$\{\begin{array}{l}{m}_t=\beta \cdot m_{t-1}+(1-\beta )\cdot {\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1})\\ {\theta }_t={\theta }_{t-1}-\eta \cdot m_t\end{array}$$
关于上式的迭代加权运算被称作指数加权移动平均法。假设$\beta =0.9$，关于$m_t$的表示如下：
$$\begin{array}{rl}{m}_t& =0.9\times m_{t-1}+0.1\times {\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1})\\ & =0.9\times \left[0.9\times m_{t-2}+0.1\times {\nabla }_{\theta ;t-2}\mathcal{J}({\theta }_{t-2})\right]+0.1\times {\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1})\\ & =\cdots \\ & =0.1\times 0.9^0\times {\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1})+0.1\times 0.9^1\times {\nabla }_{\theta ;t-2}\mathcal{J}({\theta }_{t-2})+0.1\times 0.9^2\times {\nabla }_{\theta ;t-3}\mathcal{J}({\theta }_{t-3})+\cdots +0.1\times 0.9^{t-1}\times {\nabla }_{\theta ;1}\mathcal{J}({\theta }_1)\end{array}$$
很明显，距离当前迭代步骤越近的梯度，其保留权重越大；反之，随着迭代步骤的推移，越靠近初始迭代步骤的梯度权重越小。
这让我想起了$\text{GRU}$神经网络~

这种方法就是动量法，也被称作冲量法。

Nesterov动量法

关于梯度下降法的优化，不仅可以像动量法一样考虑历史迭代步骤的梯度信息，实际上，我们同样可以超前参考未来的梯度信息。

关于动量法在某迭代步骤中的更新过程示例如下：

• 其中黄色结点表示动量法在迭代过程中的更新位置；淡蓝色曲线表示理想状态下的下降路径；
• 其中红色实线表示梯度下降法的更新方向；蓝色实线表示历史梯度构成的冲量信息；
  很明显，当前迭代步骤的梯度方向与更新点处更高线的切线相垂直~

假设$\beta =0.5$，图中的橘黄色虚线表示加权后真正的更新方向。我们不否认：此时动量法相比纯粹的梯度下降法，其下降路径更接近理想状态路径。两者比对效果如下：
很明显，梯度下降法不仅多使用一次迭代步骤，并且最后结果依然不及两步的动量法。

但即便动量法有更优的下降路径，但依然距离理想状态下的下降路径存在差距。

假设：在动量法执行完第一次迭代步骤前，就已经预估到了未来步骤的位置信息，那么通过未来步骤加权的第一次迭代的位置信息会进一步得到修正。从数学角度观察$\text{Nesterov}$动量法是如何实现超前参考的。回顾动量法公式：
$$\{\begin{array}{l}{m}_t=\beta \cdot m_{t-1}+(1-\beta )\cdot {\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1})\\ {\theta }_t={\theta }_{t-1}-\eta \cdot m_t\end{array}$$
其中${\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1})$表示当前迭代步骤$t$的梯度信息；而$\text{Nesterov}$动量法是将上一迭代步骤的${\theta }_{t-1}\Leftarrow {\theta }_{t-1}+\gamma \cdot m_{t-1}$，从而得到一个新时刻的未知的权重信息，并使用该信息替换${\theta }_{t-1}$参与运算：
之所以是新时刻，或者说是未来时刻，是因为当前迭代步骤的${\theta }_t$还没有被解出来，而${\theta }_{t-1}+\gamma \cdot m_{t-1}$又确实是超越了$t-1$迭代步骤的新信息。
$$\{\begin{array}{l}{m}_t=\beta \cdot m_{t-1}+(1-\beta )\cdot {\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1}+\gamma \cdot m_{t-1})\\ {\theta }_t={\theta }_{t-1}-\eta \cdot m_t\end{array}$$

继续观察上式：关于超前信息${\theta }_{t-1}+\gamma \cdot m_{t-1}$，它的格式与${\theta }_t={\theta }_{t-1}-\eta \cdot m_t$非常相似，相当于该超前信息是${\theta }_{t-1}$与$m_{t-1}$之间的加权方向。
为简化起见，这里仅描述一步:$t-1\Rightarrow t$

• 初始状态下，下图描述的是动量法的一次迭代步骤；红色实线表示${\nabla }_{\theta ;t-1}\nabla \mathcal{J}({\theta }_{t-1})$；蓝色实线表示$m_{t-1}$，中间的橙黄色虚线表示两者的加权结果$m_t=\beta \cdot m_{t-1}+(1-\beta )\cdot {\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1})$
  
• 那么超前信息${\theta }_{t-1}+\gamma \cdot m_{t-1}$如何表示$?$假设图中${\theta }_{t-1}$到红色点的长度为$\gamma \cdot m_{t-1}$，那么红色点的位置就是超前信息的位置：
  
• 至此，可以描述${\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1}+\gamma \cdot m_{t-1})$的方向：过红色点，与目标函数等高线相垂直的方向。
  图中的红色虚线表示${\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1}+\gamma \cdot m_{t-1})$的方向，仔细观察可以发现，它与${\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1})$描述的红色实线之间存在一丢丢的偏移，不是平行的~
  
• 接下来，将红色虚线替代红色实线，并得到$\text{Nesterov}$动量法中的$m_t=\beta \cdot m_{t-1}+(1-\beta )\cdot {\nabla }_{\theta ;t-1}\mathcal{J}({\theta }_{t-1}+\gamma \cdot m_{t-1})$：
  橙黄色虚线指向的红色点表示$\text{Nesterov}$动量法中的经过$\eta$修饰的$m_t$结果(这里暂定$\eta$不变的情况下)，我们仍可以看出，相比于动量法，$\text{Nesterov}$动量法在迭代过程中能够更偏向理想状态下降路径。
  

Nesterov动量法的算法过程描述

基于$\text{Nesterov}$动量法的随机梯度下降的算法步骤表示如下：
初始化操作：

• 学习率$\eta$，动量因子$\gamma$；
• 初始化参数$\theta$，初始动量$m$；

算法过程：

• $\text{While}$没有达到停止准则 $\text{do}$
• 从训练集$\mathcal{D}$中采集出包含$k$个样本的小批量：$\{(x^{(i)},y^{(i)}){\}}_{i=1}^k$；
• 应用临时的超前参数$\hat{\theta }$：
  $$\hat{\theta }\Leftarrow \theta +\gamma \cdot m$$
• 使用超前参数$\hat{\theta }$计算该位置的梯度信息：
  $$\mathcal{G}\Leftarrow \frac{1}{k}\sum _{i=1}^k{\nabla }_{\theta }\mathcal{L}[f(x^{(i)};\hat{\theta }),y^{(i)}]$$
• 计算动量更新：
  $$m\Leftarrow \gamma \cdot m-\eta \cdot \mathcal{G}$$
• 计算参数$\theta$更新：
  $$\theta \Leftarrow \theta +m$$
• $\text{End While}$

总结

观察上述算法过程，可以发现：虽然我们更新的是$\theta$，但整个算法至始至终都没有求解$\theta$的梯度：${\nabla }_{\theta }\mathcal{J}(\theta )$，也就是说：$m$中的历史信息也均是超前梯度${\nabla }_{\theta }\mathcal{J}(\theta +\gamma \cdot m)$构成的历史信息。

$\text{Reference}$：
“随机梯度下降、牛顿法、动量法、Nesterov、AdaGrad、RMSprop、Adam”，打包理解对梯度下降的优化
深度学习(花书)$\text{P182 8.3.2}$动量；$\text{8.3.3 nesterov}$动量