理解牛頓法

06-03

理解牛頓法

原創聲明：本文為 SIGAI 原創文章，僅供個人學習使用，未經允許，不能用於商業目的。

導言牛頓法是數值優化演算法中的大家族，她和她的改進型在很多實際問題中得到了應用。在機器學習中，牛頓法是和梯度下降法地位相當的的主要優化演算法。在本文中，SIGAI將為大家深入淺出的系統講述牛頓法的原理與應用。

牛頓法的起源

牛頓法以偉大的英國科學家牛頓命名，牛頓不僅是偉大的物理學家，是近代物理的奠基人，還是偉大的數學家，他和德國數學家萊布尼茲並列發明了微積分，這是數學歷史上最有劃時代意義的成果之一，奠定了近代和現代數學的基石。在數學中，也有很多以牛頓命名的公式和定理，牛頓法就是其中之一。

牛頓法不僅可以用來求解函數的極值問題，還可以用來求解方程的根，二者在本質上是一個問題，因為求解函數極值的思路是尋找導數為0的點，這就是求解方程。在本文中，我們介紹的是求解函數極值的牛頓法。

在SIGAI之前關於最優方法的系列文章「理解梯度下降法」，「理解凸優化」中，我們介紹了最優化的基本概念和原理，以及迭代法的思想，如果對這些概念還不清楚，請先閱讀這兩篇文章。和梯度下降法一樣，牛頓法也是尋找導數為0的點，同樣是一種迭代法。核心思想是在某點處用二次函數來近似目標函數，得到導數為0的方程，求解該方程，得到下一個迭代點。因為是用二次函數近似，因此可能會有誤差，需要反覆這樣迭代，直到到達導數為0的點處。下面我們開始具體的推導，先考慮一元函數的情況，然後推廣到多元函數。

一元函數的情況

為了能讓大家更好的理解推導過程的原理，首先考慮一元函數的情況。根據一元函數的泰勒展開公式，我們對目標函數在x0點處做泰勒展開，有：

如果忽略2次以上的項，則有：

現在我們在x0點處，要以它為基礎，找到導數為0的點，即導數為0。對上面等式兩邊同時求導，並令導數為0，可以得到下面的方程：

可以解得：

這樣我們就得到了下一點的位置，從而走到x1。接下來重複這個過程，直到到達導數為0的點，由此得到牛頓法的迭代公式：

給定初始迭代點x0，反覆用上面的公式進行迭代，直到達到導數為0的點或者達到最大迭代次數。

多元函數的情況

下面推廣到多元函數的情況，如果讀者對梯度，Hessian的概念還不清楚，請先去看微積分教材，或者閱讀SIGAI之前關於最優化的公眾號文章。根據多元函數的泰勒展開公式，我們對目標函數在x0點處做泰勒展開，有：

忽略二次及以上的項，並對上式兩邊同時求梯度，得到函數的導數（梯度向量）為：

其中 $?^{2}f(x_{0})$ 即為Hessian矩陣，在後面我們寫成H。令函數的梯度為0，則有：

這是一個線性方程組的解。如果將梯度向量簡寫為g，上面的公式可以簡寫為：

從初始點x0處開始，反覆計算函數在處的Hessian矩陣和梯度向量，然後用下述公式進行迭代：

最終會到達函數的駐點處。其中 $-H^{-1}g$ 稱為牛頓方向。迭代終止的條件是梯度的模接近於0，或者函數值下降小於指定閾值。

實現細節

根據上面的推導，我們可以得到牛頓法的完整流程為：

1.給定初始值 $x_{0}$ 和精度閾值 $varepsilon$ ，設置k = 0

2.計算梯度 $g_{k}$ 和矩陣 $H_{k}$

3.如果|| $g_{k}$ || $<varepsilon$ 即在此點處梯度的值接近於0，則達到極值點處，停止迭代

4.計算搜索方向 $d_{k}=-H_{k}^{-1}g_{k}$

5.計算新的迭代點 $X_{k+1}=X_{k}+gamma d_{k}$

6.令k = k + 1，返回步驟2

其中 $gamma$ 是一個人工設定的接近於0的常數，和梯度下降法一樣，需要這個參數的原因是保證 $X_{k+1}$ 在 $X_{k}$ 的鄰域內，從而可以忽略泰勒展開的高次項。如果目標函數是二次函數，Hessian矩陣是一個常數矩陣，對於任意給定的初始點，牛頓法只需要一步迭代就可以收斂到極值點。下圖是對x*x+y*y用牛頓法求解的一個例子：

如果我們把步長設置的足夠大（在這裡為1），則演算法一步就收斂了。在這裡，初始迭代位置為(0,4)，最優解為(0,0)。

對於不帶約束條件的問題，我們可以將x的初始值設定為任意值，最簡單的，可以設置為全0的向量。迭代終止的判定規則和梯度下降法相同，是檢查梯度是否接近於0。

牛頓法並不能保證每一步迭代時函數值下降，也不保證一定收斂。為此，提出了一些補救措施，其中的一種是直線搜索（line search）技術，即搜索最優步長。具體做法是讓 $gamma$ 取一些典型的離散值，如0.0001,0.001,0.01等，比較取哪個值時函數值下降最快，作為最優步長。

和梯度下降法相比牛頓法有更快的收斂速度，但每一步迭代的成本也更高。在每次迭代中，除了要計算梯度向量還要計算Hessian矩陣，並求解Hessian矩陣的逆矩陣。實際實現時一般不直接求Hessian矩陣的逆矩陣，而是求解如下方程組：

