梯度下降算法是機器學習中使用非常廣泛的優(yōu)化算法，也是眾多機器學習算法中最常用的優(yōu)化方法。幾乎當前每一個先進的(state-of-the-art)機器學習庫或者深度學習庫都會包括梯度下降算法的不同變種實現(xiàn)。但是，它們就像一個黑盒優(yōu)化器，很難得到它們優(yōu)缺點的實際解釋。這篇文章旨在提供梯度下降算法中的不同變種的介紹，幫助使用者根據(jù)具體需要進行使用。

這篇文章首先介紹梯度下降算法的三種框架，然后介紹它們所存在的問題與挑戰(zhàn)，接著介紹一些如何進行改進來解決這些問題，隨后，介紹如何在并行環(huán)境中或者分布式環(huán)境中使用梯度下降算法。***，指出一些有利于梯度下降的策略。

目錄

三種梯度下降優(yōu)化框架

批量梯度下降

隨機梯度下降

小批量梯度下降

問題與挑戰(zhàn)

梯度下降優(yōu)化算法

Momentum

Nesterov accelerated gradient

Adagrad

Adadelta

RMSprop

Adam

算法的可視化

選擇哪種優(yōu)化算法?

并行與分布式SDG

Hogwild!

Downpour SGD

Delay-tolerant Algorithms for SGD

TensorFlow

Elastic Averaging SGD

更多的SDG優(yōu)化策略

訓練集隨機洗牌與課程學習

批規(guī)范化

Early Stopping

Gradient noise

總結(jié)

引用

三種梯度下降優(yōu)化框架

梯度下降算法是通過沿著目標函數(shù)J(θ)參數(shù)θ∈R的梯度(一階導數(shù))相反方向−∇θJ(θ)來不斷更新模型參數(shù)來到達目標函數(shù)的極小值點(收斂)，更新步長為η。

有三種梯度下降算法框架，它們不同之處在于每次學習(更新模型參數(shù))使用的樣本個數(shù)，每次更新使用不同的樣本會導致每次學習的準確性和學習時間不同。

批量梯度下降(Batch gradient descent)

每次使用全量的訓練集樣本來更新模型參數(shù)，即： θ=θ−η⋅∇θJ(θ)

其代碼如下：

epochs 是用戶輸入的***迭代次數(shù)。通過上訴代碼可以看出，每次使用全部訓練集樣本計算損失函數(shù) loss_function 的梯度 params_grad，然后使用學習速率 learning_rate 朝著梯度相反方向去更新模型的每個參數(shù)params。一般各現(xiàn)有的一些機器學習庫都提供了梯度計算api。如果想自己親手寫代碼計算，那么需要在程序調(diào)試過程中驗證梯度計算是否正確。

批量梯度下降每次學習都使用整個訓練集，因此其優(yōu)點在于每次更新都會朝著正確的方向進行，***能夠保證收斂于極值點(凸函數(shù)收斂于全局極值點，非凸函數(shù)可能會收斂于局部極值點)，但是其缺點在于每次學習時間過長，并且如果訓練集很大以至于需要消耗大量的內(nèi)存，并且全量梯度下降不能進行在線模型參數(shù)更新。

隨機梯度下降(Stochastic gradient descent)

隨機梯度下降算法每次從訓練集中隨機選擇一個樣本來進行學習，即： θ=θ−η⋅∇θJ(θ;xi;yi)

批量梯度下降算法每次都會使用全部訓練樣本，因此這些計算是冗余的，因為每次都使用完全相同的樣本集。而隨機梯度下降算法每次只隨機選擇一個樣本來更新模型參數(shù)，因此每次的學習是非?？焖俚模⑶铱梢赃M行在線更新。

其代碼如下：

隨機梯度下降***的缺點在于每次更新可能并不會按照正確的方向進行，因此可以帶來優(yōu)化波動(擾動)，如下圖：

圖1 SGD擾動

不過從另一個方面來看，隨機梯度下降所帶來的波動有個好處就是，對于類似盆地區(qū)域(即很多局部極小值點)那么這個波動的特點可能會使得優(yōu)化的方向從當前的局部極小值點跳到另一個更好的局部極小值點，這樣便可能對于非凸函數(shù)，最終收斂于一個較好的局部極值點，甚至全局極值點。

