机器学习中的最优化方法（二）-牛顿法

机器学习 最优化方法 牛顿法

---

  牛顿法是一种在实数域和复数域上近似求解方程的方法。其使用函数$f (x)$的泰勒级数的前面几项来寻找方程$f(x)= 0$的根。牛顿法最大的特点就在于它的收敛速度很快。
  具体方法：
  选择一个接近函数 $f (x)$零点的 $x_0$，计算相应的$f (x_0)$ 和切线斜率，即$f ' (x_0)$（表示函数$f (x_0)$的导数）。然后计算穿过点$(x_0, f (x_0))$ 并且斜率为$f ' (x_0)$的直线和 $x$ 轴的交点的$x$坐标，也就是求如下方程的解：

$$xf ' (x_0)+f (x_0)-x_0f ' (x_0)=0$$
  因此，迭代公式为：
$$x_{n+1}=x_n-\frac{f(x_n)}{f ' (x_n)}$$
  由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：

牛顿法和梯度下降法的效率对比：

　　从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
　　根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。虽然其收敛速度很快，但它是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。