モンテカルロ法のソースを表示

{{読み仮名|'''モンテカルロ法'''|モンテカルロほう|{{lang-en-short|Monte Carlo method}}、'''MC'''}}とは[[シミュレーション]]や[[数値計算]]を[[乱数列|乱数]]を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るために[[スタニスワフ・ウラム]]が考案し[[ジョン・フォン・ノイマン]]により命名された手法。[[カジノ]]で有名な国家[[モナコ]]公国の4つの地区（カルティ）の1つである[[モンテカルロ]]から名付けられた。ランダム法とも呼ばれる。

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

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

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

==準モンテカルロ法==
一様乱数ではなく、{{仮リンク|超一様分布列|en|Low-discrepancy sequence|label=超一様分布列}}を使用する方法を{{仮リンク|準モンテカルロ法|en|Quasi-Monte Carlo method|label=準モンテカルロ法}}という<ref>Harald Niederreiter: ''Random Number Generation and Quasi-Monte Carlo Methods'', SIAM (CBMS 63), ISBN 0-89871-295-5 (1992).</ref>。たとえばモンテカルロ数値積分法で、乱数の代わりに準乱数を用いれば収束の加速が期待できる。ただし、分布の一様性の高い数列としての準乱数は、モンテカルロ数値積分には適切であっても、それ以外の用途に用いた場合には、本来の答えと異なる結果を生じる可能性がある。

以下は超一様分布列の例である。
* [[ファンデルコルプト数列]]<ref>{{lang-en-short|van der Corput sequence}}</ref>
* {{仮リンク|ハルトン列|en|Halton sequence}}<ref>{{lang-en-short|Halton sequence}}</ref>
* {{仮リンク|ソボル列|en|Sobol sequence}}<ref>{{lang-en-short|Sobol sequence}}</ref>
* [[ニーダーライター列]]<ref>{{lang-en-short|Niederreiter sequence}}</ref>
* [[ファウレ列]]<ref>{{lang-en-short|Faure sequence}}</ref>

==数値積分==
[[Image:Pi 30K.gif|thumb|right|モンテカルロ法を[[円周率]]πの値の近似に適用した例。30,000点をランダムに置いたとき、πの推定量は実際の値から0.07%以下の誤差の範囲内にあった。]]

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

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

''n'' 重積分
: <math>I = \int_0^1\dotsi\int_0^1 f(x_1,x_2,\dotsc,x_n) dx_1\dotsm dx_n</math>
をサンプルサイズ ''N'' のモンテカルロ法で計算するには、0 以上 1 以下の値をとる ''n'' &times; ''N'' 個の一様乱数
: <math>X_{i,j},\quad 1\leq i \leq n, 1\leq j \leq N</math>
を生成して、
: <math>I_N = \frac{1}{N}\sum_j f(X_{1,j}, X_{2,j}, \dotsc, X_{n,j})</math>
とすれば、''I<sub>N</sub>'' が積分の近似値となる。一様乱数を超一様分布列に置き換えると準モンテカルロ法になる。

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

== 強化学習 ==
{{main|強化学習}}
[[機械学習]]の[[強化学習]]の文脈では、モンテカルロ法とは行動によって得られた報酬経験だけを頼りに状態価値、行動価値を推定する方法のことを指す<ref>{{Cite book
|first     = Richard S.
|last      = Sutton 
|year      = 1998
|title     = Reinforcement Learning: An Introduction
|isbn      = 978-0262039246
|url       = http://incompleteideas.net/book/RLbook2018trimmed.pdf
|page      = 91
}}</ref>。

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

==乱数(列)の選択==
モンテカルロ法では状況に応じた[[乱数列]]の選択が重要である。また、結果の品質には使用する乱数の品質によるところがある。

; 擬似乱数列: [[擬似乱数]]列は初期状態によって未来の数列がすべて決定されるので、いわゆる「真にランダム」ではないが、シミュレーションなどでは（他に非決定的な要素が無ければ）再現性がある、という重要な特性がある。
; 物理乱数: 真の乱数が必要な場合や、擬似乱数列生成系の初期状態の設定のために良質の乱数が必要な場合は、物理現象を利用して物理乱数（真性乱数）を生成するハードウェアを利用する（[[ダイオード]]のPN接合部に生じる熱雑音を利用する方法がよく使われる。放射性元素を使うものもある）。
; 超一様分布列: 逆に規則性の強い数列であり、数値積分に用いられる<ref name="algo">{{cite book | 1=和書 | title=C言語による最新アルゴリズム事典 | publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 | pages=280-281 | isbn=4-87408-414-1}}</ref>。超一様分布列を用いたモンテカルロ法を準モンテカルロ法という。超一様分布列のことを、'''低食い違い量列'''や'''準乱数列'''<ref>{{lang-en-short|quasi-random sequence}}</ref>と呼ぶこともある。超一様分布列を数値積分に用いる目的は精度を高めることである。

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

