モンテカルロ積分

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

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

概要

数値積分において、台形則などの手法は決定論的なアプローチを採用します。一方、モンテカルロ積分は非決定論的なアプローチを採用します。つまり、各実現値は異なる結果をもたらします。モンテカルロ法では、最終的な結果はそれぞれの誤差範囲を含む正しい値の近似値であり、正しい値はそれらの誤差範囲に収まる可能性が高いです。

モンテカルロ積分が扱う問題は、Ω（Ωの部分集合）の体積が $I=\int _{\Omega }f({\overline {\mathbf {x} }})\,d{\overline {\mathbf {x} }}$ $\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}}.$

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

単純なモンテカルロ法は単純な例には有効ですが、決定論的アルゴリズムよりも優れた結果を得るには、問題固有の標本分布を用いるアルゴリズムを用いる必要があります。適切な標本分布を用いることで、高次元積分関数のほぼ全てが非常に局所的であり、積分に顕著に寄与するのは小さな部分空間のみであるという事実を利用できます。^[6]モンテカルロ法に関する文献の大部分は、誤差推定値を改善するための戦略の開発に費やされています。特に、層別サンプリング（領域をサブドメインに分割する）と重要度サンプリング（非一様分布からサンプリングする）は、そのような手法の2つの例です。

例

モンテカルロ積分の典型的な例として、πの推定がある。関数と集合Ω = [−1,1] × [−1,1]（V = 4 ）を考える。 $H\left(x,y\right)={\begin{cases}1&{\text{if }}x^{2}+y^{2}\leq 1\\0&{\text{else}}\end{cases}}$ $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})$

右の図では、相対誤差がN の関数として測定されており、が確認されています。 ${\tfrac {Q_{N}-\pi }{\pi }}$ ${\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 (時間( 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で作成されました。

numpyをnpとしてインポートする   rng  =  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の例

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

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}}$

再帰層化サンプリング法は、1次元適応求積法を多次元積分に一般化したものです。各再帰ステップにおいて、積分値と誤差は単純なモンテカルロアルゴリズムを用いて推定されます。誤差推定値が必要な精度よりも大きい場合、積分体積はサブ体積に分割され、各サブ体積に対して手順が再帰的に適用されます。

通常の「2で割る」戦略は、多次元では機能しません。なぜなら、サブボリュームの数があまりにも急速に増加し、追跡できなくなるからです。代わりに、どの次元に沿って分割すれば最も大きな利益が得られるかを推定し、その次元に沿ってのみボリュームを分割します。

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

一般的な MISER ルーチンは同様のアルゴリズムを実装します。

ミザーモンテカルロ

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

層別サンプリングの考え方は、積分と分散のモンテカルロ推定値を持つ2つの分離した領域aとbについて、結合推定値の分散Var( f )が次のように与えられるという観察から始まります。 $E_{a}(f)$ $E_{b}(f)$ $\sigma _{a}^{2}(f)$ $\sigma _{b}^{2}(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]この手法における重要度サンプリングの主な結果は、均一サンプリングがより一般的な選択の特殊なケースであり、任意の分布からサンプルが抽出されることです。つまり、測定値Q _Nの分散を小さくするように選択できるということです。 ${\overline {\mathbf {x} }}$ $p({\overline {\mathbf {x} }})$ $p({\overline {\mathbf {x} }})$

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

正式には、分布から選択されたサンプルの集合が与えられた場合、 Iの推定値は^[3]で与えられる。 $p({\overline {\mathbf {x} }}):\qquad {\overline {\mathbf {x} }}_{1},\cdots ,{\overline {\mathbf {x} }}_{N}\in V,$ $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つであり、^[3]積分を計算する効率的な方法を提供します。 ${\overline {\mathbf {x} }}$ $p({\overline {\mathbf {x} }})$

ベガスモンテカルロ

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

参照

注記

^ Press et al. 2007, 第4章
^ Press et al. 2007, 第7章
^ abcd Newman & Barkema 1999、第2章
^ ニューマン＆バーケマ 1999、第1章
^ プレス他 2007
^ マケイ 2003, 284–292ページ
^ プレス＆ファラー 1990年、190～195ページ
^ クローズ、テイムレ、ボテフ 2011
^ ルパージュ 1978より

参考文献

レバノン州カフリッシュ(1998)。「モンテカルロ法および準モンテカルロ法」。アクタヌメリカ。7 : 1– 49。書誌コード: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). 「適応型多次元積分のための新しいアルゴリズム」.計算物理学ジャーナル. 27 (2): 192– 203. Bibcode :1978JCoPh..27..192L. doi :10.1016/0021-9991(78)90004-9.
Lepage, GP (1980). 「VEGAS: 適応型多次元積分プログラム」.コーネル大学プレプリント CLNS 80-447 .
Hammersley, JM; Handscomb, DC (1964). Monte Carlo Methods . Methuen. ISBN 978-0-416-52340-9。 {{cite book}}: ISBN / Date incompatibility (help)
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 (第3版). ニューヨーク: Cambridge University Press. ISBN 978-0-521-88068-8。
マッケイ、デイビッド(2003). 「第4.4章典型性および第29.1章」(PDF) . 情報理論、推論、学習アルゴリズム. ケンブリッジ大学出版局. ISBN 978-0-521-64298-9. MR 2012999。
Newman, MEJ; Barkema, GT (1999).統計物理学におけるモンテカルロ法. Clarendon Press.
ロバート、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] Newman & Barkema 1999、第2章

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

[5] プレス他 2007

[6] マケイ 2003, 284–292ページ

[7] プレス＆ファラー 1990年、190～195ページ

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

[Lepage,_1978-9] ルパージュ 1978より