モンテカルロ法モンテカルロ法の概要

計算理論

計算理論の分野において、モンテカルロ法とは誤答する確率の上界が与えられる乱択アルゴリズム（ランダム・アルゴリズム）と定義される^[1]。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。一般にモンテカルロ法は独立な乱択を用いて繰り返し、実行時間を犠牲にすれば誤答する確率をいくらでも小さくすることができる。またモンテカルロ法の中でも任意の入力に対して最大時間計算量の上界が入力サイズの多項式で与えられるものを効率的モンテカルロ法という^[2]。

なお、これとは対照的に理論上必ずしも終了するとは限らないが、もし答えが得られれば必ず正しい乱択アルゴリズムをラスベガス法と呼ぶ。

計算複雑性理論では、確率的チューリング機械によるモデル化によってモンテカルロ法を用いて解決できる問題のクラスをいくつか定義している。代表的なところでは RPやBPP、PP などがある。これらのクラスと P や NP との関連性を解明していくことによって、モンテカルロ法のようにランダム性を含むアルゴリズムによって解ける問題の範囲が拡大しているのか（P ≠ BPP なのか）、それとも単に決定的アルゴリズムで解ける問題の多項式時間の次数を減らしているだけなのか（P=BPP なのか）は計算複雑性理論における主要課題の1つである。現在、NP ⊂ PP 、RP ⊆ NPであることはわかっているが BPP と NPとの関係はわかっていない。

準モンテカルロ法

一様乱数ではなく、超一様分布列（英語版）を使用する方法を準モンテカルロ法（英語版）という。乱数を利用するよりも収束が早くなる場合がある。ただし、純粋にランダムな方法ではないので、正解を得られる可能性が確率論的に低下する場合がある。

超一様分布列としては、以下などがある。

ファンデルコルプト数列^[3]
ハルトン列（英語版）^[4]
ソボル列（英語版）^[5]
ニーダーライター列^[6]
ファウレ列^[7]

数値積分

モンテカルロ法を円周率πの値の近似に適用した例。30,000点をランダムに置いたとき、πの推定量は実際の値から0.07%以下の誤差の範囲内にあった。

数値解析の分野においてはモンテカルロ法はよく確率を近似的に求める手法として使われる。n 回シミュレーションを行い、ある事象が m 回起これば、その事象の起こる確率は当然ながら m/n で近似される。試行回数が少なければ近似は荒く、試行回数が多ければよい近似となる。

また、この確率を利用すれば、積分（面積）の近似解を求めることが可能となる。領域 R の面積 S は、領域 R を含む面積 T の領域内でランダムに点を打ち、領域 R の中に入る確率 p をモンテカルロ法で求めれば、S = pT で近似される。

n 重積分

I=\int _{0}^{1}\dotsi \int _{0}^{1}f(x_{1},x_{2},\dotsc ,x_{n})dx_{1}\dotsm dx_{n}

をサンプルサイズ N のモンテカルロ法で計算するには、0 以上 1 以下の値をとる n × N 個の一様乱数

X_{i,j},\quad 1\leq i\leq n,1\leq j\leq N

を生成して、

I_{N}={\frac {1}{N}}\sum _{j}f(X_{1,j},X_{2,j},\dotsc ,X_{n,j})

とすれば、I_N が積分の近似値となる。一様乱数を超一様分布列に置き換えると準モンテカルロ法になる。

これに層化抽出法を行うよう改良を加えた MISER 法や、加重サンプリングを行う VEGAS 法といった改良版のアルゴリズムがある。MISER 法では、積分範囲を分割し、それぞれの領域中でランダム・サンプリングを行い、被積分関数値の分散が最も大きくなる領域をより小さな領域に分割して、そこでさらにサンプリングを行うことで精度を上げる。VEGAS 法では、被積分関数値の大きな場所にサンプリング点を増やし、積分値に寄与の大きなところに集中することで精度を上げる。積分の計算法には他に台形公式・シンプソンの公式・二重指数関数型数値積分公式等があるが、モンテカルロ法はこれらの手法より多次元問題の際に利用しやすく、誤差が少ない。

強化学習

詳細は「強化学習」を参照

機械学習の強化学習の文脈では、モンテカルロ法とは行動によって得られた報酬経験だけを頼りに状態価値、行動価値を推定する方法のことを指す^[8]。

脚注

^ Motwani & Raghavan 1995, p. 9.
^ Motwani & Raghavan 1995, p. 10.
^ 英: van der Corput sequence
^ 英: Halton sequence
^ 英: Sobol sequence
^ 英: Niederreiter sequence
^ 英: Faure sequence
^ Sutton, Richard S. (1998). Reinforcement Learning: An Introduction. p. 91. ISBN 978-0262039246
^ ^a ^b 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、280-281頁。ISBN 4-87408-414-1。
^ 英: quasi-random sequence

[前の解説]

[続きの解説]

「モンテカルロ法」の続きの解説一覧

[FOOTNOTEMotwaniRaghavan19959-1] Motwani & Raghavan 1995, p. 9.

[FOOTNOTEMotwaniRaghavan199510-2] Motwani & Raghavan 1995, p. 10.

[3] 英: van der Corput sequence

[4] 英: Halton sequence

[5] 英: Sobol sequence

[6] 英: Niederreiter sequence

[7] 英: Faure sequence

[8] Sutton, Richard S. (1998). Reinforcement Learning: An Introduction. p. 91. ISBN 978-0262039246

[algo-9] 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、280-281頁。ISBN 4-87408-414-1。

[10] 英: quasi-random sequence

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

モンテカルロ法モンテカルロ法の概要