Tikhonov正則化

同義語:Tikhonov regularizationチコノフ正則化リッジ回帰ridge regression

概要

Tikhonov正則化(Tikhonov regularization)とは、有界線形作用素 $A$ の方程式 $Ax=b$ を解く代わりに、$\|Ax-b\|^2+\alpha\|x\|^2$ を最小にする $x_\alpha=(A^*A+\alpha I)^{-1}A^*b$ を解とする方法である。$\alpha>0$ なら解は常にただ 1 つで $b$ に連続に依存し、特異値 $\sigma$ の項はフィルタ $\sigma^2/(\sigma^2+\alpha)$ で抑えられる。雑音の大きさ $\delta$ に対し $\alpha\to0$、$\delta^2/\alpha\to0$ なら最小ノルム解に収束し、不一致原理で $\alpha$ を決めることもできる。統計ではリッジ回帰と呼ぶ。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Hilbert空間, 随伴作用素, 特異値分解, 最小二乗法

連立方程式 $Ax=b$ の $A$ の特異値が小さいと、$b$ のわずかな誤差で解が大きく動く。たとえば $A=\begin{pmatrix}1&1\\1&1.001\end{pmatrix}$ では、$b=(2,\ 2.001)$ の解は $(1,1)$ なのに、$b$ を $0.001$ だけ変えた $(2,\ 2.002)$ の解は $(0,2)$ である。測定値には誤差があるので、この方程式を素直に解いても意味のある答えは得られない。Tikhonov正則化 は、残差だけでなく解の大きさにも罰則を付けて
$$ \|Ax-b\|^2+\alpha\|x\|^2 $$
を最小にする方法である。解は $x_\alpha=(A^*A+\alpha I)^{-1}A^*b$ と書け、小さい特異値の影響だけが抑えられる。
この記事では、解の存在と安定性、$\alpha\to0$ での収束、雑音があるときの誤差の上界、不一致原理の正しさを証明する。統計ではこの方法を リッジ回帰 と呼ぶので、平均二乗誤差についても述べる。

定義と使える条件

$X,Y$ を Hilbert空間、$A\colon X\to Y$ を有界線形作用素とする(行列を含む)。$A^*$ は 随伴作用素 である。方程式 $Ax=b$ が 適切(Hadamard の意味)であるとは、解が存在し、一意で、$b$ に連続に依存することをいう。$A$ がコンパクト作用素で値域が無限次元なら、$A$ の逆は(存在しても)有界でない。積分方程式 の第 1 種の方程式がこの形である。

最小ノルム解

$Q$ を $\overline{R(A)}$ への直交射影とし、$b\in R(A)+R(A)^\perp$ とする。このとき $Qb\in R(A)$ で、$\|Ax-b\|$ を最小にする $x$ は $Ax=Qb$ の解全体である。その中でノルム最小のものを 最小ノルム解 といい、$x^\dagger$ と書く。$x^\dagger\in N(A)^\perp$、$A^*Ax^\dagger=A^*b$ である。行列なら $x^\dagger=A^+b$ で、Moore–Penrose逆行列 の定理「最小二乗解とその最小ノルム性」がこれを述べる。

Tikhonov 正則化

$\alpha>0$ を 正則化パラメータ とする。Tikhonov 汎関数 $T_\alpha(x)=\|Ax-b\|^2+\alpha\|x\|^2$ を最小にする $x$ を、$b$ の Tikhonov 正則化解 といい、$x_\alpha$ と書く。$b$ の代わりに誤差を含む $b^\delta$($\|b^\delta-b\|\le\delta$)を使ったものを $x_\alpha^\delta$ と書く。

結論を使う条件は次のとおりである。

  1. $\alpha>0$:解の一意性と安定性に要る(反例の表の 1 行目)。
  2. $b\in R(A)+R(A)^\perp$:$\alpha\to0$ の収束に要る(2 行目)。有限次元では常に成り立つ。
  3. $\delta^2/\alpha\to0$:雑音があるときの収束に要る(3 行目)。
  4. $x^\dagger$ の滑らかさ($x^\dagger\in R(A^*)$ など):収束の速さの評価に要る(4 行目)。
  5. $\|b^\delta\|>\tau\delta$:不一致原理で $\alpha$ が決まるために要る(5 行目)。
    文献によって $\alpha$ を $\delta$、$\lambda$、$\alpha^2$ と書く。BV04 §6.3.2(p. 306)は $\delta$、HTF09 §3.4.1(pp. 63–64)は $\lambda$ である。

公式の表

