前のページ 1/2 次のページ

モンテカルロ法 (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\; =\; \backslash int\_0^1\backslash dots\backslash int\_0^1\; f(x\_1,x\_2,\backslash dots,x\_n)\; dx\_1\backslash dots\; dx\_n$

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

: $X\_,\backslash quad\; 1\backslash leq\; i\; \backslash leq\; n,\; 1\backslash leq\; j\; \backslash leq\; N$

を生成して、

: $I\_N\; =\; \backslash frac\backslash sum\_j\; f(X\_,\; X\_,\; \backslash dots,\; X\_)$

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

これに層化抽出法を行うよう改良を加えた MISER 法や、加重サンプリングを行う VEGAS 法といった改良版のアルゴリズムがある。

MISER 法では、積分範囲を分割し、それぞれの領域中でランダム・サンプリングを行い、被積分関数値の分散がもっとも大きくなる領域をより小さな領域に分割して、そこでさらにサンプリングを行うことで精度を上げる。VEGAS 法では、被積分関数値の大きな場所にサンプリング点を増やし、積分値に寄与の大きなところに集中することで精度を上げる。

◆ 機械学習

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

: $V(s)\; \backslash leftarrow\; V(s)\; +\; \backslash alpha\backslash left[外部リンク]\; -\; V(s)\backslash right$

: $Q(s,\; a)\; \backslash leftarrow\; Q(s,\; a)\; +\; \backslash alpha\backslash left[外部リンク]\; -\; Q(s,\; a)\backslash right$

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

: $R\_t\; =\; r\_+\; \backslash gamma\; r\_+\; \backslash gamma^2\; r\_\backslash cdots\; =\; \backslash sum^\_\backslash gamma^r\_$

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

◆統計学

統計学におけるモンテカルロ法の1つとして、ブートストラップ法を参照。

◆乱数の選択

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

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

: 擬似乱数には次のようなものがある。

:* 線形合同法

:* 超一様乱数

:* メルセンヌ・ツイスタ

: この中では、周期が長い点でメルセンヌ・ツイスタが最良の選択肢である。

; 物理乱数: より規模の大きいモンテカルロ法を実行する場合には、物理現象を利用して物理乱数(真性乱数)を生成するハードウェアを利用する(ダイオードのPN接合部に生じる熱雑音を利用する方法がよく使われる)。

; 準乱数: 逆に規則性の強い乱数であり、数値積分に用いられる。準乱数を用いたモンテカルロ法を準モンテカルロ法という。準乱数のことを、低食い違い量列と呼ぶこともある。準乱数を数値積分に用いる目的は精度を高めることである。

◆精度

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

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

: $|\; I\; -\; I\_N\; |\backslash ,$

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

:

前のページ 1/2 次のページ

・モンテカルロ法 page1

・モンテカルロ法 page2