次元の呪い(じげんののろい、: The curse of dimensionality)という言葉は、 リチャード・ベルマン が使ったもので、(数学的)空間の次元が増えるのに対応して問題の算法が 指数関数的に大きく なることを表している。

例えば、単位区間をサンプリングするには100個の点を等間隔で、かつ点間の距離を 0.01 以上にならないように配置すれば十分である。同じようなサンプリングを10次元の単位超立方体について行おうとすると、必要な点の数は 1020 にもなる。したがって、10次元の超立方体はある意味では単位区間の1018倍の大きさとも言える。

高次元ユークリッド空間の広大さを示す別の例として、単位球と単位立方体の大きさを次元を上げながら比較してみればよい。次元が高くなると、単位球は単位立方体に比較して小さくなっていく。したがってある意味では、ほとんど全ての高次元空間は中心から遠く、言い換えれば、高次元単位空間はほとんど超立方体の角で構成されており、「中間」がない。このことは、カイ二乗分布を理解する上で重要である。

最適化と機械学習における次元の呪い

次元の呪いは、状態変数の次元が大きい動的最適化問題を数値的 後ろ向き帰納法 で解く際の重大な障害となる。また機械学習問題においても、高次元の 特徴空間 と高次元空間での最近傍探索で、有限個の標本から自然の状態を学習しようとする際に、次元の呪いが問題を複雑化する。


この記事では、Creative Commons Attribution-Share-Alike License 3.0の下に公開されているWikipediaの記事次元の呪いの資料を使用しています。