由于波動，因此會使得迭代次數(shù)(學習次數(shù))增多，即收斂速度變慢。不過最終其會和全量梯度下降算法一樣，具有相同的收斂性，即凸函數(shù)收斂于全局極值點，非凸損失函數(shù)收斂于局部極值點。

小批量梯度下降(Mini-batch gradient descent)

Mini-batch 梯度下降綜合了 batch 梯度下降與 stochastic 梯度下降，在每次更新速度與更新次數(shù)中間取得一個平衡，其每次更新從訓練集中隨機選擇 m,m

θ=θ−η⋅∇θJ(θ;xi:i+m;yi:i+m) 

其代碼如下：

相對于隨機梯度下降，Mini-batch梯度下降降低了收斂波動性，即降低了參數(shù)更新的方差，使得更新更加穩(wěn)定。相對于全量梯度下降，其提高了每次學習的速度。并且其不用擔心內(nèi)存瓶頸從而可以利用矩陣運算進行高效計算。一般而言每次更新隨機選擇[50,256]個樣本進行學習，但是也要根據(jù)具體問題而選擇，實踐中可以進行多次試驗，選擇一個更新速度與更次次數(shù)都較適合的樣本數(shù)。mini-batch梯度下降可以保證收斂性，常用于神經(jīng)網(wǎng)絡(luò)中。

問題與挑戰(zhàn)

雖然梯度下降算法效果很好，并且廣泛使用，但同時其也存在一些挑戰(zhàn)與問題需要解決：

選擇一個合理的學習速率很難。如果學習速率過小，則會導致收斂速度很慢。如果學習速率過大，那么其會阻礙收斂，即在極值點附近會振蕩。

學習速率調(diào)整(又稱學習速率調(diào)度，Learning rate schedules)[11]試圖在每次更新過程中，改變學習速率，如退火。一般使用某種事先設(shè)定的策略或者在每次迭代中衰減一個較小的閾值。無論哪種調(diào)整方法，都需要事先進行固定設(shè)置，這邊便無法自適應(yīng)每次學習的數(shù)據(jù)集特點[10]。

模型所有的參數(shù)每次更新都是使用相同的學習速率。如果數(shù)據(jù)特征是稀疏的或者每個特征有著不同的取值統(tǒng)計特征與空間，那么便不能在每次更新中每個參數(shù)使用相同的學習速率，那些很少出現(xiàn)的特征應(yīng)該使用一個相對較大的學習速率。

對于非凸目標函數(shù)，容易陷入那些次優(yōu)的局部極值點中，如在神經(jīng)網(wǎng)路中。那么如何避免呢。Dauphin[19]指出更嚴重的問題不是局部極值點，而是鞍點。

梯度下降優(yōu)化算法

下面將討論一些在深度學習社區(qū)中經(jīng)常使用用來解決上訴問題的一些梯度優(yōu)化方法，不過并不包括在高維數(shù)據(jù)中不可行的算法，如牛頓法。

Momentum

如果在峽谷地區(qū)(某些方向較另一些方向上陡峭得多，常見于局部極值點)[1]，SGD會在這些地方附近振蕩，從而導致收斂速度慢。這種情況下，動量(Momentum)便可以解決[2]。

動量在參數(shù)更新項中加上一次更新量(即動量項)，即： νt=γνt−1+η ∇θJ(θ)，θ=θ−νt

其中動量項超參數(shù)γ<1一般是小于等于0.9。

其作用如下圖所示：

圖2 沒有動量

圖3 加上動量

加上動量項就像從山頂滾下一個球，求往下滾的時候累積了前面的動量(動量不斷增加)，因此速度變得越來越快，直到到達終點。同理，在更新模型參數(shù)時，對于那些當前的梯度方向與上一次梯度方向相同的參數(shù)，那么進行加強，即這些方向上更快了;對于那些當前的梯度方向與上一次梯度方向不同的參數(shù)，那么進行削減，即這些方向上減慢了。因此可以獲得更快的收斂速度與減少振蕩。

