カーネルトリック

ソフトマージン法を用いることで、線形分離可能でない場合に対しても線形しき い素子のパラメータを求めることができるようになる。しかし、ソフトマージン 法を用いたとしても、本質的に非線形で複雑な識別課題に対しては、必ずしも良 い性能の識別器を構成できるとは限らない。本質的に非線形な問題に対応するた めの方法として、特徴ベクトルを非線形変換して、その空間で線形の識別を行う 「カーネルトリック」と呼ばれている方法が知られている。この方法を用いるこ とでサポートベクターマシンの性能が飛躍的に向上した。それがサポートベクター マシンを有名にした大きな要因であると考えられる。

一般に、線形分離可能性はサンプル数が大きくなればなるほど難しくなり、逆に、 特徴空間ベクトルの次元が大きくなるほど易しくなる。例えば、特徴ベクトルの 次元が訓練サンプルの数よりも大きいなら、どんなラベル付けに対しても線形分 離可能である。しかし、高次元への写像を行うと、次元の増加に伴い汎化能力が 落ちてしまう。また、難しい問題を線形分離可能にするためには、訓練サンプル と同程度の大きな次元に写像しなければならないので、結果的に膨大な計算量が 必要となってしまう。

今、元の特徴ベクトル $\mbox{\boldmath$x$}$を非線形の写像 $\phi(\mbox{\boldmath$x$})$によって変換し、 その空間で線形識別を行うことを考えてみよう。例えば、写像$\phi$として、入 力特徴を２次の多項式に変換する写像を用いるとすると、写像した先で線形識別 を行うことは、もとの空間で２次の識別関数を構成することに対応する。一般に は、こうした非線形の写像によって変換した特徴空間の次元は非常に大きくなり がちである。しかし、サポートベクターマシンの場合には、幸いにも、目的関数 $L_{D}$や識別関数が入力パターンの内積のみに依存した形になっており、内積 が計算できれば最適な識別関数を構成することが可能である。つまり、もし非線 形に写像した空間での二つの要素 $\phi(\mbox{\boldmath$x$}_1)$と $\phi(\mbox{\boldmath$x$}_2)$の内積が

$$\phi(\mbox{\boldmath$x$}_1)^T \phi(\mbox{\boldmath$x$}_2) = K(\mbox{\boldmath$x$}_1, \mbox{\boldmath$x$}_2)$$ (24)

のように、入力特徴 $\mbox{\boldmath$x$}_1$と $\mbox{\boldmath$x$}_2$のみから計算できるなら、非線形写 像によって変換された特徴空間での特徴 $\phi(\mbox{\boldmath$x$}_1)$や $\phi(\mbox{\boldmath$x$}_2)$を 陽に計算する代わりに、 $K(\mbox{\boldmath$x$}_1, \mbox{\boldmath$x$}_2)$から最適な非線形写像を構成 できる。ここで、このような$K$のことをカーネルと呼んでいる。このように高 次元に写像しながら、実際には写像された空間での特徴の計算を避けて、カーネ ルの計算のみで最適な識別関数を構成するテクニックのことを「カーネルトリッ ク」と呼んでいる。

実用的には、$K$は計算が容易なものが望ましい。例えば、多項式カーネル

$$K(\mbox{\boldmath$x$}_1,\mbox{\boldmath$x$}_2) = (1 + \mbox{\boldmath$x$}_1^T \mbox{\boldmath$x$}_2)^{p}$$ (25)

Gaussカーネル

$$K(\mbox{\boldmath$x$}_1,\mbox{\boldmath$x$}_2) = \exp \left... ...$}_1 - \mbox{\boldmath$x$}_2 \vert\vert^2}{2 \sigma^2} \right)$$ (26)

シグモイドカーネル

$$K(\mbox{\boldmath$x$}_1,\mbox{\boldmath$x$}_2) = \mbox{tanh... ...ft(a \mbox{\boldmath$x$}_1^T \mbox{\boldmath$x$}_2 - b \right)$$ (27)

などが使われている。

式(10)や式(23)の目的関数 $L_{D}$は、

$$L_{D}(\mbox{\boldmath$\alpha$}) = \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i,j=1}^{N} \alpha_i \alpha_j t_i t_j \phi(\mbox{\boldmath$x$}_i)^T \phi(\mbox{\boldmath$x$}_j)$$

$$= \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i,j=1}^{N} \alpha_i \alpha_j t_i t_j K(\mbox{\boldmath$x$}_i, \mbox{\boldmath$x$}_j)$$ (28)

のように内積をカーネルで置き換えた形に書ける。また、式(13) から最適な識別関数は、

$$y = \mbox{sign} (\mbox{\boldmath$w$}^{*T} \phi(\mbox{\boldmath$x$}) - h^{*})$$

$$= \mbox{sign}(\sum_{i \in S} \alpha^{*}_i t_i \phi(\mbox{\boldmath$x$}_i)^T \phi(\mbox{\boldmath$x$}) - h^{*})$$

$$= \mbox{sign}(\sum_{i \in S} \alpha^{*}_i t_i K(\mbox{\boldmath$x$}_i, \mbox{\boldmath$x$}) - h^{*})$$ (29)

のようにサポートベクターマシンの内積をカーネルで置き換えた形に書ける。こ こで、この式にシグモイドカーネルを代入すると、いわゆる３層の多層パーセプ トロンと同じ構造となる。また、Gaussカーネルを代入すると、Radial Basis Function (RBF)ネットワークと同じ構造になり、構造的には従来のニューラルネッ トワークと同じになる。しかし、カーネルトリックを用いて非線形に拡張したサ ポートベクターマシンでは、中間層から出力層への結合荷重のみが学習により決 定され、前段の入力層から中間層への結合荷重は固定で、訓練データから機械的 に求められる。また、中間層のユニット数が非常に大きく、訓練サンプル数と同 じになる。つまり、カーネルトリックを用いて非線形に拡張したサポートベクター マシンでは、入力層から出力層への結合荷重を適応的に学習により求めない代わ りにあらかじめ中間層に非常に多くのユニットを用意することで複雑な非線形写 像を構成しようとする。

図 4: サポートベクターマシンの構造