カーネル法

線形分離の限界と非線形特徴写像

機械学習における多くの問題は、データを線形な境界で分割できない場合がある。例えば、2次元平面上で同心円状に分布するデータは、直線では分類できない。このような非線形なパターンを扱うために、元のデータをより高次元の特徴空間へ写像し、その空間で線形分離を試みるアプローチがとられる。この写像を非線形特徴写像と呼び、写像後の空間で線形分類器を適用することで、元の空間では非線形だった境界を捉えられる。

カーネルトリックの原理

非線形特徴写像を明示的に計算することは、高次元空間での座標計算を伴い、計算コストが膨大になる。カーネルトリックは、写像後のベクトルの内積を、元の空間でのカーネル関数の値として直接計算する技法である。カーネル関数\(k(x, y) = \langle \phi(x), \phi(y) \rangle\)と定義され、\(\phi\)は特徴写像を表す。この計算により、明示的な写像なしに高次元空間での内積を効率的に得られる。カーネル関数が特定の条件（半正定値性）を満たせば、何らかの写像が存在することが保証される。

再生核ヒルベルト空間

カーネルトリックの理論的基盤として、再生核ヒルベルト空間（RKHS）がある。RKHSは、カーネル関数によって生成される関数空間であり、任意の点での関数値が内積として表現できる。具体的には、再生性\(f(x) = \langle f, k(x, \cdot) \rangle\)が成り立つ。RKHSの枠組みにより、カーネル法は関数近似や正則化理論と結びつき、最適化問題の解法に強力な理論的保証を与える。

線形カーネル

線形カーネルは\(k(x, y) = x^\top y\)と定義される。特徴写像は恒等写像に相当し、非線形性を導入しない。これは線形モデルと等価であり、カーネル法の特殊な場合として位置づけられる。計算コストが低く、データが線形分離可能な場合に有効である。

多項式カーネル

多項式カーネルは\(k(x, y) = (x^\top y + c)^d\)で与えられる。ここで\(d\)は次数、\(c\)はバイアス項である。このカーネルは、元の特徴の多項式組み合わせを含む特徴空間への写像に対応し、非線形な相互作用を捉える。次数が高いほど表現力が増すが、過学習のリスクも高まる。

動径基底関数カーネル

シグモイドカーネル

シグモイドカーネルは\(k(x, y) = \tanh(\alpha x^\top y + c)\)で与えられる。ニューラルネットワークの活性化関数に関連し、特定の条件下で半正定値性を満たす。多層パーセプトロンとの類似性から、歴史的に使われたが、現在ではRBFカーネルほど一般的ではない。

カスタムカーネルの設計

問題に応じて、既存のカーネルを組み合わせたり、ドメイン知識を反映したカーネルを設計できる。カーネル関数の和や積は再びカーネルとなる（閉包性）。また、半正定値性を満たす任意の関数はカーネルとして利用可能であり、Mercerの定理により保証される。

サポートベクターマシン

サポートベクターマシン（SVM）は、カーネル法の最も代表的な応用である。データを分離する超平面を、マージン最大化の原理で学習する。

マージン最大化とハードマージン

データが完全に線形分離可能な場合、ハードマージンSVMは、すべてのデータ点を正しく分類し、かつ超平面からの距離（マージン）を最大にする超平面を求める。この問題は凸二次計画問題に帰着され、最適解は境界上の数点（サポートベクター）のみで決まる。

ソフトマージンとスラック変数

実データではノイズや重複により完全分離が不可能な場合が多い。ソフトマージンSVMは、スラック変数を導入して誤分類を許容し、マージン最大化と誤差最小化のトレードオフを制御する。正則化パラメータ\(C\)により、誤分類のペナルティを調整する。

カーネル主成分分析

カーネル主成分分析（カーネルPCA）は、通常の主成分分析をカーネルトリックで非線形に拡張した手法である。高次元特徴空間での分散を最大化する方向を、カーネル行列の固有値問題として解く。これにより、元のデータでは線形でない部分空間への射影が可能となり、非線形次元削減や可視化に利用される。

カーネルリッジ回帰

カーネルk-meansクラスタリング

カーネルk-meansは、k-meansクラスタリングを非線形に拡張し、データをカーネル空間内でクラスタリングする。各点のクラスタ割り当てとクラスタ中心の更新を、カーネル関数の値のみで行える。これにより、元の空間で線形分離できないクラスタ構造を捉えられる。

その他の応用

ガウス過程

ガウス過程（GP）は、カーネル関数を共分散関数として用いる確率モデルである。回帰や分類に利用され、予測の不確実性を定量化できる。カーネル関数の選択がモデルの滑らかさや周期性を決定する。

カーネル密度推定

カーネル密度推定（KDE）は、各データ点にカーネル関数を重ね合わせて確率密度を推定するノンパラメトリック手法である。バンド幅の調整が重要であり、RBFカーネルがよく用いられる。

半正定値性とMercerの定理

カーネル関数が有効であるための必要十分条件は、任意の有限点集合に対するカーネル行列が半正定値であることである。Mercerの定理は、連続対称な半正定値カーネルが、ある特徴空間上の内積として表現できることを保証する。この理論により、カーネルトリックの正当性が支えられる。

表現定理

表現定理は、正則化付き経験損失最小化問題の最適解が、学習データのカーネル関数の線形結合として表現できることを示す。すなわち、最適な関数\(f\)は\(f(x)=\sum_i \alpha_i k(x_i, x)\)の形を持つ。この定理により、無限次元空間での最適化が有限次元の問題に帰着される。

汎化誤差解析

カーネル法の汎化性能は、学習理論の枠組みで解析される。正則化項の導入により過学習を抑制し、Rademacher複雑度やVC次元を用いた誤差の上界が導かれる。適切なカーネル選択と正則化パラメータの調整により、安定した予測性能が得られる。

カーネル行列の効率的計算

カーネル行列は\(n \times n\)の行列（\(n\)はデータ数）であり、全データ間のカーネル値を計算するには\(O(n^2 d)\)の時間がかかる（\(d\)は次元数）。高速化のために、並列計算や近似計算、メモリ効率の良いデータ構造が利用される。特に大規模データでは、カーネル行列全体の格納がメモリ制限となる。

大規模データへの拡張

Nyström近似法

Nyström法は、ランダムに選択した少数のデータ点（ランドマーク）を用いてカーネル行列を低ランク近似する手法である。カーネル行列\(K\)を\(K \approx C W^\dagger C^\top\)と近似し、計算コストを\(O(nm^2)\)に削減する（\(m\)はランドマーク数、\(m \ll n\)）。

ランダムフーリエ特徴

ランダムフーリエ特徴（RFF）は、Bochnerの定理に基づき、平行移動不変なカーネル（RBFなど）をランダムなフーリエ成分で明示的に近似する。特徴写像\(\phi(x) \in \mathbb{R}^D\)を\(D\)次元にランダムに構成し、内積が元のカーネル値に近づくようにする。これにより、カーネル法を線形モデルとして扱え、大規模データへのスケーラビリティが向上する。

ソフトウェアとライブラリ

カーネル法の実装は多くの機械学習ライブラリで提供される。Pythonではscikit-learnがSVM、カーネルPCA、カーネルリッジ回帰などをサポートする。LIBSVMやLIBLINEARはC++で書かれた高速なSVM実装である。R言語ではkernlabパッケージ、MATLABではStatistics and Machine Learning Toolboxに関数が含まれる。深層学習フレームワークでは、カーネル法を陽に実装する例は少ないが、ガウス過程ライブラリ（GPy、GPflowなど）が存在する。