上一篇高斯牛頓法的
文章中提到其有些缺點，而 Levenberg–Marquardt Method 就是一種修改版的高斯牛頓法。
Levenberg–Marquardt Method 的精神
高斯牛頓法中有以下等式：
\[
J(x)^TJ(x)\ \Delta x = -J(x)^T f(x)
\]
Levenberg–Marquardt Method 修正成：
\[
(J(x)^TJ(x) + \mu I)\Delta x = -J(x)^T f(x)
\]
\(\mu\) 可以看作是調整求解演算法的一個參數，因為當 \(\mu\) 很小的時候，以上式子就與高斯牛頓法無太大差異，但是當 \(\mu\) 大的時候，\(\Delta x \approx -\frac{1}{\mu}J(x)^T f(x) = -\frac{1}{\mu}F'(x)\)，也就是逼近於梯度下降法。註：
\[
F(x) = \frac{1}{2} \sum_{i=1}^{m}(f_i(x))^2 = \frac{1}{2}\parallel f(x) \parallel ^2 = \frac{1}{2}f(x)^Tf(x)
\]
如何動態調整參數 \(\mu\)
Levenberg–Marquardt Method 定義 gain ratio (\(\varrho\)) 來調整 \(\mu\)：
\[
\varrho = \frac{F(x) - F(x + \Delta x)}{L(0) - L(\Delta x)}
\\
L(\Delta x) = F(x) + \Delta x^T J^T(x) f(x) + \frac{1}{2} \Delta x^T J(x)^T J(x) \Delta x,
\\
L(0) = F(x),
\\
L(0) - L(\Delta x) = -\Delta x^T J^T(x) f(x) - \frac{1}{2} \Delta x^T J(x)^T J(x) \Delta x
\\
= - \frac{1}{2}\Delta x^T(2F'(x) + (J(x)^TJ(x) + \mu I - \mu I) \Delta x)
\\
= - \frac{1}{2}\Delta x^T(2F'(x) - F'(x) - \mu \Delta x)
\\
= - \frac{1}{2}\Delta x^T(F'(x) - \mu \Delta x)
\]
這個值的分子是實際函數 F(x) 下降的值，分母 L(x) 是泰勒展開式近似模型下降的值。如果 gain ratio 接近於 1 代表近似得很好；若 gain ratio 很小時代表近似值下降太多，我們應該要縮小近似範圍，而當 gain ratio 很大時代表我們可以擴大近似範圍。近似範圍便是 Levenberg–Marquardt Method 中的參數 \(\mu\)。因此在實務上我們就依照 gain ratio (\(\varrho\)) 來決定每一回合的參數 \(\mu\) 要取多少，進而可以讓求解 least square problem 的過程變得更穩定。
沒有留言:
張貼留言