【干貨】機器學(xué)習最常用優(yōu)化之一：“梯度下降優(yōu)化算法”綜述

梯度下降算法是機器學(xué)習中使用非常廣泛的優(yōu)化算法，也是眾多機器學(xué)習算法中最常用的優(yōu)化方法。

【編者按】本文轉自新智元。文章來(lái)源CSDN，作者：Sebastian Ruder，譯者：一只鳥(niǎo)的天空。

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

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

目錄

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

    批量梯度下降

    隨機梯度下降

    小批量梯度下降

問(wè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)化策略

    訓練集隨機洗牌與課程學(xué)習

    批規范化

    Early Stopping

    Gradient noise

總結

引用

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

梯度下降算法是通過(guò)沿著(zhù)目標函數J(θ)參數θ∈R的梯度（一階導數）相反方向−∇θJ(θ)來(lái)不斷更新模型參數來(lái)到達目標函數的極小值點(diǎn)（收斂），更新步長(cháng)為η。

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

批量梯度下降(Batch gradient descent)

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

其代碼如下：

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

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

隨機梯度下降(Stochastic gradient descent)

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

批量梯度下降算法每次都會(huì )使用全部訓練樣本，因此這些計算是冗余的，因為每次都使用完全相同的樣本集。而隨機梯度下降算法每次只隨機選擇一個(gè)樣本來(lái)更新模型參數，因此每次的學(xué)習是非?？焖俚?，并且可以進(jìn)行在線(xiàn)更新。

其代碼如下：

隨機梯度下降最大的缺點(diǎn)在于每次更新可能并不會(huì )按照正確的方向進(jìn)行，因此可以帶來(lái)優(yōu)化波動(dòng)(擾動(dòng))，如下圖：

圖1 SGD擾動(dòng)

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

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

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

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

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

其代碼如下：

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

問(wèn)題與挑戰

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

選擇一個(gè)合理的學(xué)習速率很難。如果學(xué)習速率過(guò)小，則會(huì )導致收斂速度很慢。如果學(xué)習速率過(guò)大，那么其會(huì )阻礙收斂，即在極值點(diǎn)附近會(huì )振蕩。

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

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

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

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

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

Momentum

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

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

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

其作用如下圖所示：

圖2 沒(méi)有動(dòng)量

圖3 加上動(dòng)量

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

Nesterov accelerated gradient（NAG）

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

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

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

如下圖所示：

圖4 NAG更新

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

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

Adagrad

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

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

Adam

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

mt=β1mt−1+(1−β1)gt

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

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

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

mt^=mt1−betat1

vt^=vt1−betat2

最終，Adam的更新方程為：

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

論文中建議默認值：β1=0.9，β2=0.999，?=10−8。論文中將Adam與其它的幾個(gè)自適應學(xué)習速率進(jìn)行了比較，效果均要好。

算法的可視化

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

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

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

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

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

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

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

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

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

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

并行與分布式SGD

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

Hogwild

Niu[23]提出了被稱(chēng)為Hogwild的并行SGD方法。該方法在多個(gè)CPU時(shí)間進(jìn)行并行。處理器通過(guò)共享內存來(lái)訪(fǎng)問(wèn)參數，并且這些參數不進(jìn)行加鎖。它為每一個(gè)cpu分配不重疊的一部分參數（分配互斥），每個(gè)cpu只更新其負責的參數。該方法只適合處理數據特征是稀疏的。該方法幾乎可以達到一個(gè)最優(yōu)的收斂速度，因為cpu之間不會(huì )進(jìn)行相同信息重寫(xiě)。

Downpour SGD

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

Delay-tolerant Algorithms for SGD

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

TensorFlow

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

Elastic Averaging SGD

Zhang等[14]提出Elastic Averaging SGD(EASGD)，它通過(guò)一個(gè)elastic force(存儲參數的參數服務(wù)器中心）來(lái)連接每個(gè)work來(lái)進(jìn)行參數異步更新。

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

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

Shuffling and Curriculum Learning

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

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

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

Batch normalization

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

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

Early stopping

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

Gradient noise

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

gt,i=gt,i+N(0,σ2t)

高斯誤差的方差需要進(jìn)行退火：

σ2t=η(1+t)γ

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

總結

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

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

本文譯文授權轉載自：http://blog.csdn.net/heyongluoyao8/article/details/52478715

本文未列出全部參考文獻，請戳原文查看。

原文鏈接：http://sebastianruder.com/optimizing-gradient-descent/index.html

最后，記得關(guān)注微信公眾號：鎂客網(wǎng)（im2maker），更多干貨在等你！