讓我們首先考慮具有不常出現(xiàn)的特征的學(xué)習(xí)問題。

12.7.1。稀疏特征和學(xué)習(xí)率

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

與不常見特征關(guān)聯(lián)的參數(shù)只有在這些特征出現(xiàn)時才會收到有意義的更新。如果學(xué)習(xí)率下降，我們可能會遇到這樣一種情況，即常見特征的參數(shù)會很快收斂到它們的最優(yōu)值，而對于不常見的特征，在確定它們的最優(yōu)值之前，我們?nèi)匀粵]有足夠頻繁地觀察它們。換句話說，學(xué)習(xí)率要么對于頻繁出現(xiàn)的特征下降得太慢，要么對于不頻繁出現(xiàn)的特征下降得太快。

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

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

12.7.2。預(yù)處理

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

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

(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導(dǎo)致同樣輕微的變化cˉ，這不是最小化的情況f（和的fˉ分別）。每當(dāng)特征值Λi很大，我們只會看到很小的變化xˉi并且至少 fˉ. 反之，對于小Λi 改變在xˉi可以是戲劇性的。最大和最小特征值之比稱為優(yōu)化問題的條件數(shù)。

(12.7.2)κ=Λ1Λd.

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

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

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

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

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

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

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

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

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

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

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

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

我們將使用之前相同的學(xué)習(xí)率來實現(xiàn) Adagrad，即η=0.4. 可以看出，自變量的迭代軌跡更加平滑。然而，由于累積效應(yīng)st，學(xué)習(xí)率不斷衰減，因此自變量在迭代的后期階段不會移動太多。

%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

當(dāng)我們將學(xué)習(xí)率提高到2我們看到了更好的行為。這已經(jīng)表明學(xué)習(xí)率的降低可能相當(dāng)激進(jìn)，即使在無噪聲的情況下也是如此，我們需要確保參數(shù)適當(dāng)收斂。

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 需要維護(hù)一個與參數(shù)形狀相同的狀態(tài)變量。

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 節(jié)的實驗相比，我們使用更大的學(xué)習(xí)率來訓(xùn)練模型。

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。簡潔的實現(xiàn)

使用Trainer算法的實例adagrad，我們可以在 Gluon 中調(diào)用 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 在每個坐標(biāo)的基礎(chǔ)上動態(tài)降低學(xué)習(xí)率。

它使用梯度的大小作為調(diào)整取得進(jìn)展的速度的一種手段——具有大梯度的坐標(biāo)用較小的學(xué)習(xí)率進(jìn)行補(bǔ)償。

由于內(nèi)存和計算限制，在深度學(xué)習(xí)問題中計算精確的二階導(dǎo)數(shù)通常是不可行的。梯度可以是一個有用的代理。

如果優(yōu)化問題的結(jié)構(gòu)相當(dāng)不均勻，Adagrad 可以幫助減輕失真。

Adagrad 對于稀疏特征特別有效，在這些稀疏特征中，對于不常出現(xiàn)的術(shù)語，學(xué)習(xí)率需要更慢地降低。

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

12.7.7。練習(xí)

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

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

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

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

嘗試 Adagrad 以獲得適當(dāng)?shù)纳疃染W(wǎng)絡(luò)，例如 應(yīng)用于 Fashion-MNIST 時的第 7.6 節(jié)。

您需要如何修改 Adagrad 才能使學(xué)習(xí)率下降得不那么激進(jìn)？