上一次我們討論了具有 Q-線性收斂性的普通的 gradient descent 方法，今天我們要介紹一種收斂速度更快的算法：Newton Method（或者叫 Newton’s Method）。

可能大家知道有兩個算法同時叫做牛頓法，一個是用迭代法來求方程的根的方法，另一個是 optimization 里的牛頓法，實際上這兩者是同一個方法，或者同一個思想。今天我們要講的是后者，但是由于前者比較簡單，并且有有趣的故事，所以我們還是從前者講起。故事開始于雷神之錘 III 競技場里的一段神秘的快速求平方根倒數的代碼：

float Q_rsqrt( float number )

{

long i;

float x2, y;

const float threehalfs = 1.5F;

x2 = number * 0.5F;

y = number;

i = * ( long * ) &y;

i = 0x5f3759df - ( i >> 1 );

y = * ( float * ) &i;

y = y * ( threehalfs - ( x2 * y * y ) );

// y = y * ( threehalfs - ( x2 * y * y ) );

return y;

}

據稱比直接計算要快了 4 倍。其中的兩次迭代（第二步迭代被注釋掉了）就是用的牛頓法來求解方程?，也就是??的根。牛頓法的思想其實很簡單，給定一個初始點?，使用在該點處的切線來近似函數，然后尋找切線的根作為一次迭代。比如對于這個例子，令?，給定初始點?，在該點處的導數是?，由此可以得到該處的切線為?，求解??得到

正是代碼中的迭代。當然代碼的重點其實不在這里，而在?0x5f3759df?這個奇怪的 magic number，用于得到一個好的初始點。這個神奇的數字到底是誰發現的，根據 wikipedia 上的說法似乎至今還沒有定論。xkcd 還為此畫了一條漫畫，諷刺說每次我們驚奇地發現工業界里不知道哪個無名人士寫出了?0x5f3759df之類的神奇數字，背后都有成千上萬的其他無名人士我們無從知曉，說不定他們中的某一個人已經解決了 P=NP 的問題，但是那人卻還在調某個自動打蛋器的代碼所以我們至今仍無知曉。:D

回到我們今天的話題，從這段代碼中我們可以看到兩點：

牛頓法收斂非常快，對于精度要求不是特別高的情況，比如上面的圖形學相關的計算中，甚至只用了一次計算迭代。

另一方面，初始值的選取非常重要，我們接下去將會看到，初始值選得不好有可能會直接導致算法不收斂。

軼事講完之后，正式回到我們的 optimization 的話題。回憶一下上一次我們提到迭代優化算法許多都可以理解為通過不動點法尋找??的根，如果我們套用剛才提到的牛頓法，可以在每一次迭代的時候對??進行一階近似來尋找其零點。注意到對 gradient??進行一階近似其實就是對原函數?進行二階近似，由此我們得到了 optimization 里的牛頓法。

具體來說，從初始點??開始迭代，每一次迭代，在當前位置對??進行二階近似，在??點處進行泰勒展開并丟掉二次以上的項，得到：

?是一個二次函數，直接令??可以解得：

(eq: 1)

這就是牛頓法的基本迭代步驟。這實際上是上一次介紹的 general 迭代框架的一個特殊情況：當??的時候。但是這個特殊的??的取法使得算法的收斂性有了質的飛越。具體來說，現在我們有了 Q-二次收斂性。一個數列??滿足 Q-二次收斂是指??且

雖然聽起來只有二次，但是實際上是非常非常快的，比如如下的數列

就是二次收斂的，,?,?，粗略地講，如果一個數列按 Q-二次收斂，那么沒一次迭代我們可以使得小數點后的精確位數翻一倍。當然牛頓法并不是萬金油，首先需要注意的一點是，牛頓法并不能總是保證收斂，當然，在上一次我們分析 gradient descent 的時候也是做了許多假設，不過牛頓法在這方面更加嬌貴：首先函數的性質要好，并且初始解必須在離最優解比較近的地方才能保證收斂，而這個鄰域可以是多大則依賴于一堆通常無法計算或估計的常數。

實際上，如果 Hessian 在當前的??處是不可逆的，那么?(eq: 1)?本身就是沒法計算的。如果 Hessian 是可逆的，并且是 (semi)definite 的話，則

也就是說牛頓方向和 gradient 的負方向呈銳角，是一個下降（或者非增）方向。但是如果 Hessian 不是 (semi)definite 的話，就無法保證這一點了。另外，所謂下降方向的意思只是說沿著該方向移動足夠小的步長可以保證函數是下降（非增）的，但是這里使用固定步長 1 卻不能保證這一點（但是步長 1 又是證明二次收斂性所需要的）。

因此有一種牛頓法的變種，叫做 Damped Newton Method，就是在計算出牛頓方向之后，再用 backtracking 的方式做一次 linesearch。Backtracking linesearch 比之前介紹的基于 Wolfe’s Condition 的 linesearch 要簡單，它有兩個參數??和?。簡而言之 backtrack linesearch 從初始步長 1 開始，每一次迭代將步長乘以?，直到滿足如下條件為止：

這里的??是 linesearch 的方向。我們從?(Boyd & Vandenberghe, 2004)?盜一張圖來說明一下。

由于??是下降方向，所以對于足夠小的?，我們有

所以 linesearch 可以保證停止，從圖中來看，實際上就是尋找??中的一個步長，?的大小決定了我們期望的下降量，比如極端情況??則是任何非增的步長都會接受。以下是 julia 代碼：

function linesearch{T}(p::OptimizationProblem, x::Vector{T},

d::Vector{T})

t = convert(T, 1)

fx = objval(p, x)

