[深度学习] 牛顿法

牛顿法

牛顿法是一种二阶梯度方法。与一阶梯度算法相比，二阶梯度方法使用了二阶导数进行了优化。

具体解释如下：

1. 在函数上随便找个点，做这个点的切线，求出切线的跟（切线和x轴交点）
   
2. 从这个切线的跟出发，做一条垂线与函数相交，继续方才的工作，此时我们发现B比A点更接近跟
   
3. 继续进行上述操作，直到迭代收敛
   

公式：
$f(x) = f(x_0)+f(x_0)'(x-x_0) + \frac{1}{2}f(x_0)''(x-x_0)^2$f(x)=f(x0​)+f(x0​)′(x−x0​)+21​f(x0​)′′(x−x0​)2
现对f(x)求导，并令导数为0
$f(x)' = f(x_0)'+f(x_0)''(x-x_0)$f(x)′=f(x0​)′+f(x0​)′′(x−x0​)
$x = x_0-\frac{f(x_0)'}{f(x_0)''}$x=x0​−f(x0​)′′f(x0​)′​

在深度学习的实际应用时，使用了Hessian矩阵，具体公式为：
$J(\theta)=J(\theta_0)+(\theta - \theta_0)^T \nabla_{\theta}J(\theta_0)+\frac{1}{2}(\theta-\theta_0)^TH(\theta - \theta_0)$J(θ)=J(θ0​)+(θ−θ0​)T∇θ​J(θ0​)+21​(θ−θ0​)TH(θ−θ0​)
其中H是J相对于$\theta$θ的Hessian矩阵在$\theta_0$θ0​处的估计，如果我们要求这个函数临界点，将得到牛顿参数更新规则：
$\theta^*=\theta_0-H^{-1}\nabla_{\theta}J(\theta_0)$θ∗=θ0​−H−1∇θ​J(θ0​)
因此对于局部的二次函数，用$H^{-1}$H−1重新调整梯度，牛顿法会直接跳到极小值，如果目标函数是非二次函数（有高阶项），该更新是迭代的。

需要注意的是，对于非二次的表面，需要Hessian矩阵保持正定，牛顿法就能迭代的使用。否则使用会出现问题。
目前，使用正则化Hessian矩阵可以避免上述问题，详细之后再介绍。

除了上述问题，牛顿法用于大型神经网络还受限制于显著的计算负担。Hessian矩阵中元素数目是参数数量的平方，因此，如果参数数目为k，牛顿法需要计算k*k矩阵的逆，计算复杂度$O(k^3)$O(k3)，并且由于参数每次都会改变，因此每次训练都要计算Hessian矩阵的逆。所以，只有参数很少的网络才能在实际中用牛顿法训练。

总结

从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）

根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

牛顿法的优缺点总结：

优点：二阶收敛，收敛速度快；

缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。

参考

https://www.zhihu.com/question/20690553