レーベンバーグ・マルカートアルゴリズム

数学や計算機科学において、レーベンバーグ・マルカート法（LMAまたは単にLM ）は、減衰最小二乗法（DLS ）とも呼ばれ 、非線形最小二乗問題を解くために用いられます。これらの最小化問題は、特に最小二乗曲線フィッティングにおいて発生します。LMAは、ガウス・ニュートン法（GNA）と勾配降下法の中間に位置する手法です。LMAはGNAよりもロバストであり、多くの場合、最終的な最小値から大きく離れた初期値から始めても解を見つけることができます。性質の良い関数と妥当な初期パラメータの場合、LMAはGNAよりも処理速度が遅くなる傾向があります。LMAは、信頼領域アプローチを用いたガウス・ニュートン法とみなすこともできます。

^{このアルゴリズムは、} 1944年にケネス・レベンバーグ[ ^{1 ]}がフランクフォード陸軍兵器廠で働いていた際に初めて発表されました。1963年にデュポンで統計学者として働いていたドナルド・マーカート[ ^{2 ]によって}再発見され、またジラード^{[ 3 ]} 、ウィン^{[ 4 ] 、モリソン[ 5 ]}によっても独立して発見されました。

LMAは、一般的な曲線近似問題を解決するために多くのソフトウェアアプリケーションで使用されています。ガウス・ニュートン法を使用することで、多くの場合、一次法よりも速く収束します。^{[ 6 ]}しかし、他の反復最適化アルゴリズムと同様に、LMAは局所最小値しか見つけることができず、それが必ずしも大域最小値であるとは限りません。

レーベンバーグ・マルカート法の主な応用は、最小二乗曲線フィッティング問題です。${\displaystyle m}$経験的ペア${\displaystyle \left(x_{i},y_{i}\right)}$独立変数と従属変数のパラメータを求めます。${\displaystyle {\boldsymbol {\beta }}}$モデル曲線の${\displaystyle f{\left(x,{\boldsymbol {\beta }}\right)}}$偏差の二乗の合計${\displaystyle S{\left({\boldsymbol {\beta }}\right)}}$最小化されています:

$${\displaystyle {\hat {\boldsymbol {\beta }}}\in \mathop {\operatorname {argmin} } _{\boldsymbol {\beta }}S{\left({\boldsymbol {\beta }}\right)}\equiv \mathop {\operatorname {argmin} } _{\boldsymbol {\beta }}\sum _{i=1}^{m}\left[y_{i}-f{\left(x_{i},{\boldsymbol {\beta }}\right)}\right]^{2},}$$これは空でないと想定される。

他の数値最小化アルゴリズムと同様に、レーベンバーグ・マルカート法は反復手順です。最小化を開始するには、ユーザーはパラメータベクトルの初期推定値を提供する必要があります。${\displaystyle {\boldsymbol {\beta }}}$⁠。最小値が 1 つしかない場合、次のような情報に基づかない標準的な推測$\displaystyle {\boldsymbol {\beta }}^{\text{T}}={\begin{pmatrix}1,\ 1,\ \dots ,\ 1\end{pmatrix}}}$問題なく動作します。複数の最小値が存在する場合、アルゴリズムは初期推定値が最終解にある程度近い場合にのみ、グローバル最小値に収束します。

