一文看懂常用的梯度下降演算法

01-29

概述

梯度下降演算法（Gradient Descent Optimization）是神經網路模型訓練最常用的優化演算法。對於深度學習模型，基本都是採用梯度下降演算法來進行優化訓練的。梯度下降演算法背後的原理：目標函數 $J(theta)$ 關於參數 $theta$ 的梯度將是損失函數（loss function）上升最快的方向。而我們要最小化loss，只需要將參數沿著梯度相反的方向前進一個步長，就可以實現目標函數（loss function）的下降。這個步長 $eta$ 又稱為學習速率。參數更新公式如下：

$thetaleftarrow theta-eta cdot nabla J(theta)$

其中 $nabla J(theta)$ 是參數的梯度，根據計算目標函數採用數據量的不同，梯度下降演算法又可以分為批量梯度下降演算法（Batch Gradient Descent），隨機梯度下降演算法（Stochastic Gradient Descent）和小批量梯度下降演算法（Mini-batch Gradient Descent）。對於批量梯度下降演算法，其 $J(theta)$ 是在整個訓練集上計算的，如果數據集比較大，可能會面臨內存不足問題，而且其收斂速度一般比較慢。隨機梯度下降演算法是另外一個極端， $J(theta)$ 是針對訓練集中的一個訓練樣本計算的，又稱為在線學習，即得到了一個樣本，就可以執行一次參數更新。所以其收斂速度會快一些，但是有可能出現目標函數值震蕩現象，因為高頻率的參數更新導致了高方差。小批量梯度下降演算法是折中方案，選取訓練集中一個小批量樣本（一般是2的倍數，如32，64,128等）計算，這樣可以保證訓練過程更穩定，而且採用批量訓練方法也可以利用矩陣計算的優勢。這是目前最常用的梯度下降演算法。

對於神經網路模型，藉助於BP演算法可以高效地計算梯度，這非常利於採用梯度下降演算法對神經網路進行訓練。梯度下降演算法中一個重要的參數是學習速率，適當的學習速率很重要：學習速率過小時收斂速度慢，而過大時導致訓練震蕩，而且可能會發散。理想的梯度下降演算法要滿足兩點：收斂速度要快；而且能全局收斂。為了這個理想，出現了很多經典梯度下降演算法的變種，下面將分別介紹它們。

Exponentially weighted moving averages

在講各種改進的梯度下降演算法之前，我們先簡單介紹一下exponentially weighted moving averages，即指數加權移動平均數，因為後面講到的很多演算法要用到這個概念。其針對的序列數據，比如 $t$ 時刻的觀測值為 $x(t)$ ，那麼評估 $t$ 時刻的移動平均值為：

$v(t)leftarrow betacdot v(t-1) +(1-beta)cdot x(t)$

其中 $v(t-1)$ 是上一時刻的移動平均值，其實也可以看成歷史積累量，一般 $v(0)=0$ ，而 $beta$ 是一個係數，其在0~1之間，可以看到移動平均值是按比例合併歷史量與當前觀測量。現在我們展開上面的式子：

$v(0)=0$

$v(1)=betacdot v(0)+(1-beta)cdot x(1)$

$v(2)=betacdot v(1)+(1-beta)cdot x(2)=beta (1-beta) cdot x(1)+(1-beta)cdot x(2)$

$v(t)=betacdot v(t-1)+(1-beta)cdot x(t)=sum_{i=1}^{t}{beta ^{t-i}}(1-beta)cdot x(i)$

展開之後，我們可以直觀的看到對於每個 $x$ 值，其權重是不一樣的，實際上是指數遞減的，從當前往後指數遞減，所以距離時刻較近的數據會對當前值影響較大，這樣計算的好處是平均數會比較平穩。由於權重指數衰減，所以移動平均數只是計算比較相近時刻數據的加權平均數，一般可認為這個時間範圍為 $frac{1}{1-beta}$ ，比如 $beta = 0.9$ ，你可以近似認為只是平均了10時刻之內的數據而已，因為再往前權重太小了，基本沒影響了。如果你熟悉級數的話，也可以計算出權重和是近似為1的，這是在無窮的情況下，但是在前期計算時，權重之和是會小於1的，為了解決這個問題，指數加權移動平均數會引入偏差修正：

$v(t)leftarrow frac{v(t)}{1-beta ^{t}}$

其實很好理解，就是前期計算時要放大一下計算結果，而後期不需要，此時 $1-beta ^{t}$ 的值也接近1了。

Momentum optimization

衝量梯度下降演算法是Boris Polyak在1964年提出的，其基於這樣一個物理事實：將一個小球從山頂滾下，其初始速率很慢，但在加速度作用下速率很快增加，並最終由於阻力的存在達到一個穩定速率。對於衝量梯度下降演算法，其更新方程如下：

$mleftarrow gamma cdot m+eta cdotnabla J(theta)$

$theta leftarrow theta - m$

