몬테카를로 통합

몬테카를로 통합의 삽화. 이 예에서 도메인 D는 내부 원이고 도메인 E는 사각형이다. 사각형의 면적(4)을 쉽게 계산할 수 있기 때문에 원 안의 점(40)과 총점(50)의 비율(0.8)으로 원(元²)의 면적(4*0.8 = 3.2 π)을 추정할 수 있어 원(元)의 면적(4*0.8 = 3.2 π)에 대한 근사치를 산출할 수 있다.

수학에서 몬테카를로 통합은 난수를 이용한 숫자 통합 기법이다. 확실한 적분을 숫자로 계산하는 것은 특정한 몬테카를로 방식이다. 다른 알고리즘은 보통 정규 그리드에서 통합과 통합을 평가하는 반면,^[1] 몬테 카를로는 통합과가 평가되는 지점을 무작위로 선택한다.^[2] 이 방법은 특히 고차원적 통합에 유용하다.^[3]

몬테카를로 통합을 수행하는 방법에는 균일한 샘플링, 층화된 샘플링, 중요도 샘플링, 순차 몬테카를로(일명 입자 필터), 평균장 입자 방식 등 다양한 방법이 있다.

개요

수치적 통합에서 사다리꼴 규칙과 같은 방법은 결정론적 접근법을 사용한다. 반면에 몬테카를로 통합은 비결정론적 접근방식을 채택한다: 각 실현은 다른 결과를 제공한다. 몬테카를로에서 최종 결과는 각각의 오류 막대와 함께 정확한 값의 근사치로, 정확한 값은 그러한 오류 막대 안에 있을 가능성이 높다.

Monte Carlo 통합 주소의 문제는 다차원 확정 적분 계산이다.

I=\int _{\Oomega}f({\overline {\mathbf {x}}}})\,d{\overline {\mathbf {x}}}

여기서^m R의 하위 집합인 Ω은 볼륨을 가진다.

V=\int _{\Oomega}d{\overline {\mathbf{x}}}

순진한 몬테카를로 접근방식은 Ω으로 균일하게 점을 샘플링하는 것이다.^[4] N개의 균일한 샘플이 주어진다면,

{\mathbf {x}}{1},\cdots, {\cdots, {\cdline {\mathbf{x}}}}}\Oomega ,

나는 대략 다음과 같다.

{\displaystyle I\approx Q_{N}\equiv V{\frac {1}{N}}\sum _{i=1}^{N}f({\overline {\mathbf {x} }}_{i})

=V\langle f\angle

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

\lim _{N\to \infty }Q_{N}=I

→

\lim _{N\to \infty }Q_{N}=I

\lim _{N\to \infty }Q_{N}=I

\lim _{N\to \infty }Q_{N}=I

=

\lim _{N\to \infty }Q_{N}=I

\lim _{N\to \infit }Q_{N}=I

.

Q에서_N I를 추정할 경우, Q의_N 오차 막대는 분산에 대한 불편 추정치를 사용하여 표본 분산으로 추정할 수 있다.

{\displaystyle \mathrm {Var}(f)\equiv \sigma _{{N}^{{N-1}\sum _{i=1}^{N}\f({\overline {\mathbf{x}}}}-\langle frangle \rigle \2}}.

그 결과로 이어지다

\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 {\sigma _{N}^{2}}{N}}

.

그 순서가 있는 한

\left\{\\dotsma _{1}^{2},\ldma _{2}^{2},\ldots \right\}}

경계, 이 분산은 점증적으로 0으로 1/N로 감소한다. Q의_N 오차는 다음과 같다.

\delta Q_{N}\cHB {\sqrt {\mathrm {Var}(Q_{N})}}=V{\frac {\sigma _{N}{\sqrt{N}}}},},

