導言

對于幾乎所有機器學習算法，無論是有監督學習、無監督學習，還是強化學習，最后一般都歸結為求解最優化問題。因此，最優化方法在機器學習算法的推導與實現中占據中心地位。在這篇文章中，小編將對機器學習中所使用的優化算法做一個全面的總結，并理清它們直接的脈絡關系，幫你從全局的高度來理解這一部分知識。 ?

機器學習要求解的數學模型

幾乎所有的機器學習算法最后都歸結為求一個目標函數的極值，即最優化問題，例如對于有監督學習，我們要找到一個最佳的映射函數f (x)，使得對訓練樣本的損失函數最小化（最小化經驗風險或結構風險）：

在這里，N為訓練樣本數，L是對單個樣本的損失函數，w是要求解的模型參數，是映射函數的參數，xi為樣本的特征向量，yi為樣本的標簽值。 或是找到一個最優的概率密度函數p(x)，使得對訓練樣本的對數似然函數極大化（最大似然估計）：

在這里，θ是要求解的模型參數，是概率密度函數的參數。 對于無監督學習，以聚類算法為例，算法要是的每個類的樣本離類中心的距離之和最小化：

在這里k為類型數，x為樣本向量，μi為類中心向量，Si為第i個類的樣本集合。 對于強化學習，我們要找到一個最優的策略，即狀態s到動作a的映射函數（確定性策略，對于非確定性策略，是執行每個動作的概率）：

使得任意給定一個狀態，執行這個策略函數所確定的動作a之后，得到的累計回報最大化：

這里使用的是狀態價值函數。 總體來看，機器學習的核心目標是給出一個模型（一般是映射函數），然后定義對這個模型好壞的評價函數（目標函數），求解目標函數的極大值或者極小值，以確定模型的參數，從而得到我們想要的模型。在這三個關鍵步驟中，前兩個是機器學習要研究的問題，建立數學模型。第三個問題是純數學問題，即最優化方法，為本文所講述的核心。 ?

最優化算法的分類

對于形式和特點各異的機器學習算法優化目標函數，我們找到了適合它們的各種求解算法。除了極少數問題可以用暴力搜索來得到最優解之外，我們將機器學習中使用的優化算法分成兩種類型（本文不考慮隨機優化算法如模擬退火、遺傳算法等）：

公式求解??

數值優化

前者給出一個最優化問題精確的公式解，也稱為解析解，一般是理論結果。后者是在要給出極值點的精確計算公式非常困難的情況下，用數值計算方法近似求解得到最優點。除此之外，還有其他一些求解思想，如分治法，動態規劃等。我們在后面單獨列出。一個好的優化算法需要滿足：

能正確的找到各種情況下的極值點

速度快

下圖給出了這些算法的分類與它們之間的關系：

接下來我們將按照這張圖來展開進行講解。 ?

費馬定理

對于一個可導函數，尋找其極值的統一做法是尋找導數為0的點，即費馬定理。微積分中的這一定理指出，對于可導函數，在極值點處導數必定為0：

對于多元函數，則是梯度為0：

導數為0的點稱為駐點。需要注意的是，導數為0只是函數取得極值的必要條件而不是充分條件，它只是疑似極值點。是不是極值，是極大值還是極小值，還需要看更高階導數。對于一元函數，假設x是駐點：

如果f''(x)>0，則在該點處去極小值

如果f''(x)<0，則在該點處去極大值

如果f''(x)>=0，還要看更高階導數

對于多元函數，假設x是駐點：

如果Hessian矩陣正定，函數在該點有極小值

如果Hessian矩陣負定，函數在該點有極大值

如果Hessian矩陣不定，還需要看更（此處誤）

在導數為0的點處，函數可能不取極值，這稱為鞍點，下圖是鞍點的一個例子（來自SIGAI云端實驗室）：

除鞍點外，最優化算法可能還會遇到另外一個問題：局部極值問題，即一個駐點是極值點，但不是全局極值。如果我們對最優化問題加以限定，可以有效的避免這兩種問題。典型的是凸優化，它要求優化變量的可行域是凸集，目標函數是凸函數。 雖然駐點只是函數取得極值的必要條件而不是充分條件，但如果我們找到了駐點，再判斷和篩選它們是不是極值點，比之前要容易多了。無論是理論結果，還是數值優化算法，一般都以找駐點作為找極值點的目標。對于一元函數，先求導數，然后解導數為0的方程即可找到所有駐點。對于多元函數，對各個自變量求偏導數，令它們為0，解方程組，即可達到所有駐點。這都是微積分中所講授的基礎方法。幸運的是，在機器學習中，很多目標函數都是可導的，因此我們可以使用這套方法。 ?

