從淺層模型到深度模型：概覽機器學習優化算法
論文鏈接：https://arxiv.org/abs/1706.10207
摘要：本篇論文旨在介紹關于將最優化方法應用于機器學習的關鍵模型、算法、以及一些開放性問題。這篇論文是寫給有一定知識儲備的讀者，尤其是那些熟悉基礎優化算法但是不了解機器學習的讀者。首先，我們推導出一個監督學習問題的公式，并說明它是如何基于上下文和基本假設產生各種優化問題。然后，我們討論這些優化問題的一些顯著特征，重點討論 logistic 回歸和深層神經網絡訓練的案例。本文的后半部分重點介紹幾種優化算法，首先是凸 logistic 回歸，然后討論一階方法，包括了隨機梯度法（SGD）、方差縮減隨機方法（variance reducing stochastic method）和二階方法的使用。最后，我們將討論如何將這些方法應用于深層神經網絡的訓練，并著重描述這些模型的復雜非凸結構所帶來的困難。
1 引言
在過去二十年里，機器學習這一迷人的算法領域幾乎以史無前例的速度崛起。機器學習以統計學和計算機科學為基礎，以數學優化方法為核心。事實上，近來優化方法研究領域中的許多最新理論和實際進展都受到了機器學習和其它數據驅動的學科的影響。然而即使有這些聯系，統計學、計算機科學和致力于機器學習相關問題的優化方法研究之間仍存在許多障礙。因此本文試圖概述機器學習學習算法而打破這種障礙。
本篇論文的目的是給出與機器學習領域相關的一些關鍵問題和研究問題的概述。考慮到涉及運籌學領域的知識，我們假設讀者熟悉基本的優化方法理論，但是仍將引入在廣義機器學習領域使用的相關術語和概念，希望借此促進運籌學專家和其它貢獻領域的人員之間的溝通。為了實現這一目的，我們在詞匯表 1 中列出了本論文將介紹和使用的最重要的術語。
1.1 闡明動機
1.2 學習問題和優化問題
1.3 學習邊界、過擬合和正則化
2 解決Logistic回歸問題的優化方法（淺層模型的優化方法）
當 L 和 r 是關于 w 的任意凸函數時，可以運用在本節中討論的方法來解決問題（11）：
這一類中包含很多機器學習模型，包括支持向量機、Lasso（Least Absolute Shrinkage and Selection Operator）、稀疏逆協方差選擇等。有關這些模型的詳細信息請參見 [86] 和其中的參考文獻。為了每一步都能具體（展現出來），此處我們指定以二分類的正則化logistic回歸為例（進行講解）。為了簡化例子中的符號，我們作不失一般性的假設，令
。（此處省去了偏置項 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 范數正則化的logistic回歸問題的梯度下降和加速梯度下降拓展算法分別被稱作 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（inner 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 |大小與置信域半徑的關系。需要注意的是，對于采樣的海塞矩陣，其對樣本集的大小要求比采樣的梯度要高得多，因此支持使用精確梯度的海塞估計的思想催生了強大的算法，它擁有強大理論支撐和良好的實踐高效性。
