利盈APP下载

为什么优化算法中的Momentum会真的有效？

发布时间：2024-07-29 14:23:26 点击量：

在优化算法中，动量（momentum）经常被用在梯度下降优化算法中，并被描述成以下一个形象的故事：梯度下降可以被理解为一个人沿着最陡的山坡走到最低谷处，该过程会比较慢，但是非常稳定。动量可以被视为从同一座山上滚下的重球，该重球的增加具有一定的惯性，既起到了平滑器（smoother）的作用，又起到了加速器（accelerator）的作用，抑制了下山过程中产生的震荡，并使得快速穿过狭窄的山谷（valley）、山峰（humps）、以及局部极小值（local minima）。这个描述比较形象，也没有原则性的错误，但是并不能够准确深刻地解释或说明为什么动量（momentum）会有效。实际上，动量可以被理解为另外一种较为形象而易理解的模型。其中较为经典的模型是凸二次（convex quadratic）优化模型，能够充分地重现动量的局部动力学行为，也足够简单并且具有封闭形式（closed loop）的理解方式。

梯度下降算法有很多优点，易理解且有效，但是下降速度却是其较为明显的一个弊端。例如，在做优化一个足够平滑的目标函数 $f(w)$ 过程中（为方便理解，这里暂时假设只有一个参数，即 $w\\in\\mathbb{R}$ 是一维的。在多维情况下，以下公式表达同样适用），我们会采取将模型参数 $w$ 按照一定的方向移动一小步，即

$w^{k+1}=w^{k}- \\alpha \ abla f(w^{k}). \ ag{1}$

对于一个足够小的步长，梯度下降算法能够保证在每一步迭代的单调递增，并且能够最终收敛（局部最小）。在一些弱曲率条（weak curvature）件下，甚至可以以指数速率到达该局部最优处。虽然有时候能够以指数速度下降（在理论上），但是该下降速度在实际应用中仍会感觉太慢了，特别是随着训练或迭代次数增加，下降速度会变得超级慢。

可能导致该问题的关键之一是病态曲率（pathological curvature）。病态曲率是指目标函数 $f(w)$ 的某个部分或区间并不能被正确的缩放(scaled)，导致整个迭代过程要么在valley之间跳跃、要么以非常小的步长逐渐接近最优状态，并到达一个平衡点。但是在某些不太友好的区域，经常会导致梯度下降失败。

引入动量可以在一定程度上克服梯度下降的缺点，比如最经典的操作就是使得梯度下降的迭代具有一定的记忆功能，即

$\\begin{equation}\\begin{split}z^{k+1}&=\\beta z^{k}+ \ abla f(w^{k}) \\\\ w^{k+1}&=w^{k}- \\alpha z^{k+1}, \\end{split}\\end{equation}\ ag{2}$

可以看出，当 $\\beta=0$ 时，该操作等同于经典的梯度下降算法；当 $\\beta$ 接近于 $1$ 时（比如 $0.9999...$ ），在某些情况下，迭代重新记忆了上一迭代步的速度，以使得新的目标函数能加速达到最优状态。

为了方便理解梯度下降算法，首先我们一起用数学的角度看梯度下降算法（以凸二次优化目标函数）。

给定一个凸二次优化目标函数，假设有 $d$ 个参数 $\\left\\{ w_{1}, \\dots, w_{d}\\right\\}$ 需要优化

$f(\\boldsymbol{w})=\\frac{1}{2}\\boldsymbol{w}^{\ op}\\mathbf{A}\\boldsymbol{w}- \\mathbf{b}^{\ op}\\boldsymbol{w}, \\ \\ \\ \\boldsymbol{w}\\in \\mathbb{R}^{d}, \ ag{3}$

且矩阵 $\\mathbf{A}$ 是对称且可逆的，我们可以得出最优解为

$\\boldsymbol{w}^{\\ast}=\\mathbf{A}^{-1}\\mathbf{b}. \ ag{4}$

让我们从另外一个角度探讨一下为什么会有这样的一个解。

首先，我们可以对目标函数进行求解梯度，得到 $\ abla f(\\boldsymbol{w})=\\mathbf{A}\\boldsymbol{w}- \\mathbf{b}$ ，带入经典梯度下降公式（1）中，有

$\\boldsymbol{w}^{k+1}=\\boldsymbol{w}^{k}- \\alpha ( \\mathbf{A}\\boldsymbol{w}^{k}- \\mathbf{b}) .\ ag{5}$

这里值得注意的是：所有维度的参数下降之间都是相互独立的，也就是矩阵 $\\mathbf{A}$ 的特征向量。具体而言，矩阵 $\\mathbf{A}$ 是对称矩阵，因此可以将其分解成以下

