【原】女朋友問我什么是最優化原理（上）——系列連載（9）

梯度下降法

基本原理

梯度下降是一種簡單、好用、經典的使用一階信息的最優化方法（意味著相對低廉的計算成本），其基本原理可以想象為一個下山問題，當下降方向與梯度方向一致時，目標函數的方向導數最大，即此時目標函數在當前起點位置的下降速度最快。

基于梯度的優化算法通常有兩個核心元素：搜索方向和搜索步長，并且一般都會和泰勒定理有某種聯系，從泰勒中值定理可以得到下面的等式：

迭代框架

批量梯度下降

按照上面等式，每次迭代，為計算梯度值都需要把所有樣本掃描一遍，收斂曲線類似下圖：

From michaeljancsy

它的優點如下：

·  模型學習與收斂過程通常是平滑的和穩定的；

·  關于收斂條件有成熟完備的理論；

·  針對它有不少利用二階信息加速收斂的技術，例如             conjugate gradient；

·  對樣本噪聲點相對不敏感。

它的缺點如下：

·  收斂速度慢；

·  對初始點敏感；

·  數據集的變化無法被學習到；captured.

·  不太適用于大規模數據。

完全隨機梯度下降（Stochastic Gradient Descent，可以想想這里為什么用Stochastic而不用Random？）每次選擇一個樣本更新權重，這樣會帶來一些噪聲，但可能得到更好的解，試想很多問題都有大量局部最優解，傳統批量梯度下降由于每次收集所有樣后更新梯度值，當初始點確定后基本會落入到離它最近的洼地，而隨機梯度下降由于噪聲的引入會使它有高概率跳出當前洼地，選擇變多從而可能找到更好的洼地。收斂曲線類似下圖：

From michaeljancsy

完全隨機梯度下降和批量梯度下降的優缺點幾乎可以互換：

·  SGD的收斂速度更快；

·  SGD相對來說對初始點不敏感，容易找到更優方案；

·  SGD相對適合于大規模訓練數據；

·  SGD能夠捕捉到樣本數據的變化；

·  噪聲樣本可能導致權重波動從而造成無法收斂到局部最優     解，步長的設計對其非常重要。

實踐當中，很多樣本都有類似的模式，所以SGD可以使用較少的抽樣樣本學習得到局部最優解，當然完全的批量學習和完全的隨機學習都太極端，所以往往采用對兩者的折中。

小批量梯度下降（Mini-batch Gradient Descent）是對SGD和BGD的折中，采用相對小的樣本集學習，樣本集大小隨著學習過程保持或逐步加大，這樣既能有隨機帶來的好處，又能使用二階優化信息加速收斂，目前主流機器學習工具幾乎都支持小批量學習。小批量學習收斂過程如下：

From michaeljancsy

牛頓法

從泰勒展開式可以得到帶最優步長的迭代式：

SGD的一大缺點是函數只和當前樣本有關系，如果樣本存在噪聲則會導致權重波動，一種自然的想法就是即考慮歷史梯度又考慮新樣本的梯度：

對動量的運行過程說明如下:

·  在初始階段，歷史梯度信息會極大加速學習過程（比如       n=2時）；

·  當準備穿越函數波谷時，差的學習率會導致權重向相反方     向更新，于是學習過程會發生回退，這時有動量項的幫助     則有可能越過這個波谷；

·  最后在梯度幾乎為0的時候，動量項的存在又可能會使它     跳出當前局部最小值，于是可能找到更好的最優值點。

Nesterov accelerated gradient 是對動量法的一種改進，具體做法是：首先在之前的方向上邁一大步（棕色向量），之后計算在該點的梯度（紅色向量），然后計算兩個向量的和，得到的向量（綠色向量）作為最終優化方向。

From G. Hinton's lecture 6c

Adagrad同樣是基于梯度的方法，對每個參數給一個學習率，因此對于常出現的權重可以給個小的更新，而不常出現的則給予大的更新，于是對于稀疏數據集就很有效，這個方法常用于大規模神經網絡，Google的FTRL-Proximal也使用了類似方法，可參見：Google Ad Click Prediction a View from the Trenches和Follow-the-Regularized-Leader and Mirror Descent:

Equivalence Theorems and L1 Regularization。

這個方法有點像L2正則，其運作原理如下：

·  在學習前期，梯度比較小regularizer比較大，所以梯度會被放大；

·  在學習后期，梯度比較大regularizer比較小，所以梯度會被縮小。

但它的缺點是，當初始權重過大或經過幾輪訓練后會導致正則化太小，所以訓練將被提前終止。

Adadelta是對Adagrad的改進，解決了以下短板：

·  經過幾輪的訓練會導致正則化太小；

·  需要設置一個全局學習率；

·  當我們更新,等式左邊和右邊的單位不一致。

對于第一個短板，設置一個窗口，僅使用最近幾輪的梯度值去更新正則項但計算 太復雜，所以使用類似動量法的策略：

對其他短板，AdaDelta通過以下方法解決。

來源于Becker 和 LeCuns' 的hessian估計法：

完整的算法描述如下：

From Zeiler

對以上算法的比較如下：

From Karpathy

From SGD optimizationon loss surface contours

Adam

Adam是對Adadelta的改進，原理如下：

算法偽代碼如下：