幾乎所有的機(jī)器學(xué)習(xí)算法最后都?xì)w結(jié)為求一個目標(biāo)函數(shù)的極值，即最優(yōu)化問題，例如對于有監(jiān)督學(xué)習(xí)，我們要找到一個最佳的映射函數(shù)f (x)，使得對訓(xùn)練樣本的損失函數(shù)最小化（最小化經(jīng)驗(yàn)風(fēng)險或結(jié)構(gòu)風(fēng)險）：

在這里，N為訓(xùn)練樣本數(shù)，L是對單個樣本的損失函數(shù)，w是要求解的模型參數(shù)，是映射函數(shù)的參數(shù)，xi為樣本的特征向量，yi為樣本的標(biāo)簽值。

或是找到一個最優(yōu)的概率密度函數(shù)p(x)，使得對訓(xùn)練樣本的對數(shù)似然函數(shù)極大化（最大似然估計(jì)）：

在這里，θ是要求解的模型參數(shù)，是概率密度函數(shù)的參數(shù)。

對于無監(jiān)督學(xué)習(xí)，以聚類算法為例，算法要是的每個類的樣本離類中心的距離之和最小化：

在這里k為類型數(shù)，x為樣本向量，μi為類中心向量，Si為第i個類的樣本集合。

對于強(qiáng)化學(xué)習(xí)，我們要找到一個最優(yōu)的策略，即狀態(tài)s到動作a的映射函數(shù)（確定性策略，對于非確定性策略，是執(zhí)行每個動作的概率）：

使得任意給定一個狀態(tài)，執(zhí)行這個策略函數(shù)所確定的動作a之后，得到的累計(jì)回報最大化：

這里使用的是狀態(tài)價值函數(shù)。

總體來看，機(jī)器學(xué)習(xí)的核心目標(biāo)是給出一個模型（一般是映射函數(shù)），然后定義對這個模型好壞的評價函數(shù)（目標(biāo)函數(shù)），求解目標(biāo)函數(shù)的極大值或者極小值，以確定模型的參數(shù)，從而得到我們想要的模型。在這三個關(guān)鍵步驟中，前兩個是機(jī)器學(xué)習(xí)要研究的問題，建立數(shù)學(xué)模型。第三個問題是純數(shù)學(xué)問題，即最優(yōu)化方法，為本文所講述的核心。

對于形式和特點(diǎn)各異的機(jī)器學(xué)習(xí)算法優(yōu)化目標(biāo)函數(shù)，我們找到了適合它們的各種求解算法。除了極少數(shù)問題可以用暴力搜索來得到最優(yōu)解之外，我們將機(jī)器學(xué)習(xí)中使用的優(yōu)化算法分成兩種類型（不考慮隨機(jī)優(yōu)化算法如模擬退火、遺傳算法等，對于這些算法，我們后面會專門有文章進(jìn)行介紹）：

• 公式解  

• 數(shù)值優(yōu)化

 前者給出一個最優(yōu)化問題精確的公式解，也稱為解析解，一般是理論結(jié)果。后者是在要給出極值點(diǎn)的精確計(jì)算公式非常困難的情況下，用數(shù)值計(jì)算方法近似求解得到最優(yōu)點(diǎn)。除此之外，還有其他一些求解思想，如分治法，動態(tài)規(guī)劃等。我們在后面單獨(dú)列出。一個好的優(yōu)化算法需要滿足：

• 能正確的找到各種情況下的極值點(diǎn)
  

• 速度快

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

接下來我們將按照這張圖來展開進(jìn)行講解。

對于一個可導(dǎo)函數(shù)，尋找其極值的統(tǒng)一做法是尋找導(dǎo)數(shù)為0的點(diǎn)，即費(fèi)馬定理。微積分中的這一定理指出，對于可導(dǎo)函數(shù)，在極值點(diǎn)處導(dǎo)數(shù)必定為0：

對于多元函數(shù)，則是梯度為0：

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

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

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

• 如果f''(x)>=0，還要看更高階導(dǎo)數(shù)

對于多元函數(shù)，假設(shè)x是駐點(diǎn)：

