몬테카를로 방법

3. 수치 적분

몬테카를로 방법은 수치 적분에 유용하게 사용된다. 특히 함수가 많은 변수를 가질 때 발생하는 차원의 저주 문제를 해결하는 데 효과적이다.

• 반데르코르프 수열^[97]
• Halton sequence|할턴 수열^영어[98]
• Sobol sequence|소볼 수열^영어[99]
• 니더라이터 수열^[100]
• 포르 수열^[101]

3. 1. 몬테카를로 적분 예제

4. 강화 학습

기계 학습의 강화 학습에서 몬테카를로 방법은 경험을 통해 얻은 보상만을 바탕으로 상태 가치와 행동 가치를 추정하는 방법이다.^[102]

5. 통계학

통계학에서 몬테카를로 실험의 기준은 사윌로스키에 의해 정립되었다.^[68] 응용 통계학에서 몬테카를로 방법은 적어도 네 가지 목적으로 사용될 수 있다.

# 현실적인 데이터 조건에서 소표본에 대한 경쟁 통계량을 비교한다. 통계량의 제1종 오류와 검정력 특성은 고전적인 이론적 분포(예: 정규 분포, 코시 분포)에서 추출된 데이터에 대해 점근 조건(즉, 무한대 표본 크기 및 무한소 처리 효과)에서 계산할 수 있지만, 실제 데이터는 종종 이러한 분포를 갖지 않는다.^[69]

# 가설 검정에 대한 구현을 제공하는데, 이는 순열 검정과 같은 정확한 검정(계산이 불가능한 경우가 많음)보다 효율적이며, 점근 분포에 대한 임계값보다 더 정확하다.

# 베이즈 추론에서 사후 분포로부터의 무작위 표본을 제공한다. 이 표본은 사후 분포의 모든 필수 특징을 근사하고 요약한다.

# 피셔 정보 행렬의 추정치를 형성하기 위해 평균화될 수 있는 음의 로그-우도 함수의 헤시안 행렬의 효율적인 무작위 추정치를 제공한다.^[70][71]

몬테카를로 방법은 근사 무작위화와 순열 검정 사이의 타협점이기도 하다. 근사 무작위화 검정은 모든 순열의 지정된 부분 집합을 기반으로 한다(이는 어떤 순열이 고려되었는지에 대한 잠재적으로 엄청난 관리 작업이 필요하다). 몬테카를로 접근 방식은 지정된 수의 무작위로 추출된 순열을 기반으로 한다(순열이 두 번 이상 추출되는 경우 정밀도의 약간의 손실을 순열이 이미 선택되었는지 추적할 필요가 없는 효율성으로 교환한다).

통계학에서의 몬테카를로 방법의 하나로, 부트스트랩이 있다.

6. 난수(열)의 선택

몬테카를로 방법의 결과는 사용하는 난수의 품질에 크게 의존한다. 따라서 상황에 맞는 난수열을 선택하는 것이 중요하다.

• 의사 난수열: 의사 난수는 초기 상태에 따라 이후의 모든 수열이 결정되므로, 엄밀히 말해 "진정한 난수"는 아니다. 하지만 시뮬레이션에서는 재현 가능하다는 중요한 특징이 있다. 즉, 같은 초기 조건에서 동일한 결과를 얻을 수 있다.
• 물리 난수: 진정한 난수가 필요하거나, 의사 난수열 생성기의 초기 상태를 설정하기 위해 양질의 난수가 필요한 경우, 물리 현상을 이용하는 물리 난수(진성 난수)를 생성하는 하드웨어를 사용한다. 예를 들어, 다이오드의 PN 접합부에서 발생하는 열 잡음을 이용하거나, 방사성 원소를 사용할 수 있다.
• 초일양 분포열: 규칙성이 강한 수열로, 수치 적분에 사용된다.^[103] 초일양 분포열을 사용하는 몬테카를로 방법을 준 몬테카를로 방법이라고 한다. 초일양 분포열은 '''저분산 수열''' 또는 '''준난수열'''^[104]이라고도 불린다. 초일양 분포열을 수치 적분에 사용하면 정확도를 높일 수 있다.

7. 정밀도

