理解梯度下降法

08-10

理解梯度下降法

91 人贊了文章

導言最優化問題在機器學習中有非常重要的地位，很多機器學習演算法最後都歸結為求解最優化問題。在各種最優化演算法中，梯度下降法是最簡單、最常見的一種，在深度學習的訓練中被廣為使用。在本文中，SIGAI將為大家系統的講述梯度下降法的原理和實現細節問題

最優化問題

最優化問題是求解函數極值的問題，包括極大值和極小值。相信所有的讀者對這個問題都不陌生，在初中時我們就學會了求解二次函數的極值（拋物線的頂點），高中時學習了冪函數，指數函數，對數函數，三角函數，反三角函數等各種類型的函數，求函數極值的題更是頻頻出現。這些方法都採用了各種各樣的技巧，沒有一個統一的方案。

真正的飛躍發生在大學時，微積分為我們求函數的極值提供了一個統一的思路：找函數的導數等於0的點，因為在極值點處，導數必定為0。這樣，只要函數的可導的，我們就可以用這個萬能的方法解決問題，幸運的是，在實際應用中我們遇到的函數基本上都是可導的。

在機器學習之類的實際應用中，我們一般將最優化問題統一表述為求解函數的極小值問題，即：

其中x稱為優化變數，f稱為目標函數。極大值問題可以轉換成極小值問題來求解，只需要將目標函數加上負號即可：

有些時候會對優化變數x有約束，包括等式約束和不等式約束，它們定義了優化變數的可行域，即滿足約束條件的點構成的集合。在這裡我們先不考慮帶約束條件的問題。

一個優化問題的全局極小值 $x^{*}$ 是指對於可行域里所有的x，有：

即全局極小值點處的函數值不大於任意一點處的函數值。局部極小值 $x^{*}$ 定義為存在一個 $delta$ 鄰域，對於在鄰域內：

並且在可行域內的所有x，有：

即局部極小值點處的函數值比一個局部返回內所有點的函數值都小。在這裡，我們的目標是找到全局極小值。不幸的是，有些函數可能有多個局部極小值點，因此即使找到了導數等於0的所有點，還需要比較這些點處的函數值。

導數與梯度

由於實際應用中一般都是多元函數，因此我們跳過一元函數，直接介紹多元函數的情況。梯度是導數對多元函數的推廣，它是多元函數對各個自變數偏導數形成的向量。多元函數的梯度定義為：

其中? 稱為梯度運算元，它作用於一個多元函數，得到一個向量。下面是計算函數梯度的一個例子：

可導函數在某一點處取得極值的必要條件是梯度為0，梯度為0的點稱為函數的駐點，這是疑似極值點。需要注意的是，梯度為0隻是函數取極值的必要條件而不是充分條件，即梯度為0的點可能不是極值點。

至於是極大值還是極小值，要看二階導數/Hessian矩陣，Hessian矩陣我們將在後面的文章中介紹，這是由函數的二階偏導數構成的矩陣。這分為下面幾種情況：

如果Hessian矩陣正定，函數有極小值如果Hessian矩陣負定，函數有極大值如果Hessian矩陣不定，則需要進一步討論

這和一元函數的結果類似，Hessian矩陣可以看做是一元函數的二階導數對多元函數的推廣。一元函數的極值判別法為，假設在某點處導數等於0，則：

如果二階導數大於0，函數有極小值如果二階導數小於0，函數有極大值如果二階導數等於0，情況不定

在這裡我們可能會問：直接求函數的導數/梯度，然後令導數/梯度為0，解方程，問題不就解決了嗎？事實上沒這麼簡單，因為這個方程可能很難解。比如下面的函數：

我們分別對x和y求偏導數，並令它們為0，得到下面的方程組：

這個方程非常難以求解，對於有指數函數，對數函數，三角函數的方程，我們稱為超越方程，求解的難度並不比求極值本身小。

精確的求解不太可能，因此只能求近似解，這稱為數值計算。工程上實現時通常採用的是迭代法，它從一個初始點 $X_{0}$ 開始，反覆使用某種規則從 $X_{k}$ 移動到下一個點 $X_{k+1}$ ，構造這樣一個數列，直到收斂到梯度為0的點處。即有下面的極限成立：

這些規則一般會利用一階導數信息即梯度；或者二階導數信息即Hessian矩陣。這樣迭代法的核心是得到這樣的由上一個點確定下一個點的迭代公式：

這個過程就像我們處于山上的某一位置，要到山底找水喝，因此我們必須到達最低點處：

此時我們沒有全局信息，根本就不知道哪裡是地勢最低的點，只能想辦法往山下走，走一步看一步。剛開始我們在山上的某一點處，每一步，我們都往地勢更低的點走，以期望能走到山底。

推導過程

首先我們來看一元函數的泰勒展開，以便於更好的理解多元函數的泰勒展開。如果一個一元函數n階可導，它的泰勒展開公式為：

