Pack only the essentials: Adaptive dictionary learning for kernel ridge regression

論文要約：SQUEAK — カーネルリッジ回帰のための適応的辞書学習

1. 背景と問題設定 (Problem)

カーネルリッジ回帰（KRR）は強力な学習手法ですが、サンプル数 $n$ に対してカーネル行列 $K_n$ の保持に $O(n^2)$ のメモリ、計算に $O(n^3)$ の時間を要するため、大規模データセットへの適用が困難です。

これを解決するために、行列の一部（$m$ 個）の列のみを選択して低ランク近似を行うNyström近似が広く用いられています。近似の精度は「どの列を選択するか」に依存しますが、以下の課題があります：

• 一様サンプリング: データに相関が強い（コヒーレンスが高い）場合、非常に多くの列をサンプリングしないと精度が保てない。
• リッジ・レバレッジ・スコア (RLS) サンプリング: 各点の重要度（RLS）に基づいたサンプリングは精度が高いが、RLS自体の計算コストがKRRの解法と同等であり、実用的ではない。
• 既存の逐次近似法: 既存の逐次アルゴリズム（INK-ESTIMATE等）は、カーネル行列の最大固有値 $\lambda_{\max}$ に依存する項が含まれており、最悪の場合、メモリ効率の利点が失われる。

2. 提案手法 (Methodology: SQUEAK)

本論文では、新しい逐次アルゴリズム SQUEAK を提案しています。SQUEAKは、データの到着に合わせて辞書（近似に使用する列の集合）を動的に更新・構築します。

主なメカニズム:

1. 改良されたRLS推定器:
   行列全体を保持することなく、現在保持している辞書内の列のみを用いて、各点のRLSの $\alpha$-近似値を効率的に計算する数式（Eq. 5）を導入しました。
2. 逐次的なサンプリング・スキーム:
   新しいデータが到着するたびに、以下の2段階のプロセスを行います。
   • SHRINK (縮小): 既存の列の重要度（推定RLS）が低下した場合、二項分布を用いてその列の保持数を確率的に減らし、辞書から削除します。
   • EXPAND (拡張): 新しいデータ点の重要度に基づき、新しい列を辞書に適切な数（$0$から$q$ 個）追加します。
3. 正規化の排除:
   従来手法のように「有効次元数（effective dimension）」の推定値で確率を正規化する必要がなく、推定されたRLSを直接サンプリング確率として利用できるため、アルゴリズムが簡略化されています。

3. 主な貢献 (Key Contributions)

• 効率的なRLS推定: 辞書内のサブ行列のみを用いて、計算コストを抑えつつ精度の高いRLS近似を実現しました。
• 適応的なメモリ管理: データの有効次元数（effective dimension）の増大に合わせて、辞書のサイズを自動的に調整します。
• 単一パスでの動作: データセット全体を構築することなく、ストリーミング形式（単一パス）でRLSサンプリングを実行できる初のアルゴリズムです。

4. 結果と理論的保証 (Results)

定理1および表1に基づき、以下の特性が証明されています：

• 精度: 高い確率で、構築された近似行列 $\hat{K}_n$ は $\gamma$-近似となり、回帰リスクは厳密な解の理論的限界に近い範囲に抑えられます。
• 空間複雑度: 保持する列の数は $O(\text{deff}(\gamma)_n \log n)$ であり、これは**「事前に正確なRLSを知っている理想的なケース」と定数倍の差しかない**極めて効率的なものです。
• 頑健性: 既存手法（Calandriello et al.）が抱えていた最大固有値 $\lambda_{\max}$ への依存を排除し、最悪のケースでも効率的なメモリ使用量を維持します。

5. 意義 (Significance)

SQUEAKは、大規模かつストリーミング形式のデータに対して、**「メモリ消費を最小限に抑えつつ、理論的に最適なサンプリング精度を維持する」**という、実用上の極めて困難な課題に対する強力な解決策を提示しました。この手法は、カーネルPCAや分散環境における分散学習など、他のカーネルベースの手法への応用も期待されます。