• 如果Hessian矩陣正定，函數(shù)在該點(diǎn)有極小值

• 如果Hessian矩陣負(fù)定，函數(shù)在該點(diǎn)有極大值

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

在導(dǎo)數(shù)為0的點(diǎn)處，函數(shù)可能不取極值，這稱為鞍點(diǎn)，下圖是鞍點(diǎn)的一個例子（來自SIGAI云端實(shí)驗(yàn)室）：

除鞍點(diǎn)外，最優(yōu)化算法可能還會遇到另外一個問題：局部極值問題，即一個駐點(diǎn)是極值點(diǎn)，但不是全局極值。如果我們對最優(yōu)化問題加以限定，可以有效的避免這兩種問題。典型的是凸優(yōu)化，它要求優(yōu)化變量的可行域是凸集，目標(biāo)函數(shù)是凸函數(shù)。

雖然駐點(diǎn)只是函數(shù)取得極值的必要條件而不是充分條件，但如果我們找到了駐點(diǎn)，再判斷和篩選它們是不是極值點(diǎn)，比之前要容易多了。無論是理論結(jié)果，還是數(shù)值優(yōu)化算法，一般都以找駐點(diǎn)作為找極值點(diǎn)的目標(biāo)。對于一元函數(shù)，先求導(dǎo)數(shù)，然后解導(dǎo)數(shù)為0的方程即可找到所有駐點(diǎn)。對于多元函數(shù)，對各個自變量求偏導(dǎo)數(shù)，令它們?yōu)?，解方程組，即可達(dá)到所有駐點(diǎn)。這都是微積分中所講授的基礎(chǔ)方法。幸運(yùn)的是，在機(jī)器學(xué)習(xí)中，很多目標(biāo)函數(shù)都是可導(dǎo)的，因此我們可以使用這套方法。

費(fèi)馬定理給出的不帶約束條件下的函數(shù)極值的必要條件。對于一些實(shí)際應(yīng)用問題，一般還帶有等式或者不等式約束條件。對于帶等式約束的極值問題，經(jīng)典的解決方案是拉格朗日乘數(shù)法。

對于如下問題：

構(gòu)造拉格朗日乘子函數(shù)：

在最優(yōu)點(diǎn)處對x和乘子變量λi的導(dǎo)數(shù)都必須為0：

解這個方程即可得到最優(yōu)解。對拉格朗日乘數(shù)法更詳細(xì)的講解可以閱讀任何一本高等數(shù)學(xué)教材。機(jī)器學(xué)習(xí)中用到拉格朗日乘數(shù)法的地方有：

• 主成分分析

• 線性判別分析

• 流形學(xué)習(xí)中的拉普拉斯特征映射

• 隱馬爾可夫模型

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

和拉格朗日對偶的做法類似，KKT條件構(gòu)如下乘子函數(shù)：

λ和μ稱為KKT乘子。在最優(yōu)解處x*應(yīng)該滿足如下條件：

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

KKT條件只是取得極值的必要條件而不是充分條件。在機(jī)器學(xué)習(xí)中用到KKT條件的地方有：

• 支持向量機(jī)（SVM）

前面講述的三種方法在理論推導(dǎo)、某些可以得到方程組的求根公式的情況（如線性函數(shù)，正態(tài)分布的最大似然估計(jì)）中可以使用，但對絕大多數(shù)函數(shù)來說，梯度等于0的方程組是沒法直接解出來的，如方程里面含有指數(shù)函數(shù)、對數(shù)函數(shù)之類的超越函數(shù)。對于這種無法直接求解的方程組，我們只能采用近似的算法來求解，即數(shù)值優(yōu)化算法。這些數(shù)值優(yōu)化算法一般都利用了目標(biāo)函數(shù)的導(dǎo)數(shù)信息，如一階導(dǎo)數(shù)和二階導(dǎo)數(shù)。如果采用一階導(dǎo)數(shù)，則稱為一階優(yōu)化算法。如果使用了二階導(dǎo)數(shù)，則稱為二階優(yōu)化算法。