몬테카를로 방법의 정밀도는 표본 크기에 따라 달라지며, 일반적으로 표본 크기가 커질수록 정밀도가 향상된다. 점이 균일하게 분포되지 않으면 근사치가 떨어지지만, 평균적으로 더 많은 점을 배치할수록 근사치가 개선된다.

원하는 신뢰 수준을 선택하고, z를 해당 신뢰 수준에 해당하는 ''z''-점수라고 할 때, ''s''²를 추정 분산("표본" 분산)이라고 하며, 다음 식으로 표현된다.

:$n\backslash geq\; s^2\; /(z\backslash epsilon)^2$^[11][12]

''n'' ≤ ''k''이면, ''m_k'' = m'';'' 충분한 표본 시뮬레이션이 수행되어 ''m_k''가 ''μ''의 ''ε'' 이내에 있는지 확인되었다. 만약 ''n'' > ''k''이면, "처음부터" ''n''개의 시뮬레이션을 실행하거나, k개의 시뮬레이션이 이미 수행되었으므로 ''n'' – ''k''개의 시뮬레이션을 더 실행하고 그 결과를 표본 시뮬레이션의 결과에 추가할 수 있다.

개념적, 알고리즘적으로 단순함에도 불구하고, 몬테카를로 시뮬레이션과 관련된 계산 비용은 매우 높을 수 있다. 일반적으로 좋은 근사치를 얻기 위해 많은 표본이 필요하며, 단일 표본의 처리 시간이 길 경우 임의로 큰 총 실행 시간이 소요될 수 있다.^[13] 이는 매우 복잡한 문제에서 심각한 제약이 되지만, 이 알고리즘의 병렬 처리 특성으로 인해 지역 프로세서, 클러스터, 클라우드 컴퓨팅, GPU, FPGA 등에서 병렬 컴퓨팅 전략을 통해 이러한 막대한 비용을 줄일 수 있다(아마도 실행 가능한 수준으로).^{[14][15][16][17]}

확률론에 따르면 몬테카를로 방법에 의한 수치 적분의 정밀도는 샘플 사이즈 ''N''을 늘리면 대부분의 경우에 좋아진다. 샘플이 진정한 무작위 난수열인 경우, 몬테카를로 방법으로 얻을 수 있는 적분의 근사값의 참값으로부터의 오차는 다음과 같다.

: $|\; I\; -\; I\_N\; |\backslash ,$

샘플 사이즈 ''N''을 한없이 증대시키면 거의 확실히 0에 수렴한다(대수의 법칙). 이 수렴 속도에 관해서는 다음과 같다.

:

이는 Law of the iterated logarithm|반복 로그 법칙^영어에 따른 것이다. 즉, 오차의 크기를 10분의 1배로 줄이기 위해서는 샘플 수 ''N''을 100배로 늘릴 필요가 있다.

이에 대해, 어떤 준 몬테카를로 방법에서는 적분 변수의 수를 ''n''이라고 할 때, 다음과 같다.

:

따라서 오차의 크기를 10분의 1배로 줄이기 위해서는 샘플 수 ''N''을 약 10배로 늘리는 것만으로 충분하다. 이것이 준 몬테카를로 방법을 사용하는 이점이다.^[103] 단, 고차원 적분을 수행하는 경우에는 차원의 수 ''n''이 크므로 효과가 감소하여, 단순한 몬테카를로 방법이 더 좋은 결과를 제공하는 경우가 많다.

8. 응용 분야

몬테카를로 방법은 불확실성이 크거나 복잡한 시스템을 모델링하는 데 유용하며, 과학, 공학, 금융, 게임 등 다양한 분야에서 활용된다.

• 물리학: 전산 물리학, 물리 화학 등에서 열 차폐, 공기 역학 형태 설계, 방사선 재료 과학 등 다양한 분야에 응용된다.
• 공학: 민감도 분석 및 확률적 정량적 공정 설계 분석에 널리 사용된다.
• 금융 및 비즈니스: 금융 분야의 몬테카를로 방법은 사업 투자 분석, 프로젝트 관리, 옵션 가격 결정, 채무 불이행 위험 분석 등 다양한 분야에서 활용된다.
• 게임 인공지능: 몬테카를로 트리 탐색은 바둑과 같은 게임에서 최적의 수를 찾는 데 사용되는 기술이다.
• 기타: 전역 조명 계산, 미국 해안 경비대의 수색 및 구조 작전, 법률, 도서 출판 등 다양한 분야에 응용된다.

