從淺層模型到深度模型，你了解機器學習的學習演算法嗎？

選自arxiv

機器之心編譯

參與：乾樹、蔣思源

學習演算法一直以來是機器學習能根據數據學到知識的核心技術。而好的優化演算法可以大大提高學習速度，加快演算法的收斂速度和效果。該論文從淺層模型到深度模型縱覽監督學習中常用的優化演算法，並指出了每一種優化演算法的優點及局限性，同時其還包括了一階和二階等各種演算法的形式化表達。機器之心主要對本論文選擇性地編譯了優化演算法的部分，更詳細的推導及介紹請查看原論文。

論文鏈接：https://arxiv.org/abs/1706.10207

摘要：本篇論文旨在介紹關於將最優化方法應用於機器學習的關鍵模型、演算法、以及一些開放性問題。這篇論文是寫給有一定知識儲備的讀者，尤其是那些熟悉基礎優化演算法但是不了解機器學習的讀者。首先，我們推導出一個監督學習問題的公式，並說明它是如何基於上下文和基本假設產生各種優化問題。然後，我們討論這些優化問題的一些顯著特徵，重點討論 logistic 回歸和深層神經網路訓練的案例。本文的後半部分重點介紹幾種優化演算法，首先是凸 logistic 回歸，然後討論一階方法，包括了隨機梯度法（SGD）、方差縮減隨機方法（variance reducing stochastic method）和二階方法的使用。最後，我們將討論如何將這些方法應用於深層神經網路的訓練，並著重描述這些模型的複雜非凸結構所帶來的困難。

1 引言

在過去二十年里，機器學習這一迷人的演算法領域幾乎以史無前例的速度崛起。機器學習以統計學和計算機科學為基礎，以數學優化方法為核心。事實上，近來優化方法研究領域中的許多最新理論和實際進展都受到了機器學習和其它數據驅動的學科的影響。然而即使有這些聯繫，統計學、計算機科學和致力於機器學習相關問題的優化方法研究之間仍存在許多障礙。因此本文試圖概述機器學習學習演算法而打破這種障礙。

本篇論文的目的是給出與機器學習領域相關的一些關鍵問題和研究問題的概述。考慮到涉及運籌學領域的知識，我們假設讀者熟悉基本的優化方法理論，但是仍將引入在廣義機器學習領域使用的相關術語和概念，希望藉此促進運籌學專家和其它貢獻領域的人員之間的溝通。為了實現這一目的，我們在辭彙表 1 中列出了本論文將介紹和使用的最重要的術語。

表 1 ： 監督機器學習的術語表（監督機器學習的目的之一就是理解輸入空間 X 中每個輸入向量 x 和輸出空間 Y 中相應輸出向量 y 之間的關係）

1.1 闡明動機

1.2 學習問題和優化問題

1.3 學習邊界、過擬合和正則化

2 解決邏輯回歸問題的優化方法（淺層模型的優化方法）

當 L 和 r 是關於 w 的任意凸函數時，可以運用在本節中討論的方法來解決問題（11）：

這一類中包含很多機器學習模型，包括支持向量機、Lasso（Least Absolute Shrinkage and Selection Operator）、稀疏逆協方差選擇等。有關這些模型的詳細信息請參見 [86] 和其中的參考文獻。為了每一步都能具體（展現出來），此處我們指定以二分類的正則化邏輯回歸為例（進行講解）。為了簡化例子中的符號，我們作不失一般性的假設，令

。（此處省去了偏置項 b0），這一省略操作可以通過在輸入向量上增加一維恆為 1 的特徵值來彌補）。當 w 和 x 都是 d 維時就可以令其為特定的凸優化問題。

值得一提的是，對於此類問題，正則化項必不可少。想一想為什麼說它必不可少，假設對於所有的 i ∈{1,...,n}，有參數向量 w，滿足 yi(wT*xi) > 0 以及（存在）無界射線 {θw : θ > 0}。那問題就很明朗了，在這個例子中，當 θ →∞時，

也就是說函數（式 12）無法取最小值。另一方面，通過增加（強制）正則化函數 r，可以保證問題（12）將具有最優解。

對於正則化函數 r，我們將會參考常用選擇

