優(yōu)化算法總結(jié)

簡介

本文介紹一下機(jī)器學(xué)習(xí)和深度學(xué)習(xí)中常用的優(yōu)化算法和優(yōu)化器以及一些其他我知道的優(yōu)化算法,部分算法我也沒有搞懂,就先記錄下來以后慢慢研究吧.*_*.

1.梯度下降算法(Gradient Descent)

梯度下降法可以參考我另一篇文章機(jī)器學(xué)習(xí)-線性回歸里的講解,這里就不在重復(fù)敘述.這里需要強(qiáng)調(diào)一下,深度學(xué)習(xí)里常用的SGD,翻譯過來是隨機(jī)梯度下降,但是實(shí)質(zhì)是mini-batch梯度下降(mini-batch-gd),或者說是兩者的結(jié)合更準(zhǔn)確一些.

SGD的優(yōu)點(diǎn)是,算法簡單,計(jì)算量小,在函數(shù)為凸函數(shù)時(shí)可以找到全局最優(yōu)解.所以是最常用的優(yōu)化算法.缺點(diǎn)是如果函數(shù)不是凸函數(shù)的話,很容易進(jìn)入到局部最優(yōu)解而無法跳出來.同時(shí)SGD在選擇學(xué)習(xí)率上也是比較困難的.

2.牛頓法

牛頓法和擬牛頓法都是求解無約束最優(yōu)化問題的常用方法,其中牛頓法是迭代算法,每一步需要求解目標(biāo)函數(shù)的海森矩陣的逆矩陣,計(jì)算比較復(fù)雜.

牛頓法在求解方程根的思想:在二維情況下,迭代的尋找某一點(diǎn)x,尋找方法是隨機(jī)一個(gè)初始點(diǎn)x_0,目標(biāo)函數(shù)在該點(diǎn)x_0的切線與x坐標(biāo)軸的交點(diǎn)就是下一個(gè)x點(diǎn),也就是x_1.不斷迭代尋找x.其中切線的斜率為目標(biāo)函數(shù)在點(diǎn)x_0的導(dǎo)數(shù)(梯度),切必過點(diǎn)(x_0,f(x_0)).所以迭代的方程式如圖1,為了求該方程的極值點(diǎn),還需要令其導(dǎo)數(shù)等于0,也就是又求了一次導(dǎo)數(shù),所以需要用到f(x)的二階導(dǎo)數(shù).

圖1

在最優(yōu)化的問題中,牛頓法提供了一種求解的辦法. 假設(shè)任務(wù)是優(yōu)化一個(gè)目標(biāo)函數(shù)f, 求函數(shù)ff的極大極小問題, 可以轉(zhuǎn)化為求解函數(shù)f導(dǎo)數(shù)等于0的問題, 這樣求可以把優(yōu)化問題看成方程求解問題(f的導(dǎo)數(shù)等于0). 剩下的問題就和牛頓法求解方程根的思想很相似了.

目標(biāo)函數(shù)的泰勒展開式:

圖2

化簡后:

圖3

這樣就得到了與圖1相似的公式,這里是二維的,在多維空間上,求二階導(dǎo)數(shù)就是求海森矩陣,因?yàn)槭欠帜?所以還需要求海森矩陣的逆矩陣.

牛頓法和SGD的區(qū)別:

牛頓法是二階求導(dǎo),SGD是一階求導(dǎo),所以牛頓法要收斂的更快一些.SGD只考慮當(dāng)前情況下梯度下降最快的方向,而牛頓法不僅考慮當(dāng)前梯度下降最快,還有考慮下一步下降最快的方向.

牛頓法的優(yōu)點(diǎn)是二階求導(dǎo)下降速度快,但是因?yàn)槭堑惴?每一步都需要求解海森矩陣的逆矩陣,所以計(jì)算復(fù)雜.

3.擬牛頓法(沒搞懂,待定)

考慮到牛頓法計(jì)算海森矩陣比較麻煩,所以它使用正定矩陣來代替海森矩陣的逆矩陣,從而簡化了計(jì)算過程.

常用的擬牛頓法有DFP算法和BFGS算法.

4.共軛梯度法(Conjugate Gradient)

共軛梯度法是介于最速下降法與牛頓法之間的一個(gè)方法,它僅需利用一階導(dǎo)數(shù)信息,但克服了最速下降法收斂慢的缺點(diǎn),又避免了牛頓法計(jì)算海森矩陣并求逆的缺點(diǎn).共軛梯度法不僅是解決大型線性方程組最有用的方法之一,也是解大型非線性最優(yōu)化最有效的算法之一.

5.拉格朗日法

參考SVM里的講解機(jī)器學(xué)習(xí)-SVM

6.動(dòng)量優(yōu)化法(Momentum)

動(dòng)量優(yōu)化法主要是在SGD的基礎(chǔ)上,加入了歷史的梯度更新信息或者說是加入了速度更新.SGD雖然是很流行的優(yōu)化算法,但是其學(xué)習(xí)過程很慢,因?yàn)榭偸且酝瑯拥牟介L沿著梯度下降的方向.所以動(dòng)量是為了加速學(xué)習(xí)的方法.

圖4

其中第一行的減號(hào)部分是計(jì)算當(dāng)前的梯度,第一行是根據(jù)梯度更新速度v,而α是新引進(jìn)的參數(shù),在實(shí)踐中,α的一般取值為 0.5,0.9 和 0.99.和學(xué)習(xí)率\varepsilon 一樣,α 也會(huì)隨著時(shí)間不斷調(diào)整.一般初始值是一個(gè)較小的值,隨后會(huì)慢慢變大.

7.Nesterov加速梯度(NAG, Nesterov accelerated gradient)

