レーベンバーグ・マルカート法

数学および計算科学において、レーベンバーグ・マルカート法とは、非線形最小二乗問題の解法の一つをいう。特に曲線回帰を最小二乗法により行う場合によく用いられる。LM法はガウス・ニュートン法と最急降下法を内挿した手法といえる。GN法よりもロバストであり、初期値が解から大きく外れていた場合でも解けることが多いが、ふるまいの良い関数に対してはGN法よりも収束が遅い傾向を示す。 LM法は、GN法に信頼領域法を適用したものとみることもできる。

1944年、フランクフォード・アーセナル職員ケネス・レーヴェンバーグにより初発表され、1963年にデュポン勤務の統計家、ドナルド・マーカートにより再発見された。また、Girard, Wynne, Morrison によりそれぞれ独立に再発見されている。

LM法は、一般的な曲線回帰問題を解く必要のあるアプリケーションソフトウェアで広く用いられる。GN法を取り入れているため多くの場合で1次解法よりも収束速度が速いが、他の反復法と同様、LM法で保証されているのは局所最小値への収束のみであり、大域最小値が得られる保証はない。

1. 問題設定
-------

LM法の主な適用対象は、最小二乗曲線回帰問題である。 m}}対の独立変数と従属変数のペアが与えられたとき、β}}をパラメータとする曲線//f//}}と所与のペアとの偏差の二乗和//S//}}を最小化することを考える。

2. 解法
-----

他の数値最適化手法と同様、LM法は反復法を用いる。まず、パラメーターベクトルβ}}の初期推定値を与える必要がある 。極小点が1つしかない場合、事前情報に基づかない均一な初期推定値、たとえば 1=//supでも大域解に到達することができるが、複数の局所最小値が存在する場合、初期推定値が十分に大域最小点に近いときにしか大域解には収束しない。

各反復ステップにおいてパラメーターベクトルβ}}は新しい推定値// + //}}へ置き換えられる。δ}}を決めるため、//f//(//xsubを次のように線形近似する。//

ここで、

は関数f}}のβ}}についての勾配である。

偏差の二乗和//S//}}は、この勾配がゼロのとき局所最小となる。上式の一次近似を用いると、//f//(//xsubの偏差二乗和は以下のように近似される。//

ベクトル表記すると、以下のように書ける。

//S//}}をδ}}に関して微分した結果を0とすると、以下の式を得る。

ここで、J}}はヤコビ行列であり、そのi}}行目はJsub に等しい。また、//, //}}はそれぞれ、i}}行目成分を//f//(//xsubとするベクトルである。ヤコビ行列は一般的には正方行列ではなく、m}}をデータ点数、n}}をベクトルβ}}のサイズとして//m// × //n//}}長方形行列である。行列積//supは//n// × //n//}}正方行列となり、上式はn}}連立線形方程式であるからこれを解いてδ}}を得ることができる。これをそのまま解くのがガウス・ニュートン法である。//

LM法では、この方程式を次のように「減衰」させたものに置き換える。

ここで、I}}は単位行列である。これを解いて得られるδ}}を用いてパラメータベクトルβ}}の推定値を更新する。

非負の減衰係数λ}}は各反復ごとに調整される。S}}が急速に減少する際には小さい値が用いられ、LM法はGN法に近づく。対して、残差が十分に減少しない場合は大きい値のλ}}が用いられ、S}}のβ}}についての勾配は−2 (//supであることに注意すると、λ}}が大きいときδ}}は勾配の逆向きに近付きLM法は最急降下法に近づくことがわかる。計算されたδ}}が十分小さくなったとき、もしくは得られたパラメータ推定値// + //}}に置き換えた際の偏差二乗和の減少が十分に小さくなったときのどちらかの場合に反復は打ち切られ、解β}}を得る。

減衰係数λ}}がnormに比べて大きいときは、//supの逆行列を求める必要はなく、更新ステップδ}}はで十分に近似される。

LM法は、λ}}が大きい値のとき//supの情報がほとんど使われないという欠点を持つ。Fletcherは1971年、勾配が小さい方向への収束が遅いという問題を避けるため、勾配を曲率に応じてスケールするという考えから、単位行列I}}を//supの対角要素で置き換え、解をスケール不変にする手法が提案された。

同様の減衰因子は、線形不良設定問題を解くために用いられるティホノフ正則化や、リッジ回帰と呼ばれる推計法にも現れる。

2.1. 減衰パラメータの選び方
----------------

