次元の呪いとは？わかりやすく解説

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

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

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

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

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

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

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

組合せ理論における次元の呪い

それぞれの変数が離散値をとるような問題においては、考慮すべき変数の組合せの総数が膨大になりうる。この現象は組合せ爆発と呼ばれる。二値変数がd個存在するという最も単純な例でも、可能な組み合わせは2^d個あり、変数の個数に対して指数関数的に増大する。この場合、すべての組合せを考慮するコストは、次元が増えるたびに2倍になる。

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

次元の呪いは、状態変数の次元が大きい動的最適化問題を数値的後ろ向き帰納法で解く際には重大な障害となる。また機械学習の問題においても、高次元の特徴空間と高次元空間での最近傍探索で、有限個の標本から状態を学習する際には、次元の呪いにより問題が複雑になる。機械学習の文脈においては、訓練データ数を固定してモデルの特徴量の次元を増やしていくとき、特定の次元数までは予測性能が向上するものの、それ以上次元を増やすと予測性能がかえって悪化するという現象のことを指す場合もある^[4]。この現象は、peaking phenomenon^[5] や Hughes phenomenon^[6] と呼ばれることがある。

脚注

[脚注の使い方]

^ ^a ^b 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6。
^ 手塚集、「数値多重積分に関する話題(<特集>数値計算)」『応用数理』 1998年 8巻 4号 p.267-276, doi:10.11540/bjsiam.8.4_267, 日本応用数理学会
^ Traub, J. F., & Woźniakowski, H. (1994). Breaking intractability. Scientific American, 270(1), 102-107.
^ 赤穂, 昭太郎「少量のデータに対する機械学習」『電子情報通信学会基礎・境界ソサイエティ Fundamentals Review』第16巻第4号、2023年4月1日、247–256頁、doi:10.1587/essfr.16.4_247、 ISSN 1882-0875。
^ Zollanvari, A.; James, A. P.; Sameni, R. (2019-07-11). “A Theoretical Analysis of the Peaking Phenomenon in Classification”. Journal of Classification 37 (2). doi:10.1007/s00357-019-09327-3.
^ Hughes, G. (1968-01). “On the mean accuracy of statistical pattern recognizers”. IEEE Transactions on Information Theory 14 (1): 55–63. doi:10.1109/TIT.1968.1054102. ISSN 0018-9448.

参考文献

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.

次元の呪いとは？わかりやすく解説