モンテカルロ法
計算理論
編集計算理論の分野において、モンテカルロ法とは誤答する確率の上界が与えられる乱択アルゴリズム(ランダム・アルゴリズム)と定義される[1]。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。一般にモンテカルロ法は独立な乱択を用いて繰り返し、実行時間を犠牲にすれば誤答する確率をいくらでも小さくすることができる。またモンテカルロ法の中でも任意の入力に対して最大時間計算量の上界が入力サイズの多項式で与えられるものを効率的モンテカルロ法という[2]。
なお、これとは対照的に理論上必ずしも終了するとは限らないが、もし答えが得られれば必ず正しい乱択アルゴリズムをラスベガス法と呼ぶ。
計算複雑性理論では、確率的チューリング機械によるモデル化によってモンテカルロ法を用いて解決できる問題のクラスをいくつか定義している。代表的なところでは 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 重積分
をサンプルサイズ N のモンテカルロ法で計算するには、0 以上 1 以下の値をとる n × N 個の一様乱数
を生成して、
とすれば、IN が積分の近似値となる。一様乱数を超一様分布列に置き換えると準モンテカルロ法になる。
これに層化抽出法を行うよう改良を加えた MISER 法や、加重サンプリングを行う VEGAS 法といった改良版のアルゴリズムがある。MISER 法では、積分範囲を分割し、それぞれの領域中でランダム・サンプリングを行い、被積分関数値の分散が最も大きくなる領域をより小さな領域に分割して、そこでさらにサンプリングを行うことで精度を上げる。VEGAS 法では、被積分関数値の大きな場所にサンプリング点を増やし、積分値に寄与の大きなところに集中することで精度を上げる。 積分の計算法には他に台形公式・シンプソンの公式・二重指数関数型数値積分公式等があるが、モンテカルロ法はこれらの手法より多次元問題の際に利用しやすく、誤差が少ない。
強化学習
編集機械学習の強化学習の文脈では、モンテカルロ法とは行動によって得られた報酬経験だけを頼りに状態価値、行動価値を推定する方法のことを指す[8]。
統計学
編集統計学におけるモンテカルロ法の1つとして、ブートストラップ法を参照。
乱数(列)の選択
編集モンテカルロ法では状況に応じた乱数列の選択が重要である。また、結果の品質には使用する乱数の品質によるところがある。
- 擬似乱数列
- 擬似乱数列は初期状態によって未来の数列がすべて決定されるので、いわゆる「真にランダム」ではないが、シミュレーションなどでは(他に非決定的な要素が無ければ)再現性がある、という重要な特性がある。
- 物理乱数
- 真の乱数が必要な場合や、擬似乱数列生成系の初期状態の設定のために良質の乱数が必要な場合は、物理現象を利用して物理乱数(真性乱数)を生成するハードウェアを利用する(ダイオードのPN接合部に生じる熱雑音を利用する方法がよく使われる。放射性元素を使うものもある)。
- 超一様分布列
- 逆に規則性の強い数列であり、数値積分に用いられる[9]。超一様分布列を用いたモンテカルロ法を準モンテカルロ法という。超一様分布列のことを、低食い違い量列や準乱数列[10]と呼ぶこともある。超一様分布列を数値積分に用いる目的は精度を高めることである。
精度
編集また、精度の良い結果を得るためには多くの試行回数が必要となる。しかし、1回の試行に膨大な時間がかかる場合、多くの試行を行うことは物理的に不可能となる。そのため、モンテカルロ法の精度は1回の試行に掛かる時間にも制限を受ける。
モンテカルロ法による数値積分の精度はサンプルサイズ N を増やせばほとんどの場合によくなることが確率論によって保証される。サンプルが真にランダムな乱数列である場合には、モンテカルロ法で得られる積分の近似値の真値からの誤差
は、サンプルサイズ N を限りなく増大させればほとんど確実に 0 に収束する(大数の法則)。この収束の速さに関しては、
となる(重複対数の法則)。すなわち、誤差の大きさを10分の1倍に低減するにはサンプル数 N を100倍に増すことが必要となる。
これに対して、ある準モンテカルロ法では 積分変数の数を n とするとき,
となるので、誤差の大きさを10分の1倍に低減するにはサンプル数 N を約10倍に増すだけでよくなる。これが、準モンテカルロ法を用いる利点である[9]。 ただし高次元の積分を行う場合には次元の数 n が大きいので効果が減り、単純なモンテカルロの方が良い結果を与えることが多い。
脚注
編集- ^ Motwani & Raghavan 1995, p. 9.
- ^ Motwani & Raghavan 1995, p. 10.
- ^ 英: van der Corput sequence
- ^ 英: Halton sequence
- ^ 英: Sobol sequence
- ^ 英: Niederreiter sequence
- ^ 英: Faure sequence
- ^ Sutton, Richard S. (1998). Reinforcement Learning: An Introduction. p. 91. ISBN 978-0262039246
- ^ a b 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、280-281頁。ISBN 4-87408-414-1。
- ^ 英: quasi-random sequence
参考文献
編集- P.J. Davis and P.Rabinowitz、森正武(訳):「計算機による数値積分法」、日本コンピュータ協会(1981年2月15日)。
- Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized algorithms. Cambridge University Press. ISBN 0-521-47465-5. MR1344451. Zbl 0849.68039
- Jan van Leeuwen 編、「コンピュータ基礎理論ハンドブックⅠ:アルゴリズムと複雑さ」、廣瀬 健、野崎昭弘、小林孝次郎 監訳、丸善、1994年、ISBN 4-621-03921-0
- 電気学会 GA・ニューロを用いた学習法とその応用調査専門委員会 編、『学習とそのアルゴリズム』、森北出版、2002年、ISBN 4-627-82751-2
- 杉原・室田:「数値計算法の数理」、岩波書店 2003年、ISBN 978-4000055185
- 伏見正則 ・逆瀬川浩孝(監訳):「モンテカルロ法ハンドブック」、朝倉出版、ISBN 978-4254280050(2014年8月25日)。原著はDirk P.Kroese, Thomas Taimre, Zdravko I.Botev:Handbook of Monte Carlo Methods, John Wiley & Sons, Inc.,ISBN 978-0470177938(2011年1月28日)。
- 鈴木航介、合田隆「準モンテカルロ法の最前線」『日本応用数理学会論文誌』第30巻第4号、日本応用数理学会、2020年、320-374頁、doi:10.11540/jsiamt.30.4_320、ISSN 2424-0982。
- Müller, Fabio; Christiansen, Henrik; Schnabel, Stefan; Janke, Wolfhard (2023-07). “Fast, Hierarchical, and Adaptive Algorithm for Metropolis Monte Carlo Simulations of Long-Range Interacting Systems”. Phys. Rev. X (American Physical Society) 13 (3): 031006. 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).