12.6. 动量法¶ 在 SageMaker Studio Lab 中打开 Notebook
在 12.4节中，我们回顾了随机梯度下降（即在优化中仅使用梯度的噪声变体）时发生的情况。特别是，我们注意到，对于有噪声的梯度，在选择学习率时需要格外谨慎。如果学习率下降得太快，收敛就会停滞。如果学习率过高，我们将无法收敛到一个好的解，因为噪声会不断地将我们从最优解上推开。
12.6.1. 基础¶
在本节中，我们将探索更有效的优化算法，特别是针对实践中常见的某些类型的优化问题。
12.6.1.1. 泄露平均值¶
上一节中，我们讨论了小批量随机梯度下降是加速计算的一种方法。它还有一个很好的副作用，即平均梯度可以减少方差。小批量随机梯度下降可以通过以下方式计算：
为了简化符号，这里我们使用 \(\mathbf{h}_{i, t-1} = \partial_{\mathbf{w}} f(\mathbf{x}_i, \mathbf{w}_{t-1})\) 作为使用在时间 \(t-1\) 更新的权重的样本 \(i\) 的随机梯度下降。如果我们能从小批量梯度平均之外，进一步利用方差缩减的效果，那就更好了。完成这项任务的一个选择是用“泄露平均值”来代替梯度计算：
对于某个 \(\beta \in (0, 1)\)。这实际上是用一个在多个*过去*梯度上平均的值来代替瞬时梯度。\(\mathbf{v}\) 被称为*动量*（velocity）。它累积了过去的梯度，类似于一个重球在目标函数景观上滚动时对过去的力量进行积分。为了更详细地了解发生了什么，让我们递归地展开 \(\mathbf{v}_t\)：
大的 \(\beta\) 相当于一个长程平均，而小的 \(\beta\) 相对于梯度法只做了一个轻微的修正。新的梯度替换不再指向特定实例上的最陡下降方向，而是指向过去梯度的加权平均方向。这使我们能够在不实际计算批量梯度的情况下，实现批量平均的大部分好处。我们稍后将更详细地重新讨论这个平均过程。
上述推理构成了现在所谓的*加速*梯度法的基础，例如带动量的梯度法。它们还有一个额外的好处，即在优化问题是病态的（ill-conditioned）情况下（即在某些方向上进展比其他方向慢得多，类似于一个狭窄的峡谷），它们会更有效。此外，它们允许我们对后续梯度进行平均，以获得更稳定的下降方向。实际上，即使对于无噪声的凸问题，加速方面也是动量法起作用以及效果如此之好的关键原因之一。
正如人们所期望的，由于其有效性，动量法是深度学习及其他领域优化研究中一个被充分研究的课题。例如，请参阅 Goh (2017) 撰写的优美说明性文章，其中有深入的分析和交互式动画。它由 Polyak (1964) 提出。Nesterov (2018) 在凸优化的背景下进行了详细的理论讨论。动量法在深度学习中被认为是有益的已有很长时间。例如，请参阅 Sutskever et al. (2013) 的讨论以获取详细信息。
12.6.1.2. 一个病态问题¶
为了更好地理解动量法的几何特性，我们重新审视梯度下降，但这次使用一个明显不那么友好的目标函数。回想一下，在 12.3节 中，我们使用了 \(f(\mathbf{x}) = x_1^2 + 2 x_2^2\)，即一个中等扭曲的椭球目标函数。我们通过在 \(x_1\) 方向上拉伸它来进一步扭曲这个函数：
和以前一样，\(f\) 在 \((0, 0)\) 处有最小值。这个函数在 \(x_1\) 方向上*非常*平坦。让我们看看像以前一样对这个新函数执行梯度下降会发生什么。我们选择学习率为 \(0.4\)。
%matplotlib inline
import torch
from d2l import torch as d2l
eta = 0.4
def f_2d(x1, x2):
return 0.1 * x1 ** 2 + 2 * x2 ** 2
def gd_2d(x1, x2, s1, s2):
return (x1 - eta * 0.2 * x1, x2 - eta * 4 * x2, 0, 0)
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
epoch 20, x1: -0.943467, x2: -0.000073
%matplotlib inline
from mxnet import np, npx
from d2l import mxnet as d2l
npx.set_np()
eta = 0.4
def f_2d(x1, x2):
return 0.1 * x1 ** 2 + 2 * x2 ** 2
def gd_2d(x1, x2, s1, s2):
return (x1 - eta * 0.2 * x1, x2 - eta * 4 * x2, 0, 0)
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
epoch 20, x1: -0.943467, x2: -0.000073
[21:56:51] ../src/storage/storage.cc:196: Using Pooled (Naive) StorageManager for CPU
%matplotlib inline
import tensorflow as tf
from d2l import tensorflow as d2l
eta = 0.4
def f_2d(x1, x2):
return 0.1 * x1 ** 2 + 2 * x2 ** 2
def gd_2d(x1, x2, s1, s2):
return (x1 - eta * 0.2 * x1, x2 - eta * 4 * x2, 0, 0)
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
epoch 20, x1: -0.943467, x2: -0.000073
根据构造，\(x_2\) 方向上的梯度比水平的 \(x_1\) 方向上的梯度*大得多*，变化也快得多。因此，我们陷入了两个不受欢迎的选择之间：如果我们选择一个小的学习率，我们能确保解在 \(x_2\) 方向上不发散，但在 \(x_1\) 方向上收敛缓慢。相反，如果学习率较大，我们在 \(x_1\) 方向上进展迅速，但在 \(x_2\) 方向上发散。下面的例子说明了即使学习率从 \(0.4\) 略微增加到 \(0.6\) 后会发生什么。在 \(x_1\) 方向上的收敛性有所改善，但整体解的质量要差得多。
eta = 0.6
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
epoch 20, x1: -0.387814, x2: -1673.365109
eta = 0.6
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
epoch 20, x1: -0.387814, x2: -1673.365109
eta = 0.6
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
epoch 20, x1: -0.387814, x2: -1673.365109
12.6.1.3. 动量法¶
动量法使我们能够解决上面描述的梯度下降问题。观察上面的优化轨迹，我们可能会直觉到对过去的梯度进行平均会很有效。毕竟，在 \(x_1\) 方向上，这将聚合方向一致的梯度，从而增加我们每一步覆盖的距离。相反，在梯度振荡的 \(x_2\) 方向上，聚合梯度会因为相互抵消的振荡而减小步长。使用 \(\mathbf{v}_t\) 代替梯度 \(\mathbf{g}_t\) 得到以下更新方程：
请注意，对于 \(\beta = 0\)，我们恢复了常规的梯度下降。在深入研究数学特性之前，让我们快速看看该算法在实践中的表现。
def momentum_2d(x1, x2, v1, v2):
v1 = beta * v1 + 0.2 * x1
v2 = beta * v2 + 4 * x2
return x1 - eta * v1, x2 - eta * v2, v1, v2
eta, beta = 0.6, 0.5
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
epoch 20, x1: 0.007188, x2: 0.002553
def momentum_2d(x1, x2, v1, v2):
v1 = beta * v1 + 0.2 * x1
v2 = beta * v2 + 4 * x2
return x1 - eta * v1, x2 - eta * v2, v1, v2
eta, beta = 0.6, 0.5
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
epoch 20, x1: 0.007188, x2: 0.002553
def momentum_2d(x1, x2, v1, v2):
v1 = beta * v1 + 0.2 * x1
v2 = beta * v2 + 4 * x2
return x1 - eta * v1, x2 - eta * v2, v1, v2
eta, beta = 0.6, 0.5
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
epoch 20, x1: 0.007188, x2: 0.002553
正如我们所看到的，即使使用我们之前使用的相同学习率，动量法仍然收敛得很好。让我们看看当我们减小动量参数时会发生什么。将其减半至 \(\beta = 0.25\) 会导致一条几乎不收敛的轨迹。尽管如此，它比没有动量法时要好得多（当解发散时）。
eta, beta = 0.6, 0.25
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
epoch 20, x1: -0.126340, x2: -0.186632
eta, beta = 0.6, 0.25
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
epoch 20, x1: -0.126340, x2: -0.186632
eta, beta = 0.6, 0.25
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
epoch 20, x1: -0.126340, x2: -0.186632
请注意，我们可以将动量法与随机梯度下降相结合，特别是与小批量随机梯度下降相结合。唯一的变化是在那种情况下，我们用 \(\mathbf{g}_t\) 替换梯度 \(\mathbf{g}_{t, t-1}\)。最后，为方便起见，我们在时间 \(t=0\) 时初始化 \(\mathbf{v}_0 = 0\)。让我们看看泄露平均对更新到底做了什么。
12.6.1.4. 有效样本权重¶
回想一下，\(\mathbf{v}_t = \sum_{\tau = 0}^{t-1} \beta^{\tau} \mathbf{g}_{t-\tau, t-\tau-1}\)。在极限情况下，各项相加得到 \(\sum_{\tau=0}^\infty \beta^\tau = \frac{1}{1-\beta}\)。换句话说，我们不是在梯度下降或随机梯度下降中采取大小为 \(\eta\) 的步长，而是采取大小为 \(\frac{\eta}{1-\beta}\) 的步长，同时处理一个可能行为更好的下降方向。这是一举两得。为了说明不同 \(\beta\) 选择下权重的行为，请看下面的图表。
d2l.set_figsize()
betas = [0.95, 0.9, 0.6, 0]
for beta in betas:
x = torch.arange(40).detach().numpy()
d2l.plt.plot(x, beta ** x, label=f'beta = {beta:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
d2l.set_figsize()
betas = [0.95, 0.9, 0.6, 0]
for beta in betas:
x = np.arange(40).asnumpy()
d2l.plt.plot(x, beta ** x, label=f'beta = {beta:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
d2l.set_figsize()
betas = [0.95, 0.9, 0.6, 0]
for beta in betas:
x = tf.range(40).numpy()
d2l.plt.plot(x, beta ** x, label=f'beta = {beta:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
12.6.2. 实践中的实验¶
让我们看看动量法在实践中是如何工作的，即在一个合适的优化器中使用时。为此，我们需要一个更具可扩展性的实现。
12.6.2.1. 从零开始实现¶
与（小批量）随机梯度下降相比，动量法需要维护一组辅助变量，即速度。它的形状与梯度（以及优化问题的变量）相同。在下面的实现中，我们将这些变量称为 states。
def init_momentum_states(feature_dim):
v_w = torch.zeros((feature_dim, 1))
v_b = torch.zeros(1)
return (v_w, v_b)
def sgd_momentum(params, states, hyperparams):
for p, v in zip(params, states):
with torch.no_grad():
v[:] = hyperparams['momentum'] * v + p.grad
p[:] -= hyperparams['lr'] * v
p.grad.data.zero_()
def init_momentum_states(feature_dim):
v_w = np.zeros((feature_dim, 1))
v_b = np.zeros(1)
return (v_w, v_b)
def sgd_momentum(params, states, hyperparams):
for p, v in zip(params, states):
v[:] = hyperparams['momentum'] * v + p.grad
p[:] -= hyperparams['lr'] * v
def init_momentum_states(features_dim):
v_w = tf.Variable(tf.zeros((features_dim, 1)))
v_b = tf.Variable(tf.zeros(1))
return (v_w, v_b)
def sgd_momentum(params, grads, states, hyperparams):
for p, v, g in zip(params, states, grads):
v[:].assign(hyperparams['momentum'] * v + g)
p[:].assign(p - hyperparams['lr'] * v)
让我们看看这在实践中是如何工作的。
def train_momentum(lr, momentum, num_epochs=2):
d2l.train_ch11(sgd_momentum, init_momentum_states(feature_dim),
{'lr': lr, 'momentum': momentum}, data_iter,
feature_dim, num_epochs)
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
train_momentum(0.02, 0.5)
loss: 0.245, 0.153 sec/epoch
def train_momentum(lr, momentum, num_epochs=2):
d2l.train_ch11(sgd_momentum, init_momentum_states(feature_dim),
{'lr': lr, 'momentum': momentum}, data_iter,
feature_dim, num_epochs)
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
train_momentum(0.02, 0.5)
loss: 0.244, 1.186 sec/epoch
def train_momentum(lr, momentum, num_epochs=2):
d2l.train_ch11(sgd_momentum, init_momentum_states(feature_dim),
{'lr': lr, 'momentum': momentum}, data_iter,
feature_dim, num_epochs)
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
train_momentum(0.02, 0.5)
loss: 0.249, 1.121 sec/epoch
当我们把动量超参数 momentum 增加到 0.9 时，它相当于一个明显更大的有效样本大小 \(\frac{1}{1 - 0.9} = 10\)。我们稍微降低学习率到 \(0.01\) 来控制情况。
train_momentum(0.01, 0.9)
loss: 0.248, 0.109 sec/epoch
train_momentum(0.01, 0.9)
loss: 0.250, 1.011 sec/epoch
train_momentum(0.01, 0.9)
loss: 0.244, 1.058 sec/epoch
进一步降低学习率解决了任何非平滑优化问题。将其设置为 \(0.005\) 会产生良好的收敛特性。
train_momentum(0.005, 0.9)
loss: 0.243, 0.107 sec/epoch
train_momentum(0.005, 0.9)
loss: 0.247, 1.103 sec/epoch
train_momentum(0.005, 0.9)
loss: 0.245, 1.057 sec/epoch
12.6.2.2. 简洁实现¶
在Gluon中几乎没有什么可做的，因为标准的 sgd 求解器已经内置了动量。设置匹配的参数会产生一个非常相似的轨迹。
trainer = torch.optim.SGD
d2l.train_concise_ch11(trainer, {'lr': 0.005, 'momentum': 0.9}, data_iter)
loss: 0.250, 0.108 sec/epoch
d2l.train_concise_ch11('sgd', {'learning_rate': 0.005, 'momentum': 0.9},
data_iter)
loss: 0.242, 0.835 sec/epoch
trainer = tf.keras.optimizers.SGD
d2l.train_concise_ch11(trainer, {'learning_rate': 0.005, 'momentum': 0.9},
data_iter)
loss: 0.247, 1.220 sec/epoch
12.6.3. 理论分析¶
到目前为止，\(f(x) = 0.1 x_1^2 + 2 x_2^2\) 的二维例子似乎相当刻意。我们现在将看到，这实际上很能代表我们可能遇到的问题类型，至少在最小化凸二次目标函数的情况下是这样。
12.6.3.1. 二次凸函数¶
考虑函数
这是一个一般的二次函数。对于正定矩阵 \(\mathbf{Q} \succ 0\)，即具有正特征值的矩阵，它在 \(\mathbf{x}^* = -\mathbf{Q}^{-1} \mathbf{c}\) 处有一个最小值，最小值为 \(b - \frac{1}{2} \mathbf{c}^\top \mathbf{Q}^{-1} \mathbf{c}\)。因此我们可以将 \(h\) 重写为
梯度由 \(\partial_{\mathbf{x}} h(\mathbf{x}) = \mathbf{Q} (\mathbf{x} - \mathbf{Q}^{-1} \mathbf{c})\) 给出。也就是说，它是由 \(\mathbf{x}\) 和最小值点之间的距离乘以 \(\mathbf{Q}\) 得到的。因此，速度也是项 \(\mathbf{Q} (\mathbf{x}_t - \mathbf{Q}^{-1} \mathbf{c})\) 的线性组合。
由于 \(\mathbf{Q}\) 是正定的，它可以分解为其特征系统 \(\mathbf{Q} = \mathbf{O}^\top \boldsymbol{\Lambda} \mathbf{O}\)，其中 \(\mathbf{O}\) 是一个正交（旋转）矩阵，\(\boldsymbol{\Lambda}\) 是一个正特征值的对角矩阵。这允许我们进行变量替换，从 \(\mathbf{x}\) 变为 \(\mathbf{z} \stackrel{\textrm{def}}{=} \mathbf{O} (\mathbf{x} - \mathbf{Q}^{-1} \mathbf{c})\)，从而得到一个大大简化的表达式
这里 \(b' = b - \frac{1}{2} \mathbf{c}^\top \mathbf{Q}^{-1} \mathbf{c}\)。由于 \(\mathbf{O}\) 只是一个正交矩阵，这并不会以有意义的方式扰动梯度。用 \(\mathbf{z}\) 表示的梯度下降变为
这个表达式中的重要事实是，梯度下降在不同的特征空间之间*不混合*。也就是说，当用 \(\mathbf{Q}\) 的特征系统来表示时，优化问题是按坐标方式进行的。这也适用于
这样做，我们刚刚证明了以下定理：对于凸二次函数，带和不带冲量的梯度下降在二次矩阵的特征向量方向上分解为坐标级优化。
12.6.3.2. 标量函数¶
鉴于上述结果，让我们看看当我们最小化函数 \(f(x) = \frac{\lambda}{2} x^2\) 时会发生什么。对于梯度下降，我们有
只要 \(|1 - \eta \lambda| < 1\)，这个优化就会以指数速率收敛，因为在 \(t\) 步之后我们有 \(x_t = (1 - \eta \lambda)^t x_0\)。这显示了当我们增加学习率 \(\eta\) 直到 \(\eta \lambda = 1\) 时，收敛速度最初是如何提高的。超过这一点，情况就会发散，而对于 \(\eta \lambda > 2\)，优化问题就会发散。
lambdas = [0.1, 1, 10, 19]
eta = 0.1
d2l.set_figsize((6, 4))
for lam in lambdas:
t = torch.arange(20).detach().numpy()
d2l.plt.plot(t, (1 - eta * lam) ** t, label=f'lambda = {lam:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
lambdas = [0.1, 1, 10, 19]
eta = 0.1
d2l.set_figsize((6, 4))
for lam in lambdas:
t = np.arange(20).asnumpy()
d2l.plt.plot(t, (1 - eta * lam) ** t, label=f'lambda = {lam:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
lambdas = [0.1, 1, 10, 19]
eta = 0.1
d2l.set_figsize((6, 4))
for lam in lambdas:
t = tf.range(20).numpy()
d2l.plt.plot(t, (1 - eta * lam) ** t, label=f'lambda = {lam:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
为了分析动量情况下的收敛性，我们首先用两个标量重写更新方程：一个用于 \(x\)，一个用于速度 \(v\)。这得到
我们用 \(\mathbf{R}\) 来表示控制收敛行为的 \(2 \times 2\) 矩阵。在 \(t\) 步之后，初始选择 \([v_0, x_0]\) 变为 \(\mathbf{R}(\beta, \eta, \lambda)^t [v_0, x_0]\)。因此，收敛速度取决于 \(\mathbf{R}\) 的特征值。请参阅 Goh (2017) 的 Distill 帖子以获得精彩的动画，以及 Flammarion and Bach (2015) 进行的详细分析。可以证明，当 \(0 < \eta \lambda < 2 + 2 \beta\) 时，速度会收敛。与梯度下降的 \(0 < \eta \lambda < 2\) 相比，这是一个更大的可行参数范围。这也表明，通常大的 \(\beta\) 值是可取的。更多的细节需要相当多的技术细节，我们建议感兴趣的读者查阅原始出版物。
12.6.4. 小结¶
动量法用过去梯度的泄露平均值来代替梯度。这显著地加速了收敛。
它对于无噪声的梯度下降和（有噪声的）随机梯度下降都是可取的。
动量法防止了优化过程的停滞，而这种情况在随机梯度下降中更容易发生。
由于对过去数据的指数级降权，有效梯度数由 \(\frac{1}{1-\beta}\) 给出。
在凸二次问题的情况下，可以对此进行详细的显式分析。
实现非常直接，但需要我们存储一个额外的状态向量（速度 \(\mathbf{v}\)）。
12.6.5. 练习¶
使用动量超参数和学习率的其他组合，观察并分析不同的实验结果。
对于有多个特征值的二次问题，即 \(f(x) = \frac{1}{2} \sum_i \lambda_i x_i^2\)，例如 \(\lambda_i = 2^{-i}\)，尝试梯度下降和动量法。绘制对于初始化 \(x_i = 1\)，\(x\) 的值如何减小。
推导 \(h(\mathbf{x}) = \frac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} + \mathbf{x}^\top \mathbf{c} + b\) 的最小值和最小值点。
当我们用动量法执行随机梯度下降时，会发生什么变化？当我们用动量法使用小批量随机梯度下降时，会发生什么？实验参数？