${\tfrac {1}{\sqrt {N}}}$ ${\$ 만큼 감소함 ${\tfrac {1}{\sqrt {N}}}$ 이것은 $V$ $V$ 과 곱한 평균의 표준 오차 $V$ 이 결과는 치수에 따라 기하급수적으로 의존하는 대부분의 결정론적 방법에 대한 몬테카를로 통합의 약속된 장점인 적분 치수의 수에 의존하지 않는다.^[5] 결정론적 방법과는 달리 오류의 추정치는 엄격한 오차범위가 아니다. 무작위 표본 추출은 통합의 모든 중요한 특징을 밝혀내지 못할 수 있으며 오류를 과소평가할 수 있다.

천진난만한 몬테카를로는 단순한 예를 위해 일하지만, 결정론적 알고리즘에 대한 개선은 문제별 샘플링 분포를 사용하는 알고리즘에서만 이루어질 수 있다. 적절한 표본 분포를 통해 거의 모든 고차원적 통합업체가 매우 국부적이고 특히 작은 하위 공간만이 적분화에 기여한다는 사실을 이용할 수 있다.^[6] 몬테카를로 문헌의 상당 부분은 오류 추정치를 개선하기 위한 전략을 개발하는 데 전념하고 있다. 특히, 계층화된 표본 추출 - 지역을 하위 영역으로 나누는 것과 중요도 표본 추출 - 균일하지 않은 분포에서 표본 추출하는 것 -은 그러한 기법의 두 가지 예다.

예

스케일링

{\tfrac {1}{\sqrt {N}}}

{\tfrac {1}{\sqrt {N}}}

{\

을(를) 표시하는 샘플 수의 함수로서의 상대적 오류

몬테카를로 통합의 패러다임적인 예는 π의 추정이다. 함수를 고려하십시오.

H\left(x,y\right)={\begin{case}1&{\text{}}}}}}x^{2}+y^{2}}}\leq 1\\0&{\text{data}\end{case}}

Ω = [-1,1] × [-1,1], V = 4로 설정. 참고:

I_{\pi }=\int _{\Oomega }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 }}$ Q - ${\tfrac {Q_{N}-\pi }{\pi }}$ { ${\tfrac {Q_{N}-\pi }{\pi }}$ {\ $displaystyle {\tfrac {Q_{N}-\pi }{\pi$ }}}{\pi $}}}}}}$ 을(를) N의 함수로 측정하여 ${\tfrac {Q_{N}-\pi }{\pi }}$ ${\tfrac {1}{\sqrt {N}}}$ ${\$ { $1}{\tqrt{{{N$

C의 예

실제 난수 생성기를 사용해야 함을 명심하십시오.

인트로 i, 던지다 = 99999, 내부순환로 = 0; 곱절로 하다 랜드엑스, 랜디, 파이;  srand(시간(NULL));  을 위해 (i = 0; i < 던지다; ++i) {   랜드엑스 = 랜드() / (곱절로 하다) 랜드_MAX;   랜디 = 랜드() / (곱절로 하다) 랜드_MAX;   만일 (랜드엑스 * 랜드엑스 + 랜디 * 랜디 < 1) ++내부순환로; }  파이 = 4.0 * 내부순환로 / 던지다;

울프램 매스매티카 예

아래 코드는 함수를 통합하는 과정을 설명한다.

{\displaystyle f(x)={\frac {1}{1+\sinh(2x)\log(x)^{2}}:

$0.8<x<3$ < $0.8<x<3$ < $0.8<x<3$ $0.8<x<3$ 부터 $0.8<x<3$ Mathematica:

펑크[x_] := 1/(1 + 신[2*x]*(로그[x])^2);  (*정규 분포가 잘린 상태에서 수렴 속도를 높이는 샘플*) 분배[x_, 평균_, var_] :=   PDF[NormalDistribution[평균의, 시합을 하다], 1.1*x - 0.1]; n = 10; RV = 랜덤변량[잘림분포[{0.8, 3}, NormalDistribution[1, 0.399]], n]; 인트 = 1/n 합계[펑크[RV]/분배[RV, 1, 0.399]]*통합[분배[x, 1, 0.399], {x, 0.8, 3}]  니엔테그레이트[펑크[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}}

x

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

)

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

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

+ y

f(x,y)={\begin{cases}1&x^{2}+y^{2}<1\\0&x^{2}+y^{2}\geq 1\end{cases}}

< 1

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

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

f(x,y)={\begin{cases}1&x^{2}+y^{2}<1\\0&x^{2}+y^{2}\geq 1\end{cases}}

+ y

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

1

displaystyle f(x,y)}={\begin}1&x^{2}+y^{2

}<

1\\0&x^{2}+y^{2}\geq 1\end{case}}}}}}}}}}}}}