工程上實(shí)現(xiàn)時通常采用的是迭代法，它從一個初始點(diǎn)x0開始，反復(fù)使用某種規(guī)則從xk移動到下一個點(diǎn)xk+1，構(gòu)造這樣一個數(shù)列，直到收斂到梯度為0的點(diǎn)處。即有下面的極限成立：

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

梯度下降法沿著梯度的反方向進(jìn)行搜索，利用了函數(shù)的一階導(dǎo)數(shù)信息。梯度下降法的迭代公式為：

根據(jù)函數(shù)的一階泰勒展開，在負(fù)梯度方向，函數(shù)值是下降的。只要學(xué)習(xí)率設(shè)置的足夠小，并且沒有到達(dá)梯度為0的點(diǎn)處，每次迭代時函數(shù)值一定會下降。需要設(shè)置學(xué)習(xí)率為一個非常小的正數(shù)的原因是要保證迭代之后的xk+1位于迭代之前的值xk的鄰域內(nèi)，從而可以忽略泰勒展開中的高次項(xiàng)，保證迭代時函數(shù)值下降。

梯度下降法及其變種在機(jī)器學(xué)習(xí)中應(yīng)用廣泛，尤其是在深度學(xué)習(xí)中。

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

其中Vt+1是動量項(xiàng)，它取代了之前的梯度項(xiàng)。動量項(xiàng)的計(jì)算公式為：

它是上一時刻的動量項(xiàng)與本次梯度值的加權(quán)平均值，其中α是學(xué)習(xí)率，μ是動量項(xiàng)系數(shù)。如果按照時間t進(jìn)行展開，則第t次迭代時使用了從1到t次迭代時的所有梯度值，且老的梯度值安μt的系數(shù)指數(shù)級衰減：

動量項(xiàng)累積了之前迭代時的梯度值，使得本次迭代時沿著之前的慣性方向向前走。

AdaGrad算法是梯度下降法最直接的改進(jìn)。梯度下降法依賴于人工設(shè)定的學(xué)習(xí)率，如果設(shè)置過小，收斂太慢，而如果設(shè)置太大，可能導(dǎo)致算法那不收斂，為這個學(xué)習(xí)率設(shè)置一個合適的值非常困難。

AdaGrad算法根據(jù)前幾輪迭代時的歷史梯度值動態(tài)調(diào)整學(xué)習(xí)率，且優(yōu)化變量向量X的每一個分量xi都有自己的學(xué)習(xí)率。參數(shù)更新公式為：

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

RMSProp算法是對AdaGrad的改進(jìn)，避免了長期累積梯度值所導(dǎo)致的學(xué)習(xí)率趨向于0的問題。具體做法是由梯度值構(gòu)造一個向量RMS，初始化為0，按照衰減系數(shù)累積了歷史的梯度平方值。更新公式為：

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

其中δ是人工設(shè)定的參數(shù)，與AdaGrad一樣，這里也需要人工指定的全局學(xué)習(xí)率α。

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

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

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

這也是一個向量，計(jì)算時分別對向量的每個分量進(jìn)行。然后計(jì)算參數(shù)的更新值：

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

參數(shù)更新的迭代公式為：

Adam算法整合了自適應(yīng)學(xué)習(xí)率與動量項(xiàng)。算法用梯度構(gòu)造了兩個向量m和v，前者為動量項(xiàng)，后者累積了梯度的平方和，用于構(gòu)造自適應(yīng)學(xué)習(xí)率。它們的初始值為0，更新公式為：

其中β1,β2是人工指定的參數(shù)，i為向量的分量下標(biāo)。依靠這兩個值構(gòu)造參數(shù)的更新值，參數(shù)的更新公式為：

在這里，m類似于動量項(xiàng)，用v來構(gòu)造學(xué)習(xí)率。

假設(shè)訓(xùn)練樣本集有N個樣本，有監(jiān)督學(xué)習(xí)算法訓(xùn)練時優(yōu)化的目標(biāo)是這個數(shù)據(jù)集上的平均損失函數(shù)：

