讓我們首先考慮具有不常出現的特征的學習問題。

12.7.1。稀疏特征和學習率

想象一下，我們正在訓練一個語言模型。為了獲得良好的準確性，我們通常希望在繼續訓練時降低學習率，通常為O(t?12)或更慢。現在考慮在稀疏特征（即不常出現的特征）上進行模型訓練。這在自然語言中很常見，例如，我們看到preconditioning一詞的可能性要小于learning 。然而，它在計算廣告和個性化協同過濾等其他領域也很常見。畢竟，有很多東西只是少數人感興趣的。

與不常見特征關聯的參數只有在這些特征出現時才會收到有意義的更新。如果學習率下降，我們可能會遇到這樣一種情況，即常見特征的參數會很快收斂到它們的最優值，而對于不常見的特征，在確定它們的最優值之前，我們仍然沒有足夠頻繁地觀察它們。換句話說，學習率要么對于頻繁出現的特征下降得太慢，要么對于不頻繁出現的特征下降得太快。

解決此問題的一種可能的破解方法是計算我們看到特定功能的次數，并將其用作調整學習率的時鐘。也就是說，而不是選擇形式的學習率η=η0t+c我們可以使用 ηi=η0s(i,t)+c. 這里s(i,t) 計算特征的非零數i我們觀察到時間t. 這實際上很容易實現，而且沒有任何有意義的開銷。然而，每當我們不太具有稀疏性而只是梯度通常非常小且很少大的數據時，它就會失敗。畢竟，尚不清楚人們會在哪里劃清是否符合觀察到的特征的界限。

Duchi等人的 Adagrad 。( 2011 )通過更換相當粗糙的計數器來解決這個問題s(i,t)通過先前觀察到的梯度的平方的集合。特別是，它使用 s(i,t+1)=s(i,t)+(?if(x))2作為調整學習率的手段。這有兩個好處：首先，我們不再需要決定梯度何時足夠大。其次，它會隨著梯度的大小自動縮放。通常對應于大梯度的坐標會顯著縮小，而其他具有小梯度的坐標會得到更溫和的處理。在實踐中，這導致了計算廣告和相關問題的非常有效的優化過程。但這隱藏了 Adagrad 固有的一些額外好處，這些好處最好在預處理的背景下理解。

12.7.2。預處理

凸優化問題有利于分析算法的特性。畢竟，對于大多數非凸問題來說，很難得出有意義的理論保證，但直覺和洞察力 往往會起作用。讓我們看看最小化問題 f(x)=12x?Qx+c?x+b.

正如我們在12.6 節中看到的，可以根據其特征分解來重寫這個問題 Q=U?ΛU得出一個大大簡化的問題，其中每個坐標都可以單獨求解：

(12.7.1)f(x)=fˉ(xˉ)=12xˉ?Λxˉ+cˉ?xˉ+b.

這里我們使用了xˉ=Ux因此cˉ=Uc. 修改后的問題具有最小值 xˉ=?Λ?1cˉ 和最小值 ?12cˉ?Λ?1cˉ+b. 這更容易計算，因為Λ是包含特征值的對角矩陣Q.

如果我們擾亂cslightly 我們希望在最小化器中找到微小的變化f. 不幸的是，這種情況并非如此。雖然略有變化c導致同樣輕微的變化cˉ，這不是最小化的情況f（和的fˉ分別）。每當特征值Λi很大，我們只會看到很小的變化xˉi并且至少 fˉ. 反之，對于小Λi 改變在xˉi可以是戲劇性的。最大和最小特征值之比稱為優化問題的條件數。

(12.7.2)κ=Λ1Λd.

如果條件數κ大，難以準確求解優化問題。我們需要確保我們謹慎地獲得正確的大動態值范圍。我們的分析引出了一個明顯但有些幼稚的問題：難道我們不能簡單地通過扭曲空間來“解決”問題，使得所有特征值都是 1. 理論上這很容易：我們只需要的特征值和特征向量Q從重新調整問題 x到一個 z=defΛ12Ux. 在新的坐標系中 x?Qx可以簡化為 ‖z‖2. las，這是一個相當不切實際的建議。計算特征值和特征向量通常 比解決實際問題要昂貴得多。

雖然精確計算特征值可能很昂貴，但猜測它們并對其進行近似計算可能已經比什么都不做要好得多。特別是，我們可以使用對角線項Q并相應地重新縮放它。這比計算特征值便宜得多。

(12.7.3)Q~=diag?12(Q)Qdiag?12(Q).

在這種情況下，我們有 Q~ij=Qij/QiiQjj 特別是Q~ii=1對全部i. 在大多數情況下，這會大大簡化條件數。例如，我們之前討論的情況，這將完全消除手頭的問題，因為問題是軸對齊的。