Nesterov accelerated gradient(NAG) 

從山頂往下滾的球會盲目地選擇斜坡。更好的方式應(yīng)該是在遇到傾斜向上之前應(yīng)該減慢速度。

Nesterov accelerated gradient(NAG，涅斯捷羅夫梯度加速)不僅增加了動量項，并且在計算參數(shù)的梯度時，在損失函數(shù)中減去了動量項，即計算∇θJ(θ−γνt−1)，這種方式預估了下一次參數(shù)所在的位置。即：

νt=γνt−1+η⋅∇θJ(θ−γνt−1)，θ=θ−νt 

如下圖所示：

圖4 NAG更新

詳細介紹可以參見Ilya Sutskever的PhD論文[9]。假設(shè)動量因子參數(shù)γ=0.9，首先計算當前梯度項，如上圖小藍色向量，然后加上動量項，這樣便得到了大的跳躍，如上圖大藍色的向量。這便是只包含動量項的更新。而NAG首先來一個大的跳躍(動量項)，然后加上一個小的使用了動量計算的當前梯度(上圖紅色向量)進行修正得到上圖綠色的向量。這樣可以阻止過快更新來提高響應(yīng)性，如在RNNs中[8]。

通過上面的兩種方法，可以做到每次學習過程中能夠根據(jù)損失函數(shù)的斜率做到自適應(yīng)更新來加速SGD的收斂。下一步便需要對每個參數(shù)根據(jù)參數(shù)的重要性進行各自自適應(yīng)更新。

Adagrad

Adagrad[3]也是一種基于梯度的優(yōu)化算法，它能夠?qū)γ總€參數(shù)自適應(yīng)不同的學習速率，對稀疏特征，得到大的學習更新，對非稀疏特征，得到較小的學習更新，因此該優(yōu)化算法適合處理稀疏特征數(shù)據(jù)。Dean等[4]發(fā)現(xiàn)Adagrad能夠很好的提高SGD的魯棒性，google便用起來訓練大規(guī)模神經(jīng)網(wǎng)絡(luò)(看片識貓：recognize cats in Youtube videos)。Pennington等[5]在GloVe中便使用Adagrad來訓練得到詞向量(Word Embeddings), 頻繁出現(xiàn)的單詞賦予較小的更新，不經(jīng)常出現(xiàn)的單詞則賦予較大的更新。

Adagrad主要優(yōu)勢在于它能夠為每個參數(shù)自適應(yīng)不同的學習速率，而一般的人工都是設(shè)定為0.01。同時其缺點在于需要計算參數(shù)梯度序列平方和，并且學習速率趨勢是不斷衰減最終達到一個非常小的值。下文中的Adadelta便是用來解決該問題的。

Adam

Adaptive Moment Estimation (Adam) 也是一種不同參數(shù)自適應(yīng)不同學習速率方法，與Adadelta與RMSprop區(qū)別在于，它計算歷史梯度衰減方式不同，不使用歷史平方衰減，其衰減方式類似動量，如下：

mt=β1mt−1+(1−β1)gt 
vt=β2vt−1+(1−beta2)g2t 

mt與vt分別是梯度的帶權(quán)平均和帶權(quán)有偏方差，初始為0向量，Adam的作者發(fā)現(xiàn)他們傾向于0向量(接近于0向量)，特別是在衰減因子(衰減率)β1,β2接近于1時。為了改進這個問題，

對mt與vt進行偏差修正(bias-corrected)：

mt^=mt1−betat1  
vt^=vt1−betat2 

最終，Adam的更新方程為：

θt+1=θt−ηvt^−−√+ϵmt^ 

論文中建議默認值：β1=0.9，β2=0.999，ϵ=10−8。論文中將Adam與其它的幾個自適應(yīng)學習速率進行了比較，效果均要好。

算法的可視化

下面兩幅圖可視化形象地比較上述各優(yōu)化方法，如圖：

圖5 SGD各優(yōu)化方法在損失曲面上的表現(xiàn)

