ホーム » 機械学習 » Kernel Trickについて

Kernel Trickについて

こんにちは。
今回はカーネルについてです。カーネルといえば次元削減がもっともポピュラーな関連ワードなんじゃないでしょうか。なぜカーネルなのか、どうやって働いているのか、について少し考察してみます。
そもそもカーネルとはなんなのか?という問いに対しては
ある空間(主に高次元)での内積を計算する手法

が答えになります。では次に来るのはなぜ内積を計算したいのか?という問いです。
https://commons.wikimedia.org/wiki/File:Kernel_yontemi_ile_veriyi_daha_fazla_dimensiyonlu_uzaya_tasima_islemi.png
データを扱う際、別に高次元だけでなくあらゆる空間で内積をとるという行為はあちこちで必要となります。これについてはSVMの実装とか色々勉強してみるとわかります。つまり、先走ると、データを別次元で扱いたいさいはその内積さえわかればいいことが多いんです。

内積だけでいいのか??

と絶対思いますよね。上の図でいえば写像\phiを知る必要なしに、右側のFeature Spaceで左側のInput Spaceのデータを扱うことができるなんてあり得るのでしょうか?それがあり得るんです。 みていきましょう
写像\phi:\mathcal{R}^n \rightarrow \mathcal{R}^mを画像左側から右側へのものとします。すると、特徴空間でのxyの内積は\phi(x)^T\phi(y)となります。つまり、カーネルは次のようになります。

    \[K(x,y) = \phi(x)^T\phi(y)\]

これだけではわからないので具体例を見ましょう。すればわかります。

    \[K(x,y) = (x^T y)^2\]

上のカーネル関数を考えます。これを分解していきましょう。つまり

    \[K(x,y) = \left( \sum_{i=1}^{n}x_i y_i \right)\left( \sum_{j=1}^{n}x_j y_j \right)\]


    \[= \sum_{i=1}^{n}\sum_{j=1}^{n} x_i x_j y_i y_j\]


    \[= \sum_{i,j=1}^{n} (x_ix_j)(z_i y_j)\]


とします。もうわかりましたでしょうか。例えばn=3とすると

    \[ \bm{\phi(x)} = \left[ \begin{array}{c} x_1x_1  \ x_1x_2  \ x_1x_3  \ x_2x_1  \ x_2x_2  \ x_2x_3  \ x_3x_1  \ x_3x_2  \ x_3x_3   \end{array} \right]^T\]

ということになります。つまり、この例だと写像\phiは上のようなものであり、特徴空間は9次元だったということです。ちなみにこのカーネル関数を線形カーネルと言います。もう一例みましょう。

    \[K(x,y) = (x^T z + c)^2\]

同様に分解すると

    \[= \sum_{i,j=1}^{n} (x_ix_j)(z_i y_j) + \sum_{i,j=1}^{n} (\sqrt{2c}x_i)(\sqrt{2c}y_i) + c^2\]

n=3のとき

    \[ \bm{\phi(x)} = \left[ \begin{array}{c} x_1x_1  \ x_1x_2  \ x_1x_3  \ x_2x_1  \  x_2x_2  \ x_2x_3  \ x_3x_1  \ x_3x_2  \ x_3x_3  \ \sqrt{2c}x_1  \ \sqrt{2c}x_2  \ \sqrt{2c}x_3  \ c \end{array} \right]^T\]

見ての通り13次元の特徴空間であることがわかります。一般化するとK(x,y) = (x^Tz + c)^d\tbinom{n+d}{d}次元でのカーネルになります。
ここまででカーネルがでたらめではなく、ちゃんと高次元での内積を計算してくれていることがわかりました。では次の疑問としてどういったカーネル関数ならいいのか?が現れます。実はここが非常に難しいのです。

Mercer’s Theorem

Reproducing Kernel Hilbert Space (RKHS)

これらがキーワードになります。特に上の定理について
  • symmetry: K(x,y) = K(y,x)
  • Positive semi-definiteness
を満たす必要があります。
カーネルが何か、そして何をしているのかわかったかと思います。面白いカーネル関数がわかれば僕に連絡ください。笑

Reference


コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です