數值優化演算法

⑴ 優化演算法

動量法、AdaGrad、RMSProp、AdaDelta、Adam

在7.2節（梯度下降和隨機梯度下降）中我們提到，目標函數有關自變數的梯度代表了目標函數在自變數當前位置下降最快的方向。因此，梯度下降也叫作最陡下降（steepest descent）。在每次迭代中，梯度下降根據自變數當前位置，沿著當前位置的梯度更新自變數。然而，如果自變數的迭代方向 僅僅取決於自變數當前位置，這可能會帶來一些問題 。

可以看到，同一位置上，目標函數在豎直方向（ 軸方向）比在水平方向（ 軸方向）的斜率的絕對值更大。因此，給定學習率，梯度下降迭代自變數時會使自變數在豎直方向比在水平方向移動幅度更大。那麼，我們 需要一個較小的學習率 從而避免自變數在豎直方向上越過目標函數最優解。然而，這會造成自變數在水平方向上 朝最優解移動變慢 。

試著將學習率調大一點，此時自變數在豎直方向不斷越過最優解並逐漸發散。

動量法的提出是為了解決梯度下降的上述問題。

其中，動量超參數 滿足 。當 時，動量法等價於小批量隨機梯度下降。

因此，在實際中，我們常常將 看作是最近 個時間步的 的值的加權平均。

現在，我們對動量法的速度變數做變形：

優化演算法中，⽬標函數⾃變數的每⼀個元素在相同時間步都使⽤同⼀個學習率來⾃我迭代。在「動量法」⾥我們看到當x1和x2的梯度值有較⼤差別時，需要選擇⾜夠小的學習率使得⾃變數在梯度值較⼤的維度上不發散。但這樣會導致⾃變數在梯度值較小的維度上迭代過慢。動量法依賴指數加權移動平均使得⾃變數的更新⽅向更加⼀致，從而降低發散的可能。 本節我們介紹AdaGrad演算法，它根據⾃變數在每個維度的梯度值的⼤小來調整各個維度上的學習率，從而避免統⼀的學習率難以適應所有維度的問題。

AdaGrad演算法會使⽤⼀個小批量隨機梯度gt按元素平⽅的累加變數st。在時間步0，AdaGrad將s0中每個元素初始化為0。在時間步t，⾸先將小批量隨機梯度gt按元素平⽅後累加到變數st：

其中⊙是按元素相乘。接著，我們將⽬標函數⾃變數中每個元素的學習率通過按元素運算重新調整⼀下：

其中η是學習率，ϵ是為了維持數值穩定性而添加的常數，如10的-6次方。這⾥開⽅、除法和乘法的運算都是按元素運算的。這些按元素運算使得⽬標函數⾃變數中 每個元素都分別擁有⾃⼰的學習率 。

需要強調的是，小批量隨機梯度按元素平⽅的累加變數st出現在學習率的分⺟項中。因此，

然而，由於st⼀直在累加按元素平⽅的梯度，⾃變數中每個元素的學習率在迭代過程中⼀直在降低（或不變）。 所以，當學習率在迭代早期降得較快且當前解依然不佳時，AdaGrad演算法在迭代後期由於學習率過小，可能較難找到⼀個有⽤的解 。

當學習率在迭代早期降得較快且當前解依然不佳時，AdaGrad演算法在迭代後期由於 學習率過小 ，可能較難找到⼀個有⽤的解。為了解決這⼀問題，RMSProp演算法對AdaGrad演算法做了⼀點小小的修改。

不同於AdaGrad演算法⾥狀態變數st是 截⾄時間步t所有小批量隨機梯度gt按元素平⽅和 ，RMSProp演算法將這些梯度 按元素平⽅做指數加權移動平均 。具體來說，給定超參數0 ≤ γ < 1，RMSProp演算法在時間步t > 0計算：

和AdaGrad演算法⼀樣，RMSProp演算法將⽬標函數⾃變數中每個元素的學習率通過按元素運算重新調整，然後更新⾃變數：

