PyTorch教程-12.4。隨機(jī)梯度下降

在前面的章節(jié)中，我們一直在訓(xùn)練過(guò)程中使用隨機(jī)梯度下降，但是沒有解釋它為什么有效。為了闡明它，我們剛剛在第 12.3 節(jié)中描述了梯度下降的基本原理。在本節(jié)中，我們將繼續(xù) 更詳細(xì)地討論隨機(jī)梯度下降。

%matplotlib inline
import math
import torch
from d2l import torch as d2l

%matplotlib inline
import math
from mxnet import np, npx
from d2l import mxnet as d2l

npx.set_np()

%matplotlib inline
import math
import tensorflow as tf
from d2l import tensorflow as d2l

12.4.1。隨機(jī)梯度更新

在深度學(xué)習(xí)中，目標(biāo)函數(shù)通常是訓(xùn)練數(shù)據(jù)集中每個(gè)示例的損失函數(shù)的平均值。給定訓(xùn)練數(shù)據(jù)集n例子，我們假設(shè) fi(x)是關(guān)于 index 訓(xùn)練樣例的損失函數(shù)i， 在哪里x是參數(shù)向量。然后我們到達(dá)目標(biāo)函數(shù)

(12.4.1)f(x)=1n∑i=1nfi(x).

目標(biāo)函數(shù)的梯度在x被計(jì)算為

(12.4.2)?f(x)=1n∑i=1n?fi(x).

如果使用梯度下降，每次自變量迭代的計(jì)算成本為O(n), 線性增長(zhǎng) n. 因此，當(dāng)訓(xùn)練數(shù)據(jù)集較大時(shí)，每次迭代的梯度下降代價(jià)會(huì)更高。

隨機(jī)梯度下降 (SGD) 減少了每次迭代的計(jì)算成本。在隨機(jī)梯度下降的每次迭代中，我們統(tǒng)一采樣一個(gè)索引i∈{1,…,n}隨機(jī)獲取數(shù)據(jù)示例，并計(jì)算梯度?fi(x)更新x:

(12.4.3)x←x?η?fi(x),

在哪里η是學(xué)習(xí)率。我們可以看到每次迭代的計(jì)算成本從O(n) 梯度下降到常數(shù)O(1). 此外，我們要強(qiáng)調(diào)的是隨機(jī)梯度 ?fi(x)是完整梯度的無(wú)偏估計(jì)?f(x)因?yàn)?/p>

(12.4.4)Ei?fi(x)=1n∑i=1n?fi(x)=?f(x).

這意味著，平均而言，隨機(jī)梯度是對(duì)梯度的良好估計(jì)。

現(xiàn)在，我們將通過(guò)向梯度添加均值為 0 和方差為 1 的隨機(jī)噪聲來(lái)模擬隨機(jī)梯度下降，將其與梯度下降進(jìn)行比較。

def f(x1, x2): # Objective function
  return x1 ** 2 + 2 * x2 ** 2

def f_grad(x1, x2): # Gradient of the objective function
  return 2 * x1, 4 * x2

def sgd(x1, x2, s1, s2, f_grad):
  g1, g2 = f_grad(x1, x2)
  # Simulate noisy gradient
  g1 += torch.normal(0.0, 1, (1,)).item()
  g2 += torch.normal(0.0, 1, (1,)).item()
  eta_t = eta * lr()
  return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0)

def constant_lr():
  return 1

eta = 0.1
lr = constant_lr # Constant learning rate
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))

epoch 50, x1: 0.014749, x2: 0.009829

def f(x1, x2): # Objective function
  return x1 ** 2 + 2 * x2 ** 2

def f_grad(x1, x2): # Gradient of the objective function
  return 2 * x1, 4 * x2

def sgd(x1, x2, s1, s2, f_grad):
  g1, g2 = f_grad(x1, x2)
  # Simulate noisy gradient
  g1 += np.random.normal(0.0, 1, (1,))
  g2 += np.random.normal(0.0, 1, (1,))
  eta_t = eta * lr()
  return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0)

def constant_lr():
  return 1

