カーネルトリック

さて，線形分離可能でない場合にはどうすればよいだろうか． そのためには $\mbox{\boldmath$x$}$ そのままではなく，いったん $\mbox{\boldmath$x$}$ を 高次元空間(特徴空間)に写像した $\mbox{\boldmath$\phi$}(\mbox{\boldmath$x$})\in\Re^h$ を パーセプトロンに入れてやればよい． 一般に特徴空間の次元 $h$ を $n$ 以上にすればサンプルは線形分離可能になる． そこで以下では入出力関数を $f_w(\mbox{\boldmath$x$})=\mbox{\boldmath$w$}\cdot\mbox{\boldmath$\phi$}(\mbox{\boldmath$x$})$ と定義する． 識別を誤ったサンプルに対して $y_i\mbox{\boldmath$\phi$}(\mbox{\boldmath$x$}_i)$ に比例して重みを修正するので， $\mbox{\boldmath$w$}={\bf0}$ を初期値とすれば，学習終了時には

$$\mbox{\boldmath$w$} = \sum_{i=1}^n \alpha_i \mbox{\boldmath$\phi$}(\mbox{\boldmath$x$}_i)$$ (1)

という形になっている． これをパーセプトロンの入出力関数に 代入してやると

$$y = \mbox{sgn}[\sum_{i=1}^n \alpha_i \mbox{\boldmath$\phi$}... ...math$x$}_i) \cdot\mbox{\boldmath$\phi$}(\mbox{\boldmath$x$})]$$

となる． さて，ここに出てくる二つの特徴空間の要素 $\mbox{\boldmath$\phi$}(\mbox{\boldmath$x$}_i)$ と $\mbox{\boldmath$\phi$}(\mbox{\boldmath$x$})$ の内積を $k(\mbox{\boldmath$x$}_i,\mbox{\boldmath$x$})$ と書く． これが本講演の主役である カーネル関数 である． 入出力関数はカーネル関数を使って

$$y = \mbox{sgn}[\sum_{i=1}^n \alpha_i k(\mbox{\boldmath$x$}_i,\mbox{\boldmath$x$})]$$

と書ける． ここまでは単なる書き換えであるが，逆に勝手に持ってきた関数 $k(\mbox{\boldmath$x$}_i,\mbox{\boldmath$x$})$ が，ある特徴空間の内積の形になっていないかという ことを考える． もしそれができれば，高次元への写像を計算してから さらにその内積を取るという厄介なことをしなくても，簡単に計算できる カーネル関数を代わりに使ってやればよいことになる．

実は $k$ は何でもよいというわけではない． どんな関数なら内積の形に書けるかは，以下の定理で与えられる．

定理 1 (Mercerの定理)   $\mbox{\boldmath$x$},\mbox{\boldmath$y$}\in \cal X$ の関数 $k$ が内積の形

$$k(\mbox{\boldmath$x$},\mbox{\boldmath$y$}) = \sum_{j=1}^\in... ...boldmath$x$}) \psi_j(\mbox{\boldmath$y$}), \quad \gamma_i\ge0$$ (2)

と書けるための必要十分条件は，$k$ が対称関数 ( $k(\mbox{\boldmath$x$},\mbox{\boldmath$y$})=k(\mbox{\boldmath$y$},\mbox{\boldmath$x$})$)であり，かつ，半正定値すなわち 任意の $f$ に対して

$$\int_{{\cal X}}\int_{{\cal X}} k(\mbox{\boldmath$x$},\mbox{... ...\boldmath$y$}) d\mbox{\boldmath$x$} d\mbox{\boldmath$y$}\ge 0$$

を満たすことである． ただし， $\psi_j(\mbox{\boldmath$x$})$ は $k(\mbox{\boldmath$x$},\mbox{\boldmath$y$})$ の固有関数で，

$$\int_{{\cal X}} k(\mbox{\boldmath$x$},\mbox{\boldmath$y$}) ... ...(\mbox{\boldmath$x$}) = \gamma_j \psi_j(\mbox{\boldmath$x$}).$$

ここで，入力空間を $\Re^d$ から任意の集合 $\cal X$ に一般化した． カーネルを用いた学習機械では，実数に限らず記号列でもグラフでも うまくカーネルが定義できれば何でもよいというのが一つの特長である．

さて，Mercer の定理を満たすカーネルをMercer カーネルと呼ぶ． Mercer カーネルについては後の節でも述べるが，ここでは代表的な カーネル関数を挙げておく． ニューラルネットとの関連が深いのは シグモイドカーネル $k(\mbox{\boldmath$x$},\mbox{\boldmath$y$})=1/(1+\exp(-\beta \mbox{\boldmath$x$}\cdot\mbox{\boldmath$y$}))$ や RBF カーネル $k(\mbox{\boldmath$x$},\mbox{\boldmath$y$})=\exp(-\beta\Vert\mbox{\boldmath$x$}-\mbox{\boldmath$y$}\Vert^2)$ である． また， 多項式カーネル $(\mbox{\boldmath$x$}\cdot\mbox{\boldmath$y$}+c)^p$ などもよく使われる．