出典(authority):フリー百科事典『ウィキペディア(Wikipedia)』「2014/02/17 12:41:35」(JST)
モンテカルロ法 (モンテカルロほう、英: Monte Carlo method, MC) とは、決定論的問題および確率論的問題について、無作為抽出(乱数)によって問題の標本(sample)を集め、それを中心極限定理を用いて整理することで解を得る手法を指す[1]。
戦争中のロスアラモスにおける原子爆弾の製造にあたって、スタニスワフ・ウラムとジョン・フォン・ノイマンが本格的に用いたのを契機として、広く知られるようになった[2]。
カジノで有名な国家モナコ公国の4つの地区(カルティ)の1つであるモンテカルロに因んで名付けられた[3]。
モンテカルロ法(Monte Carlo method)は、算術、代数、幾何というような、数学における1つの分野ではなく、数学的な問題の近似解を、確率論における無作為抽出の手法を利用して求める方法を指す。
モンテカルロ法の要旨は、
ということに尽きる[4]。上記からわかるように、その理論的根拠は確率論(及び誤差論)にあるが、確率論的な問題に限らず決定論的問題についてもその解を与える。しかも手法として、解きたい問題に対してその問題の数式表現を必要としない[5]ため、問題を表現するにあたっての困難さに関係なく用いることができる。
なお、モンテカルロ法によって一定の精度を持つ解を得るにあたっては非常に多くの標本(sample)を必要とするため、乱数を得るため20世紀の前期に主として用いられていた乱数表では実務として間に合わず、短時間に多数の乱数を発生させることができる計算機(computer)に数値計算させる手法が実務的に必要とされることとなった。
計算理論の分野において、モンテカルロ法とは多項式時間で処理が終了されることは保証されるが、導かれる答えが必ずしも正しいとは限らない乱択アルゴリズム(ランダム・アルゴリズム)と一般に定義される[6]。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。
なお、これとは対照的に理論上処理の終了時間が必ずしも多項式時間で終了するとは限らないが、もし答えが得られれば必ず正しい乱択アルゴリズムをラスベガス法と呼ぶ。
計算複雑性理論では、確率的チューリング機械によるモデル化によってモンテカルロ法を用いて解決できる問題のクラスをいくつか定義している。代表的なところでは 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 重積分
をサンプル数 N のモンテカルロ法で計算するには、0 以上 1 以下の値をとる n × N 個の一様乱数
を生成して、
とすれば、IN が積分の近似値となる。
これに層化抽出法を行うよう改良を加えた MISER 法や、加重サンプリングを行う VEGAS 法といった改良版のアルゴリズムがある。MISER 法では、積分範囲を分割し、それぞれの領域中でランダム・サンプリングを行い、被積分関数値の分散が最も大きくなる領域をより小さな領域に分割して、そこでさらにサンプリングを行うことで精度を上げる。VEGAS 法では、被積分関数値の大きな場所にサンプリング点を増やし、積分値に寄与の大きなところに集中することで精度を上げる。 積分の計算法には他に台形公式・シンプソンの公式・二重指数関数型数値積分公式等があるが、モンテカルロ法はこれらの手法より多次元問題の際に利用しやすく、誤差が少ない。
機械学習の分野におけるモンテカルロ法とは強化学習の一種で、行動によって得られた報酬経験だけを頼りに状態価値、行動価値を推定する方法のことを指す。この方法はある状態 s から、得られる報酬の合計を予測しそれを基に状態の価値と次に行う行動を決定する。状態価値を V(s) 、行動価値を Q(s, a) で表す(ここで a は状態 s で行う行動である)とき、モンテカルロ法は以下の式で値を更新する。
ここで、αは学習率( 0 < α < 1)である。また Rt はシミュレーションによって得られる報酬の総和を未来に得られる分、割り引いたものであり、以下の式で表される。
ここで rt は時刻 t で得られた報酬であり、γ は割引率(0 < γ < 1) である。モンテカルロ法はある状態 s から何らかの方策で次の行動を選び、 Rt が収束するまでそれを繰り返した後、V(s) と Q(s, a) を更新するという行動を繰り返して最適な状態および行動を学習する。
統計学におけるモンテカルロ法の1つとして、ブートストラップ法を参照。
モンテカルロ法では状況に応じた乱数の選択が重要であり、モンテカルロ法の品質は使用する乱数の性質によって決まる。乱数は次の3種類に分けられる。
また、精度の良い結果を得るためには多くの試行回数が必要となる。しかし、1回の試行に膨大な時間がかかる場合、多くの試行を行うことは物理的に不可能となる。そのため、モンテカルロ法の精度は1回の試行に掛かる時間にも制限を受ける。
数値積分の精度はサンプル数 N を増やすことによって、よくなることが確率論によって保証されている。サンプルが真にランダムな乱数列だった場合には、積分の値と近似値の誤差
は、N を無限大にしたときほとんど確実に 0 に収束する(大数の法則)。この収束の速さに関しては、
となる(重複対数の法則)。すなわち、精度を10倍にするためには100倍のサンプルが必要となる。
これに対して、準モンテカルロ法では
となるので、精度を10倍にするためには約10倍のサンプルでよい。これが、準モンテカルロ法の利点である[7]。 ただし多次元の積分を行う場合には次元nが大きくなるので実際問題として効果が薄くなり、単純なモンテカルロの方が良い結果を与えることが多い。
ウィキメディア・コモンズには、モンテカルロ法に関連するカテゴリがあります。 |
|
|
全文を閲覧するには購読必要です。 To read the full text you will need to subscribe.
リンク元 | 「Monte Carlo法」「Monte Carlo method」 |
関連記事 | 「法」 |
.