カーネルトリック

内積だけで書けることへの着目

カーネルトリックは、サポートベクターマシンに関連する重要な革新の1つとして知られています。イアン・グッドフェロー (Ian Goodfellow)、ヨシュア・ベンジオ (Yoshua Bengio)、アーロン・クールヴィル (Aaron Courville) による教科書「Deep Learning」(2016年) の第5章は、カーネルトリックの出発点を「多くの機械学習アルゴリズムが、例どうしの内積の形だけで書ける」という点に置いています。

たとえばサポートベクターマシンが使う線形関数 w・x + b は、次のように書き直せます。

f(x) = b + Σ α_i (x・x^(i))

ここで x^(i) は i 番目の訓練データの例、α_i は例ごとの係数です。重み w を直接持つかわりに、新しい入力 x と各訓練例 x^(i) との内積に係数をかけて足し合わせる形になっています。

内積をカーネル関数に置き換える

次に、この式の x を入力を別の空間へ写す特徴関数 φ(x) の出力に置き換えます。すると内積は φ(x)・φ(x^(i)) になります。この内積をひとまとめにして、次の関数で表します。

k(x, x^(i)) = φ(x)・φ(x^(i))

この k がカーネルと呼ばれる関数です。置き換えた後の予測は次の形になります。

f(x) = b + Σ α_i k(x, x^(i))

この関数は x について見ると非線形です。一方で、φ(x) と f(x) の関係、そして係数 α と f(x) の関係は線形のままです。教科書は、カーネルに基づくこの関数が「すべての入力に φ(x) を適用してデータを前処理し、変換後の空間で線形モデルを学習すること」と完全に等価であると述べています。つまり、元の空間では曲がった境界を引くモデルであっても、変換後の空間では直線的なモデルとして扱えるということです。

この置き換えが強力な2つの理由

教科書はカーネルトリックが強力である理由として、次の2点を挙げています。

1つ目は最適化のしやすさです。特徴関数 φ を固定し、係数 α だけを最適化する形になるため、凸最適化の手法が使えます。凸最適化では、効率よく学習でき、収束も保証されます。非線形な関数を表せるのに、学習そのものは扱いやすい問題のまま保たれる点が重要です。

2つ目は計算の効率です。カーネル関数 k は、2つの φ(x) のベクトルを実際に組み立ててから内積を取るよりも、はるかに少ない計算で求められる実装を持つことが多いとされます。φ(x) が無限次元のベクトルになる場合でさえ、k(x, x') は x について扱いやすい非線形関数として計算できることが多いのです。変換後の空間を一度も具体的に書き出さずに、その空間での内積だけを直接求められることが、この手法が「トリック」と呼ばれるゆえんです。

無限次元の内積を1つの式で求める例

教科書は、無限次元の特徴空間でも内積が簡単に求まることを次の例で示しています。

0 以上の整数 x に対して、特徴写像 φ(x) を「先頭に x 個の 1 が並び、その後に無限個の 0 が続くベクトル」と定めます。このベクトルは無限の長さを持つため、そのまま組み立てて内積を計算することはできません。しかし2つのベクトルの内積は、両方で 1 が重なる個数に等しいので、次のカーネル関数で求まります。

k(x, x^(i)) = min(x, x^(i))

たとえば x = 3、x^(i) = 5 なら、φ(3) = (1, 1, 1, 0, 0, …)、φ(5) = (1, 1, 1, 1, 1, 0, …) で、1 が重なるのは先頭の3か所なので内積は 3 です。これは min(3, 5) = 3 と一致します。無限次元のベクトルを扱わずに、小さい方の値を選ぶだけで同じ答えが得られます。

ガウスカーネルとテンプレートマッチング

実際に最もよく使われるのは、ガウスカーネルです。RBFカーネル (動径基底関数カーネル) とも呼ばれ、次の式で表されます。

k(u, v) = N(u - v; 0, σ²I)

ここで N は正規分布の密度関数、σ² は広がりを決める値、I は単位行列です。このカーネルは、無限次元の空間での内積に対応しています。

教科書は、ガウスカーネルを u から v へのユークリッド距離に基づくテンプレートマッチングの一種とみなせると説明しています。訓練データの例とその正解ラベルは、そのラベルのクラスを代表するテンプレートになります。テスト点が、ある訓練例にユークリッド距離で近いとき、ガウスカーネルは大きな値を返します。これは、テスト点がその訓練例のテンプレートに似ていることを示しています。予測 f(x) = b + Σ α_i k(x, x^(i)) は、各テンプレートとの似ている度合いに係数をかけて足し合わせたものとして読むことができます。

押さえておきたい要点

• カーネルトリックが使えるのは、アルゴリズムが例どうしの内積だけで書ける場合です。
• 内積 φ(x)・φ(x^(i)) をカーネル関数 k(x, x^(i)) に置き換えると、特徴空間への変換を明示的に計算せずに済みます。
• 得られるモデルは入力 x について非線形ですが、変換後の空間で線形モデルを学習することと等価です。
• 係数 α だけを最適化するため凸最適化が使え、カーネル関数の計算も効率的です。
• 代表的なカーネルであるガウスカーネル (RBFカーネル) は、無限次元の空間での内積に対応します。