其中η是學習率，ϵ是為了維持數值穩定性而添加的常數，如10的-6次方。因為RMSProp演算法的狀態變數st是對平⽅項gt ⊙ gt的指數加權移動平均， 所以可以看作是最近1/(1 − γ)個時間步的小批量隨機梯度平⽅項的加權平均。如此⼀來，⾃變數每個元素的學習率在迭代過程中就不再⼀直降低（或不變）。

除了RMSProp演算法以外，另⼀個常⽤優化演算法AdaDelta演算法也針對AdaGrad演算法在迭代後期可能較難找到有⽤解的問題做了改進。有意思的是，AdaDelta演算法沒有學習率這⼀超參數。

AdaDelta演算法也像RMSProp演算法⼀樣，使⽤了小批量隨機梯度gt按元素平⽅的指數加權移動平均變數st。在時間步0，它的所有元素被初始化為0。給定超參數0 ≤ ρ < 1（對應RMSProp演算法中的γ），在時間步t > 0，同RMSProp演算法⼀樣計算：

與RMSProp演算法不同的是，AdaDelta演算法還維護⼀個 額外的狀態變數∆xt ，其元素同樣在時間步0時被初始化為0。我們使⽤∆xt−1來計算⾃變數的變化量：

最後，我們使⽤∆xt來記錄⾃變數變化量 按元素平⽅的指數加權移動平均：

Adam演算法在RMSProp演算法基礎上對小批量隨機梯度也做了指數加權移動平均。
Adam演算法使⽤了 動量變數vt 和RMSProp演算法中 小批量隨機梯度按元素平⽅的指數加權移動平均變數st ，並在時間步0將它們中每個元素初始化為0。給定超參數0 ≤ β1 < 1（演算法作者建議設為0.9），時間步t的動量變數vt即小批量隨機梯度gt的指數加權移動平均：

接下來，Adam演算法使⽤以上 偏差修正 後的變數 v ˆ t 和 s ˆ t ，將模型參數中每個元素的學習率通過按元素運算重新調整：

其中 η 是學習率， ϵ 是為了維持數值穩定性而添加的常數，如10的-8次方。和AdaGrad演算法、RMSProp演算法以及AdaDelta演算法⼀樣，⽬標函數⾃變數中每個元素都分別擁有⾃⼰的學習率。最後，使⽤ 迭代⾃變數：

⑵ 優化演算法

  SGD演算法中的一個關鍵參數是學習率。之前，我們介紹的SGD使用固定的學習率。在實踐中，有必要隨著時間的推移逐漸降低學習率，因此我們將第 k 步迭代的學習率記作 ϵ k 。
  這是因為SGD中梯度估計引入的雜訊源（m 個訓練樣本的隨機采樣）並不會在極小點處消失。相比之下，當我們使用批量梯度下降到達極小點時，整個代價函數的真實梯度會變得很小，之後為 0，因此批量梯度下降可以使用固定的學習率。保證SGD收斂的一個充分條件是

  若 ϵ 0 太大，學習曲線將會劇烈振盪，代價函數值通常會明顯增加。溫和的振盪是良好的，容易在訓練隨機代價函數（例如使用Dropout的代價函數）時出現。如果學習率太小，那麼學習過程會很緩慢。如果初始學習率太低，那麼學習可能會卡在一個相當高的代價值。通常，就總訓練時間和最終代價值而言，最優初始學習率會高於大約迭代 100 次左右後達到最佳效果的學習率。因此，通常最好是檢測最早的幾輪迭代，選擇一個比在效果上表現最佳的學習率更大的學習率，但又不能太大導致嚴重的震盪。

  雖然隨機梯度下降仍然是非常受歡迎的優化方法，但其學習過程有時會很慢。動量方法 (Polyak, 1964) 旨在加速學習，特別是處理高曲率、小但一致的梯度，或是帶雜訊的梯度。動量演算法積累了之前梯度指數級衰減的移動平均，並且繼續沿該方向移動。動量的效果如圖8.5所示

  受 Nesterov 加速梯度演算法 (Nesterov, 1983, 2004) 啟發，提出了動量演算法的一個變種。這種情況的更新規則如下：

  其中參數 α 和 ϵ 發揮了和標准動量方法中類似的作用。Nesterov 動量和標准動量之間的區別體現在梯度計算上。Nesterov 動量中，梯度計算在施加當前速度之後。因此，Nesterov 動量可以解釋為往標准動量方法中添加了一個校正因子。完整的Nesterov動量演算法如演算法3.2所示

  初始點能夠決定演算法是否收斂，有些初始點十分不穩定，使得該演算法會遭遇數值困難，並完全失敗。當學習收斂時，初始點可以決定學習收斂得多快，以及是否收斂到一個代價高或低的點。此外，差不多代價的點可以具有區別極大的泛化誤差，初始點也可以影響泛化。
  也許完全確知的唯一特性是初始參數需要在不同單元間 『『破壞對稱性』』。如果具有相同激活函數的兩個隱藏單元連接到相同的輸入，那麼這些單元必須具有不同的初始參數。如果它們具有相同的初始參數，然後應用到確定性損失和模型的確定性學習演算法將一直以相同的方式更新這兩個單元。即使模型或訓練演算法能夠使用隨機性為不同的單元計算不同的更新（例如使用Dropout的訓練），通常來說，最好還是初始化每個單元使其和其他單元計算不同的函數。這或許有助於確保沒有輸入模式
