BFGS的笔记

Hessian矩阵:

$$ G = \begin{bmatrix} \dfrac{\partial^2 f}{\partial x1^2} & \dfrac{\partial^2 f}{\partial x1,\partial x2} & \cdots & \dfrac{\partial^2 f}{\partial x1,\partial xn} \ \dfrac{\partial^2 f}{\partial x2,\partial x1} & \dfrac{\partial^2 f}{\partial x2^2} & \cdots & \dfrac{\partial^2 f}{\partial x2,\partial xn} \ \vdots & \vdots & \ddots & \vdots \ \dfrac{\partial^2 f}{\partial xn,\partial x1} & \dfrac{\partial^2 f}{\partial xn,\partial x2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix} $$

最优化中的Quasi-Newton method是当f的二阶偏导矩阵Hessian matrix难以求出来的时候,用另一个矩阵B来代替Hessian矩阵。主要有两种方法:SR1和BFGS。这两种方法的主要区别是:SR1产生的是rank 1的矩阵,而BFGS产生的是rank 2的矩阵。

SR1的全称是symmetric-rank-one。

DFP

令\( Bk \) 是Hessian矩阵\( Gk\) 的近似。那么BFP计算\( B_k \)的公式是

$$ B{k+1} = (I - \frac{yk sk^T}{yk^T sk}Bk\frac{sk yk^T}{yk^T sk} + \frac{yk yk^T}{yk^T sk})$$

它的逆矩阵\( Hk = Bk^{-1} \) 的递推公式是

$$ H{k+1} = Hk - \frac{Hk yk yk^T Hk}{yk^T Hk yk} + \frac{sk sk^T}{yk^T s_k}$$

BFGS

\(H_k\)的迭代公式是:

$$ H{k+1} = (I - \frac{sk yk^T}{yk^T sk}) Hk (I - \frac{yk sk^T}{yk^T sk})+ \frac{sk sk^T}{yk^T sk} $$

如果令$$ Vk = I - \frac{yk sk^T}{yk^T s_k} $$

则有

$$ H{k+1} = Vk^T Hk Vk + \frac{sk sk^T}{yk^T sk} $$

它具有一个很有趣的特性,如果令\(Vk=1, yk^T sk=0\), 那么\( H{k+1} = H_k \)

L-BFGS

L-BFGS的论文: "Updating Quasi-Newton Matrices with Limited Storage" (1980)

BFGS的一个困难是它需要存储Hessian矩阵或者Hessian矩阵的逆。那么假如我们有1亿个feature,那么就需要1亿*1亿*sizeof(double)=84 PB的空间来存储这个矩阵,完全不可接受。

L-BFGS的核心思想是:存储g和x的最近m次迭代的历史值。然后利用这些历史值通过求查分的方式模拟出逆Hessian矩阵的近似。实际计算中并不需要把逆Hessian矩阵算出来,而是只进行vector运算就行了。这样假设有n个feature,空间复杂度就是O(m*n)。缺点是:收敛速度会变慢。

它的paper发表于1980年,算是比较老也比较成熟的算法了。所以建议不要看原始论文,看教材即可。Springer的Numerical Optimization(2nd)中第7.2节对它有很好的阐述。

前面说过,BFGS的迭代公式是:
$$ Hk = V{k-1}^T H{k-1} V{k-1} + \frac{s{k-1} s{k-1}^T}{y{k-1}^T s{k-1}} $$

如果我们把Hk-1再次展开,可得 $$ Hk = V{k-1}^T(V{k-2}^T H{k-2} V{k-2} + \frac{s{k-2} s{k-2}^T}{y{k-2}^T s{k-2}}) V{k-1} + \frac{s{k-1} s{k-1}^T}{y{k-1}^T s{k-1}} \
= V{k-1}^T V{k-2}^T H{k-2} V{k-2}V{k-1} + \frac{1}{y{k-2}^T s{k-2}}V{k-1}^Ts{k-2} s{k-2}^T V{k-1} + \frac{s{k-1} s{k-1}^T}{y{k-1}^T s_{k-1}} $$

连续展开m次可得:

$$ \begin{align} Hk &= V{k-1}^T \dots V{k-m}^T H{k-m} V{k-m} \dots V{k-1} \
&+ \frac{1}{y{k-m}^T s{k-m}}V{k-1}^T \dots V{k-m+1}^T s{k-m} s{k-m}^T V{k-m+1} \dots V{k-1} \
&+ \frac{1}{y{k-m+1}^T s{k-m+1}}V{k-1}^T \dots V{k-m+2}^T s{k-m+1} s{k-m+1}^T V{k-m+2} \dots V{k-1} \
&+ \dots \
&+ \frac{s{k-1} s{k-1}^T}{y{k-1}^T s{k-1}} \end{align} $$

L-BFGS的思想是:把上式中的Hk-m用Hk0来取代。一般做法是,令:

$$ H1^0 = I, Hk^0 = \frac{s{k-1} y{k-1}^T}{y{k-1}^T y{k-1}} I (k>=2) $$

这样就可以通过sk-1 ... sk-m,yk-1,sk-m, ∇fk 这2m+1个向量计算出Hk

L-BFGS two-loop recursion Algorithm:
Output: Hk∇fk
q ←∇fk
for i = k − 1, k − 2, ... , k − m
  αi ← ρi siTq   q ← q − αi yi end (for)
r ← Hk0 q
for i = k − m, k − m + 1, ... , k − 1
  β ← ρi yiT r   r ←r + sii − β) end (for)
return r

主循环:
Choose starting point x0, integer m > 0;
k ← 0;
repeat
  Choose H0   用上面的two-loop recursion算法计算\( pk ←Hk∇fk \);
  计算 \(x
{k+1} ← xk + αkpk\), where \(αk\) is chosen to satisfy theWolfe conditions;
  if k > m
    Discard the vector pair \({s{k−m}, y{k−m}}\) from storage;
  计算并保存 \(sk ← x{k+1} − xk , yk=∇f{k+1}-∇fk\) ;
  k ← k + 1;
until convergence.

V-LBFGS: "Large-scale L-BFGS using MapReduce(2014)" 是微软的同事对L-BFGS的改进。核心目的是把LBFGS中计算方向的算法中的向量运算统统map-reduce化。这样就可以处理单机无法容纳的大向量(比如几百亿维的)

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