モンテカルロ積分

数学において、モンテカルロ積分は乱数を用いた数値積分の手法である。これは定積分を数値的に計算する特定のモンテカルロ法である。他のアルゴリズムは通常、規則的なグリッド上で被積分関数を評価するが、^[¹^]モンテカルロ法は被積分関数を評価する点をランダムに選択する。^[²^]この方法は特に高次元積分に有効である。^[³^]

モンテカルロ積分を実行するには、一様サンプリング、層化サンプリング、重点サンプリング、逐次モンテカルロ（粒子フィルタとも呼ばれる）、平均場粒子法など、さまざまな方法があります。

概要

数値積分において、台形公式などの手法は決定論的なアプローチを採用しています。一方、モンテカルロ積分は非決定論的なアプローチを採用しており、各試行ごとに異なる結果が得られます。モンテカルロ法では、最終的な結果は誤差範囲付きの正しい値の近似値であり、正しい値はその誤差範囲内に収まる可能性が高いです。

モンテカルロ積分が扱う問題は、多次元定積分の計算である。 $I=\int _{\Omega }f({\overline {\mathbf {x} }})\,d{\overline {\mathbf {x} }}$ ここでΩは、 $\displaystyle \mathbb {R} ^{m}}$ ボリュームがあります $V=\int _{\Omega }d{\overline {\mathbf {x} }}$

単純なモンテカルロ法はΩ上で点を均一にサンプリングすることである：^{[ 4 ]} N個の均一サンプルが与えられた場合、 ${\overline {\mathbf {x} }}_{1},\cdots ,{\overline {\mathbf {x} }}_{N}\in \Omega ,$

私は次のように近似できます $I\approx Q_{N}\equiv V{\frac {1}{N}}\sum _{i=1}^{N}f({\overline {\mathbf {x} }}_{i})=V\langle f\rangle .$

これは、大数の法則により、 $\lim _{N\to \infty }Q_{N}=I.$

Q _NからIを推定すると、 Q _Nの誤差範囲は、分散の不偏推定値を使用して標本分散によって推定できます。

$\mathrm {Var} (f)=\mathrm {E} (\sigma _{N}^{2})\equiv {\frac {1}{N-1}}\sum _{i=1}^{N}\mathrm {E} \left[\left(f({\overline {\mathbf {x} }}_{i})-\langle f\rangle \right)^{2}\right].$ これは $\mathrm {Var} (Q_{N})={\frac {V^{2}}{N^{2}}}\sum _{i=1}^{N}\mathrm {Var} (f)=V^{2}{\frac {\mathrm {Var} (f)}{N}}=V^{2}{\frac {\mathrm {E} (\sigma _{N}^{2})}{N}}.$

シーケンス以来 $\left\{\mathrm {E} (\sigma _{1}^{2}),\mathrm {E} (\sigma _{2}^{2}),\mathrm {E} (\sigma _{3}^{2}),\ldots \right\}$ これはVar(f) と恒等的に等しいため、有界である。これが有限であると仮定する限り、この分散は 1/ Nとして漸近的にゼロに減少する。したがって、 QNの誤差の推定値は次のようになる _。 $\delta Q_{N}\estimate {\sqrt {\mathrm {Var} (Q_{N})}}=V{\frac {\sqrt {\mathrm {Var} (f)}}{\sqrt {N}}},$ これは減少します $\displaystyle {\tfrac {1}{\sqrt {N}}}}$ これは平均の標準誤差に $V$ この結果は積分の次元数に依存しないため、次元数に指数関数的に依存するほとんどの決定論的方法に対するモンテカルロ積分の約束された利点となります。^{[ 5 ]} 決定論的方法とは異なり、誤差の推定は厳密な誤差限界ではないことに注意することが重要です。ランダムサンプリングでは、誤差の過小評価につながる可能性のある被積分関数の重要な特徴をすべて明らかにできない場合があります。

単純な例ではナイーブなモンテカルロ法が機能しますが、決定論的アルゴリズムよりも改善できるのは、問題固有のサンプリング分布を使用するアルゴリズムを使用した場合のみです。適切なサンプル分布を使用すると、ほとんどすべての高次元被積分関数が非常に局所的であり、小さな部分空間のみが積分に大きく寄与するという事実を利用できます。^{[ 6 ]} モンテカルロ法の文献の大部分は、誤差推定を改善するための戦略の開発に費やされています。特に、層化サンプリング（領域をサブドメインに分割する）と重点サンプリング（非一様分布からのサンプリング）は、そのような手法の 2 つの例です。

