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

稀疏特征和学习率
假设我们正在训练一个语言模型。 为了获得良好的准确性，我们大多希望在训练的过程中降低学习率，速度通常为O(t−12)\mathcal{O}(t^{-\frac{1}{2}})O(t
−
2
1
​

)或更低。 现在讨论关于稀疏特征（即只在偶尔出现的特征）的模型训练，这对自然语言来说很常见。 例如，我们看到“预先条件”这个词比“学习”这个词的可能性要小得多。 但是，它在计算广告学和个性化协同过滤等其他领域也很常见。

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

解决此问题的一个方法是记录我们看到特定特征的次数，然后将其用作调整学习率。 即我们可以使用大小为ηi=η0s(i,t)+c\eta_i = \frac{\eta_0}{\sqrt{s(i, t) + c}}η
i
​

s(i,t)+c
​

η
0
​

​
的学习率，而不是η=η0t+c\eta = \frac{\eta_0}{\sqrt{t + c}}η=
t+c
​

η
0
​

​
。 在这里s(i,t)s(i, t)s(i,t)计下了我们截至ttt时观察到功能iii的次数。 这其实很容易实施且不产生额外损耗。

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

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

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

f(x)=fˉ(xˉ)=12xˉ⊤Λxˉ+cˉ⊤xˉ+b. (11.7.1)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.~~~~~~~~~~(11.7.1)
f(x)=
f
ˉ
​
(
x
ˉ
)=
2
1
​

x
ˉ

⊤
Λ
x
ˉ
+
c
ˉ

⊤

x
ˉ
+b. (11.7.1)

在这里我们使用了x=Ux\mathbf{x} = \mathbf{U} \mathbf{x}x=Ux，且因此c=Uc\mathbf{c} = \mathbf{U} \mathbf{c}c=Uc。 修改后优化器为xˉ=−Λ−1cˉ\bar{\mathbf{x}} = -\boldsymbol{\Lambda}^{-1} \bar{\mathbf{c}}
x
ˉ
=−Λ
−1

c
ˉ
且最小值为−12cˉ⊤Λ−1cˉ+b-\frac{1}{2} \bar{\mathbf{c}}^\top \boldsymbol{\Lambda}^{-1} \bar{\mathbf{c}} + b−
2
1
​

c
ˉ

⊤
Λ
−1

c
ˉ
+b。 这样更容易计算，因为Λ\boldsymbol{\Lambda}Λ是一个包含Q\mathbf{Q}Q特征值的对角矩阵。

如果稍微扰动c\mathbf{c}c，我们会期望在fff的最小化器中只产生微小的变化。 遗憾的是，情况并非如此。 虽然c\mathbf{c}c的微小变化导致了cˉ\bar{\mathbf{c}}
c
ˉ
同样的微小变化，但fff的（以及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. (11.7.2)\kappa = \frac{\boldsymbol{\Lambda}_1}{\boldsymbol{\Lambda}_d}.~~~~~~~~~~(11.7.2)
κ=
Λ
d
​

Λ
1
​

​
. (11.7.2)

如果条件编号κ\kappaκ很大，准确解决优化问题就会很难。 我们需要确保在获取大量动态的特征值范围时足够谨慎：我们不能简单地通过扭曲空间来“修复”这个问题，从而使所有特征值都是111？ 理论上这很容易：我们只需要Q\mathbf{Q}Q的特征值和特征向量即可将问题从x\mathbf{x}x整理到z:=Λ12Ux\mathbf{z} := \boldsymbol{\Lambda}^{\frac{1}{2}} \mathbf{U} \mathbf{x}z:=Λ
2
1
​

Ux中的一个。 在新的坐标系中，x⊤Qx\mathbf{x}^\top \mathbf{Q} \mathbf{x}x
⊤
Qx可以被简化为∥z∥2|\mathbf{z}|^2∥z∥
2
。 可惜，这是一个相当不切实际的想法。 一般而言，计算特征值和特征向量要比解决实际问题“贵”得多。

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

