前言：

??????? 在機(jī)器學(xué)習(xí)方法中，若模型理解為決策模型，有些模型可以使用解析方法。不過更一般的對模型的求解使用優(yōu)化的方法，更多的數(shù)據(jù)可以得到更多的精度。

??????? AI中基于歸納的方法延伸出ML整個(gè)領(lǐng)域，基于數(shù)據(jù)的ML方法根據(jù)歸納準(zhǔn)則進(jìn)行擬合，基于約束函數(shù)和經(jīng)驗(yàn)期望，并對擬合的函數(shù)形式和函數(shù)參數(shù)，進(jìn)行優(yōu)化。

?????? 上一篇：最優(yōu)化方法之GD、SGD ；最優(yōu)化之回歸/擬合方法總結(jié)；

一、線性規(guī)劃

?????? 線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃等方法其目標(biāo)函數(shù)與約束條件都是決策變量的一次函數(shù)，全部為線性規(guī)劃，具有統(tǒng)一的數(shù)學(xué)模型及如單純形法這樣的通用解法。1947年丹齊格（G.B.Dantzig）提出了線性規(guī)劃的一般方法——單純形法。隨后專業(yè)豐富了線性規(guī)劃的數(shù)學(xué)模型和求解方法，并深入分析細(xì)節(jié)，如對偶理論、線性目標(biāo)規(guī)劃等。

?????? 摘自于小黃書，應(yīng)該是自動(dòng)化學(xué)院雙控系的教材。

?????? 若建立的一個(gè)數(shù)學(xué)模型，（1）要求一組變量X1, X2, X3....Xn的值（2）滿足特定的約束條件（Xk...Xi的之間約束關(guān)系，和Xi的定義域約束關(guān)系），（3）同時(shí)使一次目標(biāo)函數(shù) y = K1X1 + K2X2 + ... +KnXn 取得極值。即求min y( X1, X2, X3....Xn ) 。此種問題為線性規(guī)劃問題。

?????? 標(biāo)準(zhǔn)形式：

????????????? min y = K1X1 + K2X2 + ... + KnXn ;? ( 3 )

?????????????????????? a11X1 + a12X2 + ... + a1nXn ?? = b1; ? ? ?? ( 2 )

?????????????????????? a21X1 + a22X2 + ... + a2nXn? ? = b2;? ? ? ? ( 2 )

?????????????????????? ...................................................???? ? ? ? ? ( 2 )

?????????????????????? am1X1 + am2X2 + ... + amnXn = bm; ? ? ? ( 2 )

????????????????????? ? K1<< Xi? << K2?????????????????????????????? ; ?? ?? ( 2 )

???????? 簡化形式為：

?????????????????

???????? 矩陣形式為：

???????????

重要的定理：

????? 線性規(guī)劃基本定理：若線性規(guī)劃存在可行域，則可行域 S = { x | Ax=b,x>=0,A屬于Mm*n, b 屬于R^m, x 屬于R^n } 為一凸集。

?????? 極點(diǎn)：線性規(guī)劃問題的每一個(gè)基本可行解x對應(yīng)可行域S的一個(gè)極點(diǎn)。

?????? 最優(yōu)解：若線性規(guī)劃具有最優(yōu)解，則必可在其某個(gè)可行域的某個(gè)（或者多個(gè)）極點(diǎn)上達(dá)到最優(yōu)解。

?????? 示例：若約束矩陣A為m*n型矩陣，且A的秩r(A)=m，則基本解的個(gè)數(shù)<=? N= 組合(m,n)，也是基本可行解的上限。

???????????????? 最基本的尋找線性規(guī)劃最優(yōu)解的方法為枚舉法，但組合爆炸使其適用范圍極窄，因此有規(guī)律尋找最優(yōu)解成為必然。

單純形法：

?????? snip//.................................

二、非線性規(guī)劃

??????? 非線性規(guī)劃最簡單的為一維搜索，即在一維空間尋求最優(yōu)解，基本方法有黃金分割法、加步探索法、牛頓迭代法、二次優(yōu)化-拋物線法。