和 r(w) = ||w||1。不過為了簡單起見，我們通常會選擇前者，因為它使得公式 12 對於每一個因子是連續可微的。相反，r(w) = ||w||1 會導致非平滑問題，為此，（實現）函數最小化就需要更複雜的演算法。

2.1 一階方法

我們首先討論用一階方法求解問題（12），這裡的」一階」僅僅指對函數 F 中的參數進行一階偏導的數學技巧。

2.1.1 梯度下降法

從概念上講，最小化光滑凸目標的最簡單的方法是梯度下降法，具體分析參見 [ 62 ]。在這種方法中，從初始化估計值 w0 開始，通過下述公式迭代地更新權重估計值。

其中 αk > 0 是一個步長參數。步長序列 {αk} 的選擇直接決定此演算法的性能。在優化研究領域，人們普遍認為，在每次迭代中採用線性搜索來確定 {αk }，可以為解決各種類型的問題找到一個性能優越的演算法。然而，對於機器學習應用程序來說，這種運算成本高昂，因為每次函數 F 的計算都需要傳遞整個數據集，如果 n 過大，很可能帶來高昂的（訓練）成本。

好在當每個αk 都設置為一個正的常數α且它是一個足夠小的固定值時，從理論上分析，該演算法的收斂性仍可以得到保證。（固定的步長常數在機器學習領域叫做學習率。但即使不是常數，也有人把αK 或整個序列 {αK } 叫做學習率）。該演算法的收斂速度取決於函數 f 是強凸函數還是弱凸函數。

用於解決 L1 範數正則化的邏輯回歸問題的梯度下降和加速梯度下降拓展演算法分別被稱作 ISTA 和 FISTA。我們觀察到，在這種情況下，即使λ> 0，目標函數也不會是強凸函數。只有目標函數為凸時 [5]，ISTA 和 FISTA 具有與其對應的平滑函數相同的次線性收斂速度。

梯度下降在 ML 訓練過程中的一個重要特性就是計算出每次迭代中求解函數 F 的梯度的運算成本。在 ML 的訓練過程中，單個梯度計算的成本通常是 O（ND），這個確實可以看到，例如，在正則化項為

的情況中，函數 F 關於每一個特定的 w 的梯度是

2.1.2 隨機梯度法

隨機梯度法由於其用於最小化隨機目標函數而在運籌學領域廣為人知，同時也是 ML 社區中的一種特徵優化演算法。該演算法最初由 Robbins 和 Monro [ 67 ] 在解決隨機方程組問題時提出，值得注意的是，它可以用於最小化具有良好收斂性的隨機目標，而且每次迭代的計算複雜度僅為 O（d）而不是 O（nd）（梯度下降中的計算複雜度）。

在每一次迭代中，隨機梯度法都會計算梯度 F（Wk）的無偏估計 GK。該估計可以以及低的代價計算得到；例如，對於公式（12），某次迭代的隨機梯度可被求解為

其中 Sk 被稱作小批量，它的所有元素都是從總數據集 {1,...,n} 中按均勻分布選出來的。接下來的運算類似於梯度下降：

毫無疑問，該演算法的關鍵在於選擇步長序列 {αk}。不同於梯度下降，固定的步長（即學習率）不能保證演算法會收斂到強凸函數 F 的最小值，而只保證收斂到最小值的鄰域。

SGD 的收斂速度比梯度下降慢。尤其當函數 F 是強凸函數時，該演算法只保證當 k ≥ O(1/ε) 時可以得到預期精度的解（即滿足 E[F(wk)]-F(w) ≤ ε的解），而當函數 F 僅僅是凸函數時，只有在 k ≥ O(1/ε^2) [11] 時才能保證得出上述解。

另一方面，正如前文提及的，如果 Sk 的大小由一個常數限定（獨立於 n 或 k 的常數），那麼 SGD 的每次的迭代成本都比梯度下降法小 0（n）倍。

然而，在實際運用中，標準的 SGD 並不一定是解決機器學習中優化問題的最有效方法。事實上，機器學習和優化演算法領域在開發改進或替代 SGD 方面進行了大量的積極研究。在隨後的兩部分中，我們將討論兩類方法：方差縮減法和二階方法。但是在這兩類方法以外，還有多種方法。例如，加有動量的 SGD 就是一個實踐中被發現的性能好於好於標準 SGD 的拓展版 SGD。見下圖演算法 1

