Levenberg-Maquardt Algorithm 推導(dǎo)

前置知識

1. 牛頓法

作用：1. 求根 2.求極值

求根

目標(biāo): 求解 $f(y)=0$ 的根

計算穿過初始點 $(x_0,f(x_0))$ 并且斜率為 $f'(x)$ 的直線與x軸的交點可得

? $0=(x-x_0)f'(x_0)+f(x_0)$

迭代公式： $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_{n})}$
求解一維無約束最小值

目標(biāo): 求解 $min f(x) , x\in R$ 的根

牛頓法也可用來求解函數(shù)的極值空入。極值點是導(dǎo)數(shù)為0，可用牛頓法求導(dǎo)數(shù)的零點。

$f(x+\Delta)$ 的二階泰勒展開為 $f(x+\Delta)=f(x)+f'(x)\Delta+\frac{1}{2}f''(x)\Delta^2$

求解 $\frac{\partial f(x+\Delta)}{ \partial \Delta}=0$

可得 $f'(x)+f''(x)\Delta=0$
? $\Delta=-\frac{f'(x_n)}{f''(x_{n})}$

迭代公式： $x_{n+1}=x_n-\frac{f'(x_n)}{f''(x_{n})}$
求解高維無約束最小值

高維情況下泰勒二階展開為

? $f(\mathbf x+\mathbf \Delta)=f(\mathbf x)+\nabla f(\mathbf x)\Delta+\frac{1}{2}\Delta ^TH(f(\mathbf x))\Delta$

因此迭代公式： $x_{n+1}=x_n-[H(f(x_n))]^{-1}\nabla f(x)$

優(yōu)點

牛頓法是二階收斂，比一般梯度下降法更快收斂竞阐，特別是當(dāng)初始點距離目標(biāo)足夠靠近摸航。

缺點

應(yīng)用求極值的時候需要目標(biāo)函數(shù)二次可微，而梯度下降法只需要可微
需要 $Hessian$ 矩陣正定铜邮，遇到 $f$ 的極值點仪召，或者初始點距離目標(biāo)遠時候可能無法收斂
每次迭代需要求 $Hessian$ 的逆矩陣，運算量非常大

2. 高斯-牛頓法

作用：降低牛頓法的計算量松蒜，提高計算效率

最小二乘法問題

對于向量函數(shù) ${\bf f}:R^m\to R^n,m\ge n$

最小化 $||f(x)||$ 或者找到 $x^*=argmin_x\{F(x)\}$

這里 $F(x)=\frac{1}{2}\sum_{i=1}^m(f_i(x))^2=\frac{1}{2}{\bf f}({\bf x})^T{\bf f}({\bf x})$

牛頓法推導(dǎo)

已知牛頓法迭代公式： $x_{n+1}=x_n-[H(f(x_n))]^{-1}\nabla f(x)$

$F(x)$ 的梯度 $\nabla F(x)=\begin{bmatrix}\frac{\partial (\frac{1}{2}\sum_{i=1}^m(f_i(x))^2)}{\partial x_1}\\\vdots\\\frac{\partial (\frac{1}{2}\sum_{i=1}^m(f_i(x))^2)}{\partial x_n}\end{bmatrix}=\begin{bmatrix}\sum_{i=1}^{m}f_i\frac{\partial f_i}{\partial x_1}\\\vdots\\\sum_{i=1}^{m}f_i\frac{\partial f_i}{\partial x_n} \end{bmatrix}= \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \cdots & \frac{\partial f_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial f_m}{\partial x_1} & \cdots & \frac{\partial f_m}{\partial x_n} \end{bmatrix}^T\begin{bmatrix}f_1 \\ \vdots \\ f_m \end{bmatrix}$

即 $\nabla F(x)=J_f^Tf$

$Hessian$ 矩陣有 $H_{jk}=\sum_{i=1}^m(\frac{\partial f_i}{\partial x_j}\frac{\partial f_i}{\partial x_k}+f_i\frac{\partial ^2f_i}{\partial x_j\partial x_k})$

忽略二階導(dǎo)數(shù)項有： $H_{jk}\approx \sum_{i=1}^mJ_{ij}J_{ik}$

所以： $H\approx J_f^TJ_f$

高斯-牛頓迭代公式： $x_{n+1}=x_n-[J_f^TJ_f]^{-1}J_f^Tf(x_n)$ $s.t. |\frac{\partial f_i}{\partial x_j}\frac{\partial f_i}{\partial x_k}|\gg |f_i\frac{\partial ^2f_i}{\partial x_j\partial x_k}|$

優(yōu)點

$J_f$ 滿秩扔茅，此時二次項 $|f_i\frac{\partial ^2f_i}{\partial x_j\partial x_k}|$ 可以忽略，高斯牛頓和牛頓法都會收斂
無需計算 $Hessian$ 矩陣

缺點

若 $|fi|$ 或 $|f_i\frac{\partial ^2f_i}{\partial x_j\partial x_k}|$ 比較大秸苗，會導(dǎo)致難以忽略該二次項召娜，高斯牛頓法的收斂速度會很慢，甚至無法收斂惊楼。

Levenberg-Maquardt 算法

根據(jù)目標(biāo)函數(shù) $F(x)$ 二階近似得到：

? $F(x+h)\approx F( x)+\nabla F(x)h+\frac{1}{2}h^TH_Fh\approx F( x)+J_f^Tfh+\frac{1}{2}h^TJ_f^TJ_fh$

我們定義下降方向為 $L(h)$

? $L(h)\equiv F( x)+J_f^Tfh+\frac{1}{2}h^TJ_f^TJ_fh?$ $S.T. h = x_{n+1} - x_n= \Delta ?$

高斯牛頓法迭代公式：
$x_{n+1}=x_n-[J_f^TJ_f]^{-1}J_f^Tf(x_n)$

LM迭代公式： $x_{n+1}=x_n-[J_f^TJ_f+\mu I]^{-1}J_f^Tf(x_n)$
? or
? $[J_f^TJ_f+\mu I]h=-J_f^Tf(x_n)$

作用：結(jié)合了高斯牛頓法與梯度下降法的特點玖瘸，引入阻尼因子來調(diào)節(jié)算法特性。

因子作用：

當(dāng) $\mu\gt 0$ 時保證系數(shù)矩陣正定檀咙，從而確保迭代的下降方向
當(dāng) $\mu$ 很大時雅倒，退化為梯度下降法： $x_{n+1}=x_n-\frac{1}{\mu}J_f^Tf(x_n)$
當(dāng) $\mu$ 很小時，退化為高斯牛頓法： $x_{n+1}=x_n-[J_f^TJ_f]^{-1}J_f^Tf(x_n)$

$\mu$ 的計算

初始取值： $\mu$ 的初始值 $\mu_0$ 與 $J(x_0)^TJ(x_0)$ 矩陣的元素個數(shù)有關(guān)：

? $\mu_0=\tau*max_i\{a_{ii}^{(0)}\}$
更新：由系數(shù) $\varrho$ 來控制弧可，這里：

? $\varrho=\frac{F(x)-F(x+h)}{L(0)-L(h)}$

? 分子的目標(biāo)函數(shù)在步長 $h$ 下的實際變化蔑匣，分母為目標(biāo)函數(shù)二階近似的變化：

? $L(0)-L(h)=(F(x))-(F(x)+h^TJ^Tf+\frac{1}{2}h^TJ^TJh)=-h^TJ^Tf-\frac{1}{2}h^TJ^TJh$

可以看出
- $\varrho$ 越大，表明 $L$ 對 $F$ 的效果越好，可以縮小 $\mu$ 以使得 $LM$ 算法接近高斯牛頓法
- $\varrho$ 越小裁良，表明 $L$ 對 $F$ 的效果越差凿将，所以增大 $\mu$ 以使得 $LM$ 算法接近梯度下降法并減少步長 $h$