8. 1. 물리학

8. 2. 공학

• 마이크로 전자 공학에서 몬테카를로 방법은 아날로그 신호 및 디지털 데이터 집적 회로의 상관 및 비상관 변화를 분석하는 데 사용된다.
• 지질 통계학 및 지질 금속학에서 몬테카를로 방법은 광물 처리 흐름도 설계를 뒷받침하고 정량적 위험 분석에 기여한다.^[2]
• 유체 역학, 특히 희박 기체 역학에서 몬테카를로 방법은 직접 시뮬레이션 몬테카를로^[64] 방법을 고효율 계산 알고리즘과 결합하여 유한한 누센 수 유체 흐름에 대한 볼츠만 방정식을 푸는 데 사용된다.^[65]
• 자율 로봇에서 몬테카를로 국소화는 로봇의 위치를 결정할 수 있다. 이는 종종 칼만 필터 또는 입자 필터와 같은 확률적 필터에 적용되며, 이는 SLAM (동시적 위치 추정 및 지도 작성) 알고리즘의 핵심을 형성한다.
• 통신에서 무선 네트워크를 계획할 때, 설계는 주로 사용자 수, 위치 및 사용하려는 서비스에 따라 달라지는 다양한 시나리오에서 작동함을 입증해야 한다. 몬테카를로 방법은 일반적으로 이러한 사용자와 해당 상태를 생성하는 데 사용된다. 그런 다음 네트워크 성능을 평가하고, 결과가 만족스럽지 않으면 네트워크 설계는 최적화 프로세스를 거친다.
• 신뢰성 공학에서 몬테카를로 시뮬레이션은 구성 요소 수준의 응답을 바탕으로 시스템 수준의 응답을 계산하는 데 사용된다.
• 신호 처리 및 베이즈 추론에서 입자 필터 및 순차적 몬테카를로 기법은 상호 작용하는 경험적 측정을 사용하여 일부 시끄럽고 부분적인 관찰이 주어질 때 신호 프로세스의 사후 분포를 샘플링하고 계산하기 위한 평균장 입자 방법의 한 종류이다.^[66]

8. 3. 금융 및 비즈니스

8. 4. 게임 인공지능

8. 5. 기타 응용 분야

• 경로 추적은 가능한 광선 경로의 무작위 표본을 추적하여 3D 장면을 렌더링한다. 주어진 픽셀을 반복적으로 샘플링하면 결국 샘플의 평균이 렌더링 방정식의 올바른 해로 수렴하여 현존하는 가장 물리적으로 정확한 3D 그래픽 렌더링 방법 중 하나가 된다.
• 전역 조명 계산에 사용되어, 비디오 게임, 건축, 디자인, 컴퓨터 생성 영화 및 영화 특수 효과에 적용되는 가상 3D 모델의 사실적인 이미지를 생성한다.
• 미국 해안 경비대는 수색 및 구조 작전 중 선박의 예상 위치를 계산하기 위해 컴퓨터 모델링 소프트웨어 SAROPS 내에서 몬테카를로 방법을 사용한다. 각 시뮬레이션은 제공된 변수를 기반으로 무작위로 분포된 최대 10,000개의 데이터 포인트를 생성할 수 있다.^[79] 그런 다음 이러한 데이터의 외삽을 기반으로 수색 패턴이 생성되어 포괄 확률(POC) 및 탐지 확률(POD)을 최적화하며, 이 둘을 합하면 전체 성공 확률(POS)이 된다. 이는 확률 분포의 실제 적용으로, 인명과 자원을 모두 절약하면서 가장 신속하고 효율적인 구조 방법을 제공한다.^[80]
• 위스콘신 주의 여성 청원인들이 괴롭힘 및 가정 폭력 신청에서 성공할 수 있도록 돕는 제안된 프로그램의 잠재적 가치를 평가하는 데 사용되었다. 이 프로그램은 여성들에게 더 나은 옹호를 제공하여 청원 성공을 돕고, 그 결과 강간 및 폭행의 위험을 줄이는 것을 목표로 했다. 그러나 금지 명령의 효과, 옹호 유무에 따른 청원인의 성공률 등 완벽하게 추정할 수 없는 많은 변수가 존재했다. 이 연구에서는 이러한 변수를 다양하게 변화시키는 실험을 진행하여 제안된 프로그램 전체의 성공 수준에 대한 전반적인 추정치를 도출했다.^[85]
• 말레이시아의 도서 장르에 따른 도서 출판 수 시뮬레이션에도 사용되었다. 몬테카를로 시뮬레이션은 이전의 출판된 전국 도서 출판 데이터와 현지 시장의 도서 장르별 도서 가격을 활용했다. 몬테카를로 결과는 말레이시아인들이 어떤 종류의 도서를 좋아하는지 결정하는 데 사용되었으며, 말레이시아와 일본 간의 도서 출판을 비교하는 데 사용되었다.^[86]