可以看到，參數更新時不僅考慮當前梯度值，而且加上了一個積累項（衝量），但多了一個超參 $gamma$ ，一般取接近1的值如0.9。相比原始梯度下降演算法，衝量梯度下降演算法有助於加速收斂。當梯度與衝量方向一致時，衝量項會增加，而相反時，衝量項減少，因此衝量梯度下降演算法可以減少訓練的震蕩過程。

有時候，衝量梯度下降演算法也可以按下面方式實現：

$mleftarrow beta cdot m+(1-beta)cdotnabla J(theta)$

$theta leftarrow theta - eta cdot m$

此時我們就可以清楚地看到，所謂的衝量項其實只是梯度的指數加權移動平均值。這個實現和之前的實現沒有本質區別，只是學習速率進行了放縮一下而已。

TensorFlow中提供了衝量梯度下降演算法的實現：

tf.train.MomentumOptimizer(learning_rate=learning_rate,nmomentum=0.9)n

Nesterov Accelerated Gradient (NAG)

NAG演算法是Yurii Nesterov在1983年提出的對衝量梯度下降演算法的改進版本，其速度更快。其變化之處在於計算「超前梯度」更新衝量項，具體公式如下：

$mleftarrow gamma cdot m+eta cdotnabla J(theta -gamma cdot m )$

$theta leftarrow theta - m$

既然參數要沿著 $gamma cdot m$ 更新，不妨計算未來位置 $theta -gamma cdot m$ 的梯度，然後合併兩項作為最終的更新項，其具體效果如圖1所示，可以看到一定的加速效果。在TensorFlow中，NAG優化器為：

tf.train.MomentumOptimizer(learning_rate=learning_rate, momentum=0.9, use_nesterov=True)n

圖1 NAG效果圖

AdaGrad

AdaGrad是Duchi在2011年提出的一種學習速率自適應的梯度下降演算法。在訓練迭代過程，其學習速率是逐漸衰減的，經常更新的參數其學習速率衰減更快，這是一種自適應演算法。其更新過程如下：

$sleftarrow s + nabla J(theta)odot nabla J(theta)$

$theta leftarrow theta-frac{eta}{sqrt{s+varepsilon}}odot nabla J(theta)$

其中是梯度平方的積累量 $s$ ，在進行參數更新時，學習速率要除以這個積累量的平方根，其中加上一個很小值 $varepsilon$ 是為了防止除0的出現。由於 $s$ 是逐漸增加的，那麼學習速率是衰減的。考慮如圖2所示的情況，目標函數在兩個方向的坡度不一樣，如果是原始的梯度下降演算法，在接近坡底時收斂速度比較慢。而當採用AdaGrad，這種情況可以被改觀。由於比較陡的方向 $s$ 比較大，其學習速率將衰減得更快，這有利於參數沿著更接近坡底的方向移動，從而加速收斂。

圖2 AdaGrad效果圖

前面說到AdaGrad其學習速率實際上是不斷衰減的，這會導致一個很大的問題，就是訓練後期學習速率很小，導致訓練過早停止，因此在實際中AdaGrad一般不會被採用，下面的演算法將改進這一致命缺陷。不過TensorFlow也提供了這一優化器：tf.train.AdagradOptimizer。

RMSprop

RMSprop是Hinton在他的課程上講到的，其算是對Adagrad演算法的改進，主要是解決學習速率過快衰減的問題。其實思路很簡單，類似Momentum思想，引入一個超參數，在積累梯度平方項進行衰減：

$sleftarrow gammacdot s + (1-gamma)cdot nabla J(theta)odot nabla J(theta)$

$theta leftarrow theta-frac{eta}{sqrt{s+varepsilon}}odot nabla J(theta)$

此時可以看到 $s$ 是梯度平方的指數加權移動平均值，其中 $gamma$ 一般取值0.9，此時 $s$ 更平穩，減少了出現的爆炸情況，因此有助於避免學習速率很快下降的問題。同時Hinton也建議學習速率設置為0.001。RMSprop是屬於一種比較好的優化演算法了，在TensorFlow中當然有其身影：

tf.train.RMSPropOptimizer(learning_rate=learning_rate, momentum=0.9, decay=0.9, epsilon=1e-10)n

不得不說點題外話，同時期還有一個Adadelta演算法，其也是Adagrad演算法的改進，而且改進思路和RMSprop很像，但是其背後是基於一次梯度近似代替二次梯度的思想，感興趣的可以看看相應的論文，這裡不再贅述。

Adaptive moment estimation (Adam)

Adam是Kingma等在2015年提出的一種新的優化演算法，其結合了Momentum和RMSprop演算法的思想。相比Momentum演算法，其學習速率是自適應的，而相比RMSprop，其增加了衝量項。所以，Adam是兩者的結合體：

$mleftarrow beta _{1} cdot m+(1-beta _{1})cdotnabla J(theta)$

$sleftarrowbeta _{2}cdot s + (1-beta _{2})cdot nabla J(theta)odot nabla J(theta)$

$mleftarrow frac{m}{1-beta _{1}^{t}}$

$sleftarrow frac{s}{1-beta _{2}^t}$

