次元の呪い

次元の呪い（じげんののろい、英: The curse of dimensionality）という言葉は、リチャード・ベルマンが使ったもので、（数学的）問題の空間の次元が増えるに従って解法である算法が必要とする計算資源の量が指数関数的に大きくなることを表している。

たとえば、単位区間をサンプリングして各点同士の距離を 0.01 以下に抑えるためには100個の点を等間隔に配置すれば十分である。しかし同程度のサンプリングを10次元の単位超立方体について行うとすると、必要な点の数は 10^20 になる。したがって、このような問題の設定であれば、10次元の超立方体をサンプリングにより把握するのに必要な資源の量は単位区間の場合に比べると（次元数に比例して単に10倍になるのではなくて）10^18倍になる。

高次元ユークリッド空間の広大さを示す別の例として、原点を中心とする半径が1の単位超球とちょうどそれに接するように包む1辺の長さが2の超立方体の体積を次元を上げながら比較してみよう。空間の次元数が増えるに従って、単位超球の体積は超立方体に比べて小さくなっていく。したがってこの意味では、超立方体の空間はその中心から遠い。言い換えると、高次元の超立方体ではそのほとんどの体積は角付近からの寄与であって「中心付近」の寄与は非常に小さくなる。このことは、カイ二乗分布を理解する上で重要である。

数値解析における次元の呪い

数値解析における次元の呪い（計算時間・数値誤差の増大）として、以下が挙げられる。

• 数値線形代数などにおいて、多次元の連立方程式を解くこと[1]。
• 求根アルゴリズムを使って高次の代数方程式を解くこと[1]。
• 数値多重積分(多次元の数値積分)[2][3]

注記：実際には、上記の「線型」連立方程式の近似解を得る計算の手間は係数行列の次数 N に対して，N の3乗に比例する程度以下であり，いわゆる「次元の呪い」というものには該当しない。また、上記の「単変数の」数値係数高次方程式の全根を近似して求める計算についても、その手間は方程式の次数 D に対して D の3乗に比例する程度以下であるので、これもいわゆる「次元の呪い」というものには該当しない。通常は「次元の呪い」と呼ばれるものは、問題の空間次元や変数の数に対して、計算に必要となる資源の量（通常は演算量）が低次の多項式的増加関数にはならずに指数関数的増加関数になる（計算が困難な問題である）ことを意味する。

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

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

関連項目

• 動的計画法
• 組合せ爆発
• 最近傍探索
• 乱択アルゴリズム - ラスベガス法
• 逐次モンテカルロ法
• マルコフ連鎖
• MCMC

出典

1. ^ 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ 現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6。 
2. 手塚集、「数値多重積分に関する話題(<特集>数値計算)」 『応用数理』 1998年 8巻 4号 p.267-276, doi:10.11540/bjsiam.8.4_267, 日本応用数理学会
3. Traub, J. F., & Woźniakowski, H. (1994). Breaking intractability. Scientific American, 270(1), 102-107.

参考文献

• Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
  • Republished 2003: Dover, ISBN 0486428095.
• Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.
• Powell, Warren B. 2007. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley, ISBN 0470171553.