eta = 0.1
lr = constant_lr # Constant learning rate
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))

epoch 50, x1: -0.472513, x2: 0.110780

def f(x1, x2): # Objective function
  return x1 ** 2 + 2 * x2 ** 2

def f_grad(x1, x2): # Gradient of the objective function
  return 2 * x1, 4 * x2

def sgd(x1, x2, s1, s2, f_grad):
  g1, g2 = f_grad(x1, x2)
  # Simulate noisy gradient
  g1 += tf.random.normal([1], 0.0, 1)
  g2 += tf.random.normal([1], 0.0, 1)
  eta_t = eta * lr()
  return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0)

def constant_lr():
  return 1

eta = 0.1
lr = constant_lr # Constant learning rate
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))

epoch 50, x1: -0.103750, x2: 0.054715

正如我們所見，隨機(jī)梯度下降中變量的軌跡比我們?cè)?2.3 節(jié)中觀察到的梯度下降中的軌跡噪聲大得多。這是由于梯度的隨機(jī)性。也就是說(shuō)，即使我們到達(dá)最小值附近，我們?nèi)匀皇艿剿矔r(shí)梯度注入的不確定性的影響η?fi(x). 即使在 50 步之后，質(zhì)量仍然不是很好。更糟糕的是，它不會(huì)在額外的步驟后得到改善（我們鼓勵(lì)您嘗試更多的步驟來(lái)確認(rèn)這一點(diǎn)）。這給我們留下了唯一的選擇：改變學(xué)習(xí)率η. 但是，如果我們選擇的太小，我們最初不會(huì)取得任何有意義的進(jìn)展。另一方面，如果我們選擇太大，我們將得不到好的解決方案，如上所示。解決這些相互沖突的目標(biāo)的唯一方法是隨著優(yōu)化的進(jìn)行動(dòng)態(tài)降低學(xué)習(xí)率。

lr這也是在step函數(shù)中加入學(xué)習(xí)率函數(shù)的原因sgd。在上面的例子中，學(xué)習(xí)率調(diào)度的任何功能都處于休眠狀態(tài)，因?yàn)槲覀儗⑾嚓P(guān)lr 函數(shù)設(shè)置為常量。

12.4.2。動(dòng)態(tài)學(xué)習(xí)率

更換η具有隨時(shí)間變化的學(xué)習(xí)率 η(t)增加了控制優(yōu)化算法收斂的復(fù)雜性。特別是，我們需要弄清楚多快 η應(yīng)該腐爛。如果太快，我們將過(guò)早地停止優(yōu)化。如果我們減少它太慢，我們會(huì)在優(yōu)化??上浪費(fèi)太多時(shí)間。以下是一些用于調(diào)整的基本策略η隨著時(shí)間的推移（我們稍后會(huì)討論更高級(jí)的策略）：

(12.4.5)η(t)=ηiifti≤t≤ti+1piecewise constantη(t)=η0?e?λtexponential decayη(t)=η0?(βt+1)?αpolynomial decay

在第一個(gè)分段常數(shù)場(chǎng)景中，我們降低學(xué)習(xí)率，例如，每當(dāng)優(yōu)化進(jìn)展停滯時(shí)。這是訓(xùn)練深度網(wǎng)絡(luò)的常用策略?；蛘?，我們可以通過(guò)指數(shù)衰減更積極地減少它。不幸的是，這通常會(huì)導(dǎo)致在算法收斂之前過(guò)早停止。一個(gè)流行的選擇是多項(xiàng)式衰減α=0.5. 在凸優(yōu)化的情況下，有許多證據(jù)表明該比率表現(xiàn)良好。

讓我們看看指數(shù)衰減在實(shí)踐中是什么樣子的。

def exponential_lr():
  # Global variable that is defined outside this function and updated inside
  global t
  t += 1
  return math.exp(-0.1 * t)

t = 1
lr = exponential_lr
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=1000, f_grad=f_grad))

epoch 1000, x1: -0.878960, x2: -0.023958

def exponential_lr():
  # Global variable that is defined outside this function and updated inside
  global t
  t += 1
  return math.exp(-0.1 * t)

