モンテカルロ法
モンテカルロ法 (モンテカルロほう、英: Monte Carlo method, MC) とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにスタニスワフ・ウラムが考案しジョン・フォン・ノイマンにより命名された手法。カジノで有名な国家モナコ公国の4つの地区（カルティ）の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。
Contents
計算理論
計算理論の分野において、モンテカルロ法とは誤答する確率の上界が与えられる乱択アルゴリズム（ランダム・アルゴリズム）と定義される[1]。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。一般にモンテカルロ法は独立な乱択を用いて繰り返し、実行時間を犠牲にすれば誤答する確率をいくらでも小さくすることができる。またモンテカルロ法の中でも任意の入力に対して最大時間計算量の上界が入力サイズの多項式で与えられるものを効率的モンテカルロ法という[1]。
なお、これとは対照的に理論上必ずしも終了するとは限らないが、もし答えが得られれば必ず正しい乱択アルゴリズムをラスベガス法と呼ぶ。
計算複雑性理論では、確率的チューリング機械によるモデル化によってモンテカルロ法を用いて解決できる問題のクラスをいくつか定義している。代表的なところでは RPやBPP、PP などがある。これらのクラスと P や NP との関連性を解明していくことによって、モンテカルロ法のようにランダム性を含むアルゴリズムによって解ける問題の範囲が拡大しているのか（P ≠ BPP なのか）、それとも単に決定的アルゴリズムで解ける問題の多項式時間の次数を減らしているだけなのか（P=BPP なのか）は計算複雑性理論における主要課題の1つである。現在、NP ⊂ PP 、RP ⊆ NPであることは解っているが BPP と NPとの関係は解っていない。
準モンテカルロ法
乱数ではなく、一様分布列 (Low-discrepancy sequence) を使用する方法を準モンテカルロ法 (Quasi-Monte Carlo method) という。乱数を利用するよりも収束が早くなる場合がある。ただし、純粋にランダムな方法ではないので、正解を得られる可能性が確率論的に低下する場合がある。
数値積分
数値解析の分野においてはモンテカルロ法はよく確率を近似的に求める手法として使われる。n 回シミュレーションを行い、ある事象が m 回起これば、その事象の起こる確率は当然ながら m/n で近似される。試行回数が少なければ近似は荒く、試行回数が多ければよい近似となる。
また、この確率を利用すれば、積分（面積）の近似解を求めることが可能となる。領域 R の面積 S は、領域 R を含む面積 T の領域内でランダムに点を打ち、領域 R の中に入る確率 p をモンテカルロ法で求めれば、S = pT で近似される。
n 重積分
- [math]I = \int_0^1\dotsi\int_0^1 f(x_1,x_2,\dotsc,x_n) dx_1\dotsm dx_n[/math]
をサンプルサイズ N のモンテカルロ法で計算するには、0 以上 1 以下の値をとる n × N 個の一様乱数
- [math]X_{i,j},\quad 1\leq i \leq n, 1\leq j \leq N[/math]
を生成して、
- [math]I_N = \frac{1}{N}\sum_j f(X_{1,j}, X_{2,j}, \dotsc, X_{n,j})[/math]
とすれば、IN が積分の近似値となる。
これに層化抽出法を行うよう改良を加えた MISER 法や、加重サンプリングを行う VEGAS 法といった改良版のアルゴリズムがある。MISER 法では、積分範囲を分割し、それぞれの領域中でランダム・サンプリングを行い、被積分関数値の分散が最も大きくなる領域をより小さな領域に分割して、そこでさらにサンプリングを行うことで精度を上げる。VEGAS 法では、被積分関数値の大きな場所にサンプリング点を増やし、積分値に寄与の大きなところに集中することで精度を上げる。 積分の計算法には他に台形公式・シンプソンの公式・二重指数関数型数値積分公式等があるが、モンテカルロ法はこれらの手法より多次元問題の際に利用しやすく、誤差が少ない。
機械学習
機械学習の分野におけるモンテカルロ法とは強化学習の一種で、行動によって得られた報酬経験だけを頼りに状態価値、行動価値を推定する方法のことを指す。この方法はある状態 s から、得られる報酬の合計を予測しそれを基に状態の価値と次に行う行動を決定する。状態価値を V(s)、行動価値を Q(s, a) で表す（ここで a は状態 s で行う行動である）とき、モンテカルロ法は以下の式で値を更新する。
- [math] V(s) \leftarrow V(s) + \alpha\left[R_t - V(s)\right] [/math]
- [math] Q(s, a) \leftarrow Q(s, a) + \alpha\left[R_t - Q(s, a)\right] [/math]
ここで、αは学習率（0 < α < 1）である。また Rt はシミュレーションによって得られる報酬の総和を未来に得られる分、割り引いたものであり、以下の式で表される。
- [math] R_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dotsb = \sum^{\infty}_{\tau = 0}\gamma^{\tau}r_{t+1+\tau}[/math]
ここで rt は時刻 t で得られた報酬であり、γ は割引率 (0 < γ < 1) である。モンテカルロ法はある状態 s から何らかの方策で次の行動を選び、Rt が収束するまでそれを繰り返した後、V(s) と Q(s, a) を更新するという行動を繰り返して最適な状態および行動を学習する。
統計学
統計学におけるモンテカルロ法の1つとして、ブートストラップ法を参照。
乱数(列)の選択
モンテカルロ法では状況に応じた乱数列の選択が重要である。また、結果の品質には使用する乱数の品質に依るところがある。
- 擬似乱数列
- 擬似乱数列は初期状態によって未来の数列がすべて決定されるので、いわゆる「真にランダム」ではないが、シミュレーションなどでは（他に非決定的な要素が無ければ）再現性がある、という重要な特性がある。
- 物理乱数
- 真の乱数が必要な場合や、擬似乱数列生成系の初期状態の設定のために良質の乱数が必要な場合は、物理現象を利用して物理乱数（真性乱数）を生成するハードウェアを利用する（ダイオードのPN接合部に生じる熱雑音を利用する方法がよく使われる。放射性元素を使うものもある）。
- 準乱数
- 逆に規則性の強い乱数であり、数値積分に用いられる[2]。準乱数を用いたモンテカルロ法を準モンテカルロ法という。準乱数のことを、低食い違い量列と呼ぶこともある。準乱数を数値積分に用いる目的は精度を高めることである。
精度
また、精度の良い結果を得るためには多くの試行回数が必要となる。しかし、1回の試行に膨大な時間がかかる場合、多くの試行を行うことは物理的に不可能となる。そのため、モンテカルロ法の精度は1回の試行に掛かる時間にも制限を受ける。
数値積分の精度はサンプルサイズ N を増やすことによって、よくなることが確率論によって保証されている。サンプルが真にランダムな乱数列だった場合には、積分の値と近似値の誤差
- [math]| I - I_N |\,[/math]
は、N を無限大にしたときほとんど確実に 0 に収束する(大数の法則)。この収束の速さに関しては、
- [math]| I - I_N | \lt C \sqrt{\frac{\log \log N}{N}}[/math]
となる（重複対数の法則）。すなわち、精度を10倍にするためには100倍のサンプルが必要となる。
これに対して、準モンテカルロ法では
- [math]| I - I_N | \lt C \frac{(\log N)^n}{N}[/math]
となるので、精度を10倍にするためには約10倍のサンプルでよい。これが、準モンテカルロ法の利点である[2]。 ただし多次元の積分を行う場合には次元 n が大きくなるので実際問題として効果が薄くなり、単純なモンテカルロの方が良い結果を与えることが多い。
脚注
参考文献
- (1995) Randomized algorithms. Cambridge University Press. ISBN 0-521-47465-5.
- Jan van Leeuwen 編、『コンピュータ基礎理論ハンドブックI アルゴリズムと複雑さ』、廣瀬 健、野崎昭弘、小林孝次郎 監訳、丸善、1994年、ISBN 4-621-03921-0
- 電気学会 GA・ニューロを用いた学習法とその応用調査専門委員会 編、『学習とそのアルゴリズム』、森北出版、2002年、ISBN 4-627-82751-2
- 杉原・室田、 数値計算法の数理、岩波書店 2003年、978-4000055185