NAG是在動(dòng)量優(yōu)化算法的基礎(chǔ)上又進(jìn)行了改進(jìn).根據(jù)下圖可以看出,Nesterov 動(dòng)量和標(biāo)準(zhǔn)動(dòng)量之間的區(qū)別體現(xiàn)在梯度計(jì)算上, Nesterov 動(dòng)量中,梯度計(jì)算在施加當(dāng)前速度之后.因此,Nesterov 動(dòng)量可以解釋為往標(biāo)準(zhǔn)動(dòng)量方法中添加了一個(gè)校正因子

圖5

8.AdaGrad算法

AdaGrad算法,自適應(yīng)優(yōu)化算法的一種,獨(dú)立地適應(yīng)所有模型參數(shù)的學(xué)習(xí)率,縮放每個(gè)參數(shù)反比于其所有梯度歷史平均值總和的平方根.具有代價(jià)函數(shù)最大梯度的參數(shù)相應(yīng)地有個(gè)快速下降的學(xué)習(xí)率,而具有小梯度的參數(shù)在學(xué)習(xí)率上有相對(duì)較小的下降.通俗一點(diǎn)的講,就是根據(jù)實(shí)際情況更改學(xué)習(xí)率,比如模型快要收斂的時(shí)候,學(xué)習(xí)率步長就會(huì)小一點(diǎn),防止跳出最優(yōu)解.

圖6

其中g(shù)是梯度,第一行的分母是計(jì)算累計(jì)梯度的平方根,\varepsilon 是為了防止分母為0加上的極小常數(shù)項(xiàng),α是學(xué)習(xí)率.

Adagrad的主要優(yōu)點(diǎn)是不需要人為的調(diào)節(jié)學(xué)習(xí)率,它可以自動(dòng)調(diào)節(jié).但是依然需要設(shè)置一個(gè)初始的全局學(xué)習(xí)率.缺點(diǎn)是隨著迭代次數(shù)增多,學(xué)習(xí)率會(huì)越來越小,最終會(huì)趨近于0.

9.RMSProp算法

RMSProp修改 AdaGrad 以在非凸設(shè)定下效果更好,改變梯度積累為指數(shù)加權(quán)的移動(dòng)平均.AdaGrad旨在應(yīng)用于凸問題時(shí)快速收斂.

10.AdaDelta算法

11.Adam算法

Adam是Momentum和RMSprop的結(jié)合體,也就是帶動(dòng)量的自適應(yīng)優(yōu)化算法.

12.Nadam算法

13.模擬退火算法

14.蟻群算法

15.遺傳算法

總結(jié):

動(dòng)量是為了加快學(xué)習(xí)速度,而自適應(yīng)是為了加快收斂速度,注意學(xué)習(xí)速度快不一定收斂速度就快,比如步長大學(xué)習(xí)速度快,但是很容易跳出極值點(diǎn),在極值點(diǎn)附近波動(dòng),很難達(dá)到收斂.

未完待定....

參考:

《統(tǒng)計(jì)學(xué)習(xí)方法》? 李航? ? 著

《深度學(xué)習(xí)》? 花書

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末而姐,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子划咐,更是在濱河造成了極大的恐慌拴念,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,907評(píng)論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件褐缠,死亡現(xiàn)場離奇詭異政鼠,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)队魏,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,987評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門公般,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人胡桨,你說我怎么就攤上這事官帘。” “怎么了昧谊?”我有些...
    開封第一講書人閱讀 164,298評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵刽虹,是天一觀的道長。 經(jīng)常有香客問我呢诬,道長涌哲,這世上最難降的妖魔是什么胖缤? 我笑而不...
    開封第一講書人閱讀 58,586評(píng)論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮阀圾,結(jié)果婚禮上草姻,老公的妹妹穿的比我還像新娘。我一直安慰自己稍刀,他們只是感情好撩独,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,633評(píng)論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著账月,像睡著了一般综膀。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上局齿,一...
    開封第一講書人閱讀 51,488評(píng)論 1 302
  • 那天剧劝,我揣著相機(jī)與錄音,去河邊找鬼抓歼。 笑死讥此,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的谣妻。 我是一名探鬼主播萄喳,決...
    沈念sama閱讀 40,275評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢(mèng)啊……” “哼蹋半!你這毒婦竟也來了他巨?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,176評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤减江,失蹤者是張志新(化名)和其女友劉穎染突,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體辈灼,經(jīng)...
    沈念sama閱讀 45,619評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡份企,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,819評(píng)論 3 336
  • 正文 我和宋清朗相戀三年涩赢,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了傅蹂。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,932評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡显熏,死狀恐怖榕莺,靈堂內(nèi)的尸體忽然破棺而出俐芯,到底是詐尸還是另有隱情,我是刑警寧澤钉鸯,帶...
    沈念sama閱讀 35,655評(píng)論 5 346
  • 正文 年R本政府宣布,位于F島的核電站邮辽,受9級(jí)特大地震影響唠雕,放射性物質(zhì)發(fā)生泄漏贸营。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,265評(píng)論 3 329
  • 文/蒙蒙 一岩睁、第九天 我趴在偏房一處隱蔽的房頂上張望钞脂。 院中可真熱鬧,春花似錦捕儒、人聲如沸冰啃。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,871評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽阎毅。三九已至,卻和暖如春点弯,著一層夾襖步出監(jiān)牢的瞬間扇调,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,994評(píng)論 1 269
  • 我被黑心中介騙來泰國打工抢肛, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留狼钮,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,095評(píng)論 3 370
  • 正文 我出身青樓捡絮,卻偏偏與公主長得像熬芜,于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子福稳,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,884評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容