??????? 關(guān)于一般非線性規(guī)劃優(yōu)化算法的求解，最優(yōu)化方法一書已經(jīng)介紹了很多的方法，比如有梯度下降法，坐標(biāo)下降法，牛頓法和擬牛頓法，共軛梯度法。而機(jī)器學(xué)習(xí)中主要面對非線性問題，所使用的優(yōu)化方法為非線性優(yōu)化方法。

??????? 以下摘抄自百度百科。

1.最速下降法

??????? 梯度下降法是基于目標(biāo)函數(shù)梯度的，算法的收斂速度是線性的，并且當(dāng)問題是病態(tài)時(shí)或者問題規(guī)模較大時(shí)，收斂速度尤其慢（幾乎不適用）。例如。SVM方法使用梯度下降法時(shí)其運(yùn)行可行性受到樣本數(shù)目的限制，樣本數(shù)目過多會(huì)產(chǎn)生較大的系數(shù)矩陣，訓(xùn)練速度極慢。

??????? 變量輪換法（坐標(biāo)下降法）雖然不用計(jì)算目標(biāo)函數(shù)的梯度，但是其收斂速度依然很慢，因此它的適用范圍也有局限；

????????

???? 其他缺點(diǎn)：（1）靠近極小值時(shí)收斂速度減慢，如下圖所示；（2）直線搜索時(shí)可能會(huì)產(chǎn)生一些問題；（3）之字形下降。

?SGD和BGD

?????? 隨機(jī)梯度下降每次迭代只使用一個(gè)樣本，迭代一次計(jì)算量為n²，當(dāng)樣本個(gè)數(shù)m很大的時(shí)候，隨機(jī)梯度下降迭代一次的速度要遠(yuǎn)高于批量梯度下降方法。兩者的關(guān)系可以這樣理解：隨機(jī)梯度下降方法以損失很小的一部分精確度和增加一定數(shù)量的迭代次數(shù)為代價(jià)，換取了總體的優(yōu)化效率的提升。增加的迭代次數(shù)遠(yuǎn)遠(yuǎn)小于樣本的數(shù)量。

　　對批量梯度下降法和隨機(jī)梯度下降法的總結(jié)：

　　批量梯度下降---最小化所有訓(xùn)練樣本的損失函數(shù)，使得最終求解的是全局的最優(yōu)解，即求解的參數(shù)是使得風(fēng)險(xiǎn)函數(shù)最小，但是對于大規(guī)模樣本問題效率低下。

　　隨機(jī)梯度下降---最小化每條樣本的損失函數(shù)，雖然不是每次迭代得到的損失函數(shù)都向著全局最優(yōu)方向， 但是大的整體的方向是向全局最優(yōu)解的，最終的結(jié)果往往是在全局最優(yōu)解附近，適用于大規(guī)模訓(xùn)練樣本情況。

2.牛頓迭代法

?????? 牛頓法（修正的牛頓法）主要思想是：體現(xiàn)為一種函數(shù)逼近方法，在極小點(diǎn)附近用二階泰勒多項(xiàng)近似代替目標(biāo)函數(shù)f(x), 從而求出極小點(diǎn)的估計(jì)值。若f(x)在極小點(diǎn)附近有二階連續(xù)偏導(dǎo)數(shù)，且在點(diǎn)處的黑塞矩陣正定，可進(jìn)行迭代估計(jì)。又稱為切線法。

? ? ? ?? ?? 牛頓法求解迭代過程圖

? ? ? ??

注：紅色的牛頓法的迭代路徑，綠色的是梯度下降法的迭代路徑。

?????? 圖片來自于：ML中的常用優(yōu)化方法，公式挺好

?????? 根據(jù)wiki上的解釋，從幾何上說，牛頓法就是用一個(gè)二次曲面去擬合你當(dāng)前所處位置的局部曲面，而梯度下降法是用一個(gè)平面去擬合當(dāng)前的局部曲面，通常情況下，二次曲面的擬合會(huì)比平面更好，所以牛頓法選擇的下降路徑會(huì)更符合真實(shí)的最優(yōu)下降路徑。