量式使える条件根拠
解の式$x_\alpha=(A^*A+\alpha I)^{-1}A^*b=A^*(AA^*+\alpha I)^{-1}b$$\alpha>0$thm-tik-main
安定性$\Vert x_\alpha^\delta-x_\alpha\Vert\le\delta/(2\sqrt\alpha)$$\Vert b^\delta-b\Vert\le\delta$thm-tik-main
特異値の形$x_\alpha=\sum_i\frac{\sigma_i}{\sigma_i^2+\alpha}\langle b,u_i\rangle v_i$行列またはコンパクト作用素cor-tik-filter
誤差の式$x_\alpha-x^\dagger=-\alpha(A^*A+\alpha I)^{-1}x^\dagger$$b\in R(A)+R(A)^\perp$thm-tik-limit
速さ$\Vert x_\alpha-x^\dagger\Vert\le\frac{\sqrt\alpha}2\Vert w\Vert$$x^\dagger=A^*w$thm-tik-limit
速さ$\Vert x_\alpha-x^\dagger\Vert\le\alpha\Vert w\Vert$$x^\dagger=A^*Aw$thm-tik-limit
雑音込みの最良の順$\sqrt{\delta\Vert w\Vert}$($\alpha=\delta/\Vert w\Vert$)$x^\dagger=A^*w$thm-tik-noise
不一致原理$\Vert x_\alpha^\delta-x^\dagger\Vert\le\sqrt{2(\tau+1)\delta\Vert w\Vert}$$b=Ax^\dagger$、$x^\dagger=A^*w$、$\tau>1$thm-tik-morozov
リッジ回帰の平均二乗誤差$\sum_i\frac{s^2\sigma_i^2+\alpha^2\beta_i^2}{(\sigma_i^2+\alpha)^2}$$\sigma_i>0$、雑音が無相関で分散 $s^2$prop-tik-ridge
実効自由度$\sum_i\sigma_i^2/(\sigma_i^2+\alpha)$行列prop-tik-ridge

主定理と証明

解の存在と安定性

解の存在、一意性、安定性

$\alpha>0$ とする。

  1. $A^*A+\alpha I$ は有界な逆をもち、$\|(A^*A+\alpha I)^{-1}\|\le1/\alpha$ である。
  2. $T_\alpha$ の最小点はただ 1 つで、$x_\alpha=(A^*A+\alpha I)^{-1}A^*b=A^*(AA^*+\alpha I)^{-1}b$ である。任意の $h\in X$ について
    $$ T_\alpha(x_\alpha+h)=T_\alpha(x_\alpha)+\|Ah\|^2+\alpha\|h\|^2 $$
    である。
  3. $\|(A^*A+\alpha I)^{-1}A^*\|\le\dfrac1{2\sqrt\alpha}$ である。したがって $\|x_\alpha\|\le\|b\|/(2\sqrt\alpha)$、$\|x_\alpha^\delta-x_\alpha\|\le\delta/(2\sqrt\alpha)$ である。

1:$B=A^*A+\alpha I$ は自己随伴で、$\operatorname{Re}\langle Bx,x\rangle=\|Ax\|^2+\alpha\|x\|^2\ge\alpha\|x\|^2$ である。Schwarz の不等式から $\|Bx\|\ge\alpha\|x\|$ なので、$B$ は単射で値域は閉じている。値域の直交補は $N(B^*)=N(B)=0$ なので全射である。逆の評価は $\|Bx\|\ge\alpha\|x\|$ そのものである。
2:$x_\alpha=B^{-1}A^*b$ とおくと $A^*(Ax_\alpha-b)+\alpha x_\alpha=0$ である。展開すると
$$ T_\alpha(x_\alpha+h)=T_\alpha(x_\alpha)+2\operatorname{Re}\langle A^*(Ax_\alpha-b)+\alpha x_\alpha,h\rangle+\|Ah\|^2+\alpha\|h\|^2 $$
で、中央の項は $0$ である。$h\ne0$ なら増えるので、最小点はこれだけである。$A^*(AA^*+\alpha I)=(A^*A+\alpha I)A^*$ に両側から逆を掛けると、もう 1 つの式を得る。
3:正規方程式と $x_\alpha$ の内積をとると $\alpha\|x_\alpha\|^2=\operatorname{Re}\langle b,Ax_\alpha\rangle-\|Ax_\alpha\|^2\le\|b\|\,\|Ax_\alpha\|-\|Ax_\alpha\|^2\le\|b\|^2/4$ である。これは $\|B^{-1}A^*b\|\le\|b\|/(2\sqrt\alpha)$ を意味する。$x_\alpha^\delta-x_\alpha=B^{-1}A^*(b^\delta-b)$ なので後半が従う。$\square$

