6.9 カーネル法の計算量考察

「メモリベース」とはどういうことか

線形回帰を思い出してほしい。訓練データから係数$\hat{\beta}$ を求めれば、 その後は予測のたびに $\hat{\beta}$ を使うだけだ。訓練データはもう要らない。

ところがカーネル平滑化は違う。 新しい点 $x_0$ で予測したいとき、何が起こるかを見てみよう。

アニメーションが示す通り、中央のクエリ点 $x_0$ は 円周上のすべてのデータ点に向かって線を伸ばす。 これが、カーネル法の予測式が何をしているかの直感的なイメージだ。

数式の中に $x_1, x_2, \ldots, x_N$ が全部入っている。 つまり、$x_0$ で一回予測するだけで、訓練データのN個全部を見に行く必要がある。

これが「メモリベース（memory-based）」と呼ばれる理由だ。 モデルそのものがデータの記憶そのもの。線形回帰なら$\hat{\beta}$ という数個の数字に縮約されたのに、カーネル法では「データ全部」がモデルなのだ。

一見、これは贅沢な話だ。データの一切を捨てないのだから、表現力は高い。 しかし、贅沢には代償がある。1回の予測ごとに、N個のカーネル値を計算しないといけない。 N=10なら大したことはない。しかし N=100,000 なら？

1クエリで O(N)、M クエリで O(NM)

定量的に整理しよう。新しい点$x_0$ 一つの予測には何が必要か？

• N個のカーネル値 $K_\lambda(x_0, x_i)$ を計算
• それらを使って加重平均を取る

合計の演算回数は N に比例する。 これを O(N) フロップ と書く。 「O」は「オーダー」を意味し、N=1,000なら約1,000回、N=10,000なら約10,000回の演算ということだ。

ここで罠が待っている。

実用では、1点だけ予測したいということは少ない。 テスト点が $M$ 個あるなら：

訓練データもテスト集合も同じくらい大きい ($M \approx N$) と、$O(N^2)$ になる。 つまりデータを2倍にすると計算は4倍。10倍にすると100倍。これは厳しい。

一方、第5章で見た基底関数展開（線形回帰、スプライン、ウェーブレットなど）はどうか？ M個の基底 $\{h_1(x), \ldots, h_M(x)\}$ で予測するなら、 1点あたり O(M)。通常 $M \sim O(\log N)$ 程度に取れる。N が増えても M は緩やかにしか増えない。

2つの手法の構造的な違いをまとめると：

平滑化パラメータ選びは O(N²)

ここまでは「予測のコスト」だった。しかしカーネル法には、もう一つの「重さ」がある。

バンド幅 $\lambda$ をどう選ぶか。

第6章の前半で見たように、$\lambda$ は 「どこまで近い点を仲間とみなすか」を決める重要なパラメータ。 小さすぎるとガタガタ、大きすぎると平坦すぎる。ちょうどいい $\lambda$ を選ぶ必要がある。

標準的な方法は Leave-one-out 交差検証 だ：

• 1点を抜く → 残りN-1点で予測 → 抜いた点と比較
• これを全N点について行う
• $\lambda$ の候補ごとに繰り返す

「1点を抜いて残りで予測」自体が $O(N)$ 。 これを $N$ 回繰り返すから、1つの $\lambda$ あたり $O(N^2)$。

実用では N=10,000 なら、$10^8$ 回のオーダーの演算になる。 普通のラップトップで数分から数十分。訓練データだけでこれだ。

幸い、局所線形回帰には嬉しい性質がある。 Leave-one-out CV をループなしで一発計算する公式が存在するのだ。 線形平滑化器ではフィット結果を $\hat{y} = Sy$ と行列で書け、 「i番目を抜いてi番目を予測したときの誤差」が、「フィット残差 ÷ (1 − S_ii)」 という形でN個まとめて一発で出る （$S_{ii}$ はハット行列の対角要素）。N回のフィットを実際にやらなくていい。 これは第7章で詳しく扱う。

しかし、この近道が効くのは線形平滑化器に限る。 一般のカーネル法では$O(N^2)$ は避けがたい。 これが、データが大きくなるとカーネル法が苦しくなる理由だ。

三角形分割による近似 — M個の代表点を選ぶ

では、メモリベース手法は大きいデータには使えないのか？ いや、賢い近似がある。

実装の鍵は、「全ての点で律儀に予測しない」ことだ。

たとえば R の loess 関数や locfit パッケージで使われる手法は次のようなものだ：

1. データ空間を三角形分割（triangulation）で覆う — 入力空間を細かい三角形（高次元では単体）の網目に分ける
2. その頂点 M 個だけで、本物の局所回帰を実行する （合計コスト $O(NM)$、1回限り）
3. 任意のクエリ $x_0$ が来たら、$x_0$ を含む三角形の3頂点の値を線形補間（blending）する

ポイントは：

• 構築時：$O(NM)$ で済む （M個の代表点のみで本物の計算）
• クエリ時：$O(1)$ — 三角形を1つ特定して3頂点を線形補間するだけ。N にも M にも依存しない

$M$ をデータ空間の複雑さに見合うよう$M \sim O(\log N)$ や$O(\sqrt{N})$ に取れば、トータルでも実用的になる。

これは魔法ではない。真の関数が滑らかなら、細かい三角形の中ではほぼ線形だから、 頂点の値を補間しても誤差は小さい — そういう数学的な保証に支えられている。

カーネル平滑化の「精神」を保ちつつ、メモリと計算を N から M にスケールダウンする — 三角形分割はそのための技だ。

トレードオフをどう選ぶか

最後に、実装者の視点でまとめよう。

カーネル法（メモリベース）： 訓練は事実上ゼロコスト（データを保存するだけ）で柔軟性が高い反面、 予測のたびに $O(N)$、$\lambda$ 選択で $O(N^2)$、 メモリも $O(N)$。リアルタイム用途では破綻しやすい。

基底関数法：ちょうど鏡像。 訓練に $O(N + M^2)$ かかるが、 予測は $O(M)$ で十分速い。 代わりに基底の選択（ノット位置、ウェーブレット階層など）が必要。

実務での判断は、データの規模とユースケースのレイテンシ要件による：

そして最後に強調したいのは、両者は対立する技術ではなく、補完的だということだ。 多くの実装（loess など）は、メモリベースの考え方を採りつつ、 内部では基底関数的な近似で計算を加速している。

カーネル法を学ぶことは、ただの古典的手法を学ぶことではない。現代の機械学習が抱える「精度と計算量のトレードオフ」を最もシンプルな形で考える題材でもあるのだ。