$\\mathbf{A}=\\mathbf{Q}\\begin{bmatrix}\\lambda_{1}& \\dots & 0 \\\\ 0 & \\ddots & 0 \\\\ 0 & \\dots & \\lambda_{d}\\end{bmatrix}\\mathbf{Q}^{\ op}=\\mathbf{Q}\\boldsymbol{\\Lambda}\\mathbf{Q}^{\ op}, \\ \\ \\ \\ \\ \\mathbf{Q}=\\left[ \\mathbf{q}_{1}, \\dots, \\mathbf{q}_{d}\\right], \\ \\ \\ \\mathrm{and}\\ \\ \\ \\mathbf{Q}\\mathbf{Q}^{\ op}=\\mathbf{I}\ ag{6}$

这里的 $\\{\\lambda_{i}\\}$ 是经过按照由大到小排列过的矩阵 $\\mathbf{A}$ 的特征值，即 $\\lambda_{1}<\\lambda_{2}<\\cdots<\\lambda_{d}$ ， $\\{\\mathbf{q}_{i}\\}$ 为对应的特征向量， $\\mathbf{\\Lambda}$ 为对角矩阵。

若我们将公式（5）两边均减去最优解 $\\boldsymbol{w}^{\\ast}$ ，并将 $\\mathbf{A}\\boldsymbol{w}^{\\ast}=\\mathbf{b}$ 带入公式（5）中，得到

$\\begin{equation}\\begin{split}\\boldsymbol{w}^{k+1}- \\boldsymbol{w}^{\\ast}&=\\boldsymbol{w}^{k}- \\boldsymbol{w}^{\\ast}- \\alpha (\\mathbf{A}\\boldsymbol{w}^{k}- \\mathbf{A}\\boldsymbol{w}^{\\ast}) \\\\ & \\Downarrow \\\\ \\boldsymbol{w}^{k+1}- \\boldsymbol{w}^{\\ast}&=\\boldsymbol{w}^{k}- \\boldsymbol{w}^{\\ast}- \\alpha \\mathbf{Q}\\boldsymbol{\\Lambda}\\mathbf{Q}^{\ op}(\\boldsymbol{w}^{k}- \\boldsymbol{w}^{\\ast}) \\\\ & \\Downarrow \\\\ \\mathbf{Q}^{\ op}(\\boldsymbol{w}^{k+1}- \\boldsymbol{w}^{\\ast}) &=\\mathbf{Q}^{\ op}(\\boldsymbol{w}^{k}- \\boldsymbol{w}^{\\ast}) - \\alpha \\boldsymbol{\\Lambda}\\mathbf{Q}^{\ op}(\\boldsymbol{w}^{k}- \\boldsymbol{w}^{\\ast}) \\\\ & \\Downarrow \\small \\mathrm{define}\\ \\mathbf{x}^{k}=\\mathbf{Q}^{\ op}(\\boldsymbol{w}^{k}- \\boldsymbol{w}^{\\ast}) \\\\ \\mathbf{x}^{k+1}&=\\mathbf{x}^{k}- \\alpha \\boldsymbol{\\Lambda}\\mathbf{x}^{k}\\end{split}\\end{equation}\ ag{7}$

其中， $\\mathbf{x}$ 与 $\\boldsymbol{w}$ 具有相同的维度，即 $\\mathbf{x}\\in \\mathbb{R}^{d}$ 。这里注意到，公式（7）是得到的在 $\\mathbf{x}$ 参数空间下的表达，给出了参数从迭代步 $k$ 到 $k+1$ 的过程。由于 $\\mathbf{\\Lambda}$ 是对角矩阵，且对角各个元素相互独立，因此可以独立的计算参数 $\\mathbf{x}=[x_{1}, \\dots, x_{d}]$ 中任意元素如下

$\\begin{equation}\\begin{split}x_{i}^{k+1}&=x_{i}^{k}- \\alpha \\lambda_{i}x_{i}^{k}, \\ \\ \\ \\forall i=1, 2, \\dots, d \\\\ &=(1 - \\alpha \\lambda_{i})\\color{red}{x_{i}^{k}}\\\\ &=(1-\\alpha \\lambda_{i})\\color{red}{(1-\\alpha\\lambda_{i})x_{i}^{k-1}}\\\\ & \\ \\ \\vdots \\\\ &=(1-\\alpha \\lambda_{i})^{k+1}x_{i}^{0}\\end{split}\\end{equation}\ ag{8}$

其中， $x_{i}^{0}$ 为参数的初始化状态。因此，以下公式 $x_{i}^{k}=(1-\\alpha \\lambda_{i})^{k}x_{i}^{0}\ ag{9}$ 成立。将在 $\\mathbf{x}$ 空间下转换回到原始的 $\\boldsymbol{w}$ 空间下，我们可以得到