各反復ステップにおいて、パラメータベクトルは${\displaystyle {\boldsymbol {\beta }}}$⁠は新しい推定値に置き換えられます⁠${\displaystyle {\boldsymbol {\beta }}+{\boldsymbol {\delta }}}$決定するために${\displaystyle {\boldsymbol {\デルタ }}}$⁠、関数${\displaystyle f{\left(x_{i},{\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)}}$線形化によって近似される：

$${\displaystyle f{\left(x_{i},{\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)}\approx f{\left(x_{i},{\boldsymbol {\beta }}\right)}+\mathbf {J} _{i}{\boldsymbol {\delta }},}$$

どこ $${\displaystyle \mathbf {J} _{i}={\frac {\partial f{\left(x_{i},{\boldsymbol {\beta }}\right)}}{\partial {\boldsymbol {\beta }}}}}$$は、 ⁠の勾配（この場合は行ベクトル） です。${\displaystyle f}$に関して​​${\displaystyle {\boldsymbol {\beta }}}$⁠ .

合計${\displaystyle S\left({\boldsymbol {\beta }}\right)}$二乗偏差の最小値は、 に関して勾配がゼロのときに得られます。${\displaystyle {\boldsymbol {\beta }}}$上記の一次近似は${\displaystyle f{\left(x_{i},{\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)}}$与える $${\displaystyle S\left({\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)\approx \sum _{i=1}^{m}\left[y_{i}-f\left(x_{i},{\boldsymbol {\beta }}\right)-\mathbf {J} _{i}{\boldsymbol {\delta }}\right]^{2},}$$ またはベクトル表記では、 $${\displaystyle {\begin{aligned}S\left({\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)&\approx \left\|\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}-\mathbf {J} {\boldsymbol {\delta }}\right\|^{2}\\&=\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}-\mathbf {J} {\boldsymbol {\delta }}\right]^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}-\mathbf {J} {\boldsymbol {\delta }}\right]\\&=\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right]^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right]-\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right]^{\mathrm {T} }\mathbf {J} {\boldsymbol {\delta }}-\left(\mathbf {J} {\boldsymbol {\delta }}\right)^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right]+{\boldsymbol {\delta }}^{\mathrm {T} }\mathbf {J} ^{\mathrm {T} }\mathbf {J} {\boldsymbol {\delta }}\\&=\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right]^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right]-2\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right]^{\mathrm {T} }\mathbf {J} {\boldsymbol {\delta }}+{\boldsymbol {\delta }}^{\mathrm {T} }\mathbf {J} ^{\mathrm {T} }\mathbf {J} {\boldsymbol {\delta }}.\end{aligned}}}$$ この近似の導関数を取ると、${\displaystyle S\left({\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)}$～に関して${\displaystyle {\boldsymbol {\delta }}}$結果をゼロに設定すると

$${\displaystyle \left(\mathbf {J} ^{\mathrm {T} }\mathbf {J} \right){\boldsymbol {\delta }}=\mathbf {J} ^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right],}$$

どこ${\displaystyle \mathbf {J} }$はヤコビ行列であり、その⁠${\displaystyle i}$⁠ - 番目の行は${\displaystyle \mathbf {J} _{i}}$、そして${\displaystyle \mathbf {f} \left({\boldsymbol {\beta }}\right)}$そして${\displaystyle \mathbf {y} }$は、 ⁠のベクトルです。${\displaystyle i}$⁠ - 番目のコンポーネント ${\displaystyle f\left(x_{i},{\boldsymbol {\beta }}\right)}$そして${\displaystyle y_{i}}$それぞれ。上記の式は⁠に対して得られた。${\displaystyle {\boldsymbol {\beta }}}$ガウス・ニュートン法では、ヤコビ行列は（一般に）正方行列ではなく、サイズの長方形行列になります。${\displaystyle m\times n}$、 どこ${\displaystyle n}$パラメータの数（ベクトルのサイズ）${\displaystyle {\boldsymbol {\beta }}}$行列の乗算${\displaystyle \left(\mathbf {J} ^{\mathrm {T} }\mathbf {J} \right)}$必要な結果が得られる${\displaystyle n\times n}$正方行列と右辺の行列ベクトル積は、サイズのベクトルを生成する。${\displaystyle n}$結果は次のセットです。${\displaystyle n}$線形方程式は、解くことができます。${\displaystyle {\boldsymbol {\delta }}}$⁠ .

レーベンバーグの貢献は、この方程式を「減衰バージョン」に置き換えることである。

$${\displaystyle \left(\mathbf {J} ^{\mathrm {T} }\mathbf {J} +\lambda \mathbf {I} \right){\boldsymbol {\delta }}=\mathbf {J} ^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right],}$$

どこで${\displaystyle \mathbf {I} }$は単位行列であり、増分として を与える。${\displaystyle {\boldsymbol {\delta }}}$推定パラメータベクトルへ${\displaystyle {\boldsymbol {\beta }}}$⁠ .