如果在某一點處導數值大於0（+），則函數在此處是增函數，加大x的值函數值會增加，減小x的值（-）函數會減小。相反的，如果在某一點處導數值小於0（-），則函數是減函數，增加x的值函數值會減小（+），減小x的值函數會增加。因此我們可以得出一個結論：如果x的變化很小，並且變化值與導數值反號，則函數值下降。對於一元函數，x的變化只有兩個方向，要麼朝左，要麼朝右。

下面我們把這一結論推廣到多元函數的情況。多元函數 $f(x)$ 在x點處的泰勒展開為：

這裡我們忽略了二次及更高的項。其中，一次項是梯度向量? $f(x)$ 與自變數增量 $Delta X$ 的內積 $(? f(x))^{T}Delta x$ ，這等價於一元函數的 $f(x_{0})(x-x_{0})$ 。這樣，函數的增量與自變數的增量

$Delta x$ 、函數梯度的關係可以表示為：

如果 $Delta x$ 足夠小，在x的某一鄰域內，則我們可以忽略二次及以上的項，有：

這裡的情況比一元函數複雜多了，是一個向量， $Delta x$ 有無窮多種方向，該往哪個方向走呢？如果能保證：

則有：

即函數值遞減，這就是下山的正確方向。因為有：

在這裡，||·||表示向量的模， $heta$ 是向量 $? f(x)$ 和 $Delta x$ 的夾角。因為向量的模一定大於等於0，如果：

則能保證：

即選擇合適的增量 $Delta x$ ，就能保證函數值下降，要達到這一目的，只要保證梯度和 $Delta x$ 的夾角的餘弦值小於等於0就可以了。由於有：

只有當：

時 $cos heta$ 有極小值-1，此時梯度和 $Delta x$ 反向，即夾角為180度。因此當向量 $Delta x$ 的模大小一定時，當：

即在梯度相反的方向函數值下降的最快。此時有：

函數的下降值為：

只要梯度不為0，往梯度的反方向走函數值一定是下降的。直接用 $Δx = ??f (x )$ 可能會有問題，因為 $X+Delta X$ 可能會超出x的鄰域範圍之外，此時是不能忽略泰勒展開中的二次及以上的項的，因此步伐不能太大。一般設：

其中 $alpha$ 為一個接近於0的正數，稱為步長，由人工設定，用於保證 $X+Delta X$ 在x的鄰域內，從而可以忽略泰勒展開中二次及更高的項，則有：

從初始點 $X_{0}$ 開始，使用如下迭代公式：

只要沒有到達梯度為0的點，則函數值會沿著序列 $X_{k}$ 遞減，最終會收斂到梯度為0的點，這就是梯度下降法。迭代終止的條件是函數的梯度值為0（實際實現時是接近於0），此時認為已經達到極值點。注意我們找到的是梯度為0的點，這不一定就是極值點，後面會說明。梯度下降法只需要計算函數在某些點處的梯度，實現簡單，計算量小。

實現細節問題

下面我們介紹梯度下降法實現時的一些細節問題，包括初始值的設定，學習率的設定，下面分別進行介紹。

初始值的設定

一般的，對於不帶約束條件的優化問題，我們可以將初始值設置為0，或者設置為隨機數，對於神經網路的訓練，一般設置為隨機數，這對演算法的收斂至關重要[1]。

學習率的設定

學習率設置為多少，也是實現時需要考慮的問題。最簡單的，我們可以將學習率設置為一個很小的正數，如0.001。另外，可以採用更複雜的策略，在迭代的過程中動態的調整學習率的值。比如前1萬次迭代為0.001，接下來1萬次迭代時設置為0.0001。

面臨的問題

在實現時，梯度下降法可能會遇到一些問題，典型的是局部極小值和鞍點問題，下面分別進行介紹。

局部極小值

有些函數可能有多個局部極小值點，下面是一個例子：

這張圖中的函數有3個局部極值點，分別是A，B和C，但只有A才是全局極小值，梯度下降法可能迭代到B或者C點處就終止。

鞍點

鞍點是指梯度為0，Hessian矩陣既不是正定也不是負定，即不定的點。下面是鞍點的一個例子，假設有函數：

顯然在(0, 0)這點處不是極值點，但梯度為0，下面是梯度下降法的運行結果：

在這裡，梯度下降法遇到了鞍點，認為已經找到了極值點，從而終止迭代過程，而這根本不是極值點。

對於怎麼逃離局部極小值點和鞍點，有一些解決方案，在這裡我們暫時不細講，以後有機會再專門寫文章介紹。對於凸優化問題，不會遇到上面的局部極小值與鞍點問題，即梯度下降法一定能找到全局最優解。凸優化的概念將在SIGAI後續的文章中介紹。

變種