t = 1
lr = exponential_lr
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=1000, f_grad=f_grad))

epoch 1000, x1: -0.820458, x2: 0.004701

def exponential_lr():
  # Global variable that is defined outside this function and updated inside
  global t
  t += 1
  return math.exp(-0.1 * t)

t = 1
lr = exponential_lr
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=1000, f_grad=f_grad))

epoch 1000, x1: -0.798681, x2: -0.067649

正如預(yù)期的那樣，參數(shù)的方差顯著減少。然而，這是以無(wú)法收斂到最優(yōu)解為代價(jià)的x=(0,0). 即使在 1000 次迭代之后，我們?nèi)匀浑x最佳解決方案很遠(yuǎn)。實(shí)際上，該算法根本無(wú)法收斂。另一方面，如果我們使用多項(xiàng)式衰減，其中學(xué)習(xí)率隨步數(shù)的平方根反比衰減，則收斂?jī)H在 50 步后變得更好。

def polynomial_lr():
  # Global variable that is defined outside this function and updated inside
  global t
  t += 1
  return (1 + 0.1 * t) ** (-0.5)

t = 1
lr = polynomial_lr
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))

epoch 50, x1: -0.060831, x2: 0.028779

def polynomial_lr():
  # Global variable that is defined outside this function and updated inside
  global t
  t += 1
  return (1 + 0.1 * t) ** (-0.5)

t = 1
lr = polynomial_lr
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))

epoch 50, x1: 0.025029, x2: 0.115820

def polynomial_lr():
  # Global variable that is defined outside this function and updated inside
  global t
  t += 1
  return (1 + 0.1 * t) ** (-0.5)

t = 1
lr = polynomial_lr
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))

epoch 50, x1: 0.280001, x2: -0.037688

關(guān)于如何設(shè)置學(xué)習(xí)率，還有更多選擇。例如，我們可以從一個(gè)小的速率開始，然后迅速上升，然后再次下降，盡管速度會(huì)更慢。我們甚至可以在更小和更大的學(xué)習(xí)率之間交替。存在多種此類時(shí)間表?，F(xiàn)在讓我們關(guān)注可以進(jìn)行綜合理論分析的學(xué)習(xí)率計(jì)劃，即凸設(shè)置中的學(xué)習(xí)率。對(duì)于一般的非凸問(wèn)題，很難獲得有意義的收斂保證，因?yàn)橥ǔＷ钚』蔷€性非凸問(wèn)題是 NP 難題。有關(guān)調(diào)查，請(qǐng)參見 Tibshirani 2015 的優(yōu)秀講義 。

12.4.3。凸目標(biāo)的收斂性分析

以下針對(duì)凸目標(biāo)函數(shù)的隨機(jī)梯度下降的收斂分析是可選的，主要用于傳達(dá)有關(guān)問(wèn)題的更多直覺。我們將自己限制在最簡(jiǎn)單的證明之一（Nesterov 和 Vial，2000）。存在顯著更高級(jí)的證明技術(shù)，例如，每當(dāng)目標(biāo)函數(shù)表現(xiàn)得特別好時(shí)。

假設(shè)目標(biāo)函數(shù) f(ξ,x)是凸的x 對(duì)全部ξ. 更具體地說(shuō)，我們考慮隨機(jī)梯度下降更新：

(12.4.6)xt+1=xt?ηt?xf(ξt,x),

在哪里f(ξt,x)是關(guān)于訓(xùn)練樣例的目標(biāo)函數(shù)ξt 在步驟中從一些分布中提取t和x是模型參數(shù)。表示為

(12.4.7)R(x)=Eξ[f(ξ,x)]

預(yù)期的風(fēng)險(xiǎn)和R?它的最低限度 x. 最后讓x?是最小化器（我們假設(shè)它存在于x被定義為）。在這種情況下，我們可以跟蹤當(dāng)前參數(shù)之間的距離xt在時(shí)間t和風(fēng)險(xiǎn)最小化 x?看看它是否隨著時(shí)間的推移而改善：

