轉(zhuǎn)自Poll 的筆記
閱讀目錄
- 梯度下降法（Gradient Descent）
- 牛頓法和擬牛頓法（Newton's method & Quasi-Newton Methods）
- 共軛梯度法（Conjugate Gradient）
- 啟發(fā)式優(yōu)化方法
- 解決約束優(yōu)化問題——拉格朗日乘數(shù)法
我們每個人都會在我們的生活或者工作中遇到各種各樣的最優(yōu)化問題，比如每個企業(yè)和個人都要考慮的一個問題“在一定成本下悼瘾，如何使利潤最大化”等芥玉。最優(yōu)化方法是一種數(shù)學(xué)方法唤衫，它是研究在給定約束之下如何尋求某些因素(的量)，以使某一(或某些)指標(biāo)達(dá)到最優(yōu)的一些學(xué)科的總稱端蛆。隨著學(xué)習(xí)的深入，博主越來越發(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)前位置負(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ī)梯度下降法和批量梯度下降法。
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很大，那么可想而知這種方法的迭代速度會相當(dāng)?shù)穆嗯椤Ｋ约夤觯@就引入了另外一種方法——隨機(jī)梯度下降。
對于批量梯度下降法瞧柔，樣本個數(shù)m漆弄，x為n維向量，一次迭代需要把m個樣本全部帶入計(jì)算造锅，迭代一次計(jì)算量為mn2
撼唾。
2）隨機(jī)梯度下降（Stochastic Gradient Descent，SGD）
「缥怠（1）上面的風(fēng)險函數(shù)可以寫成如下這種形式倒谷，損失函數(shù)對應(yīng)的是訓(xùn)練集中每個樣本的粒度，而上面批量梯度下降對應(yīng)的是所有的訓(xùn)練樣本：
〔诠俊（2）每個樣本的損失函數(shù)渤愁，對theta求偏導(dǎo)得到對應(yīng)梯度，來更新theta：
”睹摇（3）隨機(jī)梯度下降是通過每個樣本來迭代更新一次猴伶，如果樣本量很大的情況（例如幾十萬），那么可能只用其中幾萬條或者幾千條的樣本塌西，就已經(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ù)量。*
對批量梯度下降法和隨機(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)練樣本情況。
回到頂部
- 牛頓法和擬牛頓法（Newton's method & Quasi-Newton Methods）
1）牛頓法（Newton's method）
牛頓法是一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法做裙。方法使用函數(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 '(x0
)的直線和 x 軸的交點(diǎn)的x坐標(biāo)拧廊，也就是求如下方程的解：
我們將新求得的點(diǎn)的 x 坐標(biāo)命名為x1
，通常x1
會比x0
更接近方程f (x) = 0的解晋修。因此我們現(xiàn)在可以利用x1
開始下一輪迭代吧碾。迭代公式可化簡為如下所示：
已經(jīng)證明，如果f ' 是連續(xù)的墓卦，并且待求的零點(diǎn)x是孤立的倦春，那么在零點(diǎn)x周圍存在一個區(qū)域，只要初始值x0
位于這個鄰近區(qū)域內(nèi)落剪，那么牛頓法必定收斂睁本。 并且，如果f ' (x)不為0, 那么牛頓法將具有平方收斂的性能. 粗略的說忠怖，這意味著每迭代一次呢堰，牛頓法結(jié)果的有效數(shù)字將增加一倍。下圖為一個牛頓法執(zhí)行過程的例子凡泣。
由于牛頓法是基于當(dāng)前位置的切線來確定下一次的位置枉疼，所以牛頓法又被很形象地稱為是"切線法"。牛頓法的搜索路徑（二維情況）如下圖所示：
牛頓法搜索動態(tài)示例圖：
關(guān)于牛頓法和梯度下降法的效率對比：
從本質(zhì)上去看鞋拟，牛頓法是二階收斂骂维，梯度下降是一階收斂摇锋，所以牛頓法就更快冰单。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部奠蹬，梯度下降法每次只從你當(dāng)前所處位置選一個坡度最大的方向走一步哮笆，牛頓法在選擇方向時来颤，不僅會考慮坡度是否夠大汰扭，還會考慮你走了一步之后，坡度是否會變得更大福铅。所以萝毛，可以說牛頓法比梯度下降法看得更遠(yuǎn)一點(diǎn)，能更快地走到最底部滑黔。（牛頓法目光更加長遠(yuǎn)笆包，所以少走彎路；相對而言略荡，梯度下降法只考慮了局部的最優(yōu)庵佣，沒有全局思想。）
根據(jù)wiki上的解釋汛兜，從幾何上說巴粪，牛頓法就是用一個二次曲面去擬合你當(dāng)前所處位置的局部曲面，而梯度下降法是用一個平面去擬合當(dāng)前的局部曲面粥谬，通常情況下肛根，二次曲面的擬合會比平面更好，所以牛頓法選擇的下降路徑會更符合真實(shí)的最優(yōu)下降路徑漏策。
注：紅色的牛頓法的迭代路徑派哲，綠色的是梯度下降法的迭代路徑。
牛頓法的優(yōu)缺點(diǎn)總結(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)谦絮。
擬牛頓法的本質(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
是一個對稱正定矩陣隙赁，于是我們?nèi)∵@個二次模型的最優(yōu)解作為搜索方向，并且得到新的迭代點(diǎn)：
其中我們要求步長ak
滿足Wolfe條件梆暖。這樣的迭代與牛頓法類似伞访，區(qū)別就在于用近似的Hesse矩陣Bk
代替真實(shí)的Hesse矩陣。所以擬牛頓法最關(guān)鍵的地方就是每一步迭代中矩陣Bk
的更新『洳担現(xiàn)在假設(shè)得到一個新的迭代xk+1
厚掷，并得到一個新的二次模型：
我們盡可能地利用上一步的信息來選取Bk
。具體地级解，我們要求
從而得到
這個公式被稱為割線方程蝗肪。常用的擬牛頓法有DFP算法和BFGS算法。
回到頂部
- 共軛梯度法（Conjugate Gradient）
共軛梯度法是介于最速下降法與牛頓法之間的一個方法蠕趁，它僅需利用一階導(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-Ax; p=r; rsold=r'r; for i=1:length(b) Ap=Ap; alpha=rsold/(p'Ap); x=x+alphap; r=r-alphaAp; rsnew=r'r; if sqrt(rsnew)<1e-10 break; end p=r+(rsnew/rsold)p; rsold=rsnew; endend
回到頂部
- 啟發(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)化算法咸包，它主要針對同時優(yōu)化多個目標(biāo)（兩個及兩個以上）的優(yōu)化問題，這方面比較經(jīng)典的算法有NSGAII算法杖虾、MOEA/D算法以及人工免疫算法等烂瘫。
這部分的內(nèi)容會在之后的博文中進(jìn)行詳細(xì)總結(jié)，敬請期待亏掀。這部分內(nèi)容的介紹已經(jīng)在博客《[Evolutionary Algorithm] 進(jìn)化算法簡介》進(jìn)行了概要式的介紹忱反，有興趣的博友可以進(jìn)行參考（2015.12.13）。
- 解決約束優(yōu)化問題——拉格朗日乘數(shù)法
有關(guān)拉格朗日乘數(shù)法的介紹請見我的另一篇博客：《拉格朗日乘數(shù)法》
[1]. Gradient Descent, Wolfe's Condition and Logistic Regression