위의 그림으로부터 제안된 알고리즘을 사용하여 단위 사각형 안에 통합되었다. 샘플링된 점들은 기록되고 플롯되었다. 명확히 층화된 표본 추출 알고리즘은 함수의 변동이 가장 큰 지역의 점을 집중시킨다.

재귀성 층화 표본 추출은 1차원 적응형 쿼드러처를 다차원 통합에 일반화한 것이다. 각 재귀 단계에서 적분과 오차는 일반 몬테카를로 알고리즘을 사용하여 추정한다. 오류 추정치가 필요한 정확도보다 클 경우 통합 볼륨은 하위 볼륨으로 분할되고 절차는 하위 볼륨에 재귀적으로 적용된다.

서브볼륨의 수가 너무 빨리 증가하여 추적할 수 없기 때문에 일반적인 '2로 나누기' 전략은 다중 디멘션에는 효과가 없다. 대신에 어떤 차원을 따라 하위분할이 가장 많은 배당을 가져와야 하고 이 차원을 따라 볼륨만 세분화해야 하는지를 추정한다.

계층화된 샘플링 알고리즘은 함수의 분산이 가장 큰 지역에 샘플링 포인트를 집중시켜 그림에서 보듯이 대분산을 줄이고 샘플링을 더욱 효과적으로 만든다.

인기 있는 MIRZI 루틴은 유사한 알고리즘을 구현한다.

MIZR 몬테 카를로

MIRZI 알고리즘은 재귀성 층화 표본 추출에 기초한다. 이 기법은 분산이 가장 높은 지역에 통합 지점을 집중시킴으로써 전체 통합 오류를 줄이는 것을 목적으로 한다.^[7]

The idea of stratified sampling begins with the observation that for two disjoint regions a and b with Monte Carlo estimates of the integral $E_{a}(f)$ and $E_{b}(f)$ and variances $\sigma _{a}^{2}(f)$ and ${\displa$ $ystyle \sigma _{b}^{2}(f)}$ , 결합된 추정치의 분산 Var(f)

E(f)={\tfrac {1}{1}:{2}}\왼쪽(E_{a}(f)+E_{b}(f)\오른쪽)

에 의해 주어진다,

\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}{a}}+\sigma _{b}}}}}}}}}}}}

따라서 각 하위 영역에서 함수의 표준 편차에 비례하여 표본 점을 할당하여 가장 작은 오차 추정치를 구한다.

MIZR 알고리즘은 각 단계에서 두 개의 하위 영역을 부여하기 위해 하나의 좌표 축을 따라 통합 영역을 이등분하여 진행한다. 방향은 가능한 모든 분산을 검사하고 두 하위 영역의 결합 분산을 최소화하는 분산을 선택하여 선택한다. 하위 영역의 분산은 현재 단계에서 사용할 수 있는 총 점 수의 일부분으로 표본 추출하여 추정한다. 그런 다음 가장 좋은 이분법에서 두 개의 반공간 각각에 대해 동일한 절차를 반복적으로 반복한다. 나머지 샘플 포인트는 N과_a N의_b 공식을 사용하여 하위 영역에 할당된다. 이러한 통합 지점의 재귀적 할당은 각 하위 영역이 일반 몬테카를로 추정치를 사용하여 통합되는 사용자 지정 깊이까지 계속된다. 그런 다음 이러한 개별 값과 오차 추정치를 위로 결합하여 전체 결과와 오차의 추정치를 제공한다.