特異値のフィルタ

$A=\sum_i\sigma_iu_iv_i^*$($\sigma_i>0$、行列またはコンパクト作用素)なら
$$ x_\alpha=\sum_i\frac{\sigma_i^2}{\sigma_i^2+\alpha}\cdot\frac{\langle b,u_i\rangle}{\sigma_i}v_i $$
である。最小ノルム解の各項 $\langle b,u_i\rangle v_i/\sigma_i$ に フィルタ $\sigma_i^2/(\sigma_i^2+\alpha)$ が掛かり、$\sigma_i^2\gg\alpha$ の項はほぼそのまま残り、$\sigma_i^2\ll\alpha$ の項は抑えられる。

$A^*Av_i=\sigma_i^2v_i$ で、$v_i$ の直交補の上では $A^*A=0$ である。$A^*b=\sum_i\sigma_i\langle b,u_i\rangle v_i$ に $(A^*A+\alpha I)^{-1}$ を掛ける。$\square$

$\alpha\to0$ の極限

雑音のないときの極限

$b\in R(A)+R(A)^\perp$ とし、$e_\alpha=x_\alpha-x^\dagger$ とする。

  1. $e_\alpha=-\alpha(A^*A+\alpha I)^{-1}x^\dagger$、$\|e_\alpha\|\le\|x^\dagger\|$ で、$\alpha\to0$ で $e_\alpha\to0$ である。
  2. $x^\dagger=A^*w$ なら $\|e_\alpha\|\le\frac{\sqrt\alpha}2\|w\|$、$x^\dagger=A^*Aw$ なら $\|e_\alpha\|\le\alpha\|w\|$ である。
  3. $\|e_\alpha\|\ge\dfrac{\alpha\|x^\dagger\|}{\|A\|^2+\alpha}$ である。したがって $x^\dagger\ne0$ なら、どんな滑らかさを仮定しても速さは $\alpha$ の 1 次を超えない。
  4. $b\notin R(A)+R(A)^\perp$ なら $\alpha\to0$ で $\|x_\alpha\|\to\infty$ である。

$B=A^*A+\alpha I$ とする。1:$A^*b=A^*Ax^\dagger=(B-\alpha I)x^\dagger$ なので $x_\alpha=x^\dagger-\alpha B^{-1}x^\dagger$ である。$\|\alpha B^{-1}\|\le1$ から評価を得る。
2:thm-tik-main の 3 から $\|\alpha B^{-1}A^*w\|\le\frac{\sqrt\alpha}2\|w\|$ である。また $B^{-1}A^*A=I-\alpha B^{-1}$ のノルムは $1$ 以下なので $\|\alpha B^{-1}A^*Aw\|\le\alpha\|w\|$ である。
1 の収束:$x^\dagger\in N(A)^\perp=\overline{R(A^*)}$ なので、$\varepsilon>0$ に対し $\|x^\dagger-A^*w\|<\varepsilon$ となる $w$ がある。$\|\alpha B^{-1}\|\le1$ と 2 の計算から $\|e_\alpha\|\le\varepsilon+\frac{\sqrt\alpha}2\|w\|$ である。
3:$y=B^{-1}x^\dagger$ とすると $\|x^\dagger\|=\|By\|\le(\|A\|^2+\alpha)\|y\|$、$\|e_\alpha\|=\alpha\|y\|$ である。
4:$\alpha_n\to0$ で $x_n=x_{\alpha_n}$ が有界だとする。部分列をとって $x_n$ は $x$ に弱収束するとしてよい。$A^*Ax_n=A^*b-\alpha_nx_n\to A^*b$ で、$A^*A$ は弱連続なので $A^*Ax=A^*b$ である。よって $b-Ax\in N(A^*)=R(A)^\perp$ で、$b\in R(A)+R(A)^\perp$ となり矛盾する。$\square$

3 の現象を 飽和 という。$x^\dagger$ がいくら滑らかでも、誤差は $\alpha$ の 1 次より速く減らない。

雑音があるとき

雑音込みの誤差