例

サンプル数に対する相対誤差のスケーリングを示す $\displaystyle {\tfrac {1}{\sqrt {N}}}}$

モンテカルロ積分の典型的な例は、πの推定である。関数を考えてみよう。 $H\left(x,y\right)={\begin{cases}1&{\text{if }}x^{2}+y^{2}\leq 1\\0&{\text{else}}\end{cases}}$ そして集合Ω = [−1,1] × [−1,1]、V = 4。 $I_{\pi }=\int _{\Omega }H(x,y)dxdy=\pi .$

したがって、モンテカルロ積分を用いてπの値を計算する粗雑な方法は、 Ω上でN個の乱数を選び、 $Q_{N}=4{\frac {1}{N}}\sum _{i=1}^{N}H(x_{i},y_{i})$

右の図では、相対誤差 ${\tfrac {Q_{N}-\pi }{\pi }}$ N の関数として測定され、 $\displaystyle {\tfrac {1}{\sqrt {N}}}}$ 。

C/C++ の例

#include <stdio.h> #include <stdlib.h> #include <time.h> int main () { // ループ内のカウント数を 0 に初期化し、合計数を 100000 に設定します。int throws = 99999 , insideCircle = 0 ; double randX , randY , pi ;srand ( time ( NULL ));// xとyのランダムなペアごとに、半径1の円の内側にあるかどうかをチェックします。for ( int i = 0 ; i < throws ; i ++ ) { randX = rand () / ( double ) RAND_MAX ; randY = rand () / ( double ) RAND_MAX ; if ( randX * randX + randY * randY < 1 ) { insideCircle ++ ; } }// 円周率を計算して出力します。pi = 4.0 * insideCircle / throws ; printf ( "%lf \n " , pi ); }

Pythonの例

Pythonで作成されました。

import numpy as nprng = np.random.default_rng ( 0 )投擲数= 2000 、半径= 1# 0,0 を中心としたランダムな X と Y データを選択しますx = rng . uniform ( - radius , radius , throws ) y = rng . uniform ( - radius , radius , throws )# (x, y) が円の内側にある回数をカウントします。# これは、sqrt(x^2 + y^2) <= radius の場合に発生します。inside_circle = np . count_nonzero ( np . hypot ( x , y ) <= radius )# 面積を計算して出力します。投球回数が増えるにつれてπに近づくはずです。area = ( 2 * radius ) ** 2 * inside_circle / throws print ( area )

Wolfram Mathematicaの例

以下のコードは、関数を統合するプロセスを示しています。 $f(x)={\frac {1}{1+\sinh(2x)\log(x)^{2}}}$ から $0.8<x<3$ Mathematicaでモンテカルロ法を使用する：

func [ x_ ] := 1 / ( 1 + Sinh [ 2 * x ] * ( Log [ x ]) ^ 2 );(*収束を速めるために、切断正規分布からサンプルを抽出します*) Distrib [ x_ , average_ , var_ ] := PDF [ NormalDistribution [ average , var ], 1.1 * x - 0.1 ]; n = 10 ; RV = RandomVariate [ TruncatedDistribution [{ 0.8 , 3 }, NormalDistribution [ 1 , 0.399 ]], n ]; Int = 1 / n Total [ func [ RV ] / Distrib [ RV , 1 , 0.399 ]] * Integrate [ Distrib [ x , 1 , 0.399 ], { x , 0.8 , 3 }]NIntegrate [ func [ x ], { x , 0.8 , 3 }] (*実際の結果と比較してください*)

再帰的層化サンプリング

再帰的層化抽出法の例。この例では、関数は次のようになります。 $f(x,y)={\begin{cases}1&x^{2}+y^{2}<1\\0&x^{2}+y^{2}\geq 1\end{cases}}$ 上記の図から、提案されたアルゴリズムを用いて単位正方形内に積分した。サンプリングされた点を記録し、プロットした。明らかに、層別サンプリングアルゴリズムは、関数の変動が最も大きい領域に点を集中させる。

{\displaystyle f(x,y)={\begin{cases}1&x^{2}+y^{2}<1\\0&x^{2}+y^{2}\geq 1\end{cases}}} — 再帰的層化抽出法の例。この例では、関数は次のようになります。 $f(x,y)={\begin{cases}1&x^{2}+y^{2}<1\\0&x^{2}+y^{2}\geq 1\end{cases}}$ 上記の図から、提案されたアルゴリズムを用いて単位正方形内に積分した。サンプリングされた点を記録し、プロットした。明らかに、層別サンプリングアルゴリズムは、関数の変動が最も大きい領域に点を集中させる。

