梯度下降算法及其變種：批量梯度下降，小批量梯度下降和隨機(jī)梯度下降

最優(yōu)化是指由變量x構(gòu)成的目標(biāo)函數(shù)f(x)進(jìn)行最小化或最大化的過程。在機(jī)器學(xué)習(xí)或深度學(xué)習(xí)術(shù)語中，通常指最小化損失函數(shù)J(w)，其中模型參數(shù)w∈R^d。最小化最優(yōu)化算法具有以下的目標(biāo)：

- 如果目標(biāo)函數(shù)是凸的，那么任何的局部最小值都是全局最小值。

- 通常情況下，在大多數(shù)深度學(xué)習(xí)問題中，目標(biāo)函數(shù)是非凸的，那就只能找到目標(biāo)函數(shù)鄰域內(nèi)的最低值。

圖1: 向著最小化邁進(jìn)

目前主要有三種最優(yōu)化算法：

- 對單點問題，最優(yōu)化算法不用進(jìn)行迭代和簡單求解。

- 對于邏輯回歸中經(jīng)常用到梯度下降法，這類最優(yōu)化算法本質(zhì)上是迭代，不管參數(shù)初始化好壞都能收斂到可接受的解。

- 對于一系列具有非凸損失函數(shù)的問題中，如神經(jīng)網(wǎng)絡(luò)。為保證收斂速度與低錯誤率，最優(yōu)化算法中的參數(shù)初始化中起著至關(guān)重要的作用。

梯度下降是機(jī)器學(xué)習(xí)和深度學(xué)習(xí)中最常用的優(yōu)化算法。它屬于一階優(yōu)化算法，參數(shù)更新時只考慮一階導(dǎo)數(shù)。在每次迭代中，梯度表示最陡的上升方向，于是我們朝著目標(biāo)函數(shù)梯度的反方向更新參數(shù)，并通過學(xué)習(xí)速率α來調(diào)整每次迭代中達(dá)到局部最小值的步長。因此，目標(biāo)函數(shù)會沿著下坡的方向，直到達(dá)到局部最小值。

在本文中，我們將介紹梯度下降算法及其變種：批量梯度下降，小批量梯度下降和隨機(jī)梯度下降。

我們先看看梯度下降是如何在邏輯回歸中發(fā)揮作用的，然后再討論其它變種算法。簡單起見，我們假設(shè)邏輯回歸模型只有兩個參數(shù)：權(quán)重w和偏差b。

1.將初始化權(quán)重w和偏差b設(shè)為任意隨機(jī)數(shù)。

2.為學(xué)習(xí)率α選擇一個合適的值，學(xué)習(xí)速率決定了每次迭代的步長。

- 如果α非常小，則需要很長時間才能收斂并且計算量很大。

- 如果α較大，則可能無法收斂甚至超出最小值。

- 通過我們會使用以下值作為學(xué)習(xí)速度 : 0.001, 0.003, 0.01, 0.03, 0.1, 0.3.

圖2: 不同學(xué)習(xí)速度下的梯度下降

因此，通過觀察比較不同的α值對應(yīng)的損失函數(shù)變化，我們選擇第一次未達(dá)到收斂的α值的前一個作為最終的α值，這樣我們就可以有一個快速且收斂的學(xué)習(xí)算法。

3.如果數(shù)據(jù)尺度不一，那就要對數(shù)據(jù)進(jìn)行尺度縮放。如果我們不縮放數(shù)據(jù)，那么等高線（輪廓）會變得越來越窄，意味著它需要更長的時間來達(dá)到收斂（見圖3）。

圖3. 梯度下降: 數(shù)據(jù)歸一化后的等高線與未進(jìn)行歸一化的對比

使數(shù)據(jù)分布滿足μ= 0和σ= 1。以下是數(shù)據(jù)縮放的公式：

4.在每次迭代中，用損失函數(shù)J的偏導(dǎo)數(shù)來表示每個參數(shù)（梯度）

更新方程如下：

- 特地說明一下，此處我們假設(shè)不存在偏差。 如果當(dāng)前值w對應(yīng)的梯度方向為正，這意味著當(dāng)前點處在最優(yōu)值w*的右側(cè)，則需要朝著負(fù)方向更新，從而接近最優(yōu)值w*。然而如果現(xiàn)在梯度是負(fù)值，那么更新方向?qū)⑹钦模瑢⒃黾觲的當(dāng)前值以收斂到w*的最優(yōu)值（參見圖4）：

