機(jī)器學(xué)習(xí)中常見的幾種優(yōu)化方法

1、機(jī)器學(xué)習(xí)中常見的幾種優(yōu)化方法閱讀目錄1. 梯度下降法( Gradient Descent )2. 牛頓法和擬牛頓法( Newtons method & Quasi-Newton Methods )3. 共軛梯度法( Conjugate Gradient )4. 啟發(fā)式優(yōu)化方法5. 解決約束優(yōu)化問題拉格朗日乘數(shù)法我們每個人都會在我們的生活或者工作中遇到各種各 樣的最優(yōu)化問題，比如每個企業(yè)和個人都要考慮的一個問題 “在一定成本下，如何使利潤最大化”等。最優(yōu)化方法是一種 數(shù)學(xué)方法，它是研究在給定約束之下如何尋求某些因素(的量 )，以使某一 (或某些 )指標(biāo)達(dá)到最優(yōu)的一些學(xué)科的總稱。隨 著學(xué)習(xí)

2、的深入，博主越來越發(fā)現(xiàn)最優(yōu)化方法的重要性，學(xué)習(xí) 和工作中遇到的大多問題都可以建模成一種最優(yōu)化模型進(jìn) 行求解，比如我們現(xiàn)在學(xué)習(xí)的機(jī)器學(xué)習(xí)算法，大部分的機(jī)器 學(xué)習(xí)算法的本質(zhì)都是建立優(yōu)化模型，通過最優(yōu)化方法對目標(biāo) 函數(shù)(或損失函數(shù))進(jìn)行優(yōu)化，從而訓(xùn)練出最好的模型。常 見的最優(yōu)化方法有梯度下降法、牛頓法和擬牛頓法、共軛梯回到頂部1. 梯度下降法（ Gradient Descent ）梯度下降法是最早最簡單，也是最為常用的最優(yōu)化方法。 梯度下降法實(shí)現(xiàn)簡單，當(dāng)目標(biāo)函數(shù)是凸函數(shù)時，梯度下降法 的解是全局解。一般情況下，其解不保證是全局最優(yōu)解，梯 度下降法的速度也未必是最快的。梯度下降法的優(yōu)化思想是 用當(dāng)前位

3、置負(fù)梯度方向作為搜索方向，因?yàn)樵摲较驗(yàn)楫?dāng)前位 置的最快下降方向，所以也被稱為是”最速下降法“。最速下 降法越接近目標(biāo)值，步長越小，前進(jìn)越慢。梯度下降法的搜 索迭代示意圖如下圖所示：牛頓法的缺點(diǎn)：（1）靠近極小值時收斂速度減慢，如下圖所示；（2）直線搜索時可能會產(chǎn)生一些問題；（3）可能會“之字形”地下降。從上圖可以看出，梯度下降法在接近最優(yōu)解的區(qū)域收斂 速度明顯變慢，利用梯度下降法求解需要很多次的迭代。在機(jī)器學(xué)習(xí)中，基于基本的梯度下降法發(fā)展了兩種梯度 下降方法，分別為隨機(jī)梯度下降法和批量梯度下降法比如對一個線性回歸( Linear Logistics )模型，假設(shè)下 面的 h(x) 是要擬合的函

4、數(shù)， J(theta) 為損失函數(shù)， theta 是參 數(shù)，要迭代求解的值， theta 求解出來了那最終要擬合的函 數(shù) h(theta) 就出來了。其中 m 是訓(xùn)練集的樣本個數(shù)， n 是特 征的個數(shù)。1)批量梯度下降法( Batch Gradient Descent ，BGD )(1 )將 J(theta) 對 theta 求偏導(dǎo)，得到每個 theta 對應(yīng) 的的梯度：(2)由于是要最小化風(fēng)險函數(shù)，所以按每個參數(shù)theta的梯度負(fù)方向，來更新每個 theta ：(3)從上面公式可以注意到，它得到的是一個全局最 優(yōu)解，但是每迭代一步，都要用到訓(xùn)練集所有的數(shù)據(jù)，如果 m 很大，那么可想而知這種方

5、法的迭代速度會相當(dāng)?shù)穆?。?以，這就引入了另外一種方法隨機(jī)梯度下降。對于批量梯度下降法，樣本個數(shù) m， x 為 n 維向量，一 次迭代需要把 m 個樣本全部帶入計(jì)算，迭代一次計(jì)算量為m*n2 。2）隨機(jī)梯度下降 （ Random Gradient Descent ，RGD ）（1）上面的風(fēng)險函數(shù)可以寫成如下這種形式，損失函 數(shù)對應(yīng)的是訓(xùn)練集中每個樣本的粒度，而上面批量梯度下降 對應(yīng)的是所有的訓(xùn)練樣本：（ 2）每個樣本的損失函數(shù)，對 theta 求偏導(dǎo)得到對應(yīng)梯 度，來更新 theta ：（ 3 ）隨機(jī)梯度下降是通過每個樣本來迭代更新一次， 如果樣本量很大的情況（例如幾十萬） ，那么可能只用其中

