Hessian BFGS 牛頓矩陣迭代

數值最佳化-從梯度下降到L-BFGS

由 Yunfan 發表于娛樂2020-12-18

Yunfan REN

renyunfan@outlook。com

數值最佳化是許多機器學習演算法的核心。當一個問題的模型確定了之後，所謂的訓練其實就是一個引數估計問題。這個問題可以被歸結為最小化一個多元函式

$f(\mathrm x)$

，其中

$\mathrm x$

是模型引數，是一個高維向量。寫成最佳化問題的形式其實就是

$\mathrm{minimize}\,\,\, f(\mathrm x)\\$

我們要透過一系列的方法求解這個最佳化問題，例如傳統的梯度下降法可以用下圖表示

牛頓法

不同於有解析的最佳化方法，大多數的數值最佳化演算法都是迭代式的，他們產生一個序列，這個序列最終收斂到

$\mathrm x^*$

使得目標函式最小化。在迭代過程中，假設我們有一個當前估計

$\mathrm x_n$

，我們希望我們的下一個估計

$\mathrm x_{n+1}$

有這樣的屬性

$f(\mathrm x_{n+1})<f(\mathrm x_n)\\$

牛頓法的思想是在

$\mathrm x_n$

附近使用二次函式近似

，假設

是二階可微的，那麼我們可以使用函式

在

$\mathrm x_n$

處的二階泰勒展開來近似

$f(\mathrm x+\Delta \mathrm x) \approx f(\mathrm x)+\Delta \mathrm x^T\nabla f(\mathrm x) +\frac{1}{2}\Delta \mathrm x^T(\nabla^2f(x))\Delta x \\$

其中

$\nabla f,\nabla^2f$

分別是它的梯度和Hessian矩陣。為了簡化符號罵我們將函式

在

$\mathrm x_n$

處的近似記為

，梯度為

，Hessian矩陣為

，那麼上式可以改寫為

$h_n(\Delta x) = f(\mathrm x_n) + \Delta x^Tg_n + \frac{1}{2}\Delta x^TH_n\Delta x \\$

我們假設

$\mathrm x _{n+1} = \mathrm x_n + \Delta \mathrm x$

，我們希望找到一個最好的

$\Delta \mathrm x$

來逼近，因此我們對

$\Delta \mathrm x$

求導

$\frac{\partial h_n(\Delta \mathrm x)}{\partial \Delta \mathrm x}=g_n+H_n\Delta \mathrm x \\$

根據數學分析的知識，任何使得上述偏導為0的點，都是

的極值點。若函式

是凸函式，那麼他的Hessian是正定矩陣，則區域性的極值點就是全域性的最優點，這個問題就退化為【凸二次規劃 QP】，這時候我們就可以閉式的寫出

$\Delta \mathrm x$

$\Delta \mathrm x = -H_n^{-1}g_n\\$

這樣一來我們就得到了一個很好迭代方向，我們選擇一個迭代步長

$\alpha$

，那麼迭代更新的方程就可以寫成

$x_{n+1} = x_n - \alpha (H^{-1}g_n)\\$

這可以使得

$f(\mathrm x_{n+1})-f(\mathrm x_n)$

最大。那麼牛頓法迭代的虛擬碼就可以表示為

其中步長

$\alpha$

可以採用任何的line search的方法，例如給定一個較大的初始值，逐步減小

$\alpha$

的大小，直到

的收斂精度達到要求。

對於凸函式，牛頓法一定能收斂到全域性最優解，而非凸函式，它可以收斂到區域性最優解。

擬牛頓法

上述的牛頓法思路很簡單，但是存在一個計算上的問題。當資料維度很大的時候，Hessian就會變成一個很大的方陣，這時候對Hessian求導將變得非常耗時。這時候就有了Quasi Update的策略來生成

$H_n^{-1}$

的近似。先不考慮具體的Quasi Update方法，擬牛頓法的虛擬碼可以表示為

