Gauss–Newton法(Gauss–Newton method)とは、残差のベクトルの 2 乗の和を最小にする非線形最小二乗問題で、各回に残差を現在の点で 1 次近似し、その線形の最小二乗問題の解を次の点にする反復法である。目的関数の Hesse 行列を残差の Jacobi 行列 $J$ による $J^{\mathsf T}J$ で近似したことにあたり、2 階導関数を使わない。解で Jacobi 行列の列が 1 次独立なら、解での残差が 0 のときは局所的に 2 次収束し、残差が小さいときは残差に比例する比で 1 次収束するが、残差が大きいと大域的な最小点の近くからでも収束しないことがある。1 歩の長さに罰則を加えた Levenberg–Marquardt 法は信頼領域法と同じ 1 歩の族を使う。
Gauss–Newton法(Gauss–Newton method)は、残差のベクトル $r(x)=(r_1(x),\dots,r_m(x))$ の 2 乗の和
$$
F(x)=\frac12\lvert r(x)\rvert^2=\frac12\sum_{i=1}^mr_i(x)^2\qquad(x\in\mathbb R^n,\ m\ge n)
$$
を最小にする 非線形最小二乗問題 の反復法である。各回で $r$ を現在の点で 1 次近似し、その 1 次の 最小二乗法 の解を次の点にする。データ $(t_i,y_i)$ にモデル $\varphi(t;x)$ を当てはめる問題($r_i(x)=\varphi(t_i;x)-y_i$)が典型である。
Newton法 を $\nabla F=0$ に当てはめるには $r$ の 2 階導関数が要るが、Gauss–Newton 法は 1 階導関数(Jacobi 行列 $J$)だけを使い、Hesse行列 を $J^{\mathsf T}J$ で近似する。近似で落とした項は残差に比例するので、解で残差が $0$ なら Newton 法と同じく 2 次収束し、残差が小さければ速い 1 次収束をする(thm-gn-local)。残差が大きいと、近似の誤差のために局所最小点に収束しないことがある(ex-gn-counterexample)。
この記事では、方法を定義して降下方向であることを示し(prop-gn-descent)、主定理として局所収束の評価を証明する。続いて残差が大きい場合の反例を挙げ、各回の 1 歩に罰則を加えた Levenberg–Marquardt 法とその信頼領域としての解釈(prop-gn-lm)を述べる。
$\lvert\cdot\rvert$ は Euclid ノルム、行列 $M$ の $\lvert M\rvert$ は作用素ノルム(最大の特異値)とする。$m\times n$ 行列 $M$($m\ge n$)の最小の特異値を $\sigma_{\min}(M):=\min_{\lvert v\rvert=1}\lvert Mv\rvert$ と書く。$\sigma_{\min}(M)>0$ は $M$ の列が 1 次独立であることと同値で、このとき $M^{\mathsf T}M$ は正則、$\lvert(M^{\mathsf T}M)^{-1}\rvert=\sigma_{\min}(M)^{-2}$、$\lvert(M^{\mathsf T}M)^{-1}M^{\mathsf T}\rvert=\sigma_{\min}(M)^{-1}$ である(特異値分解 で対角にすれば分かる)。
$r\colon D\to\mathbb R^m$ を開集合 $D\subseteq\mathbb R^n$ 上の $C^1$ 級写像、$J(x)$ をその Jacobi 行列($m\times n$、第 $(i,j)$ 成分 $\partial_jr_i(x)$)とする。$F=\frac12\lvert r\rvert^2$ の勾配と、$r$ が $C^2$ 級のときの Hesse 行列は
$$
\nabla F(x)=J(x)^{\mathsf T}r(x),\qquad\nabla^2F(x)=J(x)^{\mathsf T}J(x)+\sum_{i=1}^mr_i(x)\nabla^2r_i(x)
$$
である。
初期点 $x_0\in D$ をとり、$k=0,1,2,\dots$ について、$J_k:=J(x_k)$ の列が 1 次独立である間、
$$
p_k:=\operatorname*{arg\,min}_{p\in\mathbb R^n}\bigl\lvert r(x_k)+J_kp\bigr\rvert^2=-(J_k^{\mathsf T}J_k)^{-1}J_k^{\mathsf T}r(x_k),\qquad x_{k+1}:=x_k+p_k
$$
とする。$p_k$ を Gauss–Newton の 1 歩 という。
$p_k$ は 1 次近似 $r(x_k+p)\approx r(x_k)+J_kp$ の 最小二乗法 の解で、最小二乗法 の定理「最小二乗解と正規方程式」により正規方程式 $J_k^{\mathsf T}J_kp=-J_k^{\mathsf T}r(x_k)$ の解である。実際の計算では、正規方程式を作らずに $J_k$ の QR 分解で解くことが多い(同記事の定理「QR 分解による最小二乗解」。正規方程式の条件数は $J_k$ の条件数の 2 乗になる)。$m=n$ で $J_k$ が正則なら $p_k=-J_k^{-1}r(x_k)$ で、方程式 $r(x)=0$ に対する Newton法 そのものである(VMLS18 §18.2、pp. 386–389)。
Newton 法を $\nabla F=0$ に当てはめた 1 歩は $\bigl(J_k^{\mathsf T}J_k+S_k\bigr)p=-J_k^{\mathsf T}r(x_k)$、$S_k:=\sum_ir_i(x_k)\nabla^2r_i(x_k)$ である。Gauss–Newton 法はこの $S_k$ を落としたもので、$J^{\mathsf T}J$ を Gauss–Newton 行列 という(BCN18 §6.3、pp. 59–60)。$J^{\mathsf T}J$ は半正定値なので、Newton 法と違って $F$ の Hesse 行列が不定な点でも向きが降下方向になる。
$J_k$ の列が 1 次独立で $\nabla F(x_k)\ne0$ なら、$\nabla F(x_k)\cdot p_k=-\lvert J_kp_k\rvert^2< 0$ であり、$\nabla F(x_k)$ と $-p_k$ のなす角 $\varphi$ は
$$
\cos\varphi\ge\Bigl(\frac{\sigma_{\min}(J_k)}{\lvert J_k\rvert}\Bigr)^2
$$
をみたす。とくに $F(x_k+tp_k)< F(x_k)$ となる $t\in(0,1]$ がある。
$u:=J_k^{\mathsf T}r(x_k)=\nabla F(x_k)\ne0$、$B:=J_k^{\mathsf T}J_k$ とおくと $p_k=-B^{-1}u$ で、$\nabla F(x_k)\cdot p_k=-u\cdot B^{-1}u=-(Bp_k)\cdot p_k=-\lvert J_kp_k\rvert^2$ である。$p_k\ne0$ で $J_k$ の列は 1 次独立なので、これは負である。$B^{-1}$ の固有値は $\lvert J_k\rvert^{-2}$ 以上 $\sigma_{\min}(J_k)^{-2}$ 以下なので、$u\cdot B^{-1}u\ge\lvert u\rvert^2/\lvert J_k\rvert^2$、$\lvert p_k\rvert\le\lvert u\rvert/\sigma_{\min}(J_k)^2$ で、$\cos\varphi=\frac{u\cdot B^{-1}u}{\lvert u\rvert\lvert p_k\rvert}$ の評価を得る。最後の主張は、方向微分係数が負であることによる(最適化 の命題「降下方向」)。$\square$
そこで、刻み $t_k\in(0,1]$ を直線探索で選んで $x_{k+1}=x_k+t_kp_k$ とする 減衰 Gauss–Newton 法 もよく使われる。角の評価は、直線探索の大域的な収束の議論で必要になる「向きが勾配と直交に近づかないこと」を、$J_k$ の条件数で保証するものである。ただし $J_k$ の列が 1 次独立でない点では $p_k$ が定まらない。この 2 つの弱点($x_{k+1}$ で値が増えうること、$J_k$ の階数落ち)を同時に扱うのが、節「Levenberg–Marquardt 法」の方法である(VMLS18 §18.2.1、p. 388)。
$D$ を凸な開集合とし、$J$ が $D$ で $\gamma$-Lipschitz 連続、すなわち $\lvert J(x)-J(y)\rvert\le\gamma\lvert x-y\rvert$($x,y\in D$)とする。
1:$r(y)-r(x)=\int_0^1J(x+s(y-x))(y-x)\,ds$ なので、左辺は $\bigl\lvert\int_0^1\bigl(J(x+s(y-x))-J(x)\bigr)(y-x)\,ds\bigr\rvert\le\int_0^1\gamma s\lvert y-x\rvert^2ds$ 以下である。2:$\lvert v\rvert=1$ について $\lvert J(y)v\rvert\ge\lvert J(x)v\rvert-\lvert(J(y)-J(x))v\rvert\ge\sigma_{\min}(J(x))-\gamma\lvert y-x\rvert$ である。$\square$
$D$ を凸な開集合、$r\colon D\to\mathbb R^m$ を $C^1$ 級、$J$ を $D$ で $\gamma$-Lipschitz 連続とする。$x^*\in D$ が $J(x^*)^{\mathsf T}r(x^*)=0$($F$ の停留点)をみたし、
$$
\sigma:=\sigma_{\min}(J(x^*))>0,\qquad\rho:=\gamma\lvert r(x^*)\rvert<\sigma^2
$$
とする。$e_k:=x_k-x^*$ と書く。
1:lem-gn-tools の 2 により $\sigma_{\min}(J_k)\ge\sigma_k>0$ なので $J_k$ の列は 1 次独立で、$J_k^+:=(J_k^{\mathsf T}J_k)^{-1}J_k^{\mathsf T}$ について $\lvert J_k^+\rvert\le\sigma_k^{-1}$、$\lvert(J_k^{\mathsf T}J_k)^{-1}\rvert\le\sigma_k^{-2}$ である。$J_k^+J_k=I$ なので
$$
e_{k+1}=e_k-J_k^+r(x_k)=J_k^+\bigl(J_ke_k-r(x_k)\bigr)
$$
である。lem-gn-tools の 1 を $x=x_k$、$y=x^*$ に使い、$w:=r(x^*)-r(x_k)+J_ke_k$ とおくと $\lvert w\rvert\le\frac\gamma2\lvert e_k\rvert^2$ で、$J_ke_k-r(x_k)=w-r(x^*)$ である。よって
$$
e_{k+1}=J_k^+w-(J_k^{\mathsf T}J_k)^{-1}J_k^{\mathsf T}r(x^*)
$$
である。停留点の条件 $J(x^*)^{\mathsf T}r(x^*)=0$ から $J_k^{\mathsf T}r(x^*)=\bigl(J_k-J(x^*)\bigr)^{\mathsf T}r(x^*)$ で、その長さは $\gamma\lvert e_k\rvert\lvert r(x^*)\rvert=\rho\lvert e_k\rvert$ 以下である。2 つの項を評価すると 1 を得る。
2:$\delta>0$ を、閉球 $\bar B(x^*,\delta)\subseteq D$、$\gamma\delta<\sigma$、
$$
c(\delta):=\frac\rho{(\sigma-\gamma\delta)^2}+\frac{\gamma\delta}{2(\sigma-\gamma\delta)}\le q
$$
となるようにとる。$\delta\to0$ で $c(\delta)\to\rho/\sigma^2< q$ なので可能である。$\lvert e_k\rvert\le\delta$ なら $\sigma_k\ge\sigma-\gamma\delta$ なので、1 から $\lvert e_{k+1}\rvert\le c(\delta)\lvert e_k\rvert\le q\lvert e_k\rvert\le\delta$ である。帰納法によりすべての $k$ でこれが成り立ち、$\lvert e_k\rvert\le q^k\delta\to0$ である。さらに $\sigma_k\to\sigma$ なので 1 の右辺を $\lvert e_k\rvert$ で割ったものは $\rho/\sigma^2$ に近づく。
3:$\rho=0$ なので、2 の評価の第 1 項が消える。$\square$
条件 $\rho<\sigma^2$ は、残差 $\lvert r(x^*)\rvert$ が、$J$ の変化の速さ $\gamma$ と解での $J$ の最小の特異値 $\sigma$ に比べて小さいことを求める。$\rho/\sigma^2$ が 1 次収束の比の上界で、残差が小さいほど速い。零残差(モデルがデータにちょうど合う場合)では Newton 法と同じ 2 次収束になる。
$r$ が $C^2$ 級なら、比はもっと正確に分かる。Gauss–Newton の写像 $\Phi(x):=x-(J^{\mathsf T}J)^{-1}J^{\mathsf T}r$ を $x^*$ で微分すると、$(J^{\mathsf T}J)^{-1}$ の微分に掛かる因子 $J(x^*)^{\mathsf T}r(x^*)$ が $0$ なので
$$
D\Phi(x^*)=I-(J_*^{\mathsf T}J_*)^{-1}\bigl(J_*^{\mathsf T}J_*+S_*\bigr)=-K,\qquad K:=(J_*^{\mathsf T}J_*)^{-1}S_*
$$
である($J_*:=J(x^*)$、$S_*:=\sum_ir_i(x^*)\nabla^2r_i(x^*)$)。Gauss–Newton 法は不動点 $x^*$ の周りで線形写像 $-K$ で近似される反復であり、$K$ のスペクトル半径が $1$ より小さければ $x^*$ の近くから収束し、$\limsup_k\lvert e_k\rvert^{1/k}$ はスペクトル半径以下になる。多くの場合、誤差の比 $\lvert e_{k+1}\rvert/\lvert e_k\rvert$ もスペクトル半径に近づく(ex-gn-fit)。$K$ は Newton 法で落とした項 $S_*$ を $J_*^{\mathsf T}J_*$ で測ったもので、零残差では $K=0$ である。
モデル $\varphi(t;c,a)=ce^{at}$ を 4 点に当てはめる。$r_i(c,a)=ce^{at_i}-y_i$($t_i=0,1,2,3$)、$J$ の第 $i$ 行は $(e^{at_i},\ ct_ie^{at_i})$ である。初期点はどちらも $x_0=(c,a)=(1,0.5)$ とする(数値計算による値)。
(1) 零残差:$y=(1,2,4,8)$。解は $x^*=(1,\log2)$ で $r(x^*)=0$ である。誤差 $\lvert e_k\rvert$ は $0.193$、$0.111$、$1.60\times10^{-2}$、$1.72\times10^{-4}$、$7.94\times10^{-9}$ と減り、有効数字の桁数がほぼ倍々に増える(2 次収束、thm-gn-local の 3)。
(2) 残差あり:$y=(1,2,4,7)$。最小点は $x^*\approx(1.11968,\ 0.61371)$、$F(x^*)\approx0.027239$ である。誤差の比 $\lvert e_{k+1}\rvert/\lvert e_k\rvert$ は、初めの 3 回の $0.370$、$0.028$、$0.097$ のあと $0.0308$、$0.0332$、$0.0333,\dots$ と一定の値に近づき(1 次収束)、その値は $K$ のスペクトル半径 $0.03330$ に一致する。
指数関数のモデルの対数をとって 1 次の最小二乗にした当てはめは、別の量を最小にする問題の答えで、(2) の最小点とは一致しない。初期点を作るのには使える(最小二乗法 の例「指数関数のモデルと対数をとった当てはめ」)。
$\lambda\in\mathbb R$ について、$n=1$、$m=2$、$r(x)=(x+1,\ \lambda x^2+x-1)$ とする。$J(x)=(1,\ 2\lambda x+1)^{\mathsf T}$ で、
$$
F(x)-1=\frac{x^2}2\bigl(\lambda^2x^2+2\lambda x+2-2\lambda\bigr),\qquad F'(x)=x\bigl(2\lambda^2x^2+3\lambda x+2-2\lambda\bigr)
$$
である。$x^*=0$ は停留点で、$r(0)=(1,-1)\ne0$、$F''(0)=2-2\lambda$ である。Gauss–Newton の写像は
$$
\Phi(x)=x-\frac{x\bigl(2\lambda^2x^2+3\lambda x+2-2\lambda\bigr)}{1+(2\lambda x+1)^2}
$$
で、$\Phi(0)=0$、$\Phi'(0)=1-\frac{2-2\lambda}2=\lambda$ である。
Gauss–Newton の 1 歩は 1 次近似の最小点だが、1 次近似が信用できるのは $x_k$ の近くだけである。そこで、1 歩の長さに罰則を加える。
$\mu>0$ について、$m_k(p):=\frac12\lvert r(x_k)+J_kp\rvert^2$ とし、
$$
p_k(\mu):=\operatorname*{arg\,min}_p\Bigl(m_k(p)+\frac\mu2\lvert p\rvert^2\Bigr)=-(J_k^{\mathsf T}J_k+\mu I)^{-1}J_k^{\mathsf T}r(x_k)
$$
とおく。各回で $p_k(\mu_k)$ を試し、$F(x_k+p_k(\mu_k))< F(x_k)$ なら受け入れて $\mu$ を小さくし、そうでなければ $x_k$ に留まって $\mu$ を大きくする方法を Levenberg–Marquardt 法 という。
$J_k^{\mathsf T}J_k+\mu I$ は $\mu>0$ なら正定値なので、$J_k$ の列が 1 次独立でなくても $p_k(\mu)$ は定まり、右辺の式は罰則つきの 2 次関数の勾配を $0$ とおいて得られる。VMLS18 Algorithm 18.3(p. 392)は、受け入れたら $\mu$ を $0.8$ 倍、退けたら $2$ 倍にする規則を挙げている。方法は Levenberg Lev44 と Marquardt Mar63 による。
$\mu>0$、$u:=J_k^{\mathsf T}r(x_k)\ne0$ とする。
1:$\lvert p\rvert\le\Delta$ なら、$p_k(\mu)$ が罰則つきの関数の最小点であることから
$$
m_k(p)\ge m_k(p_k(\mu))+\frac\mu2\bigl(\Delta^2-\lvert p\rvert^2\bigr)\ge m_k(p_k(\mu))
$$
である。2・3:$B:=J_k^{\mathsf T}J_k$ の固有値 $s_1,\dots,s_n\ge0$ の正規直交な固有ベクトルで $u=\sum_ic_iv_i$ と書くと
$$
p_k(\mu)=-\sum_i\frac{c_i}{s_i+\mu}v_i,\qquad\lvert p_k(\mu)\rvert^2=\sum_i\frac{c_i^2}{(s_i+\mu)^2},\qquad u\cdot p_k(\mu)=-\sum_i\frac{c_i^2}{s_i+\mu}<0
$$
で、各項は $\mu$ について単調である。$\mu p_k(\mu)=-\sum_i\frac\mu{s_i+\mu}c_iv_i\to-u$($\mu\to\infty$)で、すべての $s_i>0$ なら $\mu\to0$ で $-\sum_i\frac{c_i}{s_i}v_i=-B^{-1}u$ に近づく。$\square$
$\mu$ を大きくすると 1 歩は短く、向きは $-\nabla F$ に近づいて、刻み幅の小さい 勾配降下法 に近づく。$\mu\to0$ では Gauss–Newton 法に戻る。1 の逆、すなわち球の上のモデルの最小点が罰則つきの最小点の形をしていることは、信頼領域法 の定理「部分問題の解の特徴づけ」で $B=J_k^{\mathsf T}J_k$ とした場合である。したがって、$\mu$ を直接調整する Levenberg–Marquardt 法は、半径を調整する信頼領域法と同じ 1 歩の族を使い、違うのは族の助変数の取り方である。ex-gn-counterexample の $\lambda=-2$、$x_0=0.1$ に VMLS の規則($\mu_0=1$)を当てると、値の増える 1 歩が退けられ、点は最小点 $0$ に近づく(数値計算)。
各行は thm-gn-local の条件を 1 つだけ外している。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 残差が小さいこと($\rho<\sigma^2$) | ex-gn-counterexample の $\lambda=-2$ | 最小点 $x^*=0$ のどんな近くから始めても($x_k=0$ にちょうど当たる場合を除き)$x^*$ に収束しない |
| 解での $J$ の列の 1 次独立性($\sigma>0$) | $r(x)=(x^2,\ x^2)$、$x^*=0$ | 2 次収束($J(0)=0$ で、$x_{k+1}=\frac{x_k}2$ と 1 次収束にとどまる) |
| 停留点であること($J_*^{\mathsf T}r_*=0$) | $r(x)=(x,\ 1)$、点 $x^*=1$ | $x^*$ への収束($x_1=0$ で止まる。$F'(1)=1\ne0$) |
2 行目:$J=(2x,2x)^{\mathsf T}$、$J^{\mathsf T}J=8x^2$、$J^{\mathsf T}r=4x^3$ なので $x_{k+1}=x_k-\frac{x_k}2$ である。最小点 $0$ では $J$ が $0$ になり、Newton法 の重根での振る舞い(1 次収束)と同じである。3 行目:$r$ は 1 次なので 1 回で $F$ の最小点 $0$ に達し、停留点でない点 $1$ の近くに留まる理由がない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する