再帰的層化サンプリングは、一次元適応型求積法を多次元積分に一般化したものです。各再帰ステップにおいて、積分と誤差は単純なモンテカルロ法を用いて推定されます。誤差推定値が必要な精度よりも大きい場合、積分領域は複数のサブボリュームに分割され、そのサブボリュームに対して再帰的に処理が繰り返されます。

一般的な「2で割る」戦略は、多次元データには適していません。なぜなら、分割されるサブボリュームの数が急速に増えすぎて、管理が追いつかなくなるからです。そこで、どの次元に沿って分割すれば最も利益が得られるかを予測し、その次元に沿ってのみボリュームを分割します。

層化サンプリングアルゴリズムは、関数の分散が最大となる領域にサンプリングポイントを集中させることで、全体の分散を低減し、サンプリングをより効果的にします。これは図に示されています。

広く使われているMISERルーチンも同様のアルゴリズムを実装している。

マイザー・モンテカルロ

MISERアルゴリズムは再帰的層化サンプリングに基づいています。この手法は、分散が最も大きい領域に積分点を集中させることで、全体の積分誤差を低減することを目的としています。^{[ 7 ]}

層化サンプリングの考え方は、2 つの互いに素な領域aとbに対して、積分のモンテカルロ推定値から、 $E_{a}(f)$ そして $E_{b}(f)$ および差異 $\displaystyle \sigma _{a}^{2}(f)$ そして $\displaystyle \sigma _{b}^{2}(f)$ 結合推定値の分散 Var( f ) $E(f)={\tfrac {1}{2}}\left(E_{a}(f)+E_{b}(f)\right)$ は、 $\mathrm {Var} (f)={\frac {\sigma _{a}^{2}(f)}{4N_{a}}}+{\frac {\sigma _{b}^{2}(f)}{4N_{b}}}$

この分散は、点を次のように配置することで最小化されることが示せる。 ${\frac {N_{a}}{N_{a}+N_{b}}}={\frac {\sigma _{a}}{\sigma _{a}+\sigma _{b}}}$

したがって、各サブ領域において、関数の標準偏差に比例してサンプル点を割り当てることで、最小の誤差推定値が得られる。

MISERアルゴリズムは、各ステップで積分領域を1つの座標軸に沿って二等分し、2つのサブ領域を作成します。方向は、d個の可能な二等分をすべて調べ、2つのサブ領域の結合分散を最小にする方向を選択することによって決定されます。サブ領域の分散は、現在のステップで使用可能な点の総数の一部を使用してサンプリングすることによって推定されます。次に、最適な二等分から得られる2つの半空間それぞれについて、同じ手順が再帰的に繰り返されます。残りのサンプル点は、N _aとN _bの式を使用してサブ領域に割り当てられます。この積分点の再帰的な割り当ては、ユーザーが指定した深さまで続き、各サブ領域は単純なモンテカルロ推定を使用して積分されます。これらの個々の値とその誤差推定値は、上方向に結合され、全体的な結果とその誤差の推定値が得られます。

重要度サンプリング

重要度サンプリングアルゴリズムには、次のようなさまざまな種類があります。

重要度サンプリングアルゴリズム

重点サンプリングは、モンテカルロ積分を実行するための非常に重要なツールを提供する。^{[ 3 ]}^{[ 8 ]}この方法に対する重点サンプリングの主な結果は、一様サンプリングによって ${\overline {\mathbf {x} }}$ これは、サンプルが任意の分布から抽出される、より一般的な選択肢の特殊なケースである。 $p({\overline {\mathbf {x} }})$ その考えは、 $p({\overline {\mathbf {x} }})$ 測定値Q _Nの分散を減らすように選択できます。

0 を中心とし、σ = 1 のガウス関数を −1000 から 1000 まで数値積分したい場合を考えてみましょう。当然ながら、区間 [−1000, 1000] で一様にサンプルを抽出すると、積分に意味を持つのはごく一部に過ぎません。これを改善するには、サンプルが選択される分布とは異なる分布を選択します。たとえば、0 を中心とし、σ = 1 のガウス分布に従ってサンプリングします。もちろん、「正しい」選択は被積分関数に大きく依存します。

正式には、分布から選択されたサンプルのセットが与えられた場合 $p({\overline {\mathbf {x} }}):\qquad {\overline {\mathbf {x} }}_{1},\cdots ,{\overline {\mathbf {x} }}_{N}\in V,$ I の推定値は^[³^]で与えられる。 $Q_{N}\equiv {\frac {1}{N}}\sum _{i=1}^{N}{\frac {f({\overline {\mathbf {x} }}_{i})}{p({\overline {\mathbf {x} }}_{i})}}$