6、 幾萬條或者幾千條的樣本， 就已經(jīng)將 theta 迭代到最優(yōu)解了， 對比上面的批量梯度下降，迭代一次需要用到十幾萬訓(xùn)練樣 本，一次迭代不可能最優(yōu)，如果迭代 10 次的話就需要遍歷 訓(xùn)練樣本10次。但是，SGD伴隨的一個問題是噪音較 BGD 要多，使得 SGD 并不是每次迭代都向著整體最優(yōu)化方向。隨機(jī)梯度下降每次迭代只使用一個樣本，迭代一次計(jì)算量為n2，當(dāng)樣本個數(shù) m很大的時候，隨機(jī)梯度下降迭代一 次的速度要遠(yuǎn)高于批量梯度下降方法。兩者的關(guān)系可以這樣 理解：隨機(jī)梯度下降方法以損失很小的一部分精確度和增加 一定數(shù)量的迭代次數(shù)為代價，換取了總體的優(yōu)化效率的提升。 增加的迭代次數(shù)遠(yuǎn)遠(yuǎn)小于樣本的數(shù)量。對

7、批量梯度下降法和隨機(jī)梯度下降法的總結(jié)： 批量梯度下降 - 最小化所有訓(xùn)練樣本的損失函數(shù)，使得 最終求解的是全局的最優(yōu)解，即求解的參數(shù)是使得風(fēng)險函數(shù) 最小，但是對于大規(guī)模樣本問題效率低下。隨機(jī)梯度下降 - 最小化每條樣本的損失函數(shù)，雖然不是 每次迭代得到的損失函數(shù)都向著全局最優(yōu)方向， 但是大的整體的方向是向全局最優(yōu)解的，最終的結(jié)果往往是 在全局最優(yōu)解附近，適用于大規(guī)模訓(xùn)練樣本情況。回到頂部2. 牛頓法和擬牛頓法( Newtons method &Quasi-Newton Methods )1 )牛頓法( Newtons method )牛頓法是一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方 法。

8、方法使用函數(shù) f (x) 的泰勒級數(shù)的前面幾項(xiàng)來尋找方程f(x)= 0 的根。牛頓法最大的特點(diǎn)就在于它的收斂速度很快。具體步驟：首先，選擇一個接近函數(shù) f (x)零點(diǎn)的x0 ,計(jì)算相應(yīng)的f(x0) 和切線斜率 f (x0) (這里 f 表示函數(shù) f的導(dǎo)數(shù))。然后我們計(jì)算穿過點(diǎn) (x0, f (x0) 并且斜率為 f(xO)的直線和x軸的交點(diǎn)的x坐標(biāo)，也就是求如下方程的解：我們將新求得的點(diǎn)的x坐標(biāo)命名為x1，通常x1會比xO 更接近方程 f(x) = O 的解。因此我們現(xiàn)在可以利用 x1 開始下一輪迭代。 迭代公式可化簡為如下所示：已經(jīng)證明，如果f 是連續(xù)的，并且待求的零點(diǎn)x是孤 立的，那么在零

9、點(diǎn)x周圍存在一個區(qū)域，只要初始值 xO位 于這個鄰近區(qū)域內(nèi)，那么牛頓法必定收斂。并且，如果f (x)不為0,那么牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結(jié)果的有效數(shù) 字將增加一倍。下圖為一個牛頓法執(zhí)行過程的例子。由于牛頓法是基于當(dāng)前位置的切線來確定下一次的位 置，所以牛頓法又被很形象地稱為是切線法 。牛頓法的搜索路徑(二維情況)如下圖所示：牛頓法搜索動態(tài)示例圖：關(guān)于牛頓法和梯度下降法的效率對比： 從本質(zhì)上去看，牛頓法是二階收斂，梯度下降是一階收 斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找 一條最短的路徑走到一個盆地的最底部，梯度下降法每次只 從你當(dāng)前所處位置

10、選一個坡度最大的方向走一步，牛頓法在 選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一 步之后，坡度是否會變得更大。所以，可以說牛頓法比梯度 下降法看得更遠(yuǎn)一點(diǎn)，能更快地走到最底部。 （牛頓法目光 更加長遠(yuǎn)，所以少走彎路；相對而言，梯度下降法只考慮了 局部的最優(yōu)，沒有全局思想。 ）根據(jù) wiki 上的解釋，從幾何上說，牛頓法就是用一個二 次曲面去擬合你當(dāng)前所處位置的局部曲面，而梯度下降法是 用一個平面去擬合當(dāng)前的局部曲面，通常情況下，二次曲面 的擬合會比平面更好，所以牛頓法選擇的下降路徑會更符合 真實(shí)的最優(yōu)下降路徑。注：紅色的牛頓法的迭代路徑，綠色 的是梯度下降法的迭代路徑。牛頓法的優(yōu)缺點(diǎn)

11、總結(jié)： 優(yōu)點(diǎn)：二階收斂，收斂速度快； 缺點(diǎn)：牛頓法是一種迭代算法，每一步都需要求解目標(biāo) 函數(shù)的 Hessian 矩陣的逆矩陣，計(jì)算比較復(fù)雜。2 )擬牛頓法( Quasi-Newton Methods ) 擬牛頓法是求解非線性優(yōu)化問題最有效的方法之一，于 20 世紀(jì) 50 年代由美國 Argonne 國家實(shí)驗(yàn)室的物理學(xué)家 W.C.Davidon 所提出來。 Davidon 設(shè)計(jì)的這種算法在當(dāng)時看 來是非線性優(yōu)化領(lǐng)域最具創(chuàng)造性的發(fā)明之一。不久 R. Fletcher 和 M. J. D. Powell 證實(shí)了這種新的算法遠(yuǎn)比其他方 法快速和可靠，使得非線性優(yōu)化這門學(xué)科在一夜之間突飛猛 進(jìn)。擬牛頓法

