教養学部報
第673号 
次元の呪いを解く魔法 ─まるこふれんさもんてかるろほう─
福島孝治
「次元の呪い」とは、変数の数が増えるにつれて、問題の難しさが急激に増える現象を指す。ここでいう次元とは、空間の縦・横・高さに限らず、系を記述するために必要な変数の数だと考えればよい。二次元や三次元なら、図を描いて全体像を眺めたり、調べたい場所の見当をつけたりできる。しかし、変数が10個、１００個と増えると、そうした直感はほとんど役に立たない。各変数の可能性を少しずつ調べるだけで、全体として考えるべき場合の数は爆発的に増えてしまうからである。
その一例がNクイーン問題である。これは、N×Nの盤面にN個のクイーンを、互いに取り合わないように置く問題である。クイーンは行・列だけでなく斜め方向にも移動できるため、条件は見た目以上に厳しい。各行と各列に１個ずつ置くとしても、配置の候補はN!（階乗）通りもあり、その中から斜めの衝突がない配置を選び出す必要がある。小さなNであれば解を一つ見つけることは容易であるが、すべてを数え上げるとなると事情は大きく変わる。実際、二〇一六年にドイツの研究者たちがわずか27クイーンの解の個数を厳密に数え上げたが、その数は約2.3×1017（23京）個にも及ぶ。この規模の問題にすら潜む、膨大な組み合わせの数を扱う大変さこそが、次元の呪いの本質である。<
筆者の専門は統計物理学である。大学初年次にはマクロな世界の法則を扱う熱力学を学ぶが、その背後で、多数の粒子からなるミクロな世界と熱力学を結びつける体系が統計力学である。統計力学では系を構成する膨大な自由度を扱うため、必然的に高次元の問題が現れる。しかも知りたいことは、個々の粒子の運動そのものではなく、エネルギーや熱容量といったマクロな量の振る舞いである。そのためには高次元の確率分布に従って平均をとる必要があるが、ミクロな状態の数はあまりにも多すぎて、直接計算することができない。この「呪い」は物理学に限った話ではない。ベイズ統計、最適化問題、機械学習でも同様の困難が現れる。対象は異なっても、「巨大な可能性の空間をどう扱うか」という課題は共通しているのである。
この困難を回避する「魔法」が、マルコフ連鎖モンテカルロ法（ＭＣＭＣ）である。高次元の空間を隈なく調べる代わりに、乱数を用いて状態から状態へ少しずつ移動し、目的とする分布の「典型的な状態」を多く訪れることで、全体の性質を推定する。「マルコフ連鎖」とは、次の行き先が現在の状態だけで決まる確率的な過程のことである。ＭＣＭＣは、この移動を積み重ねることで、全体を見渡せない高次元空間を効率よく探索する。この方法は一九五三年に物理学で生まれ、その後、計算機の進展と方法論の改良によって大きく発展した。現在では、物理学にとどまらず、統計学、最適化問題、機械学習など多くの分野で重要な役割を果たしている。
ＭＣＭＣは、目的の分布を別の分布に置き換える近似計算ではなく、目的分布に従う状態を実際に生成し、そこから興味ある量を推定する手法である。原理的には、十分長く計算すれば正しい値に収束することが保証されている。一方で、乱数を用いるため、計算のたびに得られる値は少しずつ異なる。その結果を正しく評価するには、ゆらぐ値を統計的な誤差を伴う量として理解しなければならない。ＭＣＭＣを使うとは、単に一つの数値を得ることだけでなく、そのゆらぎを含めて結果を読み解くことなのである。ちなみに筆者は、ＭＣＭＣに物理学のエントロピー計算の知見を援用して64クイーンの解の個数を推定している。もちろん、これは厳密な数え上げではなく、統計的な妥当性をもった巨大な数の探求である。
このたび、西川宜彦さん（名古屋大学）と共著で『マルコフ連鎖モンテカルロ法入門─例からはじめるＭＣＭＣの基礎とアルゴリズム』（東京図書)を執筆した。本書では、具体的な例から出発してＭＣＭＣの基本的な考え方をたどりながら、最新のアルゴリズムまで俯瞰することを目指した。もちろん、ＭＣＭＣは魔法ではない。しかし、高次元の困難を紐解くための、極めて強力な智慧である。本書が、そのための入口となり、みなさんの抱える「次元の呪い」を解き明かすための手がかりとなれば幸いである。
（相関基礎科学／先進科学）
無断での転載、転用、複写を禁じます。