求解這個線性方程組一般使用迭代法，如共軛梯度法，當然也可以使用其他演算法。

面臨的問題

和梯度下降法一樣，牛頓法尋找的也是導數為0的點，這不一定是極值點，因此會面臨局部極小值和鞍點問題，這在之前的文章中已經介紹過了，這裡不再重複。

牛頓法面臨的另外一個問題是Hessian矩陣可能不可逆，從而導致這種方法失效。此外，求解Hessian矩陣的逆矩陣或者求解線性方程組計算量大，需要耗費大量的時間。為此，提出了擬牛頓法這種改進方案，在後面會介紹。

除此之外，牛頓法在每次迭代時序列xi可能不會收斂到一個最優解，它甚至不能保證函數值會按照這個序列遞減。解決第一個問題可以通過調整牛頓方向的步長來實現，目前常用的方法有兩種：直線搜索和可信區域法。可信域牛頓法在後面也會介紹。

可信域牛頓法

可信域牛頓法（Trust Region Newton Methods）可以求解帶界限約束的最優化問題，是對牛頓法的改進。在可信域牛頓法的每一步迭代中，有一個迭代序列 $x_{k}$ ，一個可信域的大小 $Delta_{k}$ ，以及一個二次目標函數：

這個式子可以通過泰勒展開得到，忽略二次以上的項，這是對函數下降值：

的近似。演算法尋找一個 $S_{k}$ ，在滿足約束條件 $||S||leq Delta_{k}$ 下近似最小化 $q_{k}(s)$

。接下來檢查如下比值以更新 $x_{k}$ 和 $Delta_{k}$ ：

這是函數值的實際減少量和二次近似模型預測方嚮導致的函數減少量的比值。迭代方向可以接受的條件是 $p_{k}$ 足夠大，由此得到參數的更新規則為：

其中 $eta_{0}$ 是一個人工設定的值。 $Delta_{k}$ 的更新規則取決於人工設定的正常數 $eta_{1}$ 和 $eta_{2}$ ，其中：

而 $Delta_{k}$ 的更新率取決於人工設定的正常數 $sigma_{1},sigma_{2},sigma_{3}$ ，其中：

可行域的邊界 $Delta_{k}$ 更新規則為：

在牛頓法的每一步迭代中，動態調整可信域，確保序列收斂。

擬牛頓法

牛頓法在每次迭代時需要計算出Hessian矩陣，然後求解一個以該矩陣為係數矩陣的線性方程組，這非常耗時，另外Hessian矩陣可能不可逆。為此提出了一些改進的方法，典型的代表是擬牛頓法（Quasi-Newton）。

擬牛頓法的思想是不計算目標函數的Hessian矩陣然後求逆矩陣，而是通過其他手段得到Hessian矩陣或其逆矩陣的近似矩陣。具體做法是構造一個近似Hessian矩陣或其逆矩陣的正定對稱矩陣，用該矩陣進行牛頓法的迭代。將函數在 $x_{k+1}$ 點處進行泰勒展開，忽略二次以上的項，有：

對上式兩邊同時取梯度，有：

令 $X=X_{k}$ ，有：

這可以簡寫為：

如果令：

上式可以簡寫為：

即：

這個條件稱為擬牛頓條件，用來近似代替Hessian矩陣的矩陣需要滿足此條件。根據此條件，構造出了多種擬牛頓法，典型的有DFP演算法、BFGS演算法、L-BFGS演算法等，在這裡我們重點介紹BFGS演算法。下圖列出了常用的擬牛頓法的迭代公式（圖片來自維基百科）：

BFGS演算法是它的四個發明人Broyden，Fletcher，Goldfarb和Shanno名字首字母的簡寫。演算法的思想是構造Hessian矩陣的近似矩陣：

并迭代更新這個矩陣：

該矩陣的初始值 $B_{0}$ 為單位陣I。這樣，要解決的問題就是每次的修正矩陣 $Delta$ $B_{k}$ 的構造。其計算公式為：

其中：

因此有：

演算法的完整流程為：

1.給定優化變數的初始值 $x_{0}$ 和精度閾值 $varepsilon$ ，令 $B_{0}=I$ ,K=0

2.確定搜索方向 $d_{k}=-B_{k}^{-1}g_{k}$

3.搜索得到步長 $lambda_{k}$ ，令 $S_{k}=lambda_{k}d_{k},X_{k+1}=X_{k}+S_{k}$

4.如果 $||g_{k+1}||<varepsilon$ ，則迭代結束

5.計算 $Y_{k}=g_{k+1}-g_{k}$

6.計算 $B_{k+1}=B_{k}+frac{Y_{k}Y_{k}^{T}}{Y_{k}^{Y}S_{k}}-frac{B_{k}S_{k}S_{k}^{T}B_{k}}{S_{k}^{t}B_{k}xS_{k}}$

7.令K=K+1，返回步驟2

每一步迭代需要計算nxn的矩陣 $D_{k}$ ，當n很大時，存儲該矩陣非常耗費內存。為此提出了改進方案L-BFGS，其思想是不存儲完整的矩陣 $D_{k}$ ，只存儲向量 $S_{k}$ 和 $Y_{k}$ 。

實際應用

下面介紹牛頓法在機器學習中的實際應用。在這裡我們以線性支持向量機和liblinear為例。liblinear是一個線性演算法的開源庫，其作者是台灣大學林智仁教授和他的學生，與libsvm的作者相同。這個庫支持logistic回歸和線性支持向量機兩類演算法，包括各種損失函數和正則化的版本。L1正則化L2損失函數線性支持向量機訓練時求解如下最優化問題：