机器学习基础·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的原理部分，具体实现是采用递推的算法。

6. L-BFGS算法

以下算法来自Numerical Optimization

输入：当前的x_k，函数f(x)，\rho_i,s_i,q_i,i=1,2,...,k-1

输出：求x_{k+1}时的更新方向

（1）q \leftarrow \nabla f_k

（2）for\ \ \ i= k-1,k-2,...,k-m
    \alpha_i \leftarrow \rho_i s_i^Tq\ ;
    q \leftarrow q -\alpha_iy_i\ ;
   end

（3）r\ \leftarrow H_k^0q\ ;

（4）for\ \ \ i= k-m,k-m+1,...,k-1
    \beta\ \leftarrow \rho_i y_i^Tr\ ;
    r \leftarrow r +s_i(\alpha_i-\beta)\ ;
   end

（5）stop\ \ with\ \ result\ \ H_k\nabla f_k=r

参考资料

[1] 李航.统计学习方法(第二版).清华大学出版社,2019.
[2] https://www.jianshu.com/p/287b43e837c1
[3] https://blog.csdn.net/Shenpibaipao/article/details/89352840
[4] https://blog.csdn.net/google19890102/article/details/46389869
[5] Numerical Optimization
[6] https://www.cnblogs.com/sunruina2/p/9244709.html

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,133评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,682评论 3赞 390
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,784评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,508评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,603评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,607评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,604评论 3赞 415
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,359评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,805评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,121评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,280评论 1赞 344
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,959评论 5赞 339
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,588评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,206评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,442评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,193评论 2赞 367
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,144评论 2赞 352

推荐阅读更多精彩内容