$b\in R(A)+R(A)^\perp$、$\|b^\delta-b\|\le\delta$ とする。
$$ \|x_\alpha^\delta-x^\dagger\|\le\frac\delta{2\sqrt\alpha}+\|e_\alpha\| $$
である。したがって次が成り立つ。

  1. $\delta\to0$ で $\alpha(\delta)\to0$、$\delta^2/\alpha(\delta)\to0$ なら $x_{\alpha(\delta)}^\delta\to x^\dagger$ である。
  2. $x^\dagger=A^*w$($w\ne0$)で $\alpha=\delta/\|w\|$ なら、誤差は $\sqrt{\delta\|w\|}$ 以下である。
  3. $x^\dagger=A^*Aw$($w\ne0$)で $\alpha=(\delta/(4\|w\|))^{2/3}$ なら、誤差は $3\|w\|^{1/3}(\delta/4)^{2/3}$ 以下である。

三角不等式と thm-tik-main の 3 による。1 は thm-tik-limit の 1 から従う。2 は $\frac\delta{2\sqrt\alpha}+\frac{\sqrt\alpha}2\|w\|$ に代入する。3 は $\frac\delta{2\sqrt\alpha}+\alpha\|w\|$ に代入すると、$\alpha^{3/2}=\delta/(4\|w\|)$ から第 1 項が $2\alpha\|w\|$ になり、和は $3\alpha\|w\|$ である。$\square$

第 1 項は $\alpha$ を小さくすると増え、第 2 項は減る。この 2 つの釣り合いで最良の $\alpha$ が決まり、$\alpha$ を小さくしていくと誤差は一度減ってから増える(ex-tik-integral)。ただし上の $\alpha$ は $\|w\|$ を知らないと決められない。

不一致原理

雑音の大きさ $\delta$ だけ分かるなら、残差が雑音と同じ大きさになるところまで緩める。これを 不一致原理 という(Morozov)。

不一致原理の正しさ

$b=Ax^\dagger$、$\delta>0$、$\|b^\delta-b\|\le\delta$、$\tau>1$、$\|b^\delta\|>\tau\delta$ とし、$\varphi(\alpha)=\|Ax_\alpha^\delta-b^\delta\|$ とおく。

  1. $\varphi$ は $(0,\infty)$ で連続かつ狭義単調増加で、$\varphi(\alpha)=\tau\delta$ となる $\alpha$ がただ 1 つある。
  2. その $\alpha$ について $\|x_\alpha^\delta\|\le\|x^\dagger\|$、$\|Ax_\alpha^\delta-b\|\le(\tau+1)\delta$ である。
  3. $x^\dagger=A^*w$ なら $\|x_\alpha^\delta-x^\dagger\|\le\sqrt{2(\tau+1)\delta\|w\|}$ である。
  4. $\|b^\delta\|\le\tau\delta$ のときは $x^\delta=0$ を採用し、そうでなければこの $\alpha$ の解を $x^\delta$ とすると、$\delta\to0$ で $x^\delta\to x^\dagger$ である。

