【深度学习笔记】优化算法——AdaGrad算法

AdaGrad算法

🏷sec_adagrad

我们从有关特征学习中并不常见的问题入手。

稀疏特征和学习率

假设我们正在训练一个语言模型。
为了获得良好的准确性，我们大多希望在训练的过程中降低学习率，速度通常为 O ( t − 1 2 ) \mathcal{O}(t^{-\frac{1}{2}}) O(t−21​)或更低。
现在讨论关于稀疏特征（即只在偶尔出现的特征）的模型训练，这对自然语言来说很常见。
例如，我们看到“预先条件”这个词比“学习”这个词的可能性要小得多。
但是，它在计算广告学和个性化协同过滤等其他领域也很常见。

只有在这些不常见的特征出现时，与其相关的参数才会得到有意义的更新。
鉴于学习率下降，我们可能最终会面临这样的情况：常见特征的参数相当迅速地收敛到最佳值，而对于不常见的特征，我们仍缺乏足够的观测以确定其最佳值。
换句话说，学习率要么对于常见特征而言降低太慢，要么对于不常见特征而言降低太快。

解决此问题的一个方法是记录我们看到特定特征的次数，然后将其用作调整学习率。
即我们可以使用大小为 η i = η 0 s ( i , t ) + c \eta_i = \frac{\eta_0}{\sqrt{s(i, t) + c}} ηi​=s(i,t)+c ​η0​​的学习率，而不是 η = η 0 t + c \eta = \frac{\eta_0}{\sqrt{t + c}} η=t+c ​η0​​。
在这里 s ( i , t ) s(i, t) s(i,t)计下了我们截至 t t t时观察到功能 i i i的次数。
这其实很容易实施且不产生额外损耗。

AdaGrad算法 :cite:Duchi.Hazan.Singer.2011通过将粗略的计数器 s ( i , t ) s(i, t) s(i,t)替换为先前观察所得梯度的平方之和来解决这个问题。
它使用 s ( i , t + 1 ) = s ( i , t ) + ( ∂ i f ( x ) ) 2 s(i, t+1) = s(i, t) + \left(\partial_i f(\mathbf{x})\right)^2 s(i,t+1)=s(i,t)+(∂i​f(x))2来调整学习率。
这有两个好处：首先，我们不再需要决定梯度何时算足够大。
其次，它会随梯度的大小自动变化。通常对应于较大梯度的坐标会显著缩小，而其他梯度较小的坐标则会得到更平滑的处理。
在实际应用中，它促成了计算广告学及其相关问题中非常有效的优化程序。
但是，它遮盖了AdaGrad固有的一些额外优势，这些优势在预处理环境中很容易被理解。

预处理

凸优化问题有助于分析算法的特点。
毕竟对大多数非凸问题来说，获得有意义的理论保证很难，但是直觉和洞察往往会延续。
让我们来看看最小化 f ( x ) = 1 2 x ⊤ Q x + c ⊤ x + b f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} + \mathbf{c}^\top \mathbf{x} + b f(x)=21​x⊤Qx+c⊤x+b这一问题。

正如在 :numref:sec_momentum中那样，我们可以根据其特征分解 Q = U ⊤ Λ U \mathbf{Q} = \mathbf{U}^\top \boldsymbol{\Lambda} \mathbf{U} Q=U⊤ΛU重写这个问题，来得到一个简化得多的问题，使每个坐标都可以单独解出：

f ( x ) = f ˉ ( x ˉ ) = 1 2 x ˉ ⊤ Λ x ˉ + c ˉ ⊤ x ˉ + b . f(\mathbf{x}) = \bar{f}(\bar{\mathbf{x}}) = \frac{1}{2} \bar{\mathbf{x}}^\top \boldsymbol{\Lambda} \bar{\mathbf{x}} + \bar{\mathbf{c}}^\top \bar{\mathbf{x}} + b. f(x)=fˉ​(xˉ)=21​xˉ⊤Λxˉ+cˉ⊤xˉ+b.

在这里我们使用了 x = U x \mathbf{x} = \mathbf{U} \mathbf{x} x=Ux，且因此 c = U c \mathbf{c} = \mathbf{U} \mathbf{c} c=Uc。
修改后优化器为 x ˉ = − Λ − 1 c ˉ \bar{\mathbf{x}} = -\boldsymbol{\Lambda}^{-1} \bar{\mathbf{c}} xˉ=−Λ−1cˉ且最小值为 − 1 2 c ˉ ⊤ Λ − 1 c ˉ + b -\frac{1}{2} \bar{\mathbf{c}}^\top \boldsymbol{\Lambda}^{-1} \bar{\mathbf{c}} + b −21​cˉ⊤Λ−1cˉ+b。
这样更容易计算，因为 Λ \boldsymbol{\Lambda} Λ是一个包含 Q \mathbf{Q} Q特征值的对角矩阵。

