【AI初識境】為了圍剿SGD大家這些年想過的那十幾招(從momentum到Adabound)
這是《AI初識境》第7篇，這次我們說說常用的優化演算法。所謂初識，就是對相關技術有基本了解，掌握了基本的使用方法。
深度學習框架目前基本上都是使用一階的梯度下降演算法及其變種進行優化，在此基礎上也發展出了很多的改進演算法。另外，近年來二階的優化演算法也開始慢慢被研究起來。
今天就來說說神經網路的優化相關的內容。
作者&編輯 | 言有三
1 優化簡述
深度學習模型的優化是一個非凸優化問題，這是與凸優化問題對應的。
對於凸優化來說，任何局部最優解即為全局最優解。用貪婪演算法或梯度下降法都能收斂到全局最優解，損失曲面如下。
而非凸優化問題則可能存在無數個局部最優點，損失曲面如下，可以看出有非常多的極值點，有極大值也有極小值。
除了極大極小值，還有一類值為「鞍點」，簡單來說，它就是在某一些方向梯度下降，另一些方向梯度上升，形狀似馬鞍，如下圖紅點就是鞍點。
對於深度學習模型的優化來說，鞍點比局部極大值點或者極小值點帶來的問題更加嚴重。
目前常用的優化方法分為一階和二階，這裡的階對應導數，一階方法只需要一階導數，二階方法需要二階導數。
常用的一階演算法就是：隨機梯度下降SGD及其各類變種了。
常用的二階演算法就是：牛頓法等。
我們這裡主要還是說一階方法，二階方法因為計算量的問題，現在還沒有被廣泛地使用。
2 梯度下降演算法
本文目標不是為了從零開始講清楚優化演算法，所以有些細節和基礎就略過。
梯度下降演算法，即通過梯度的反方向來進行優化，批量梯度下降（Batch gradient descent）用公式表述如下：
寫成偽代碼如下：
for i in range(nb_epochs):
params_grad = evaluate_gradient(loss_function, data, params)
params = params - learning_rate * params_grad
上面的梯度下降演算法用到了數據集所有的數據，這在解決實際問題時通常是不可能，想想Imagenet1000有100G以上的圖像，內存裝不下，速度也很慢。
我們需要在線能夠實時計算，於是一次取一個樣本，就有了隨機梯度下降（Stochastic gradient descent），簡稱sgd。
公式如下：
寫成偽代碼如下：
for i in range(nb_epochs):
np.random.shuffle(data)
for example in data:
params_grad = evaluate_gradient(loss_function , example , params)
params = params - learning_rate * params_grad
sgd方法缺點很明顯，梯度震蕩，所以就有了後來大家常用的小批量梯度下降演算法（Mini-batch gradient descent）。
偽代碼如下：
for i in range(nb_epochs):
np.random.shuffle(data)
for batch in get_batches(data, batch_size=50):
params_grad = evaluate_gradient(loss_function, batch, params)
params = params - learning_rate * params_grad
下面我們要形成共識，說sgd演算法，實際上指的就是mini-batch gradient descent演算法，沒有人會去一次拿整個數據集或者一個樣本進行優化。
當然還是要總結一下SGD演算法的毛病。
(1) 學習率大小和策略選擇困難，想必動手經驗豐富的自然懂。
(2) 學習率不夠智能，對參數的各個維度一視同仁。
(3) 同時面臨局部極值和鞍點的問題。
3 梯度下降演算法改進
1 Momentum 動量法
在所有的改進演算法中，我覺得真正最有用的就是它。
前面說了梯度下降演算法是按照梯度的反方向進行參數更新，但是剛開始的時候梯度不穩定呀，方向改變是很正常的，梯度就是抽瘋了似的一下正一下反，導致做了很多無用的迭代。
而動量法做的很簡單，相信之前的梯度。如果梯度方向不變，就越發更新的快，反之減弱當前梯度。
畫成圖就是這樣。
效果對比就這意思。
2 Nesterov accelerated gradient法 ，簡稱NAG演算法
仍然是動量法，只是它要求這個下降更加智能。
既然動量法已經把前一次的梯度和當前梯度融合，那何不更進一步，直接先按照前一次梯度方向更新一步將它作為當前的梯度，看下面的式子就明白了。
如上圖，自己領會。nesterov的好處就是，當梯度方向快要改變的時候，它提前獲得了該信息，從而減弱了這個過程，再次減少了無用的迭代。
3 Adagrad法
思路很簡單，不同的參數是需要不同的學習率的，有的要慢慢學，有的要快快學，所以就給了一個權重咯，而且是用了歷史上所有的梯度幅值。
4 Adadelta與Rmsprop
Adagrad用了所有的梯度，問題也就來了，累加的梯度幅值是越來越大的。導致學習率前面的乘因子越來越小，後來就學不動了呀。
Adadelta就只是動了一丟丟小心思，只累加了一個窗口的梯度，而且計算方法也更有效。
並且，將學習率用前一時刻參數的平方根來代替，最終更新演算法變成了這樣。
把γ變成0.9，就是RMSprop方法了，這個方法在Hinton的課程中使用的，沒有發表成論文，畢竟有Adadelta了，沒有發表必要。與adadelta另一個不同是還是需要學習率的，建議0.001。
5 Adam方法
Adam演算法可能是除了SGD演算法之外大家最熟悉的了，無腦使用，不需調參。
Adam對梯度的一階和二階都進行了估計與偏差修正，使用梯度的一階矩估計和二階矩估計來動態調整每個參數的學習率。
看出來了吧，與Adadelta和Rmsprop如出一轍，與Momentum SGD也頗為相似。上面的式子根據梯度對參數更新的幅度進行了動態調整，所以Adam對學習率沒有那麼敏感。
Adam每次迭代參數的學習步長都有一個確定的範圍，不會因為很大的梯度導致很大的學習步長，參數的值比較穩定，但是它也並非真的是參數不敏感的，學習率在訓練的後期可仍然可能不穩定導致無法收斂到足夠好的值，泛化能力較差，這在文[3]中有非常詳細的研究，後面也會簡單說一下。
6 AdaMax
將Adam使用的二階矩變成更高階，就成了Adamax演算法。
7 Nadam法
Nag加上Adam，就成了Nadam方法，即帶有動量項的Adam，所以形式也很簡單，如下，可以將其分別與Adam演算法和NAG演算法的式子比較看看。
8 AMSgrad方法
ICLR 2018最佳論文提出了AMSgrad方法，研究人員觀察到Adam類的方法之所以會不能收斂到好的結果，是因為在優化演算法中廣泛使用的指數衰減方法會使得梯度的記憶時間太短。
在深度學習中，每一個mini-batch對結果的優化貢獻是不一樣的，有的產生的梯度特別有效，但是也一視同仁地被時間所遺忘。
具體的做法是使用過去平方梯度的最大值來更新參數，而不是指數平均。
9 Adafactor方法
Adam演算法有兩個參數，beta1和beta2，相關研究表明beta2的值對收斂結果有影響，如果較低，衰減太大容易不收斂，反之就容易收斂不穩定。Adafactor是通過給beta1和beta2本身也增加了一個衰減。
beta2的值剛開始是0，之後隨著時間的增加而逼近預設值。
10 Adabound方法
上面說了，beta2的值造成Adam演算法有可能不收斂或者不穩定而找不到全局最優解，落實到最後的優化參數那就是不穩定和異常(過大或者過小)的學習率。Adabound採用的解決問題的方式就非常的簡單了，那就是限制最大和最小值範圍，約束住學習率的大小。
ηl(t)和ηu(t)分別是一個隨著時間單調遞增和遞減的函數，最後兩者收斂到同一個值。
說了這麼多，對上面各種方法從一個鞍點開始優化，表現如何的預期效果圖如下，參考文[1]。
理論上，就是上面這樣的。文章作者會告訴你對於數據稀疏的問題，用自適應學習率演算法就好了，而且使用人家推薦的參數就好。其中，Adam會最佳。
4 總結
4.1 改進方法是否都比SGD演算法強？
上面說了這麼多理論，分析起來頭頭是道，各種改進版本似乎各個碾壓SGD演算法。但是否真的如此。筆者曾經做過一個簡單的實驗，結果如下。
所有方法都採用作者們的默認配置，並且進行了參數調優，不好的結果就不拿出來了。
- nesterov方法，與sgd演算法同樣的配置。
- adam演算法，m1=0.9，m2=0.999，lr=0.001。
- rms演算法，rms_decay=0.9，lr=0.001。
- adagrad，adadelta學習率不敏感。
看起來好像都不如SGD演算法，實際上這是一個很普遍的現象，各類開源項目和論文[3-4]都能夠印證這個結論。
總體上來說，改進方法降低了調參工作量，只要能夠達到與精細調參的SGD相當的性能，就很有意義了，這也是Adam流行的原因。但是，改進策略帶來的學習率和步長的不穩定還是有可能影響演算法的性能，因此這也是一個研究的方向，不然哪來這麼多Adam的變種呢。
4.2 二階方法研究的怎麼樣了呢？
二階的方法因為使用了導數的二階信息，因此其優化方向更加準確，速度也更快，這是它的優勢。
但是它的劣勢也極其明顯，使用二階方法通常需要直接計算或者近似估計Hessian 矩陣，一階方法一次迭代更新複雜度為O(N)，二階方法就是O(N*N)，深層神經網路中變數實在是太多了，搞不動的。
不過，還是有研究者去研究的。比如東京工業大學和NVIDIA在[5]中使用的K-FAC方法，用1024塊Tesla V100豪無人性地在10分鐘內把ImageNet在35個epoch內訓練到75%的top-1精度。K-FAC已經在CNN的訓練中很常用了，感興趣的可以去了解。
其他的二階方法筆者也關注到了一些，以後等有了比較多穩定靠譜的研究，再來分享吧。
[1] Ruder S. An overview of gradient descent optimization algorithms[J]. arXiv preprint arXiv:1609.04747, 2016.
[2] Reddi S J, Kale S, Kumar S. On the convergence of adam and beyond[J]. 2018.
[3] Bottou L, Curtis F E, Nocedal J. Optimization methods for large-scale machine learning[J]. Siam Review, 2018, 60(2): 223-311.
[4] Keskar N S, Socher R. Improving generalization performance by switching from adam to sgd[J]. arXiv preprint arXiv:1712.07628, 2017.
[5] Osawa K, Tsuji Y, Ueno Y, et al. Second-order Optimization Method for Large Mini-batch: Training ResNet-50 on ImageNet in 35 Epochs[J]. arXiv preprint arXiv:1811.12019, 2018.
更多請移步知乎專欄《有三AI學院》
推薦閱讀：