2.1.3 方差縮減法（Variance reducing method）

考慮到問題（11），人們發現通過利用目標 F 的結構作為 n 個函數的有限和再加上簡單的凸函數項，可以改善 SGD 方法。目前已經研究出幾種方法，如 SAG [74]，SAGA [22]，SDCA [76] 和 SVRG [44]。

為了方便引用，我們把 SVRG 叫做演算法 2。該演算法在每個外部迭代中執行一次完整的梯度計算，然後沿著隨機方向再迭代 L 步，這是整個梯度的隨機修正過程。內環步長 L（nner loop size）必須滿足一定的條件以保證收斂 [ 44 ]。

SVRG，全稱為隨機方差減小梯度，其名稱源自於該演算法可以被視為 SGD 的方差減小變體（尤其是有限和最小化/finite-sum minimization）。

研究員通過結合 SVRG 和 SAGA 的一些思想，提出一個新的方法，叫做 SARAH。僅是內層迭代步長不同於 SVRG，SARAH 的公式如下

該變化導致

，使得 SARAH 中的步長不基於無偏梯度估計。不過，相對於 SVRG，它獲得了改進的收斂特性。

表 2 ： 最小化強凸函數的一階方法計算複雜度

表 3 ： 最小化一般凸函數的一階方法計算複雜度

2.2 二階方法和擬牛頓法

受確定性優化研究領域幾十年研究成果的激勵，ML 優化中最活躍的研究領域之一就是關於如何使用二階導數（即曲率）信息來加速訓練。

不幸的是，當 n 或 d 很大時，在機器學習應用程序中，海塞矩陣（Hessian matrix）的計算和存儲變得非常昂貴。

另一類基於形如（21）模型的演算法是擬牛頓方法：

有趣的是，這些方法沒有計算出顯式二階導數，而是通過在每次迭代中應用低秩更新構造完全由一階導數的海塞近似矩陣。例如，讓我們簡要介紹最流行的擬牛頓演算法，全稱為 Broyden-Fletcher-Goldfarb-Shanno（BFGS）方法。在這種方法中，我們首先可以看到（21）的最小值為、

進一步發現它實際上可以方便地計算出逆 Hessian 近似。由於

隨著步長 sk = w_k+1 ? wk 和位移 yk = ?F(wk+1) ? ?F(wk) 的移動，有人選擇

以最小化

以滿足割線方程 sk = (B^-1)yk。使用精心挑選的規範表達，這個問題的解析式可以顯示的寫成

其中

之間的差異可以僅表示為二階矩陣。

為方便引用，完整的經典 BFGS 演算法被稱為演算法 3。

即使採用二階信息，隨機優化方法（無差異減少）也無法達到比次線性更快的收斂速度。不過，使用二階信息是一個不錯的想法，因為如果海塞近似矩陣收斂于海塞矩陣的真實解，則可以減少收斂速度中的常數，同時還可以減少病態（ill-conditioning）的影響。

不幸的是，儘管已經觀察到了實際的效率提升，但在理論上還沒有一個真正的二階方法，可以實現這樣的提升。到目前為止，只要海塞（近似）矩陣保持良好特性，大多數實際的方法只能保證實現 SGD 的收斂（速率）特性。例如，如果序列 {Bk}（不一定由 BFGS 更新生成）滿足所有 k，

此時

具有與 SGD 相同的收斂速度屬性。我們就 可以合理地假設這些限定適用於上述討論的方法，這些假設有適當的保障。然而，在擬牛頓方法的背景下應該小心，其中隨機梯度估計可能與海塞近似相關。

3 深度學習

沿著這些方向進行的主要進展包括深層神經網路（DNN）的運用。機器學習的一個相應的分支稱為深度學習（或分層學習），它代表了一類試圖通過使用包含連續線性和非線性變換的多層次深層圖來構造數據中高層次抽象的演算法 [6, 51, 73, 37, 38, 23]。近年來科學家們已經研究了各種神經網路類型，包括全連接神經網路（FNN）[84,28]，卷積神經網路（CNN）[50] 和循環神經網路（RNN）[41,57,52]。對於我們來說，將主要關注前兩類神經網路，同時留意其它網路。