如果稍微扰动 c \mathbf{c} c，我们会期望在 f f f的最小化器中只产生微小的变化。
遗憾的是，情况并非如此。
虽然 c \mathbf{c} c的微小变化导致了 c ˉ \bar{\mathbf{c}} cˉ同样的微小变化，但 f f f的（以及 f ˉ \bar{f} fˉ​的）最小化器并非如此。
每当特征值 Λ i \boldsymbol{\Lambda}_i Λi​很大时，我们只会看到 x ˉ i \bar{x}_i xˉi​和 f ˉ \bar{f} fˉ​的最小值发声微小变化。
相反，对小的 Λ i \boldsymbol{\Lambda}_i Λi​来说， x ˉ i \bar{x}_i xˉi​的变化可能是剧烈的。
最大和最小的特征值之比称为优化问题的条件数（condition number）。

κ = Λ 1 Λ d . \kappa = \frac{\boldsymbol{\Lambda}_1}{\boldsymbol{\Lambda}_d}. κ=Λd​Λ1​​.

如果条件编号 κ \kappa κ很大，准确解决优化问题就会很难。
我们需要确保在获取大量动态的特征值范围时足够谨慎：难道我们不能简单地通过扭曲空间来“修复”这个问题，从而使所有特征值都是 1 1 1？
理论上这很容易：我们只需要 Q \mathbf{Q} Q的特征值和特征向量即可将问题从 x \mathbf{x} x整理到 z : = Λ 1 2 U x \mathbf{z} := \boldsymbol{\Lambda}^{\frac{1}{2}} \mathbf{U} \mathbf{x} z:=Λ21​Ux中的一个。
在新的坐标系中， x ⊤ Q x \mathbf{x}^\top \mathbf{Q} \mathbf{x} x⊤Qx可以被简化为 ∥ z ∥ 2 \|\mathbf{z}\|^2 ∥z∥2。
可惜，这是一个相当不切实际的想法。
一般而言，计算特征值和特征向量要比解决实际问题“贵”得多。

虽然准确计算特征值可能会很昂贵，但即便只是大致猜测并计算它们，也可能已经比不做任何事情好得多。
特别是，我们可以使用 Q \mathbf{Q} Q的对角线条目并相应地重新缩放它。
这比计算特征值开销小的多。

Q ~ = d i a g − 1 2 ( Q ) Q d i a g − 1 2 ( Q ) . \tilde{\mathbf{Q}} = \mathrm{diag}^{-\frac{1}{2}}(\mathbf{Q}) \mathbf{Q} \mathrm{diag}^{-\frac{1}{2}}(\mathbf{Q}). Q~​=diag−21​(Q)Qdiag−21​(Q).

在这种情况下，我们得到了 Q ~ i j = Q i j / Q i i Q j j \tilde{\mathbf{Q}}_{ij} = \mathbf{Q}_{ij} / \sqrt{\mathbf{Q}_{ii} \mathbf{Q}_{jj}} Q~​ij​=Qij​/Qii​Qjj​ ​，特别注意对于所有 i i i， Q ~ i i = 1 \tilde{\mathbf{Q}}_{ii} = 1 Q~​ii​=1。
在大多数情况下，这大大简化了条件数。
例如我们之前讨论的案例，它将完全消除眼下的问题，因为问题是轴对齐的。

遗憾的是，我们还面临另一个问题：在深度学习中，我们通常情况甚至无法计算目标函数的二阶导数：对于 x ∈ R d \mathbf{x} \in \mathbb{R}^d x∈Rd，即使只在小批量上，二阶导数可能也需要 O ( d 2 ) \mathcal{O}(d^2) O(d2)空间来计算，导致几乎不可行。
AdaGrad算法巧妙的思路是，使用一个代理来表示黑塞矩阵（Hessian）的对角线，既相对易于计算又高效。

为了了解它是如何生效的，让我们来看看 f ˉ ( x ˉ ) \bar{f}(\bar{\mathbf{x}}) fˉ​(xˉ)。
我们有

∂ x ˉ f ˉ ( x ˉ ) = Λ x ˉ + c ˉ = Λ ( x ˉ − x ˉ 0 ) , \partial_{\bar{\mathbf{x}}} \bar{f}(\bar{\mathbf{x}}) = \boldsymbol{\Lambda} \bar{\mathbf{x}} + \bar{\mathbf{c}} = \boldsymbol{\Lambda} \left(\bar{\mathbf{x}} - \bar{\mathbf{x}}_0\right), ∂xˉ​fˉ​(xˉ)=Λxˉ+cˉ=Λ(xˉ−xˉ0​),

其中 x ˉ 0 \bar{\mathbf{x}}_0 xˉ0​是 f ˉ \bar{f} fˉ​的优化器。
因此，梯度的大小取决于 Λ \boldsymbol{\Lambda} Λ和与最佳值的差值。
如果 x ˉ − x ˉ 0 \bar{\mathbf{x}} - \bar{\mathbf{x}}_0 xˉ−xˉ0​没有改变，那这就是我们所求的。
毕竟在这种情况下，梯度 ∂ x ˉ f ˉ ( x ˉ ) \partial_{\bar{\mathbf{x}}} \bar{f}(\bar{\mathbf{x}}) ∂xˉ​fˉ​(xˉ)的大小就足够了。
由于AdaGrad算法是一种随机梯度下降算法，所以即使是在最佳值中，我们也会看到具有非零方差的梯度。
因此，我们可以放心地使用梯度的方差作为黑塞矩阵比例的廉价替代。
详尽的分析（要花几页解释）超出了本节的范围，请读者参考 :cite:Duchi.Hazan.Singer.2011。

