|
|
背景介绍
在优化算法中，动量（momentum）经常被用在梯度下降优化算法中，并被描述成以下一个形象的故事：梯度下降可以被理解为一个人沿着最陡的山坡走到最低谷处，该过程会比较慢，但是非常稳定。动量可以被视为从同一座山上滚下的重球，该重球的增加具有一定的惯性，既起到了平滑器（smoother）的作用，又起到了加速器（accelerator）的作用，抑制了下山过程中产生的震荡，并使得快速穿过狭窄的山谷（valley）、山峰（humps）、以及局部极小值（local minima）。这个描述比较形象，也没有原则性的错误，但是并不能够准确深刻地解释或说明为什么动量（momentum）会有效。实际上，动量可以被理解为另外一种较为形象而易理解的模型。其中较为经典的模型是凸二次（convex quadratic）优化模型，能够充分地重现动量的局部动力学行为，也足够简单并且具有封闭形式（closed loop）的理解方式。
从梯度下降（gradient descent）到动量引入
梯度下降算法有很多优点，易理解且有效，但是下降速度却是其较为明显的一个弊端。例如，在做优化一个足够平滑的目标函数 f(w) 过程中（为方便理解，这里暂时假设只有一个参数，即 w\in\mathbb{R} 是一维的。在多维情况下，以下公式表达同样适用），我们会采取将模型参数 w 按照一定的方向移动一小步，即
w^{k+1} = w^{k} - \alpha \nabla f(w^{k}). \tag{1}
对于一个足够小的步长，梯度下降算法能够保证在每一步迭代的单调递增，并且能够最终收敛（局部最小）。在一些弱曲率条（weak curvature）件下，甚至可以以指数速率到达该局部最优处。虽然有时候能够以指数速度下降（在理论上），但是该下降速度在实际应用中仍会感觉太慢了，特别是随着训练或迭代次数增加，下降速度会变得超级慢。
可能导致该问题的关键之一是病态曲率（pathological curvature）。病态曲率是指目标函数 f(w) 的某个部分或区间并不能被正确的缩放(scaled)，导致整个迭代过程要么在valley之间跳跃、要么以非常小的步长逐渐接近最优状态，并到达一个平衡点。但是在某些不太友好的区域，经常会导致梯度下降失败。
引入动量可以在一定程度上克服梯度下降的缺点，比如最经典的操作就是使得梯度下降的迭代具有一定的记忆功能，即
\begin{equation} \begin{split} z^{k+1} & = \beta z^{k} + \nabla f(w^{k}) \\ w^{k+1} &= w^{k} - \alpha z^{k+1}, \end{split} \end{equation} \tag{2}
可以看出，当 \beta = 0 时，该操作等同于经典的梯度下降算法；当 \beta 接近于 1 时（比如 0.9999... ），在某些情况下，迭代重新记忆了上一迭代步的速度，以使得新的目标函数能加速达到最优状态。
为了方便理解梯度下降算法，首先我们一起用数学的角度看梯度下降算法（以凸二次优化目标函数）。
梯度下降
给定一个凸二次优化目标函数，假设有 d 个参数 \left\{ w_{1}, \dots, w_{d} \right\} 需要优化
f(\boldsymbol{w}) = \frac{1}{2}\boldsymbol{w}^{\top}\mathbf{A}\boldsymbol{w} - \mathbf{b}^{\top}\boldsymbol{w}, \ \ \ \boldsymbol{w}\in \mathbb{R}^{d}, \tag{3}
且矩阵 \mathbf{A} 是对称且可逆的，我们可以得出最优解为
\boldsymbol{w}^{\ast} = \mathbf{A}^{-1}\mathbf{b}. \tag{4}
让我们从另外一个角度探讨一下为什么会有这样的一个解。
首先，我们可以对目标函数进行求解梯度，得到\nabla 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}) .\tag{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}^{\top} = \mathbf{Q} \boldsymbol{\Lambda} \mathbf{Q}^{\top}, \ \ \ \ \ \mathbf{Q} = \left[ \mathbf{q}_{1}, \dots, \mathbf{q}_{d} \right], \ \ \ \mathrm{and}\ \ \ \mathbf{Q}\mathbf{Q}^{\top} = \mathbf{I} \tag{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}^{\top}(\boldsymbol{w}^{k} - \boldsymbol{w}^{\ast}) \\ & \Downarrow \\ \mathbf{Q}^{\top} (\boldsymbol{w}^{k+1} - \boldsymbol{w}^{\ast}) & = \mathbf{Q}^{\top} (\boldsymbol{w}^{k} - \boldsymbol{w}^{\ast}) - \alpha \boldsymbol{\Lambda}\mathbf{Q}^{\top}(\boldsymbol{w}^{k} - \boldsymbol{w}^{\ast}) \\ & \Downarrow \small \mathrm{define} \ \mathbf{x}^{k} = \mathbf{Q}^{\top} (\boldsymbol{w}^{k} - \boldsymbol{w}^{\ast}) \\ \mathbf{x}^{k+1} & = \mathbf{x}^{k} - \alpha \boldsymbol{\Lambda} \mathbf{x}^{k} \end{split} \end{equation}\tag{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} \tag{8}
其中， x_{i}^{0} 为参数的初始化状态。因此，以下公式x_{i}^{k} = (1-\alpha \lambda_{i})^{k} x_{i}^{0} \tag{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} \tag{10}
这里我们注意到，公式（10）是一个梯度下降算法的闭环形式表达。换而言之，通过给定初始值 \mathbf{x}^{0}=[x_{1}^{0}, x_{2}^{0}, \dots, x_{d}^{0}] 并计算凸二次优化目标函数中矩阵 \mathbf{A} 的特征值与特征向量，可以利用迭代方法优化参数，逐渐逼近最优值。
分解误差（Error Decomposition）
针对于公式（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}\tag{11}
步长选择
以上分析给出了一个很直接的结论用于如何选择步长大小 \alpha 。为了能够保证收敛，每个 （1-\alpha\lambda_{i}） 的绝对值必须得严格小于 1 。若保证所有步长均可正常工作并收敛，需要使得步长大小满足以下条件：
\alpha\lambda_{i} \in (0, 2) \tag{12} 因此，整体收敛的速率是由最慢的误差部分来决定的，即或者是 \lambda_{1} ，或者是 \lambda_{d} ，即收敛速率 \eta(\alpha) 为
\eta(\alpha) = \max_{i} |1-\alpha \lambda_{i}| = \max \{|1-\alpha \lambda_{1}| , |1-\alpha \lambda_{d}| \} \tag{13} 另外，当 \lambda_{1} = \lambda_{d} 时，整体的收敛速率 \eta(\alpha) 达到最小。通过最小化公式（13），得到最优解
\alpha^{\ast} = \arg\min_{\alpha} \eta(\alpha) = \frac{2}{\lambda_{1} + \lambda_{d}} \tag{14} 将最优解（14）代入收敛速率，可以得到最优收敛速率为
\eta^{\ast} = \min_{\alpha} \eta(\alpha) = \frac{\lambda_{d}/\lambda_{1}-1}{\lambda_{d}/\lambda_{1}+1} \tag{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} 的鲁棒性
<hr/>参考资料：
https://distill.pub/2017/momentum/ |
|
窥视卡
雷达卡
发表于 2023-4-19 10:32
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