拉格朗日乘數法

費馬定理給出的不帶約束條件下的函數極值的必要條件。對于一些實際應用問題，一般還帶有等式或者不等式約束條件。對于帶等式約束的極值問題，經典的解決方案是拉格朗日乘數法。 對于如下問題：

構造拉格朗日乘子函數：

在最優點處對x和乘子變量λi的導數都必須為0：

解這個方程即可得到最優解。對拉格朗日乘數法更詳細的講解可以閱讀任何一本高等數學教材。機器學習中用到拉格朗日乘數法的地方有：

主成分分析

線性判別分析

流形學習中的拉普拉斯特征映射

隱馬爾可夫模型

KKT條件

KKT條件是拉格朗日乘數法的推廣，用于求解既帶有等式約束，又帶有不等式約束的函數極值。對于如下優化問題：

和拉格朗日對偶的做法類似，KKT條件構如下乘子函數：

λ和μ稱為KKT乘子。在最優解處x*應該滿足如下條件：

等式約束hj (x*)=0和不等式約束gk (x*)<=0是本身應該滿足的約束，▽xL(x*)=0和之前的拉格朗日乘數法一樣。唯一多了關于gi (x)的條件：

KKT條件只是取得極值的必要條件而不是充分條件。在機器學習中用到KKT條件的地方有：

支持向量機（SVM）

數值優化算法

前面講述的三種方法在理論推導、某些可以得到方程組的求根公式的情況（如線性函數，正態分布的最大似然估計）中可以使用，但對絕大多數函數來說，梯度等于0的方程組是沒法直接解出來的，如方程里面含有指數函數、對數函數之類的超越函數。對于這種無法直接求解的方程組，我們只能采用近似的算法來求解，即數值優化算法。這些數值優化算法一般都利用了目標函數的導數信息，如一階導數和二階導數。如果采用一階導數，則稱為一階優化算法。如果使用了二階導數，則稱為二階優化算法。 工程上實現時通常采用的是迭代法，它從一個初始點x0開始，反復使用某種規則從xk移動到下一個點xk+1，構造這樣一個數列，直到收斂到梯度為0的點處。即有下面的極限成立：

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

? 梯度下降法

梯度下降法沿著梯度的反方向進行搜索，利用了函數的一階導數信息。梯度下降法的迭代公式為：

根據函數的一階泰勒展開，在負梯度方向，函數值是下降的。只要學習率設置的足夠小，并且沒有到達梯度為0的點處，每次迭代時函數值一定會下降。需要設置學習率為一個非常小的正數的原因是要保證迭代之后的xk+1位于迭代之前的值xk的鄰域內，從而可以忽略泰勒展開中的高次項，保證迭代時函數值下降。 梯度下降法及其變種在機器學習中應用廣泛，尤其是在深度學習中。（可以擴展閱讀：一文概覽神經網絡優化算法） ? 動量項

為了加快梯度下降法的收斂速度，減少震蕩，引入了動量項。動量項累積了之前迭代時的梯度值，加上此項之后的參數更新公式為：

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

它是上一時刻的動量項與本次梯度值的加權平均值，其中α是學習率，μ是動量項系數。如果按照時間t進行展開，則第t次迭代時使用了從1到t次迭代時的所有梯度值，且老的梯度值安μt的系數指數級衰減：

動量項累積了之前迭代時的梯度值，使得本次迭代時沿著之前的慣性方向向前走。 ? AdaGrad算法

AdaGrad算法是梯度下降法最直接的改進。梯度下降法依賴于人工設定的學習率，如果設置過小，收斂太慢，而如果設置太大，可能導致算法那不收斂，為這個學習率設置一個合適的值非常困難。 AdaGrad算法根據前幾輪迭代時的歷史梯度值動態調整學習率，且優化變量向量X的每一個分量xi都有自己的學習率。參數更新公式為：

