몬테카를로 방법

위키백과, 우리 모두의 백과사전.

몬테카를로 방법(Monte Carlo method) (또는 몬테카를로 실험)은 반복된 무작위 추출(repeated random sampling)을 이용하여 함수의 값을 수리적으로 근사하는 알고리즘을 부르는 용어이다. 수학이나 물리학 등에 자주 사용되며, 계산하려는 값이 닫힌 형식으로 표현되지 않거나 복잡한 경우에 근사적으로 계산할 때 사용된다. 몬테카를로 방법은 주로 확률 분포에서 확률 변수값을 생성하는 작업, 수학적 최적화, 수치적분 등에서 활용된다.[1] 알고리즘의 반복과 큰 수의 계산이 관련되기 때문에 몬테카를로 방법은 다양한 컴퓨터 모의 실험 기술을 사용하여 컴퓨터로 계산하는 것이 적합하다.

엔리코 페르미중성자의 특성을 연구하기 위해 이 방법을 사용한 것으로 유명하다. 맨해튼 계획의 시뮬레이션이나 수소폭탄의 개발에서도 핵심적인 역할을 담당하였다. 몬테카를로(Monte Carlo)라는 용어 또한 맨해튼 계획에 참여하고 있던 니콜라스 메트로폴리스맨해튼 계획이 끝나가던 1947년에 제안한 이름이다.[2] 맨해튼 계획 당시 그의 동료였던 폴란드 출신 수학자 스타니스와프 울람에게는 삼촌이 있었는데, 그는 모나코의 유명한 도박의 도시 몬테카를로에서 도박을 하기 위해 친척들의 돈을 종종 빌려갔다. 몬테카를로 방법 또한 무작위성이 있으므로 이로부터 이름이 유래된 것이 지금까지 이어져 내려왔다.

물리 문제에서 몬테카를로 방법은 유체, 무질서한 물질, 강하게 결합한 고체 및 세포 구조와 같은 많은 결합 자유도를 가진 시스템을 모의실험하는 데 유용하다. 그 밖의 예로는 사업의 위험성 계산과 같은 입력 값에 상당한 불확실성이 있는 모델링 현상과, 수학에서는 복잡한 경계 조건을 가진 다차원의 정적분이 있다. 우주, 석유 탐사, 항공기 설계 등의 시스템 엔지니어링 문제에 적용할 경우, 실패, 비용 초과 및 스케줄 초과에 대한 몬테카를로 방법 기반의 예측은 많은 경우 인간의 직관 또는 수리적인 계산이 적은 다른 대안들보다 나은 결과를 가져온다.[3]

대체적으로, 몬테카를로 방법은 확률론적 해석을 가진 문제를 해결하기 위해 사용될 수 있다. 큰 수의 법칙에 의해, 어떤 확률 변수기댓값으로 설명되는 적분랜덤표본(random sample)의 표본 평균을 취함으로써 근사치를 구할 수 있다. 변수의 확률 분포가 매개변수로 표현 가능할 때는 주로 마르코프 연쇄 몬테카를로(MCMC) 샘플러를 사용한다.[4][5][6] MCMC 방법에 의해 생성되는 표본의 극한 분포는 원하는 (목표) 분포의 표본이 될 것이기 때문에 핵심 아이디어는 잘 규정된 정상(stationary) 확률 분포를 가진 마르코프 연쇄 모델을 설계하는 것이다.[7][8] 에르고딕 정리에 의해, 정상(stationary) 확률 분포는 MCMC 샘플러의 무작위 상태의 경험적 측도에 의해 근사된다.

다른 문제에서의 목표는 비선형 발전 방정식(evolution equation)을 만족시키는 일련의 확률 분포에서 표본을 뽑는 것이다. 이러한 확률 분포의 흐름은 변환 확률이 현재 무작위 상태의 분포에 따라 달라지는 마르코프 연쇄의 무작위 상태의 분포로 항상 해석될 수 있다. (McKean – Vlasov 프로세스, 비선형 필터링 방정식 참조).[9][10] 다른 경우에는 시간 지평선이 증가하는 경로 공간 모델, 온도 매개변수 감소와 관련된 Boltzmann – Gibbs 측도 등 표본 복잡도가 증가하는 확률 분포의 흐름이 주어진다. 이 모델들은 비선형 마르코프 연쇄의 무작위 상태의 법칙이 발전된 것으로도 볼 수 있다.[11][12] 이러한 정교한 비선형 마르코프 연쇄시뮬레이션하는 자연스러운 방법은 해당 마르코프 연쇄의 많은 사본을 표집하여 발전 방정식(evolution equation)에서 무작위 상태의 알 수 없는 분포를 표본의 경험적 측도로 대체하는 것이다. 전통적인 몬테카를로 및 MCMC 방법과는 대조적으로, 이러한 평균-장 입자 방법은 순차적으로 상호작용하는 표본들에 의존한다. 평균-장이라는 용어는 각 표본(예: 입자, 개인, 보행자, 대리인, 생물 또는 표현형)이 마르코프 연쇄경험적 측도과 상호작용한다는 사실을 반영한다. 시스템의 크기가 무한대로 발산할 때, 이러한 무작위 경험적 측도는 비선형 마르코프 연쇄의 무작위 상태의 결정론적 분포로 수렴하여 입자 사이의 통계적 상호작용이 사라진다.