梯度下降法有大量的變種，它們都只利用之前迭代時的梯度信息來構造每次的更新值，下面我們分別進行介紹。最直接的改進是為迭代公式加上動量項，動量項累積了之前的權重更新值，加上此項之後的參數更新公式為：

其中 $V_{t+1}$ 是動量項，它取代了之前的梯度項。動量項的計算公式為：

動量項累積了之前的梯度信息，類似於保持行走時的慣性，以避免來回震蕩，加快收斂速度。

AdaGrad的為自適應梯度，即adaptive gradient演算法[2]，是梯度下降法最直接的改進。唯一不同的是，AdaGrad根據前幾輪迭代時的歷史梯度值來調整學習率，參數更新公式為：

其中 $alpha$ 是學習因子， $g_{t}$ 是第t次迭代時的參數梯度向量， $varepsilon$ 是一個很小的正數，為了避免除0操作，下標 $i$ 表示向量的分量。和標準梯度下降法唯一不同的是多了分母中的這一項，它累積了到本次迭代為止梯度的歷史值信息用於生成梯度下降的係數值。

AdaDelta演算法[3]也是梯度下降法的變種，在每次迭代時也利用梯度值構造參數的更新值。假設要優化的參數為x，梯度下降法第t次迭代時計算出來的參數梯度值為 $g_{t}$ 。演算法首先初始化如下兩個向量為0向量：

其中 $E[g^{2}]$ 是梯度平方（對每個分量分別平分）的累計值，更新公式為：

在這裡 $g^{2}$ 是向量每個元素分別計算平方，後面所有的計算公式都是對向量的每個分量進行。接下來計算如下RMS量：

這也是一個向量，計算時分別對向量的每個分量進行。然後計算參數的更新值：

$RMS[Delta X]_{t-1}$ 的計算公式和這個類似。這個更新值同樣通過梯度來構造，只不過學習率是通過梯度的歷史值確定的。更新公式為：

參數更新的迭代公式為：

和帶動量項的梯度下降法不同的是這裡用歷史梯度值來構造學習率，包括了梯度的平方值。

Adam演算法[4]全稱為adaptive moment estimation，它由梯度項構造了兩個向量m和v，它們的初始值為0，更新公式為：

其中 $eta_{1},eta_{2}$ 是人工指定的參數， $i$ 為向量的分量下標。依靠這兩個值構造參數的更新值，參數的更新公式為：

在這裡，用m代替梯度，用v來構造學習率。

NAG演算法是一種凸優化方法，由Nesterov提出。和標準梯度下降法的權重更新公式類似，NAG演算法構造一個向量v，初始值為0。v的更新公式為：

參數的更新公式為：

與帶動量項的SGD相比NAG只是計算梯度時用的參數值不同，NAG計算誤差梯度時考慮了動量項，使用的是 $X_{t}+mu V_{t}$ ，其他都是一樣的。

RMSProp演算法[5]也是標準梯度下降法的變種，它由梯度值構造一個向量MS，初始化為0，更新公式為：

參數更新公式為：

其中 $delta$ 是人工設定的參數。這種方法通過梯度的歷史信息來生成參數更新值的權重係數。

隨機梯度下降法

對於有些機器學習問題，我們的目標函數是對樣本的損失函數。假設訓練樣本集有N個樣本，訓練時優化的目標是這個數據集上的平均損失函數：

其中 $L(W,X_{i},Y_{i})$ 是對單個訓練樣本 $(X_{i},Y_{i})$ 的損失函數，w是需要學習的參數。如果訓練時每次都用所有樣本計算梯度並更新，成本太高，作為改進可以在每次迭代時選取一批樣本，將損失函數定義在這些樣本上。

批量隨機梯度下降法在每次迭代中使用上面目標函數的隨機逼近值，即只使用 $Mll N$

個樣本來近似計算損失函數。在每次迭代時要優化的目標函數變為：

已經證明，隨機梯度下降法在數學期望的意義下收斂，即隨機採樣產生的梯度的期望值是真實的梯度。因為每次迭代時的目標函數實際上是不一樣的，因此隨機梯度下降法並不能保證每次迭代時函數值一定下降。

參考文獻

[1] I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the Importance of Initialization and Momentum in Deep Learning. Proceedings of the 30th International Conference on Machine Learning, 2013.

[2] Duchi, E. Hazan, and Y. Singer. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. The Journal of Machine Learning Research, 2011.

[3] M. Zeiler. ADADELTA: An Adaptive Learning Rate Method. arXiv preprint, 2012.

[4] D. Kingma, J. Ba. Adam: A Method for Stochastic Optimization. International Conference for Learning Representations, 2015.

[5] T. Tieleman, and G. Hinton. RMSProp: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning.Technical report, 2012.

[6] Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (8 October 1986). Learning representations by back-propagating errors. Nature. 323 (6088): 533–536.

[7] L. Bottou. Stochastic Gradient Descent Tricks. Neural Networks: Tricks of the Trade. Springer, 2012.