カーネル法(kernel method)とは、データの点を Hilbert 空間に写して線形の方法を使う手法を、写した点どうしの内積を与える関数 $k(x,y)$(カーネル)だけで計算する方法の総称である。$k$ がある Hilbert 空間の内積として書けるのは、$k$ が対称で、有限個の点の Gram 行列 $(k(x_i,x_j))$ がつねに半正定値であるとき(正定値カーネル)に限り、そのとき $k$ を再生核とする関数の Hilbert 空間(再生核 Hilbert 空間)がただ 1 つ定まる(Moore–Aronszajn の定理)。データ点での値とノルムの非減少関数の和を最小にする問題の解は、データ点のカーネルの 1 次結合にとれ(表現定理)、カーネルリッジ回帰の係数は $(K+\lambda I)^{-1}y$ で与えられる。回帰・分類・サポートベクターマシンに使う。
前提知識: Hilbert空間, 正定値行列, 射影定理(Hilbert空間), 最小二乗法
カーネル法(kernel method)は、データの点 $x\in X$ をある Hilbert空間 $H$ の点 $\varphi(x)$ に写し、$H$ の中で線形の方法(線形回帰、線形の分類)を使う手法の総称である。$H$ の次元は非常に大きくてよく、無限次元でもよい。鍵になるのは、多くの線形の方法が点どうしの内積 $\langle\varphi(x),\varphi(x')\rangle$ だけで計算できることである。この内積を関数 $k(x,x')$ として直接与えれば、$\varphi$ を書き下さずに済む(カーネルトリック)。
たとえば $X=\mathbb{R}$ の 1 次元のデータに 2 次以下の多項式を当てはめるのは、$\varphi(x)=(1,\sqrt2x,x^2)$ に写して 1 次式を当てはめることである。このとき $\langle\varphi(x),\varphi(y)\rangle=(1+xy)^2$ で、内積は元の空間で簡単に計算できる。Gauss 型の $k(x,y)=e^{-(x-y)^2/2}$ も、ある Hilbert 空間の内積として書ける(prop-km-closure と cor-km-characterization)。その構成には指数関数の冪級数のすべての次数の項が現れる。
どんな関数 $k$ が内積として書けるか。その答えが 正定値カーネル で、正定値カーネルには関数の空間である 再生核 Hilbert 空間 がただ 1 つ対応する(Moore–Aronszajn の定理。証明は 再生核Hilbert空間 で行う)。この記事ではこれを使って、学習の問題の解がデータ点のカーネルの 1 次結合で書けること(表現定理)と、カーネルリッジ回帰の解の公式を証明する。サポートベクターマシン はこの枠組みの代表的な応用である。
以下、$X$ は空でない集合で、関数は実数値とする。$m\ge1$ と $x_1,\dots,x_m\in X$ について、行列 $K=(k(x_i,x_j))_{i,j}$ を Gram 行列 という。
関数 $k\colon X\times X\to\mathbb{R}$ が 正定値カーネル(positive definite kernel)であるとは、次の 2 つを満たすことをいう。
名前に「正定値」とあるが、Gram 行列に求めるのは半正定値性である(文献によって「半正定値カーネル」「正の型の核」ともいう。Mercerの定理 の記事の「正の型の核」は、区間の上の連続な核についての同じ条件である)。
$X$ 上の実数値関数からなる Hilbert 空間 $H$(和とスカラー倍は各点ごと)と、関数 $k\colon X\times X\to\mathbb{R}$ が次を満たすとき、$H$ を $k$ を 再生核 とする 再生核 Hilbert 空間(reproducing kernel Hilbert space、RKHS)という。
再生性から $k(y,x)=k_x(y)=\langle k_x,k_y\rangle_H$ なので、再生核は対称で、Gram 行列は $\sum_{i,j}c_ic_jk(x_i,x_j)=\bigl\|\sum_ic_ik_{x_i}\bigr\|^2\ge0$ を満たす。つまり再生核は正定値カーネルである。また $\lvert f(x)\rvert\le\| f\|_H\sqrt{k(x,x)}$(Cauchy–Schwarz)なので、ノルムで近い関数は各点でも近い。これが $L^2$ 空間(関数は零集合の上の値を除いて決まる)との違いである。
この記事の結論を使う条件をまとめる。
$\mathcal H$ を実 Hilbert 空間、$\varphi\colon X\to\mathcal H$ を写像とすると、$k(x,y)=\langle\varphi(x),\varphi(y)\rangle$ は正定値カーネルである。
対称性は内積の対称性による。$\sum_{i,j}c_ic_jk(x_i,x_j)=\bigl\langle\sum_ic_i\varphi(x_i),\sum_jc_j\varphi(x_j)\bigr\rangle=\bigl\|\sum_ic_i\varphi(x_i)\bigr\|^2\ge0$ である。$\square$
逆も成り立ち、そのとき $\mathcal H$ として関数の空間をとれる。
$k$ を $X$ 上の正定値カーネルとする。$k$ を再生核とする再生核 Hilbert 空間 $H_k$ がただ 1 つ存在する。$H_k$ の中で、$k_x$($x\in X$)の有限個の 1 次結合全体 $H_0$ は稠密である。
この記事では証明せず、再生核Hilbert空間 の定理「Moore–Aronszajn の定理」で証明する。構成の要点は、$k_x$ の有限個の 1 次結合の空間に $\langle k_x,k_y\rangle_0=k(x,y)$ で内積を入れ、再生性から出る評価 $\lvert f(x)\rvert\le\| f\|_0\sqrt{k(x,x)}$ を使って、その完備化を関数の空間として読むことである。同じ記事は、再生核をもつことが評価写像の連続性と同値であること(定理「再生核の存在と一意性」)や、関数が $H_k$ に属するかの判定(定理「属する関数の判定」)も扱う。
関数 $k\colon X\times X\to\mathbb{R}$ について、次は同値である。
2 から 1 は prop-km-feature。1 から 2 は、thm-km-moore-aronszajn の $H_k$ と $\varphi(x)=k_x$ をとれば、再生性から $\langle k_x,k_y\rangle=k_y(x)=k(x,y)$ である。$\square$
この系は SSBD14 Lemma 16.2 にあたる(そこでの証明は内積の正値性と完備化を省略している)。正定値カーネル $k$ を決めることは、特徴写像を決めることと同じで、しかも特徴の空間として関数の空間 $H_k$ を標準的にとれる。
$H$ を $k$ を再生核とする再生核 Hilbert 空間、$x_1,\dots,x_m\in X$、$L\colon\mathbb{R}^m\to\mathbb{R}\cup\{+\infty\}$ を任意の関数、$\Omega\colon[0,\infty)\to\mathbb{R}$ を非減少な関数とし、
$$
J(f)=L\bigl(f(x_1),\dots,f(x_m)\bigr)+\Omega(\| f\|_H)\qquad(f\in H)
$$
とおく。$V=\{\sum_{i=1}^m\alpha_ik_{x_i}\mid\alpha\in\mathbb{R}^m\}$ とする。
$V$ は有限次元なので閉部分空間で、射影定理(Hilbert空間) により $f\in H$ は $f=Pf+u$($Pf\in V$、$u\perp V$)とただ 1 通りに分けられる。$u\perp k_{x_i}$ と再生性から $u(x_i)=\langle u,k_{x_i}\rangle=0$ なので $f(x_i)=(Pf)(x_i)$($i=1,\dots,m$)で、$L$ の項は $f$ と $Pf$ で等しい。$\| f\|^2=\| Pf\|^2+\| u\|^2\ge\| Pf\|^2$ と $\Omega$ が非減少であることから $\Omega(\| Pf\|)\le\Omega(\| f\|)$ で、$J(Pf)\le J(f)$ である。
1:$f$ が最小点なら $J(Pf)\le J(f)$ から $Pf\in V$ も最小点である。2:最小点 $f$ で $u\ne0$ なら $\| Pf\|<\| f\|$ で、$J(f)$ は有限で $\Omega$ が狭義増加なので $J(Pf)< J(f)$ となり、最小性に反する。よって $u=0$、$f=Pf\in V$ である。$\square$
これにより、無限次元の空間 $H$ での最小化が、係数 $\alpha\in\mathbb{R}^m$ についての最小化になる。$f=\sum_i\alpha_ik_{x_i}$ なら $f(x_j)=(K\alpha)_j$、$\| f\|^2=\alpha^{\mathsf T}K\alpha$ で、どちらも Gram 行列 $K$ だけで計算できる。1 の主張と証明は SSBD14 Theorem 16.1(特徴写像の言葉で述べたもの)、2 乗のノルムの正則化の場合は HTF09 §5.8.1(式 (5.48)–(5.52)、pp. 168–169)にある。
$H$ を $k$ を再生核とする再生核 Hilbert 空間、$(x_i,y_i)\in X\times\mathbb{R}$($i=1,\dots,m$)、$\lambda>0$ とする。
$$
J(f)=\sum_{i=1}^m\bigl(f(x_i)-y_i\bigr)^2+\lambda\| f\|_H^2
$$
は $H$ でただ 1 つの最小点をもち、それは
$$
f^\ast=\sum_{i=1}^m\alpha_ik_{x_i},\qquad\alpha=(K+\lambda I)^{-1}y
$$
である。学習データでの値は $(f^\ast(x_1),\dots,f^\ast(x_m))=K(K+\lambda I)^{-1}y$ である。
$K$ は半正定値なので $K+\lambda I$ の固有値は $\lambda$ 以上で、可逆である。$g\in V$ を $g=\sum_i\beta_ik_{x_i}$ と書くと $J(g)=\lvert K\beta-y\rvert^2+\lambda\beta^{\mathsf T}K\beta$ である。$\alpha=(K+\lambda I)^{-1}y$ について $y-K\alpha=\lambda\alpha$ なので、$\beta=\alpha+\gamma$ とおいて展開すると
$$
J(g)-J(f^\ast)=\lvert K\gamma\rvert^2-2\gamma^{\mathsf T}K(y-K\alpha)+2\lambda\gamma^{\mathsf T}K\alpha+\lambda\gamma^{\mathsf T}K\gamma=\lvert K\gamma\rvert^2+\lambda\gamma^{\mathsf T}K\gamma\ge0
$$
である。よって $f^\ast$ は $V$ での最小点である。prf-km-representer と同じく、任意の $f\in H$ で $J(Pf)\le J(f)$ なので、$f^\ast$ は $H$ での最小点である。一意性:$\|\cdot\|^2$ は狭義凸で、$f\mapsto\sum_i(f(x_i)-y_i)^2$ は凸なので、$J$ は狭義凸であり、最小点は 1 つしかない。$\square$
$\alpha$ の式は HTF09 §5.8.2 の式 (5.54)–(5.58)(pp. 170–171)と同じである。$K$ が特異なら $\alpha$ の代わりに $\alpha+\gamma$($K\gamma=0$)も同じ $f^\ast$ を与えるが、$K+\lambda I$ を使えば $\alpha$ も 1 つに決まる。
図: Gauss カーネル exp(-(x-y)^2/(2σ^2)) によるカーネルリッジ回帰。13 個の点 x=0,0.5,…,6 で sin x に雑音を足したデータ(黒い点)に当てはめた関数。左は σ=0.7 で λ=0.0001、0.1、10 としたもの。λ が小さいと点をほぼ通って振動し、大きいと 0 に近づく。右は λ=0.1 で σ=0.15、0.7、3 としたもの。σ が小さいと点ごとに山ができ、大きいとなめらかすぎる。点線は sin x。
$k_1,k_2$ を $X$ 上の正定値カーネルとする。
1・3・4 は Gram 行列の 2 次形式についての対応する事実($0$ 以上の数の和、極限、$c_i$ を $c_ig(x_i)$ に替える)から従う。2 は Gram 行列の成分ごとの積が半正定値であること、すなわち Schurの積定理 の定理「Schurの積定理」である。5:$x\cdot y$ は prop-km-feature から正定値カーネルで、定数 $c\ge0$ も正定値カーネルなので、1 と 2 から $(c+x\cdot y)^p$ は正定値カーネルである。$\exp(x\cdot y/\sigma^2)=\sum_{p\ge0}(x\cdot y/\sigma^2)^p/p!$ は 1・2・3 から正定値カーネルで、$g(x)=\exp(-\lvert x\rvert^2/(2\sigma^2))$ として 4 を使うと、$g(x)\exp(x\cdot y/\sigma^2)g(y)=\exp(-\lvert x-y\rvert^2/(2\sigma^2))$ である。$\square$
Gauss カーネルの Gram 行列の半正定値性は Schurの積定理 の例「Gauss 核の行列」でも確かめられている(点を $1/(\sqrt2\sigma)$ 倍するとその例の形になる)。
| 量・操作 | 式 | 使える条件 | 根拠 |
|---|---|---|---|
| 特徴写像の内積 | $k(x,y)=\langle\varphi(x),\varphi(y)\rangle$ | $\varphi$ は Hilbert 空間への写像 | prop-km-feature |
| 再生性 | $f(x)=\langle f,k_x\rangle_H$、$k(x,y)=\langle k_x,k_y\rangle_H$ | $H$ は $k$ の RKHS | def-km-rkhs |
| 各点の評価 | $\lvert f(x)\rvert\le\Vert f\Vert_H\sqrt{k(x,x)}$ | 同上 | Cauchy–Schwarz |
| 1 次結合のノルム | $\Vert\sum_i\alpha_ik_{x_i}\Vert^2=\alpha^{\mathsf T}K\alpha$ | 同上 | 再生性 |
| 表現定理 | 最小点を $\sum_i\alpha_ik_{x_i}$ の形にとれる | $\Omega$ が非減少、最小点がある | thm-km-representer |
| カーネルリッジ回帰 | $\alpha=(K+\lambda I)^{-1}y$ | $\lambda>0$ | prop-km-krr |
| 多項式カーネル | $(c+x\cdot y)^p$ | $c\ge0$ | prop-km-closure |
| Gauss カーネル | $\exp(-\lvert x-y\rvert^2/(2\sigma^2))$ | $\sigma>0$ | prop-km-closure |
カーネルリッジ回帰で、データ $(x_i,y_i)$ から関数 $f^\ast$ を求め、新しい点 $x$ での値を予測する手順である。
| 状況 | 起こること | 対処 |
|---|---|---|
| $\lambda$ が小さすぎる | 点をほぼ通り、点のあいだで振動する(図の左) | $\lambda$ を大きくする |
| $\lambda$ が大きすぎる | $f^\ast$ が $0$ に近づく | $\lambda$ を小さくする |
| $\sigma$ が小さすぎる | 各点のまわりにだけ山ができ、点から離れると $0$ | $\sigma$ を点の間隔より大きくする(図の右) |
| $m$ が大きい | Gram 行列が大きく、$m^3$ の計算が重い | 低い階数の近似、乱択の特徴写像 |
$X=\mathbb{R}^2$、$k(x,y)=(x\cdot y)^2$ の特徴写像を求め、4 点 $(1,0),(0,1),(1,1),(1,-1)$ の Gram 行列を計算する。
使う公式:prop-km-feature。
答え:$\varphi(x)=(x_1^2,\sqrt2x_1x_2,x_2^2)\in\mathbb{R}^3$ で $k(x,y)=\varphi(x)\cdot\varphi(y)$。Gram 行列の行は $(1,0,1,1)$、$(0,1,1,1)$、$(1,1,4,0)$、$(1,1,0,4)$ で、固有値は $0,1,4,5$ である。点が 4 個で特徴の空間が 3 次元なので、固有値 $0$ が現れる。
$(x_1y_1+x_2y_2)^2=x_1^2y_1^2+2x_1x_2y_1y_2+x_2^2y_2^2$。$\varphi(1,1)=(1,\sqrt2,1)$、$\varphi(1,-1)=(1,-\sqrt2,1)$ の内積は $1-2+1=0$。$\varphi(1,0)+\varphi(0,1)=(1,0,1)$ と $\varphi(1,1)+\varphi(1,-1)=(2,0,2)$ が比例するので、$2\varphi(1,0)+2\varphi(0,1)-\varphi(1,1)-\varphi(1,-1)=0$ で、固有値 $0$ の固有ベクトルは $(2,2,-1,-1)$ である。
答え:たとえば $f(u)=u(1-u)$ のノルムの 2 乗は $\int_0^1(1-2u)^2du=\frac13$、$k_{1/4}+k_{3/4}$ のノルムの 2 乗は $k(\frac14,\frac14)+2k(\frac14,\frac34)+k(\frac34,\frac34)=\frac32$ である。
1:$\{f_w\}$ に $\langle f_w,f_v\rangle=w\cdot v$ を入れると $\mathbb{R}^d$ と同じ Hilbert 空間で($w\mapsto f_w$ は単射)、$k_x=f_x$、$\langle f_w,k_x\rangle=w\cdot x=f_w(x)$。thm-km-moore-aronszajn の一意性から、これが RKHS である。2:$k_t(u)=\min(u,t)$ は $k_t(0)=0$、$k_t'=\mathbf 1_{[0,t]}$ なので空間に属し、$\langle f,k_t\rangle=\int_0^tf'(u)\,du=f(t)-f(0)=f(t)$。$f\mapsto f'$ はこの空間から $L^2(0,1)$ への等長な全単射(逆は $h\mapsto\int_0^th(u)\,du$)なので、空間は完備である。一意性から RKHS である。$k_{1/4}+k_{3/4}$ の導関数は $[0,\frac14]$ で $2$、$[\frac14,\frac34]$ で $1$、それ以降 $0$ なので、$\int=4\cdot\frac14+1\cdot\frac12=\frac32$。
2 の空間は Brown運動 の共分散 $\min(s,t)$ の RKHS で、Cameron–Martin 空間とも呼ばれる。Mercerの定理 の例「Brown 運動の共分散」は同じ核の固有関数展開である。
Gauss カーネル $k(x,y)=e^{-(x-y)^2/2}$、データ $(0,0),(1,1),(2,0)$、$\lambda=0.1$ で $f^\ast$ を求める。
使う公式:prop-km-krr。
答え:$\alpha\approx(-0.973393,\ 1.982532,\ -0.973393)$。$f^\ast(1)\approx0.801747$、$f^\ast(0)=f^\ast(2)\approx0.097339$、$f^\ast(1.5)\approx0.574548$ である。正則化のため $f^\ast(1)$ は $1$ より小さい。
$K$ の行は $(1,e^{-1/2},e^{-2})$、$(e^{-1/2},1,e^{-1/2})$、$(e^{-2},e^{-1/2},1)$ で、$e^{-1/2}\approx0.606531$、$e^{-2}\approx0.135335$。対称性から $\alpha=(a,b,a)$ とおくと、$(K+0.1I)\alpha=(0,1,0)$ は $(1.1+e^{-2})a+e^{-1/2}b=0$、$2e^{-1/2}a+1.1b=1$。これを解く。$f^\ast(1.5)=a(e^{-9/8}+e^{-1/8})+be^{-1/8}$。
各行は、この記事の定理の仮定を 1 つだけ外す。
| 外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|
| 対称性 | $X=\mathbb{R}$、$k(x,y)=x-y$。$\sum_{i,j}c_ic_j(x_i-x_j)=0\ge0$ で 2 次形式の条件は満たす | $k(1,0)=1\ne-1=k(0,1)$ なので、内積 $\langle\varphi(x),\varphi(y)\rangle$ の形には書けない(cor-km-characterization が成り立たない) |
| Gram 行列の半正定値性 | $k(x,y)=\lvert x-y\rvert$、点 $0,1$、$y=(1,0)$、$\lambda=1$ | Gram 行列の固有値は $\pm1$ で $K+\lambda I$ は特異。2 次形式 $\alpha^{\mathsf T}K\alpha$ をノルムの 2 乗の代わりに使うと、$\alpha=t(1,-1)$ で目的関数は $1+2t\to-\infty$ になり、最小点がない |
| $\Omega$ が非減少 | 線形カーネルの $\mathbb{R}^2$、データ点 $x_1=(1,0)$、$L(a)=a^2$、$\Omega(r)=(r-1)^2$ | 最小値 $0$ は $w=(0,\pm1)$ でとられ、$V=\{(c,0)\}$ の上では $c^2+(\lvert c\rvert-1)^2\ge\frac12$。$V$ に最小点がない |
| $\lambda>0$ | Gauss カーネル $e^{-(s-t)^2/2}$、$\lambda=0$、データ点 $x_1=x_2=0$ で $y=(0,1)$ | 最小値 $\frac12$ は $f(x_1)=\frac12$ の全ての $f$ でとられ、最小点は 1 つに決まらない |
2 行目:$K=\begin{pmatrix}0&1\\1&0\end{pmatrix}$、$K\alpha=t(-1,1)$、$\lvert y-K\alpha\rvert^2=(1+t)^2+t^2$、$\alpha^{\mathsf T}K\alpha=-2t^2$。和は $1+2t$。3 行目:$f_w(x_1)=w_1$、$\|f_w\|=\lvert w\rvert$ なので $J=w_1^2+(\lvert w\rvert-1)^2\ge0$ で、等号は $w_1=0$、$\lvert w\rvert=1$。$V$ の上の最小は $c=\pm\frac12$ で $\frac12$。4 行目:$(f(x_1)-0)^2+(f(x_1)-1)^2$ は $f(x_1)=\frac12$ で最小。$\frac12k_0$ と $\frac12k_0+k_1-e^{-1/2}k_0$ はどちらも $0$ での値が $\frac12$ の異なる関数である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 「似ている度合い」を表す関数なら何でもカーネルに使える | Gram 行列の半正定値性を確かめる | 反例の表の 2 行目。$\tanh(x\cdot y-1)$ は $k(0,0)=\tanh(-1)<0$ で正定値カーネルでない |
| RKHS のノルムを $L^2$ ノルムと同じとみなす | ノルムは核で決まる(例:$\min(s,t)$ では $\int f'^2$) | ex-km-spaces |
| $\alpha=K^{-1}y$ と解く | $\lambda>0$ を足して $(K+\lambda I)^{-1}y$ | $K$ は特異になりうる(ex-km-poly) |
| 正則化の項を $\lambda\lvert\alpha\rvert^2$ とする | $\lambda\alpha^{\mathsf T}K\alpha=\lambda\Vert f\Vert^2$ | 前者は関数のノルムでなく、表現定理の形と合わない |
表現定理の $L$ をヒンジ損失にとったものが(定数項の扱いを除いて)サポートベクターマシン である。また、$f$ を平均 $0$、共分散 $k$ の Gauss過程 の実現とみなし、正則化の項を事前分布から来るものと読む解釈もある(HTF09 §5.8.1、p. 170)。主成分分析を特徴の空間で行うカーネル主成分分析もある。カーネルを Mercerの定理 で展開すると、$H_k$ は固有関数の重みつきの空間として書ける(HTF09 式 (5.45)–(5.47)、pp. 168–169)。
SSBD14 第 16 章(Theorem 16.1、Lemma 16.2)、HTF09 §5.8(pp. 167–174)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する