Publicitad E▼
⇨ definición de モンテカルロ法 (Wikipedia)
Publicidad ▼
Wikipedia
モンテカルロ法 (モンテカルロほう、Monte Carlo method, MC) とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにジョン・フォン・ノイマンにより考案された手法。カジノで有名な国家モナコ公国の4つの地区(カルティ)の1つであるモンテ・カルロから名付けられた。ランダム法とも呼ばれる。
目次 |
計算理論の分野において、モンテカルロ法とは多項式時間で処理が終了されることは保証されるが、導かれる答えが必ずしも正しいとは限らない乱択アルゴリズム(ランダム・アルゴリズム)と一般に定義される[1]。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に 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倍のサンプルでよい。これが、準モンテカルロ法の利点である[2]。 ただし多次元の積分を行う場合には次元nが大きくなるので実際問題として効果が薄くなり、単純なモンテカルロの方が良い結果を与えることが多い。
Contenido de sensagent
computado en 0,031s