開篇廢話

優(yōu)化算法幾乎是絕大部分機(jī)器學(xué)習(xí)模型訓(xùn)練的必要算法番宁，最近參加一些大廠的筆試优幸，發(fā)現(xiàn)優(yōu)化算法是基礎(chǔ)考點(diǎn)颓帝，本文著重介紹幾種常用的優(yōu)化算法响疚，同時(shí)整理一些面試、筆試題以供大家參考灸促，以后相關(guān)的博客都會(huì)以基礎(chǔ)概念和面試試題兩部分呈現(xiàn)。當(dāng)然這些博客（包括已發(fā)表的）也會(huì)持續(xù)更新

正式內(nèi)容

優(yōu)化算法基本可以分為兩類算法：一階算法和二階算法，一階算法主要以計(jì)算梯度為主尤勋，比如我們熟知的梯度下降，也叫最速下降法茵宪；二階算法主要以計(jì)算海塞矩陣為主最冰。

1、梯度下降

梯度下降法是最早最簡單稀火，也是最為常用的最優(yōu)化方法暖哨。梯度下降法實(shí)現(xiàn)簡單，當(dāng)目標(biāo)函數(shù)是凸函數(shù)時(shí)凰狞，梯度下降法的解是全局解篇裁。一般情況下沛慢，其解不保證是全局最優(yōu)解，梯度下降法的速度也未必是最快的达布。梯度下降法的優(yōu)化思想是用當(dāng)前位置負(fù)梯度方向作為搜索方向团甲，因?yàn)樵摲较驗(yàn)楫?dāng)前位置的最快下降方向，所以也被稱為是”最速下降法“黍聂。最速下降法越接近目標(biāo)值躺苦，步長越小，前進(jìn)越慢产还。梯度下降法的搜索迭代示意圖如下圖所示：

梯度下降法的缺點(diǎn)：

（1）靠近極小值時(shí)收斂速度減慢圾另，如下圖所示；

（2）直線搜索時(shí)可能會(huì)產(chǎn)生一些問題雕沉；

（3）可能會(huì)“之字形”地下降集乔。

從上圖可以看出，梯度下降法在接近最優(yōu)解的區(qū)域收斂速度明顯變慢坡椒，利用梯度下降法求解需要很多次的迭代扰路。

在機(jī)器學(xué)習(xí)中，基于基本的梯度下降法發(fā)展了兩種梯度下降方法倔叼，分別為隨機(jī)梯度下降法和批量梯度下降法汗唱。

比如對一個(gè)線性回歸（Linear Logistics）模型，假設(shè)下面的h(x)是要擬合的函數(shù)丈攒，J(theta)為損失函數(shù)哩罪，theta是參數(shù)，要迭代求解的值巡验，theta求解出來了那最終要擬合的函數(shù)h(theta)就出來了际插。其中m是訓(xùn)練集的樣本個(gè)數(shù)，n是特征的個(gè)數(shù)显设。
比如對一個(gè)線性回歸（Linear Logistics）模型框弛，假設(shè)下面的h(x)是要擬合的函數(shù)，J(theta)為損失函數(shù)捕捂，theta是參數(shù)瑟枫，要迭代求解的值，theta求解出來了那最終要擬合的函數(shù)h(theta)就出來了指攒。其中m是訓(xùn)練集的樣本個(gè)數(shù)慷妙，n是特征的個(gè)數(shù)。

1）批量梯度下降法（Batch Gradient Descent允悦，BGD）

（1）將J(theta)對theta求偏導(dǎo)膝擂，得到每個(gè)theta對應(yīng)的的梯度：

（2）由于是要最小化風(fēng)險(xiǎn)函數(shù)，所以按每個(gè)參數(shù)theta的梯度負(fù)方向，來更新每個(gè)theta：

對于批量梯度下降法姚淆，樣本個(gè)數(shù)m孕蝉，x為n維向量，一次迭代需要把m個(gè)樣本全部帶入計(jì)算腌逢，迭代一次計(jì)算量為m*n^2降淮。

2）隨機(jī)梯度下降（Stochastic Gradient Descent，SGD）

（1）上面的風(fēng)險(xiǎn)函數(shù)可以寫成如下這種形式搏讶，損失函數(shù)對應(yīng)的是訓(xùn)練集中每個(gè)樣本的粒度佳鳖，而上面批量梯度下降對應(yīng)的是所有的訓(xùn)練樣本：

（2）每個(gè)樣本的損失函數(shù)，對theta求偏導(dǎo)得到對應(yīng)梯度媒惕，來更新theta：

（3）隨機(jī)梯度下降是通過每個(gè)樣本來迭代更新一次系吩，如果樣本量很大的情況（例如幾十萬），那么可能只用其中幾萬條或者幾千條的樣本妒蔚，就已經(jīng)將theta迭代到最優(yōu)解了穿挨，對比上面的批量梯度下降，迭代一次需要用到十幾萬訓(xùn)練樣本肴盏，一次迭代不可能最優(yōu)科盛，如果迭代10次的話就需要遍歷訓(xùn)練樣本10次。但是菜皂，SGD伴隨的一個(gè)問題是噪音較BGD要多土涝，使得SGD并不是每次迭代都向著整體最優(yōu)化方向。