(12.4.8)‖xt+1?x?‖2=‖xt?ηt?xf(ξt,x)?x?‖2=‖xt?x?‖2+ηt2‖?xf(ξt,x)‖2?2ηt?xt?x?,?xf(ξt,x)?.

我們假設(shè)?2隨機(jī)梯度范數(shù) ?xf(ξt,x)受一些常數(shù)的限制L, 因此我們有

(12.4.9)ηt2‖?xf(ξt,x)‖2≤ηt2L2.

我們最感興趣的是兩者之間的距離 xt和x?預(yù)期的變化。事實(shí)上，對(duì)于任何特定的步驟序列，距離很可能會(huì)增加，具體取決于哪個(gè)ξt我們遇到。因此我們需要綁定點(diǎn)積。因?yàn)閷?duì)于任何凸函數(shù)f它認(rèn)為 f(y)≥f(x)+?f′(x),y?x? 對(duì)全部x和y, 根據(jù)凸性我們有

(12.4.10)f(ξt,x?)≥f(ξt,xt)+?x??xt,?xf(ξt,xt)?.

將不等式(12.4.9)和 (12.4.10)代入(12.4.8)我們得到了時(shí)間參數(shù)之間距離的界限t+1如下：

(12.4.11)‖xt?x?‖2?‖xt+1?x?‖2≥2ηt(f(ξt,xt)?f(ξt,x?))?ηt2L2.

這意味著只要當(dāng)前損失與最優(yōu)損失之間的差異大于ηtL2/2. 由于這種差異必然會(huì)收斂到零，因此學(xué)習(xí)率ηt也需要消失。

接下來(lái)我們對(duì)(12.4.11)進(jìn)行期望。這產(chǎn)生

(12.4.12)E[‖xt?x?‖2]?E[‖xt+1?x?‖2]≥2ηt[E[R(xt)]?R?]?ηt2L2.

最后一步涉及對(duì)不等式求和 t∈{1,…,T}. 由于總和望遠(yuǎn)鏡并且通過(guò)刪除較低的項(xiàng)我們獲得

(12.4.13)‖x1?x?‖2≥2(∑t=1Tηt)[E[R(xt)]?R?]?L2∑t=1Tηt2.

請(qǐng)注意，我們利用了x1是給定的，因此可以放棄期望。最后定義

(12.4.14)xˉ=def∑t=1Tηtxt∑t=1Tηt.

自從

(12.4.15)E(∑t=1TηtR(xt)∑t=1Tηt)=∑t=1TηtE[R(xt)]∑t=1Tηt=E[R(xt)],

由 Jensen 不等式（設(shè)置i=t, αi=ηt/∑t=1Tηt在 (12.2.3) ) 和凸性R它遵循E[R(xt)]≥E[R(xˉ)]， 因此

(12.4.16)∑t=1TηtE[R(xt)]≥∑t=1TηtE[R(xˉ)].

將其代入不等式(12.4.13)得到邊界

(12.4.17)[E[xˉ]]?R?≤r2+L2∑t=1Tηt22∑t=1Tηt,

在哪里 r2=def‖x1?x?‖2 是參數(shù)的初始選擇與最終結(jié)果之間距離的界限。簡(jiǎn)而言之，收斂速度取決于隨機(jī)梯度的范數(shù)如何有界（L) 以及初始參數(shù)值離最優(yōu)性有多遠(yuǎn) (r). 請(qǐng)注意，邊界是根據(jù)xˉ而不是 xT. 這是因?yàn)閤ˉ是優(yōu)化路徑的平滑版本。每當(dāng)r,L， 和 T已知我們可以選擇學(xué)習(xí)率 η=r/(LT). 這產(chǎn)生作為上限 rL/T. 也就是說(shuō)，我們收斂于 rate O(1/T)到最優(yōu)解。

12.4.4。隨機(jī)梯度和有限樣本