可以看到，和牛頓法相比，位移的不同在於更新下一次迭代的梯度和Hessian矩陣採用了上一次的資料，交給了QuasiUpdate模組來完成。如果QuasiUpdate能夠返回精確的Hessian矩陣逆，那麼擬牛頓法就等價於牛頓法。

QuasiUpdate

那麼QuasiUpdate要如何來近似Hessian矩陣呢？顯然如果QuasiUpdate返回一個單位陣，那麼我們的牛頓法就退化成了梯度下降法，因為函式遞推只用到了梯度的反方向。我們再來回顧一下

$h_n(\Delta x) = f(\mathrm x_n) + \Delta x^Tg_n + \frac{1}{2}\Delta x^TH_n\Delta x \\$

的一個性質是，它的梯度與

在

$\mathrm x_n$

處的梯度是一致的（因為近似函式與原函式的梯度一致）。也就是我們希望保證

$\nabla h_n(x_n) = g_n\\ \nabla h_n(x_{n-1})g_{n-1}$

將上述兩式相減得

$\nabla h_n(x_n) - \nabla h_n(x_{n-1}) = g_n-g_{n-1}\\$

由微分中值定理，我們知道

$H_n (x_n-x_{n-1}) = (g_n-g_{n-1})\\$

這個式子稱為Secant Condition，該條件保證

$H_{n+1}$

至少對於

$x_n-x_{n-1}$

是近似Hessian矩陣的。等式兩邊同時乘以

$H_{n}^{-1}$

，並且由於我們定義過：

$s_{n+1}\leftarrow x_{n+1}-x_n\\ y_{n+1}\leftarrow g_{n+1} - g_n$

於是可以得到

$H_n^{-1} y_n = s_n\\$

同時由於Hessian是二階偏導陣列成的矩陣，因此他一定是對稱的。

BFGS更新

形式化的講，我們希望

至少滿足上述兩個條件

對於

滿足Secant condition。

滿足對稱性。

給定上述條件，我們還希望

相較於

$H_{n-1}$

的變化量最小。事實上滿足上述條件的有很多，我們選擇變化最小的，這種約束最佳化問題可以寫成

$\min_{H^{-1}}|||H^{-1}- H_{n-1}^{-1}||^2\\ s.t. H^{-1}y_n = s_n\\ H^{-1} \, is\, symmetric$

經過著名的Broyden–Fletcher–Goldfarb–Shanno （BFGS）演算法，我們可以得到上述最佳化問題的解為

$H_{n+1}^{-1} = (I-\rho_ny_ns_n^T)H_n^{-1}(I-\rho_ns_ny_n^T)+\rho_ns_ns_n^T\\ \rho_n = (y_n^Ts_n)^{-1}$

關於BFGS，有幾個需要注意的

只要

$H_{n}^{-1}$

是正定的，那麼

$H_{n+1}^{-1}$

就一定是正定的。所以我們只需要選擇一個正定的

$H_0^{-1}$

就行了，甚至可以選擇單位矩陣。

$H_n^{-1},H_{n+1}^{-1}$

還存在簡單的算數關係，給定了

$H_{n+1}^{-1},s_n,y_n$

，就可以倒推出

$H_n^{-1}$

。

總結起來，我們就得到了BFGS演算法，給定方向

我們就能算出

$H^{-1}_nd$

同時不需要求

$H_n^{-1}$

矩陣。偽程式碼表示為

L-BFGS

BFGS擬牛頓近似演算法雖然免去了計算海森矩陣的煩惱，但是我們仍然需要儲存每次迭代的

和

的歷史值。

L-BFGS是limited BFGS的縮寫，簡單地只使用最近的m個

和

記錄值。

L-BFGS的改進

在實際應用中，有許多L-BFGS的改進演算法，例如

othant-wise 的L-BFGS改進演算法

來訓練

正則損失函式。

參考資料

https：//www。

hankcs。com/ml/l-bfgs。ht

ml

“我花百萬養過袁詠儀”，千億富豪羅兆輝：破產、自殺、賣秘聞

第一位小提琴老師的重要性