12.7. Adagrad¶ 在 SageMaker Studio Lab 中打开 Notebook
让我们从一个有关特征学习的问题开始，这些特征的出现频率有着天壤之别。
12.7.1. 稀疏特征和学习率¶
假设我们正在训练一个语言模型。为了获得良好的精度，我们通常希望在训练过程中降低学习率，速率通常为\(\mathcal{O}(t^{-\frac{1}{2}})\)或更慢。现在讨论关于稀疏特征（即只在偶尔出现的特征）的模型训练，这在自然语言处理中很常见。例如，我们看到“预处理”这个词比“学习”这个词的可能性要小得多。然而，这种情况在其他领域也很常见，例如计算广告学和个性化协同过滤。毕竟，有许多事物只在少数人感兴趣。
对于不常见的特征，相关参数仅在这些特征出现时才会接收有意义的更新。鉴于学习率不断下降，我们可能会面临这样的情况：常见特征的参数相当迅速地收敛到最佳值，而对于不常见的特征，我们仍需要当足够多的数据出现后，才能确定合适的参数值。换句话说，学习率要么对于常见特征而言降低太慢，要么对于不常见特征而言降低太快。
解决此问题的一个方法是记录我们看到特定特征的次数，然后将其用作调整学习率的时钟。也就是说，我们不是选择学习率\(\eta = \frac{\eta_0}{\sqrt{t + c}}\)，而是使用\(\eta_i = \frac{\eta_0}{\sqrt{s(i, t) + c}}\)。在这里\(s(i, t)\)计下了我们截至\(t\)时观察到功能\(i\)的次数。这其实很容易实现，而且开销很小。然而，它失败了，因为每当数据不那么稀疏时，梯度可能经常很小，只是偶尔很大。毕竟，我们不清楚某个特征何时算作真正的观测值。
Duchi等人 (2011)提出的Adagrad算法，通过将粗略的计数器\(s(i, t)\)替换为先前观察所得梯度的平方和来解决这个问题。它使用\(s(i, t+1) = s(i, t) + \left(\partial_i f(\mathbf{x})\right)^2\)来调整学习率。这有两个好处：首先，我们不再需要决定梯度何时算足够大。其次，它会随梯度的大小自动缩放。通常对应于较大梯度的坐标会显著缩小，而其他梯度较小的坐标会得到更温和的处理。在实践中，它导致了计算广告学及其相关问题的一个非常有效的优化过程。但它隐藏了Adagrad固有的额外好处，这些好处在预处理环境中很容易被理解。
12.7.2. 预处理器¶
凸优化问题是分析算法特性的好工具。毕竟，对于大多数非凸问题，很难推导出有意义的理论保证，但直觉和洞察力往往延续。让我们来看看最小化\(f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} + \mathbf{c}^\top \mathbf{x} + b\)的问题。
正如我们在12.6节中看到的那样，可以通过其特征分解\(\mathbf{Q} = \mathbf{U}^\top \boldsymbol{\Lambda} \mathbf{U}\)来重写此问题，以达到一个非常简化的目的，其中每个坐标都可以单独求解：
在这里我们使用了\(\bar{\mathbf{x}} = \mathbf{U} \mathbf{x}\)，因此\(\bar{\mathbf{c}} = \mathbf{U} \mathbf{c}\)。修改后问题的最小化器为\(\bar{\mathbf{x}} = -\boldsymbol{\Lambda}^{-1} \bar{\mathbf{c}}\)，最小值为\(-\frac{1}{2} \bar{\mathbf{c}}^\top \boldsymbol{\Lambda}^{-1} \bar{\mathbf{c}} + b\)。这要容易计算得多，因为\(\boldsymbol{\Lambda}\)是一个包含\(\mathbf{Q}\)的特征值的对角矩阵。
如果我们稍微扰动\(\mathbf{c}\)，我们会期望在\(f\)的最小化器中只看到微小的变化。不幸的是，情况并非如此。虽然\(\mathbf{c}\)的微小变化会导致\(\bar{\mathbf{c}}\)同样发生微小变化，但这并不是\(f\)（以及\(\bar{f}\)）的最小化器的情况。每当特征值\(\boldsymbol{\Lambda}_i\)很大时，我们只会在\(\bar{x}_i\)和\(\bar{f}\)的最小值中看到微小的变化。相反，对于\(\boldsymbol{\Lambda}_i\)较小的\(\bar{x}_i\)的变化可能是剧烈的。最大和最小特征值之比称为优化问题的条件数（condition number）。
如果条件数\(\kappa\)很大，就很难准确地解决优化问题。我们需要确保我们对值的动态范围有相当的把握。我们的分析提出了一个显而易见但有点天真的问题：我们能不能通过扭曲空间来“修复”这个问题，从而使所有特征值都是\(1\)？理论上，这很容易：我们只需要\(\mathbf{Q}\)的特征值和特征向量，就可以将问题从\(\mathbf{x}\)重新缩放到\(\mathbf{z} \stackrel{\textrm{def}}{=} \boldsymbol{\Lambda}^{\frac{1}{2}} \mathbf{U} \mathbf{x}\)中的一个。在新的坐标系中，\(\mathbf{x}^\top \mathbf{Q} \mathbf{x}\)可以简化为\(\|\mathbf{z}\|^2\)。可惜，这是一个不切实际的建议。计算特征值和特征向量通常比解决问题本身要昂贵得多。
虽然精确计算特征值可能代价高昂，但猜测并粗略计算它们可能已经比完全不做任何事情要好得多。特别地，我们可以使用\(\mathbf{Q}\)的对角线条目并相应地重新缩放它。这比计算特征值开销小得多。
在这种情况下，我们有\(\tilde{\mathbf{Q}}_{ij} = \mathbf{Q}_{ij} / \sqrt{\mathbf{Q}_{ii} \mathbf{Q}_{jj}}\)，特别地，对于所有\(i\)，\(\tilde{\mathbf{Q}}_{ii} = 1\)。在大多数情况下，这大大简化了条件数。例如，我们前面讨论的案例，由于问题是轴对齐的，这可以完全消除问题。
不幸的是，我们还面临另一个问题：在深度学习中，我们通常甚至无法访问目标函数的二阶导数：对于\(\mathbf{x} \in \mathbb{R}^d\)，即使在小批量上，二阶导数也可能需要\(\mathcal{O}(d^2)\)空间和工作来计算，这使得它在实践中变得不可行。Adagrad的巧妙思想是使用一个代理来表示黑塞矩阵（Hessian）难以捉摸的对角线，这个代理既相对便宜又有效——梯度的量级本身。
为了了解它的工作原理，让我们来看看\(\bar{f}(\bar{\mathbf{x}})\)。我们有
其中\(\bar{\mathbf{x}}_0\)是\(\bar{f}\)的最小化器。因此，梯度的量级取决于\(\boldsymbol{\Lambda}\)和与最优值的距离。如果\(\bar{\mathbf{x}} - \bar{\mathbf{x}}_0\)没有改变，那这就是我们所需要的一切。毕竟，在这种情况下，梯度\(\partial_{\bar{\mathbf{x}}} \bar{f}(\bar{\mathbf{x}})\)的大小就足够了。由于AdaGrad是一种随机梯度下降算法，所以即使在最优值时，我们也会看到具有非零方差的梯度。因此，我们可以安全地使用梯度的方差作为黑塞矩阵比例的廉价替代。详细的分析超出了本节的范围（将需要几页的篇幅）。我们建议读者参考Duchi等人 (2011)的论文了解详情。
12.7.3. 算法¶
让我们正式地讨论一下。我们使用变量\(\mathbf{s}_t\)来累积过去的梯度方差，如下所示。
在这里，操作是按坐标应用的。也就是说，\(\mathbf{v}^2\)有条目\(v_i^2\)。同样，\(\frac{1}{\sqrt{v}}\)有条目\(\frac{1}{\sqrt{v_i}}\)，\(\mathbf{u} \cdot \mathbf{v}\)有条目\(u_i v_i\)。和以前一样，\(\eta\)是学习率，\(\epsilon\)是一个附加的常量，以确保我们不会除以\(0\)。最后，我们初始化\(\mathbf{s}_0 = \mathbf{0}\)。
就像动量法一样，我们需要跟踪一个辅助变量，在这种情况下是每个坐标的学习率。相对于SGD，Adagrad的成本并没有显著增加，这主要是因为主要成本通常是计算\(l(y_t, f(\mathbf{x}_t, \mathbf{w}))\)及其导数。
请注意，在\(\mathbf{s}_t\)中累积平方梯度意味着\(\mathbf{s}_t\)基本上以线性速率增长（实际上比线性速率慢一些，因为梯度最初会减小）。这导致\(\mathcal{O}(t^{-\frac{1}{2}})\)的学习率，尽管是按坐标调整的。对于凸问题，这是完全足够的。然而，在深度学习中，我们可能希望学习率下降得更慢一些。这导致了许多Adagrad的变体，我们将在后续章节中讨论。现在，让我们看看它在二次凸问题中的表现。我们使用与之前相同的问题：
我们将使用与之前相同的学习率来实现Adagrad，即\(\eta = 0.4\)。正如我们所看到的，自变量的迭代轨迹更平滑。然而，由于\(\boldsymbol{s}_t\)的累积效应，学习率不断衰减，因此自变量在迭代后期移动不多。
%matplotlib inline
import math
import torch
from d2l import torch as d2l
def adagrad_2d(x1, x2, s1, s2):
eps = 1e-6
g1, g2 = 0.2 * x1, 4 * x2
s1 += g1 ** 2
s2 += g2 ** 2
x1 -= eta / math.sqrt(s1 + eps) * g1
x2 -= eta / math.sqrt(s2 + eps) * g2
return x1, x2, s1, s2
def f_2d(x1, x2):
return 0.1 * x1 ** 2 + 2 * x2 ** 2
eta = 0.4
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
epoch 20, x1: -2.382563, x2: -0.158591
%matplotlib inline
import math
from mxnet import np, npx
from d2l import mxnet as d2l
npx.set_np()
def adagrad_2d(x1, x2, s1, s2):
eps = 1e-6
g1, g2 = 0.2 * x1, 4 * x2
s1 += g1 ** 2
s2 += g2 ** 2
x1 -= eta / math.sqrt(s1 + eps) * g1
x2 -= eta / math.sqrt(s2 + eps) * g2
return x1, x2, s1, s2
def f_2d(x1, x2):
return 0.1 * x1 ** 2 + 2 * x2 ** 2
eta = 0.4
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
epoch 20, x1: -2.382563, x2: -0.158591
[22:07:35] ../src/storage/storage.cc:196: Using Pooled (Naive) StorageManager for CPU
%matplotlib inline
import math
import tensorflow as tf
from d2l import tensorflow as d2l
def adagrad_2d(x1, x2, s1, s2):
eps = 1e-6
g1, g2 = 0.2 * x1, 4 * x2
s1 += g1 ** 2
s2 += g2 ** 2
x1 -= eta / math.sqrt(s1 + eps) * g1
x2 -= eta / math.sqrt(s2 + eps) * g2
return x1, x2, s1, s2
def f_2d(x1, x2):
return 0.1 * x1 ** 2 + 2 * x2 ** 2
eta = 0.4
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
epoch 20, x1: -2.382563, x2: -0.158591
当我们将学习率提高到\(2\)时，我们看到了更好的行为。这已经表明，即使在无噪声的情况下，学习率的下降也可能相当剧烈，我们需要确保参数能够适当地收敛。
eta = 2
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
epoch 20, x1: -0.002295, x2: -0.000000
eta = 2
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
epoch 20, x1: -0.002295, x2: -0.000000
eta = 2
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
epoch 20, x1: -0.002295, x2: -0.000000
12.7.4. 从零开始实现¶
与动量法一样，Adagrad需要维护一个与参数形状相同的状态变量。
def init_adagrad_states(feature_dim):
s_w = torch.zeros((feature_dim, 1))
s_b = torch.zeros(1)
return (s_w, s_b)
def adagrad(params, states, hyperparams):
eps = 1e-6
for p, s in zip(params, states):
with torch.no_grad():
s[:] += torch.square(p.grad)
p[:] -= hyperparams['lr'] * p.grad / torch.sqrt(s + eps)
p.grad.data.zero_()
def init_adagrad_states(feature_dim):
s_w = np.zeros((feature_dim, 1))
s_b = np.zeros(1)
return (s_w, s_b)
def adagrad(params, states, hyperparams):
eps = 1e-6
for p, s in zip(params, states):
s[:] += np.square(p.grad)
p[:] -= hyperparams['lr'] * p.grad / np.sqrt(s + eps)
def init_adagrad_states(feature_dim):
s_w = tf.Variable(tf.zeros((feature_dim, 1)))
s_b = tf.Variable(tf.zeros(1))
return (s_w, s_b)
def adagrad(params, grads, states, hyperparams):
eps = 1e-6
for p, s, g in zip(params, states, grads):
s[:].assign(s + tf.math.square(g))
p[:].assign(p - hyperparams['lr'] * g / tf.math.sqrt(s + eps))
与12.5节中的实验相比，我们使用更大的学习率来训练模型。
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
d2l.train_ch11(adagrad, init_adagrad_states(feature_dim),
{'lr': 0.1}, data_iter, feature_dim);
loss: 0.243, 0.162 sec/epoch
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
d2l.train_ch11(adagrad, init_adagrad_states(feature_dim),
{'lr': 0.1}, data_iter, feature_dim);
loss: 0.243, 0.495 sec/epoch
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
d2l.train_ch11(adagrad, init_adagrad_states(feature_dim),
{'lr': 0.1}, data_iter, feature_dim);
loss: 0.243, 1.146 sec/epoch
12.7.5. 简洁实现¶
通过使用算法adagrad的Trainer实例，我们可以在Gluon中调用Adagrad算法。
trainer = torch.optim.Adagrad
d2l.train_concise_ch11(trainer, {'lr': 0.1}, data_iter)
loss: 0.242, 0.129 sec/epoch
d2l.train_concise_ch11('adagrad', {'learning_rate': 0.1}, data_iter)
loss: 0.242, 0.583 sec/epoch
trainer = tf.keras.optimizers.Adagrad
d2l.train_concise_ch11(trainer, {'learning_rate' : 0.1}, data_iter)
loss: 0.242, 1.194 sec/epoch
12.7.6. 小结¶
Adagrad在每个坐标上动态地降低学习率。
它使用梯度的量级作为调整进展速度的手段——梯度大的坐标用较小的学习率来补偿。
由于内存和计算限制，在深度学习问题中计算精确的二阶导数通常是不可行的。梯度可以作为一个有用的代理。
如果优化问题的结构相当不均匀，Adagrad可以帮助减轻扭曲。
Adagrad对于稀疏特征特别有效，其中不常出现的项的学习率需要更慢地降低。
在深度学习问题上，Adagrad有时在降低学习率方面可能过于激进。我们将在12.10节的背景下讨论减轻这种情况的策略。
12.7.7. 练习¶
证明对于一个正交矩阵\(\mathbf{U}\)和一个向量\(\mathbf{c}\)，以下成立：\(\|\mathbf{c} - \mathbf{\delta}\|_2 = \|\mathbf{U} \mathbf{c} - \mathbf{U} \mathbf{\delta}\|_2\)。为什么这意味着扰动的量级在变量的正交变化后不会改变？
对\(f(\mathbf{x}) = 0.1 x_1^2 + 2 x_2^2\)以及目标函数旋转45度的情况，即\(f(\mathbf{x}) = 0.1 (x_1 + x_2)^2 + 2 (x_1 - x_2)^2\)，尝试使用Adagrad。它的行为有何不同？
证明盖尔什戈林圆盘定理，该定理指出矩阵\(\mathbf{M}\)的特征值\(\lambda_i\)满足\(|\lambda_i - \mathbf{M}_{jj}| \leq \sum_{k \neq j} |\mathbf{M}_{jk}|\)，其中至少有一个\(j\)的选择。
盖尔什戈林圆盘定理告诉我们关于对角预处理矩阵\(\textrm{diag}^{-\frac{1}{2}}(\mathbf{M}) \mathbf{M} \textrm{diag}^{-\frac{1}{2}}(\mathbf{M})\)的特征值的什么信息？
尝试将Adagrad应用于一个真正的深度网络，例如7.6节中的LeNet，并应用于Fashion-MNIST数据集。
你需要如何修改Adagrad以实现学习率不那么激进的衰减？