隨機(jī)梯度下降每次迭代只使用一個(gè)樣本幌墓，迭代一次計(jì)算量為n^2但壮，當(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)練樣本情況。

PS: 講完了梯度下降前方，下面讓我們聊一聊深度學(xué)習(xí)中的一些優(yōu)化算法狈醉，它們很大程度都在改進(jìn)梯度下降的算法

SGD缺點(diǎn)：（正因?yàn)橛羞@些缺點(diǎn)才讓這么多大神發(fā)展出了后續(xù)的各種算法）

此處的SGD指mini-batch gradient descent（小批量梯度下降），可以解決高方差的參數(shù)更新和不穩(wěn)定收斂的問題惠险。單個(gè)樣本的SGD會(huì)造成參數(shù)比較劇烈的波動(dòng)苗傅，關(guān)于batch gradient descent, stochastic gradient descent, 以及 mini-batch gradient descent的具體區(qū)別就不細(xì)說了。現(xiàn)在的SGD一般都指mini-batch gradient descent班巩。

SGD就是每一次迭代計(jì)算mini-batch的梯度渣慕，然后對參數(shù)進(jìn)行更新，是最常見的優(yōu)化方法了抱慌。

這里的圖片中的符號作為參考摇庙，方法眾多，容易產(chǎn)生公式的混淆遥缕，f=損失函數(shù)

SGD完全依賴于當(dāng)前batch的梯度卫袒，所以η可理解為允許當(dāng)前batch的梯度多大程度影響參數(shù)更新

缺點(diǎn)

選擇合適的learning rate比較困難
對所有的參數(shù)更新使用同樣的learning rate。對于稀疏數(shù)據(jù)或者特征单匣，有時(shí)我們可能想更新快一些對于不經(jīng)常出現(xiàn)的特征夕凝，對于常出現(xiàn)的特征更新慢一些，這時(shí)候SGD就不太能滿足要求了
SGD容易收斂到局部最優(yōu)户秤，在某些情況下可能被困在鞍點(diǎn)【但是在合適的初始化和學(xué)習(xí)率設(shè)置下码秉，鞍點(diǎn)的影響其實(shí)沒這么大】

2、學(xué)習(xí)率改進(jìn)的一些優(yōu)化算法

1）Adagrad

Adagrad其實(shí)是對學(xué)習(xí)率進(jìn)行了一個(gè)約束鸡号。

也有人使用之前的梯度平方和做約束转砖，思想是大同小異

特點(diǎn)：
前期G（G是由g累加起來的，這里是指第一種定義）
較小的時(shí)候鲸伴， regularizer較大府蔗，能夠放大梯度
后期G
較大的時(shí)候，regularizer較小汞窗，能夠約束梯度適合處理稀疏梯度

缺點(diǎn)：
由公式可以看出姓赤，仍依賴于人工設(shè)置一個(gè)全局學(xué)習(xí)率η，設(shè)置過大的話仲吏，會(huì)使regularizer過于敏感不铆，對梯度的調(diào)節(jié)太大中后期蝌焚，分母上梯度平方的累加將會(huì)越來越大，使gradient→0誓斥，使得訓(xùn)練提前結(jié)束

3）RMSprop

3只洒、關(guān)于梯度本身的一些改進(jìn)

1）Momentum

SGD方法的一個(gè)缺點(diǎn)是其更新方向完全依賴于當(dāng)前batch計(jì)算出的梯度，因而十分不穩(wěn)定劳坑。Momentum算法借用了物理中的動(dòng)量概念毕谴，它模擬的是物體運(yùn)動(dòng)時(shí)的慣性，即更新的時(shí)候在一定程度上保留之前更新的方向泡垃，同時(shí)利用當(dāng)前batch的梯度微調(diào)最終的更新方向析珊。這樣一來羡鸥，可以在一定程度上增加穩(wěn)定性蔑穴，從而學(xué)習(xí)地更快，并且還有一定擺脫局部最優(yōu)的能力：

Momentum算法會(huì)觀察歷史梯度v_(t-1)惧浴，若當(dāng)前梯度的方向與歷史梯度一致（表明當(dāng)前樣本不太可能為異常點(diǎn)）存和，則會(huì)增強(qiáng)這個(gè)方向的梯度，若當(dāng)前梯度與歷史梯方向不一致衷旅，則梯度會(huì)衰減捐腿。一種形象的解釋是：我們把一個(gè)球推下山，球在下坡時(shí)積聚動(dòng)量柿顶，在途中變得越來越快茄袖，γ可視為空氣阻力，若球的方向發(fā)生變化嘁锯，則動(dòng)量會(huì)衰減宪祥。Momentum可以使網(wǎng)絡(luò)能更優(yōu)和更穩(wěn)定的收斂；減少振蕩過程家乘。

給大家一個(gè)直觀的感受蝗羊，前面梯度會(huì)影響后面梯度的方向和大小，這邊的圖就是提了前面一個(gè)梯度的影響仁锯，其實(shí)影響這一時(shí)刻的梯度是前面所有梯度的指數(shù)平均梯度耀找。

紅色代表是我們的momentum，黑色代表的是我們的sgd业崖；

（未完待續(xù)……）

20170806000414235.gif

20170806001149509.gif