到目前為止，在談到隨機(jī)梯度下降時(shí)，我們玩得有點(diǎn)快和松了。我們假設(shè)我們繪制實(shí)例 xi，通常帶有標(biāo)簽yi從一些分布 p(x,y)并且我們使用它以某種方式更新模型參數(shù)。特別地，對(duì)于有限的樣本量，我們簡(jiǎn)單地認(rèn)為離散分布 p(x,y)=1n∑i=1nδxi(x)δyi(y) 對(duì)于某些功能δxi和δyi允許我們對(duì)其執(zhí)行隨機(jī)梯度下降。

然而，這并不是我們所做的。在當(dāng)前部分的玩具示例中，我們只是將噪聲添加到其他非隨機(jī)梯度中，即，我們假裝有對(duì)(xi,yi). 事實(shí)證明，這是有道理的（詳細(xì)討論見習(xí)題）。更麻煩的是，在之前的所有討論中，我們顯然都沒有這樣做。相反，我們只對(duì)所有實(shí)例進(jìn)行一次迭代。要了解為什么這樣做更可取，請(qǐng)考慮相反的情況，即我們正在抽樣n從帶有替換的離散分布觀察 。選擇元素的概率i隨機(jī)是1/n. 因此至少選擇一次是

(12.4.18)P(choosei)=1?P(omiti)=1?(1?1/n)n≈1?e?1≈0.63.

類似的推理表明，恰好一次選擇某個(gè)樣本（即訓(xùn)練示例）的概率由下式給出

(12.4.19)(n1)1n(1?1n)n?1=nn?1(1?1n)n≈e?1≈0.37.

相對(duì)于無(wú)放回抽樣，放回抽樣會(huì)導(dǎo)致方差增加和數(shù)據(jù)效率降低。因此，在實(shí)踐中我們執(zhí)行后者（這是貫穿本書的默認(rèn)選擇）。最后請(qǐng)注意，重復(fù)通過(guò)訓(xùn)練數(shù)據(jù)集以不同的隨機(jī)順序遍歷它。

12.4.5。概括

對(duì)于凸問(wèn)題，我們可以證明，對(duì)于廣泛選擇的學(xué)習(xí)率，隨機(jī)梯度下降將收斂到最優(yōu)解。

對(duì)于深度學(xué)習(xí)，通常情況并非如此。然而，對(duì)凸問(wèn)題的分析讓我們對(duì)如何接近優(yōu)化有了有用的認(rèn)識(shí)，即逐步降低學(xué)習(xí)率，盡管不是太快。

學(xué)習(xí)率太小或太大時(shí)都會(huì)出現(xiàn)問(wèn)題。在實(shí)踐中，通常需要經(jīng)過(guò)多次實(shí)驗(yàn)才能找到合適的學(xué)習(xí)率。

當(dāng)訓(xùn)練數(shù)據(jù)集中有更多示例時(shí)，梯度下降的每次迭代計(jì)算成本更高，因此在這些情況下首選隨機(jī)梯度下降。

隨機(jī)梯度下降的最優(yōu)性保證在非凸情況下通常不可用，因?yàn)樾枰獧z查的局部最小值的數(shù)量很可能是指數(shù)級(jí)的。

12.4.6。練習(xí)

試驗(yàn)隨機(jī)梯度下降的不同學(xué)習(xí)率計(jì)劃和不同的迭代次數(shù)。特別是，繪制與最佳解決方案的距離 (0,0)作為迭代次數(shù)的函數(shù)。

證明對(duì)于函數(shù)f(x1,x2)=x12+2x22 向梯度添加正常噪聲相當(dāng)于最小化損失函數(shù) f(x,w)=(x1?w1)2+2(x2?w2)2 在哪里x從正態(tài)分布中提取。

當(dāng)您從中采樣時(shí)比較隨機(jī)梯度下降的收斂性{(x1,y1),…,(xn,yn)}有更換和當(dāng)您在沒有更換的情況下取樣時(shí)。

如果某個(gè)梯度（或者與其相關(guān)的某個(gè)坐標(biāo)）始終大于所有其他梯度，您將如何更改隨機(jī)梯度下降求解器？

假使，假設(shè)f(x)=x2(1+sin?x). 有多少局部最小值f有？你能改變嗎f以這樣一種方式來(lái)最小化它需要評(píng)估所有局部最小值？