カーネル法とガウス過程 — NN以前の王者

深層学習が来る前、分類の王座に座っていたのはSVMとカーネル法だった。高次元へ持ち上げるコストをタダにする「カーネルトリック」から、関数そのものに確率を置くガウス過程、そして不確実性を武器にするベイズ最適化までを、前提知識ゼロで組み立てる。

Practical Bayesian Optimization of Machine Learning Algorithms

定規1本では切れない紙

テーブルの上に赤と青のおはじきが撒かれています。赤は真ん中にかたまり、青はその周りをドーナツのように囲んでいる。ここに定規を1本置いて赤と青をきれいに分けてください——と言われたら、どう置いても無理です。まっすぐな線では、囲まれた内側だけを切り出せません。

ところが、テーブルクロスの真ん中をつまんで持ち上げるとどうでしょう。赤いおはじきだけが高い位置に上がり、青は低いまま。ここで水平に板を差し込めば、たった1枚のまっすぐな板で赤と青が分かれます。

これがカーネル法の出発点です。曲がった境界が必要に見える問題も、データを高い次元に持ち上げれば、まっすぐな境界で切れるようになる。そして本当の主題は、この「持ち上げる」操作のコストをどうやってタダにするかにあります。

持ち上げ方を書き下すと、次元が爆発する

持ち上げる操作は、数学では特徴写像と呼ばれる関数 $\phi$ で表します。入力 $x$ を、より高い次元の別の空間へ移す関数です。

さきほどのドーナツなら、2次元の点 $(x_1, x_2)$ を $(x_1, x_2, x_1^2 + x_2^2)$ に写すだけで済みます。3つ目の成分は「原点からの距離の2乗」なので、中央のおはじきは低く、外周は高くなる。まさにテーブルクロスをつまみ上げた形です。

問題は、どんな曲がり方をしているか事前に分からないときです。安全策として「3次までの項を全部」と網羅的に持ち上げると、次元は組合せ的に増えます。$d$ 個の特徴量から3次の項をすべて作ると項の数は $\binom{d+2}{3}$ 個で、$d = 1000$ なら 1億6716万7000 個。1件のデータを変換するだけで1億6千万個の数値が並ぶことになり、それを何万件ぶんも保持するのは現実的ではありません。

トリック: 内積さえ分かればいい

ここで効いてくる観察が1つあります。分類や回帰のアルゴリズムの多くは、$\phi(x)$ そのものを必要としていないのです。必要なのは「$\phi(x)$ と $\phi(y)$ がどれだけ似ているか」、つまり2本のベクトルの内積だけです。

内積が「似ている度合い」の物差しになることは、Attention機構を1から理解するでも中心的な役割を果たしていました。向きが揃っているベクトル同士は内積が大きい——それが「似ている」の数学的な言い換えです。

そこで、内積そのものを1つの関数として定義してしまいます。

$k$ をカーネル関数と呼びます。左辺は $x$ と $y$ を受け取って1つの数値を返す関数、右辺は「両方を高次元に持ち上げてから内積を取った値」。この式が主張しているのは、両者が等しくなるような都合のいい $k$ を見つけられれば、$\phi$ を一度も計算しなくていいということです。

そんな関数は本当にあるのか。あります。たとえば $k(x, y) = (x \cdot y + 1)^3$ を展開すると、ちょうど「3次までのすべての項を並べたベクトル同士の内積」になります。左辺の計算量は $d$ 回の掛け算と足し算、それに3乗が1回だけ。右辺は1億6千万次元の内積。同じ値が、片方は一瞬で出る。これがカーネルトリックです。

どんな関数でもカーネルになれるわけではない

$k$ が「ある $\phi$ の内積」として書けるための条件は正定値性です。任意の有限個の点 $x_1, \dots, x_n$ を選んだとき、$K_{ij} = k(x_i, x_j)$ で作られる $n \times n$ の行列（グラム行列、またはカーネル行列）が半正定値であること。これを満たせば、対応する $\phi$ が——たとえ無限次元であっても——必ず存在することが保証されます（Mercerの定理）。

逆に言えば、思いつきで「これを類似度ということにしよう」と書いた関数を放り込むと、この条件が破れて最適化が発散したり、後で出てくるコレスキー分解が失敗したりします。カーネルを自作するときは、既存のカーネルの和・積・正の定数倍は再びカーネルになるという性質を組み合わせて作るのが安全です。

実務で使われるカーネルは、ほぼこの4つに絞られます。

• 線形 $k(x,y) = x \cdot y$ — 持ち上げなし。素の内積
• 多項式 $(x \cdot y + c)^p$ — $p$ 次までの交互作用を捉える
• RBF（ガウス） $\exp(-\|x-y\|^2 / 2\ell^2)$ — 対応する $\phi$ は無限次元
• Matérn — 関数の滑らかさを $\nu$ というパラメータで直接指定できる

RBFの直感は「距離が0なら1、遠ざかるほど急速に0へ落ちる類似度」です。$\ell$（length_scale）はどれくらい離れたら他人と見なすかの物差しで、小さいと境界がぐにゃぐにゃに、大きいとのっぺりします。scikit-learnのSVMでは同じものを $\gamma = 1/(2\ell^2)$ と逆数の形で指定するので、gamma を上げると柔軟に、length_scale を上げると滑らかに——向きが逆になる点に注意してください。