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