$x_\alpha=x_\alpha^\delta$ と略す。
1:$b^\delta-Ax_\alpha=\alpha(AA^*+\alpha I)^{-1}b^\delta$ である(thm-tik-main の 2 の式による)。したがって $\varphi$ は連続である。$\alpha<\beta$ とする。$T_\alpha(x_\alpha)\le T_\alpha(x_\beta)$ と $T_\beta(x_\beta)\le T_\beta(x_\alpha)$ を足すと $\|x_\beta\|\le\|x_\alpha\|$ を得て、最初の不等式から
$$ \varphi(\beta)^2-\varphi(\alpha)^2\ge\alpha(\|x_\alpha\|^2-\|x_\beta\|^2)\ge0 $$
である。等号なら $T_\alpha(x_\beta)=T_\alpha(x_\alpha)$ なので最小点の一意性から $x_\alpha=x_\beta$ で、2 つの正規方程式の差から $x_\alpha=0$、すなわち $A^*b^\delta=0$ である。
極限を調べる。$\alpha\to\infty$ では $\|Ax_\alpha\|\le\|A\|\,\|b^\delta\|/(2\sqrt\alpha)\to0$ なので $\varphi\to\|b^\delta\|$ である。$\alpha\to0$ では、$H=AA^*$ として $C_\alpha=\alpha(H+\alpha I)^{-1}$ は $\|C_\alpha\|\le1$ を満たし、$z\in N(A^*)$ で $C_\alpha z=z$、$z=Au$ で $\|C_\alpha Au\|=\alpha\|A(A^*A+\alpha I)^{-1}u\|\le\frac{\sqrt\alpha}2\|u\|\to0$ である($A(A^*A+\alpha I)^{-1}$ は thm-tik-main の 3 の作用素の随伴である)。稠密性から $C_\alpha b^\delta\to(I-Q)b^\delta$ で、$b\in R(A)$ なので $\lim_{\alpha\to0}\varphi=\|(I-Q)(b^\delta-b)\|\le\delta$ である。
$\tau>1$ と仮定から、$\lim_{\alpha\to0}\varphi\le\delta< \tau\delta< \|b^\delta\|=\lim_{\alpha\to\infty}\varphi$ である。とくに $\varphi$ は定数でなく、$A^*b^\delta\ne0$($A^*b^\delta=0$ なら $\varphi\equiv\|b^\delta\|$)なので狭義単調である。中間値の定理から解はただ 1 つある。
2:$T_\alpha(x_\alpha)\le T_\alpha(x^\dagger)$ から $\tau^2\delta^2+\alpha\|x_\alpha\|^2\le\delta^2+\alpha\|x^\dagger\|^2$ で、$\tau>1$ より $\|x_\alpha\|\le\|x^\dagger\|$ である。残差は三角不等式による。
3:2 から
$$ \|x_\alpha-x^\dagger\|^2\le2\|x^\dagger\|^2-2\operatorname{Re}\langle x_\alpha,x^\dagger\rangle=2\operatorname{Re}\langle x^\dagger-x_\alpha,A^*w\rangle=2\operatorname{Re}\langle b-Ax_\alpha,w\rangle\le2(\tau+1)\delta\|w\| $$
である。
4:$b=0$ なら $x^\dagger=0$ で、$\|x^\delta\|\le\|x^\dagger\|$ から明らかである($\|b^\delta\|\le\tau\delta$ なら $x^\delta=0$)。$b\ne0$ なら、小さい $\delta$ で $\|b^\delta\|\ge\|b\|-\delta>\tau\delta$ である。$\varepsilon>0$ に対し $x^\dagger=A^*w+z$、$\|z\|<\varepsilon$ とすると、3 と同じ計算で $\|x_\alpha-x^\dagger\|^2\le2(\tau+1)\delta\|w\|+4\|x^\dagger\|\varepsilon$ である。$\delta\to0$、$\varepsilon\to0$ の順に極限をとる。$\square$

統計の見方

計画行列 $Z$($n\times p$)、$y=Z\beta+\varepsilon$ の線形回帰で、$A=Z$、$b=y$ とした $\hat\beta_\alpha=(Z^{\mathsf T}Z+\alpha I)^{-1}Z^{\mathsf T}y$ を リッジ回帰 の推定量という(HTF09 §3.4.1、pp. 63–64。BV04 §6.3.2、p. 306 の問題と同じものである)。

リッジ回帰の平均二乗誤差

$Z$ の特異値を $\sigma_1,\dots,\sigma_p>0$、右特異ベクトルを $v_i$、$\beta_i=\langle\beta,v_i\rangle$ とし、$\varepsilon$ は平均 $0$、共分散行列 $s^2I$($s>0$)とする。
$$ \operatorname{MSE}(\alpha):=E\|\hat\beta_\alpha-\beta\|^2=\sum_{i=1}^p\frac{s^2\sigma_i^2+\alpha^2\beta_i^2}{(\sigma_i^2+\alpha)^2} $$
である。$\operatorname{MSE}'(0)=-2s^2\sum_i\sigma_i^{-4}< 0$ なので、十分小さい $\alpha>0$ でリッジ回帰の平均二乗誤差は最小二乗推定量より小さい。また $\operatorname{tr}\bigl(Z(Z^{\mathsf T}Z+\alpha I)^{-1}Z^{\mathsf T}\bigr)=\sum_i\sigma_i^2/(\sigma_i^2+\alpha)$(実効自由度)である。

$\tilde\varepsilon_i=\langle\varepsilon,u_i\rangle$ とすると $E\tilde\varepsilon_i=0$、$E\tilde\varepsilon_i^2=s^2$ である。cor-tik-filter から $\langle\hat\beta_\alpha,v_i\rangle=\frac{\sigma_i}{\sigma_i^2+\alpha}(\sigma_i\beta_i+\tilde\varepsilon_i)$ なので、
$$ \langle\hat\beta_\alpha-\beta,v_i\rangle=-\frac{\alpha\beta_i}{\sigma_i^2+\alpha}+\frac{\sigma_i\tilde\varepsilon_i}{\sigma_i^2+\alpha} $$
である。第 1 項が偏り、第 2 項の分散が $s^2\sigma_i^2/(\sigma_i^2+\alpha)^2$ で、平方の期待値を足すと式を得る。$\alpha=0$ で微分すると、分子の項は $\alpha$ の 2 次なので寄与せず、$-2s^2\sigma_i^2/\sigma_i^6$ が残る。跡は $Z$ を特異値分解すれば分かる。$\square$

