2.5 高次元における局所的手法 — 次元の呪い

k-最近傍法は「近くのデータから学ぶ」というシンプルで強力なアイデアだった。 でも、変数（特徴量）が増えると、この「近さ」という概念が崩壊していく。 これが「次元の呪い（Curse of Dimensionality）」だ。 なぜ高次元空間では直感が通用しないのか、そして呪いをどう回避するかを見ていこう。

変数が増えると何が起きる？

前のセクションで、k-最近傍法（k-NN）を学んだ。 新しいデータ点の周囲にある訓練データを見て、そこから予測する手法だ。

直感的には強力に見える。データが十分あれば、どんな複雑な関数でも近似できそうだ。 入力の近くのデータを集めて平均すれば、理論的に最適な予測 —— つまり「その入力が与えられたときの出力の平均（条件付き期待値）」 —— に近づけるはずだから。

では、こんな状況を考えてみよう。

入力変数が1つのとき（1次元）、訓練データが100点あればそこそこ「近い」点が見つかる。 入力変数が10個のとき（10次元）、同じ100点が空間を密に埋められるだろうか？

1D・2D・3Dで同じ点数が疎になっていく様子
同じ25点でも、次元が上がるにつれて点と点の間が広くなっていく

答えはNOだ。アニメーションを見てほしい。 1次元の数直線上では点が密に並んでいる。 2次元の正方形の中では、同じ点数でも間隔が広くなる。 3次元の立方体になると、点はさらに疎らになる。

そして、この現象は10次元、100次元になると爆発的に悪化する。 これが「次元の呪い（Curse of Dimensionality）」と呼ばれる問題の本質だ。 このセクションでは、なぜ高次元空間では直感が通用しないのかを、具体的な数値で見ていこう。

ハイパーキューブの呪い — 「近所」はどれだけ大きい？

具体的に考えよう。

p次元の単位超立方体（全辺の長さが1の箱）を考える。 訓練データは均一に分布しているとする。

全データの中からr割（例えば1%）に相当する点を集めて「近所」とするには、 その近所の超立方体の辺の長さはどれくらい必要か？

$$e_p(r) = r^{1/p}$$

ここで $e_p(r)$ は p次元空間でr割をカバーするのに必要な辺の長さだ。

超立方体の辺の長さが次元に応じて急増するグラフ
青: r=1%をカバーする辺の長さ、黄: r=10%をカバーする辺の長さ。どちらも次元とともに急速に1に近づく

グラフを見ると一目瞭然だ。次元が増えるにつれ、辺の長さが急速に1（全体）に近づいていく。

p=10、r=0.01（1%）のとき：

$$e_{10}(0.01) = 0.01^{1/10} \approx 0.63$$

各軸の63%もの範囲をカバーしなければならない！

p=10、r=0.1（10%）のとき：

$$e_{10}(0.1) = 0.1^{1/10} \approx 0.80$$

各軸の80%もの範囲だ。

これはもはや「局所的」ではない。「近所」が実際には空間全体にまたがってしまっている。

比較しよう。1次元なら10%をカバーするのに必要な辺の長さは0.1（10%）だけ。 10次元なら同じ10%のデータをカバーするのに80%の範囲が必要になる。 k-NNが「局所的な学習」のはずなのに、高次元では局所的な学習が不可能になってしまうのだ。

端に集まる — もう一つの罠

高次元空間では別の奇妙な現象も起きる。

すべてのサンプル点が「端」に近くなる。

直感的に考えてみよう。p次元の球の中に点をランダムにまき散らす。 次元が高くなると、球の「中心付近」の体積の割合が急激に小さくなる。 その結果、ほとんどの点が球の外側（境界付近）に集まってしまう。

次元が増えるにつれて点が球の境界付近に集まる様子
左: 2D円では中心付近にも点が分布する。右のグラフ: 次元が増えると最近傍の距離 d(p, N) が急上昇する

p次元の単位球（原点を中心とする半径1の球）にN個の点を均一に配置したとき、 原点に最も近いデータ点はどれくらいの距離にあるだろうか？ 計算すると：

$$d(p, N) = \left(1 - \frac{1}{2}^{1/N}\right)^{1/p}$$

例えば、N=500点、p=10次元のとき：

$$d(10, 500) \approx 0.52$$

つまり、最も近いデータ点でも半径の52%の距離にある！

500点もあるのに、一番近い点が球の中心からそんなに離れているのだ。 アニメーションで、外側（明るい黄色）の点だけが残り、中心付近（暗くなった）の点が 実質的に「使えない」状態になる様子を確認してほしい。