참조

_[1] 논문 Why the Monte Carlo method is so important today
_[2] 논문 Modeling Without Measurements http://viewer.zmags.[...] 2009-10
_[3] 논문 Equation of State Calculations by Fast Computing Machines 1953-06-01
_[4] 논문 Monte Carlo sampling methods using Markov chains and their applications 1970-04-01
_[5] 논문 The Multiple-Try Method and Local Optimization in Metropolis Sampling 2000-03-01
_[6] 논문 Estimation via Markov Chain Monte Carlo
_[7] 논문 Stationarity and Convergence of the Metropolis-Hastings Algorithm: Insights into Theoretical Aspects
_[8] 서적 Nonlinear Markov processes Cambridge University Press
_[9] 서적 Mean field simulation for Monte Carlo integration http://www.crcpress.[...] Chapman & Hall/[[CRC Press]]
_[10] 논문 Sequential Monte Carlo samplers
_[11] 서적 Monte Carlo Theory, Methods and Examples https://artowen.su.d[...] Work in progress 2013
_[12] 논문 Determining the number of Iterations for Monte Carlo Simulations of Weapon Effectiveness https://apps.dtic.mi[...] 2004-04
_[13] 서적 Explorations in Monte Carlo Methods Springer
_[14] 논문 On the parallelization approaches for Intel MIC architecture
_[15] 논문 Uncertainty quantification through the Monte Carlo method in a cloud computing setting
_[16] 논문 A GPU-based parallelized Monte-Carlo method for particle coagulation using an acceptance–rejection strategy
_[17] 논문 Random number generators for large-scale parallel Monte Carlo simulations on FPGA
_[18] 논문 Los Alamos Bets on ENIAC: Nuclear Monte Carlo Simulations, 1947-1948 https://ieeexplore.i[...] 2014
_[19] 논문 Propagation of chaos for a class of non-linear parabolic equations
_[20] 논문 A class of Markov processes associated with nonlinear parabolic equations
_[21] 논문 Estimation of particle transmission by random sampling https://dornsifecms.[...]
_[22] 논문 Computing machinery and intelligence
_[23] 논문 Esempi numerici di processi di evoluzione
_[24] 논문 Symbiogenetic evolution processes realized by artificial methods
_[25] 서적 Feynman–Kac formulae. Genealogical and interacting particle approximations https://www.springer[...] Springer
_[26] 서적 Séminaire de Probabilités XXXIV http://www.numdam.or[...] Springer
_[27] 논문 A Moran particle system approximation of Feynman–Kac formulae.
_[28] 논문 Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman–Kac semigroups http://journals.camb[...] 2003
_[29] 논문 Diffusion Monte Carlo Methods with a fixed number of walkers http://qmcchem.ups-t[...] 2000
_[30] 논문 Comment on Feynman–Kac Path-Integral Calculation of the Ground-State Energies of Atoms 1993
_[31] 논문 Observations on the statistical iteration of matrices 1984
_[32] 논문 Note on census-taking in Monte Carlo calculations http://scienze-como.[...] 1948
_[33] 논문 Monte-Carlo calculations of the average extension of macromolecular chains 1955
_[34] 논문 Novel approach to nonlinear/non-Gaussian Bayesian state estimation 1993-04
_[35] 논문 Monte carlo filter and smoother for non-Gaussian nonlinear state space models
_[36] 논문 Non Linear Filtering: Interacting Particle Solution. https://web.archive.[...] 1996
_[37] 논문 Optimal Non-linear Filtering in GPS/INS Integration. https://web.archive.[...] 1997-07
_[38] 간행물 "Estimation and nonlinear optimal control: An unified framework for particle solutions" LAAS-CNRS, Toulouse 1991-04
_[39] 간행물 "Nonlinear and non Gaussian particle filters applied to inertial platform repositioning." LAAS-CNRS, Toulouse 1991-09
_[40] 간행물 "Estimation and nonlinear optimal control: Particle resolution in filtering and estimation: Experimental results" 1992-01
_[41] 간행물 "Estimation and nonlinear optimal control: Particle resolution in filtering and estimation: Theoretical results" 1992-10
_[42] 간행물 "Particle filters in radar signal processing: detection, estimation and air targets recognition" LAAS-CNRS, Toulouse 1992-12
_[43] 간행물 "Estimation and nonlinear optimal control: Particle resolution in filtering and estimation". Studies on: Filtering, optimal control, and maximum likelihood estimation. 1993-01
_[44] 논문 Measure Valued Processes and Interacting Particle Systems. Application to Non Linear Filtering Problems http://projecteuclid[...] 1998
_[45] 논문 Convergence of a branching particle method to the solution of the Zakai 1998
_[46] 논문 Nonlinear filtering and measure-valued processes 1997
_[47] 논문 A particle approximation of the solution of the Kushner–Stratonovitch equation 1999
_[48] 논문 Discrete filtering using branching and interacting particle systems http://web.maths.uns[...] 1999
_[49] 논문 On the stability of Measure Valued Processes with Applications to filtering 1999
_[50] 논문 On the stability of interacting processes with applications to filtering and genetic algorithms http://web.maths.uns[...] 2001
_[51] 문서 1987
_[52] 문서 2003
_[53] 문서 2008
_[54] 논문 An efficient sensitivity analysis method for modified geometry of Macpherson suspension based on Pearson Correlation Coefficient
_[55] 문서 1992
_[56] 논문 Radio-flaring Ultracool Dwarf Population Synthesis 2017-08-10
_[57] 논문 GPU-based high-performance computing for radiation therapy
_[58] 논문 Advances in kilovoltage x-ray beam dosimetry 2014-03
_[59] 논문 Fifty years of Monte Carlo simulations for medical physics
_[60] 문서 2009
_[61] 논문 Tridyn — A TRIM simulation code including dynamic composition changes 1984-03-01
_[62] 문서 1982
_[63] 문서 1979
_[64] 문서 Molecular Gas Dynamics Clarendon, Oxford 1976
_[65] 논문 A Scalar optimized parallel implementation of the DSMC technique
_[66] 논문 Improvement of generalized finite difference method for stochastic subsurface flow modeling 2021-03-15
_[67] 서적 Climate Change 2013 The Physical Science Basis http://www.climatech[...] Cambridge University Press 2013
_[68] 논문 Simulating confidence for the Ellison-Glaeser Index
_[69] 문서 2003
_[70] 논문 Monte Carlo Computation of the Fisher Information Matrix in Nonstandard Settings
_[71] 논문 Efficient Monte Carlo computation of Fisher information matrix using prior information
_[72] 웹사이트 Monte-Carlo Tree Search: A New Framework for Game AI http://sander.landof[...] 2017-10-28
_[73] 웹사이트 Monte Carlo Tree Search - About https://web.archive.[...] 2013-05-15
_[74] 서적 Computers and Games
_[75] 보고서 Monte-Carlo Tree Search in the game of Tantrix: Cosc490 Final Report https://www.tantrix.[...]
_[76] 웹사이트 Monte-Carlo Planning in Large POMDPs https://web.archive.[...] 2017-10-28
_[77] 서적 Computers and Games
_[78] 웹사이트 Arimaa challenge – comparison study of MCTS versus alpha-beta methods http://www.arimaa.co[...] 2017-10-28
_[79] 웹사이트 How the Coast Guard Uses Analytics to Search for Those Lost at Sea http://insights.dice[...] 2014-01-03
_[80] 웹사이트 Search Modeling and Optimization in USCG's Search and Rescue Optimal Planning System (SAROPS) http://www.ifremer.f[...] 2017-10-28
_[81] 웹사이트 Project Risk Simulation (BETA) https://risk.octigo.[...] 2024-05-21
_[82] 서적 Numerical Methods in Finance Springer Berlin Heidelberg 2012
_[83] 서적 Handbook of Monte Carlo Methods John Wiley & Sons
_[84] 논문 A Monte Carlo simulation approach for estimating the health and economic impact of interventions provided at a student-run clinic
_[85] 웹사이트 Increasing Access to Restraining Orders for Low Income Victims of Domestic Violence: A Cost-Benefit Analysis of the Proposed Domestic Abuse Grant Program https://web.archive.[...] State Bar of Wisconsin 2016-12-12
_[86] 논문 Perbandingan Penerbitan dan Harga Buku Mengikut Genre di Malaysia dan Jepun Menggunakan Data Akses Terbuka dan Simulasi Monte Carlo http://web.usm.my/km[...] 2021-10-29
_[87] 문서 Press, Teukolsky, Vetterling, Flannery, 1996
_[88] 논문 Adaptive umbrella sampling: Self-consistent determination of the non-Boltzmann bias 1986-12-31
_[89] 논문 Probability Distributions for Complex Systems: Adaptive Umbrella Sampling of the Potential Energy 1997-12-31
_[90] 논문 Sequential Monte Carlo samplers
_[91] 문서 Spall, J. C. (2003), Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control, Wiley, Hoboken, NJ. http://www.jhuapl.edu/ISSO
_[92] 문서 Mosegaard, Tarantola, 1995
_[93] 문서 Tarantola, 2005
_[94] 문서 McCracken, D. D., (1955) The Monte Carlo Method, Scientific American, 192(5), pp. 90-97
_[95] 문서 Elishakoff, I., (2003) Notes on Philosophy of the Monte Carlo Method, International Applied Mechanics, 39(7), pp.753-762
_[96] 문서 Grüne-Yanoff, T., & Weirich, P. (2010). The philosophy and epistemology of simulation: A review, Simulation & Gaming, 41(1), pp. 20-50
_[97] 문서 van der Corput sequence
_[98] 문서 Halton sequence
_[99] 문서 Sobol sequence
_[100] 문서 Niederreiter sequence
_[101] 문서 Faure sequence
_[102] 서적 Reinforcement Learning: An Introduction http://incompleteide[...]
_[103] 서적 C言語による最新アルゴリズム事典 技術評論社
_[104] 문서 quasi-random sequence
_[105] 논문 Why the Monte Carlo method is so important today https://semanticscho[...]
_[106] 논문 The beginning of the Monte Carlo method http://library.lanl.[...]
_[107] 논문 Modeling Without Measurements http://viewer.zmags.[...] 2009-10
_[108] 논문 Equation of State Calculations by Fast Computing Machines https://semanticscho[...] 1953-06-01
_[109] 논문 Monte Carlo sampling methods using Markov chains and their applications https://semanticscho[...] 1970-04-01
_[110] 논문 The Multiple-Try Method and Local Optimization in Metropolis Sampling https://semanticscho[...] 2000-03-01
_[111] 논문 Estimation via Markov Chain Monte Carlo
_[112] 논문 Stationarity and Convergence of the Metropolis-Hastings Algorithm: Insights into Theoretical Aspects
_[113] 서적 Nonlinear Markov processes Cambridge Univ. Press
_[114] 서적 Mean field simulation for Monte Carlo integration http://www.crcpress.[...] Chapman & Hall/CRC Press
_[115] 서적 Mean field simulation for Monte Carlo integration http://www.crcpress.[...] Chapman & Hall/CRC Press
_[116] 논문 Sequential Monte Carlo samplers