Author: Frank
在機器學習領域中，梯度下降法和牛頓下降法是兩個非常有分量的方法。兩者在本質上都是為了尋找極值點的位置，但是牛頓下降法的收斂速度更快。下面以單變量函數為例來進行基本的解釋。
牛頓下降法的遞推公式：
梯度下降算法的遞推公式：
xn+1=xn−μ∗f′(xn)
方法比較：
一般稱 梯度下降法用平面去拟合目前的局部曲面，牛頓法用二次曲面來拟合。下圖中紅色的收斂軌迹代表牛頓法，另一條為梯度下降法。
原理闡釋：
梯度下降法：
一階泰勒展式如下所示：
f(x+Δx)≈f(x)+f′(x)∗Δx 在通過疊代尋找極小值點過程中，就是尋找Δx，使得疊代之後的點x+Δx對應的f(x+Δx)<f(x)。 由上式可知，隻需要 f′(x)∗Δx<0即可。進而可令： 簡單的方法就是： Δx=−f′(x)Δx=−f′(x)
這樣上式就變為
f(x+Δx)=f(x)−f′(x)∗f′(x)
泰勒展式隻在局部成立，Δx不能太大，但是取Δx=−f′(x) 有可能太大，進而需要加個小的修正的因子，上式就變為：
Δx=−μ∗f′(x)Δx=−μ∗f′(x)
最終得到公式：
xn+1=xn−μ∗f′(xn)xn+1=xn−μ∗f′(xn)
這就是為什麼說梯度下降算法是用平面拟合函數的局部曲面。
牛頓下降法：
二階泰勒展式如下所示：
f(x+Δx)≈f(x)+f′(x)Δx+1/2∗f′′(x)∗Δx2
同樣希望疊代之後的點x+Δx對應的f(x+Δx)<f(x)。那麼将左式看成是△x的函數，當取合适的△x值時，左邊的式子達到極小值，此時導數為0，上式對Δx求導數，得：
0=f′(x)+f′′(x)∗Δx0=f′(x)+f″(x)∗Δx
此時可得到公式：
xn+1=xn−f′(xn)/f′′(xn)xn+1=xn−f′(xn)/f″(xn)
是以說牛頓下降法是用二次曲面來拟合函數的局部曲面。
兩種方法的關系：
關于梯度下降算法，其中最重要的就是要确定步長μ，它的值嚴重的影響了梯度下降算法的表現。
接下來考慮如下公式： （疊代後x+Δx處的導數為零時，對應最理想的情況）
f′(x+Δx)=f′(x)+f′′(x)∗Δxf′(x+Δx)=f′(x)+f″(x)∗Δx
和
Δx=−μ∗f′(x)Δx=−μ∗f′(x)
結合兩個式子，得到：
f′(x+Δx)=f′(x)−μ∗f′′(x)∗f′(x)f′(x+Δx)=f′(x)−μ∗f″(x)∗f′(x)
令左邊的式子為0，得到：
μ=1/f′′(x)μ=1/f″(x)
由此可見牛頓下降法是梯度下降法的最優情況，是以牛頓下降法的收斂的速度必然更快。
牛頓法同時考慮了目标函數的一、二階偏導數，考慮了梯度變化趨勢，因而能更合适的确定搜尋方向加快收斂，但牛頓法也存在以下缺點：
1、對目标函數有嚴格要求，必須有連續的一、二階偏導數，海森矩陣必須正定；
2、計算量大，除梯度外，還需計算二階偏導矩陣及其逆矩陣。
--------------------------------
梯度法從初始點的領域開始判斷，用目标函數的一階偏導、以負梯度方向作為搜尋方向，在局部進行下降，隻考慮目标函數在疊代點的局部性質，然後步步逼近極值，往往是走之字型的。
牛頓法在二階導數的作用下，從函數的凸性出發，直接搜尋怎樣到達極值點，也就是說在選擇方向時，不僅考慮目前坡度是否夠大，還會考慮你走了一步之後，坡度是否會變得更大。從收斂速度來看，梯度下降是線性收斂，牛頓法是超線性的，至少二階收斂。
多變量函數需要用到Hessian matrix, 原理相同，可以參考：點選打開連結