直感的に言えば、これは、特定のサンプルを他のサンプルの2倍多く選んだ場合、そのサンプルには他のサンプルの半分の重みを付けるという意味です。この推定量は、均一サンプリングの場合に自然に有効です。 $p({\overline {\mathbf {x} }})$ 定数である。

メトロポリス・ヘイスティングスアルゴリズムは、最もよく使われるアルゴリズムの1つです。 ${\overline {\mathbf {x} }}$ から $p({\overline {\mathbf {x} }})$ , ^{[ 3 ]}これにより、積分を計算する効率的な方法が提供される。

ベガス・モンテカルロ

VEGASアルゴリズムは、関数fのヒストグラムを作成する積分領域を複数回通過することで、正確な分布を近似します。各ヒストグラムは、次の通過のためのサンプリング分布を定義するために使用されます。漸近的に、この手順は目的の分布に収束します。^[⁹^]ヒストグラムのビンの数がKd^のように増加するのを避けるために、確率分布は分離可能な関数によって近似されます。 $g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\ldots$ そのため、必要なビンの数はKdだけになります。これは、被積分関数の座標軸への射影から関数のピークを特定することと同等です。VEGAS の効率はこの仮定の妥当性に依存します。被積分関数のピークが適切に局所化されている場合に最も効率的です。被積分関数を近似的に分離可能な形式に書き換えることができれば、VEGAS による積分の効率が向上します。VEGAS には多くの追加機能が組み込まれており、層化サンプリングと重点サンプリングの両方を組み合わせています。^{[ 9 ]}

参考文献

レバノン州カフリッシュ(1998)。「モンテカルロ法および準モンテカルロ法」。アクタヌメリカ。7 : 1– 49。Bibcode : 1998AcNum...7....1C。土井：10.1017/S0962492900002804。S2CID 5708790。
Weinzierl, S. (2000). "モンテカルロ法入門". arXiv : hep-ph/0006269 .
Press, WH; Farrar, GR (1990). "多次元モンテカルロ積分のための再帰的層別サンプリング" . Computers in Physics . 4 (2): 190. Bibcode : 1990ComPh...4..190P . doi : 10.1063/1.4822899 .
Lepage, GP (1978). "適応型多次元積分のための新しいアルゴリズム". Journal of Computational Physics . 27 (2): 192–203 . Bibcode : 1978JCoPh..27..192L . doi : 10.1016/0021-9991(78)90004-9 .
Lepage, GP (1980). "VEGAS: 適応型多次元統合プログラム". Cornell Preprint CLNS 80-447 .
ハマーズリー、JM; ハンズコム、DC (1964).モンテカルロ法. メシュエン. ISBN 978-0-416-52340-9。{{cite book}}ISBN /日付の不一致（ヘルプ）
Kroese, DP ; Taimre, T.; Botev, ZI (2011).モンテカルロ法ハンドブック. John Wiley & Sons.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8。
マッケイ、デイビッド（2003）。「第4.4章典型性および第29.1章」（PDF）。情報理論、推論、学習アルゴリズム。ケンブリッジ大学出版局。ISBN 978-0-521-64298-9. MR 2012999 .
ニューマン、MEJ; バーケマ、GT (1999).統計物理学におけるモンテカルロ法. クラレンドン・プレス.
ロバート、CP;カセラ、G (2004)。モンテカルロ統計手法(第 2 版)。スプリンガー。ISBN 978-1-4419-1939-7。

外部リンク

カフェ数学：モンテカルロ積分：モンテカルロ積分（原理、仮説、信頼区間）を解説するブログ記事
Boost.Math ：ナイーブモンテカルロ積分：C++ナイーブモンテカルロルーチンのドキュメント
統計物理学の問題に適用されるモンテカルロアプレット

[1] Press et al. 2007 、第4章

[2] Press et al. 2007 、第7章

[newman1999ch2-3] 1 2 3 4ニューマン＆バーケマ 1999 、第2章

[newman1999ch1-4] ニューマン＆バーケマ 1999 、第1章

[5] プレス他、2007年

[6] マッケイ 2003、284 ～292ページ

[7] Press & Farrar 1990 、pp. 190–195

[kr11-8] クローゼ、タイムレ、ボテフ 2011

[Lepage,_1978-9] 1 2ルパージュ 1978

[

[

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[