從梯度下降演算法的詳解及實現到共軛牛頓法等優化演算法的基本概念

梯度下降法，是當今最流行的優化（optimization）演算法，亦是至今最常用的優化神經網路的方法。與此同時，最新的深度學習程序庫都包含了各種優化梯度下降的演算法（可以參見如 lasagne、caffe 及 Kera 等程序庫的說明文檔）。但它們的演算法則不被公開，都作為黑箱優化器被使用，這也就是為什麼它們的優勢和劣勢往往難以被實際地解釋。

本文旨在讓你對不同的優化梯度下降法的演算法有一個直觀認識，以幫助你使用這些演算法。我們首先會考察梯度下降法的各種變體，然後會簡要地總結在訓練（神經網路或是機器學習演算法）的過程中可能遇到的挑戰。接著，我們將會討論一些最常見的優化演算法，研究它們的解決這些挑戰的動機及推導出更新規律（update rules）的過程。我們還會簡要探討一下，在平行計算或是分布式處理情況下優化梯度下降法的演算法和架構。最後，我們會考慮一下其他有助於優化梯度下降法的策略。

梯度下降法的核心，是最小化目標函數 J(θ)，其中θ是模型的參數，θ∈Rd。它的方法是，在每次迭代中，對每個變數，按照目標函數在該變數梯度的相反方向，更新對應的參數值。其中，學習率η決定了函數到達（局部）最小值的迭代次數。換句話說，我們在目標函數的超平面上，沿著斜率下降的方向前進，直到我們遇到了超平面構成的「谷底」。如果你不熟悉梯度下降法的話，你可以在這裡找到一個很好的關於優化神經網路的介紹。

梯度下降法變體

本文討論了三種梯度下降法的變體——它們的不同之處在於，一次性使用多少數據來計算目標函數的梯度。對於不同的數據量，我們需要在參數更新準確性和參數更新花費時間兩方面做出權衡。

批量梯度下降法（Batch Gradient Descent）

Vanilla 梯度下降法（譯者註：Vanilla 是早期機器學習演算法相關的名詞，也是如今一個機器學習 python 程序庫的名字，在該處指的是後者，參見：https://github.com/vinhkhuc/VanillaML），也就是大家所熟知的批量梯度下降法，在整個數據集上（求出罰函數 J(θ 並）對每個參數 θ 求目標函數 J(θ) 的偏導數：

在該方法中，每次更新我們都需要在整個數據集上求出所有的偏導數。因此批量梯度下降法的速度會比較慢，甚至對於較大的、內存無法容納的數據集，該方法都無法被使用。同時，梯度下降法不能以「在線」的形式更新我們的模型，也就是不能再運行中加入新的樣本進行運算。

批量梯度下降法的實現代碼，如下所示：

for i in range(nb_epochs):

對於給定的迭代次數，我們首先基於輸入的罰函數 loss_function 對輸入的參數向量 params 計算梯度向量 params_grad。注意，最新的深度學習程序庫中，提供了自動求導的功能，能夠高效、快速地求給定函數對於特定參數的導數。如果你希望自己寫代碼求出梯度值，那麼「梯度檢查」會是一個不錯的注意。（你可以參考這裡，了解關於如何檢查梯度的相關建議。）

然後，我們對參數減去梯度值乘學習率的值，也就是在反梯度方向，更新我們參數。當目標函數 J(θ) 是一凸函數時，則批量梯度下降法必然會在全局最小值處收斂；否則，目標函數則可能會局部極小值處收斂。

隨機梯度下降法（Stochastic Gradient Descent）

相比批量梯度下降法，隨機梯度下降法的每次更新，是對數據集中的一個樣本（x，y）求出罰函數，然後對其求相應的偏導數：

因為批量梯度下降法在每次更新前，會對相似的樣本求算梯度值，因而它在較大的數據集上的計算會有些冗餘（redundant）。而隨機梯度下降法通過每次更新僅對一個樣本求梯度，去除了這種冗餘的情況。因而，它的運行速度被大大加快，同時也能夠「在線」學習。

隨機梯度下降法更新值的方差很大，在頻繁的更新之下，它的目標函數有著如下圖所示的劇烈波動。

SGD 函數波動，來源：Wikipedia

相比批量梯度下降法的收斂會使目標函數落入一個局部極小值，SGD 收斂過程中的波動，會幫助目標函數跳入另一個可能的更小的極小值。另一方面，這最終會讓收斂到特定最小值的過程複雜化，因為該方法可能持續的波動而不停止。但是，當我們慢慢降低學習率的時候，SGD 表現出了與批量梯度下降法相似的收斂過程，也就是說，對非凸函數和凸函數，必然會分別收斂到它們的極小值和最小值。

相比批量梯度下降法的代碼，在如下的代碼中，我們僅僅加入了一個循環，用以遍歷所有的訓練樣本並求出相應的梯度值。注意，如這裡所說，在每次迭代中，我們會打亂訓練數據集。