Q~=diag−12(Q)Qdiag−12(Q). (11.7.3)\tilde{\mathbf{Q}} = \mathrm{diag}^{-\frac{1}{2}}(\mathbf{Q}) \mathbf{Q} \mathrm{diag}^{-\frac{1}{2}}(\mathbf{Q}).~~~~~~~~~~(11.7.3)
Q
~
​
=diag
−
2
1
​

(Q)Qdiag
−
2
1
​

(Q). (11.7.3)

在这种情况下，我们得到了Q~ij=Qij/QiiQjj\tilde{\mathbf{Q}}{ij} = \mathbf{Q}{ij} / \sqrt{\mathbf{Q}{ii} \mathbf{Q}{jj}}
Q
~
​

ij
​
=Q
ij
​
/
Q
ii
​
Q
jj
​

​
，特别注意对于所有iii，Q~ii=1\tilde{\mathbf{Q}}_{ii} = 1
Q
~
​

ii
​
=1。 在大多数情况下，这大大简化了条件数。 例如我们之前讨论的案例，它将完全消除眼下的问题，因为问题是轴对齐的。

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

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

∂xˉfˉ(xˉ)=Λxˉ+cˉ=Λ(xˉ−xˉ0), (11.7.4)\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),~~~~~~~~~~(11.7.4)
∂
x
ˉ

​

f
ˉ
​
(
x
ˉ
)=Λ
x
ˉ
+
c
ˉ
=Λ(
x
ˉ
−
x
ˉ

0
​
), (11.7.4)

其中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算法是一种随机梯度下降算法，所以即使是在最佳值中，我们也会看到具有非零方差的梯度。 因此，我们可以放心地使用梯度的方差作为黑塞矩阵比例的廉价替代。 详尽的分析（要花几页解释）超出了本节的范围，请读者参考 Duchi.Hazan.Singer.2011。

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

gt=∂wl(yt,f(xt,w)),st=st−1+gt2,wt=wt−1−ηst+ϵ⋅gt. (11.7.5)\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}~~~~~~~~~~(11.7.5)
g
t
​

s
t
​

w
t
​

​

=∂
w
​
l(y
t
​
,f(x
t
​
,w)),
=s
t−1
​
+g
t
2
​
,
=w
t−1
​
−
s
t
​
+ϵ
​

η
​
⋅g
t
​
.
​
(11.7.5)

在这里，操作是按照坐标顺序应用。 也就是说，v2\mathbf{v}^2v
2
有条目vi2v_i^2v
i
2
​
。 同样，1v\frac{1}{\sqrt{v}}
v
​

1
​
有条目1vi\frac{1}{\sqrt{v_i}}
v
i
​

​

1
​
， 并且u⋅v\mathbf{u} \cdot \mathbf{v}u⋅v有条目uiviu_i v_iu
i
​
v
i
​
。 与之前一样，η\etaη是学习率，ϵ\epsilonϵ是一个为维持数值稳定性而添加的常数，用来确保我们不会除以000。 最后，我们初始化s0=0\mathbf{s}_0 = \mathbf{0}s
0
​
=0。

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

请注意，在st\mathbf{s}_ts
t
​
中累加平方梯度意味着st\mathbf{s}_ts
t
​
基本上以线性速率增长（由于梯度从最初开始衰减，实际上比线性慢一些）。 这产生了一个学习率O(t−12)\mathcal{O}(t^{-\frac{1}{2}})O(t
−
2
1
​

)，但是在单个坐标的层面上进行了调整。 对于凸问题，这完全足够了。 然而，在深度学习中，我们可能希望更慢地降低学习率。 这引出了许多AdaGrad算法的变体，我们将在后续章节中讨论它们。 眼下让我们先看看它在二次凸问题中的表现如何。 我们仍然同一函数为例：

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

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

In [ ]
%matplotlib inline
import math
import paddle
from d2l import paddle 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))
我们将学习率提高到222，可以看到更好的表现。 这已经表明，即使在无噪声的情况下，学习率的降低可能相当剧烈，我们需要确保参数能够适当地收敛。

