機器學習中常見的幾種優(yōu)化方法

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

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

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

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

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

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

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

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

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

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

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

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

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

14、需利用一階導數信息，但克服了最速下降法收斂慢 的缺點，又避免了牛頓法需要存儲和計算 Hesse 矩陣并求逆 的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方 法之一，也是解大型非線性最優(yōu)化最有效的算法之一。 在 各種優(yōu)化算法中，共軛梯度法是非常重要的一種。其優(yōu)點是 所需存儲量小，具有步收斂性，穩(wě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ā)式方法指人在解決問題時所采取的一種根據經驗 規(guī)則進行發(fā)現的方法。 其特點是在解決問題時 ,利用過去的經 驗,選擇已經行之有效的方法， 而不是系統(tǒng)地、 以確定的步驟 去尋求答案。啟發(fā)式優(yōu)化方法種類繁多，包括經典的模擬退 火方法、遺傳算法、蟻群算法以及粒子群算法等等。還有一種特殊的優(yōu)化算法被稱之多目標優(yōu)化