$theta leftarrow theta-frac{eta}{sqrt{s+varepsilon}}odot m$

可以看到前兩項和Momentum和RMSprop是非常一致的，由於和的初始值一般設置為0，在訓練初期其可能較小，第三和第四項主要是為了放大它們。最後一項是參數更新。其中超參數的建議值是: $beta _{1}=0.9,beta _{2}=0.999,varepsilon = 1e-8$ 。Adm是性能非常好的演算法，在TensorFlow其實現如下：

tf.train.AdamOptimizer(learning_rate=0.001, beta1=0.9, beta2=0.999, epsilon=1e-08)n

學習速率

前面也說過學習速率的問題，對於梯度下降演算法，這應該是一個最重要的超參數。如果學習速率設置得非常大，那麼訓練可能不會收斂，就直接發散了；如果設置的比較小，雖然可以收斂，但是訓練時間可能無法接受；如果設置的稍微高一些，訓練速度會很快，但是當接近最優點會發生震蕩，甚至無法穩定。不同學習速率的選擇影響可能非常大，如圖3所示。

圖3 不同學習速率的訓練效果

理想的學習速率是：剛開始設置較大，有很快的收斂速度，然後慢慢衰減，保證穩定到達最優點。所以，前面的很多演算法都是學習速率自適應的。除此之外，還可以手動實現這樣一個自適應過程，如實現學習速率指數式衰減：

$eta(t)=eta _{0}cdot10^{-frac{t}{r}}$

在TensorFlow中，你可以這樣實現：

initial_learning_rate = 0.1ndecay_steps = 10000ndecay_rate = 1/10nglobal_step = tf.Variable(0, trainable=False)nnlearning_rate = tf.train.exponential_decay(initial_learning_rate, nglobal_step, decay_steps,ndecay_rate)n# decayed_learning_rate = learning_rate *decay_rate ^ (global_step / decay_steps)noptimizer = tf.train.MomentumOptimizer(learning_rate, momentum=0.9)ntraining_op = optimizer.minimize(loss, global_step=global_step)n

局部最優和鞍點

前面說到，我們希望優化演算法能夠收斂速度快，並且想找到全局最優。對於凸函數來說，其僅有一個極值點，就是全局最優點，如圖4所示，此時採用梯度下降演算法是可以收斂到最優點的，因為沿著下坡的道路走就可以了。但是其實現在的深度學習模型是一個龐大的非線性結構，這樣其一般是非凸函數，就如圖5所示那樣，存在很多局部最優點（local optimum），一旦梯度下降演算法跳進局部陷阱，可以想像其很難走出來，這就很尷尬了，此時梯度下降演算法變得不再那麼可靠，因為我們想要的是全局最優。很難找到全局最優，這可能是目前優化演算法共同面對的問題，如進化演算法。不過到底深度學習的損失函數是不是存在很多局部最優點呢？前面所有的分析都是基於低維空間，我們很容易觀察到局部最優點。但是深度學習的參數一般龐大，其損失函數已經成為了超高維空間。但是Bengio等最新的研究表明，對於高維空間，非凸函數最大的存在不是局部最優點，而是鞍點（saddle point），鞍點也是梯度為0的點，但是它不像局部最優點或者全局最優點。對於局部最優或者全局最優點，其周圍的所有方向要朝向上（最小）或者朝向上（最大），但是考慮到參數龐大，很有可能是一部分方向朝下，一部分方向朝上，這就成為了鞍點。意思就是說在高維度空間，不大可能像低維度空間那樣出現很多局部最優。而且鞍點也不大可能會成為梯度下降演算法的葬身之地。那麼真正影響梯度下降演算法會是什麼呢？可能是平穩區（plateaus），如果出現大面積梯度很小或者近似為0的區域，那麼梯度下降演算法就找不到方向，想像你自己站在一望無際的平原，估計你也方向感全無了。當前上面所有的談論僅是停留在經驗，對於高維空間，無論如何很難直觀想像，這還是一個歷史難題吧。

圖4 凸函數，無局部最優

圖5 存在很多局部最優點的非凸函數

圖6 存在鞍點的函數

總結

本文簡單介紹了梯度下降演算法的分類以及常用的改進演算法，總結來看，優先選擇學習速率自適應的演算法如RMSprop和Adam演算法，大部分情況下其效果是較好的。還有一定要特別注意學習速率的問題。其實還有很多方面會影響梯度下降演算法，如梯度的消失與爆炸，這也是要額外注意的。最後不得不說，梯度下降演算法目前無法保證全局收斂還將是一個持續性的數學難題。

參考資料

An overview of gradient descent optimization algorithms.
Hands-On Machine Learning with Scikit-Learn and TensorFlow, Aurélien Géron, 2017.
NAG
Adagrad
RMSprop
Adadelta
Adam
不同演算法對比的效果可視化
On the saddle point problem for non-convex optimization

歡迎交流與轉載，文章會同步發布在公眾號：機器學習演算法全棧工程師(Jeemy110)