從上圖可以看出， Adagrad、Adadelta與RMSprop在損失曲面上能夠立即轉(zhuǎn)移到正確的移動方向上達到快速的收斂。而Momentum 與NAG會導致偏離(off-track)。同時NAG能夠在偏離之后快速修正其路線，因為其根據(jù)梯度修正來提高響應(yīng)性。

圖6 SGD各優(yōu)化方法在損失曲面鞍點處上的表現(xiàn)

從上圖可以看出，在鞍點(saddle points)處(即某些維度上梯度為零，某些維度上梯度不為零)，SGD、Momentum與NAG一直在鞍點梯度為零的方向上振蕩，很難打破鞍點位置的對稱性;Adagrad、RMSprop與Adadelta能夠很快地向梯度不為零的方向上轉(zhuǎn)移。

從上面兩幅圖可以看出，自適應(yīng)學習速率方法(Adagrad、Adadelta、RMSprop與Adam)在這些場景下具有更好的收斂速度與收斂性。

如何選擇SGD優(yōu)化器

如果你的數(shù)據(jù)特征是稀疏的，那么你***使用自適應(yīng)學習速率SGD優(yōu)化方法(Adagrad、Adadelta、RMSprop與Adam)，因為你不需要在迭代過程中對學習速率進行人工調(diào)整。

RMSprop是Adagrad的一種擴展，與Adadelta類似，但是改進版的Adadelta使用RMS去自動更新學習速率，并且不需要設(shè)置初始學習速率。而Adam是在RMSprop基礎(chǔ)上使用動量與偏差修正。RMSprop、Adadelta與Adam在類似的情形下的表現(xiàn)差不多。Kingma[15]指出收益于偏差修正，Adam略優(yōu)于RMSprop，因為其在接近收斂時梯度變得更加稀疏。因此，Adam可能是目前***的SGD優(yōu)化方法。

有趣的是，最近很多論文都是使用原始的SGD梯度下降算法，并且使用簡單的學習速率退火調(diào)整(無動量項)?，F(xiàn)有的已經(jīng)表明：SGD能夠收斂于最小值點，但是相對于其他的SGD，它可能花費的時間更長，并且依賴于魯棒的初始值以及學習速率退火調(diào)整策略，并且容易陷入局部極小值點，甚至鞍點。因此，如果你在意收斂速度或者訓練一個深度或者復雜的網(wǎng)絡(luò)，你應(yīng)該選擇一個自適應(yīng)學習速率的SGD優(yōu)化方法。

并行與分布式SGD

如果你處理的數(shù)據(jù)集非常大，并且有機器集群可以利用，那么并行或分布式SGD是一個非常好的選擇，因為可以大大地提高速度。SGD算法的本質(zhì)決定其是串行的(step-by-step)。因此如何進行異步處理便是一個問題。雖然串行能夠保證收斂，但是如果訓練集大，速度便是一個瓶頸。如果進行異步更新，那么可能會導致不收斂。下面將討論如何進行并行或分布式SGD，并行一般是指在同一機器上進行多核并行，分布式是指集群處理。

Hogwild

Niu[23]提出了被稱為Hogwild的并行SGD方法。該方法在多個CPU時間進行并行。處理器通過共享內(nèi)存來訪問參數(shù)，并且這些參數(shù)不進行加鎖。它為每一個cpu分配不重疊的一部分參數(shù)(分配互斥)，每個cpu只更新其負責的參數(shù)。該方法只適合處理數(shù)據(jù)特征是稀疏的。該方法幾乎可以達到一個***的收斂速度，因為cpu之間不會進行相同信息重寫。

Downpour SGD

Downpour SGD是Dean[4]提出的在DistBelief(Google TensorFlow的前身)使用的SGD的一個異步變種。它在訓練子集上訓練同時多個模型副本。這些副本將各自的更新發(fā)送到參數(shù)服務(wù)器(PS,parameter server)，每個參數(shù)服務(wù)器只更新互斥的一部分參數(shù)，副本之間不會進行通信。因此可能會導致參數(shù)發(fā)散而不利于收斂。

Delay-tolerant Algorithms for SGD