最小二乗推定量は線形不偏推定量の中で分散が最小である(Gauss–Markovの定理)。この命題は、不偏性を捨てれば平均二乗誤差でそれを超えられることを示す。$\beta$ の事前分布を $N(0,(s^2/\alpha)I)$、雑音を $N(0,s^2I)$ とすれば、$\hat\beta_\alpha$ は事後分布の最頻値である(HTF09 p. 64、Bayes統計)。

計算の手順

  1. 尺度をそろえる。 罰則 $\|x\|^2$ は座標の尺度に依存する。統計では説明変数を標準化し、切片には罰則を付けない(HTF09 pp. 63–64)。
  2. 解を計算する。 同じ $A$ で多くの $\alpha$ を試すなら、特異値分解を 1 回計算して cor-tik-filter を使う。1 回だけなら、拡大した最小二乗問題 $\min\Bigl\|\begin{pmatrix}A\\\sqrt\alpha I\end{pmatrix}x-\begin{pmatrix}b\\0\end{pmatrix}\Bigr\|$ を QR 分解で解くと、$A^*A$ を作らないので条件数の 2 乗を避けられる(最小二乗法 の命題「正規方程式の条件数」)。
  3. $\alpha$ を決める。 $\delta$ が分かるなら不一致原理(thm-tik-morozov)を使い、$\varphi(\alpha)=\tau\delta$ を $\log\alpha$ についての二分法で解く。$\delta$ が分からないなら交差検証などの方法を使う。
    図: 左は特異値 σ に対するフィルタ σ²/(σ²+α) のグラフで、α を 10⁻⁴、10⁻²、1 としたとき、σ² が α より十分大きければ 1 に近く、十分小さければ 0 に近い。右は例題「積分作用素」の誤差を α に対して両対数目盛で描いたもので、誤差は α を小さくすると一度減ってから増え、不一致原理の α は最小の近くにある。 図: 左は特異値 σ に対するフィルタ σ²/(σ²+α) のグラフで、α を 10⁻⁴、10⁻²、1 としたとき、σ² が α より十分大きければ 1 に近く、十分小さければ 0 に近い。右は例題「積分作用素」の誤差を α に対して両対数目盛で描いたもので、誤差は α を小さくすると一度減ってから増え、不一致原理の α は最小の近くにある。

例題

2 次の悪条件行列

$A=\begin{pmatrix}1&1\\1&1.001\end{pmatrix}$、$b=(2,\ 2.001)$、$x^\dagger=(1,1)$、$b^\delta=(2,\ 2.002)$($\delta=0.001$)とする。
使う公式:thm-tik-main、thm-tik-noise、thm-tik-morozov。
答え:特異値は $2.0005,\ 0.0005$、条件数は $4002.0$ で、素朴な解は $(0,2)$(誤差 $1.414$)である。$\tau=1.1$ の不一致原理では $\alpha\approx0.0011926$、$x_\alpha^\delta\approx(0.99949,\ 1.00041)$、誤差 $6.53\times10^{-4}$ である。

$\alpha$$x_\alpha^\delta$誤差残差
$10^{-6}$$(0.80008,\ 1.20032)$$0.2830$$5.65\times10^{-4}$
$10^{-5}$$(0.97562,\ 1.02486)$$0.0348$$6.90\times10^{-4}$
$10^{-4}$$(0.99748,\ 1.00297)$$0.00389$$7.09\times10^{-4}$
$10^{-3}$$(0.99950,\ 1.00050)$$7.07\times10^{-4}$$9.995\times10^{-4}$
$10^{-2}$$(0.99748,\ 0.99803)$$0.00320$$0.00709$
$10^{-1}$$(0.97562,\ 0.97611)$$0.0341$$0.0690$
対角行列とフィルタ

$A=\operatorname{diag}(1,\ 0.1,\ 0.01)$、$x^\dagger=(1,1,1)$、$b^\delta=Ax^\dagger+0.01\cdot(1,1,1)/\sqrt3$ とする。
使う公式:cor-tik-filter。
答え:素朴な解は $(1.00577,\ 1.05774,\ 1.57735)$(誤差 $0.5803$)で、誤差は最も小さい特異値の成分に集まる。

