标签归档：非线性最小二乘

Levenberg-Marquardt算法

发表评论

匆匆一更。还没写完，对不起我太懒了T_T

版权声明：原创作品，欢迎转载，但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明，否则将追究法律责任。

Levenberg-Marquardt算法（下文简称LM算法）通常用于非线性最小二乘法的目标函数极小化。这是一个置信域方法（Trust-Region Method），为了防止步长太大而跳到非预期的局部极小值，这类算法自适应的调整步长。

假设f(x)为一个向量函数，每个分量都刻画了一个样本和模型预测之间的某种偏差，则非线性最小二乘目标函数为

(1)   \begin{eqnarray*} E&=&\transp{f}f \end{eqnarray*}

通常基于梯度的数值极小化算法，都是用一点的局域特征（如导数）建立该函数变化趋势的模型，以此来推测一个最可取的下降方向和步长。取一阶导数近似是线性模型，用切平面来近似函数在该点附近的变化趋势；取到二阶导数近似则是二阶模型，用一个抛物面来近似。当然，也可以取到更多阶，模型的几何直观也会越来越复杂，越来越精确的逼近真实的函数变化趋势，但是会付出更大的计算代价。当取到无穷阶时，模型在级数收敛区间内可以做到完全精确的刻画函数，此时这就是模型就是函数的泰勒展开了。

我们把f在任一点x附近展开f(x+\delta x)=f(x)+J(x)\delta x,这样E在x附近就是

(2)   \begin{eqnarray*} E(x+\delta x)&=&|f(x)+J(x)\delta x)|^2\\ &=&|f|^2+2\transp{f}J(x)\delta x + |J(x)\delta x|^2 \end{eqnarray*}

注意J是f而非E的导数，这里我们得到了E的二阶展开，即用一个抛物面来近似目标函数E在一点附近的形态。这个二阶模型显然是一个线性最小二乘问题——这正是我们所要的，把一个非线性最小二乘问题转换为一系列线性最小二乘问题来求解。

因此一个简单直接的想法就是，每一迭代步构造这样一个线性最小二乘问题，通过极小化它下降到下一个迭代点，循环直到收敛。但这个方案显然有问题。我们的二阶展开模型只能在一个小邻域上有效，当\delta x增大时，被我们忽略掉的高阶项就会越来越明显，最后让二阶模型彻底失效。这样，直接根据二阶模型计算出来的迭代点对目标函数而言可能并非我们想要的，它的函数值可能比上一点还要高（因而目标函数不降反增）；也可能尽管比上一点下降了但是却跳到了另一个我们不想要的凸区域里（因而算法会收敛到离初始猜测解更远的局部极小值点上）；更严重的情况，模型甚至可能是退化的，即一种极端形式的抛物面——就像一本被半卷起的书，此时我们在弯折的方向仍能找到极小值，但在其垂直方向已经无法找到极小值（或者说处处极小）。

为了解决以上问题，我们需要给模型加入一些约束，把迭代步长约束在一个合理的范围内，保证在这个范围内模型足够有效。同时，我们也希望在二阶模型退化的时候，约束能够拯救它，保证算法总能求出一个极小值。这个约束很简单，如下

(3)   \begin{eqnarray*} E(x+\delta x)&=&|f(x)+J(x)\delta x)|^2 + \lambda |C(x)\delta x|^2 \end{eqnarray*}

我们加入了一个二次约束项。单独看该项，它是一个中心在x点，开口向上的抛物面，或者说一个二次势阱。这个势阱像一个箍，把\delta x箍在x点附近的小邻域中。通过调节\lambda可以增强或减弱它对\delta x的约束：当\lambda充分大时，约束项成为主要贡献项，这时模型总有一个极小值，且步长较小；当\lambda较小时，约束项几乎可以忽略，算法以大步长快速往极小值接近。

再来看矩阵C(x). 这个矩阵通常被设置为对角的。此时，

(4)   \begin{eqnarray*} |C(x)\delta x|^2 &=& \transp{\delta x}\transp{C}C\delta x\\ &=&\sum_{i} \lambda_i \delta x_i^2 \end{eqnarray*}

\transp{C}C的本征值控制着每个方向上抛物面上升的快慢。可见，如果一个方向相应的本征值被设置的较小，那么该方向的约束项上升缓慢，约束较弱，步长跨度较大；否则反之。现实中使用的模型，目标函数对于各个参数的敏感度不同，有的参数略微调整就可以导致目标函数的强烈变化，有的则反之。C(x)这个参数矩阵使得我们可以针对各个不同的参数设置不同程度的步长约束，从而能够构造出一个稳定的算法。

（未完待补）