ガウス・ニュートン法

ガウス・ニュートン法（ガウス・ニュートンほう、）は、非線形最小二乗法を解く手法の一つである。これは関数の最大・最小値を見出すニュートン法の修正とみなすことができる。ニュートン法とは違い、ガウス・ニュートン法は二乗和の最小化に"しか"用いることができないが、計算するのが困難な2階微分が不要という長所がある。
非線形最小二乗法は非線形回帰などで、観測データを良く表すようにモデルのパラメータを調整するために必要となる。
この手法の名称はカール・フリードリヒ・ガウスとアイザック・ニュートンにちなむ。
概要.
データフィッティングにおいて、与えられたモデル関数 "y" = "f" ("x" , β) が"m" 個のデータ点 {("xi" , "yi" ); "i" = 1, ... , "m" } に最もよくフィットするような"n" （≤ "m" ）個のパラメータβ = (β1 , ... , β"n" )を見つけることが目的である。
このとき、残差を
とする。
このとき、ガウス・ニュートン法は残差の平方和
の最小値を反復計算で求める。初期推測値β(0) から初めて、この方法は以下の計算を繰り返す。
ここで
はβ("s" ) におけるr のヤコビアン、"Jr"T は行列"Jr" の転置を表す。
"m" = "n" ならば、この反復計算は
のように簡略化される。これは1次元ニュートン法の直接的な一般化である。
ガウス・ニュートン法は関数"f" のヤコビアン"Jf" を用いて次のように表すこともできる：
注釈.
ガウス・ニュートン法は関数"ri" を並べたベクトルの線形近似で与えられる。テイラーの定理を用いれば、各反復において次式が成り立つ：
ここで Δ = β - β"s" である。右辺の残差平方和を最小化するΔを見つけること、すなわち
は線形最小二乗法の問題であるため、陽的に解くことができ、正規方程式を与える。ここで ||*||2 は 2-ノルム（ユークリッドノルム）である。
正規方程式は未知の増分Δについての"m" 本の線形同次方程式である。これはコレスキー分解を用いることで、またはより良い方法としては"Jr" のQR分解を用いることで、1ステップで解ける。大きな系に対しては、共役勾配法のような反復解法が有効である。"Jr" の列ベクトルが線形従属である場合、"Jr"T"Jr" が非正則になるため反復解法は失敗する。
例.
ここでは例として、ガウス・ニュートン法を使ってデータとモデルによる予測値の間の残差平方和を最小化し、データにモデルをフィットさせる。
生物実験において、酵素媒介反応における基質濃度[S] と反応率"v" の関係として次表のようなデータが得られたとする（右図の赤点）。
これらのデータに対し、次の形のモデル曲線（ミカエリス・メンテン式）のパラメータ"V"max と"K"M を、最小二乗の意味で最もよくフィットするように決定したい：
"xi" と"yi" ("i" = 1, ... , 7) で [S] と"v" のデータを表す。また、"β"1 = "V"max 、"β"2 = "KM" とする。残差
の平方和を最小化する"β"1 と"β"2 を見つけることが目的となる。
未知パラメータβに関する残差ベクトルr のヤコビアン"Jr" は7×2の行列で、"i" 番目の行は次の要素を持つ：
初期推定値としてβ1 = 0.9、β2 = 0.2から始め、ガウス・ニュートン法による5回の反復計算を行うと、最適値 formula_12 が得られる。残差平方和は5回の反復計算で初期の1.445から0.00784まで減少する。右図はこれらの最適パラメータを用いたモデルで決まる曲線と、実験データとの比較を示す。
収束性.
増分Δが"S" の減少方向を向いていることは証明されている。もしこのアルゴリズムが収束すれば、その極限は"S" の停留点である。しかし収束については、ニュートン法では保証されている局所収束さえも保証されていない。
ガウス・ニュートン法のは2次である。もし初期推測値が最小値から遠いか、または行列"Jr"T "Jr" が悪条件であれば収束は遅いか、全くしなくなる。例えば、"m" = 2本の方程式と"n" = 1個の変数のある次の問題を考える：
この問題の最適値はβ = 0 である。もしλ = 0 なら実質的に線形問題であり、最適値は一回の計算で見つかる。もし|λ| < 1 なら、この手法は線形に収束し残差は係数|λ|で反復ごとに漸近的に減少する。しかし|λ| > 1 なら、この方法はもはや局所的にも収束しない。
ニュートン法からの導出.
後に示すように、ガウス・ニュートン法は近似関数の最適化に用いられるニュートン法から与えられる。その結果、ガウス・ニュートン法の収束の速さはほとんど2次である。
パラメータβを持つ関数"S" の最小化をするとき、ニュートン法による漸化式は
である。ここでg は"S" の勾配ベクトル、"H" は"S" のヘッシアンである。formula_15であるから、勾配g は次で与えられる：
ヘッシアン"H" は勾配g をβ で微分することで計算される：
2階微分項（右辺第2項）を無視することでガウス・ニュートン法を得る。つまり、ヘッシアンは
と近似される。ここで
はヤコビアン"Jr" の成分である。
これらの表現を上述の漸化式に代入して、次式を得る：
ガウス・ニュートン法の収束は常に保証されているわけではない。2階微分項を無視するという近似、すなわち
に正当性があるのは次の2つの条件の下であり、これらが成り立つ場合には収束が期待される：
改善バージョン.
ガウス・ニュートン法は、初期推定値が真の解から大きく離れていたり、モデル関数の非線形性が大きい場合には安定性が悪い。また、残差平方和"S" は反復ごとに必ずしも減少するわけではない。そのため、実用上は安定化が必要である。
"S" は反復ごとに必ずしも減少するわけではないが、増分ベクトルΔは"S" が減少する方向を向いているから、"S" (βs) が停留点にない限り、任意の十分に小さな"α"> 0 に対して "S" (βs + "αΔ) < "S" (β"s) が成り立つ。したがって、発散したときに、更新方程式に縮小因子"α"を導入して
とすることが解決法の一つとなる。
言い換えれば、増分ベクトルΔは目的関数"S" の下り方向を指してはいるが長すぎるので、その道のほんの一部を行くことで、"S" を減少させようというアイディアである。縮小因子"α"の最適値は直線探索で見つけることができる。つまり、直接探索法を（通常 0 < α ≤ 1 の区間で）用いて、"S" を最小化する値を探すことで"α"の大きさは決められる。
最適な縮小因子"α"が 0 に近いような場合、発散を回避する別の方法はレーベンバーグ・マルカート法（信頼領域法）を使うことである。増分ベクトルが最急降下方向に向くように正規方程式は修正される。
ここで"D" は正定値対角行列である。λが 0 から増大するにつれて増分ベクトルΔは長さが単調に減少し、かつ方向は最急降下方向に近づくため、λを十分大きくすれば必ずより小さい"S" の値を見出せることが保証されている。
いわゆるマルカートパラメータλは直線探索により最適化されるが、λが変わるたびに毎回シフトベクトルの再計算をしなければならないため非効率的である。より効率的な方法は、発散が起きた時にλを"S" が減少するまで増加させる。そしてその値を1回の反復から次まで維持する、しかしλを 0 に設定することができるときにもしカットオフ値に届くまで可能なら減少させる。このとき"S" の最小値は標準のガウス・ニュートン法の最小化になる。
関連するアルゴリズム.
DFP法やBFGS法のような準ニュートン法では、ヘッシアンformula_25の推定は1階微分formula_26のみを用いて数値的になされる。したがって"n" 回の反復計算による修正の後、この方法はパフォーマンスにおいてニュートン法を近似する。ガウス・ニュートン法やレーベンバーグ・マルカート法などは非線形最小二乗問題にのみ適用できるのに対して、準ニュートン法は一般的な実数値関数を最小化できることに注意する。
1階微分のみを使って最小化問題を解く他の方法は、最急降下法である。しかし、その方法は近似に2階微分を考慮していないので、多くの関数に対して、特にパラメータが強い相互作用を持っている場合には、計算効率が非常に悪い。