精华内容
参与话题
问答
  • 一文读懂L-BFGS算法

    万次阅读 多人点赞 2018-11-26 00:03:01
    接前一篇:逻辑回归... 本章我们来学习L-BFGS算法.L-BFGS是机器学习中解决函数最优化问题比较常用的手段,本文主要包括以下六部分:  1-L-BFGS算法简介  2-牛顿法求根问题  3-牛顿法求函数的驻点  4-...

    接前一篇:逻辑回归(logistics regression)

            本章我们来学习L-BFGS算法.L-BFGS是机器学习中解决函数最优化问题比较常用的手段,本文主要包括以下六部分:

                   1-L-BFGS算法简介

                   2-牛顿法求根问题

                   3-牛顿法求函数的驻点

                   4-牛顿法求驻点的本质

                   5-BFGS算法

                   6-L-BFGS算法

     

    1-L-BFGS算法简介

             我们知道算法在计算机中运行的时候是需要很大的内存空间的.就像我们解决函数最优化问题常用的梯度下降,它背后的原理就是依据了泰勒一次展开式.泰勒展开式展开的次数越多,结果越精确,没有使用三阶四阶或者更高阶展开式的原因就是目前硬件内存不足以存储计算过程中演变出来更复杂体积更庞大的矩阵.L-BFGS算法翻译过来就是有限内存中进行BFGS算法,L是limited memory的意思.

             那算法为什么叫BFGS呢,请看下图:

             

            上图中从左到右依次是Broyden,Fletcher,Goldfarb,Shanno.四位数学家名字的首字母是BFGS,所以算法的名字就叫做BFGS算法.接下来我们就一起来学习BFGS算法的内容.

             学习BFGS必须要先了解牛顿法的求根问题.

     

    2-牛顿法求根问题

            牛顿发现,一个函数的跟从物理的角度就可以根据函数图像迭代求得.牛顿法求根的思路是:

            a.在X轴上随机一点x_{1},经过x_{1}做X轴的垂线,得到垂线与函数图像的交点f(x_{1}).

            b.通过f(x_{1})做函数的切线,得到切线与X轴的交点x_{2}.

            c.迭代a/b两步.

            下面附上一张动图方便理解:

            

            通过图片我们可以看到.在X轴上取的点会随着迭代次数的增加而越来越接近函数的根.经过无限多次的迭代,x_{n}就等于函数f(x)的根.但牛顿法在实际应用的时候我们不会让算法就这么迭代下去,所以当x_{k-1}x_{k}相同或者两个值的差小于一个阈值的时候,x_{k}就是函数f(x)的根.

            那么问题来了,怎么样找到f(x)的导函数与X轴的交点.请看下图:

            

             图片是上边动图从x_{1}x_{2}的动作.可以看到,三角形绿色的直角边的值是x_{1} - x_{2} ,  x_{1}是已知的(随机出来的),而且函数表达式f(x)也是已知的(不知道要求的函数咱们折腾啥呢).所以三角形的另一条直角边f(x_{1})也是已知的.根据导函数定义,函数f(x)x_{1} 点的导函数就是f^{'}(x) = \frac{f(x_{1})}{x_{1} - x_{2}} (公式一).

    公式一变换一下得到:x_{2} =x_{1} - \frac{ f(x_{1})}{f^{'}(x_{1})}(公式二 ),同理可以得出每一次迭代x_{k}的表达式都是x_{k} =x_{k-1} - \frac{ f(x_{k-1})}{f^{'}(x_{k-1})}(公式三).

            所以,根据牛顿法求根的思路,我们可以总结(模仿)一下使用牛顿法求根的步骤:

            a.已知函数f(x)的情况下,随机产生点x_{0}.

            b.由已知的x_{0}点按照x_{k} =x_{k-1} - \frac{ f(x_{k-1})}{f^{'}(x_{k-1})}的公式进行k次迭代.

            c.如果x_{k}与上一次的迭代结果x_{k-1}相同或者相差结果小于一个阈值时,本次结果x_{k}就是函数f(x)的根.

    以上为牛顿法的求根的思路.

     

    3-牛顿法求函数的驻点

             我们知道,机器学习过程中的函数最优化问题,大部分优化的都是目标函数的导函数,我们要求得导函数为零时的点或近似点来作为机器学习算法表现最好的点.现在我们知道了牛顿求根法,那把牛顿求根法的函数换成咱们要优化的导函数不就行了么.要求的的导函数为零的点叫做驻点.所以用牛顿法求函数驻点同求函数的根是没有任何区别的.只是公式二中的f(x)变为了f^{'}(x),原来的f^{'}(x)变成了一阶导函数f^{'}(x)的导函数也就是二阶导函数f^{''}(x),求x_{k}的迭代公式如下:

            x_{k} = x_{k-1} - \frac{f^{'}(x_{k-1})}{f^{''}(x_{k-1})}    (公式四)

            这样,我们通过几何直觉,得到了求解函数根的办法,那这么厉害的一个想法,有没有什么理论依据作为支撑呢?当然有了,要不我也不这么问.

     

    4-牛顿法求驻点的本质

            牛顿法求驻点的本质其实是二阶泰勒展开.我们来看二阶泰勒展开式:

            

            \varphi (x)是我们要求解的原函数的近似式.当我们要对原函数求解时,可以直接求得\varphi (x)的导函数\varphi^{'} (x) 令\varphi^{'} (x) = 0时的结果就是原函数的解.所以对\varphi (x)求导,消去常数项后得到公式如下:

            

             经过变换后所得的公式就是上边的公式四.所以,牛顿法求驻点的本质就是对函数进行二阶泰勒展开后变换所得到的结果.

             在一元函数求解的问题中,我们可以很愉快的使用牛顿法求驻点,但我们知道,在机器学习的优化问题中,我们要优化的都是多元函数,所以x往往不是一个实数,而是一个向量.所以将牛顿求根法利用到机器学习中时,x是一个向量,f^{'}(x)也是一个向量,但是对f^{'}(x)求导以后得到的f^{''}(x)是一个矩阵,叫做Hessian矩阵.等价公式如下:

            

            公式中,g_{k}为公式四种的f^{'}(x),H_{k}^{-1}代表二阶导函数的倒数.

            当x的维度特别多的时候,我们想求得f^{''}(x)是非常困难的.而牛顿法求驻点又是一个迭代算法,所以这个困难我们还要面临无限多次,导致了牛顿法求驻点在机器学习中无法使用.有没有什么解决办法呢?请看博客开头的照片,四位数学家在向你微笑....

     

    5-BFGS算法

              BFGS算法是通过迭代来逼近H_{k}^{-1}的算法.逼近的方式如下:

                    (公式五)

             公式五中的 D_{k}就是H_{k}^{-1}.s_{k} = x_{k+1} - x_{k},y_{k} = g_{k+1} - g_{k}g_{k}是原函数的导函数.

             D_{k}的迭代公式复杂无比,还好我们不用记住它.BFGS是通过迭代来逼近H_{k}^{-1}矩阵,第一步的D矩阵是单位矩阵.

             我们要通过牛顿求驻点法和BFGS算法来求得一个函数的根,两个算法都需要迭代,所以我们干脆让他俩一起迭代就好了.两个算法都是慢慢逼近函数根,所以经过k次迭代以后,所得到的解就是机器学习中目标函数导函数的根.这种两个算法共同迭代的计算方式,我们称之为On The Fly.个人翻译:让子弹飞~

              回顾一下梯度下降的表达式\Theta_{k} = \Theta_{k+1} - \alpha \cdot g ,在BFGS算法迭代的第一步,单位矩阵与梯度g相乘,就等于梯度g,形式上同梯度下降的表达式是相同的.所以BFGS算法可以理解为从梯度下降逐步转换为牛顿法求函数解的一个算法.

             虽然我们使用了BFGS算法来利用单位矩阵逐步逼近H矩阵,但是每次计算的时候都要存储D矩阵,D矩阵有多大呢.假设我们的数据集有十万个维度(不算特别大),那么每次迭代所要存储D矩阵的结果是74.5GB.我们无法保存如此巨大的矩阵内容,如何解决呢?

             使用L-BFGS算法.

    6-L-BFGS算法:

             我们每一次对D矩阵的迭代,都是通过迭代计算s_{k}和y_{k}y_{k}得到的.既然存不下D矩阵,那么我们存储下所有的s_{k}和y_{k}y_{k},想要得到D_{10}就用单位矩阵同存储下的s_{1}y_{1}s_{10}y_{10}计算就可以了.这样一个时间换空间的办法可以让我们在数据集有10000个维度的情况下,由存储10000 x 10000的矩阵变为了存储十个1 x 10000的10个向量,有效节省了内存空间.

            但是,仅仅是这样还是不够的,因为当迭代次数非常大的时候,我们的内存同样存不下.这个时候只能丢掉一些存不下的数据.假设我们设置的存储向量数为100,当s和y迭代超过100时,就会扔掉第一个s和y,存储s_{2}s_{101}y_{2}y_{101},每多一次迭代就对应的扔掉最前边的s和y.这样虽然损失了精度,但确可以保证使用有限的内存将函数的解通过BFGS算法求得到.

            所以L-BFGS算法可以理解为对BFGS算法的又一次近似..

    到这里,L-BFGS算法的逻辑和由来就已经讲解完毕了文章中唯一没有讲到的地方就是BFGS算法的推导过程,因为推导过程比较长而且不是我们学习的重点.如果大家有兴趣的话可以去百度BFGS算法推导过程.

            最后,感谢您的耐心阅读.非常感谢.

     

    下一篇:决策树(Decision Tree)

    展开全文
  • 大规模优化算法 - LBFGS算法

    千次阅读 2017-02-16 22:10:47
    L-BFGS算法比较适合在大规模的数值计算中,具备牛顿法收敛速度快的特点,但不需要牛顿法那样存储Hesse矩阵,因此节省了大量的空间以及计算资源。本文主要通过对于无约束最优化问题的一些常用算法总结,一步步的理解L...

    L-BFGS算法比较适合在大规模的数值计算中,具备牛顿法收敛速度快的特点,但不需要牛顿法那样存储Hesse矩阵,因此节省了大量的空间以及计算资源。本文主要通过对于无约束最优化问题的一些常用算法总结,一步步的理解L-BFGS算法,本文按照最速下降法 - 牛顿法 - 共轭梯度法 - 拟牛顿法 - DFP矫正 - BFGS 矫正 - LBFGS算法这样一个顺序进行概述。(读了一些文章之后,深感数学功底不够,在计算机视觉领域和机器学习领域,数学还是王道)


    1. 最优化方法的迭代思想: 最优化方法采用的都是迭代的方法,基本思想是给定一个初始的点x_0,按照某一个迭代的规则产生一个点列{x_k},在点列有限的情况下最后一个x_k就为最优解,当点列无穷的时候,则极限点为最优解。基本的迭代方程形式如下:

    大规模优化算法 <wbr>- <wbr>LBFGS算法

    其中x_k就是迭代点列中的点,d_k为第k次搜索的方向,a_k为步长。

    在所有的优化方法中三个关键的因素是:初始值x_0, 方向d_k 以及步长a_k,因此在一般的对于优化算法的学习,只需要搞懂这三个东西是怎么生成的,也就可以了。进一步理解则需要对于其理论进行深入的分析了。

     

    2.  最速下降法(Gradient descent):GD算法是无约束最优化算法中最简单的一种算法,它的各种变种也被应用到大规模的机器学习任务中来,比如SGDbatch GDmini-batch等。

     

    GD算法的一个基本假设就是函数f(x)x_k处是连续可谓的,并且其导数g_kx_k处不为0. 将一个函数在x_k这一点做一阶的泰勒展开,得到:

     大规模优化算法 <wbr>- <wbr>LBFGS算法

    优化的目的是让函数值随着点列{x_k}的渐进,逐渐下降,在上式中就是让f(x)小于f(x_k),如何达到这一个目的呢。

    由于泰勒展开余项的值相对很小,因此我们可以忽略它。看第二项大规模优化算法 <wbr>- <wbr>LBFGS算法 ,如果它为负值,就可以达到我们的目的。记大规模优化算法 <wbr>- <wbr>LBFGS算法,那么大规模优化算法 <wbr>- <wbr>LBFGS算法的方向d_k就是下降的方向,这个方向有无穷多个,那那个最大呢,由Cauchy-Schwartz不等式,有

     大规模优化算法 <wbr>- <wbr>LBFGS算法

    这样我么可以很容易的推导出当且仅当大规模优化算法 <wbr>- <wbr>LBFGS算法时候,第二项最小,由此得到最速下降法的迭代公式

    大规模优化算法 <wbr>- <wbr>LBFGS算法

    这里需要注意的是,最速下降方向仅仅是算法的局部性质,也就是说在局部它是一个下降最快的方向,并不是在全局上。在极值点附近,步长越小,前进越慢。

     

    3. 牛顿法(Newton method

     

    最速下降法采用的泰勒的一阶展开,而牛顿法采用的是泰勒二阶展开。

     大规模优化算法 <wbr>- <wbr>LBFGS算法

    其中s = x-x_k,将右边的式子最小化,就可以得到牛顿法的迭代公式

    大规模优化算法 <wbr>- <wbr>LBFGS算法

    对于正定的二次函数,牛顿法一步就可以达到最优解,也就是不用迭代,就是解析解。而对于非二次函数,牛顿法并不能保证经过有限次迭代就可以求得最优解。有一点是在极小点附近目标函数接近于二次函数,因此其收敛速度一般是快的(2阶收敛速度)。另外需要注意的是牛顿法需要计算二阶导也就是hesse 矩阵,因此需要较大的存储空间和计算量,在大规模的数值计算中直接使用牛顿法是不合适的。

     

    4. 共轭梯度法(Conjugate Gradient):共轭梯度法是介于GDNewton法之间的一个方法,它仅仅需要利用一阶导数的信息,克服了GD方法收敛慢的特点,由避免了计算和存储Hesse矩阵信息。其基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜素,求出目标函数的极小点。

     

     共轭:对于任意两个n维向量d1d2来说,如果对于对于一个n*n对称正定矩阵,满足大规模优化算法 <wbr>- <wbr>LBFGS算法则称d1d2G共轭的,同时它们也就是线性无关的。假设我们所要求的函数具有以下形式(这个形式和牛顿法的那个二阶展开是否很像,G是二阶导数矩阵,G正定 ?,这一点是BFGS算法的核心点,下面会提到)。

     大规模优化算法 <wbr>- <wbr>LBFGS算法


    导数矩阵为

    大规模优化算法 <wbr>- <wbr>LBFGS算法

    共轭梯度法关键点是如何找共轭的方向,同时保证函数下降。一般说来,基本的假设是当前的搜索方向是当前梯度和前面所有梯度的一个线性组合,这个假设在一定程度上是合理的:每一个下降方向都是和前面的相关的,并不是完全无关的。初始化一个d_0方向,根据这个假设可以得到:

     大规模优化算法 <wbr>- <wbr>LBFGS算法 

    其中beta就是关于上一方向的系数,而beta如何计算?我们如果有了一个对称的正定矩阵Gbeta可以由下面的公式来计算(由上式子,和共轭条件推导得来)

     大规模优化算法 <wbr>- <wbr>LBFGS算法 

    这样最后可以得到最终的共轭梯度法的计算公式:

     大规模优化算法 <wbr>- <wbr>LBFGS算法


    大规模优化算法 <wbr>- <wbr>LBFGS算法

     

    总结以下4个属性

    a. 同一点处的搜索方向与梯度的点积等于该点处的负梯度与梯度的点积,

    b. 某一点处的梯度与前面所有搜索方向的点积为0

    c. 某一点处的梯度与前面所有梯度的点积为0

    d . 某一点处的搜索方向与前面所有搜索方向共轭。

     

    在一个需要特别指出的一点:共轭梯度法只使用到了函数的一阶导数的,而没有涉及到二阶导数,在beta的计算中给消掉了,所以不用计算和存储Hesse矩阵了。但是共轭方法经过n步迭代之后,产生的新方向可能不再有共轭性,需要进一步的修正,比如从新取负梯度方向为下降方向等。

     

     

    5. 拟牛顿法(Quasi-Newton

     

    在牛顿法中,函数的Hesse矩阵实际上提供的是函数的曲率,但是计算Hesse矩阵在很多情况下并不是很方便的事情,在高纬的情况下,存在计算量大,需要较大的存储空间的问题,人们想到能不能不显示的计算Hesse矩阵,而是利用一个和Hesse矩阵的近似来替代它呢,这就是拟牛顿法的初衷也是它名字的由来。

     

    拟牛顿法的核心思想是:构造与Hesse矩阵相似的正定矩阵,而这个构造方法计算量比牛顿法小。其实可以发现上面讲的共轭梯度法也避免了Hesse矩阵的直接计算,一定程度上可以认为拟牛顿法是共轭梯度法的兄弟。

     

    首先将目标函数展成二阶的泰勒级数,(和3中的牛顿法的表示略有不同,只是为了后边书写的方便,其实是一样的)

     大规模优化算法 <wbr>- <wbr>LBFGS算法


    目标是推导一个G的近似,因此上面两边对x求导,可以得到

    大规模优化算法 <wbr>- <wbr>LBFGS算法

      大规模优化算法 <wbr>- <wbr>LBFGS算法可以得到 

    大规模优化算法 <wbr>- <wbr>LBFGS算法

    再变化一下,得到

    大规模优化算法 <wbr>- <wbr>LBFGS算法

    此处的H表示的是G的逆的近似,这个公式就是逆牛顿条件或者逆牛顿方程。同时我们也可以这样来写这个方程

    大规模优化算法 <wbr>- <wbr>LBFGS算法

    此处的B表示的就是G的近似,也是BFGS公式推导的一个基础。以上两个公式互为对偶。

    总结一下,如果我们使用H来替代原来牛顿方法中的G的逆,就变成了拟牛顿法。如何拟合H变成了重点。

    在拟牛顿法中有两个重要的方法,一个是DFPDavidonFletcherPowell三人的首字母)方法,由Davidon1959)提出,FeletherPowell1963)发展,一个就是BFGS方法。下面分别来讨论一下。

     

    6. 拟牛顿法 - DFP

     

    DFP算法的矫正公式为

     大规模优化算法 <wbr>- <wbr>LBFGS算法 

    这个公式是由对于矩阵的秩二矫正(rank two update)推导而来的,设uv为任意的n维向量,构造:

     大规模优化算法 <wbr>- <wbr>LBFGS算法

    带入拟牛顿条件可以得到:

    大规模优化算法 <wbr>- <wbr>LBFGS算法

     为了使得上述公式成立,做如下的构造:

     

    大规模优化算法 <wbr>- <wbr>LBFGS算法 大规模优化算法 <wbr>- <wbr>LBFGS算法

    这样公式就成立了,由此导出了DFP算法的矫正公式。

     

    7. 拟牛顿法 - BFGS

    到这里我们终于距离L-BFGS算法越来越接近了。关于BBFGS矫正公式如下

     大规模优化算法 <wbr>- <wbr>LBFGS算法


     

    利用两次Sharman-Morrison的逆的 rank one update就可以得到关于HBFGS矫正公式

     

    大规模优化算法 <wbr>- <wbr>LBFGS算法

     

    Sharman-Morrison 定理(如下式)是描述的如何求秩一校正后的矩阵的逆矩阵:

    大规模优化算法 <wbr>- <wbr>LBFGS算法

    其实B_k就是H_k的逆矩阵,利用这个定理可以对于BBFGS矫正公式的右端求逆矩阵,从而可以得到关于HBFGS矫正。


    8. L-BFGS算法

     

    在上述的BFGS算法的计算过程中,H_k逐渐的变得稠密,因此计算量逐渐正大。为了避免这个问题,LBFGS算法做了以下的改进:

    a) 在每一步估算hesse矩阵的近似的时候,给出一个当前的初始估计H0

    b) 利用过去的m-1次的曲率信息修正H0直到得到最终的Hesse矩阵。


    在关于HBFGS矫正中,令

    大规模优化算法 <wbr>- <wbr>LBFGS算法

    得到

    大规模优化算法 <wbr>- <wbr>LBFGS算法

     然后给定m,则迭代m+1次后得到此时的H

     大规模优化算法 <wbr>- <wbr>LBFGS算法

    写出H的最终表达式为

     大规模优化算法 <wbr>- <wbr>LBFGS算法 

    初始值由以下公式给出。

     大规模优化算法 <wbr>- <wbr>LBFGS算法

    L-BFGS算法的优点是,它不需要记忆H或者B这两个近似矩阵,而只需要存储{siyi}的一个序列,这样就大大节省了存储空间。

     

    9. @夏粉_百度 的几次讲座中都提到了LBFGS算法,并提到百度首创的Shooting算法,既然是和LBFGS算法比较的,相必也应该是从这个算法出发的,提出的一些改进。可以看到Shooting算法在初始的时候下降的非常快,收敛速度比LBFGS要快一些,具体怎么做的就不知道了。


    顺便提一下,LBFGS构造的H并不一定是最优的下降方向,但保证正定,也就是函数一定会下降,估计Shooting算法会在这个最优方向上做文章。

    大规模优化算法 <wbr>- <wbr>LBFGS算法

     

    10. 总结:


    从LBFGS算法的流程来看,其整个的核心的就是如何快速计算一个Hesse的近似:重点一是近似,所以有了LBFGS算法中使用前m个近似下降方向进行迭代的计算过程;重点二是快速,这个体现在不用保存Hesse矩阵上,只需要使用一个保存后的一阶导数序列就可以完成,因此不需要大量的存储,从而节省了计算资源;重点三,是在推导中使用秩二校正构造了一个正定矩阵,即便这个矩阵不是最优的下降方向,但至少可以保证函数下降。

     

    参考文献:

     

    1. 《最优化理论与方法》 袁亚湘 孙文瑜

     

    2.   http://blog.csdn.net/nocml/article/details/8287466

     

    3.  Updating Quasi-Newton Matrices with Limited Storage , Jorge Nocedal

     

    4.  Nonlinear Programming, second edition, Dimitri P. Bertsekas


    5. 《广告数据上的大规模机器学习》  夏粉

    展开全文
  • 在博文“优化算法——拟牛顿法之L-BFGS算法”中,已经对L-BFGS的算法原理做了详细的介绍,本文主要就开源代码liblbfgs重新回顾L-BFGS的算法原理以及具体的实现过程,在L-BFGS算法中包含了处理L1正则的OWL-QN算法,...

    在博文“优化算法——拟牛顿法之L-BFGS算法”中,已经对L-BFGS的算法原理做了详细的介绍,本文主要就开源代码liblbfgs重新回顾L-BFGS的算法原理以及具体的实现过程,在L-BFGS算法中包含了处理L1正则的OWL-QN算法,对于OWL-QN算法的详细原理,可以参见博文“优化算法——OWL-QN”。

    1、liblbfgs简介

    liblbfgs是L-BFGS算法的C语言实现,用于求解非线性优化问题。

    liblbfgs的主页:http://www.chokkan.org/software/liblbfgs/

    下载链接(见上面的主页链接):

    https://github.com/downloads/chokkan/liblbfgs/liblbfgs-1.10.tar.gz 用于Linux平台
    https://github.com/chokkan/liblbfgs
    用于Windows平台

    2、liblbfgs源码解析

    2.1、主要的结构

    在liblbfgs中,主要的代码包括

    • liblbfgs-1.10/include/lbfgs.h:头文件
    • liblbfgs-1.10/lib/lbfgs.c:具体的实现
    • liblbfgs-1.10/lib/arithmetic_ansi.h(另两个arithmetic_sse_double.harithmetic_sse_float.h是两个汇编编写的等价形式):相当于一些工具
    • liblbfgs-1.10/sample/sample.c:测试样例

    2.2、工具arithmetic_ansi.h

    arithmetic_ansi.h文件中,主要是对向量(vector)的一些操作,这部分的程序代码比较简单,在这里简单对没个函数的作用进行描述,包括:

    • 申请size大小的空间,同时对其进行初始化
    void* vecalloc(size_t size)
    • 释放空间
    void vecfree(void *memblock)
    • 将向量x中的值设置为c
    void vecset(lbfgsfloatval_t *x, const lbfgsfloatval_t c, const int n)
    • 将向量x中的值复制到向量y中
    void veccpy(lbfgsfloatval_t *y, const lbfgsfloatval_t *x, const int n)
    • 取向量x中的每个值的负数,将其放到向量y中
    void vecncpy(lbfgsfloatval_t *y, const lbfgsfloatval_t *x, const int n)
    • 对向量y中的每个元素增加向量x中对应元素的c倍
    void vecadd(lbfgsfloatval_t *y, const lbfgsfloatval_t *x, const lbfgsfloatval_t c, const int n)
    • 计算向量x和向量y的差
    void vecdiff(lbfgsfloatval_t *z, const lbfgsfloatval_t *x, const lbfgsfloatval_t *y, const int n)
    • 向量与常数的积
    void vecscale(lbfgsfloatval_t *y, const lbfgsfloatval_t c, const int n)
    • 向量的外积
    void vecmul(lbfgsfloatval_t *y, const lbfgsfloatval_t *x, const int n)
    • 向量的点积
    void vecdot(lbfgsfloatval_t* s, const lbfgsfloatval_t *x, const lbfgsfloatval_t *y, const int n)
    • 向量的点积的开方
    void vec2norm(lbfgsfloatval_t* s, const lbfgsfloatval_t *x, const int n)
    • 向量的点积的开方的倒数
    void vec2norminv(lbfgsfloatval_t* s, const lbfgsfloatval_t *x, const int n)

    2.3、L-BFGS算法的主要函数

    在liblbfgs中,有很多利用汇编语言优化的代码,这里暂且不考虑这些优化的代码,对于这些优化的代码,作者提供了基本的实现方式。

    2.3.1、为变量分配和回收内存空间

    函数lbfgs_malloc是为优化函数中的变量分配内存空间的函数,其具体形式为:

    // 为变量分配空间
    lbfgsfloatval_t* lbfgs_malloc(int n)
    {
    // 涉及到汇编的一些知识,暂且不考虑
    #if     defined(USE_SSE) && (defined(__SSE__) || defined(__SSE2__))
        n = round_out_variables(n);
    #endif/*defined(USE_SSE)*/
        // 分配n个大小的内存空间
        return (lbfgsfloatval_t*)vecalloc(sizeof(lbfgsfloatval_t) * n);
    }

    函数lbfgs_malloc用于为变量分配长度为n的内存空间,其中,lbfgsfloatval_t为定义的变量的类型,其定义为float或者是double类型:

    #if     LBFGS_FLOAT == 32
    typedef float lbfgsfloatval_t;
    
    #elif   LBFGS_FLOAT == 64
    typedef double lbfgsfloatval_t;
    
    #else
    #error "libLBFGS supports single (float; LBFGS_FLOAT = 32) or double (double; LBFGS_FLOAT=64) precision only."
    
    #endif

    与内存分配对应的是内存的回收,其具体形式为:

    // 释放变量的空间
    void lbfgs_free(lbfgsfloatval_t *x)
    {
        vecfree(x);
    }

    2.3.2、L-BFGS中参数的初始化

    函数lbfgs_parameter_init提供了L-BFGS默认参数的初始化方法。

    其实在L-BFGS的算法过程中也回提供默认的参数的方法,所以该方法有点多余。

    // 默认初始化lbfgs的参数
    void lbfgs_parameter_init(lbfgs_parameter_t *param)
    {
        memcpy(param, &_defparam, sizeof(*param));// 使用默认的参数初始化
    }

    函数lbfgs_parameter_init将默认参数_defparam复制到参数param中,lbfgs_parameter_t是L-BFGS参数的结构体,其具体的代码如下所示:

    作者在这部分代码中的注释写得特别详细,从这些注释中可以学习到很多调参时的重要信息。

    2.3.3、L-BFGS算法的核心过程概述

    函数lbfgs是优化算法的核心过程,其函数的参数为:

    int n,// 变量的个数
    lbfgsfloatval_t *x,// 变量
    lbfgsfloatval_t *ptr_fx,// 目标函数值
    lbfgs_evaluate_t proc_evaluate,// 计算目标函数值和梯度的回调函数
    lbfgs_progress_t proc_progress,// 处理计算过程的回调函数
    void *instance,// 数据
    lbfgs_parameter_t *_param// L-BFGS的参数

    该函数通过调用两个函数proc_evaluateproc_progress用于计算具体的函数以及处理计算过程中的一些工作。

    在函数lbfgs中,其基本的过程为:

    这里写图片描述

    2.3.4、参数的声明和初始化

    在初始化阶段涉及到很多参数的声明,接下来将详细介绍每一个参数的作用。

    2.3.5、循环求解的过程

    循环的求解过程从for循环开始,在for循环中,首先需要利用线搜索策略进行最优的步长选择,其具体的过程如下所示:

    /* Store the current position and gradient vectors. */
    // 存储当前的变量值和梯度值
    veccpy(xp, x, n);// 将当前的变量值复制到向量xp中
    veccpy(gp, g, n);// 将当前的梯度值复制到向量gp中
    
    /* Search for an optimal step. */
    // 线搜索策略,搜索最优步长
    if (param.orthantwise_c == 0.) {// 无L1正则
        ls = linesearch(n, x, &fx, g, d, &step, xp, gp, w, &cd, &param);// gp是梯度
    } else {// 包含L1正则
        ls = linesearch(n, x, &fx, g, d, &step, xp, pg, w, &cd, &param);// pg是伪梯度
        // 计算伪梯度
        owlqn_pseudo_gradient(
                    pg, x, g, n,
                    param.orthantwise_c, param.orthantwise_start, param.orthantwise_end
                    );
    }
    if (ls < 0) {// 已达到终止条件
        // 由于在线搜索的过程中更新了向量x和向量g,因此从xp和gp中恢复变量值和梯度值
        /* Revert to the previous point. */
        veccpy(x, xp, n);
        veccpy(g, gp, n);
        ret = ls;
        goto lbfgs_exit;// 释放资源
    }

    由于在线搜索的过程中会对变量x以及梯度的向量g修改,因此在进行线搜索之前,先将变量x以及梯度g保存到另外的向量中。参数param.orthantwise_c表示的是L1正则的参数,若为0则不使用L1正则,即使用L-BFGS算法;若不为0,则使用L1正则,即使用OWL-QN算法。

    关于线搜索的具体方法,可以参见2.3.6。
    对于owlqn_pseudo_gradient函数,可以参见2.3.4

    在OWL-QN中,由于在某些点处不存在导数,因此使用伪梯度代替L-BFGS中的梯度。

    2.3.6、循环的终止条件

    在选择了最优步长过程中,会同时对变量进行更新,第二步即是判断此时的更新是否满足终止条件,终止条件分为以下三类:

    • 是否收敛
    vec2norm(&xnorm, x, n);// 平方和的开方
    if (param.orthantwise_c == 0.) {// 非L1正则
        vec2norm(&gnorm, g, n);
    } else {// L1正则
        vec2norm(&gnorm, pg, n);
    }
    // 判断是否收敛
    if (xnorm < 1.0) xnorm = 1.0;
    if (gnorm / xnorm <= param.epsilon) {
        /* Convergence. */
        ret = LBFGS_SUCCESS;
        break;
    }

    收敛的判断方法为:

    |g(x)|max(1,|x|)<ε

    如果上式满足,则表示已满足收敛条件。

    • 目标函数值是否有足够大的下降(最小问题)
    if (pf != NULL) {// 终止条件
        /* We don't test the stopping criterion while k < past. */
        // k为迭代次数,只考虑past>k的情况,past是指只保留past次的值
        if (param.past <= k) {
            /* Compute the relative improvement from the past. */
            // 计算函数减小的比例
            rate = (pf[k % param.past] - fx) / fx;
    
            /* The stopping criterion. */
            // 下降比例是否满足条件
            if (rate < param.delta) {
                ret = LBFGS_STOP;
                break;
            }
        }
    
        /* Store the current value of the objective function. */
        // 更新新的目标函数值
        pf[k % param.past] = fx;
    }

    pf中,保存了param.past次的目标函数值。计算的方法为:

    fofnfn<Δ
    • 是否达到最大的迭代次数
    // 已达到最大的迭代次数
    if (param.max_iterations != 0 && param.max_iterations < k+1) {
        /* Maximum number of iterations. */
        ret = LBFGSERR_MAXIMUMITERATION;
        break;
    }

    如果没有满足终止的条件,那么需要拟合新的Hessian矩阵。

    2.3.7、拟合Hessian矩阵

    在BFGS算法(优化算法——拟牛顿法之BFGS算法)中,其Hessian矩阵为:

    Hk+1=(IskyTkyTksk)THk(IyksTkyTksk)+sksTkyTksk

    其中,yk=f(xk+1)f(xk)sk=xk+1xk。在计算的过程中,需要不断的计算和存储历史的Hessian矩阵,在L-BFGS算法,希望只保留最近的m次迭代信息,便能够拟合Hessian矩阵。在L-BFGS算法中,不再保存完整的Hk,而是存储向量序列{sk}{yk},需要矩阵时Hk,使用向量序列{sk}{yk}计算就可以得到,而向量序列{sk}{yk}也不是所有都要保存,只要保存最新的m步向量即可。其具体的计算方法为:

    这里写图片描述

    L-BFGS的具体原理可以参见“优化算法——拟牛顿法之L-BFGS算法”。

    在上述过程中,第一个循环计算出倒数第m代时的下降方向,第二个阶段利用上面计算出的方法迭代计算出当前的下降方向。

    根据上述的流程,开始拟合Hessian矩阵:

    • 计算向量序列{sk}{yk}
    // 更新s向量和y向量
    it = &lm[end];// 初始时,end0
    vecdiff(it->s, x, xp, n);// x - xp,xp为上一代的值,x为当前的值
    vecdiff(it->y, g, gp, n);// g - gp,gp为上一代的值,g为当前的值
    • 两个循环
    // 通过拟牛顿法计算Hessian矩阵
    // L-BFGS的两个循环
    j = end;
    for (i = 0;i < bound;++i) {
        j = (j + m - 1) % m;    /* if (--j == -1) j = m-1; */
        it = &lm[j];
        /* \alpha_{j} = \rho_{j} s^{t}_{j} \cdot q_{k+1}. */
        vecdot(&it->alpha, it->s, d, n);// 计算alpha
        it->alpha /= it->ys;// 乘以rho
        /* q_{i} = q_{i+1} - \alpha_{i} y_{i}. */
        vecadd(d, it->y, -it->alpha, n);// 重新修正d
    }
    
    vecscale(d, ys / yy, n);
    
    for (i = 0;i < bound;++i) {
        it = &lm[j];
        /* \beta_{j} = \rho_{j} y^t_{j} \cdot \gamma_{i}. */
        vecdot(&beta, it->y, d, n);
        beta /= it->ys;// 乘以rho
        /* \gamma_{i+1} = \gamma_{i} + (\alpha_{j} - \beta_{j}) s_{j}. */
        vecadd(d, it->s, it->alpha - beta, n);
        j = (j + 1) % m;        /* if (++j == m) j = 0; */
    }

    其中,ys和yy的计算方法如下所示:

    vecdot(&ys, it->y, it->s, n);// 计算点积
    vecdot(&yy, it->y, it->y, n);
    it->ys = ys;

    bound和end的计算方法如下所示:

    bound = (m <= k) ? m : k;// 判断是否有足够的m代
    ++k;
    end = (end + 1) % m;

    2.3.8、线搜索策略

    在liblbfgs中涉及到大量的线搜索的策略,线搜索的策略主要作用是找到最优的步长。我们将在下一个主题中进行详细的分析。

    补充

    1、回调函数

    回调函数就是一种利用函数指针进行函数调用的过程。回调函数的好处是具体的计算过程以函数指针的形式传递给其调用处,这样可以较方便地对调用函数进行扩展。

    假设有个print_result函数,需要输出两个int型数的和,那么直接写即可,如果需要改成差,那么得重新修改;如果在print_result函数的参数中传入一个函数指针,具体的计算过程在该函数中实现,那么就可以在不改变print_result函数的条件下对功能进行扩充,如下面的例子:

    • frame.h
    #include <stdio.h>
    
    void print_result(int (*get_result)(int, int), int a, int b){
        printf("the final result is : %d\n", get_result(a, b));
    }
    
    • process.cc
    #include <stdio.h>
    #include "frame.h"
    
    int add(int a, int b){
        return a + b;
    }
    
    int sub(int a, int b){
        return a - b;
    }
    
    int mul(int a, int b){
        return a * b;
    }
    
    int max(int a, int b){
        return (a>b?a:b);
    }
    
    int main(){
        int a = 1;
        int b = 2;
        print_result(add, a, b);
        print_result(sub, a, b);
        print_result(mul, a, b);
        print_result(max, a, b);
        return 1;
    }

    参考文献

    展开全文
  • 数值优化:理解L-BFGS算法

    千次阅读 2018-07-27 14:49:43
    译自《Numerical Optimization: Understanding L-BFGS》,本来只想作为学习CRF的补充材料,读完后发现收获很多,把许多以前零散的知识点都串起来了。对我而言,的确比零散地看论文要轻松得多。原文并没有太多关注...

    译自《Numerical Optimization: Understanding L-BFGS》,本来只想作为学习CRF的补充材料,读完后发现收获很多,把许多以前零散的知识点都串起来了。对我而言,的确比零散地看论文要轻松得多。原文并没有太多关注实现,对实现感兴趣的话推荐原作者的golang实现梯度.png

    数值优化是许多机器学习算法的核心。一旦你确定用什么模型,并且准备好了数据集,剩下的工作就是训练了。估计模型的参数(训练模型)通常归结为最小化一个多元函数f(x).png,其中输入CodeCogsEqn (3).png是一个高维向量,也就是模型参数。换句话说,如果你求解出:

    CodeCogsEqn (1).png

    那么CodeCogsEqn (3).png*就是最佳的模型参数(当然跟你选择了什么目标函数有关系)。 

    在这篇文章中,我将重点放在讲解L-BFGS算法的无约束最小化上,该算法在一些能用上批处理优化的ML问题中特别受欢迎。对于更大的数据集,则常用SGD方法,因为SGD只需要很少的迭代次数就能达到收敛。在以后的文章中,我可能会涉及这些技术,包括我个人最喜欢的AdaDelta 。

    注 : 在整个文章中,我会假设你记得多元微积分。所以,如果你不记得什么是梯度或海森矩阵,你得先复习一下。

    牛顿法

    大多数数值优化算法都是迭代式的,它们产生一个序列,该序列最终收敛于CodeCogsEqn (4).png,使得f(x).png达到全局最小化。假设,我们有一个估计屏幕快照 2016-08-11 下午8.10.12.png,我们希望我们的下一个估计屏幕快照 2016-08-11 下午8.11.00.png有这种属性:屏幕快照 2016-08-11 下午8.11.27.png

    牛顿的方法是在点屏幕快照 2016-08-11 下午8.10.12.png附近使用二次函数近似屏幕快照 2016-08-11 下午8.13.06.png。假设屏幕快照 2016-08-11 下午8.13.06.png是二次可微的,我们可以用屏幕快照 2016-08-11 下午8.13.06.png在点屏幕快照 2016-08-11 下午8.14.16.png的泰勒展开来近似屏幕快照 2016-08-11 下午8.13.06.png

    屏幕快照 2016-08-11 下午8.15.12.png

    其中,屏幕快照 2016-08-11 下午8.17.05.png屏幕快照 2016-08-11 下午8.17.24.png分别为目标函数屏幕快照 2016-08-11 下午8.13.06.png在点屏幕快照 2016-08-11 下午8.10.12.png处的梯度和Hessian矩阵。当屏幕快照 2016-08-11 下午8.18.28.png时,上面的近似展开式是成立的。你可能记得微积分中一维泰勒多项式展开,这是其推广。

    为了简化符号,将上述二次近似记为屏幕快照 2016-08-11 下午8.21.18.png,我们把生成屏幕快照 2016-08-11 下午8.21.18.png这样的二次近似的迭代算法中的一些概念简记如下:

    不失一般性,我们可以记屏幕快照 2016-08-11 下午8.19.33.png,那么上式可以写作:

    屏幕快照 2016-08-11 下午8.22.34.png

    其中屏幕快照 2016-08-11 下午8.23.12.png屏幕快照 2016-08-11 下午8.24.27.png分别表示目标函数在点屏幕快照 2016-08-11 下午8.10.12.png处的梯度和Hessian矩阵。

    我们想找一个屏幕快照 2016-08-11 下午8.32.42.png,使得屏幕快照 2016-08-11 下午8.13.06.png屏幕快照 2016-08-11 下午8.10.12.png的二次近似最小。上式对屏幕快照 2016-08-11 下午8.32.42.png求导:

    屏幕快照 2016-08-11 下午8.35.10.png

    任何使得屏幕快照 2016-08-11 下午8.38.01.png屏幕快照 2016-08-11 下午8.38.31.png都是屏幕快照 2016-08-11 下午8.38.53.png的局部极值点,如果我们假设屏幕快照 2016-08-11 下午8.13.06.png是凸函数,则屏幕快照 2016-08-11 下午8.24.27.png正定的,那么局部极值点就是全局极值点(凸二次规划)。

    解出屏幕快照 2016-08-11 下午8.38.31.png

    屏幕快照 2016-08-11 下午8.54.55.png

    这就得到了一个很好的搜索方向,在实际应用中,我们一般选择一个步长α,即按照下式更新屏幕快照 2016-08-11 下午8.11.00.png

    屏幕快照 2016-08-11 下午8.58.16.png

    使得屏幕快照 2016-08-11 下午8.59.06.png相比f(x).png的减小量最大化。

    迭代算法伪码:

    屏幕快照 2016-08-11 下午9.03.34.png

    步长α的确定可以采用任何line search算法,其中最简单的一种是backtracking line search。该算法简单地选取越来越小的步长α,直到屏幕快照 2016-08-11 下午8.13.06.png的值小到满意为止。关于line search算法的详情请参考Line Search Methods.pdfLecture 5- Gradient Descent.pdf

    在软件工程上,我们可以将牛顿法视作实现了下列Java接口的一个黑盒子:

    
     
    1. public interface TwiceDifferentiableFunction
    2. {
    3.     // compute f(x)
    4.     double valueAt(double[] x);
    5.  
    6.     // compute grad f(x)
    7.     double[] gradientAt(double[] x);
    8.  
    9.     // compute inverse hessian H^-1
    10.     double[][] inverseHessian(double[] x);
    11. }

    如果你有兴趣,你还可以通过一些枯燥无味的数学公式,证明对任意一个凸函数,上述算法一定可以收敛到一个唯一的最小值屏幕快照 2016-08-11 下午9.54.52.png,且不受初值屏幕快照 2016-08-11 下午9.55.27.png的影响。对于非凸函数,上述算法仍然有效,但只能保证收敛到一个局部极小值。在上述算法于非凸函数的实际应用中,用户需要注意初值的选取以及其他算法细节。

    巨大的海森矩阵

    牛顿法最大的问题在于我们必须计算海森矩阵的逆。注意在机器学习应用中,屏幕快照 2016-08-11 下午8.13.06.png的输入的维度常常与模型参数对应。十万维度的参数并不少见(SVM中文文本分类取词做特征的话,就在十万这个量级),在一些图像识别的场景中,参数可能上十亿。所以,计算海森矩阵或其逆并不现实。对许多函数而言,海森矩阵可能根本无法计算,更不用说表示出来求逆了。

    所以,在实际应用中牛顿法很少用于大型的优化问题。但幸运的是,即便我们不求出屏幕快照 2016-08-11 下午8.13.06.png屏幕快照 2016-08-11 下午8.10.12.png的精确屏幕快照 2016-08-12 下午8.38.44.png,而使用一个近似的替代值,上述算法依然有效。

    拟牛顿法

    如果不求解屏幕快照 2016-08-11 下午8.13.06.png屏幕快照 2016-08-11 下午8.10.12.png的精确屏幕快照 2016-08-12 下午8.38.44.png,我们要使用什么样的近似呢?我们使用一种叫QuasiUpdate的策略来生成屏幕快照 2016-08-12 下午8.38.44.png的近似,先不管QuasiUpdate具体是怎么做的,有了这个策略,牛顿法进化为如下的拟牛顿法:

    屏幕快照 2016-08-12 下午8.50.21.png

    跟牛顿法相比,只是把屏幕快照 2016-08-12 下午8.38.44.png的计算交给了QuasiUpdate。为了辅助QuasiUpdate,计算了几个中间变量。QuasiUpdate只需要上个迭代的屏幕快照 2016-08-12 下午8.38.44.png、输入和梯度的变化量(屏幕快照 2016-08-12 下午8.54.12.png屏幕快照 2016-08-12 下午8.54.18.png)。如果QuasiUpdate能够返回精确的屏幕快照 2016-08-12 下午8.57.16.png的逆,则拟牛顿法等价于牛顿法。

    在软件工程上,我们又可以写一个黑盒子接口,该接口不再需要计算海森矩阵的逆,只需要在内部更新它,再提供一个矩阵乘法的接口即可。事实上,内部如何处理,外部根本无需关心。用Java表示如下:

    
     
    1. public interface DifferentiableFunction
    2. {
    3.     // compute f(x)
    4.     double valueAt(double[] x);
    5.  
    6.     // compute grad f(x)
    7.     double[] gradientAt(double[] x);
    8. }
    9.  
    10. public interface QuasiNewtonApproximation
    11. {
    12.     // update the H^{-1} estimate (using x_{n+1}-x_n and grad_{n+1}-grad_n)
    13.     void update(double[] deltaX, double[] deltaGrad);
    14.     
    15.     // H^{-1} (direction) using the current H^{-1} estimate
    16.     double[] inverseHessianMultiply(double[] direction);
    17. }

    注意我们唯一用到海森矩阵的逆的地方就是求它与梯度的乘积,所以我们根本不需要在内存中将其显式地、完全地表示出来。这对接下来要阐述的L-BFGS特别有用。如果你对实现细节感兴趣,可以看看作者的golang实现。

    近似海森矩阵

    QuasiUpdate到底要如何近似海森矩阵呢?如果我们让QuasiUpdate忽略输入参数,直接返回单位矩阵,那么拟牛顿法就退化成了梯度下降法了,因为函数减小的方向永远是梯度屏幕快照 2016-08-11 下午8.17.05.png。梯度下降法依然能保证凸函数屏幕快照 2016-08-11 下午8.13.06.png收敛到全局最优对应的CodeCogsEqn (4).png,但直觉告诉我们,梯度下降法没有利用到屏幕快照 2016-08-11 下午8.13.06.png的二阶导数信息,收敛速度肯定更慢了。

    我们先把屏幕快照 2016-08-11 下午8.13.06.png的二次近似写在下面,从这里找些灵感。

    屏幕快照 2016-08-11 下午8.22.34.png

    Secant Condition

    屏幕快照 2016-08-12 下午9.28.30.png的一个性质是,它的梯度与屏幕快照 2016-08-11 下午8.13.06.png屏幕快照 2016-08-11 下午8.10.12.png处的梯度一致(近似函数的梯度与原函数的梯度一致,这才叫近似嘛)。也就是说我们希望保证:

    屏幕快照 2016-08-12 下午9.31.14.png

    我们做个减法:

    屏幕快照 2016-08-12 下午9.33.53.png

    由中值定理,我们有:

    屏幕快照 2016-08-12 下午9.37.12.png

    这个式子就是所谓的Secant Condition,该条件保证屏幕快照 2016-08-12 下午9.49.21.png至少对屏幕快照 2016-08-12 下午9.50.06.png而言是近似海森矩阵的。

    等式两边同时乘以屏幕快照 2016-08-12 下午8.38.44.png,并且由于我们定义过:

    屏幕快照 2016-08-12 下午9.39.06.png

    于是我们得到:

    屏幕快照 2016-08-12 下午9.40.50.png

    对称性

    由定义知海森矩阵是函数的二阶偏导数矩阵,即屏幕快照 2016-08-12 下午9.44.57.png,所以海森矩阵一定是对称的。

    BFGS更新

    形式化地讲,我们希望屏幕快照 2016-08-11 下午8.24.27.png至少满足上述两个条件:

    1. 屏幕快照 2016-08-12 下午8.54.12.png屏幕快照 2016-08-12 下午8.54.18.png而言满足Secant Condition

    2. 满足对称性

    给定上述两个条件,我们还希望屏幕快照 2016-08-11 下午8.24.27.png相较于屏幕快照 2016-08-12 下午9.53.27.png的变化量最小。这类似“ MIRA 更新”,我们有许多满足条件的选项,但我们只选那个变化最小的。这种约束形式化地表述如下:

    屏幕快照 2016-08-12 下午9.55.33.png

    上面的范数屏幕快照 2016-08-12 下午9.57.15.png表示weighted frobenius norm。这个约束最小化问题的解是:

    屏幕快照 2016-08-12 下午9.59.02.png

    式中屏幕快照 2016-08-12 下午10.00.37.png。我不知道如何推导它,推导的话需要用很多符号,并且费时费力。

    这种更新算法就是著名的Broyden–Fletcher–Goldfarb–Shanno (BFGS)算法,该算法是取发明者名字的首字母命名的。

    bfgs.png

    关于BFGS,有一些需要注意的点:

    • 只要屏幕快照 2016-08-12 下午8.38.44.png是正定的,屏幕快照 2016-08-12 下午10.11.17.png就一定是正定的。所以我们只需要选择一个正定的屏幕快照 2016-08-12 下午10.13.05.png即可,甚至可以选择单位矩阵。

    • 屏幕快照 2016-08-12 下午8.38.44.png屏幕快照 2016-08-12 下午10.11.17.png还存在简单的算术关系,给定屏幕快照 2016-08-12 下午10.11.17.png屏幕快照 2016-08-12 下午8.54.12.png屏幕快照 2016-08-12 下午8.54.18.png,我们就能倒推出屏幕快照 2016-08-12 下午8.38.44.png

    把这些知识放到一起,我们就得出了BFGS更新的算法,给定方向d,该算法可以计算出屏幕快照 2016-08-12 下午10.17.59.png,却不需要求屏幕快照 2016-08-12 下午8.38.44.png矩阵,只需要按照上述表达式不断地递推即可:

    屏幕快照 2016-08-12 下午10.19.22.png

    由于屏幕快照 2016-08-12 下午8.38.44.png的唯一作用就是计算屏幕快照 2016-08-12 下午10.21.08.png,我们只需用该更新算法就能实现拟牛顿法。

    L-BFGS:省内存的BFGS

    BFGS拟牛顿近似算法虽然免去了计算海森矩阵的烦恼,但是我们仍然需要保存每次迭代的屏幕快照 2016-08-12 下午8.54.12.png屏幕快照 2016-08-12 下午8.54.18.png的历史值。这依然没有减轻内存负担,要知道我们选用拟牛顿法的初衷就是减小内存占用。

    L-BFGS是limited BFGS的缩写,简单地只使用最近的m个屏幕快照 2016-08-12 下午8.54.12.png屏幕快照 2016-08-12 下午8.54.18.png记录值。也就是只储存屏幕快照 2016-08-12 下午10.29.13.png屏幕快照 2016-08-12 下午10.29.32.png,用它们去近似计算屏幕快照 2016-08-12 下午10.21.08.png。初值屏幕快照 2016-08-12 下午10.30.56.png依然可以选取任意对称的正定矩阵。

    L-BFGS改进算法

    在实际应用中有许多L-BFGS的改进算法。对不可微分的函数,可以用 othant-wise 的L-BFGS改进算法来训练屏幕快照 2016-08-12 下午10.34.38.png正则损失函数。

    不在大型数据集上使用L-BFGS的原因之一是,在线算法可能收敛得更快。这里甚至有一个L-BFGS的在线学习算法,但据我所知,在大型数据集上它们都不如一些SGD的改进算法(包括 AdaGrad 或 AdaDelta)的表现好。

    Reference

    http://aria42.com/blog/2014/12/understanding-lbfgs

     

    展开全文
  • 牛顿法与拟牛顿法学习笔记(五)L-BFGS 算法

    万次阅读 多人点赞 2014-03-24 00:53:27
    机器学习算法中经常碰到非线性优化问题,...在具体实现中,大多调用的是成熟的软件包做支撑,其中最常用的一个算法是 L-BFGS。为了解这个算法的数学机理,这几天做了一些调研,现把学习过程中理解的一些东西整理出来。
  • L-BFGS

    千次阅读 2018-07-26 20:30:03
    L-BFGS L-BFGS算法比较适合在大规模的数值计算中,具备牛顿法收敛速度快的特点,但不需要牛顿法那样存储Hesse矩阵,因此节省了大量的空间以及计算资源。本文主要通过对于无约束最优化问题的一些常用算法总结,一...
  • L-BFGS算法介绍

    千次阅读 2018-12-14 16:15:00
    一、 L-BFGS是什么L-BFGS是解无约束非线性规划问题最常用的方法,具有收敛速度快、内存开销少等优点,在机器学习各类算法中常有它的身影。简单的说,L-BFGS和梯度下降、SGD干的同样的事情,但大多数情况下收敛速度...
  • L-BFGS剖析

    万次阅读 2018-04-04 15:37:22
    机器学习中经常利用梯度下降法求最优解问题,通过大量的迭代来得到最优解,但是对于维度较多的数据,除了占用大量的内存还会很耗时,L-BFGS算法是一种在牛顿法基础上提出的一种求解函数根的算法,下面由简入深尽量用...
  • L-BFGS的MATLAB代码

    热门讨论 2011-07-23 21:45:34
    l-bfgs的程序代码,优点是对存储器的要求小,并且运算速度飞快
  • spark mllib源码分析之L-BFGS(一)

    千次阅读 2017-07-05 19:53:48
    简要介绍L-BFGS的原理,分析spark中L-BFGS的源码实现,这是第一部分
  • 机器学习优化算法—L-BFGS

    千次阅读 2014-11-27 09:53:21
    L-BFGS算法由于其高效的性能而被广泛运用在实际工程中,本文首先介绍L-BFGS算法和其它算法的比较,然后详细介绍该算法的主要思想以及每一步迭代时近似矩阵的更新细节。
  • L-BFGS-B的代码,是一种基于梯度的非线性优化方法。
  • 对抗样本(二)L-BFGS

    2020-02-29 14:33:52
    文章目录一、论文相关信息  1.论文题目  2.论文时间  3.论文文献二、论文背景及简介三、论文所使用的符号及数据等信息四、论文主要内容1、第一个特征 神经元的语义信息2、第二个特征 神经网络的盲点五、实验...
  • 最近做的科研项目需要用到L-BFGS,这段时间看了不少关于L-BFGS的博客以及论文,在此进行一下小小的总结。在无约束优化问题中,牛顿法及拟牛顿法是常用的方法,L-BFGS属于拟牛顿法,下面从牛顿法开始说起。牛顿法,...
  • L-BFGS优化算法

    千次阅读 2015-11-02 14:40:56
    关于优化算法的求解,书上已经介绍了很多的方法,比如有梯度下降法,坐标下降法,牛顿法和拟牛顿法。梯度下降法是基于目标函数梯度的,算法的收敛速度是线性的,并且当问题是病态时或者问题规模较大时,收敛速度尤其...
  • 译自《Numerical Optimization: Understanding L-BFGS》,本来只想作为学习CRF的补充材料,读完后发现收获很多,把许多以前零散的知识点都串起来了。对我而言,的确比零散地看论文要轻松得多。原文并没有太多关注...
  • 线性收敛的随机L-BFGS算法

    千次阅读 2018-04-27 21:28:38
    线性收敛的随机L-BFGS算法 以下皆为翻译A Linearly-Convergent Stochastic L-BFGS Algorithm 原文链接 六级没过,莫怪 概要 我们提出了一个新的随机L-BFGS算法,并证明其对强凸连续函数可以达到线性收敛.我们的...
  • 数值最优化:理解L-BFGS

    千次阅读 2016-05-07 11:35:58
    数值最优化:理解L-BFGS 数值最优化是很多机器学习中的核心,一旦你已经选定了模型和数据集,那么就需要数值最优化方法去最小化多元函数 f(x)f(x),从而估计出模型的参数: x∗=argminxf(x)x∗=arg⁡minxf(x) ...
  • 这个函数可以从UFLDL网站上下载,其好处是在用10000个样本优化30多万个参数时内存不溢出,比网站上所用的minFunc函数好。我下载后整理了一下,翻译了注释,行数从800多行压倒660行
  • L-BFGS算法和神经网络

    2017-02-20 01:22:17
    各位大哥,,, 我想问一下 这个L-BFGS算法的可以跟神经网络结合用于对传感器采集的数据进行数据融合么? 麻烦您有时间的话看下 谢谢大家
  • method = 'L-BFGS-B', options = {'maxiter': 50000, 'maxfun': 50000, 'maxcor': 50, 'maxls': 50, 'ftol' : 1.0 * np.finfo(float).eps}) ...
  • 来源:星环科技数据猿官网 | www.datayuan.cn今日头条丨一点资讯丨腾讯丨搜狐丨网易丨凤凰丨阿里UC大鱼丨新浪微博丨新浪看点丨百度百家丨博客中国丨趣头条丨腾讯...
  • Intriguing properties of neural network(Box-constrained L-BFGS)论文简述semantic meaning of individual units先前工作作者观点验证方法思考思考 论文简述 本篇论文首先提出了对抗样本(Adversarial example...
  • 【题目】【SciPy库】scipy.optimize.fmin_l_bfgs_b进行L-BFGS优化 具体用法参考官方文档:scipy.optimize.fmin_l_bfgs_b x,min_val,info=scipy.optimize.fmin_l_bfgs_b(func, x0, fprime=None, args=(), approx_...
  • 在了解CRF推导与参数估计的时候,会用到收敛优化方法去迭代求解凸优化问题,至此,总结一下我对牛顿法、BFGS算法和L-BFGS算法这三种方法的理解。
  • L-BFGS 算法

    2018-02-13 14:55:33
    机器学习算法中经常碰到非线性优化问题,...在具体实现中,大多调用的是成熟的软件包做支撑,其中最常用的一个算法是 L-BFGS。为了解这个算法的数学机理,这几天做了一些调研,现把学习过程中理解的一些东西整理出来。...

空空如也

1 2 3 4 5 ... 20
收藏数 8,670
精华内容 3,468
关键字:

l-bfgs