无约束最优化五

3.2 Quasi-Newton Method
  Quasi-Newton Method每一步计算过程中仅涉及到函数值和函数梯度值计算,这样有效避免了Newton Method中涉及到的Hessian矩阵计算问题。于Newton Method不同的是Quasi-Newton Method在每点处构建一个如下的近似模型:
 opt5-1
从上面的近似模型我们可以看出,该模型用B_k代替了Newton Method中近似模型中涉及到的Hessian矩阵。因此Quasi-Newton Method中方向计算公式如下所示:
      opt5-2   (24)
  这里有必要解释一下用于近似Hessian矩阵的B_k可行性,及一个指导性方案。根据Taylor(泰勒)级数可知如下公式:
opt5-3
由于函数▽f(.)连续,因此上式可以表示为:
opt5-4
                           (25)
  因此每一选择Hessian矩阵的近似B_ k+1时,可以像式(24)那样模仿真实的Hessian矩阵的性质。得到下式:
     opt5-5     (26)
其中:

s_k = x_k+1 – x_k y_k = ▽f(x_k+1) – ▽f(x_k) (27)

同时要求B_k+1为对称正定矩阵。

3.2.1 BFGS Method
  从Quasi-Newton Method方向公式 (24) 中,可以看到每一步计算方向的过程中均涉及到B_k+1矩阵求逆的问题,为了避免该计算,通过分析公式(26)可知,我们可以构建一个近似H_k+1,该近视满足如下方程:

   H_k+1*y_k = s_k     (28)

同时要求H_k+1为对称正定矩阵。因此BFGS Method中,每个点处的方向由如下公式计算:

   p_k = –H_k*▽f(x_k)   (29)

  在此基础上,BFGS方向迭代公式如下所示:
opt5-6
                         (30)
其中ρ_k为一个标量:
     opt5-7
有了上面(30)的H_k迭代公式后,还有一个问题就是初始的H_0如何计算,目前常用的方法是初始的H_0直接设为单位矩阵I。因此BFGS Method用于解无约束最优化的过程可以表示为如下过程:
opt5-8

3.2.2 LBFGS Method
  上一节所介绍的BFGS Method比较适合解决中小规模无约束最优化问题,但是BFGS算法产生的Hessian近似矩阵H_k为n * n的,同时该矩阵非稀疏,因此当n的规模较大时将面临两个问题:
1) 存储问题:n规模较大时,n*n矩阵对内存的消耗将较大;
2) 计算问题:n规模较大,同时n*n矩阵非稀疏时,计算复杂度将较高;
为了解决以上问题,引申出了Limited-Memory Quasi-Newton Method,目前使用较多的LBFGS算法即属于该类算法。为了减少H_k矩阵的存储,LBFGS算法利用最近几代的curvature 信息来构建Hessian矩阵的近似。由BFGS Method我们知道:

   x_k+1 = x_k + a_k * H_k*▽f(x_k)

其中a_k为步长,H_k为Hessian矩阵的近似,可以通过如下迭代公式计算:

 H_k+1 = V_k* H_k*V_k+ρ_k * s_k* s_k   (31)

其中:
  opt5-9
从上面的H_k的迭代计算公式可知,H_k会慢慢由稀疏矩阵转变为稠密矩阵,因此存储该矩阵以及进行该矩阵和向量的相乘运算的消耗将较大。为了避免该问题,LBFGS算法在BFGS算法的基础上从两点进行了改进:
1)估算每一步对应的Hessian近似矩阵时,给出一个当前步的初始Hessian矩阵估计H_k0
2) 利用过去当前代及过去m-1代的curvature信息修正初始Hessian矩阵估计H_k0,得到最终的Hessian矩阵近似估计H_k。
计算式如下所示:
opt5-10
                     (32)
上述计算式(32),可以通过公式(31)递归计算获取。公式(32)可以用以下算法表示:
     opt5-11
  从上面计算H_k的公式(32)可知,要估算每个点x_k处的Hessian矩阵近似,需要给出初始估计H_k0,H_k0一般通过以下公式计算:
     opt5-12
