1 基本原理と背景
カーネル近似は、カーネル法における計算量の爆発的増大を抑制するために開発された一連の手法である。カーネル法は再生核ヒルベルト空間（RKHS）上で内積を暗黙的に計算するが、データ数nに対してO(n³)の計算量が必要となる。この課題を解決するため、カーネル行列や特徴写像を低ランク近似やランダム写像で置き換えることで、大規模データへの適用を可能にする。
1.1 カーネル法の計算的課題
カーネル法では、n個の訓練データに対するカーネル行列K（サイズn×n）の計算と逆行列演算が中心的役割を担う。この行列の要素はすべてのデータペア間のカーネル関数値であり、その計算にはO(n²)の時間とメモリが必要となる。さらに、ガウス過程回帰やサポートベクトルマシンの学習ではO(n³)の時間計算量が生じる。nが10万を超える大規模データセットでは、これらのコストが現実的ではなくなる。また、カーネル行列は一般に密行列であるため、メモリ消費も問題となる。
1.2 近似の必要性と応用領域
近似手法の導入により、O(n³)からO(n²)以下、さらにはO(n)に近い計算量へと削減できる。これにより、画像認識、自然言語処理、バイオインフォマティクスなど、数百万サンプルを扱うアプリケーションでもカーネル法の恩恵が得られるようになった。特に、リアルタイム処理やストリーミングデータの解析において、近似は必須の技術である。
2 主な近似手法
主要なアプローチとして、Nyström法とランダムフーリエ特徴が広く利用されている。その他にも、ランダムビット特徴やハッシュベースの方法が存在する。
2.1 Nyström法
Nyström法は、カーネル行列を少数のランダムに選ばれた列（または行）から復元する低ランク近似手法である。元のカーネル行列Kを、サンプリングされた部分行列を用いて近似する。
2.1.1 ランダムサンプリングによる低ランク近似
まず、m個のインデックスを一様ランダムに選択する（m << n）。選択されたインデックスに対応するカーネル行列の部分行列K_{mm}と、全データとサンプル間のカーネル行列K_{nm}を用いて、近似カーネル行列を \(\tilde{K} = K_{nm} K_{mm}^{-1} K_{nm}^T\) と計算する。この近似のランクは高々mであり、計算量はO(n m²)と大幅に削減される。
2.1.2 決定論的サンプリング戦略
ランダムサンプリングの代わりに、k-meansクラスタリングやレバレッジスコアに基づく戦略を用いることで、近似精度が向上する場合がある。決定論的手法は、カーネル行列の特異値分解に基づいて重要な列を選択する。ただし、ランダムサンプリングに比べ前処理コストが増加するため、トレードオフが存在する。
2.2 ランダムフーリエ特徴
ランダムフーリエ特徴（RFF）は、Bochnerの定理を利用して、並進不変カーネルを明示的な有限次元特徴写像で近似する手法である。
2.2.1 Bochnerの定理と余弦写像
並進不変カーネル\(k(x,y)=k(x-y)\)が正定値であるとき、そのフーリエ変換は確率密度関数となる。Bochnerの定理により、\(k(x-y)=\int p(\omega) e^{i\omega^T(x-y)} d\omega\)と表現できる。これをサンプリングにより近似し、実数部のみを用いると、\(z(x)=\sqrt{2/D}[\cos(\omega_1^T x + b_1),...,\cos(\omega_D^T x + b_D)]\)というD次元の特徴写像が得られる。ここで\(\omega_i\)はp(ω)から、b_iは一様分布[0,2π]からサンプリングする。
2.2.2 多様なカーネルへの拡張
ラプラスカーネル、コーシーカーネルなど、他の並進不変カーネルにも同様の手法が適用可能である。また、マターナカーネルなどへの拡張も研究されている。非定常カーネルに対しては、別の近似手法が必要となる。
2.3 その他の手法
2.3.1 ランダムビット特徴
ランダムビット特徴は、バイナリデータやハッシングに基づく超高速な近似を提供する。入力ベクトルをランダムな超平面で分割し、その符号を特徴として用いる。これにより、カーネル近似がビット演算で実行可能となり、極めて低レイテンシが要求される場面で有用である。
2.3.2 ハッシュベース近似
特徴ベクトルをハッシュ関数で離散化し、カウントやテーブルルックアップでカーネル値を近似する手法である。Locality-Sensitive Hashing（LSH）が代表的で、近傍探索と組み合わせることで、高次元データに対する効率的な近似が可能となる。
3 理論的保証と誤差解析
近似手法の品質は、誤差上界や集中不等式によって保証される。計算量とのトレードオフを理論的に理解することが重要である。
3.1 近似誤差の上界
3.1.1 Nyström法の誤差評価
| Nyström法の近似誤差は、カーネル行列のランクmによる切り捨て特異値分解の誤差に関連する。ランダムサンプリングの場合、\(\|K-\tilde{K}\|_2\)は高確率で\(O(n/\sqrt{m})\)のオーダーに抑えられることが知られている。決定論的サンプリングではより良い保証が得られる場合がある。 |
|---|
3.1.2 ランダムフーリエ特徴の集中不等式
| RFFの近似誤差は、特徴次元Dについて\(\|k(x,y)-\langle z(x),z(y)\rangle\|_\infty\)が\(O(1/\sqrt{D})\)で抑えられる。より強い保証として、一様収束性や行列のスペクトルノルムに関する集中不等式が導出されている。具体的には、\(D\)を\(O(\epsilon^{-2}\log n)\)と取れば、近似カーネル行列と真のカーネル行列の差がスペクトルノルムで\(\epsilon\)以下になることが示されている。 |
|---|
3.2 計算複雑性とメモリ使用量
3.2.1 時間計算量の比較
真のカーネル法の学習はO(n³)、Nyström法はO(n m² + m³)、RFFはO(n D)の時間がかかる。ここでmやDは数百から数千のオーダーであり、nが大きいほど近似手法の効果が顕著になる。
3.2.2 空間計算量の最適化
真のカーネル行列はO(n²)のメモリを必要とするが、Nyström法ではO(n m)、RFFではO(n D)に削減される。さらに、ストリーミングやオンライン学習と組み合わせることで、メモリ使用量をO(1)にすることも可能である。
4 実装とパラメータ選択
近似手法の性能は、特徴次元やサンプル数などのパラメータに依存する。適切な選択方法が実用上重要である。
4.1 特徴次元の決定方法
4.1.1 クロスバリデーションを用いた調整
最も実用的な方法は、ホールドアウト検証やk分割交差検証により、特徴次元Dやサンプリング数mを選択することである。計算コストが比較的小さいため、グリッドサーチやベイズ最適化が利用される。
4.1.2 理論的ガイドライン
理論的保証から、Dは\(O(\epsilon^{-2}\log n)\)が推奨される。しかし、実際のデータではより小さな次元で十分な場合が多い。経験則として、Dをデータ数nの平方根程度に設定することもある。
4.2 大規模データへのスケーリング
4.2.1 ストリーミング処理との統合
RFFは独立なランダムサンプリングにより逐次的に特徴を増やせるため、ストリーミング環境に適している。Nyström法もオンラインクラスタリングと組み合わせることで、データ到着に応じて近似を更新できる。
4.2.2 分散並列計算フレームワーク
MapReduceやSparkなどのフレームワーク上で、RFFやNyström法を並列実行することが可能である。各ノードが独立に特徴写像を計算し、最後に集約することで、テラバイト規模のデータも処理できる。
5 応用例
5.1 大規模画像分類
ImageNetのような数百万枚の画像データセットでは、通常のカーネルSVMは非現実的である。RFFを用いて線形SVMに変換することで、高精度かつ高速な分類が実現される。畳み込みニューラルネットワークの特徴量と組み合わせることも多い。
5.2 時系列予測
ガウス過程回帰は時系列予測に有効だが、計算量が問題となる。Nyström法により、入力点を間引くことで、長期間の系列でも実用的な計算時間で予測が可能となる。金融データや気象データでの活用例がある。
5.3 異常検知
カーネル主成分分析（kPCA）の近似として、RFFを用いた異常検知が行われる。高次元の正常パターンを学習し、異常なサンプルを効率的に検出する。ネットワーク侵入検知や製造品質管理に応用されている。
6 発展的トピック
6.1 深層学習との融合
カーネル近似はニューラルネットワークの活性化関数としても解釈できる。特に、RFFはランダム特徴量と深層ネットワークの中間層を結びつける研究が進んでいる。カーネルから導かれるカーネルリッジ回帰と深層学習のハイブリッドモデルも提案されている。
6.2 適応的カーネル近似
データ分布に応じて近似のパラメータを動的に調整する手法である。例えば、重要度サンプリングを用いて特徴写像をデータに適合させることで、固定ランダム写像よりも少ない次元で高い精度を達成する。適応的Nyström法も同様のアイデアに基づく。
6.3 非定常カーネルへの拡張
Bochnerの定理が適用できない非定常カーネル（例えば多項式カーネルや周期カーネル）に対しては、異なる近似戦略が必要となる。テンソル積構造やランダムフェルミオン特徴など、新たな理論的枠組みが研究されている。