圖4: 梯度下降，示例說明梯度下降算法如何用損失函數(shù)的一階導(dǎo)數(shù)實現(xiàn)下降并達(dá)到最小值。

- 繼續(xù)這個過程，直至損失函數(shù)收斂。也就是說，直到誤差曲線變得平坦不變。

- 此外，每次迭代中，朝著變化最大的方向進(jìn)行，每一步都與等高線垂直。

上面就是梯度下降法的一般過程，我們需要確定目標(biāo)函數(shù)、優(yōu)化方法，并通過梯度來引導(dǎo)系統(tǒng)搜尋到最優(yōu)值。

現(xiàn)在我們來討論梯度下降算法的三個變種，它們之間的主要區(qū)別在于每個學(xué)習(xí)步驟中計算梯度時使用的數(shù)據(jù)量，是對每個參數(shù)更新（學(xué)習(xí)步驟）時的梯度準(zhǔn)確性與時間復(fù)雜度的折衷考慮。

批量梯度下降

批量梯度下降是指在對參數(shù)執(zhí)行更新時，在每次迭代中使用所有的樣本。

for i in range(num_epochs):

grad = compute_gradient(data, params)

params = params — learning_rate * grad

主要的優(yōu)點:

- 訓(xùn)練期間，我們可以使用固定的學(xué)習(xí)率，而不用考慮學(xué)習(xí)率衰減的問題。

- 它具有朝向最小值的直線軌跡，并且如果損失函數(shù)是凸的，則保證理論上收斂到全局最小值，如果損失函數(shù)不是凸的，則收斂到局部最小值。

- 梯度是無偏估計的。樣本越多，標(biāo)準(zhǔn)誤差就越低。

主要的缺點：

- 盡管我們可以用向量的方式計算，但是可能仍然會很慢地遍歷所有樣本，特別是數(shù)據(jù)集很大的時候算法的耗時將成為嚴(yán)重的問題。

- 學(xué)習(xí)的每一步都要遍歷所有樣本，這里面一些樣本可能是多余的，并且對更新沒有多大貢獻(xiàn)。

小批量梯度下降

為了克服上述方法的缺點，人們提出了小批量梯度下降。在更新每一參數(shù)時，不用遍歷所有的樣本，而只使用一部分樣本來進(jìn)行更新。 因此，每次只用小批量的b個樣本進(jìn)行更新學(xué)習(xí)，其主要過程如下：

- 打亂訓(xùn)練數(shù)據(jù)集以避免樣本預(yù)先存在順序結(jié)構(gòu)。

- 根據(jù)批量的規(guī)模將訓(xùn)練數(shù)據(jù)集分為b個小批量。如果訓(xùn)練集大小不能被批量大小整除，則將剩余的部分單獨作為一個小批量。

for i in range(num_epochs):

np.random.shuffle(data)

for batch in radom_minibatches(data, batch_size=32):

grad = compute_gradient(batch, params)

params = params — learning_rate * grad

批量的大小我們可以調(diào)整，通常被選為2的冪次方，例如32,64,128,256,512等。其背后的原因是一些像GPU這樣的硬件也是以2的冪次方的批量大小來獲得更好的運(yùn)行時間。

主要的優(yōu)點:

- 比起批量梯度下降，速度更快，因為它少用了很多樣本。

- 隨機(jī)選擇樣本有助于避免對學(xué)習(xí)沒有多大貢獻(xiàn)冗余樣本或非常相似的樣本的干擾。

- 當(dāng)批量的大小小于訓(xùn)練集大小時，會增加學(xué)習(xí)過程中的噪聲，有助于改善泛化誤差。

- 盡管用更多的樣本可以獲得更低的估計標(biāo)準(zhǔn)誤差，但所帶來的計算負(fù)擔(dān)卻小于線性增長

主要缺點：

- 在每次迭代中，學(xué)習(xí)步驟可能會由于噪聲而來回移動。 因此它會在最小值區(qū)域周圍波動，但不收斂。

- 由于噪聲的原因，學(xué)習(xí)步驟會有更多的振蕩（見圖4），并且隨著我們越來越接近最小值，需要增加學(xué)習(xí)衰減來降低學(xué)習(xí)速率。

圖5: 梯度下降：批量與小批量的損失函數(shù)對比

對于大規(guī)模的訓(xùn)練數(shù)據(jù)集，我們通常不需要超過2-10次就能遍歷所有的訓(xùn)練樣本。 注意：當(dāng)批量大小b等于訓(xùn)練樣本數(shù)m時候，這種方法就相當(dāng)于批量梯度下降。