예제[편집]

몬테카를로 방법으로 원주율을 계산하는 과정

몬테카를로 방법은 다양하지만, 특정한 패턴을 따르는 경향이 있다.

1.    표본 공간의 값으로 가능한 범위를 정의한다.

2.    표본 공간의 확률 분포에서 임의로 표본을 뽑는다. (표집한다.)

3.    표본에 대한 결정론적인 계산을 수행한다.

4.    결과를 집계한다.

예를 들어 단위 정사각형에 새겨진 사분원(원형 부분)을 생각해 보자. 몬테카를로 방법을 사용해서 의 값을 근사치로 추정할 수 있다.[13]

1.    정사각형을 그린 다음, 그 안에 사분원을 삽입한다.

2.    정사각형 위에 일정한 개수의 점을 균일하게 분포한다.

3.    사분원 내부의 점(즉, 원점으로부터 1 미만)의 개수를 센다.

4.    내부의 개수와 전체 개수의 비율은 두 영역의 비율을 나타낸다. 그 값에 4를 곱하여 를 만든다.

여기서 두 가지의 중요한 점이 있다.

1.    점이 균일하게 분포되지 않으면 근사치가 떨어진다.

2.    평균적으로 더 많은 점을 배치할수록 근사치가 개선된다.

다음은 원주율을 계산하는 몬테카를로 알고리즘의 한 예시이다.

  • 에서 점 표집한다.
  • 표집한 점이 중심이 에 있고 반지름이 1인 원에 속하는지 계산한다. 이는 원의 정의에 따라 와 1을 비교함으로써 계산할 수 있다.
  • 위의 두 과정을 충분히 반복하여, 원에 속한 점들의 개수를 계산한다.

표집 영역과 원의 공통 영역은 의 넓이를 가지며, 원에 속한 점 개수를 전체 점 개수로 나눈 비율은 를 근사한다.

같이 보기[편집]

참고문헌[편집]

인용[편집]

  1. Kroese, D. P.; Brereton, T.; Taimre, T.; Botev, Z. I. (2014). “Why the Monte Carlo method is so important today”. 《WIREs Comput Stat》 6 (6): 386–392. doi:10.1002/wics.1314. 
  2. Metropolis, N. (1987). “The beginning of the Monte Carlo method” (PDF). 《Los Alamos Science》 (1987 Special Issue dedicated to Stanislaw Ulam): 125–130. 
  3. Hubbard, Douglas; Samuelson, Douglas A. (October 2009). “Modeling Without Measurements”. 《OR/MS Today》: 28–33. 
  4. Metropolis, Nicholas; Rosenbluth, Arianna W.; Rosenbluth, Marshall N.; Teller, Augusta H.; Teller, Edward (1953년 6월 1일). “Equation of State Calculations by Fast Computing Machines”. 《The Journal of Chemical Physics》 21 (6): 1087–1092. Bibcode:1953JChPh..21.1087M. doi:10.1063/1.1699114. ISSN 0021-9606. OSTI 4390578. 
  5. Hastings, W. K. (1970년 4월 1일). “Monte Carlo sampling methods using Markov chains and their applications”. 《Biometrika》 57 (1): 97–109. Bibcode:1970Bimka..57...97H. doi:10.1093/biomet/57.1.97. ISSN 0006-3444. 
  6. Liu, Jun S.; Liang, Faming; Wong, Wing Hung (2000년 3월 1일). “The Multiple-Try Method and Local Optimization in Metropolis Sampling”. 《Journal of the American Statistical Association》 95 (449): 121–134. doi:10.1080/01621459.2000.10473908. ISSN 0162-1459. 
  7. Spall, J. C. (2003). “Estimation via Markov Chain Monte Carlo”. 《IEEE Control Systems Magazine》 23 (2): 34–45. doi:10.1109/MCS.2003.1188770. 
  8. Hill, Stacy D.; Spall, James C. (2019). “Stationarity and Convergence of the Metropolis-Hastings Algorithm: Insights into Theoretical Aspects”. 《IEEE Control Systems Magazine》 39: 56–67. doi:10.1109/MCS.2018.2876959. 
  9. Kolokoltsov, Vassili (2010). 《Nonlinear Markov processes》. Cambridge Univ. Press. 375쪽. 
  10. Del Moral, Pierre (2013). 《Mean field simulation for Monte Carlo integration》. Chapman & Hall/CRC Press. 626쪽. Monographs on Statistics & Applied Probability 
  11. Del Moral, Pierre (2013). 《Mean field simulation for Monte Carlo integration》. Chapman & Hall/CRC Press. 626쪽. Monographs on Statistics & Applied Probability 
  12. Del Moral, P; Doucet, A; Jasra, A (2006). “Sequential Monte Carlo samplers”. 《Journal of the Royal Statistical Society, Series B》 68 (3): 411–436. arXiv:cond-mat/0212648. doi:10.1111/j.1467-9868.2006.00553.x. 
  13. Kalos & Whitlock 2008.

출처[편집]