其中α是學習因子，gt是第t次迭代時參數的梯度向量，ε是一個很小的正數，為了避免除0操作，下標i表示向量的分量。和標準梯度下降法唯一不同的是多了分母中的這一項，它累積了到本次迭代為止梯度的歷史值信息用于生成梯度下降的系數值。根據上式，歷史導數值的絕對值越大分量學習率越小，反之越大。雖然實現了自適應學習率，但這種算法還是存在問題：需要人工設置一個全局的學習率α，隨著時間的累積，上式中的分母會越來越大，導致學習率趨向于0，參數無法有效更新。 ? RMSProp算法

RMSProp算法是對AdaGrad的改進，避免了長期累積梯度值所導致的學習率趨向于0的問題。具體做法是由梯度值構造一個向量RMS，初始化為0，按照衰減系數累積了歷史的梯度平方值。更新公式為：

AdaGrad直接累加所有歷史梯度的平方和，而這里將歷史梯度平方值按照δt衰減之后再累加。參數更新公式為：

其中δ是人工設定的參數，與AdaGrad一樣，這里也需要人工指定的全局學習率α。 ? AdaDelta算法

AdaDelta算法也是對AdaGrad的改進，避免了長期累積梯度值所導致的學習率趨向于0的問題，另外，還去掉了對人工設置的全局學習率的依賴。假設要優化的參數為x，梯度下降法第t次迭代時計算出來的參數梯度值為gt。算法首先初始化如下兩個向量為0向量：

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

在這里g2是向量每個元素分別計算平方，后面所有的計算公式都是對向量的每個分量進行。接下來計算如下RMS量：

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

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

參數更新的迭代公式為：

? Adam算法

Adam算法整合了自適應學習率與動量項。算法用梯度構造了兩個向量m和v，前者為動量項，后者累積了梯度的平方和，用于構造自適應學習率。它們的初始值為0，更新公式為：

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

在這里，m類似于動量項，用v來構造學習率。? ?

隨機梯度下降法

假設訓練樣本集有N個樣本，有監督學習算法訓練時優化的目標是這個數據集上的平均損失函數：

其中L(w,xi,yi )是對單個訓練樣本(xi,yi )的損失函數，w是需要學習的參數，r(w)是正則化項，λ是正則化項的權重。在訓練樣本數很大時，如果訓練時每次迭代都用所有樣本，計算成本太高，作為改進可以在每次迭代時選取一批樣本，將損失函數定義在這些樣本上。 批量隨機梯度下降法在每次迭代中使用上面目標函數的隨機逼近值，即只使用M《N個隨機選擇的樣本來近似計算損失函數。在每次迭代時要優化的目標函數變為：

隨機梯度下降法在概率意義下收斂。 ? 牛頓法

牛頓法是二階優化技術，利用了函數的一階和二階導數信息，直接尋找梯度為0的點。牛頓法的迭代公式為：

其中H為Hessian矩陣，g為梯度向量。牛頓法不能保證每次迭代時函數值下降，也不能保證收斂到極小值點。在實現時，也需要設置學習率，原因和梯度下降法相同，是為了能夠忽略泰勒展開中的高階項。學習率的設置通常采用直線搜索（line search）技術。 在實現時，一般不直接求Hessian矩陣的逆矩陣，而是求解下面的線性方程組：

其解d稱為牛頓方向。迭代終止的判定依據是梯度值充分接近于0，或者達到最大指定迭代次數。 牛頓法比梯度下降法有更快的收斂速度，但每次迭代時需要計算Hessian矩陣，并求解一個線性方程組，運算量大。另外，如果Hessian矩陣不可逆，則這種方法失效。 牛頓法在logistic回歸，AdaBoost算法等機器學習算法中有實際應用。

? 擬牛頓法

牛頓法在每次迭代時需要計算出Hessian矩陣，并且求解一個以該矩陣為系數矩陣的線性方程組，Hessian矩陣可能不可逆。為此提出了一些改進的方法，典型的代表是擬牛頓法。擬牛頓法的思路是不計算目標函數的Hessian矩陣然后求逆矩陣，而是通過其他手段得到一個近似Hessian矩陣逆的矩陣。具體做法是構造一個近似Hessian矩陣或其逆矩陣的正定對稱矩陣，用該矩陣進行牛頓法的迭代。 所有這些主要的數值優化算法都可以在SIGAI云端實驗室上免費完成實驗： www.sigai.cn 通過構造目標函數，指定優化算法的參數與初始化迭代值，可以可視化的顯示出算法的運行過程，并對不同參數時的求解結果進行比較。

