关于人工智能:牛顿迭代法的可视化详解

牛顿迭代法（Newton‘s method）又称为牛顿 - 拉夫逊（拉弗森）办法（Newton-Raphson method），它是牛顿在 17 世纪提出的一种在实数域和复数域上近似求解方程的办法。

以 Isaac Newton 和 Joseph Raphson 命名的 Newton-Raphson 办法在设计上是一种求根算法，这意味着它的指标是找到函数 f(x)=0 的值 x。在几何上能够将其视为 x 的值，这时函数与 x 轴相交。

Newton-Raphson 算法也能够用于一些简略的事件，例如在给定之前的间断评估问题的状况下，找出预测须要在期末考试中取得 A 的分数。其实如果你已经在 Microsoft Excel 中应用过求解器函数，那么就应用过像 Newton-Raphson 这样的求根算法。另外一个简单用例是应用 Black-Scholes 公式反向求解金融期权合约的隐含稳定率。

Newton-Raphson 公式

尽管公式自身非常简单，但如果想晓得它实际上在做什么就须要认真查看。

首先，让咱们回顾一下整体办法：

1、初步猜想根可能在哪里

2、利用 Newton-Raphson 公式取得更新后的猜想，该猜想将比初始猜想更靠近根

3、反复步骤 2，直到新的猜想足够靠近实在值。

这样就足够了吗？Newton-Raphson 办法给出了根的近似值，只管通常它对于任何正当的利用都足够靠近！然而咱们如何定义足够靠近？什么时候进行迭代？

个别状况下 Newton-Raphson 办法有两种解决何时进行的办法。1、如果猜想从一个步骤到下一步的变动不超过阈值，例如 0.00001，那么算法将进行并确认最新的猜想足够靠近。2、如果咱们达到肯定数量的猜想但仍未达到阈值，那么咱们就放弃持续猜想。

从公式中咱们能够看到，每一个新的猜想都是咱们之前的猜想被某个神秘的数量调整了🔮。如果咱们通过一个例子来可视化这个过程，它很快就会分明产生了什么!

作为一个例子，让咱们思考下面的函数，并做一个 x=10 的初始猜想（留神这里理论的根在 x=4）。Newton-Raphson 算法的前几个猜想在上面的 GIF 中可视化👇

咱们最后的猜想是 x=10。为了计算咱们的下一个猜想，咱们须要评估函数自身及其在 x=10 处的导数。在 10 处求值的函数的导数只是简略地给出了该点切线曲线的斜率。该切线在 GIF 中绘制为 Tangent 0。

看下一个猜想绝对于前一个切线呈现的地位，你留神到什么了吗？下一个猜想呈现在前一个切线与 x 轴相交的地位。这就是 Newton-Raphson 办法的亮点！

事实上，f(x)/f'(x) 只是给出了咱们以后猜想与切线穿过 x 轴的点之间的间隔（在 x 方向上）。正是这个间隔通知咱们每次更新的猜想是多少，正如咱们在 GIF 中看到的那样，随着咱们靠近基本身，更新变得越来越小。

如果函数无奈手动微分怎么办？

下面的例子中是一个很容易用手微分的函数，这意味着咱们能够毫无艰难地计算 f'(x)。然而，理论状况可能并非如此，并且有一些有用的技巧能够在不须要晓得其解析解的状况下迫近导数。

这些导数迫近办法超出了本文的范畴，能够查找无关无限差分办法的更多信息。

问题

敏锐的读者可能曾经从下面的示例中发现了一个问题，示例函数有两个根（x=-2 和 x=4），Newton-Raphson 办法也只能辨认一个根。牛顿迭代会依据初值的抉择向某个值收敛，所以只能求出一个值来。如果须要别的值，是要把以后求的根带入后将方程降次，而后求第二个根。这当然是一个问题，并不是这种办法的惟一毛病：

• 牛顿法是一种迭代算法，每一步都须要求解指标函数的 Hessian 矩阵的逆矩阵，计算比较复杂。
• 牛顿法收敛速度为二阶，对于正定二次函数一步迭代即达最优解。
• 牛顿法是局部收敛的，当初始点抉择不过后，往往导致不收敛；
• 二阶 Hessian 矩阵必须可逆，否则算法进行艰难。

与梯度降落法的比照

梯度降落法和牛顿法都是迭代求解，不过梯度降落法是梯度求解，而牛顿法 / 拟牛顿法是用二阶的 Hessian 矩阵的逆矩阵或伪逆矩阵求解。从实质下来看，牛顿法是二阶收敛，梯度降落是一阶收敛，所以牛顿法就更快。如果更艰深地说的话，比方你想找一条最短的门路走到一个盆地的最底部，梯度降落法每次只从你以后所处地位选一个坡度最大的方向走一步，牛顿法在抉择方向时，不仅会思考坡度是否够大，还会思考你走了一步之后，坡度是否会变得更大。能够说牛顿法比梯度降落法看得更远一点，能更快地走到最底部。（牛顿法眼光更加久远，所以少走弯路；相对而言，梯度降落法只思考了部分的最优，没有全局思维）。

那为什么不必牛顿法代替梯度降落呢？

• 牛顿法应用的是指标函数的二阶导数，在高维状况下这个矩阵十分大，计算和存储都是问题。
• 在小批量的状况下，牛顿法对于二阶导数的预计噪声太大。
• 指标函数非凸的时候，牛顿法容易受到鞍点或者最大值点的吸引

实际上目前深度神经网络算法的收敛性自身就是没有很好的实践保障的，用深度神经网络只是因为它在理论利用上有较好的成果，但在深度神经网络上用梯度降落法是不是能收敛，收敛到的是不是全局最长处目前还都是无奈确认的。并且二阶办法能够取得更高精度的解，然而对于神经网络这种参数精度要求不高的状况下反而成了问题，深层模型下如果参数精度太高，模型的泛化性就会升高，反而会进步模型过拟合的危险。

https://www.overfit.cn/post/37cdf43c67df46bbb1ac52418a4237ef

作者：Rian Dolphin