$\\boldsymbol{w}^{k}- \\boldsymbol{w}^{\\ast}=\\mathbf{Q}\\mathbf{x}^{k}=[\\mathbf{q}_{1}, \\mathbf{q}_{2}, \\dots, \\mathbf{q}_{d},]\\begin{bmatrix}x_{1}^{k}\\\\ x_{2}^{k}\\\\ \\vdots \\\\ x_{d}^{k}\\end{bmatrix}=\\sum_{i=1}^{d}x_{i}^{k}\\mathbf{q}_{i}=\\sum_{i=1}^{d}x_{i}^{0}(1-\\alpha\\lambda_{i})^{k}\\mathbf{q}_{i}\ ag{10}$

这里我们注意到，公式（10）是一个梯度下降算法的闭环形式表达。换而言之，通过给定初始值 $\\mathbf{x}^{0}=[x_{1}^{0}, x_{2}^{0}, \\dots, x_{d}^{0}]$ 并计算凸二次优化目标函数中矩阵 $\\mathbf{A}$ 的特征值与特征向量，可以利用迭代方法优化参数，逐渐逼近最优值。

针对于公式（10）而言，可以有一个比较简单的解释或理解：参数初始状态的每一个元素 $x_{i}^{0}$ 可以被看作是基于 $\\mathbf{Q}$ 基的一个初始猜测误差，该误差表示猜测结果到最优参数值的距离大小，共有 $d$ 个这样的误差，且每一个误差之间都是相互独立的，并且以 $(1-\\alpha \\lambda_{i})$ 复合率程指数下降，其中， $(1-\\alpha \\lambda_{i})$ 越接近 $0$ ，下降越快；反之，越接近 $1$ ，下降越慢。

通过分析公式（10），得知：对大部分步长 $\\alpha$ 而言，较大特征值对应的特征向量收敛的会快一些。这会在最初的几次迭代中出现爆炸式下降，然后随着较小的特征向量出现，迭代收敛速度会变慢。

回顾一下优化目标函数（3），我们可以将损失函数误差记为

$f(\\boldsymbol{w}^{k}) - f(\\boldsymbol{w}^{\\ast})=\\sum_{i=1}^{d}(1-\\alpha \\lambda_{i})^{2k}\\lambda_{i}(x_{i}^{0})^{2}\ ag{11}$

以上分析给出了一个很直接的结论用于如何选择步长大小 $\\alpha$ 。为了能够保证收敛，每个 $（1-\\alpha\\lambda_{i}）$ 的绝对值必须得严格小于 $1$ 。若保证所有步长均可正常工作并收敛，需要使得步长大小满足以下条件：

$\\alpha\\lambda_{i}\\in (0, 2) \ ag{12}$ 因此，整体收敛的速率是由最慢的误差部分来决定的，即或者是 $\\lambda_{1}$ ，或者是 $\\lambda_{d}$ ，即收敛速率 $\\eta(\\alpha)$ 为

$\\eta(\\alpha)=\\max_{i}|1-\\alpha \\lambda_{i}|=\\max \\{|1-\\alpha \\lambda_{1}| , |1-\\alpha \\lambda_{d}| \\}\ ag{13}$ 另外，当 $\\lambda_{1}=\\lambda_{d}$ 时，整体的收敛速率 $\\eta(\\alpha)$ 达到最小。通过最小化公式（13），得到最优解

$\\alpha^{\\ast}=\\arg\\min_{\\alpha}\\eta(\\alpha)=\\frac{2}{\\lambda_{1}+ \\lambda_{d}}\ ag{14}$ 将最优解（14）代入收敛速率，可以得到最优收敛速率为

$\\eta^{\\ast}=\\min_{\\alpha}\\eta(\\alpha)=\\frac{\\lambda_{d}/\\lambda_{1}-1}{\\lambda_{d}/\\lambda_{1}+1}\ ag{15}$ 值得指出的是，特征值 $\\lambda_{1}, \\lambda_{d}$ 之间的比值 $\\lambda_{d}/\\lambda_{1}$ 决定了整个优化问题的收敛速率，该比值也叫做条件值（condition number）记为 $\\kappa=\\frac{\\lambda_{d}}{\\lambda_{1}}$ 。该处特征值的比值 $\\kappa$ 不仅可以用来衡量梯度下降收敛速度的快慢或好坏（比如当 $\\kappa=1$ 时，可以实现1步迭代即可收敛），还有很多其他含义和解释：

（i）可以解释一个给定矩阵 $\\mathbf{A}$ 的奇异性

（ii）可以度量 $\\mathbf{A}^{-1}\\mathbf{b}$ 相对于 $\\mathbf{b}$ 的鲁棒性

参考资料：

https://distill.pub/2017/momentum/

上一篇：营销人必备网站：6大类，41个网站

下一篇：从零写CRNN文字识别 —— （5）优化器和Loss