for i in range(nb_epochs):

小批量梯度下降法（Mini-Batch Gradient Descent）

小批量梯度下降法集合了上述兩種方法的優勢，在每次更新中，對 n 個樣本構成的一批數據，計算罰函數 J(θ)，並對相應的參數求導：

這種方法，(a) 降低了更新參數的方差（variance），使得收斂過程更為穩定；(b) 能夠利用最新的深度學習程序庫中高度優化的矩陣運算器，能夠高效地求出每小批數據的梯度。通常一小批數據含有的樣本數量在 50 至 256 之間，但對於不同的用途也會有所變化。小批量梯度下降法，通常是我們訓練神經網路的首選演算法。同時，有時候我們也會使用隨機梯度下降法，來稱呼小批量梯度下降法（譯者註：在下文中，我們就用 SGD 代替隨機梯度下降法）。注意：在下文對於隨機梯度法優化的介紹中，為方便起見，我們會省略式子中的參數 x(i:i+n),y(i:i+n)。

如下的代碼所示，我們不再對每個樣本進行循環，而是對每批帶有 50 個樣本的小批數據進行循環：

for i in range(nb_epochs):

面臨的挑戰

由於 Vanilla 小批量梯度下降法並不能保證良好地收斂，這給我們留下了如下待解決的挑戰：

• 選擇適當的學習率是一個難題。太小的學習率會導致較慢的收斂速度，而太大的學習率則會阻礙收斂，並會引起罰函數在最小值處震蕩，甚至有可能導致結果發散；

• 我們可以設置一個關於學習率地列表，通過如退火的方法，在學習過程中調整學習率——按照一個預先定義的列表、或是當每次迭代中目標函數的變化小於一定閾值時來降低學習率。但這些列表或閾值，需要根據數據集地特性，被提前定義。

• 此外，我們對所有的參數都採用了相同的學習率。但如果我們的數據比較稀疏，同時特徵有著不同的出現頻率，那麼我們不希望以相同的學習率來更新這些變數，我們希望對較少出現的特徵有更大的學習率。

在對神經網路最優化非凸的罰函數時，另一個通常面臨的挑戰，是如何避免目標函數被困在無數的局部最小值中，以導致的未完全優化的情況。Dauphin 及其他人 [19] 認為，這個困難並不來自於局部最小值，而是來自於「鞍點」，也就是在一個方向上斜率是正的、在一個方向上斜率是負的點。這些鞍點通常由一些函數值相同的面環繞，它們在各個方向的梯度值都為 0，所以 SGD 很難從這些鞍點中脫開。

以下是其他幾種經典的最優化方法，可用於神經網路等演算法收斂到全局（或局部）最優解。

牛頓法

牛頓法是二階演算法，因為該演算法使用了海塞矩陣（Hessian matrix）求權重的二階偏導數。牛頓法的目標就是採用損失函數的二階偏導數尋找更好的訓練方向。現在我們將採用如下表示： f(wi) = fi、?f(wi) = gi 和 Hf(wi) = Hi。在 w0 點使用泰勒級數展開式二次逼近函數 f。

H0 為函數 f 在點 w0 的海塞矩陣。通過將 g 設定為 0，我們就可以找到 f(w) 的極小值，也就得到了以下方程式。

因此，從參數向量 w0 開始，牛頓法服從以下方式進行迭代：

向量 Hi-1·gi（參考上式）也就是所說的牛頓下降步（Newton"s step）。注意，參數的這些變化將朝著極大值而不是極小值逼近，出現這樣的情況是因為海塞矩陣非正定。因此在不能保證矩陣正定的情況下，損失函數並不能保證在每一次迭代中都是減少的。為了防止上述問題，牛頓法的方程式通常可以修改為：

學習速率η同樣可是設定為固定常數或通過單變數優化取值。向量 d=Hi-1·gi（參考上式）現在就稱為牛頓訓練方向（Newton"s training direction）。

使用牛頓法的訓練過程狀態圖就如下圖所示。從此圖可以看出來，系統首先通過獲得牛頓訓練方向，然後獲得合適的學習速率來進行參數的更新優化。

下面的梯度圖展示了牛頓法的性能。因為牛頓法是採用其損失函數的二階偏導數尋找更好的訓練下降方向，所以它相比梯度下降只要更少的迭代次數就能下降到損失函數的極小值，因此函數收斂速度也會大幅度地加快。

然而，牛頓法的困難之處在於其計算量，因為對海塞矩陣及其逆的精確求值在計算量方面是十分巨大的。

共軛梯度法（Conjugate gradient）

共軛梯度法可認為是梯度下降法和牛頓法的中間物。該演算法希望能加速梯度下降的收斂速度，同時避免使用海塞矩陣進行求值、儲存和求逆獲得必要的優化信息。