其中L(w,xi,yi )是對單個訓(xùn)練樣本(xi,yi )的損失函數(shù)，w是需要學(xué)習(xí)的參數(shù)，r(w)是正則化項(xiàng)，λ是正則化項(xiàng)的權(quán)重。在訓(xùn)練樣本數(shù)很大時，如果訓(xùn)練時每次迭代都用所有樣本，計(jì)算成本太高，作為改進(jìn)可以在每次迭代時選取一批樣本，將損失函數(shù)定義在這些樣本上。

批量隨機(jī)梯度下降法在每次迭代中使用上面目標(biāo)函數(shù)的隨機(jī)逼近值，即只使用M《N個隨機(jī)選擇的樣本來近似計(jì)算損失函數(shù)。在每次迭代時要優(yōu)化的目標(biāo)函數(shù)變?yōu)椋?/p>

隨機(jī)梯度下降法在概率意義下收斂。

牛頓法是二階優(yōu)化技術(shù)，利用了函數(shù)的一階和二階導(dǎo)數(shù)信息，直接尋找梯度為0的點(diǎn)。牛頓法的迭代公式為：

其中H為Hessian矩陣，g為梯度向量。牛頓法不能保證每次迭代時函數(shù)值下降，也不能保證收斂到極小值點(diǎn)。在實(shí)現(xiàn)時，也需要設(shè)置學(xué)習(xí)率，原因和梯度下降法相同，是為了能夠忽略泰勒展開中的高階項(xiàng)。學(xué)習(xí)率的設(shè)置通常采用直線搜索（line search）技術(shù)。

在實(shí)現(xiàn)時，一般不直接求Hessian矩陣的逆矩陣，而是求解下面的線性方程組：

其解d稱為牛頓方向。迭代終止的判定依據(jù)是梯度值充分接近于0，或者達(dá)到最大指定迭代次數(shù)。

牛頓法比梯度下降法有更快的收斂速度，但每次迭代時需要計(jì)算Hessian矩陣，并求解一個線性方程組，運(yùn)算量大。另外，如果Hessian矩陣不可逆，則這種方法失效。

牛頓法在logistic回歸，AdaBoost算法等機(jī)器學(xué)習(xí)算法中有實(shí)際應(yīng)用。

牛頓法在每次迭代時需要計(jì)算出Hessian矩陣，并且求解一個以該矩陣為系數(shù)矩陣的線性方程組，Hessian矩陣可能不可逆。為此提出了一些改進(jìn)的方法，典型的代表是擬牛頓法。擬牛頓法的思路是不計(jì)算目標(biāo)函數(shù)的Hessian矩陣然后求逆矩陣，而是通過其他手段得到一個近似Hessian矩陣逆的矩陣。具體做法是構(gòu)造一個近似Hessian矩陣或其逆矩陣的正定對稱矩陣，用該矩陣進(jìn)行牛頓法的迭代。

所有這些主要的數(shù)值優(yōu)化算法都可以在SIGAI云端實(shí)驗(yàn)室上免費(fèi)完成實(shí)驗(yàn)：

www.sigai.cn

通過構(gòu)造目標(biāo)函數(shù)，指定優(yōu)化算法的參數(shù)與初始化迭代值，可以可視化的顯示出算法的運(yùn)行過程，并對不同參數(shù)時的求解結(jié)果進(jìn)行比較。

標(biāo)準(zhǔn)牛頓法可能不會收斂到一個最優(yōu)解，也不能保證函數(shù)值會按照迭代序列遞減。解決這個問題可以通過調(diào)整牛頓方向的步長來實(shí)現(xiàn)，目前常用的方法有兩種：直線搜索和可信區(qū)域法。可信域牛頓法是截?cái)嗯ｎD法的一個變種，用于求解帶界限約束的最優(yōu)化問題。在可信域牛頓法的每一步迭代中，有一個迭代序列xk，一個可信域的大小Δk，以及一個二次目標(biāo)函數(shù)：

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

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

這是函數(shù)值的實(shí)際減少量和二次近似模型預(yù)測方向?qū)е碌暮瘮?shù)減少量的比值。根據(jù)之前的計(jì)算結(jié)果，再動態(tài)調(diào)整可信域的大小。