In [ ]
eta = 2
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
从零开始实现
同动量法一样，AdaGrad算法需要对每个自变量维护同它一样形状的状态变量。

In [ ]
def init_adagrad_states(feature_dim):
s_w = d2l.zeros((feature_dim, 1))
s_b = d2l.zeros(shape=(1,))
return (s_w, s_b)

def adagrad(params, states, hyperparams):
a = []
eps = 1e-6
for p, s in zip(params, states):
with paddle.no_grad():
s[:] += paddle.square(p.grad)
p[:] -= hyperparams[‘lr’] * p.grad / paddle.sqrt(s + eps)
p.grad.zero_()
a.append§
return a
与11.5节中的实验相比，这里使用更大的学习率来训练模型。

In [ ]
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);
简洁实现
我们可直接使用深度学习框架中提供的AdaGrad算法来训练模型。

In [ ]
trainer = paddle.optimizer.Adagrad
d2l.train_concise_ch11(trainer, {‘learning_rate’: 0.1}, data_iter)
小结
AdaGrad算法会在单个坐标层面动态降低学习率。
AdaGrad算法利用梯度的大小作为调整进度速率的手段：用较小的学习率来补偿带有较大梯度的坐标。
在深度学习问题中，由于内存和计算限制，计算准确的二阶导数通常是不可行的。梯度可以作为一个有效的代理。
如果优化问题的结构相当不均匀，AdaGrad算法可以帮助缓解扭曲。
AdaGrad算法对于稀疏特征特别有效，在此情况下由于不常出现的问题，学习率需要更慢地降低。
在深度学习问题上，AdaGrad算法有时在降低学习率方面可能过于剧烈。我们将在 11.10节讨论缓解这种情况的策略。
练习
证明对于正交矩阵U\mathbf{U}U和向量c\mathbf{c}c，以下等式成立：∥c−δ∥2=∥Uc−Uδ∥2|\mathbf{c} - \mathbf{\delta}|2 = |\mathbf{U} \mathbf{c} - \mathbf{U} \mathbf{\delta}|2∥c−δ∥
2
​
=∥Uc−Uδ∥
2
​
。为什么这意味着在变量的正交变化之后，扰动的程度不会改变？
尝试对函数f(x)=0.1x12+2x22f(\mathbf{x}) = 0.1 x_1^2 + 2 x_2^2f(x)=0.1x
1
2
​
+2x
2
2
​
、以及它旋转45度后的函数即f(x)=0.1(x1+x2)2+2(x1−x2)2f(\mathbf{x}) = 0.1 (x_1 + x_2)^2 + 2 (x_1 - x_2)^2f(x)=0.1(x
1
​
+x
2
​
)
2
+2(x
1
​
−x
2
​
)
2
使用AdaGrad算法。它的表现会不同吗？
证明格什戈林圆盘定理，其中提到，矩阵M\mathbf{M}M的特征值λi\lambda_iλ
i
​
在至少一个jjj的选项中满足∣λi−Mjj∣≤∑k≠j∣Mjk∣|\lambda_i - \mathbf{M}{jj}| \leq \sum{k \neq j} |\mathbf{M}_{jk}|∣λ
i
​
−M
jj
​
∣≤∑
k

=j
​
∣M
jk
​
∣的要求。
关于对角线预处理矩阵diag−12(M)Mdiag−12(M)\mathrm{diag}^{-\frac{1}{2}}(\mathbf{M}) \mathbf{M} \mathrm{diag}^{-\frac{1}{2}}(\mathbf{M})diag
−
2
1
​

(M)Mdiag
−
2
1
​

(M)的特征值，格什戈林的定理告诉了我们什么？
尝试对适当的深度网络使用AdaGrad算法，例如，当应用于时尚MNIST时，使用 6.6节中lenet。
你要如何修改AdaGrad算法，才能使其在学习率方面的衰减不那么激进？
如果想系统性学习该项目，可前往“动手学AI”课程（https://aistudio.baidu.com/aistudio/course/introduce/25851）查看完整章节

Discussions