机器学习基础·L-BFGS算法

简介

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

关键字

拟牛顿法、BFGS、L-BFGS、机器学习、优化方法

正文

1. 概述

L-BFGS由牛顿法发展而来，是为了提高计算效率而提出的近似计算方法，在施行牛顿法的过程中需要计算海森矩阵的逆 $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算法

输入：目标函数 $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 }$
发现除了 $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$ 这些向量来表达。

根据以上结论，在每次迭代时只要保存 $y_k,\delta _k,k=1,2,...,k-1$ 这些值，BFGS算法可以只使用 $B_0$ 表达，那么L-BFGS在这个基础上，再一次进行近似，就是只用有限的内存来保存近 $m$ 个向量的值来进行计算。

具体实现时，为了方便还要对表达式进行一定的变换，首先对 $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的原理部分，具体实现是采用递推的算法。