冰冰点灯,照亮我家门前~
欢迎进入nnetinfo
用户名:
密码:
深圳学习数据分析,数据挖掘,请联系yahushuxue@163.com~
nnetinfo : 本网发布神经网络相关的学习与研讨内容。
当前位置:教学区
Levenberg-Marquardt法理论基础
作者:xiaoH   日期:2015-11-24 19:39:15.0

Levenberg-Marquardt(列文伯格-马跨特)法就是matlab工具箱中默认的训练方法---trainlm法

我们先看二次最小均方问题的表达式:

                                           (注意:这里的x是向量)

矩阵形式:

                                                             f(x)和x都是列向量。

       目前,还没找到什么好的方法求它的全局最小解,所以一般都使用搜索算法:先初始化一个解,然后根据算法找到一个让F下降的方向,将解沿下降的方向移动,得到新的解。通过n轮迭代后,最终得到一个局部最优解。

        搜索算法一般有两个问题:1.怎么找到下降方向。2.每次沿下降方向移动的步长大小。这里着重讨论下降方向的寻找。

        假设我们当前位置为 x, 企图找到一个让 F 下降的方向,现在让我们研究一下 x 附近的情况,研究函数附近的情况,自然使用泰勒展式。

 

一.梯度下降法

        为了简单起见,先使用泰勒展式的第一项(线性主部),即

      F(x+h) = F(x) + F(x)’h

        可以发现,h = - F( x )’的时候,F 是下降得最快的,这就是我们熟悉的梯度下降法,也叫极速下降法。

        梯度下降法有个很大的缺点,就是离极小点很近的时候,梯度经常变得非常小,于是收敛到极小点就很慢。(例如函数 y = x *x,dx 等于 x,x 越接近 0,dx 也越接近 0,使得每次移动的步子非常小。)

 

二.牛顿法

        我们都知道,梯度下降法只考虑了一阶展开,已被证明,它在接近极小值时,只是一阶收敛(指收敛速度)。因此,我们想要得到更快的收敛速度,就要得到更“长远”一些的眼光,就需要考虑它的二阶,

                                       

可以看出,实际它是用一个二次曲面去迫近F(x)在x这一点附近的情况。

二次曲面是有极值的,我们就取指向极值的方向作为下降方向,这样比梯度法更具有全局性。我们求下指向极值的方向,我们令它的导数为0:

           

由最后一个等号就可以得到指向曲面极值的方向:

                                           h = (  F''( x) )-1 *( -F'( x ))

       这里重温一下牛顿法求零点法:初始化一个点作为解,求该点的切线(切平面),将解更新到切线与x轴的交点上,不断以此法迭代,直到满足退出条件。

       而二次最小均方问题,可以转化为求原问题导数的零点,既然是求零点,就可用牛顿法。

       实际上仔细观察下,上面的方法就是牛顿法。

 

三.高斯-牛顿法

      上面的牛顿法已经考虑到两阶的情况了,但是求 h 时需要求二阶导数,这个非常不好求,所以有人动了下脑筋,因为我们的目标函数是均方误差,里面带有平方这个运算了,那

么何不直接在f(x)展开成一阶,经过平方后,不就保留了二阶的部分信息吗?

我们先看x的维度和样本数m都为1的情况:

                                             

f的一阶泰勒展开:

                                   

那么

                             

      可以看到,已经有 h 的平方项了,这曲面虽然没有原来求二阶导那么准确,但总算凑出来了,至少比只有线性主部要强一些。接下来如牛顿法一样,令导数为0即可求出指向曲面极值的方向。

 

      上面是 x 的维度和样本数 m 都为1的情况,下面给出一般情况(x为多维,m也为多维)时的矩阵表达形式:

 

                                     

其中f(x)和x都是向量

 

                                         

在神经网络里 fi( x)代表第 i 个样本的拟合误差。

对 f( x) 取一阶展开:

 

                                   

其中J是雅克比矩阵:

                      

那么

                         

令上式导数为0,

                               

即可求得

                                 

其中 JTf 实际就是梯度:

                               

下面证明h能够使F下降:

                                

       所以,当 JTJ 是正定时,hJTJh > 0,那么 -hJTf = - hF'(x)也大于0,即 hF'( x) 小于0,说明 h 是个下降的方向。

       这就是高斯-牛顿法。

      经过重重基础知识铺垫,下面终于可以讲述本文的目标---列文伯格-马跨特法了。

 

四.列文伯格-马跨特(LM)法

列文伯格-马跨特提出,将高斯-牛顿法与梯度下降法结合。

那么只需要这样改进:

                            

那么,

(1) 当u很大的时候,上式近似于 ,它相当于一个梯度下降,

(2 )当u很小的时候,上式近似于,相当于高斯牛顿法。

 然后通过一些机制,去调整u的大小,来使距离解较远的时候,使用梯度下降法,距离极小值较近的时候,使u减小,这样就近似高斯牛顿法,能得到比梯度下降法更快的收敛速度。

牛顿-高斯法是利用了目标函数里的平方运算,列文伯格-马跨特法又是建立在牛顿-高斯法的基础,到这里,我们已经明白,列文伯格-马跨特法是专门针对二次均方最小值问题的,若果神经网络换了其它目标函数,那么LM法就不一定适用了。

 这就是列文伯格-马跨特(Levenberg-Marquardt)法。

 

五.关于mu

   下面给出matlab神经网络工具箱中,关于mu的自适应机制的伪代码:

%matlab神经网络工具箱里,trainlm法的mu的自适应代码。
%本代码是伪代码,仅为提供思路。
%本代码来自《神经网络之家》www.nnetinfo.com。

while (1)      
    Jmat = getJmat();  %计算雅克比矩阵
    je   = Jmat * e';      %JF
    jj   = Jmat * Jmat'; %JJ
    while (mu <= mu_max)
        dX   = -(jj + ii*mu) \ je; %计算当前mu下的dx
        newX = X + dX;           %当前mu下的新解newX
        [newE] = cal(newX);      %计算当前误差
        if (newE < E)            %若果误差比之前更小
            X = newX;            %则接受newX作为X
            mu =max(mu * mu_dec,1e-20);%下降mu
            break;
        end
        mu = mu * mu_inc;         %否则增大mu,使它更接近梯度下降法
    end
 
    if ('终止条件') %判断是否终止
        break; %若是,则退出训练
    end  
end

 

六.相关阅读

本文大部分借鉴于文献《methods for non-linear least squares problems》,有兴趣的同学可以直接阅读文献。

然后推荐沈乐君老师的《Levenberg-Marquardt快速入门教程(荐)》, 《Levenberg-Marquardt最优化C++源码(OpenCV版)》

 

后语

        很久以前就在使用matlab神经网络工具箱中的trainlm法,直到工作,才弄明白了它的原理,感觉到的确是一种不错的方法(怪不得matlab神经网络工具箱会将它作为默认的训练算法),然后综合自己的看法,写了这篇文章,希望对大家有所帮助。

 

=============<原创文章,转载请说明来自神经网络之家www.nnetinfo.com >     ========

=========<转载请保留本文的地址:http://nnetinfo.com/nninfo/showText.jsp?id=42>======