不幸的是，我們面臨另一個問題：在深度學習中，我們通常甚至無法訪問目標函數的二階導數：對于x∈Rd即使是小批量的二階導數也可能需要O(d2)空間和計算工作，因此實際上是不可行的。Adagrad 的巧妙想法是使用一個代理來表示 Hessian 的難以捉摸的對角線，它既計算成本相對低又有效——梯度本身的大小。

為了了解為什么會這樣，讓我們??看一下 fˉ(xˉ). 我們有那個

(12.7.4)?xˉfˉ(xˉ)=Λxˉ+cˉ=Λ(xˉ?xˉ0),

在哪里xˉ0是的最小值fˉ. 因此，梯度的大小取決于 Λ和最優的距離。如果 xˉ?xˉ0沒有改變，這將是所有需要的。畢竟，在這種情況下，梯度的大小?xˉfˉ(xˉ) 足夠了。由于 AdaGrad 是一種隨機梯度下降算法，即使在最優狀態下，我們也會看到具有非零方差的梯度。因此，我們可以安全地使用梯度的方差作為 Hessian 尺度的廉價代理。徹底的分析超出了本節的范圍（可能需要好幾頁）。詳情請讀者參考 ( Duchi et al. , 2011 ) 。

12.7.3。算法

讓我們將上面的討論正式化。我們使用變量 st如下累積過去的梯度方差。

(12.7.5)gt=?wl(yt,f(xt,w)),st=st?1+gt2,wt=wt?1?ηst+??gt.

這里的操作是按坐標應用的。那是， v2有條目vi2. 同樣地 1v有條目1vi和 u?v有條目uivi. 像之前一樣η是學習率和?是一個附加常數，確保我們不除以0. 最后，我們初始化s0=0.

就像在動量的情況下一樣，我們需要跟蹤一個輔助變量，在這種情況下允許每個坐標的單獨學習率。相對于 SGD，這不會顯著增加 Adagrad 的成本，因為主要成本通常是計算 l(yt,f(xt,w))及其衍生物。

請注意，在中累積平方梯度st意思是st基本上以線性速率增長（實際上比線性速率慢一些，因為梯度最初會減小）。這導致O(t?12) 學習率，盡管在每個坐標的基礎上進行了調整。對于凸問題，這已經足夠了。但是，在深度學習中，我們可能希望更慢地降低學習率。這導致了我們將在后續章節中討論的許多 Adagrad 變體。現在讓我們看看它在二次凸問題中的表現。我們使用與之前相同的問題：

(12.7.6)f(x)=0.1x12+2x22.

我們將使用之前相同的學習率來實現 Adagrad，即η=0.4. 可以看出，自變量的迭代軌跡更加平滑。然而，由于累積效應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

%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

%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.242, 0.143 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.242, 23.515 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.242, 1.183 sec/epoch

12.7.5。簡潔的實現

使用Trainer算法的實例adagrad，我們可以在 Gluon 中調用 Adagrad 算法。

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

loss: 0.242, 0.143 sec/epoch

d2l.train_concise_ch11('adagrad', {'learning_rate': 0.1}, data_iter)

loss: 0.242, 23.234 sec/epoch

trainer = tf.keras.optimizers.Adagrad
d2l.train_concise_ch11(trainer, {'learning_rate' : 0.1}, data_iter)

loss: 0.243, 1.159 sec/epoch

12.7.6。概括

Adagrad 在每個坐標的基礎上動態降低學習率。

它使用梯度的大小作為調整取得進展的速度的一種手段——具有大梯度的坐標用較小的學習率進行補償。

由于內存和計算限制，在深度學習問題中計算精確的二階導數通常是不可行的。梯度可以是一個有用的代理。

如果優化問題的結構相當不均勻，Adagrad 可以幫助減輕失真。

Adagrad 對于稀疏特征特別有效，在這些稀疏特征中，對于不常出現的術語，學習率需要更慢地降低。

在深度學習問題上，Adagrad 有時會過于激進地降低學習率。我們將在第 12.10 節的上下文中討論緩解這種情況的策略。

12.7.7。練習

證明對于正交矩陣U和一個向量 c以下內容成立： ‖c?δ‖2=‖Uc?Uδ‖2. 為什么這意味著在變量正交變化后擾動的大小不會改變？

試用 Adagradf(x)=0.1x12+2x22并且目標函數也旋轉了 45 度，即 f(x)=0.1(x1+x2)2+2(x1?x2)2. 它的行為是否不同？

證明Gerschgorin 的圓定理 ，該定理指出特征值λi矩陣的 M滿足 |λi?Mjj|≤∑k≠j|Mjk| 至少一個選擇j.

Gerschgorin 定理告訴我們關于對角線預處理矩陣的特征值的什么信息 diag?12(M)Mdiag?12(M)？

嘗試 Adagrad 以獲得適當的深度網絡，例如 應用于 Fashion-MNIST 時的第 7.6 節。

您需要如何修改 Adagrad 才能使學習率下降得不那么激進？