在共軛梯度訓練演算法中，因為是沿著共軛方向（conjugate directions）執行搜索的，所以通常該演算法要比沿著梯度下降方向優化收斂得更迅速。共軛梯度法的訓練方向是與海塞矩陣共軛的。

我們用 d 表示訓練方向向量，然後從初始參數向量 w0 和初始訓練方向向量 d0=-g0 開始，共軛梯度法所構建的訓練方向序列為：

在上式中，γ 稱之為共軛參數，並且有一些方法計算這個參數。兩種最常用的方法是源自 Fletcher、Reeves 和 Polak 、Ribiere。對於所有的共軛梯度演算法，訓練方向周期性地重置為負梯度向。

參數通過下面的表達式得以更新和優化。通常學習速率η可使用單變數函數優化方法求得。

共軛梯度法的訓練過程流程圖就如下所示。從圖中我們可以看出來模型是通過第一次計算共軛梯度訓練方向而優化參數的，然後再尋找適當的學習速率。

共軛梯度法已經證實其在神經網路中要比梯度下降法有效得多。並且由於共軛梯度法並沒有要求使用海塞矩陣，所以在大規模神經網路中其還是可以做到很好的性能。

擬牛頓法（Quasi-Newton method）

因為需要很多的操作求解海塞矩陣的值還有計算矩陣的逆，應用牛頓法所產生的計算量是十分巨大的。因此有一種稱之為擬牛頓法（quasi-Newton）或變數矩陣法來解決這樣的缺點。這些方法並不是直接計算海塞矩陣然後求其矩陣的逆，擬牛頓法是在每次迭代的時候計算一個矩陣，其逼近海塞矩陣的逆。最重要的是，該逼近值只是使用損失函數的一階偏導來計算。

海塞矩陣由損失函數的二階偏導組成，擬牛頓法背後的思想主要是僅使用損失函數的一階偏導數，通過另一矩陣 G 逼近海塞矩陣的逆。擬牛頓法的公式可以表示為：

學習速率 η可以設定為固定常數，也可以通過單變數函數優化得到。其中矩陣 G 逼近海塞矩陣的逆，且有不同的方式進行逼近。通常，最常用的兩種方式是 Davidon–Fletcher–Powell formula (DFP) 和 the Broyden–Fletcher–Goldfarb–Shanno formula (BFGS)。

擬牛頓法的訓練過程流程圖就如下所示。從圖中我們可以看出來模型是通過第一次計算擬牛頓訓練方向而優化參數的，然後再尋找適當的學習速率。

擬牛頓法適用於絕大多數案例中：它比梯度下降和共軛梯度法收斂更快，並且也不需要確切地計算海塞矩陣及其逆矩陣。

Levenberg-Marquardt 演算法

Levenberg-Marquardt 演算法，也稱之為衰減最小二乘法（damped least-squares method），該演算法的損失函數採用平方誤差和的形式。該演算法的執行也不需要計算具體的海塞矩陣，它僅僅只是使用梯度向量和雅可比矩陣（Jacobian matrix）。

該演算法的損失函數如下方程式所示為平方誤差和的形式：

在上式中，m 是數據集樣本的數量。

我們可以定義損失函數的雅可比矩陣以誤差對參數的偏導數為元素，如下方程式所示：

其中 m 是數據集樣本的數量，n 是神經網路的參數數量。那麼雅可比矩陣就是 m×n 階矩陣。

損失函數的梯度向量就可以按如下計算出來：

e 在這裡是所有誤差項的向量。

最終，我們可以用以下表達式逼近海塞矩陣：

其中λ為衰減因子，它確保了海塞矩陣的正定性（positiveness），I 是單位矩陣。

下面的表達式定義了 Levenberg-Marquardt 演算法中參數的更新和優化過程：

當衰減參數λ為 0 時，Levenberg-Marquardt 演算法就是使用海塞矩陣逼近值的牛頓法。而當 λ很大時，該演算法就近似於採用很小學習速率的梯度下降法。如果進行迭代導致了損失函數上升，衰減因子λ就會增加。如果損失函數下降，那麼λ就會下降，從而 Levenberg-Marquardt 演算法更接近於牛頓法。該過程經常用於加速收斂到極小值點。

使用 Levenberg-Marquardt 法的神經網路訓練過程狀態圖就如下圖所示。第一步就是計算損失函數、梯度和海塞矩陣逼近值，隨後再在每次迭代降低損失中調整衰減參數。

正如我們所了解到的，Levenberg-Marquardt 演算法是為平方誤差和函數所定製的。這就讓使用這種誤差度量的神經網路訓練地十分迅速。然而 Levenberg-Marquardt 演算法還有一些缺點，第一就是其不能用於平方根誤差或交叉熵誤差（cross entropy error）等函數，此外該演算法還和正則項不兼容。最後，對於大型數據集或神經網路，雅可比矩陣會變得十分巨大，因此也需要大量的內存。所以我們在大型數據集或神經網路中並不推薦採用 Levenberg-Marquardt 演算法。