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

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

目錄

三種梯度下降優化框架

批量梯度下降

隨機梯度下降

小批量梯度下降

問題與挑戰

梯度下降優化算法

Momentum

Nesterov accelerated gradient

Adagrad

Adadelta

RMSprop

Adam

算法的可視化

選擇哪種優化算法?

并行與分布式SDG

Hogwild!

Downpour SGD

Delay-tolerant Algorithms for SGD

TensorFlow

Elastic Averaging SGD

更多的SDG優化策略

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

批規范化

Early Stopping

Gradient noise

總結

引用

三種梯度下降優化框架

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

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

批量梯度下降(Batch gradient descent)

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

其代碼如下：

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

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

隨機梯度下降(Stochastic gradient descent)

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

批量梯度下降算法每次都會使用全部訓練樣本，因此這些計算是冗余的，因為每次都使用完全相同的樣本集。而隨機梯度下降算法每次只隨機選擇一個樣本來更新模型參數，因此每次的學習是非常快速的，并且可以進行在線更新。

其代碼如下：

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

圖1 SGD擾動

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

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

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

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

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

其代碼如下：

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

問題與挑戰

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

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

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

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

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

梯度下降優化算法

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

Momentum

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

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

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

其作用如下圖所示：

圖2 沒有動量

圖3 加上動量

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

Nesterov accelerated gradient(NAG) 

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

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

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

如下圖所示：

圖4 NAG更新

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

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

Adagrad

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

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

Adam

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

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

mt與vt分別是梯度的帶權平均和帶權有偏方差，初始為0向量，Adam的作者發現他們傾向于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與其它的幾個自適應學習速率進行了比較，效果均要好。

算法的可視化

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

圖5 SGD各優化方法在損失曲面上的表現

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

圖6 SGD各優化方法在損失曲面鞍點處上的表現

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

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

如何選擇SGD優化器

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

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

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

并行與分布式SGD

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

Hogwild

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

Downpour SGD

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

Delay-tolerant Algorithms for SGD

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

TensorFlow

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

Elastic Averaging SGD 

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

更多的SGD優化策略

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

Shuffling and Curriculum Learning 

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

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

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

Batch normalization 

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

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

Early stopping 

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

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

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

σ2t=η(1+t)γ 

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

總結

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

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