dfx = gradient(p, x)

while objval(p, x + t*d) > fx + alpha * t * dot(dfx, d)

t = beta * t

end

return t

end

增加了 linesearch 之后的 Damped Newton Method 有一個比較好的性質就是當迭代進入離最優解足夠近的一個收斂區域之后，linesearch 一定會返回默認步長 1，從而進入 pure Newton Method 的 Q-二次收斂的階段。具體細節和證明可以參考?(Boyd & Vandenberghe, 2004)?第 9 章的 Newton Method 一節。

這里我們給一個簡單的一維情況下的例子，最小化?，這是一個 convex 函數，其最小值在??處達到。這里我們給出 Newton Method、Damped Newton Method 和普通的 Gradient Descent 的結果。

大約在??這個區間內是該函數的 Newton 收斂區間?(這里 Gradient Descent 比 Newton Method 要收斂快，并不是違反了收斂性分析，因為收斂性分析是一個粗略的“階”的分析，一般需要在迭代步數很多的時候才能看出區別來，這里我們的初始點本身和最優值點已經非常接近了，各種算法都很容易就收斂到了最優點。)，可以看到當我們選取初始值為 1.09 之后 Newton Method 直接不收斂了。但是 Damped Newton Method 則表現良好，并且在第三個例子中初始點離最優解比較遠的情況，二次收斂的速度優勢就體現出來了。

接下來我們可以再看一個更加實際一點的例子，也就是我們上一次介紹過的 Logistic Regression 的情況。為了將牛頓法用在 Logistic Regression 上，我們需要求目標函數的 Hessian，為了方便起見我再把目標函數搬過來：

上一次我們已經求過其 gradient 為

接下來很容易算出?(好吧，其實我很不好意思說我自己算了好久……對于像我這樣向量二階導搞得不熟悉的同學可以在求導的時候先針對向量的每一個元素單獨求，也就是求出 Hessian 矩陣的每個元素?，將其形式寫出來再找矩陣形式的式子。)其 Hessian 矩陣為

然后直接套用我們剛才說的 Damped Newton Method，目標函數在 USPS 數據集上的收斂結果如圖所示，可以和上一次的 Gradient Descent + Wolfe Linesearch 進行對比。

可以看到 Newton Method 十來次迭代就收斂了。不過這里有一個細節需要注意，就是我們在上一次的例子中給出用 gradient descent 來優化 Logistic Regression 的目標函數的時候，直接丟掉了 regularizer ()，而這里則必須要加上 regularizer，因為否者計算出來的 Hessian 會接近 singular，在求逆（或者說解線性方程組）計算?(eq: 1)?的時候直接爆炸掉了，沒法收斂到一個好的結果。圖中的結果對應取??的情況。

實際上這里暴露出來的一個問題也確實是牛頓法在實際中經常碰到的一個問題：Hessian 矩陣 singular 或者是接近 singular 的情況。通常的做法是在對角線上加正數，在這里其實就對應于目標函數里的 regularizer?。上一次的 Gradient Descent 算法中我們也討論過，加 regularizer 可以減小 condition number，從而改善收斂速度。但是需要注意的是并不是 regularizer 加得越厲害越好。因為加 regularizer 的原因不僅是出于優化來考慮，而且還有 learning theory 方面的 generalization performance 方面的考慮，從后者的角度來說 regularizer （系數）的大小是有一個合適的值范圍的，太大太小都不好（實際中一般通過 cross validation 來選取 regularizer 系數）。因為我們的最終目的是做 learning 和 prediction，如果一切只是為了優化方便，那么只要把目標函數變成一個 constant function 之類的，那么任何優化算法都可以一步收斂，但是卻沒有什么用處。

除了加 regularizer 之外，解決 Newton Method 的 near-singular Hessian 問題的方法還有其他很多，比如并不精確計算 Hessian，而是用一個性質良好的正定矩陣去近似估計當前的 Hessian，這一類方法通常被稱為?Quasi-Newton Method，比如比較有名的?L-BFGS?算法，今天就不在這里細講了。

不過 Quasi-Newton Method 的更重要的 motivation 其實是 Newton Method 的另一個嚴重的弱點：計算量。雖然 Newton Method 收斂快，只需要很少次的迭代，但是每一步迭代的計算量卻比普通的 Gradient Descent 要大很多：Gradient Descent 只要計算一個??維 Gradient 向量即可，Newton Method 不僅要計算 Hessian 矩陣（?維），而且要對該矩陣求逆（或者是解線性方程組）——對于通常的 dense 矩陣，這是一個復雜度為??的操作。

對于所謂的 big data 問題，Newton Method 通常難以應用。比如剛才的 Logistic Regression 的例子，如果數據點的個數非常多，由于計算 Hessian 每次都要遍歷一遍所有數據并計算外積?，這會在每一次迭代都花掉很多時間。更嚴重的是，如果數據的維度非常高，且不說后面的求逆操作，即使 Hessian 矩陣本身的求解甚至存儲都會出現問題。有時候碰到的情況是連 Newton Method 迭代一次的計算量都承擔不起，所以在大規模機器學習或者 general 的大規模優化問題中，簡單的一階（只需要用到 gradient 信息）算法得到了更多的關注。以后我們還會看到，不僅是 Hessian，連 Gradient 向量的計算都非常 costly 的情況，以及對應提出的?Stochastic Gradient Descent?系的算法。

References

• Boyd, S. P., & Vandenberghe, L. (2004).?Convex optimization. Cambridge university press

from:?http://freemind.pluskid.org/machine-learning/newton-method/

總結

以上是生活随笔為你收集整理的牛顿法 Newton Method的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。