モンテカルロ法による数値積分の精度はサンプルサイズ ''N'' を増やせばほとんどの場合によくなることが[[確率論]]によって保証される。サンプルが真にランダムな乱数列である場合には、モンテカルロ法で得られる積分の近似値の真値からの誤差
: <math>| I - I_N |\,</math>
は、サンプルサイズ ''N'' を限りなく増大させればほとんど確実に 0 に収束する([[大数の法則]])。この収束の速さに関しては、
: <math>| I - I_N | < C \sqrt{\frac{\log \log N}{N}}</math>
となる（{{ill|重複対数の法則|en|Law of the iterated logarithm}}）。すなわち、誤差の大きさを10分の1倍に低減するにはサンプルサイズ ''N'' を100倍に増すことが必要となる。

これに対して、ある準モンテカルロ法では　積分変数の数を ''n'' とするとき，
: <math>| I - I_N | < C' \frac{(\log N)^n}{N}</math>
となるので、誤差の大きさを10分の1倍に低減するにはサンプルサイズ ''N'' を約10倍に増すだけでよくなる。これが、準モンテカルロ法を用いる利点である<ref name="algo" />。
ただし高次元の積分を行う場合には次元の数 ''n'' が大きいので効果が減り、単純なモンテカルロの方が良い結果を与えることが多い。

== 脚注 ==
{{reflist}}

== 参考文献 ==
{{参照方法|date=2015年10月9日 (金) 13:09 (UTC)}}
* P.J. Davis and P.Rabinowitz、森正武（訳）：「計算機による数値積分法」、日本コンピュータ協会（1981年2月15日）。
* {{cite book|last1 = Motwani|first1 = Rajeev|last2 = Raghavan|first2 = Prabhakar|year = 1995|title = Randomized algorithms|url = {{google books|QKVY4mDivBEC|plainurl=yes}}|publisher = Cambridge University Press|isbn = 0-521-47465-5|mr = 1344451|zbl = 0849.68039|ref = harv}}
* Jan van Leeuwen 編、「コンピュータ基礎理論ハンドブックⅠ：アルゴリズムと複雑さ」、廣瀬 健、野崎昭弘、小林孝次郎 監訳、丸善、1994年、ISBN 4-621-03921-0
* 電気学会 GA・ニューロを用いた学習法とその応用調査専門委員会 編、『学習とそのアルゴリズム』、森北出版、2002年、ISBN 4-627-82751-2
* 杉原・室田：「数値計算法の数理」、岩波書店 2003年、ISBN 978-4-00-005518-5
* 伏見正則 ・逆瀬川浩孝（監訳)：「モンテカルロ法ハンドブック」、朝倉出版、ISBN 978-4-254-28005-0（2014年8月25日）。原著はDirk P.Kroese, Thomas Taimre, Zdravko I.Botev：''Handbook of Monte Carlo Methods'', John Wiley & Sons, Inc.，ISBN 978-0-47017793-8（2011年1月28日）。
* {{Cite journal|和書 |author=鈴木航介 |author2=合田隆 |year=2020 |url=https://doi.org/10.11540/jsiamt.30.4_320 |title=準モンテカルロ法の最前線 |journal=日本応用数理学会論文誌 |volume=30 |issue=4 |pages=320-374 |doi=10.11540/jsiamt.30.4_320 |ISSN=2424-0982 |publisher=日本応用数理学会 |ref=harv}}
* {{Cite journal |author=Müller, Fabio; Christiansen, Henrik; Schnabel, Stefan; Janke, Wolfhard |date=2023-07 |url=https://doi.org/10.1103/PhysRevX.13.031006 |title=Fast, Hierarchical, and Adaptive Algorithm for Metropolis Monte Carlo Simulations of Long-Range Interacting Systems |journal=Phys. Rev. X |volume=13 |issue=3 |pages=031006 |publisher=American Physical Society |doi=10.1103/PhysRevX.13.031006}}
* K.K. Sabelfeld: ''Monte Carlo Methods: In Boundary Value Problems'', Springer-Verlag, ISBN 978-3-642-75979-6 (1991).
* 鈴木航介、合田隆：「重点解説 モンテカルロ法と準モンテカルロ法」、サイエンス社（SGC 197）、ISBN 978-4-7819-1623-1 (2025年1月25日)。

==関連項目==
{{Commonscat|Monte Carlo method}}
* [[ブートストラップ法]]
* [[数値積分]]
* [[乱数列]]
* [[メトロポリス法]]
* [[レプリカ交換法]]
* [[計算物理学]]
* [[保険数理]]
* [[金融工学]]
* [[乱択アルゴリズム]] - [[ラスベガス法]]
* [[逐次モンテカルロ法]]
* [[モンテカルロ木探索]]
* [[マルコフ連鎖モンテカルロ法]]
* [[次元の呪い]]
* [[マルコフ連鎖]]
* [[ランダム]]
* [[R言語]]
* [[GNU Octave]]
* [[コンピュータ囲碁]] - モンテカルロ法を応用した探索法により、レベルが急上昇した。
* [[ビュフォンの針]] - モンテカルロ法の考えが適用された古い例。
* [[レイトレーシング]] - レンダリング方程式を解く際に解法としてモンテカルロ法が使われる

{{Normdaten}}
{{DEFAULTSORT:もんてかるろほう}}
[[Category:モンテカルロ法|*]]
[[Category:ランダム・アルゴリズム]]
[[Category:統計学的近似]]
[[Category:統計力学]]
[[Category:数値解析]]
[[Category:計算物理学]]
[[Category:計算化学]]
[[Category:計算科学]]
[[Category:近似法]]
[[Category:数学に関する記事]]