（非負の）減衰係数${\displaystyle \lambda }$は各反復で調整されます。 の削減が${\displaystyle S}$が速い場合、より小さな値を使用でき、アルゴリズムをガウス・ニュートン法に近づけることができますが、反復によって残差が十分に減少しない場合は、${\displaystyle \lambda }$⁠を増やすことで、勾配降下法の方向に一歩近づくことができます。 ⁠の勾配は${\displaystyle S}$に関して​​${\displaystyle {\boldsymbol {\beta }}}$等しい​${\displaystyle -2\left(\mathbf {J} ^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right]\right)^{\mathrm {T} }}$したがって、 の値が大きい場合${\displaystyle \lambda }$⁠、ステップは勾配とほぼ反対方向に取られます。計算されたステップの長さが⁠${\displaystyle {\boldsymbol {\delta }}}$または、最新のパラメータベクトルからの二乗和の減少${\displaystyle {\boldsymbol {\beta }}+{\boldsymbol {\delta }}}$事前に定義された制限を下回ると、反復が停止し、最後のパラメータベクトルが${\displaystyle {\boldsymbol {\beta }}}$⁠は解決策と考えられています。

減衰係数が${\displaystyle \lambda }$は、${\displaystyle \|\mathbf {J} ^{\mathrm {T} }\mathbf {J} \|}$反転${\displaystyle \mathbf {J} ^{\mathrm {T} }\mathbf {J} +\lambda \mathbf {I} }$更新は小さな勾配ステップで十分に近似されるため、必要ありません。${\displaystyle \lambda ^{-1}\mathbf {J} ^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right]}$。

解のスケール不変性を確保するために、マルカートのアルゴリズムは、勾配の各成分を曲率に応じてスケーリングした修正問題を解きました。これにより、勾配が小さい方向に沿ってより大きな移動が可能になり、勾配が小さい方向での収束の遅さを回避できます。フレッチャーは、1971年の論文「非線形最小二乗法のための修正マルカートサブルーチン」で、単位行列を置き換えることで形式を簡略化しました。${\displaystyle \mathbf {I} }$対角行列は、の対角要素から構成される。${\displaystyle \mathbf {J} ^{\text{T}}\mathbf {J} }$⁠ :

$${\displaystyle \left[\mathbf {J} ^{\mathrm {T} }\mathbf {J} +\lambda \operatorname {diag} \left(\mathbf {J} ^{\mathrm {T} }\mathbf {J} \right)\right]{\boldsymbol {\delta }}=\mathbf {J} ^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} {\left({\boldsymbol {\beta }}\right)}\right].}$$

同様の減衰係数は、線形不適切問題を解くために使用されるティホノフ正則化や、統計学における推定手法であるリッジ回帰にも現れる。

この例では、関数を当てはめようとします${\displaystyle y=a\cos \left(bX\right)+b\sin \left(aX\right)}$GNU Octaveに実装されているleasqr関数として、レーベンバーグ・マルカート法を使用しています。グラフは、パラメータの適合度が徐々に向上していく様子を示しています。${\displaystyle a=100}$、${\displaystyle b=102}$初期曲線で使用されます。最後のグラフのパラメータが元の値に最も近い値に選択された場合にのみ、曲線は正確にフィットします。この方程式は、レーベンバーグ・マルカート法の非常に敏感な初期条件の例です。この感度の理由の1つは、複数の最小値が存在することです。関数${\displaystyle \cos \left(\beta x\right)}$パラメータ値で最小値を持つ${\displaystyle {\hat {\beta }}}$そして${\displaystyle {\hat {\beta }}+2n\pi }$。

• トラスト地域
• ネルダー・ミード法
• レーベンバーグ・マルカート法の変種は、非線形方程式系の解法にも用いられてきた。^{[ 10 ]}

• アルゴリズムの詳細については、『Numerical Recipes in C』第15.5章「非線形モデル」を参照してください。
• CT Kelley、「最適化のための反復法」、SIAM Frontiers in Applied Mathematics、第18号、1999年、ISBN 0-89871-433-8オンライン版
• SIAMニュースにおけるアルゴリズムの歴史
• アナンス・ランガナタンによるチュートリアル
• K. Madsen、HB Nielsen、O. Tingleff、「非線形最小二乗問題のための方法（非線形最小二乗チュートリアル、LMコード：解析的ヤコビアンセカント）」
• T. ストルツ著：データフィッティングと不確実性（重み付き最小二乗法とその先への実践的入門）。第2版、Springer Vieweg、2016年、ISBN 978-3-658-11455-8。
• HP Gavin著、「非線形最小二乗曲線フィッティング問題のためのレーベンバーグ・マルカート法（MATLAB実装を含む）」