3.1 問題公式化

3.2 隨機梯度下降法

我們引用以下內容來強調將優化演算法應用於訓練 DNN 的令人困惑的反應。首先，例如在 [11] 中，有一個結論表明，通過應用 SGD 來最小化非凸目標函數（一直從輸入×輸出空間繪製），可以保證預期梯度風險將消失，至少在一個子序列上是這樣，即：這一結論令人欣慰，這表明 SGD 可以實現與其他最先進的基於梯度的優化演算法類似的收斂保證。然而，儘管文獻中的種種保證是有局限性的; 畢竟，儘管許多基於梯度的優化演算法確保目標函數單調減少，但 SG 並不以這種方式計算。因此，如果一個子序列收斂到一個固定點，那麼我們怎麼能確定該點不是鞍點，或者是有誤差局部最小值，亦或是一些目標值比初始點差的最大值？事實上，我們並不能肯定。也就是說，SGD 方法通常擅長找到局部極小值，而不是全局最小值。另一方面，SGD 往往會在固定值附近減緩收斂速度，這可能會阻礙它在深度神經網路中發展。

一般來說，對於非凸問題，SGD 的收斂速度記錄在 [29,30]，但是它們非常有限，特別是它們不適用於§1.3 中的討論。因此，我們不能以同樣的方式爭論 SGD 是機器學習中非凸優化問題的最佳方法。此外，下式

中的學習界限是沒有用的，因為對於許多 DNN 和 CNN，由神經網路產生的分類的複雜度 C 比訓練樣本數 n 大得多。事實上，在 [90] 中，經驗表明，只有這些集合中的數據隨機擾動，神經網路才能輕易地超過典型的數據集類型。

3.3 海塞-自由優化方法（Hessian-free method）

有研究者發現我們可以修改 DNN 的反向傳播演算法來計算這樣的海塞-矢量乘積，因為它們可以被看作是方嚮導數 [65]。計算這種乘積的複雜度只是比計算梯度多一個常數因子。所得到的類的方法通常被稱為海塞-自由優化方法，因為當訪問和使用 Hessian 信息時，沒有顯式地存儲 Hessian 矩陣。

由於目標函數的非凸性，在 DNN 的情況中出現了其它的問題，真正的海塞矩陣可能不是正定矩陣。一般來說，在確定性優化中，處理這個問題的兩種可能的方法是修改海森矩陣和運用置信域（trust region）方法。這兩種方法都在訓練 DNN 的情況中探討過，例如，在 [54,55] 中，提出了一種高斯牛頓法，其在（11）中函數 F 的 Hessian 的公式中的第一項近似於 Hessian 矩陣（省略了正則化項）

其中

是關於第一個參數的損失函數 l(·, ·) 的海塞矩陣，?p(w, xi) 是 dy-維函數 p(w, x) 對於權重 w 的雅可比式，?^2 [pj (w, xi)] for all j ∈ {1, . . . , dy} 是關於 w 的按元素運算的海塞矩陣。

3.4 子採樣海森方法（Subsampled Hessian method）

最近，在一系列論文（3, 15, 34）中，研究員們利用一個很一般的隨機模型框架，對凸區域和非凸情形下的置信域、線搜索和自適應三次正則化方法進行了分析。在這項工作中，它表明，只要梯度和 Hessian 估計是足夠準確的一些正概率，使用隨機不精確梯度和 Hessian 信息的標準優化方法就可以保留其收斂速度。

在機器學習和採樣 Hessian 和梯度的情況下，結果只要求| SK |必須選擇足夠大的相對於該演算法採取的步驟的長度。例如，在 [ 3, 34 ]，| SK |大小與置信域半徑的關係。需要注意的是，對於採樣的海塞矩陣，其對樣本集的大小要求比採樣的梯度要高得多，因此支持使用精確梯度的海塞估計的思想催生了強大的演算法，它擁有強大理論支撐和良好的實踐高效性。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！