$\alpha$フィルタ$x_\alpha^\delta$誤差
$10^{-4}$$(0.9999,\ 0.9901,\ 0.5)$$(1.00567,\ 1.04726,\ 0.78868)$$0.2166$
$10^{-3}$$(0.9990,\ 0.9091,\ 0.0909)$$(1.00477,\ 0.96158,\ 0.14340)$$0.8575$
$10^{-2}$$(0.9901,\ 0.5,\ 0.0099)$$(0.99581,\ 0.52887,\ 0.01562)$$1.0913$

$\alpha$ が大きいと第 3 成分が失われ、誤差はかえって増える。$\alpha$ は大きいほど良いのではない。

積分作用素

$(Ax)(t)=\int_0^tx(s)\,ds$ を $[0,1]$ の幅 $h=0.01$ の 100 個の格子で離散化する。行列は $h$ に下三角の $1$ を掛け、対角を $h/2$ としたもの(中点則)である。$x^\dagger_i=\sin(\pi t_i)$($t_i=(i-\frac12)h$)、$\|x^\dagger\|\approx7.071$、雑音は $\delta=0.01$ で、成分が $\delta(-1)^{i-1}/10$ のベクトルとする。
使う公式:thm-tik-noise、thm-tik-morozov。
答え:条件数は $16210.7$ で、素朴な解の誤差は $230.9$ である。$\alpha$ を小さくしていくと誤差は一度減って増える(図の右)。

$\alpha$$10^{-8}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$
誤差$35.25$$1.118$$0.1989$$0.0423$$0.1398$$0.8160$$2.892$

$\tau=1.1$ の不一致原理は $\alpha\approx2.127\times10^{-4}$、誤差 $0.0463$ で、最良の $\alpha\approx1.30\times10^{-4}$ の誤差 $0.0407$ に近い。$\delta$ を変えたときの不一致原理の誤差は次のとおりである。

$\delta$$0.1$$0.01$$0.001$$10^{-4}$
誤差$0.2699$$0.0463$$0.0134$$0.0063$
リッジ回帰の数値

$\sigma=(1,\ 0.1)$、$\beta_i=1$($i=1,2$)、$s^2=0.01$ とする。
使う公式:prop-tik-ridge。
答え:最小二乗推定量の平均二乗誤差は $1.01$ である。$\alpha=0.01$ で $0.50990$ となり、これが最小値である。実効自由度は $1.4901$ である。

途中の計算を開く

$\beta_i=1$ のとき、各項 $\frac{s^2\sigma_i^2+\alpha^2}{(\sigma_i^2+\alpha)^2}$ の $\alpha$ についての微分は $\frac{2\sigma_i^2(\alpha-s^2)}{(\sigma_i^2+\alpha)^3}$ なので、$\alpha=s^2$ で最小である。値は各項が $\frac{\alpha}{\sigma_i^2+\alpha}$ となり、$\frac{0.01}{1.01}+\frac{0.01}{0.02}$ である。

使える条件と反例

各行は、結論に必要な仮定を 1 つだけ外す。

外す仮定反例成り立たなくなること
$\alpha>0$$A=(1\ \ 1)$、$b=2$、$\alpha=0$$x_1+x_2=2$ のすべてが最小点で、一意でない。$\alpha>0$ なら $x_\alpha=\frac2{2+\alpha}(1,1)$
$b\in R(A)+R(A)^\perp$$\ell^2$ で $Ae_i=e_i/i$、$b_i=1/i$$\Vert x_\alpha\Vert\to\infty$($\alpha^{-1/4}$ の程度)
$\delta^2/\alpha\to0$$Ae_i=e_i/i$、$b=0$、$\delta=1/n$、$b^\delta=\delta e_n$、$\alpha=\delta^2$$\alpha,\delta\to0$ でも $\Vert x_\alpha^\delta\Vert=\frac12$ で、$x^\dagger=0$ に収束しない
$x^\dagger\in R(A^*)$$Ae_i=e_i/i$、$x^\dagger_i=1/i$、$b=Ax^\dagger$収束はするが $\Vert e_\alpha\Vert$ は $\alpha^{1/4}$ の程度で、$\sqrt\alpha$ の上界が成り立たない
$\Vert b^\delta\Vert>\tau\delta$$A=1$、$b^\delta=\delta$、$\tau=2$$\varphi(\alpha)=\frac{\alpha\delta}{1+\alpha}< \delta< \tau\delta$ で、$\varphi(\alpha)=\tau\delta$ に解がない
反例の確かめを開く