最良の減衰係数λ}}を選ぶ方法としては、様々な議論があるが、大なり小なりヒューリスティックなものである。それらの選び方がなぜ局所最小点への収束を保証するかを示す理論的な議論はあるが、大域最小点へ収束するような選び方をすると最急降下法の望ましくない特質、とくに収束が遅いという側面が表われてしまう。

どんな選び方をしても、パラメータの大きさはもとの問題がどれほど良くスケールするかに依存する。マーカートは次のような選び方を推奨している。まず初期値1=//λ// = //λ//subを選んで最初のステップを実行し、残差//S//}}が最初の点よりも減った場合は//ν// > 1}}なる係数を用いて次のステップは1=//λ// = //λ//subとする。残差が増えてしまった場合は、減るようになるまで繰り返しν}}を掛け//λ//subを用いて計算をする。

減衰係数//λ/////ν//}}を用いた結果が二乗残差を減少させたなら、これをλ}}の新しい値とし、プロセスを続行する。もし//λ/////ν//}}を用いた残差がλ}}を用いた残差よりも大きくなったならば、λ}}の値を変えず、λ}}を用いた結果を採用する。

//delayed gratification//date=2022年9月}}と呼ばれる減衰係数の効果的な制御方法がある。この方法では、上り坂のステップごとに係数を少しずつ増やし、下り坂のステップごとにパラメーターを大幅に減らす。この戦略は、最適化の開始時に坂を下りすぎ、後に使用できるステップが制限されて、収束が遅くなることを防ぐことを主眼においている。 ほとんどの場合、増加時には2倍、減少時には3分の1を採用すればうまくいくことが示されているが、大規模な問題の場合は、増加時は1.5倍、減少時は5分の1というより極端な値を用いる方がよいことが知られている。

2.2. 測地加速度項
-----------

レーベンバーグ・マルカート法の更新ステップ//subを、パラメーター空間の測地経路に沿った速度と捉えると、測地経路に沿う加速度に対応する2次の項//subを次のように加える改善が考えられる。

ここで、//subは次の方程式の解である。

この測地線加速度項は速度//}}に沿う方向微分 のみに依存するため、完全な二次導関数行列を計算する必要はなく、計算コスト上のオーバーヘッドは比較的小さい。2次導関数はかなり複雑な式になる場合があるため、有限差分近似に置き換えると便利な場合がある。

ここで、//}}とJ}}は通常のアルゴリズムでもすでに計算されているため、追加で計算する必要があるのは//}}だけである。有限差分ステップh}}の選択によってはアルゴリズムが不安定になる場合があるが、通常はおよそ0.1が妥当である。

加速度は速度と反対の方向を指す可能性があり、減衰が小さすぎて収束が失速するのを防ぐために、ステップの採用条件に加速度に関する以下のような追加の基準が追加される。

ここでα}}は通常は1未満の固定値とされる。より難しい問題ではより小さい値とする。

測地加速度項を追加すると、収束速度が大幅に向上する可能性があり、特にアルゴリズムが目的関数ランドスケープ上の狭い峡谷を移動する場合に有用である。このような場合、2次の項の効果によりステップ幅はより小さく、精度が高くなる。

3. 例
----

この例では、関数 をGNU Octave上のレーベンバーグ・マルカート法実装//leasqr//関数をもちいてフィッティングする。グラフから、パラメーターフィッティング結果が徐々に改善し、 、 の曲線に近付いていく様子が見てとれる。初期パラメータが元のパラメータに近い場合にのみ、曲線が正確に一致する。この例は、レーベンバーグ・マルカート法が初期条件に非常に敏感であることを示す一例である。その理由の1つは、複数の最小点  が存在すること、つまりcos}}に一致するパラメータの値はhatだけでなくhatと複数あることである。

4. 出典
-----

5. 関連文献
-------

last=Pujol

6. 関連項目
-------

信頼領域法
ネルダー・ミード法
非線形連立方程式を解くためにも、レーベンバーグ・マルカート法のさまざまな亜種が使用される。

7. 外部リンク
--------

Detailed description of the algorithm can be found in [1]
C. T. Kelley, //Iterative Methods for Optimization//, SIAM Frontiers in Applied Mathematics, no 18, 1999, 0-89871-433-8}}. [2]
[3]
[4]
K. Madsen, H. B. Nielsen, O. Tingleff, //[5]// 
T. Strutz: //Data Fitting and Uncertainty .// 2nd edition, Springer Vieweg, 2016, 978-3-658-11455-8}}.
H. P. Gavin, [8]