カーネルトリックとは

カーネルトリックは、サポートベクターマシン（SVM）で曲がった境界を作るときに使われる計算の工夫です。

高次元に移すと分けられる

平面上で、原点の近くにAクラスのデータが集まり、そのまわりをBクラスのデータが輪のように囲んでいる場合を考えます。どんな直線を引いても、この2つは分けられません。ここで各点に、原点からの距離の2乗x1^2 + x2^2を3つ目の座標として加え、3次元の空間に移します。するとAは低い位置に、Bは高い位置に並ぶので、水平な平面1枚で分けられます。このように、元の空間では線形分離できないデータも、高次元の空間に写像すると線形に分けられる場合があります。

写像を計算せずに済ませる

ただし、次元を増やすほど計算量は大きくなります。そこで注目するのが、SVMの学習と予測の計算は、写像後のデータどうしの内積の値だけで書けるという性質です。写像をφ(x)とすると、必要なのはφ(x)・φ(x')の値だけです。この値を元の空間のデータから直接計算できる関数k(x, x') = φ(x)・φ(x')があれば、φ(x)そのものを求める必要はありません。この関数をカーネル関数と呼び、内積をカーネル関数に置き換えることをカーネルトリックといいます。

代表的なカーネル関数には、多項式カーネルやガウスカーネル（RBFカーネル）があります。ガウスカーネルk(x, x') = exp(-γ‖x - x'‖^2)は無限次元の空間での内積に対応しますが、計算は元の空間での距離だけで済みます。

位置づけと用語の注意

SVMにカーネルトリックを取り入れたのは、1992年のボーザー、ギヨン、ヴァプニクの論文です。考え方はSVM以外にも広がり、カーネル主成分分析などで使われています。

なお、CNNの畳み込み層でいう「カーネル」は、画像に当てる小さなフィルタの重みのことで、別の意味です。

覚え方

「移した先の内積を、移さずに計算する」と覚えます。