前言
學(xué)習(xí)機(jī)器學(xué)習(xí)一直是用梯度下降法的，對(duì)于牛頓下降法并沒(méi)有什么了解，但是小學(xué)期同學(xué)的一個(gè)項(xiàng)目用到了牛頓下降法，同時(shí)好多大神同學(xué)的夏令營(yíng)之旅問(wèn)到了牛頓下降法（我等弱雞瘋狂被刷。。。）所以就總結(jié)學(xué)習(xí)一下。
梯度下降法
梯度
梯度高等數(shù)學(xué)都學(xué)過(guò)，在向量微積分中，標(biāo)量場(chǎng)的梯度是一個(gè)向量場(chǎng)。標(biāo)量場(chǎng)中某一點(diǎn)上的梯度指向標(biāo)量場(chǎng)增長(zhǎng)最快的方向，梯度的長(zhǎng)度是這個(gè)最大的變化率。也就是梯度表示數(shù)值變化最快的方向，在一元情況下，梯度當(dāng)然就是斜率，或者導(dǎo)數(shù)。在多元的情況下梯度是這樣的：
其實(shí)就是計(jì)算了φ在三個(gè)方向上的微分，表示了在三個(gè)方向上的變化量。
梯度下降與推導(dǎo)
梯度下降法其實(shí)就是下面這個(gè)式子：
下一次函數(shù)的值為上一次的值在變化最大的方向上移動(dòng)μ*f'(xn)。我們知道變化最快可以變大也可以變小那么梯度下降為什么可以保證一定變小呢？
我們知道梯度方向增加最快，那么梯度方向的反方向是下降最快的，所以在梯度上加負(fù)號(hào)保證了一定是下降的。例如：f(x)=-3x 它的梯度就是導(dǎo)數(shù)-3，在負(fù)方向是增加的也就是x減小，函數(shù)值增大我們看到上面梯度下降的公式是針對(duì)自變量的，那么假設(shè)第一步我們處于x=1這個(gè)位置，那么下一步可能就在1-0.01*（-3）=1.03，x增大了，最后的函數(shù)值減小了，下降了。
牛頓下降法
牛頓下降法的遞推公式：
關(guān)于兩者的解釋?zhuān)?/h1>
下圖是兩種方法的圖示表示，紅色為牛頓下降法，綠色為梯度下降法，從圖中直觀的感覺(jué)是，紅色線(xiàn)短，下降速度快。因?yàn)榕ｎD下降法是用二次曲面去擬合當(dāng)前的局部曲面，而梯度下降法是用平面去擬合當(dāng)前的局部曲面，一般用二次曲面擬合的更好，所以一般牛頓算法收斂快。
為啥梯度下降是平面擬合而牛頓下降是二次曲線(xiàn)擬合呢？
解釋來(lái)源于博客：
http://blog.csdn.net/njucp/article/details/50488869
一階泰勒展式如下表示：
左式表示一個(gè)曲面，而右式相當(dāng)于用平面在x附近表示曲面，所以一階泰勒展式可以表示平面近似擬合曲面，主要的擬合部分是f'*Δx的部分。
我們的目的是使得左邊的值變小，那是不是應(yīng)該使得下面的式子變?yōu)樨?fù)值。
但是如何使得上式一定為負(fù)值，簡(jiǎn)單的方法就是：
這樣上式就變?yōu)?
但是不要忘了以上所有的一切只有在局部成立，也就是說(shuō)在小范圍才成立，那么下式就有很能太大 :
所以加個(gè)小的修正的因子，上式就變?yōu)椋?br>
得到最終的梯度下降公式。
平面擬合曲面是有于一階泰勒展開(kāi)。那么二次曲面擬合曲面的牛頓迭代很顯然就是二階泰勒展開(kāi)的結(jié)果了?？紤]一下二階泰勒：
同樣我們希望左式最小，那么將左式看成是△x的函數(shù)，當(dāng)取合適的△x值時(shí)，左邊的式子達(dá)到極小值，此時(shí)導(dǎo)數(shù)為0。因此上式對(duì)△x進(jìn)行求導(dǎo)數(shù)，得到以下公式：
所以有：
所以牛頓迭代法表示為：
為什么牛頓法更快
第一種解釋是，牛頓下降法利用了函數(shù)的更多的信息，能夠更好的擬合局部曲面，所以收斂的速度也會(huì)加快。
第二種是：
關(guān)于梯度下降算法，其中最重要的就是要確定步長(zhǎng)μ，它的值嚴(yán)重的影響了梯度下降算法的表現(xiàn)。
接下來(lái)考慮如下公式：
和
結(jié)合起來(lái)有：
令左邊的式子為0，得到：
由此可見(jiàn)牛頓下降法是梯度下降法的最優(yōu)情況，因此牛頓下降法的收斂的速度必然更快。
對(duì)于高維數(shù)據(jù)要計(jì)算Hessian 矩陣，關(guān)于Hessian 矩陣，很簡(jiǎn)單，自行百度吧。
為什么大多數(shù)機(jī)器學(xué)習(xí)算法是基于梯度下降的？
機(jī)器學(xué)習(xí)大多數(shù)都有著極高維度的特征以及極多的樣本，所以計(jì)算Hessian 矩陣需要的時(shí)間很長(zhǎng)，效率很低。
還有來(lái)自知乎大神的關(guān)于牛頓法的缺點(diǎn)和優(yōu)點(diǎn)：
https://www.zhihu.com/question/19723347/answer/28414541）
- 牛頓法起始點(diǎn)不能離局部極小點(diǎn)太遠(yuǎn)，否則很可能不會(huì)收斂。(考慮到二階擬合應(yīng)該很容易想象)，所以實(shí)際操作中會(huì)先使用別的方法，比如梯度下降法，使更新的點(diǎn)離最優(yōu)點(diǎn)比較近，再開(kāi)始用牛頓法。
- 牛頓法每次需要更新一個(gè)二階矩陣，當(dāng)維數(shù)增加的時(shí)候是非常耗內(nèi)存的，所以實(shí)際使用是會(huì)用擬牛頓法。
- 梯度下降法在非常靠近最優(yōu)點(diǎn)時(shí)會(huì)有震蕩，就是說(shuō)明明離的很近了，卻很難到達(dá)，因?yàn)榫€(xiàn)性的逼近非常容易一個(gè)方向過(guò)去就過(guò)了最優(yōu)點(diǎn)(因?yàn)橹荒苁秦?fù)梯度方向)。但牛頓法因?yàn)槭嵌问諗烤秃苋菀椎竭_(dá)了。
牛頓法最明顯快的特點(diǎn)是對(duì)于二階函數(shù)(考慮多元函數(shù)的話(huà)要在凸函數(shù)的情況下)，牛頓法能夠一步到達(dá)，非常有效。
多變量的牛頓下降法
來(lái)源于博客：
http://blog.csdn.net/itplus/article/details/21896453，我覺(jué)得寫(xiě)的很好。
關(guān)于隨機(jī)梯度下降和批量梯度下降
見(jiàn)我的下一篇文章吧2333！
