마르코프 연쇄 몬테카를로

마르코프 연쇄 몬테카를로 방법(Markov chain Monte Carlo, 무작위 행보 몬테 카를로 방법 포함)은 마르코프 연쇄의 구성에 기반한 확률 분포로부터 원하는 분포의 정적 분포를 갖는 표본을 추출하는 알고리즘의 한 부류이다. 큰 수의 단계(step) 이후에 연쇄의 상태는 목표로 하는 분포로부터 추출된 표본처럼 사용될 수 있다. 표본의 품질은 단계 수의 함수로 개선된다. 일반적으로 원하는 특성을 갖는 마르코프 연쇄를 구성하는 것은 어렵지 않다. 보다 어려운 문제는 수용할 만한 오차 범위의 정적 분포로 수렴하는데까지 얼마나 많은 단계가 필요한지를 결정하는 것이다. 좋은 연쇄는 임의의 위치에서부터 시작하여 정적 분포에 빠르게 도달하는 빠른 혼합(mixing)을 가질 것이며, 이에 대해서는 마르코프 연쇄 혼합 시간에서 상세히 설명된다.

MCMC의 전형적인 사용은 목표 분포를 근사하는 것이며, 여기에는 항상 시작 위치로부터의 약간의 잔여 효과(residual effect)가 존재한다.

이 알고리즘의 가장 일반적인 적용 예는 다차원 적분을 수치적으로 계산하는 것이다.

무작위 행보 알고리즘 (Random walk algorithm)

많은 MCMC 방법은 평형 분포(equilibrium distribution) 주위에서 비교적 작은 보폭으로 움직이며, 이 보폭은 동일한 방향으로 진행하려는 경향을 갖지 않는다. 이 방법은 구현하기로 쉽고 분석하기도 쉽지만, 보행자(walker)가 모든 공간을 탐색하는데에는 오랜 시간이 걸린다. 보행자는 종종 왔다갔다 하기도 하고 갔던 곳을 다시 가기도 한다. 다음은 몇가지 무작위 행보 MCMC 방법들이다.

메트로폴리스 해스팅스 알고리즘: 제안된 밀도와 제안된 이동을 거부하는 방법을 이용하여 무작위 행보를 생성한다.
깁스 표집: 목표 분포의 모든 조건 분포가 정확하게 추출되는 것을 필요로 한다. 이 방법은 어떠한 튜닝도 필요하지 않다는 점 때문에 인기가 있다.

무작위 행보를 피하기

좀 더 복잡한 알고리즘은 보행자가 왔다 갔다 하는 것을 방지하기 위해 몇가지 방법을 사용한다. 이러한 알고리즘은 구현하기가 더 어려울 수 있지만, 보다 빠른 수렴을 보여주기도 한다.

Successive over-relaxation : 이 방법은 깁스 샘플링(Gibbs sampling)의 변형이며, 종종 무작위 행보를 피한다.
하이브리드 몬테 카를로 (HMC) ('해밀토니언 몬테 카를로'라고 불림) : 부가적인 모멘텀 벡터를 도입하고 목표 밀도의 포텐션 함수를 갖는 해밀토니언 역학을 구현하여 무작위 행보를 피하려고 한다.

같이 보기

베이즈 추론

출처/참고

Christophe Andrieu et al, "An Introduction to MCMC for Machine Learning", 2003
Bernd A. Berg. "Markov Chain Monte Carlo Simulations and Their Statistical Analysis". Singapore, World Scientific 2004.
George Casella and Edward I. George. "Explaining the Gibbs sampler". The American Statistician, 46:167-174, 1992. (Basic summary and many references.)
A.E. Gelfand and A.F.M. Smith. "Sampling-Based Approaches to Calculating Marginal Densities". J. American Statistical Association, 85:398-409, 1990.
Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin. Bayesian Data Analysis. London: Chapman and Hall. First edition, 1995. (See Chapter 11.)
S. Geman and D. Geman. "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images". IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721-741, 1984.
Radford M. Neal, Probabilistic Inference Using Markov Chain Monte Carlo Methods, 1993.
Gilks W.R., Richardson S. and Spiegelhalter D.J. "Markov Chain Monte Carlo in Practice". Chapman & Hall/CRC, 1996.
C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004.
R. L. Smith ``Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions, Operations Research , Vol. 32, pp. 1296-1308, 1984.