丟失在前向傳播的零空間中，沒有梯度模式丟失在反向傳播的零空間中。每個單元計算不同函數的目標促使了參數的隨機初始化。我們可以明確地搜索一大組彼此互不相同的基函數，但這經常會導致明顯的計算代價。例如，如果我們有和輸出一樣多的輸入，我們可以使用 Gram-Schmidt 正交化於初始的權重矩陣，保證每個單元計算彼此非常不同的函數。在高維空間上使用高熵分布來隨機初始化，計算代價小並且不太可能分配單元計算彼此相同的函數。
  通常情況下，我們可以為每個單元的偏置設置啟發式挑選的常數，僅隨機初始化權重。額外的參數（例如用於編碼預測條件方差的參數）通常和偏置一樣設置為啟發式選擇的常數。
  我們幾乎總是初始化模型的權重為高斯或均勻分布中隨機抽取的值。高斯或均勻分布的選擇似乎不會有很大的差別，但也沒有被詳盡地研究。然而，初始分布的大小確實對優化過程的結果和網路泛化能力都有很大的影響。
  更大的初始權重具有更強的破壞對稱性的作用，有助於避免冗餘的單元。它們也有助於避免在每層線性成分的前向或反向傳播中丟失信號——矩陣中更大的值在矩陣乘法中有更大的輸出。如果初始權重太大，那麼會在前向傳播或反向傳播中產生爆炸的值。在循環網路中，很大的權重也可能導致混沌（chaos）（對於輸入中很小的擾動非常敏感，導致確定性前向傳播過程表現隨機）。在一定程度上，梯度爆炸問題可以通過梯度截斷來緩解（執行梯度下降步驟之前設置梯度的閾值）。較大的權