2 行目:$b_i=\sigma_i\cdot1$ で $(1,1,\dots)\notin\ell^2$ なので $b\notin R(A)$ で、$R(A)^\perp=0$ である。$x_{\alpha,i}=\frac1{1+\alpha i^2}$ で、和を積分と比べると $\Vert x_\alpha\Vert^2$ は $\alpha^{-1/2}$ の程度である。3 行目:$x_{\alpha,n}^\delta=\frac{\sigma_n\delta}{\sigma_n^2+\alpha}=\frac{n^{-2}}{2n^{-2}}=\frac12$ である。4 行目:$w_i=1$ が必要で $\ell^2$ に入らない。$e_{\alpha,i}=\frac{\alpha i^2}{1+\alpha i^2}\cdot\frac1i$ で、$\alpha=10^{-2},\ 10^{-4},\ 10^{-6}$ のとき $\Vert e_\alpha\Vert\approx0.2802,\ 0.0886,\ 0.0279$ である。比 $\Vert e_\alpha\Vert/\sqrt\alpha$ は $2.8,\ 8.9,\ 27.9$ と増える。

よくある誤り

誤り正しくはなぜ
$\alpha$ は大きいほど安定で良いとする偏りが増えるので、雑音との釣り合いで選ぶthm-tik-noise、ex-tik-diag
$\alpha$ を小さくすれば必ず真の解に近づくとする雑音があると、ある所から誤差は増えるex-tik-integral
雑音の大きさを知らずに $\tau\delta$ で止める$\delta$ の見積もりが小さすぎると解が暴れる。分からないなら別の選び方を使うthm-tik-morozov は $\delta$ を入力とする
正規方程式を丸めの注意なく解く悪条件なら QR 分解か特異値分解を使う手順 2
説明変数の尺度を変えても解は同じとするリッジ回帰は尺度に依存する。最小二乗法とは違う手順 1
解が滑らかなほど収束はいくらでも速くなるとする誤差は $\alpha$ の 1 次より速くならないthm-tik-limit の 3

補足

一般の罰則

$L$ を有界線形作用素、$x_0$ を基準の点として $\|Ax-b\|^2+\alpha\|L(x-x_0)\|^2$ を最小にする形もよく使う($L$ を差分にすれば滑らかさを求める。BV04 §6.3.2、p. 307)。行列で $N(A)\cap N(L)=\{0\}$ なら $A^*A+\alpha L^*L$ は正則で、解は $(A^*A+\alpha L^*L)^{-1}(A^*b+\alpha L^*Lx_0)$ である。条件を外すと一意でない。たとえば $A=L=(1\ \ 0)$ なら行列は特異で、$x_2$ が決まらない。

ほかの方法との比較

$x=\sum_if(\sigma_i)\frac{\langle b,u_i\rangle}{\sigma_i}v_i$ の形の方法はフィルタ $f$ で比べられる。第 2 の形 $x_\alpha=A^*(AA^*+\alpha I)^{-1}b$ で内積だけを使えるので、カーネル法 のカーネルリッジ回帰がこの形になる。$\ell^1$ の罰則は線形のフィルタでなく、解が疎になる(LASSO)。一般論の成書は EHN96 である。

方法フィルタ $f(\sigma)$性質
Tikhonov$\sigma^2/(\sigma^2+\alpha)$滑らか。thm-tik-limit の飽和がある
打ち切り$\sigma^2\ge\alpha$ で $1$、それ以外 $0$$A$ の階数の低い最良近似で解くのと同じ(Eckart–Youngの定理)
反復 Tikhonov($m$ 回)$1-\bigl(\alpha/(\sigma^2+\alpha)\bigr)^m$$x_{j+1}=x_j+(A^*A+\alpha I)^{-1}A^*(b-Ax_j)$、$x_0=0$
Landweber($k$ 回)$1-(1-\omega\sigma^2)^k$$x_{j+1}=x_j+\omega A^*(b-Ax_j)$、$x_0=0$。最小二乗の勾配降下法 で、$k$ が正則化パラメータの役をする
名前

方法の名前は Tik63 に、不一致原理は Mor66 による。統計での導入は HK70 である(HTF09 p. 64)。

関連項目

参考文献

[4]
A. N. Tikhonov, Solution of incorrectly formulated problems and the regularization method, Soviet Mathematics Doklady, 1963
[5]
V. A. Morozov, On the solution of functional equations by the method of regularization, Soviet Mathematics Doklady, 1966
[6]
Arthur E. Hoerl, Robert W. Kennard, Ridge regression: biased estimation for nonorthogonal problems, Technometrics, 1970

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する