1. 文章
An overview of gradient descent optimization algorithms
2. 概要
梯度優(yōu)化算法，作為各大開源庫（如Tensorflow，Keras，PyTorch等）中重要的黑盒子，在網(wǎng)絡(luò)訓(xùn)練中至關(guān)重要，擁有很強(qiáng)的魔力（實用性），但官網(wǎng)一般很少介紹各種梯度優(yōu)化算法變種的原理。作者在這篇文章里，介紹了不同優(yōu)化算法的基本原理，旨在讓讀者知道每個優(yōu)化算法的利弊和適用的場景，也涉及了一些在并行化和分布式下的結(jié)構(gòu)形式。
3. 前言
對于優(yōu)化神經(jīng)網(wǎng)絡(luò)而言，梯度下降是目前最主流、最常見的算法，目前幾乎所有的開源庫都包含豐富的梯度優(yōu)化算法，如Adam、Adagrad，SGD，RMSprop等。作者在文章依次介紹了當(dāng)前常見的算法參數(shù)更新原理，并給出了自己的一些見解。
在給定神經(jīng)網(wǎng)絡(luò)時，梯度下降被用來最小化目標(biāo)函數(shù)J(θ)，通過不斷往負(fù)梯度方向更新網(wǎng)絡(luò)參數(shù)。學(xué)習(xí)率η用來確定每次更新多大的梯度步長。換句話說，我們總是沿著目標(biāo)函數(shù)的斜坡往下走，直到到達(dá)一個山谷（局部最優(yōu)解或者最優(yōu)解）。
4. 梯度下降
4.1 Batch gradient descent
又稱Vanilla gradient descent，通過計算整個訓(xùn)練樣本的梯度來更新參數(shù)θ：
因為我們需要計算所有的訓(xùn)練數(shù)據(jù)的梯度，進(jìn)行一次參數(shù)更新，因此BGD非常慢，無法處理內(nèi)存放不下數(shù)據(jù)的情況，也無法進(jìn)行在線更新。
for i in range(nb_epochs):
params_grad = evaluate_gradient(loss_function, data, params)
Params = params - learning_rate * params_grad
目前各大框架都支持梯度的自動求導(dǎo)，如果要自己實現(xiàn)求導(dǎo)，最好做一下梯度檢查。
4.2 隨機(jī)梯度下降（Stochastic gradient descent）
隨機(jī)梯度下降，每次選取一個樣本進(jìn)行參數(shù)更新：
BGD存在著梯度冗余計算的問題——在每個參數(shù)更新之前，重復(fù)計算了相同的樣本梯度。SGD通常速度更快一些，可用于在線更新。但是因為SGD每次僅用一個樣本進(jìn)行頻繁的參數(shù)更新，可能導(dǎo)致目標(biāo)函數(shù)值震蕩比較厲害，如下圖：
4.3 Mini-Batch gradient descent
MBGD結(jié)合了上述兩個基本算法的優(yōu)點，每次借助batch_size個樣本進(jìn)行參數(shù)更新：
- 降低了參數(shù)跟新的波動方差，保證穩(wěn)定收斂
- 在計算batch樣本的梯度更新參數(shù)時，可以借助矩陣運算，非常高效
- batch_size一般在50~256，根據(jù)不同的任務(wù)取值不同
- batch是很經(jīng)典的思想，在后文中提到的SGD，均指支持batch的SGD
for i in range(nb_epochs):
np.random.shuffle(data)
for batch in get_batches(data, batch_sizes=50):
params_grad = evaluate_gradient(loss_function, batch, params)
Params = params - learning_rate * params_grad
4.4 存在的挑戰(zhàn)
mini-batch梯度下降算法并不能保證能收斂到一個很好解上，主要面臨以下幾個問題：
- 很難選擇一個合適的學(xué)習(xí)率η。學(xué)習(xí)率太小則收斂特別慢，學(xué)習(xí)率太大，會導(dǎo)致在最優(yōu)解附近震蕩，甚至偏離最優(yōu)解得到局部最優(yōu)解
- 自適應(yīng)學(xué)習(xí)率調(diào)度，能夠在訓(xùn)練過程不斷調(diào)整學(xué)習(xí)率的大小。根據(jù)預(yù)定義的降級參數(shù)，可以訓(xùn)練的不同階段，遞減的降低學(xué)習(xí)率的大?。ㄋp因子），但是在何時，以何種尺度衰減學(xué)習(xí)率，同樣是一個難題。
- 此外，所有的參數(shù)共享同一學(xué)習(xí)率η。如果訓(xùn)練數(shù)據(jù)是稀疏的，特征具有不同的頻次，這時我們并不想以同樣的步長更新參數(shù)，更希望對很少出現(xiàn)的特征對應(yīng)的參數(shù)，進(jìn)行更大步長的更新。
- 另一個重要問題是，在神經(jīng)網(wǎng)絡(luò)里常常是嚴(yán)重非凸的誤差函數(shù)，如果避免落入局部最優(yōu)解？Dauphin等人認(rèn)為局部最優(yōu)解并不是最棘手問題——鞍點才是，在鞍點處，梯度接近為0，在用SGD時，很難保證能逃離鞍點區(qū)域。
5. 優(yōu)化算法
作者介紹了目前常見的優(yōu)化算法，這里不討論在高維數(shù)據(jù)中無法技術(shù)實現(xiàn)的算法，如擬牛頓法。
5.1 動量法（Momentum）
SGD在目標(biāo)函數(shù)的“峽谷”處常出現(xiàn)震蕩難以快速收斂的問題，如下圖所示，在每一次更新時，損失函數(shù)會在峽谷處來回擺動。動量法的思想在于通過阻尼這種往復(fù)“擺動”，保持SGD在相對不變方便的動量，以加速收斂速度——抵消峽谷兩側(cè)的動量，維護(hù)向谷底運動的動量。
γ通常取0.9。實質(zhì)上，當(dāng)我們使用動量法時，就像從山上推下一個球，球會逐漸累積往山谷滾的動量，越滾越快。在參數(shù)更新中，動量會對指向相同方向的維度對應(yīng)的參數(shù)進(jìn)行持續(xù)更新，約束梯度方向總是改變的維度參數(shù)，盡可能引導(dǎo)損失函數(shù)向“谷底”收斂。
5.2 Nesterov accelerated gradient（NAG）
但是，讓“球”無腦地沿著斜坡向下滾并不總能得到讓人滿意的解。我們更希望有這樣的一個小球，它能夠?qū)ο乱徊皆趺礉L有個基本的“主見“，在滾過斜坡遇到上坡時，能夠減速，防止越過最優(yōu)解。
NAG則在動量法的基礎(chǔ)上引入了”預(yù)測“的功能。在動量法中，我們用γv_{t-1}更新參數(shù)θ。通過計算θ-γv_{t-1}處的梯度，可以對下一個位置的走向做一個初步的預(yù)估：
依舊設(shè)γ在0.9左右。當(dāng)動量法第一次計算當(dāng)前梯度時（短藍(lán)線），并在累積梯度方向上進(jìn)行了一大步參數(shù)更新（長藍(lán)線）；NAG是首先在之前的梯度方向上走了一大步（棕色線），然后在此位置上評估一下梯度，最后做出一個相對正確的參數(shù)更新（綠線）。這種“先知”更新方法可以避免走過頭而逃離了最優(yōu)解——這在RNN相關(guān)的各種任務(wù)中收益甚好。
以上的參數(shù)更新策略同樣可以適用于SGD。
5.3 Adagrad
Adagrad可以自適應(yīng)的調(diào)節(jié)學(xué)習(xí)率：對于很少更新的參數(shù)采用較大的學(xué)習(xí)率，對于頻繁更新的參數(shù)采取更小的學(xué)習(xí)率——非常適合處理稀疏的數(shù)據(jù)。谷歌的Dean等人發(fā)現(xiàn)，在使用它訓(xùn)練大規(guī)模神經(jīng)網(wǎng)絡(luò)時，Adagrad很大程度上提升了SGD的魯棒性。同時，Penningto等人用它來訓(xùn)練GloVe詞嵌入模型，因為低頻詞相對高頻詞需要更大的學(xué)習(xí)步長。
在之前的優(yōu)化算法中，我們對所有的參數(shù)θ采取了相同的學(xué)習(xí)η。Adagrad在不同訓(xùn)練的step t中，對不同的參數(shù)θi應(yīng)用不同的學(xué)習(xí)率。我們先看每個參數(shù)是怎么更新的，在進(jìn)行向量表示。為了簡要起見，令g(t,i)為在step t下參數(shù)θi的梯度：
SGD在每一步t對參數(shù)θi的更新：
Adagrad修正了上述的更新量，考慮了歷史梯度的信息：
其中Gt是一個對角矩陣，在(i, i)處的元素表示到step t時歷史θi的梯度平方和。分母下的常量是平滑因子（一般取1e-8）。值得注意的是，沒有平方根運算時，算法性能會很差。
Adagrad的好處在于，它避開了人工調(diào)參學(xué)習(xí)率的問題，絕大部分開源庫實現(xiàn)只需要在開始的時候設(shè)置η=0.01即可。
主要缺點在于它累積了歷史梯度作為分母：因為每一個新梯度平方后都是非負(fù)值，在訓(xùn)練過程中，分母會越來越大，導(dǎo)致學(xué)習(xí)率整體會減小直至最后無限小——意味著算法不再能夠?qū)W習(xí)到新的知識。后續(xù)算法會解決這個問題的。
5.4 Adadelta
Adadelta是Adagrad的一種拓展形式——Adadelta僅考慮了一個歷史時間窗口w下的累積梯度（在實現(xiàn)上并非存儲歷史梯度，而是借助衰減因子），避免了Adagrad中學(xué)習(xí)率總是單調(diào)遞減的問題。
在t步時的平均梯度，取決于歷史累積梯度和當(dāng)前梯度（衰減因子作為trade-off）：
γ值類似之前動量法中的因子，通常取0.9。簡單期間，我們重寫一下SGD的參數(shù)更新公式：
在Adagrad優(yōu)化算法中，上兩式變?yōu)椋?/p>
我們把Gt替換為歷史梯度的衰減平方:
對于分母，剛好是梯度的均方根誤差，則上式變?yōu)椋?/p>
作者指出：the units is this update(as well as in SGD, Momentum, or Adagrad) do not match, i.e. the update should have the same hypothetical units as the paramter. 因此，則定義了另一個指數(shù)衰減方式——參數(shù)平方更新，而非梯度的平方。
因此，參數(shù)更新的的均方根誤差為：
但是RMS[delt(θ)t]是未知的，我們借助先前step的參數(shù)更新的估計值逼近。則在之前的更新規(guī)則中用RMS[delt(θ)t-1]代替學(xué)習(xí)率：
在 Adadelta優(yōu)化算法中，并不需要我們設(shè)置學(xué)習(xí)率的初始值，η會自動根據(jù)更新規(guī)則進(jìn)行估計。
5.5 RMSprop
RMSprop是Hinton在他的Coursera課程上提出的（未公布）的自適應(yīng)學(xué)習(xí)率的梯度優(yōu)化方法。它和Adadelta關(guān)注和解決的問題是一樣的——學(xué)習(xí)率的單調(diào)遞減問題。
Hinton 建議γ設(shè)置為0.9，初始學(xué)習(xí)率建議設(shè)置為0.001
5.6 Adam
Adaptive Moment Estimation(Adam)，是另一種針對每個參數(shù)自適應(yīng)調(diào)整學(xué)習(xí)率η的優(yōu)化算法。除了會衰減累積歷史的梯度平方和（類似Adadelta, RMSprop），Adam還會保存歷史梯度的衰減累積和，類似動量的概念：
Mt和vt分別是梯度的一階、二階估計，并在訓(xùn)練開始時被初始為0，Adam的作者觀察到這兩值偏置接近0，尤其在初始化前后且兩個beta的取值接近1時（衰減率很小）。
計算兩個和梯度相關(guān)變量的無偏估計值：
進(jìn)行參數(shù)更新：
作者提出beta1的值建議0.9，beta2的值建議0.999，平滑因子設(shè)置為1e-8。經(jīng)驗上來講，在實際使用中Adam相對于其他自適應(yīng)學(xué)習(xí)率優(yōu)化算法，效果要更好一點
5.7 AdaMax
在Adam中vt的更新規(guī)則類似于在歷史的梯度上應(yīng)用了L2正則：
我們可以基于此擴(kuò)展成Lp正則：
但是p值取得過大可能導(dǎo)致數(shù)值不穩(wěn)定——這也是為什么實際使用中L1和L2才比較常見。但是，當(dāng)p=無窮大時也具有穩(wěn)定行為?；诖耍髡咛岢隽薃daMax，為了避免與Adam混淆，我們使用ut表示無窮正則約束：
我們將ut代替之前Adam更新公式中vt的平方根：
需要指出的是，ut依賴于max操作，因此并不像Adam中的vt和mt那樣偏置接近于0，這也是為什么我們不要計算ut的bias correction的原因。建議η=0.002，beta1=0.9，beta2=0.999
5.8 Nadam
正如上述所見，Adam可以看做是RMSprop和動量法的結(jié)合，NAG是動量法的高階版本。而Nadam(Nesterov-accelerated Adaptive Moment Estimation)則可以看做是Adam和NAG的組合版本。為了把NAG整合進(jìn)Adam里，我們需要修正一下動量mt的計算方式。
首先，我們先回顧下動量法的更新公式：
其中，J是目標(biāo)損失函數(shù)，γ是動量衰減因子，η是學(xué)習(xí)率，上式可以整理為：
從式子中可以看出，動量法涉及兩個部分——歷史動量方向一小步和當(dāng)前梯度方向一小步。NAG考慮了預(yù)測信息，能夠在當(dāng)前梯度方向邁出更加精確的一步：
Dozat提出了一種方式修正NAG：相對于應(yīng)用動量值兩次——①更新梯度gt②更新參數(shù)θt+1，我們現(xiàn)在應(yīng)用一個前視（look-ahead）動量直接更新當(dāng)前參數(shù)：
這里，相對于之前利用mt-1的向量，我們使用了當(dāng)前向量mt做眺望。為了能夠把NAG動量加到Adam中，我們替換了先前的動量向量，首先，回憶一下Adam的更新規(guī)則：
將mt的表達(dá)式帶入最后一個公式里：
括號里的第一項是先前步驟的無偏估計，可以替換為：
考慮到look-ahead的動量，將mt-1替換為mt即可得到Nadam的更新規(guī)則：
5.9 可視化
所有的優(yōu)化算法都是同樣的初始點出發(fā)，可以看出，Adagrad，Adadelta，RMSprop可以很迅速的沿著正確方向收斂，而動量法和NAG開始時會偏離正確收斂方向，但是NAG在后續(xù)的step中由于考慮到了預(yù)見信息，修正了方向。
在鞍點的表現(xiàn)：SGD，動量法和NAG很難突破鞍點的困境——盡管最后后兩者逃離了鞍點。但Adagrad，RMSprop和Adadelta能夠很好的快速找到最優(yōu)負(fù)梯度防線，Adadelta拔得頭籌。
5.10 如何選擇
那么如何選擇合適的優(yōu)化算法呢？
如果數(shù)據(jù)是稀疏的，你也許可以使用自適應(yīng)學(xué)習(xí)率的算法，可幫助你獲取更好的性能，而且不需要手動調(diào)節(jié)學(xué)習(xí)率參數(shù)。
總的來說，RMSprop是Adagrad的擴(kuò)展——在處理梯度單調(diào)衰減問題上。RMSprop，Adadelta，Adam在考慮歷史梯度方面，非常相似。目前，Adam是整體最好的選擇。
SGD雖然傾向于能找到最小值，但是花費的step要更大一些，對權(quán)重初始化比較敏感，不能輕易逃出鞍點，有陷入局部最優(yōu)解的風(fēng)險。如果你在訓(xùn)練一個很深很復(fù)雜的神經(jīng)網(wǎng)絡(luò)，又希望能快速收斂，建議選擇上述自適應(yīng)學(xué)習(xí)率的優(yōu)化算法。
6. 并行和分布式下的SGD
TODO
7. 優(yōu)化SGD的其他技巧
我們討論一些除了優(yōu)化算法之外的能提升模型性能的tircks。
7.1 Shuffling and Curriculum Learning
一般情況下，我們在訓(xùn)練模型時，常常會打亂樣本的輸入順序——否則，模型可能會捕捉這種順序信息，最后得到有偏置的模型。
從另一方面來講，有時候我們目的在于逐漸學(xué)習(xí)越來越難得問題，這時我們可以先喂給模型相對容易區(qū)分學(xué)習(xí)的樣本，然后逐漸提升樣本區(qū)分難度——這稱為Curriculum Learning
7.2 Batch Normalization
為了促進(jìn)學(xué)習(xí)過程，我們一般會對模型參數(shù)進(jìn)行零均值單位方差的初始化，在訓(xùn)練過程中，由于參數(shù)往不同方向更新，網(wǎng)絡(luò)層常會損失這種分布，會導(dǎo)致模型收斂較慢，尤其是網(wǎng)絡(luò)很深的時候。
Batch Normalization會對每個batch的樣本重建這種零均值單位方差的數(shù)據(jù)分布，同時隨著反向傳播進(jìn)行適應(yīng)改變?？梢詫N作為網(wǎng)絡(luò)單獨的一層，這樣我們可以用更大的學(xué)習(xí)率而不用太過關(guān)心參數(shù)初始化問題。BN可以認(rèn)為是一種正則手段，一般不和dropout一起使用。
7.3 Early Stopping
Hinton言：Early stopping is beautiful free lunch. 如果在訓(xùn)練過程中，你的validation error不再下降時，就應(yīng)該考慮終止訓(xùn)練。
7.4 Gradient Noise
Neelakantan等人在每個梯度更新中添加了高斯噪音：
并對方差進(jìn)行了退火處理：
他們指出通過添加高斯噪聲能夠提高模型在初始化不好時的魯棒性，幫助訓(xùn)練復(fù)雜的網(wǎng)絡(luò)，認(rèn)為高斯噪聲能夠幫助模型逃離局部最優(yōu)解。
8. 小結(jié)
作者在這篇文章中，介紹了各種梯度下降優(yōu)化算法的變種——動量法，NAG，Adagrad，Adadelta，RMSprop，Adam，Nadam，Adamax等。