これは何を意味するか。原点（テスト点）から見て、訓練データのほとんどが「境界付近」に集まっている。 予測には「補間（内挿）」ではなく「外挿」が必要になる。

外挿は難しい。隣接する点から学ぶのではなく、 遠く離れた点から「想像」しなければならないからだ。

次元がMSEを壊す — シミュレーションで見る

実際に数値で確かめよう。

以下の設定でシミュレーションを行う：

予測誤差（MSE）はバイアスと分散の和として書ける：

$$\text{MSE}(x_0) = \text{Var}_\mathcal{T}(\hat{y}_0) + \text{Bias}^2(\hat{y}_0)$$
MSE・バイアス・分散が次元の増加に伴い変化するグラフ
青: MSE、赤: バイアス²、緑: 分散。次元が増えるとバイアスが支配的になりMSEが急上昇する

次元p=1のとき：
最近傍は原点に非常に近い（距離≈0）。 関数値も $f(0) = 1$ に近い。バイアスも分散も小さい。

次元p=10のとき：
99%以上のサンプルで、最近傍は原点から0.5以上離れている。$f$ は原点から離れると急速に0に近づくため、$\hat{y}_0$ はほぼ0になる。 バイアスは最大となり、MSEは1.0に近づく（完全に外れた予測）。

グラフを見ると、分散（緑）はほとんど変わらないのに、 バイアス²（赤）が次元の増大とともに急上昇し、それがMSE全体（青）を押し上げている。 これが「次元の呪い」の実害だ。

線形モデルの救い — 構造が呪いを破る

では、こんな問いが生まれる。

「高次元では何も予測できないのか？」

答えは否だ。ただし、条件がある。

真の関係が線形だと仮定するなら：

$$Y = X^T \beta + \varepsilon, \quad \varepsilon \sim N(0, \sigma^2)$$

最小二乗法でフィットすると、テスト点 $x_0$ での期待予測誤差（EPE）は次のように近似できる：

$$\text{E}_{x_0}[\text{EPE}(x_0)] \approx \frac{\sigma^2 p}{N} + \sigma^2$$

変数の数 $p$ と誤差は線形の関係だ。

k-NNと線形モデルのEPEを次元の関数として比較するグラフ
青: 線形モデルのEPE（緩やかな上昇）、赤: 1-NNのEPE（急激な上昇）。次元が高くなるほど差が拡大する

k-NNでは次元の呪いが「指数的」に効いていた。 線形モデルでは $p$ の増加は「線形」に効くだけだ。 グラフで確認できるように、高次元になるほど両者の差が広がっていく。

なぜ線形モデルは呪いを回避できるのか？

k-NNは「近所」の概念に依存する。近所が崩壊すると手が使えない。 線形モデルは「全体的な傾き（β）」を学ぶ。局所的な近さに依存しない。

仮定が正しければ、線形モデルは高次元でも強力だ。 仮定が間違えていれば、k-NNが有利になる場合もある。

これが機械学習におけるバイアスとバリアンスのトレードオフの根本的な理由だ。 「強い仮定を置く（バイアスを増やす）」ことで「分散を下げ、次元の呪いに対処する」という選択が常に存在する。

まとめ — 次元の呪いと機械学習の本質

2.5節で学んだことをまとめよう。

次元の呪いの3つの側面をまとめた図
左: 近所の拡大（青）、中: 端への集中（赤）、右: 必要データ量の指数的増加（黄）

次元の呪い（Curse of Dimensionality）の正体：

1. 局所的な近所が局所的でなくなる

p次元で10%のデータをカバーするには各軸の80%が必要になる。

$$e_p(r) = r^{1/p} \xrightarrow{p \to \infty} 1$$

辺の長さは次元とともに1に近づく。

2. データが端に集まる

高次元では全データが球の境界付近に位置する。 内挿ではなく外挿が必要になる。

$$d(10, 500) \approx 0.52$$

3. 必要なデータ量が指数的に増える

1次元で100点が密なら、10次元で同じ密度には$100^{10} = 10^{20}$ 点が必要になる。 現実には集められないデータ量だ。

4. 解決策は「仮定」を置くこと

線形性を仮定すれば次元の呪いを線形スケールに抑制できる。 滑らかさを仮定すれば適度な汎化が得られる。 この仮定が「バイアス」を生む。 バイアスとバリアンスのトレードオフの根本がここにある。

次のセクション（2.6）では、統計モデルという枠組みで、 この仮定をどう組み込むかを学ぶ。 「モデルを仮定する」ということが単なるテクニックではなく、 高次元での学習を可能にする本質的なアプローチであることが見えてくるはずだ。