次元の呪い - yuuk1's Digital Garden

## 定義次元の呪い(curse of dimensionality、Bellman 1961)とは、入力空間の次元$p$が増すにつれ、局所的な近傍に基づく推定・平均化が破綻していく現象群を指す。[[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]] §2.5は、この現象を複数の側面から定量的に示す。 - **被覆率の増大**: 単位超立方体上に一様分布するデータについて、体積の割合$r$を捉える部分立方体の辺長は$e_p(r)=r^{1/p}$。10次元でデータの10%を捉えるには各座標の範囲の80%を覆う必要があり、そのような近傍はもはや「局所的」ではない。 - **境界近接性**: 単位球内に一様分布する$N$点について、原点から最近傍点までの距離の中央値は$d(p,N)=\left(1-(1/2)^{1/N}\right)^{1/p}$。$N=500, p=10$で$d\approx0.52$となり、ほとんどの点が訓練データの境界近くに位置する。予測点の近傍で内挿ではなく補外が必要になる。 - **サンプリング密度の低下**: サンプリング密度は$N^{1/p}$に比例するため、1次元で密なサンプル数$N_1$を保つ密度を10次元で再現するには$N_1^{10}$個のサンプルが必要になる。この結果、1最近傍法のようなバイアスの小さい局所平均化手法は、次元が増すとバイアス・分散がともに増大し、平均二乗誤差(MSE)が頭打ちになる。一方、線形モデルのような強い構造的仮定を課す手法は、期待予測誤差が次元$p$に対して線形($\sigma^2(p/N)+\sigma^2$)にしか増加せず、次元の呪いを回避できる。ただし、その構造的仮定が誤っていれば代償を払う。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]] §2.5) ## 横断的知見 - (2026-08-14時点で[[統計的機械学習]]との突き合わせは未着手。[[統計的機械学習]]にも「$d$次元標準正規分布でランダムに生成した2点間の距離が$\sqrt{2d}$付近に集中する」という別角度の定量的記述があり、本ページの部分立方体・境界近接性による定式化と補い合う関係にあるが、両者を突き合わせた横断的知見はまだ書けていない) - **局所回帰(kernel smoothing)は、k最近傍法と同じ「境界近傍の点の割合が次元とともに1に近づく」という機序で高次元で破綻する**: [[@2009__Springer__The Elements of Statistical Learning - Chapter 6 Kernel Smoothing Methods]] §6.3は、本ページが第2章由来で定式化した境界近接性(単位球内で最近傍点までの距離の中央値が次元とともに増大する現象)が、局所回帰・局所多項式回帰にも同様に当てはまることを明示する。局所多項式回帰は任意次元で境界補正を自動的に行える点でk-NNより有利だが、それでも2〜3次元を超えると実用性を失う。第6章は次元の呪いへの具体的な回避策として、第2章の「線形モデルのような構造的仮定」を一般化した3つの構造化手法を与える: (1) 計量行列$A$で座標ごとに重みを変える構造化カーネル、(2) ANOVA分解の高次項を削る加法モデル(第9章のバックフィッティングで1次元局所回帰に帰着させる)、(3) 一部の変数だけ局所化する変動係数モデル。これは「次元の呪いを回避する具体的手法の効果」という未解決の問いに対する、加法モデル・構造化カーネルの観点からの初回答である。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]] §2.5, [[@2009__Springer__The Elements of Statistical Learning - Chapter 6 Kernel Smoothing Methods]] §6.3-6.4) - **第18章は「$p$の大きさ」そのものではなく「有効自由度の大きさ」が呪いの本体であることを、$p\gg N$という極端な設定で裏づける**: 本ページが第2章から引く核心の主張は「線形モデルのような構造的仮定を課す手法は期待予測誤差が$p$に対して線形にしか増加せず次元の呪いを回避できる」というものだが、この式$\sigma^2(p/N)+\sigma^2$は暗黙に無正則化最小二乗($N>p$)を想定しており、$p>N$では共分散行列が特異になりそのままでは破綻する。[[@2009__Springer__The Elements of Statistical Learning - Chapter 18 High-Dimensional Problems - p >> N]] §18.1のシミュレーション(図18.1)は、$p$が20→100→1000と増えても、正則化強度(有効自由度)を$p$に応じて連続的に強めさえすれば予測誤差は制御可能であることを示す。すなわち両章を突き合わせると、次元の呪いの本体は名目上の次元数$p$ではなく、実際にデータから推定される**有効自由度**(第6章・第7章の$\mathrm{trace}(S)$型の尺度、[[バイアス-バリアンストレードオフ]]参照)であり、$p$がどれだけ大きくても有効自由度を$N$未満に抑える正則化を選べば予測は破綻しない、という統一的な描像が浮かび上がる。第2章は「構造的仮定さえあれば呪いを避けられる」と一般論を述べるにとどまるが、第18章は「その構造的仮定(正則化強度)を$p/N$比に応じてどれだけ強めるべきか」を具体的な数値(有効自由度20→35→43)で補う。矛盾ではなく、第2章の一般論を$p\gg N$という極限まで検証・具体化した関係にある。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]] §2.5, [[@2009__Springer__The Elements of Statistical Learning - Chapter 18 High-Dimensional Problems - p >> N]] §18.1) - **カーネル法(第12章)は、次元の呪いを自動的には回避しない――第2章「構造的仮定があれば呪いを避けられる」という一般論に対する反例的な検証になる**: [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]] §12.3.4は、真の分離が4変数(部分空間)にしか依存しないデータに6個のノイズ変数を加えた実験(Table 12.2)で、多項式SVM(カーネル法)の性能がノイズ変数の混入と多項式次数の誤選択に敏感に劣化することを示す。これはカーネル自身が「部分空間に集中する」という構造的仮定を持たないためであり、第2章が述べた「構造的仮定を課す手法は次元の呪いを回避できる」という一般論の逆――**構造的仮定を持たない手法(素朴なカーネルSVM)は、拡大された特徴空間においてもなお次元の呪いを受ける**――を具体的に裏づける。対照的に、変数選択能力を持つ加法モデル(BRUTO)・MARSはノイズ変数があっても性能をほぼ維持し、第6章が示した「加法モデルによる次元の呪い回避」という知見が分類設定でも再確認される。第2章「線形モデルのような構造的仮定」・第6章「加法モデル・構造化カーネル」に続き、第12章は「カーネルトリックによる特徴空間拡大それ自体は構造的仮定にならない」という否定的な事例を追加する。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]] §2.5, [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]] §12.3.4) - **第13章は、第6章の未解決の問い「最近傍法は高次元でどう修正・adaptiveな距離計量で対処されるか」に、局所適応という第6章とは異なる粒度の回答を与える**: [[@2009__Springer__The Elements of Statistical Learning - Chapter 6 Kernel Smoothing Methods]] §6.3の構造化カーネル(計量行列$A$)は、データ全体に対して大域的に固定された1つの計量を学習することで次元の呪いに対処する。これに対し[[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.4の判別適応最近傍法(DANN)は、単位立方体内の一様分布データで1最近傍点までの距離の中央値が次元とともに急速に0.5(立方体の端)へ近づくこと(式13.7、本ページの「境界近接性」と同じ機序)を出発点に、クエリ点ごとに局所的なクラス内・クラス間共分散行列から計量$\Sigma=W^{-1/2}[W^{-1/2}BW^{-1/2}+\epsilon I]W^{-1/2}$(式13.8-13.9)をその都度再計算する。すなわち第6章が「1つのグローバルな構造的仮定」で呪いに対処するのに対し、第13章は「仮定を置かずクエリ点周辺の局所構造をデータから直接推定する」という対極のアプローチを取る。10次元の同心球シミュレーション(図13.15)でDANNは標準k-NN・LVQより有意に低いテスト誤差を示し、局所適応が高次元での近傍の伸びを実際に緩和できることを裏づける。第13章はさらに、クエリ点ごとの局所計量を全訓練点で平均した大域的部分空間削減(§13.4.2、$\bar B=\frac1N\sum_i B_i$の固有ベクトル)も提示しており、これは第6章の大域的構造化カーネルに近い折衷案として両アプローチを橋渡しする。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 6 Kernel Smoothing Methods]] §6.3, [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.4, §13.4.2) - **入門書(ch.2)は次元の呪いを、ESLの距離集中・被覆率・境界近接性とは異なる第4の角度――取りうる入力パターンの組合せ爆発――から定式化する**: 本ページがESL第2章から引く3つの定量化(被覆率・境界近接性・サンプリング密度)は、いずれも連続空間上の点の分布に関する幾何的な議論である。これに対し[[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.3は、32×32の2値画像だけで取りうるパターン数が$2^{1024}$通り(約300桁)、19路盤の囲碁では$3^{19\times19}\approx10^{360}$通り(宇宙の原子数より多い)という**組合せ論的な場合の数**として次元の呪いを提示する。これは離散(あるいは離散化された)高次元データに固有の定式化であり、ESLが扱う連続値の統計的推定(k-NN・カーネル平滑化)における次元の呪いとは異なる文脈(丸暗記・網羅的列挙が不可能になる)で同じ現象を指し示す。ch.2はこの組合せ爆発を、機械学習が丸暗記ではなく汎化能力を必要とする根拠として使っており、ESLの「局所平均化手法の破綻」という統計的な帰結とは異なる、「網羅的な記憶が原理的に不可能になる」というアルゴリズム的な帰結を強調する点で相補的である。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]] §2.5, [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.3) ## 未解決の問い - 実データの「実効次元」(intrinsic dimension)が名目上の$p$より小さい場合、次元の呪いの影響はどの程度緩和されるか。 - 第18章は「有効自由度を$p/N$比に応じて強める」という処方箋を線形モデル(ridge・RDA・ロジスティック回帰)に限って示したが、この処方箋はk最近傍法や局所回帰のような非線形・局所平均化手法にも同様に適用できるか(近傍数$k$を$p$に応じてどこまで大きくすべきかという問いに一般化できるか)は本書の範囲では明示的に検証されていない。 - 第12章はカーネルSVMが次元の呪いを回避しない反例を示したが、カーネル自体に部分空間への適応性を持たせる方法(マルチカーネル学習、Automatic Relevance Determination等、いずれも本書の範囲外)は、第6章の構造化カーネル(計量行列$A$)とどう関係づけられるか。 - 第13章のDANN(局所適応)と第6章の構造化カーネル(大域適応)を同一データセットで直接比較した実証結果は本書に見当たらない。局所適応の柔軟性が計算コスト増加に見合う精度向上を常にもたらすかは未検証(詳細は[[最近傍法]]参照)。 ## 関連 - source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 6 Kernel Smoothing Methods]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]](カーネルSVMが次元の呪いを回避しない実験) / [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]](DANNによる局所適応距離計量) / [[@2009__Springer__The Elements of Statistical Learning - Chapter 18 High-Dimensional Problems - p >> N]](p≫Nでも正則化強度を上げれば呪いを回避できるという具体例) / [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]](組合せ論的な場合の数としての定式化) - concept: [[統計的機械学習]] / [[バイアス-バリアンストレードオフ]] / [[局所回帰]] / [[最近傍法]] / [[縮小推定]] / [[カーネル法]] / [[サポートベクターマシン]] / [[汎化能力]] ## 出典 - Hastie, T., Tibshirani, R., Friedman, J., *The Elements of Statistical Learning*, 2nd Edition, Springer, 2009, Chapter 2, §2.5; Chapter 6, §6.3; Chapter 12, §12.3.4; Chapter 13, §13.4; Chapter 18, §18.1. - 岡野原大輔, 『ディープラーニングを支える技術』, 技術評論社, 2022, 第2章, §2.3.