?????? 牛頓法是基于目標(biāo)函數(shù)的二階導(dǎo)數(shù)（海森矩陣）的，其收斂速度較快，迭代次數(shù)較少，尤其是在最優(yōu)值附近時(shí)，收斂速度是二次的。但牛頓法的問題在于當(dāng)海森矩陣稠密時(shí)，每次迭代的計(jì)算量比較大，因?yàn)?strong>每次都會(huì)計(jì)算目標(biāo)函數(shù)的海森矩陣的逆，這樣一來，當(dāng)問題規(guī)模較大時(shí)，不僅計(jì)算量大（有時(shí)大到不可計(jì)算），而且需要的存儲(chǔ)空間也多，因此牛頓法在面對海量數(shù)據(jù)時(shí)由于每一步迭代的開銷巨大而變得不適用；

??????

3.擬牛頓法

??????? 牛頓法在每次迭代時(shí)不能總是保證海森矩陣是正定的，一旦海森矩陣不是正定的，優(yōu)化方向就會(huì) “ 跑偏 ”，從而使得牛頓法失效，也說明了牛頓法的魯棒性較差。擬牛頓法用海森矩陣的逆矩陣來替代海森矩陣，雖然每次迭代不能保證是最優(yōu)的優(yōu)化方向，但是近似矩陣始終是正定的，因此算法總是朝著最優(yōu)值的方向在搜索。

??????? 擬牛頓法（DFP和BFGS）是20世紀(jì)50年代，美國Argonne國家實(shí)驗(yàn)室的物理學(xué)家W. C. Davidon所提出來的。是在牛頓法的基礎(chǔ)上引入了海森矩陣的近似矩陣，避免每次迭代都要計(jì)算海森矩陣的逆，擬牛頓法的收斂速度介于梯度下降法和牛頓法之間，是超線性的。擬牛頓法的問題也是當(dāng)問題規(guī)模很大時(shí)，近似矩陣變得很稠密，在計(jì)算和存儲(chǔ)上也有很大的開銷，因此也會(huì)變得不實(shí)用。