? 可信域牛頓法

標準牛頓法可能不會收斂到一個最優解，也不能保證函數值會按照迭代序列遞減。解決這個問題可以通過調整牛頓方向的步長來實現，目前常用的方法有兩種：直線搜索和可信區域法。可信域牛頓法是截斷牛頓法的一個變種，用于求解帶界限約束的最優化問題。在可信域牛頓法的每一步迭代中，有一個迭代序列xk，一個可信域的大小Δk，以及一個二次目標函數：

這個式子可以通過泰勒展開得到，忽略二次以上的項，這是對函數下降值：

的近似。算法尋找一個sk，在滿足約束條件||S||<=Δk下近似最小化qk(S)。接下來檢查如下比值以更新wk和Δk：

這是函數值的實際減少量和二次近似模型預測方向導致的函數減少量的比值。根據之前的計算結果，再動態調整可信域的大小。 可信域牛頓法在logistic回歸，線性支持向量的求解時有實際的應用，具體可以閱讀liblinear開源庫。 ? 分治法

分治法是一種算法設計思想，它將一個大的問題分解成子問題進行求解。根據子問題解構造出整個問題的解。在最優化方法中，具體做法是每次迭代時只調整優化向量的一部分分量，其他的分量固定住不動。 ? 坐標下降法

坐標下降法的基本思想是每次對一個變量進行優化，這是一種分治法。假設要求解的優化問題為;

坐標下降法求解流程為每次選擇一個分量xi進行優化，將其他分量固定住不動，這樣將一個多元函數的極值問題轉換為一元函數的極值問題。如果要求解的問題規模很大，這種做法能有效的加快速度。 坐標下降法在logistic回歸，線性支持向量的求解時有實際的應用，具體可以閱讀liblinear開源庫。 ? SMO算法

SMO算法也是一種分治法，用于求解支持向量機的對偶問題。加上松弛變量和核函數后的對偶問題為：

SMO算法的核心思想是每次在優化變量中挑出兩個分量αi 和?αj進行優化，讓其他分量固定，這樣能保證滿足等式約束條件。之所以要選擇兩個變量進行優化而不是選擇一個變量，是因為這里有等式約束，如果只調整一個變量的值，將會破壞等式約束。 假設選取的兩個分量為αi 和?αj，其他分量都固定即當成常數。對這兩個變量的目標函數是一個二元二次函數。這個問題還帶有等式和不等式約束條件。對這個子問題可以直接求得公式解，就是某一區間內的一元二次函數的極值。 ? 分階段優化

分階段優化的做法是在每次迭代時，先固定住優化變量X一部分分量a不動，對另外一部分變量b進行優化；然后再固定住b不動，對b進行優化。如此反復，直至收斂到最優解處。 AdaBoost算法是這種方法的典型代表。AdaBoost算法在訓練時采用了指數損失函數：

由于強分類器是多個弱分類器的加權和，代入上面的損失函數中，得到算法訓練時要優化的目標函數為：

這里將指數損傷函數拆成了兩部分，已有的強分類器Fj?1，以及當前弱分類器f對訓練樣本的損失函數，前者在之前的迭代中已經求出，因此可以看成常數。這樣目標函數可以簡化為：

其中：

這個問題可以分兩步求解，首先將弱分類器權重β看成常數，得到最優的弱分類器f。得到弱分類器之后，再優化它的權重系數β。 ? 動態規劃算法

動態規劃也是一種求解思想，它將一個問題分解成子問題求解，如果整個問題的某個解是最優的，則這個解的任意一部分也是子問題的最優解。這樣通過求解子問題，得到最優解，逐步擴展，最后得到整個問題的最優解。 隱馬爾可夫模型的解碼算法（維特比算法），強化學習中的動態規劃算法是這類方法的典型代表，此類算法一般是離散變量的優化，而且是組合優化問題。前面講述的基于導數的優化算法都無法使用。動態規劃算法能高效的求解此類問題，其基礎是貝爾曼最優化原理。一旦寫成了遞歸形式的最優化方程，就可以構造算法進行求解。

編輯：黃飛

?