可信域牛頓法在logistic回歸，線性支持向量的求解時有實(shí)際的應(yīng)用，具體可以閱讀liblinear開源庫。

分治法是一種算法設(shè)計(jì)思想，它將一個大的問題分解成子問題進(jìn)行求解。根據(jù)子問題解構(gòu)造出整個問題的解。在最優(yōu)化方法中，具體做法是每次迭代時只調(diào)整優(yōu)化向量的一部分分量，其他的分量固定住不動。

坐標(biāo)下降法的基本思想是每次對一個變量進(jìn)行優(yōu)化，這是一種分治法。假設(shè)要求解的優(yōu)化問題為;

坐標(biāo)下降法求解流程為每次選擇一個分量xi進(jìn)行優(yōu)化，將其他分量固定住不動，這樣將一個多元函數(shù)的極值問題轉(zhuǎn)換為一元函數(shù)的極值問題。如果要求解的問題規(guī)模很大，這種做法能有效的加快速度。

坐標(biāo)下降法在logistic回歸，線性支持向量的求解時有實(shí)際的應(yīng)用，具體可以閱讀liblinear開源庫。

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

SMO算法的核心思想是每次在優(yōu)化變量中挑出兩個分量αi 和 αj進(jìn)行優(yōu)化，讓其他分量固定，這樣能保證滿足等式約束條件。之所以要選擇兩個變量進(jìn)行優(yōu)化而不是選擇一個變量，是因?yàn)檫@里有等式約束，如果只調(diào)整一個變量的值，將會破壞等式約束。

假設(shè)選取的兩個分量為αi 和 αj，其他分量都固定即當(dāng)成常數(shù)。對這兩個變量的目標(biāo)函數(shù)是一個二元二次函數(shù)。這個問題還帶有等式和不等式約束條件。對這個子問題可以直接求得公式解，就是某一區(qū)間內(nèi)的一元二次函數(shù)的極值。

分階段優(yōu)化的做法是在每次迭代時，先固定住優(yōu)化變量X一部分分量a不動，對另外一部分變量b進(jìn)行優(yōu)化；然后再固定住b不動，對b進(jìn)行優(yōu)化。如此反復(fù)，直至收斂到最優(yōu)解處。

AdaBoost算法是這種方法的典型代表。AdaBoost算法在訓(xùn)練時采用了指數(shù)損失函數(shù)：

由于強(qiáng)分類器是多個弱分類器的加權(quán)和，代入上面的損失函數(shù)中，得到算法訓(xùn)練時要優(yōu)化的目標(biāo)函數(shù)為：

這里將指數(shù)損傷函數(shù)拆成了兩部分，已有的強(qiáng)分類器Fj?1，以及當(dāng)前弱分類器f對訓(xùn)練樣本的損失函數(shù)，前者在之前的迭代中已經(jīng)求出，因此可以看成常數(shù)。這樣目標(biāo)函數(shù)可以簡化為：

其中：

這個問題可以分兩步求解，首先將弱分類器權(quán)重β看成常數(shù)，得到最優(yōu)的弱分類器f。得到弱分類器之后，再優(yōu)化它的權(quán)重系數(shù)β。

動態(tài)規(guī)劃也是一種求解思想，它將一個問題分解成子問題求解，如果整個問題的某個解是最優(yōu)的，則這個解的任意一部分也是子問題的最優(yōu)解。這樣通過求解子問題，得到最優(yōu)解，逐步擴(kuò)展，最后得到整個問題的最優(yōu)解。

隱馬爾可夫模型的解碼算法（維特比算法），強(qiáng)化學(xué)習(xí)中的動態(tài)規(guī)劃算法是這類方法的典型代表，此類算法一般是離散變量的優(yōu)化，而且是組合優(yōu)化問題。前面講述的基于導(dǎo)數(shù)的優(yōu)化算法都無法使用。動態(tài)規(guī)劃算法能高效的求解此類問題，其基礎(chǔ)是貝爾曼最優(yōu)化原理。一旦寫成了遞歸形式的最優(yōu)化方程，就可以構(gòu)造算法進(jìn)行求解。