??????? 優(yōu)勢：擬牛頓法和最速下降法(Steepest Descent Methods)一樣只要求每一步迭代時(shí)知道目標(biāo)函數(shù)的梯度。通過測量梯度的變化，構(gòu)造一個(gè)目標(biāo)函數(shù)的模型使之足以產(chǎn)生超線性收斂性。這類方法大大優(yōu)于最速下降法，尤其對于困難的問題。另外，因?yàn)閿M牛頓法不需要二階導(dǎo)數(shù)的信息，所以有時(shí)比牛頓法(Newton's Method)更為有效。如今，優(yōu)化軟件中包含了大量的擬牛頓算法用來解決無約束，約束，和大規(guī)模的優(yōu)化問題。

??????
擬牛頓法主要有這幾種方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。

DFP方法

BFGS方法
?
???????
SR1方法 有別于DFP和BFG方法，SR1是一種秩-1更新。它的公式是：B_{k+1}=(y_k-B_ks_k)(y_k-B_ks_k)^T/((y_k-B_ks_k)^Ts_k)。SR1公式不要求矩陣B_k保持正定性，從而更逼近真實(shí)的Hesse矩陣，所以適用于信賴域方法(Trust Region Methods)。

Broyden族

Boyden族是更廣泛的一類更新公式，其形式為：B_{k+1}=(1-c_k)B_{k+1}^{BFGS}+c_k B_{k+1}^{DFP}。當(dāng)c_k=0時(shí)，Broyden族公式就變成了BFGS公式；當(dāng)c_k=1時(shí)，Broyden族公式就變成了DFP公式。因此BFGS和DFP均可看成Broyden族的特殊形式或者其中一員。

4. L-FBGS算法

?????? 從上面的綜合描述可以看出，很多優(yōu)化算法在理論上有很好的結(jié)果，并且當(dāng)優(yōu)化問題的規(guī)模較小時(shí)，上面的任何算法都能夠很好地解決問題。而在實(shí)際工程中，很多算法卻失效了。比如說，在實(shí)際工程中，很多問題是病態(tài)的，這樣一來，基于梯度的方法肯定會(huì)失效，即便迭代上千上萬次也未必收斂到很好的結(jié)果；另外，當(dāng)數(shù)據(jù)量大的時(shí)候，牛頓法和擬牛頓法需要保存矩陣的內(nèi)存開銷和計(jì)算矩陣的開銷都很大，因此也會(huì)變得不適用。

??????? 實(shí)際工程中解決大規(guī)模優(yōu)化問題時(shí)必然會(huì)用到的一種優(yōu)化算法：L-BFGS算法。

??????? L-BFGS算法就是對擬牛頓算法的一個(gè)改進(jìn)。它的名字已經(jīng)告訴我們它是基于擬牛頓法BFGS算法的改進(jìn)。L-BFGS算法的基本思想是：算法只保存并利用最近m次迭代的曲率信息來構(gòu)造海森矩陣的近似矩陣。

在介紹L-BFGS算法之前，我們先來簡單回顧下BFGS算法。

?????? 以下參考：http://blog.csdn.net/henryczj/article/details/41542049?utm_source=tuicool&utm_medium=referral

在算法的每一步迭代，有如下式：

，????? k = 0, 1, 2,…,?????????? （1）

式（1）中a_k是步長，H_k的更新通過如下公式：

?（2）

在式（2）中

?（3）

?（4）

?（5）

（6）

從式（2）到式（6）可以看出H_k+1是用{s_k, y_k}修正H_k來得到的。需要注意的是，這里H_k表示海森矩陣的逆的近似矩陣。

?????? 在BFGS算法中，由于H_k隨著迭代次數(shù)的增加會(huì)越來越稠密，當(dāng)優(yōu)化問題的規(guī)模很大時(shí)，存儲(chǔ)和計(jì)算矩陣H_k將變得不可行。

?????? 為了解決上述問題，我們可以不存儲(chǔ)矩陣H_k，而是存儲(chǔ)最近m次迭代的曲率信息，即{s_k, y_k}。每當(dāng)完成一次迭代，最舊的曲率信息{s_i, y_i}將被刪除，而最新的曲率信息被保存下來，維持一個(gè)曲率隊(duì)列。通過這種方式，算法保證了保存的曲率信息是來自于最近的m次迭代。在實(shí)際工程中，m取3到20往往能有很好的結(jié)果。除了更新矩陣H_k的策略和初始化H_k的方式不同外，L-BFGS算法和BFGS算法是一樣的。

下面將會(huì)詳細(xì)介紹一下矩陣H_k的更新步驟。

?????? 在第k次迭代，算法求得了x_k，并且保存的曲率信息為{s_i, y_i}，其中i = k-m, …, k-1。為了得到H_k，算法首先選擇一個(gè)初始的矩陣H_k⁰，這是不同于BFGS算法的一個(gè)地方，L-BFGS算法允許每次迭代選取一個(gè)初始的矩陣，然后用最近的m次曲率信息對該初始矩陣進(jìn)行修正，從而得到H_k。

?????? 通過反復(fù)利用式（2），我們可以得到下式：

?????

?????? 關(guān)于每次迭代時(shí)H _k ⁰的初始值的設(shè)定，一個(gè)在實(shí)踐中經(jīng)常用到的有效方法為：

??????

?（8）

（9）

??????? 其中r_k表示比例系數(shù)，它利用最近一次的曲率信息來估計(jì)真實(shí)海森矩陣的大小，這就使得當(dāng)前步的搜索方向較為理想，而不至于跑得“太偏”，從而使得步長a_k = 1在大多數(shù)時(shí)候都是滿足的，這樣就省去了步長搜索的步驟，節(jié)省了時(shí)間。

??????? 在L-BFGS算法中，通過保存最近m次的曲率信息來更新近似矩陣的這種方法在實(shí)踐中是很有效的。

??????? 雖然L-BFGS算法是線性收斂，但是每次迭代的開銷非常小，因此L-BFGS算法執(zhí)行速度還是很快的，而且由于每一步迭代都能保證近似矩陣的正定，因此算法的魯棒性還是很強(qiáng)的。

shooting算法

??????? 百度最近提出了一個(gè)shooting算法，該算法比L-BFGS快了十倍。由于L-BFGS算法的迭代方向不是最優(yōu)的，所以我猜想shooting算法應(yīng)該是在迭代的方向上做了優(yōu)化。

???????? ............................

總結(jié)

以上是生活随笔為你收集整理的**ML : ML中的最优化方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。