亚洲人妻系,一区二区中文在线观看

簡介

L-BFGS的算法原理及步驟。

關鍵字

擬牛頓法、BFGS、L-BFGS、機器學習、優(yōu)化方法

正文

1. 概述

??L-BFGS由牛頓法發(fā)展而來，是為了提高計算效率而提出的近似計算方法，在施行牛頓法的過程中需要計算海森矩陣的逆 $H^{-1}$ ，計算矩陣逆工作量巨大，所以采用符合擬牛頓條件的矩陣代替 $H^{-1}$ 或 $H$ 進行計算，這種方法稱為擬牛頓法，其代表性方法有DFP算法和BFGS算法，L-BFGS在BFGS的基礎上進一步在有限的內存下進行近似而提高效率的算法。

2. 擬牛頓條件

??假設問題是：
$\arg \min_x f(x)$
??且有 $g_k=\nabla f(x)\ , \ y_k=g_{k+1}-g_k\ ,\ \delta _k=x_{k+1}-x_k$ 。

??首先進行二階泰勒展開，得到：
$f(x)=f(x_k)+g_k(x-x_k)+\frac12(x-x_k)^TH(x_k)(x-x_k)$
??對其求導后，代入 $x=x_{k+1}$ ，可得：

$y_k=H_k \delta _k \ \ \ 或\ \ \ H_k^{-1} y_k = \delta _k$
??上面的式子稱作擬牛頓條件，要求 $H$ ， $H^{-1}$ 正定。

3. BFGS原理

??BFGS算法考慮使用矩陣 $B_k$ 近似矩陣 $H$ ，對應的擬牛頓條件是上面的第1個。每次對 $B_k$ 進行迭代，所以算法核心就是如何求得 $B_{k+1}$ 。
??令：
$B_{k+1}=B_k+P_k+Q_k$
??自然有：
$B_{k+1}\delta_k=B_k\delta_k+P_k\delta_k+Q_k\delta_k$
??考慮使 $P_k,Q_k$ 滿足：
$P_k\delta_k=y_k \ ,\ Q_k\delta_k=-B_k\delta_k$
??得到 $B_{k+1}$ 的迭代公式：
$B_{k+1}=B_k + \frac{y_ky_k^T}{y_k^T \delta _k}-\frac{B_k \delta_k \delta_k^T B_k }{\delta_k^T B_k \delta_k }$

4. BFGS算法

??輸入：目標函數(shù) $f(x)$ ， $g(x)=\nabla f(x)$ ，精度要求 $\epsilon$

??輸出： $f(x)$ 的極小點 $x^*$

??（1）選定 $x_0,B_0$ ，設置 $k=0$

??（2）計算 $g_k=g(x^{(k)})$ ，如滿足 $\mid\mid g_k\mid\mid \le \epsilon$ ，則停止，得解。

??（3）由 $B_kp_k=-g_k$ 求出 $p_k$

??（4）求 $\lambda_k=\arg\min_{\lambda \ge 0}f(x^{(k)}+\lambda_{p_k})$

??（5）置 $x^{(k+1)}=x^{(k)}+\lambda_k p_k$

??（6）計算 $g_{k+1}=g(x^{(k+1)})$ ，如滿足 $\mid\mid g_{k+1}\mid\mid \le \epsilon$ ，則停止，得解。否則計算 $B_{k+1}$

??（7） $k=k+1$ ，轉（3）

5. L-BFGS原理

??在BFGS算法的提出目的是為了不計算矩陣的逆，然而上面的算法中（3）求 $p_k$ ，需要 $p_k=-B_k^{-1} g_k$ ，還是需要計算矩陣逆，還好有辦法可以不用算，仔細觀察上面的式子，為了方便，這里再寫一遍：
$B_{k+1}=B_k + \frac{y_ky_k^T}{y_k^T \delta _k}-\frac{B_k \delta_k \delta_k^T B_k }{\delta_k^T B_k \delta_k }$
發(fā)現(xiàn)除了 $B_k$ ，剩下的都是向量，說明 $B_{k+1}$ 可以由 $B_k$ 來表達，而 $B_k$ 可以由 $B_{k-1}$ 來表達，依次類推，可以得到結論對于任何一個 $B_k\ ,\ k \gt1$ 最終都可以使用 $B_0$ 及 $y_k,\delta _k,k=1,2,...,k-1$ 這些向量來表達。

??根據(jù)以上結論，在每次迭代時只要保存 $y_k,\delta _k,k=1,2,...,k-1$ 這些值，BFGS算法可以只使用 $B_0$ 表達，那么L-BFGS在這個基礎上，再一次進行近似，就是只用有限的內存來保存近 $m$ 個向量的值來進行計算。

??具體實現(xiàn)時，為了方便還要對表達式進行一定的變換，首先對 $B_{k+1}$ 進行變換，變換推導比較復雜，參考資料[3]給出了大概的思路和過程，具體變換為：
$B_{k+1}^{-1}=(I-\frac{\delta_k y_k^T}{y_k^T \delta _k })B_k^{-1}(I-\frac{y_k \delta _k ^T}{y_k^T \delta _k })+\frac{\delta_k \delta _k^T}{y_k^T \delta _k }$
??接下來記：
$\rho _k^{-1}=y_k^T\delta_k \ \ \ \ ,\ \ \ V_k=I-\rho_ky_k \delta _k^T$
??且假設 $B_0=I$ ，則有：
$B_{k+1}^{-1}=V_k^T B_k^{-1} V_k + \rho_k \delta _k \delta _k ^T$
??遞推至 $B_0$ ，則有：
$B_{k+1}^{-1}=\prod_{i=0}^k V_{k-i}^T \cdot B_0 \cdot \prod_{i=0}^k V_i+\sum_{i=0}^k(\prod_{j=i+1}^k V_{k-j+1}^T \cdot \rho_i \delta_i \delta_i^T \cdot \prod_{j=i+1}^k V_j)$
??只使用近m次的結果來近似，得到：
$\begin{align} B_{k+1}^{-1} & = \prod_{i=1}^m V_{k-i+1}^T \cdot B_0 \cdot \prod_{i=k-m+1}^k V_i\\ &+\sum_{i=1}^m(\prod_{j=m-i+1}^{m-1} V_{k-m+j+1}^T \cdot \rho_{k-i+1} \delta _{k-i+1} \delta _{k-i+1}^T \cdot \prod_{j=k-i+2}^k V_j) \end{align}$
??以上是L-BFGS的原理部分，具體實現(xiàn)是采用遞推的算法。