重也會產生使得激活函數飽和的值，導致飽和單元的梯度完全丟失。這些競爭因素決定了權重的理想初始大小。
  也有助於避免在每層線性成分的前向或反向傳播中丟失信號——矩陣中更大的值在矩陣乘法中有更大的輸出。如果初始權重太大，那麼會在前向傳播或反向傳播中產生爆炸的值。在循環網路中，很大的權重也可能導致混沌（chaos）（對於輸入中很小的擾動非常敏感，導致確定性前向傳播過程表現隨機）。在一定程度上，梯度爆炸問題可以通過梯度截斷來緩解（執行梯度下降步驟之前設置梯度的閾值）。較大的權重也會產生使得激活函數飽和的值，導致飽和單元的梯度完全丟失。這些競爭因素決定了權重的理想初始大小。
  有些啟發式方法可用於選擇權重的初始大小。一種初始化 m 個輸入和 n 輸出的全連接層的權重的啟發式方法是從分布 U(−1/√ m ,
1/√ m ) 中采樣權重，而 Glorot and Bengio 建議使用標准初始化

  後一種啟發式方法初始化所有的層，折衷於使其具有相同激活方差和使其具有相同梯度方差之間。這假設網路是不含非線性的鏈式矩陣乘法，據此推導得出。現實的神經網路顯然會違反這個假設，但很多設計於線性模型的策略在其非線性對應中的效果也不錯。
  數值范圍准則的一個缺點是，設置所有的初始權重具有相同的標准差，例如1/√ m ，會使得層很大時每個單一權重會變得極其小。Martens (2010) 提出了一種被稱為稀疏初始化（sparse initialization）的替代方案，每個單元初始化為恰好有 k 個非零權重。這個想法保持該單元輸入的總數量獨立於輸入數目 m，而不使單一權重元素的大小隨 m 縮小。稀疏初始化有助於實現單元之間在初始化時更具多樣性。但是，獲得較大取值的權重也同時被加了很強的先驗。因為梯度下降需要很長時間縮小 『『不正確』』 的大值，這個初始化方案可能會導致某些單元出問題，例如maxout單元有幾個過濾器，互相之間必須仔細調整。

  Delta-bar-delta 演算法 (Jacobs, 1988) 是一個早期的在訓練時適應模型參數各自學習率的啟發式方法。該方法基於一個很簡單的想法，如果損失對於某個給定模型參數的偏導保持相同的符號，那麼學習率應該增加。如果對於該參數的偏導變化了符號，那麼學習率應減小。當然，這種方法只能應用於全批量優化中。

  AdaGrad 演算法，如演算法8.4所示，獨立地適應所有模型參數的學習率，縮放每個參數反比於其所有梯度歷史平方值總和的平方根 (Duchi et al., 2011)。具有損失最大偏導的參數相應地有一個快速下降的學習率，而具有小偏導的參數在學習率上有相對較小的下降。凈效果是在參數空間中更為平緩的傾斜方向會取得更大的進步。

  在凸優化背景中，AdaGrad 演算法具有一些令人滿意的理論性質。然而，經驗上已經發現，對於訓練深度神經網路模型而言，從訓練開始時積累梯度平方會導致有效學習率過早和過量的減小。AdaGrad在某些深度學習模型上效果不錯，但不是全部。

  RMSProp 演算法 (Hinton, 2012) 修改 AdaGrad 以在非凸設定下效果更好，改變梯度積累為指數加權的移動平均。AdaGrad旨在應用於凸問題時快速收斂。當應用於非凸函數訓練神經網路時，學習軌跡可能穿過了很多不同的結構，最終到達一個局部是凸碗的區域。AdaGrad 根據平方梯度的整個歷史收縮學習率，可能使得學習率在達到這樣的凸結構前就變得太小了。RMSProp 使用指數衰減平均以丟棄遙遠過去的歷史，使其能夠在找到凸碗狀結構後快速收斂，它就像一個初始化於該碗狀結構的 AdaGrad 演算法實例。
  RMSProp 的標准形式如演算法8.5所示，結合 Nesterov 動量的形式如演算法8.6所示。相比於 AdaGrad，使用移動平均引入了一個新的超參數ρ，用來控制移動平均的長度范圍。經驗上，RMSProp 已被證明是一種有效且實用的深度神經網路優化演算法。目前它是深度學習從業者經常採用的優化方法之一。

  Adam (Kingma and Ba, 2014) 是另一種學習率自適應的優化演算法，最好被看作結合 RMSProp 和具有一些重要區別的動量的變種。首先，在 Adam 中，動量直接並入了梯度一階矩（指數加權）的估計。將動量加入 RMSProp 最直觀的方法是將動量應用於縮放後的梯度。結合縮放的動量使用沒有明確的理論動機。其次，Adam 包括偏置修正，修正從原點初始化的一階矩（動量項）和（非中心的）二階矩的估計（演算法8.7）。RMSProp 也採用了（非中心的）二階矩估計，然而缺失了修正因子。因此，不像 Adam，RMSProp 二階矩估計可能在訓練初期有很高的偏置。Adam 通常被認為對超參數的選擇相當魯棒，盡管學習率有時需要從建議的默認修改。

  目前，最流行並且使用很高的優化演算法包括 SGD、具動量的 SGD、RMSProp、具動量的 RMSProp、AdaDelta 和 Adam。