次元の呪い
From Wikipedia, the free encyclopedia
次元の呪い（じげんののろい、英: The curse of dimensionality）という言葉は、リチャード・ベルマンが使ったもので、（数学的）問題の空間の次元が増えるに従って解法である算法から信頼できる結果を得るためのに必要となる計算資源の量が指数関数的に大きくなることを表している。
たとえば、単位区間をサンプリングして各点同士の距離を 0.01 以下に抑えるためには100個の点を等間隔に配置すれば十分である。しかし同程度のサンプリングを10次元の単位超立方体について行うとすると、必要な点の数は 1020 になる。したがって、このような問題の設定であれば、10次元の超立方体をサンプリングにより把握するのに必要な資源の量は単位区間の場合に比べると（次元数に比例して単に10倍になるのではなくて）1018倍になる。
高次元ユークリッド空間の広大さを示す別の例として、原点を中心とする半径が1の単位超球とちょうどそれに接するように包む1辺の長さが2の超立方体の体積を次元を上げながら比較してみよう。空間の次元数が増えるに従って、単位超球の体積は超立方体に比べて小さくなっていく。したがってこの意味では、超立方体の空間はその中心から遠い。言い換えると、高次元の超立方体ではそのほとんどの体積は角付近からの寄与であって「中心付近」の寄与は非常に小さくなる。このことは、カイ二乗分布を理解する上で重要である。
数値解析における次元の呪い（計算時間・数値誤差の増大）として、以下が挙げられる。
注記：実際には、上記の「線型」連立方程式の近似解を得る計算の手間は係数行列の次数 N に対して，N の3乗に比例する程度以下であり，いわゆる「次元の呪い」というものには該当しない。また、上記の「単変数の」数値係数高次方程式の全根を近似して求める計算についても、その手間は方程式の次数 D に対して D の3乗に比例する程度以下であるので、これもいわゆる「次元の呪い」というものには該当しない。通常は「次元の呪い」と呼ばれるものは、問題の空間次元や変数の数に対して、計算に必要となる資源の量（通常は演算量）が低次の多項式的増加関数にはならずに指数関数的増加関数になる（計算が困難な問題である）ことを意味する。