중요도 샘플링

중요도 샘플링 알고리즘은 다음과 같이 다양하다.

중요도 샘플링 알고리즘

중요도 샘플링은 몬테카를로 통합을 수행하는 데 매우 중요한 도구를 제공한다.^[3]^[8] 이 방법에 대한 중요도 샘플링의 주요 결과는 보다 $일반적$ 인 선택 사례로 $\overline {{\mathbf {x}}}$ $,$ 표본이 분포 $p({\overline {\mathbf {x} }})$ ( $p({\overline {\mathbf {x} }})$ " $x$ $"){\displaystyle$ p $({\overline {\mathbf {x}}}}}}$ 에서 추출된다 $p({\overline {\mathbf {x} }})$ $'''){\displaystyle p({\overline {\mathbf{x}}}}}$ 을(를) 선택하여 측정 Q의_N 분산을 줄일 수 있다는 $p({\overline {\mathbf {x} }})$ 생각이다.

0에서 0 = 1, -1000에서 -1000까지를 중심으로 가우스 함수를 숫자적으로 통합하려는 경우 다음 예를 고려해 보십시오. 당연히 표본이 [-1000, 1000] 간격으로 균일하게 그려지는 경우, 그 중 극히 일부만이 적분에게 유의미할 것이다. 이는 예를 들어 0을 중심으로 한 가우스 분포에 따라 표본을 추출하는 경우와 같이 표본을 선택하는 장소와 다른 분포를 선택함으로써 개선할 수 있다. 물론 "올바른" 선택은 통합체에 따라 강하게 좌우된다.

공식적으로는 분포에서 선택한 표본 집합이 주어진다.

p({\overline {\mathbf {x} }}}}}}):\qquad {\mathbf {x}{1},\cdots,{\overline {\mathbf {x}}}}}V,}

I에 대한 추정자는 에 의해^[3] 주어진다.

Q_{N}\equiv {\frac {1}{{N}\sum _{i=1}^{N}{\frac {f({\overline {\mathbf{x}}}}}}}{p)({\overline {\mathbf{}}}}}}{i}})}}

직관적으로 이것은 우리가 특정 샘플을 다른 샘플보다 2배 더 많이 고르면, 우리는 다른 샘플보다 절반의 무게를 잰다고 말한다. $p({\overline {\mathbf {x} }})$ 추정기는 $p({\overline {\mathbf {x} }})$ ( x $){\displaystyle$ p $({\overline {\mathbf{x}}}}}}$ 이(가) 일정한 경우 당연히 $p({\overline {\mathbf {x} }})$ 균일한 샘플링에 유효하다.

Metropolitan-Hastings 알고리즘은 p $p({\overline {\mathbf {x} }})$ ( x $){\$ $displaystyle {\overline {\mathbf{x$ $p({\overline {\mathbf {x} }})$ ^[3]에서 $\overline {{\mathbf {x}}}$ ${\overline {\mathbf {x} }}$ $¯($ $p({\overline {\mathbf {x} }})$ ){\ $displaystyle p({\overline {\mathbf {x}}})$ 를 생성하기 위해 가장 많이 사용되는 알고리즘 중 하나이다.

베가스 몬테카를로

VEGAS 알고리즘은 f함수의 히스토그램을 생성하는 통합 영역을 여러 번 통과함으로써 정확한 분포를 근사하게 된다. 각 히스토그램은 다음 통과에 대한 표본 분포를 정의하는 데 사용된다. 점증적으로 이 절차는 원하는 분포로 수렴된다.^[9] K처럼^d 증가하는 히스토그램 빈의 수를 피하기 위해 확률 분포는 분리 가능한 함수에 의해 근사치된다.

g(x_{1},x_{2},\ldots )=g_{1}(x_{1}}g_{2}(x_{2})\ldots }

필요한 빈의 수가 Kd에 불과하도록 한다. 이는 통합의 투영에서 좌표 축으로 함수의 피크를 찾는 것과 같다. 베가스의 효율성은 이 가정의 타당성에 달려있다. 통합의 정점이 잘 현지화될 때 가장 효율적이다. 만약 통합이 거의 분리 가능한 형태로 다시 작성될 수 있다면, 이것은 라스베가스와의 통합의 효율성을 증가시킬 것이다. 베가스는 많은 추가적인 특징들을 포함하며, 층화된 샘플링과 중요도 샘플링을 모두 결합한다.^[9]

참고 항목

메모들

^ 2007년 4월 4일 기자 회견
^ 2007년 7월 7일 기자 회견
^ ^a ^b ^c ^d 1999년 뉴먼 2세
^ 뉴먼, 1999년 1차장
^ 2007년 프레스 외
^ MacKay, David (2003). "chapter 4.4 Typicality & chapter 29.1" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. ISBN 978-0-521-64298-9. MR 2012999.
^ 프레스, 1990, 페이지 190-195.
^ Kroese, D. P.; Taimre, T.; Botev, Z. I. (2011). Handbook of Monte Carlo Methods. John Wiley & Sons.
^ ^a ^b 1978년 르페이지

참조

Caflisch, R. E. (1998). "Monte Carlo and quasi-Monte Carlo methods". Acta Numerica. 7: 1–49. Bibcode:1998AcNum...7....1C. doi:10.1017/S0962492900002804. S2CID 5708790.
Weinzierl, S. (2000). "Introduction to Monte Carlo methods". arXiv:hep-ph/0006269.
Press, W. H.; Farrar, G. R. (1990). "Recursive Stratified Sampling for Multidimensional Monte Carlo Integration". Computers in Physics. 4 (2): 190. Bibcode:1990ComPh...4..190P. doi:10.1063/1.4822899.
Lepage, G. P. (1978). "A New Algorithm for Adaptive Multidimensional Integration". Journal of Computational Physics. 27 (2): 192–203. Bibcode:1978JCoPh..27..192L. doi:10.1016/0021-9991(78)90004-9.
Lepage, G. P. (1980). "VEGAS: An Adaptive Multi-dimensional Integration Program". Cornell Preprint CLNS 80-447.
Hammersley, J. M.; Handscomb, D. C. (1964). Monte Carlo Methods. Methuen. ISBN 978-0-416-52340-9.
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.
Newman, MEJ; Barkema, GT (1999). Monte Carlo Methods in Statistical Physics. Clarendon Press.
Robert, CP; Casella, G (2004). Monte Carlo Statistical Methods (2nd ed.). Springer. ISBN 978-1-4419-1939-7.

외부 링크

카페 수학 : 몬테카를로 통합 : 몬테카를로 통합을 기술한 블로그 기사 (원칙, 가설, 신뢰구간)
부스트.수학: 순진한 몬테카를로 통합: C+++ 순진한 몬테카를로 루틴에 대한 문서화
통계 물리학 문제에 적용된 몬테카를로 애플릿

[1] 2007년 4월 4일 기자 회견

[2] 2007년 7월 7일 기자 회견

[newman1999ch2-3] 1999년 뉴먼 2세

[newman1999ch1-4] 뉴먼, 1999년 1차장

[5] 2007년 프레스 외

[6] MacKay, David (2003). "chapter 4.4 Typicality & chapter 29.1" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. ISBN 978-0-521-64298-9. MR 2012999.

[7] 프레스, 1990, 페이지 190-195.

[kr11-8] Kroese, D. P.; Taimre, T.; Botev, Z. I. (2011). Handbook of Monte Carlo Methods. John Wiley & Sons.

[Lepage,_1978-9] 1978년 르페이지

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search