スポンサードリンク

モンテカルロ法

モンテカルロ法 (Monte Carlo method, MC)とはシミュレーションや数値計算を乱数を用いて行なう手法の総称。元々は、中性子が物質中を動き回る様子を探るためにジョン・フォン・ノイマンにより考案された手法。カジノの都市国家モナコ公国の4つの地区（カルティ）の一つであるモンテ・カルロから名づけられた。

計算理論

計算理論の分野に於いて、モンテカルロ法とは多項式時間で処理が終了されることは保証されるが、導かれる答えが必ずしも正しいとは限らない乱択アルゴリズムと一般に定義される。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。

なお、これとは別に答えは必ず正しいが処理の終了時間が必ずしも多項式時間で終了するとは限らない乱択アルゴリズムの場合はラスベガス法と呼ばれる。

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

数値積分

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

また、この確率を利用すれば、積分（面積）の近似解を求めることが可能となる。領域Rの面積Sは、領域Rを含む面積Tの領域内でランダムに点を打ち、領域Rの中に入る確率pをモンテカルロ法で求めれば、S=pTで近似される。積分の計算法には他に台形公式・シンプソンの公式等があるが、モンテカルロ法はこれらの手法より重積分に強いという特徴がある。

n 重積分

$I = \int_0^1\dots\int_0^1 f(x_1,x_2,\dots,x_n) dx_1\dots 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}, \dots, X_{n,j})$

とすれば、IN が積分の近似値となる。

機械学習

機械学習の分野におけるモンテカルロ法とは強化学習の一種で、行動によって得られた報酬経験だけを頼りに状態価値、行動価値を推定する方法のことを指す。この方法はある状態 s から、得られる報酬の合計を予測しそれをもとに状態の価値と次に行う行動を決定する。状態価値を　V(s) 、行動価値を Q(s, a) で表す（ここで a は状態 s で行う行動である）とき、モンテカルロ法は以下の式で値を更新する。

$V(s) \leftarrow V(s) + \alpha\left[R_t - V(s)\right]$ $Q(s, a) \leftarrow Q(s, a) + \alpha\left[R_t - Q(s, a)\right]$

ここで、αは学習率（ 0 < α < 1）である。また　Rt はシミュレーションによって得られる報酬の総和を未来に得られる分割り引いたものであり、以下の式で表わされる。

$R_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} \cdots = \sum^{\infty}_{\tau = 0}\gamma^{\tau}r_{t+1+\tau}$

ここで rt は時刻 t で得られた報酬であり、γ は割引率（0 < γ < 1) である。モンテカルロ法はある状態 s から何らかの方策で次の行動を選び、 Rt が収束するまでそれを繰り返した後、V(s) と Q(s, a) を更新するという行動を繰り返して最適な状態および行動を学習する。

乱数の選択

モンテカルロ法では状況に応じた乱数の選択が重要であり、モンテカルロ法の精度は使用する乱数の性質によって決まる。乱数は次の三種類に分けられる。

擬似乱数コンピュータ等を利用する場合は、完全な乱数ではなく、擬似乱数を使うことになる。擬似乱数による乱数列は、初期値を決めるとすべて決定されるので、ランダムな数列ではないが、簡単に利用できるので、モンテカルロ法を使用する場合の最初の選択肢である。擬似乱数には次のようなものがある。

線形合同法
超一様乱数
メルセンヌ・ツイスタ

この中では、周期が長い点でメルセンヌ・ツイスタが最良の選択肢である。物理乱数より規模の大きいモンテカルロ法を実行する場合には、物理現象を利用して物理乱数（真性乱数）を生成するハードウェアを利用する（ダイオードのPN接合部に生じる熱雑音を利用する方法がよく使われる）。準乱数逆に規則性の強い乱数であり、数値積分に用いられる。準乱数を用いたモンテカルロ法を準モンテカルロ法という。準乱数のことを、低食い違い量列と呼ぶこともある。準乱数を数値積分に用いる目的は精度を高めることである。

精度

また、精度の良い結果を得るためには多くの試行回数が必要となる。しかし、一回の試行に膨大な時間がかかる場合、多くの試行を行うことは物理的に不可能となる。そのため、モンテカルロ法の精度は一回の試行にかかる時間にも制限を受ける。

数値積分の精度はサンプル数 N を増やすことによって、よくなることが確率論によって保証されている。サンプルが真にランダムな乱数列だった場合には、積分の値と近似値の誤差

$| I - I_N |\,$

は、N を無限大にしたときほとんど確実に 0 に収束する(大数の法則)。この収束の速さに関しては、

$| I - I_N | < C \sqrt{\frac{\log \log N}{N}}$

となる（重複対数の法則）。すなわち、精度を10倍にするためには100倍のサンプルが必要となる。

これに対して、準モンテカルロ法では

$| I - I_N | < C \frac{(\log N)^n}{N}$

となるので、精度を10倍にするためには約10倍のサンプルでよい。これが、準モンテカルロ法の利点である。ただし多次元の積分を行う場合には次元nが大きくなるので実際問題として効果が薄くなり、単純なモンテカルロの方が良い結果を与えることが多い。

参考文献

Jan van Leeuwen 編、『コンピュータ基礎理論ハンドブックI アルゴリズムと複雑さ』、廣瀬健、野崎昭弘、小林孝次郎監訳、丸善、1994年、ISBN 4-621-03921-0
電気学会 GA・ニューロを用いた学習法とその応用調査専門委員会編、『学習とそのアルゴリズム』、森北出版、2002年、ISBN 4-627-82751-2

変更履歴
Wikipedia All text is available under the terms of the GNU Free Documentation License.

モンテカルロ法の書籍検索結果

乱数とモンテカルロ法

マルコフ連鎖モンテカルロ法 (統計ライブラリー)

モンテカルロ法の金融工学への応用 (シリーズ・現代金融工学)

ビジネスリスク分析入門―モンテカルロ・シミュレーションの応用事例 (早稲田大学理工総研シリーズ)

計算統計 2 マルコフ連鎖モンテカルロ法とその周辺 (統計科学のフロンティア)