McMahan與Streeter[12]擴展AdaGrad，通過開發(fā)延遲容忍算法(delay-tolerant algorithms)，該算法不僅自適應(yīng)過去梯度，并且會更新延遲。該方法已經(jīng)在實踐中表明是有效的。

TensorFlow

TensorFlow[13]是Google開源的一個大規(guī)模機器學習庫，它的前身是DistBelief。它已經(jīng)在大量移動設(shè)備上或者大規(guī)模分布式集群中使用了，已經(jīng)經(jīng)過了實踐檢驗。其分布式實現(xiàn)是基于圖計算，它將圖分割成多個子圖，每個計算實體作為圖中的一個計算節(jié)點，他們通過Rend/Receive來進行通信。

Elastic Averaging SGD 

Zhang等[14]提出Elastic Averaging SGD(EASGD)，它通過一個elastic force(存儲參數(shù)的參數(shù)服務(wù)器中心)來連接每個work來進行參數(shù)異步更新。

更多的SGD優(yōu)化策略

接下來介紹更多的SGD優(yōu)化策略來進一步提高SGD的性能。另外還有眾多其它的優(yōu)化策略，可以參見[22]。

Shuffling and Curriculum Learning 

為了使得學習過程更加無偏，應(yīng)該在每次迭代中隨機打亂訓練集中的樣本。

另一方面，在很多情況下，我們是逐步解決問題的，而將訓練集按照某個有意義的順序排列會提高模型的性能和SGD的收斂性，如何將訓練集建立一個有意義的排列被稱為Curriculum Learning[16]。

Zaremba與Sutskever[17]在使用Curriculum Learning來訓練LSTMs以解決一些簡單的問題中，表明一個相結(jié)合的策略或者混合策略比對訓練集按照按照訓練難度進行遞增排序要好。(表示不懂，衰)

Batch normalization 

為了方便訓練，我們通常會對參數(shù)按照0均值1方差進行初始化，隨著不斷訓練，參數(shù)得到不同程度的更新，這樣這些參數(shù)會失去0均值1方差的分布屬性，這樣會降低訓練速度和放大參數(shù)變化隨著網(wǎng)絡(luò)結(jié)構(gòu)的加深。

Batch normalization[18]在每次mini-batch反向傳播之后重新對參數(shù)進行0均值1方差標準化。這樣可以使用更大的學習速率，以及花費更少的精力在參數(shù)初始化點上。Batch normalization充當著正則化、減少甚至消除掉Dropout的必要性。

Early stopping 

在驗證集上如果連續(xù)的多次迭代過程中損失函數(shù)不再顯著地降低，那么應(yīng)該提前結(jié)束訓練，詳細參見NIPS 2015 Tutorial slides，或者參見防止過擬合的一些方法。

Gradient noise 
Gradient noise[21]即在每次迭代計算梯度中加上一個高斯分布N(0,σ2t)的隨機誤差，即  
gt,i=gt,i+N(0,σ2t) 

高斯誤差的方差需要進行退火：

σ2t=η(1+t)γ 

對梯度增加隨機誤差會增加模型的魯棒性，即使初始參數(shù)值選擇地不好，并適合對特別深層次的負責的網(wǎng)絡(luò)進行訓練。其原因在于增加隨機噪聲會有更多的可能性跳過局部極值點并去尋找一個更好的局部極值點，這種可能性在深層次的網(wǎng)絡(luò)中更常見。

總結(jié)

在上文中，對梯度下降算法的三種框架進行了介紹，并且mini-batch梯度下降是使用最廣泛的。隨后，我們重點介紹了SGD的一些優(yōu)化方法：Momentum、NAG、Adagrad、Adadelta、RMSprop與Adam，以及一些異步SGD方法。***，介紹了一些提高SGD性能的其它優(yōu)化建議，如：訓練集隨機洗牌與課程學習(shuffling and curriculum learning)、batch normalization、early stopping 與 Gradient noise。

希望這篇文章能給你提供一些關(guān)于如何使用不同的梯度優(yōu)化算法方面的指導。如果還有更多的優(yōu)化建議或方法還望大家提出來?或者你使用什么技巧和方法來更好地訓練SGD可以一起交流?Thanks。