12、的本質(zhì)思想是改善牛頓法每次需要求解復(fù)雜 的 Hessian 矩陣的逆矩陣的缺陷，它使用正定矩陣來近似 Hessian 矩陣的逆，從而簡化了運(yùn)算的復(fù)雜度。擬牛頓法和 最速下降法一樣只要求每一步迭代時知道目標(biāo)函數(shù)的梯度。 通過測量梯度的變化，構(gòu)造一個目標(biāo)函數(shù)的模型使之足以產(chǎn) 生超線性收斂性。這類方法大大優(yōu)于最速下降法，尤其對于 困難的問題。另外，因?yàn)閿M牛頓法不需要二階導(dǎo)數(shù)的信息， 所以有時比牛頓法更為有效。如今，優(yōu)化軟件中包含了大量 的擬牛頓算法用來解決無約束， 約束，和大規(guī)模的優(yōu)化問題。具體步驟： 擬牛頓法的基本思想如下。首先構(gòu)造目標(biāo)函數(shù)在當(dāng)前迭 代 xk 的二次模型：這里 Bk 是一個對稱正定

13、矩陣，于是我們?nèi)∵@個二次模型的最優(yōu)解作為搜索方向，并且得到新的迭代點(diǎn)：其中我們要求步長 ak滿足 Wolfe 條件。這樣的迭代與牛頓法類似，區(qū)別就在于用近似的 Hesse 矩陣 Bk代替真實(shí)的 Hesse 矩陣。所以擬牛頓法最關(guān)鍵的地方就是每一步迭代中矩陣 Bk的更新?，F(xiàn)在假設(shè)得到一個新的迭代 xk+1 ，并得到一個新的二次模型：我們盡可能地利用上一步的信息來選取Bk 。具體地，我們要求從而得到這個公式被稱為割線方程。常用的擬牛頓法有 DFP 算 法和 BFGS 算法?；氐巾敳?. 共軛梯度法( Conjugate Gradient ) 共軛梯度法是介于最速下降法與牛頓法之間的一個方 法，它僅

14、需利用一階導(dǎo)數(shù)信息，但克服了最速下降法收斂慢 的缺點(diǎn)，又避免了牛頓法需要存儲和計(jì)算 Hesse 矩陣并求逆 的缺點(diǎn)，共軛梯度法不僅是解決大型線性方程組最有用的方 法之一，也是解大型非線性最優(yōu)化最有效的算法之一。 在 各種優(yōu)化算法中，共軛梯度法是非常重要的一種。其優(yōu)點(diǎn)是 所需存儲量小，具有步收斂性，穩(wěn)定性高，而且不需要任何 外來參數(shù)。具體的實(shí)現(xiàn)步驟請參加 wiki 百科共軛梯度法。 下圖為共軛梯度法和梯度下降法搜索最優(yōu)解的路徑對 比示意圖：注：綠色為梯度下降法，紅色代表共軛梯度法MATLAB 代碼： function x = conjgrad(A,b,x) r=b-A*x;p=r;rsold=r

15、*r; for i=1:length(b)Ap=A*p; alpha=rsold/(p*Ap); x=x+alpha*p; r=r-alpha*Ap;rsnew=r*r;if sqrt(rsnew)<1e-10break;end p=r+(rsnew/rsold)*p; rsold=rsnew;endend回到頂部4. 啟發(fā)式優(yōu)化方法 啟發(fā)式方法指人在解決問題時所采取的一種根據(jù)經(jīng)驗(yàn) 規(guī)則進(jìn)行發(fā)現(xiàn)的方法。 其特點(diǎn)是在解決問題時 ,利用過去的經(jīng) 驗(yàn),選擇已經(jīng)行之有效的方法， 而不是系統(tǒng)地、 以確定的步驟 去尋求答案。啟發(fā)式優(yōu)化方法種類繁多，包括經(jīng)典的模擬退 火方法、遺傳算法、蟻群算法以及粒子群算法等等。還有一種特殊的優(yōu)化算法被稱之多目標(biāo)優(yōu)化