隨機(jī)梯度下降

隨機(jī)梯度下降（SGD）只對樣本（xi，yi）執(zhí)行參數(shù)更新，而不是遍歷所有樣本。因此，學(xué)習(xí)發(fā)生在每個樣本上，其具體過程如下：

- 打亂訓(xùn)練數(shù)據(jù)集以避免樣本預(yù)先存在順序

- 將訓(xùn)練數(shù)據(jù)集劃分為m個樣本。

for i in range(num_epochs):

np.random.shuffle(data)

for example in data:

grad = compute_gradient(example, params)

params = params — learning_rate * grad

它與小批量版本擁有很多相似的優(yōu)點和缺點。以下是特定于SGD的特性：

- 與小批量方法相比，它為學(xué)習(xí)過程增加了更多的噪聲，有助于改善泛化誤差。但同時也增加了運(yùn)行時間。

- 我們不能用向量的形式來處理1個樣本，導(dǎo)致速度非常慢。 此外，由于每個學(xué)習(xí)步驟我們僅使用1個樣本，所以方差會變大。

下圖顯示了梯度下降的變種方法以及它們朝向最小值的方向走勢，如圖所示，與小批量版本相比，SGD的方向噪聲很大：

圖6: 梯度下降變種方法朝向最小值的軌跡

難點

以下是關(guān)于梯度下降算法及其變種遇到的一些常見問題：

- 梯度下降屬于一階優(yōu)化算法，這意味著它不考慮損失函數(shù)的二階導(dǎo)數(shù)。 但是，函數(shù)的曲率會影響每個學(xué)習(xí)步長的大小。梯度描述了曲線的陡度，二階導(dǎo)數(shù)則測量曲線的曲率。因此，如果：

1.二階導(dǎo)數(shù)= 0→曲率是線性的。 因此，步長=學(xué)習(xí)率α。

2.二階導(dǎo)數(shù)> 0→曲率向上。 因此，步長<學(xué)習(xí)率α可能會導(dǎo)致發(fā)散。

3.二階導(dǎo)數(shù)<0→曲率向下。 因此，步長>學(xué)習(xí)率α。

因此，對梯度看起來有希望的方向可能不會如此，并可能導(dǎo)致學(xué)習(xí)過程減慢甚至發(fā)散。

- 如果Hessian矩陣不夠好，比如最大曲率的方向要比最小曲率的方向曲率大得多。 這將導(dǎo)致?lián)p失函數(shù)在某些方向上非常敏感，而在其他方向不敏感。 因此，有些看起來有利于梯度的方向可能不會導(dǎo)致?lián)p失函數(shù)發(fā)生很大變化（請參見圖7）。

圖7: 梯度下降未能利用包含在Hessian矩陣中的曲率信息。

- 隨著每個學(xué)習(xí)步驟完成，梯度gTg的范數(shù)應(yīng)該緩慢下降，因為曲線越來越平緩，曲線的陡度也會減小。 但是，由于曲線的曲率使得梯度的范數(shù)在增加。盡管如此，但我們還能夠獲得非常低的錯誤率（見圖8）。

圖8: 梯度范數(shù). Source

- 在小規(guī)模數(shù)據(jù)集中，局部最小值是常見的; 然而，在大規(guī)模數(shù)據(jù)集中，鞍點更為常見。鞍點是指函數(shù)在某些方向上向上彎曲而在其他方向上向下彎曲。換句話說，鞍點看起來像是一個方向的最小值，另一個方向的最大值（見圖9）。 當(dāng)Hessian矩陣的特征值至少有一個是負(fù)值而其余的特征值是正值時就會發(fā)生這種情況。

圖9: 鞍點

- 如前所述，選擇適當(dāng)?shù)膶W(xué)習(xí)率是困難的。 另外，對于小批量梯度下降，我們必須在訓(xùn)練過程中調(diào)整學(xué)習(xí)速率，以確保它收斂到局部最小值而不是在其周圍來回游蕩。計算學(xué)習(xí)率的衰減率也是很難的，并且這會隨著數(shù)據(jù)集不同而變化。

- 所有參數(shù)更新具有相同的學(xué)習(xí)率; 然而，我們可能更希望對一些參數(shù)執(zhí)行更大的更新，因為這些參數(shù)的方向?qū)?shù)比其他參數(shù)更接近朝向最小值的軌跡，那么就需要針對性的設(shè)定學(xué)習(xí)率及其變化。