牛頓迭代法的可視化詳解

來源：DeepHub IMBA
本文約1800字，建議閱讀10分鐘
本文利用可視化方法，為你直觀地解析牛頓迭代法。

牛頓迭代法（Newton's method）又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method），它是牛頓在17世紀提出的一種在實數(shù)域和復(fù)數(shù)域上近似求解方程的方法。

以 Isaac Newton 和 Joseph Raphson 命名的 Newton-Raphson 方法在設(shè)計上是一種求根算法，這意味著它的目標是找到函數(shù) f(x)=0 的值 x。在幾何上可以將其視為 x 的值，這時函數(shù)與 x 軸相交。

Newton-Raphson 算法也可以用于一些簡單的事情，例如在給定之前的連續(xù)評估成績的情況下，找出預(yù)測需要在期末考試中獲得 A 的分數(shù)。其實如果你曾經(jīng)在 Microsoft Excel 中使用過求解器函數(shù)，那么就使用過像 Newton-Raphson 這樣的求根算法。另外一個復(fù)雜用例是使用 Black-Scholes 公式反向求解金融期權(quán)合約的隱含波動率。

Newton-Raphson公式

雖然公式本身非常簡單，但如果想知道它實際上在做什么就需要仔細查看。

首先，讓我們回顧一下整體方法：

1. 初步猜測根可能在哪里？

2. 應(yīng)用 Newton-Raphson 公式獲得更新后的猜測，該猜測將比初始猜測更接近根。

3. 重復(fù)步驟 2，直到新的猜測足夠接近真實值。

這樣就足夠了嗎？Newton-Raphson 方法給出了根的近似值，盡管通常它對于任何合理的應(yīng)用都足夠接近！但是我們?nèi)绾味x足夠接近？什么時候停止迭代？

一般情況下Newton-Raphson 方法有兩種處理何時停止的方法。1、如果猜測從一個步驟到下一步的變化不超過閾值，例如 0.00001，那么算法將停止并確認最新的猜測足夠接近。2、如果我們達到一定數(shù)量的猜測但仍未達到閾值，那么我們就放棄繼續(xù)猜測。

從公式中我們可以看到，每一個新的猜測都是我們之前的猜測被某個神秘的數(shù)量調(diào)整了??。如果我們通過一個例子來可視化這個過程，它很快就會清楚發(fā)生了什么!

作為一個例子，讓我們考慮上面的函數(shù)，并做一個 x=10 的初始猜測（注意這里實際的根在 x=4）。Newton-Raphson 算法的前幾個猜測在下面的 GIF 中可視化??

我們最初的猜測是 x=10。為了計算我們的下一個猜測，我們需要評估函數(shù)本身及其在 x=10 處的導(dǎo)數(shù)。在 10 處求值的函數(shù)的導(dǎo)數(shù)只是簡單地給出了該點切線曲線的斜率。該切線在 GIF 中繪制為 Tangent 0。

看下一個猜測相對于前一個切線出現(xiàn)的位置，你注意到什么了嗎？下一個猜測出現(xiàn)在前一個切線與 x 軸相交的位置。這就是 Newton-Raphson 方法的亮點！

事實上， f(x)/f'(x) 只是給出了我們當前猜測與切線穿過 x 軸的點之間的距離（在 x 方向上）。正是這個距離告訴我們每次更新的猜測是多少，正如我們在 GIF 中看到的那樣，隨著我們接近根本身，更新變得越來越小。

如果函數(shù)無法手動微分怎么辦？

上面的例子中是一個很容易用手微分的函數(shù)，這意味著我們可以毫無困難地計算 f'(x)。然而，實際情況可能并非如此，并且有一些有用的技巧可以在不需要知道其解析解的情況下逼近導(dǎo)數(shù)。

這些導(dǎo)數(shù)逼近方法超出了本文的范圍，可以查找有關(guān)有限差分方法的更多信息。

問題

敏銳的讀者可能已經(jīng)從上面的示例中發(fā)現(xiàn)了一個問題，示例函數(shù)有兩個根（x=-2 和 x=4），Newton-Raphson 方法也只能識別一個根。牛頓迭代會根據(jù)初值的選擇向某個值收斂，所以只能求出一個值來。如果需要別的值，是要把當前求的根帶入后將方程降次，然后求第二個根。這當然是一個問題，并不是這種方法的唯一缺點：

• 牛頓法是一種迭代算法，每一步都需要求解目標函數(shù)的Hessian矩陣的逆矩陣，計算比較復(fù)雜。
• 牛頓法收斂速度為二階，對于正定二次函數(shù)一步迭代即達最優(yōu)解。
• 牛頓法是局部收斂的，當初始點選擇不當時，往往導(dǎo)致不收斂；
• 二階Hessian矩陣必須可逆，否則算法進行困難。

與梯度下降法的對比

梯度下降法和牛頓法都是迭代求解，不過梯度下降法是梯度求解，而牛頓法/擬牛頓法是用二階的Hessian矩陣的逆矩陣或偽逆矩陣求解。從本質(zhì)上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部，梯度下降法每次只從你當前所處位置選一個坡度最大的方向走一步，牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之后，坡度是否會變得更大。可以說牛頓法比梯度下降法看得更遠一點，能更快地走到最底部。（牛頓法目光更加長遠，所以少走彎路；相對而言，梯度下降法只考慮了局部的最優(yōu)，沒有全局思想）。

那為什么不用牛頓法替代梯度下降呢？

• 牛頓法使用的是目標函數(shù)的二階導(dǎo)數(shù)，在高維情況下這個矩陣非常大，計算和存儲都是問題。
• 在小批量的情況下，牛頓法對于二階導(dǎo)數(shù)的估計噪聲太大。
• 目標函數(shù)非凸的時候，牛頓法容易受到鞍點或者最大值點的吸引。

實際上目前深度神經(jīng)網(wǎng)絡(luò)算法的收斂性本身就是沒有很好的理論保證的，用深度神經(jīng)網(wǎng)絡(luò)只是因為它在實際應(yīng)用上有較好的效果，但在深度神經(jīng)網(wǎng)絡(luò)上用梯度下降法是不是能收斂，收斂到的是不是全局最優(yōu)點目前還都是無法確認的。并且二階方法可以獲得更高精度的解，但是對于神經(jīng)網(wǎng)絡(luò)這種參數(shù)精度要求不高的情況下反而成了問題，深層模型下如果參數(shù)精度太高，模型的泛化性就會降低，反而會提高模型過擬合的風(fēng)險。

作者：Rian Dolphin

編輯：黃繼彥