算法

让我们接着上面正式开始讨论。
我们使用变量 s t \mathbf{s}_t st​来累加过去的梯度方差，如下所示：

g t = ∂ w l ( y t , f ( x t , w ) ) , s t = s t − 1 + g t 2 , w t = w t − 1 − η s t + ϵ ⋅ g t . \begin{aligned} \mathbf{g}_t & = \partial_{\mathbf{w}} l(y_t, f(\mathbf{x}_t, \mathbf{w})), \\ \mathbf{s}_t & = \mathbf{s}_{t-1} + \mathbf{g}_t^2, \\ \mathbf{w}_t & = \mathbf{w}_{t-1} - \frac{\eta}{\sqrt{\mathbf{s}_t + \epsilon}} \cdot \mathbf{g}_t. \end{aligned} gt​st​wt​​=∂w​l(yt​,f(xt​,w)),=st−1​+gt2​,=wt−1​−st​+ϵ ​η​⋅gt​.​

在这里，操作是按照坐标顺序应用。
也就是说， v 2 \mathbf{v}^2 v2有条目 v i 2 v_i^2 vi2​。
同样， 1 v \frac{1}{\sqrt{v}} v ​1​有条目 1 v i \frac{1}{\sqrt{v_i}} vi​ ​1​，
并且 u ⋅ v \mathbf{u} \cdot \mathbf{v} u⋅v有条目 u i v i u_i v_i ui​vi​。
与之前一样， η \eta η是学习率， ϵ \epsilon ϵ是一个为维持数值稳定性而添加的常数，用来确保我们不会除以 0 0 0。
最后，我们初始化 s 0 = 0 \mathbf{s}_0 = \mathbf{0} s0​=0。

就像在动量法中我们需要跟踪一个辅助变量一样，在AdaGrad算法中，我们允许每个坐标有单独的学习率。
与SGD算法相比，这并没有明显增加AdaGrad的计算代价，因为主要计算用在 l ( y t , f ( x t , w ) ) l(y_t, f(\mathbf{x}_t, \mathbf{w})) l(yt​,f(xt​,w))及其导数。

请注意，在 s t \mathbf{s}_t st​中累加平方梯度意味着 s t \mathbf{s}_t st​基本上以线性速率增长（由于梯度从最初开始衰减，实际上比线性慢一些）。
这产生了一个学习率 O ( t − 1 2 ) \mathcal{O}(t^{-\frac{1}{2}}) O(t−21​)，但是在单个坐标的层面上进行了调整。
对于凸问题，这完全足够了。
然而，在深度学习中，我们可能希望更慢地降低学习率。
这引出了许多AdaGrad算法的变体，我们将在后续章节中讨论它们。
眼下让我们先看看它在二次凸问题中的表现如何。
我们仍然以同一函数为例：

f ( x ) = 0.1 x 1 2 + 2 x 2 2 . f(\mathbf{x}) = 0.1 x_1^2 + 2 x_2^2. f(x)=0.1x12​+2x22​.

我们将使用与之前相同的学习率来实现AdaGrad算法，即 η = 0.4 \eta = 0.4 η=0.4。
可以看到，自变量的迭代轨迹较平滑。
但由于 s t \boldsymbol{s}_t st​的累加效果使学习率不断衰减，自变量在迭代后期的移动幅度较小。

%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

我们将学习率提高到 2 2 2，可以看到更好的表现。
这已经表明，即使在无噪声的情况下，学习率的降低可能相当剧烈，我们需要确保参数能够适当地收敛。

eta = 2
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))

epoch 20, x1: -0.002295, x2: -0.000000

从零开始实现

同动量法一样，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_()

与 :numref:sec_minibatch_sgd一节中的实验相比，这里使用更大的学习率来训练模型。

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.242, 0.012 sec/epoch

简洁实现

我们可直接使用深度学习框架中提供的AdaGrad算法来训练模型。

trainer = torch.optim.Adagrad
d2l.train_concise_ch11(trainer, {'lr': 0.1}, data_iter)

loss: 0.242, 0.013 sec/epoch

小结

• AdaGrad算法会在单个坐标层面动态降低学习率。
• AdaGrad算法利用梯度的大小作为调整进度速率的手段：用较小的学习率来补偿带有较大梯度的坐标。
• 在深度学习问题中，由于内存和计算限制，计算准确的二阶导数通常是不可行的。梯度可以作为一个有效的代理。
• 如果优化问题的结构相当不均匀，AdaGrad算法可以帮助缓解扭曲。
• AdaGrad算法对于稀疏特征特别有效，在此情况下由于不常出现的问题，学习率需要更慢地降低。
• 在深度学习问题上，AdaGrad算法有时在降低学习率方面可能过于剧烈。我们将在 :numref:sec_adam一节讨论缓解这种情况的策略。