有了上面的方向计算算法后,LBFGS算法用于解无约束最优化问题,可以表示为如下算法:

1 选择一个初始点x_0,并选择收敛判断条件 ε> 0,以及常量m(代表过去代数)一般为6
2 k left 0 H_0 left I,因此r = H_0 *▽f(x_0) =▽f(x_0)
3 while ||▽f(x_k)|| > ε
4   计算从当前点x_k走到下一个点x_k+1的方向
      p_k = –r
5 采用line search策略计算步长a_k
6 x_k+1 = x_k + a_k * p_k
7 if k > m
   删除LBFGS计算H_k时用不上的向量对(s_k-m, y_k-m)
8 计算并保存 s_k = x_k+1 – x_k y_k = ▽f(x_k+1) – ▽f(x_k)
9 采用LBFGS Hessian矩阵近似算法计算 r
10 k left k+1

4.算法总结
  用于解无约束优化算法的Quasi-Newton Method中的LBFGS算法到这里总算初步介绍完了,不过这里笔者要承认的是这篇文档省略了许多内容,包括算法收敛性的证明以及收敛速度证明等许多内容。因此读者若希望对这一块有一个更深入的认识可以参考以下两本书:
1) Numerical Methods for Unconstrained Optimization and Nonlinear Equations(J.E. Dennis Jr. Robert B. Schnabel)
2) Numerical Optimization(Jorge Nocedal Stephen J. Wright)

同时我想引用一下侯捷老师的话:

  大哉问。学习需要明师。但明师可遇不可求,所以退而求其次你需要好书,并尽早建立自修的基础。迷时师渡,悟了自渡,寻好书看好书,就是你的自渡法门。切记,徒学不足以自行,计算机是实作性很强的一门科技,你一定要动手做,最忌讳眼高手低。学而不思则罔,思而不学则殆,一定要思考、沉淀、整理。

因此这里附上一个我阅读后感觉代码还比较美观的LBFGS实现(C++):
  http://www.chokkan.org/software/liblbfgs/(Naoaki Okazaki)
  最后我不得不承认这篇文档,对许多读者来说也许是几张废纸,甚至使读者昏昏欲睡,或烦躁。因为该文档从头至尾并未涉及到一个例子。-_- ||
老天啊,饶恕我吧,毕竟愿望是美好的,但愿它能对你理解LBFGS算法有一点帮助,哪怕是一点点…
                    jianzhu
                    jzhu.nlp (at) gmail.com
                    2009-11-1-2009-12-1

全文完!

注:这个系列的作者是我的师兄jianzhu,他在中文分词、语言模型方面的研究很深入,如果大家对于srilm的源代码感兴趣,可以参考他个人博客上写的“srilm阅读文档系列”,很有帮助。

原创文章,转载请注明出处“我爱自然语言处理”:www.52nlp.cn

本文链接地址:http://www.52nlp.cn/unconstrained-optimization-five

此条目发表在专题, 自然语言处理分类目录,贴了, , , , , , , 标签。将固定链接加入收藏夹。

无约束最优化五》有 8 条评论

  1. goog说:

    你好!通过那个算法我似乎得不到公式(32),能麻烦给个推导过程吗? THX!

    [回复]

  2. 52nlp说:

    可以直接发邮件给原作者:jzhu.nlp (at) gmail.com

    [回复]

  3. jianzhu说:

    可以得到公式32的,这里给出一个更好的tutorial
    http://www.cs.washington.edu/homes/galen/files/quasi-newton-notes.pdf

    [回复]

  4. eacl说:

    赞!这个系列太好了!

    [回复]

  5. zxc说:

    大赞! 我正在学习这方面的内容,找了好多文献,要么讲的不全面,要么太深奥看不懂! 这篇文档真是深入浅出鞭譬如里,解了我的燃眉之急! 太感谢了!

    [回复]

  6. 说:

    谢谢,我最近在看最大熵,看到训练模型这块儿没看懂,文章写得很好

    [回复]

  7. hbf0803说:

    请问作者文中向左的箭头代表什么意思?

    [回复]

  8. HUA说:

    公式31上面的那个公式a_k前面的符号应该是不是负号?

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注