마르코프 연쇄 몬테카를로

Markov chain Monte Carlo
시리즈의 일부
베이지안 통계
Bayes icon.svg
이론.
기술

통계학에서 마르코프 연쇄 몬테카를로(MCMC) 방법은 확률분포에서 샘플링하기 위한 알고리즘의 클래스를 구성한다.원하는 분포를 평형 분포로 하는 마르코프 체인을 구성함으로써 체인으로부터 상태를 기록함으로써 원하는 분포의 샘플을 얻을 수 있다.포함되는 단계가 많을수록 표본의 분포가 실제 원하는 분포와 더 밀접하게 일치합니다.Metropolis-Hastings 알고리즘을 포함하여 체인을 구축하기 위한 다양한 알고리즘이 존재합니다.

응용 프로그램 도메인

MCMC 방법은 베이지안 통계학,[3][4] 계산물리학,[1] 계산생물학[2] 및 계산언어학 등에서 다차원 적분의 수치 근사치 계산에 주로 사용된다.

베이지안 통계학에서는 최근 MCMC 방법의 개발로 수백에서 수천 개의 알려지지 않은 파라미터에 [5]대한 통합을 필요로 하는 대규모 계층적 모델을 계산할 수 있게 되었다.

희귀 사건 표본 추출에서는 희귀 고장 [citation needed]영역을 점차 채우는 표본을 생성하는 데도 사용됩니다.

일반적인 설명

Metropolis-Hastings 알고리즘의 컨버전스.마르코프 연쇄 몬테 카를로는 주황색 분포로 파란색 분포를 근사하려고 시도합니다.

마르코프 연쇄 몬테 카를로 방법은 알려진 함수에 비례하는 확률 밀도를 가진 연속 랜덤 변수로부터 샘플을 생성한다.이러한 표본을 사용하여 해당 변수에 대한 적분을 기대값 또는 분산으로 평가할 수 있습니다.

실질적으로 체인 앙상블은 일반적으로 임의로 선택되고 서로 충분히 떨어져 있는 일련의 포인트로부터 개발된다.이러한 체인은 적분에 대한 기여도가 상당히 높은 장소를 찾는 알고리즘에 따라 랜덤하게 이동하는 "보행자"의 확률적 과정으로, 더 높은 확률을 할당한다.

랜덤 워크 몬테카를로 방법은 일종의 랜덤 시뮬레이션 또는 몬테카를로 방법이다.그러나 기존의 몬테카를로 통합에 사용된 적분자의 무작위 표본은 통계적으로 독립적이지만, MCMC에 사용된 표본은 자기 상관 관계이다.표본의 상관관계는 평균값의 오차를 추정할 때 마르코프 연쇄 중심 한계 정리를 사용할 필요성을 야기한다.

이러한 알고리즘은 주어진 함수에 비례하는 평형 분포를 가지도록 마르코프 사슬을 만든다.

상관 관계 감소

MCMC 방법은 일반적인 몬테카를로 알고리즘보다 다차원 문제를 더 잘 다루기 위해 개발되었지만, 차원 수가 증가하면 차원성의 저주에 시달리는 경향이 있다. 즉, 높은 확률의 영역은 적분에 거의 기여하지 않는 증가하는 공간 볼륨에서 확장되고 상실되는 경향이 있다.이 문제를 해결하는 한 가지 방법은 워커의 스텝을 단축하는 것입니다.이렇게 하면 프로세스는 자기 상관성이 높고 비용이 많이 듭니다(정확한 결과를 얻으려면 많은 스텝이 필요합니다).Hamiltonian Monte Carlo 및 Wang and Landau 알고리즘과 같은 보다 정교한 방법은 적분에 더 높은 기여를 하는 영역에서 프로세스를 유지하는 동안 이 자기 상관을 줄이는 다양한 방법을 사용한다.이러한 알고리즘은 보통 보다 복잡한 이론에 의존하며 구현하기가 더 어렵지만, 대개 더 빨리 수렴됩니다.

예

랜덤 워크

  • Metropolis-Hastings 알고리즘:이 방법은 새로운 단계에 대한 제안 밀도와 제안된 움직임의 일부를 거부하는 방법을 사용하여 마르코프 체인을 생성한다.이 프레임워크는 실제로 특별한 경우로서 가장 처음이자 단순한 MCMC(메트로폴리스 알고리즘)와 아래에 나열된 많은 최신 대안을 포함하는 일반적인 프레임워크입니다.
    • Gibbs 샘플링:이 방법을 사용하려면 목표 분포의 모든 조건부 분포를 정확하게 표본 추출해야 합니다.완전 조건부 분포에서 그리기가 간단하지 않은 경우 다른 썬플러스 내 Gibbs가 사용됩니다(예: 를 참조).깁스 샘플링은 부분적으로 '튜닝'이 필요하지 않기 때문에 인기가 있습니다.깁스 샘플링의 알고리즘 구조는 두 알고리즘이 갱신 절차에서 [8]완전한 조건부 분포를 이용한다는 점에서 좌표 상승 변동 추론의 구조와 매우 유사하다.
    • 메트로폴리스 보정 Langevin 알고리즘 및 로그 목표 밀도의 기울기(및 아마도 두 번째 도함수)에 의존하여 높은 확률 [9]밀도의 방향에 있을 가능성이 높은 단계를 제안하는 기타 방법.
    • 의사-마지노선 메트로폴리스-헤스팅:이 방법은 목표 분포의 밀도 평가를 편향되지 않은 추정치로 대체하며, 목표 밀도를 분석적으로 이용할 수 없는 경우(예: 잠재 변수 모델)에 유용합니다.
  • 슬라이스 샘플링:이 방법은 밀도 함수의 그림 아래 영역에서 균일하게 표본을 추출하여 분포에서 표본을 추출할 수 있는 원리에 따라 달라집니다.수직 방향으로 균일한 샘플링과 현재 수직 위치에 의해 정의된 수평 '슬라이스'로부터의 균일한 샘플링이 번갈아 이루어집니다.
  • 멀티 트라이 메트로폴리스:이 방법은 Metropolis-Hastings 알고리즘의 변형으로, 각 지점에서 여러 번의 시행이 가능합니다.반복할 때마다 더 큰 단계를 밟을 수 있게 함으로써 차원성의 문제를 해결하는 데 도움이 됩니다.
  • 리버서블 점프:이 방법은 공간의 [10]차원성을 변경하는 제안을 허용하는 Metropolis-Hastings 알고리즘의 변형입니다.차원성을 변화시키는 마르코프 연쇄 몬테 카를로 방법은 통계 물리학 응용 분야에서 오랫동안 사용되어 왔으며, 일부 문제에서는 대표준 앙상블 분포가 사용된다(예: 상자 안의 분자 수가 가변적일 때).그러나 가역점프 변형은 데이터로부터 혼합 성분/클러스터 등의 수가 자동으로 추론되는 디리클레 공정이나 중국 식당 공정과 같은 비모수 베이지안 모델에 대해 마르코프 연쇄 몬테 카를로 또는 깁스 표본을 추출할 때 유용하다.
  • Hamiltonian (또는 Hybrid) Monte Carlo (HMC) : 보조 운동량 벡터를 도입하고 Hamiltonian dynamics를 구현하여 랜덤 보행 동작을 피하려고 합니다.따라서 잠재적 에너지 함수는 목표 밀도입니다.운동량 샘플은 샘플링 후 폐기됩니다.Hybrid Monte Carlo의 최종 결과는 제안서가 더 큰 단계에서 표본 공간을 가로질러 이동한다는 것이다. 따라서 그들은 덜 상관성이 있고 목표 분포에 더 빠르게 수렴된다.

상호작용 입자법

상호작용 MCMC 방법론은 표본 추출 [11]복잡도가 증가하는 일련의 확률 분포로부터 랜덤 샘플을 얻기 위한 평균장 입자 방법의 한 종류이다.이러한 확률론적 모델에는 시간 지평선이 증가하는 경로 공간 상태 모델, 부분 관측의 사후 분포, 조건부 분포에 대한 제약 수준 세트 증가, 일부 볼츠만-기브스 분포와 관련된 온도 일정 감소 등이 포함된다.원칙적으로 어떤 마르코프 연쇄 몬테카를로 샘플러는 상호작용 마르코프 연쇄 몬테카를로 샘플러로 바뀔 수 있다.이러한 상호작용하는 마르코프 연쇄 몬테 카를로 표본 추출기는 마르코프 연쇄 몬테 카를로 표본 추출기의 시퀀스를 병렬로 실행하는 방법으로 해석될 수 있다.예를 들어, 상호작용 시뮬레이션 어닐링 알고리즘은 선택-재샘플링 유형 메커니즘과 순차적으로 상호작용하는 독립적인 메트로폴리스-헤스팅 이동을 기반으로 한다.전통적인 마르코프 연쇄 몬테카를로 방법과는 대조적으로, 상호작용 마르코프 연쇄 몬테카를로 샘플러의 이 클래스의 정밀 매개변수는 상호작용 마르코프 연쇄 몬테카를로 샘플러의 수와만 관련이 있다.이러한 고급 입자 방법론은 파인만-Kac 입자 [12][13]모델의 클래스에 속하며, 베이지안 추론 [14]및 신호 처리 커뮤니티에서 순차 몬테 카를로 또는 입자 필터 방법이라고도 합니다.마르코프 연쇄 몬테카를로 방법 상호작용은 마르코프 연쇄 몬테카를로 돌연변이를 가진 돌연변이 선택 유전 입자 알고리즘으로도 해석될 수 있다.

마르코프 연쇄 준 몬테 카를로(MCQMC).[15][16]

단순 독립 몬테카를로 샘플링을 위한 난수 대신 저불확실성 시퀀스의 이점은 [17]잘 알려져 있다.준 몬테카를로법(QMC)[18]으로 알려진 이 절차는 IID 샘플링에 의해 얻어진 것보다 높은 비율로 Koksma-Hlawka 부등식에 의해 감소하는 적분 오류를 생성합니다.경험적으로 추정 오류와 수렴 시간을 크기 [citation needed]순서로 줄일 수 있습니다.그 Array-RQMC 방법 화합해서 한quasi–Monte 카를로, 마르코프 연쇄 시뮬레이션을 동시에 진행에 사슬의 진정한 분포의 평범한 MCMC.[19]인 e.보다는 n{n\displaystyle}주 주어진 단계에서 경험적 분배는 더 좋은 근사 n{n\displaystyle}체인점을 모의 실험해mpi리칼 실험에서는 상태 함수 평균의 분산이 O-)몬테카를로 [20] O-)({ 또는 그보다 더 빠르게 수렴되는 경우가 있다.

컨버전스

일반적으로 원하는 성질을 가진 마르코프 사슬을 구성하는 것은 어렵지 않다.더 어려운 문제는 허용 [21]오차 내에서 정적 분포로 수렴하는 데 필요한 단계 수를 결정하는 것입니다.양호한 체인은 빠르게 혼합됩니다. 즉, 임의의 위치에서 시작하여 고정 분포에 빠르게 도달합니다.수렴을 평가하기 위한 표준 경험적 방법은 여러 개의 독립된 시뮬레이션 마르코프 사슬을 실행하고 표본 추출된 모든 파라미터에 대해 사슬 간 분산의 비율이 [21][22]1에 가까운지 확인하는 것이다.

일반적으로 마르코프 연쇄 몬테 카를로 표본 추출은 시작 위치의 잔존 효과가 항상 존재하기 때문에 목표 분포에 근사할 수 있다.과거의 커플링과 같은 보다 정교한 마르코프 연쇄 몬테 카를로 기반 알고리즘은 추가 계산의 비용과 (기대에는 유한하지만) 무제한 실행 시간을 들여 정확한 샘플을 생산할 수 있다.

많은 랜덤 워크 몬테카를로 방법은 비교적 작은 단계로 평형 분포를 중심으로 이동하며, 단계가 동일한 방향으로 진행되는 경향이 없다.이 방법들은 구현과 분석이 쉽지만, 안타깝게도 보행자가 모든 공간을 탐험하는 데는 오랜 시간이 걸릴 수 있다.보행기는 종종 뒤로 젖혀져 이미 덮인 땅을 덮는다.

수렴에 대한 추가적인 고려는 마르코프 연쇄 중심 한계 정리에 있다.Metropolis-Hastings 알고리즘의 컨버전스 및 정지성에 관한 이론에 대해서는, 을 참조해 주세요.

소프트웨어

다음과 같은 여러 소프트웨어 프로그램이 MCMC 샘플링 기능을 제공합니다.

「 」를 참조해 주세요.

레퍼런스

인용문

  1. ^ Kasim, M.F.; Bott, A.F.A.; Tzeferacos, P.; Lamb, D.Q.; Gregori, G.; Vinko, S.M. (September 2019). "Retrieving fields from proton radiography without source profiles". Physical Review E. 100 (3): 033208. arXiv:1905.12934. Bibcode:2019PhRvE.100c3208K. doi:10.1103/PhysRevE.100.033208. PMID 31639953. S2CID 170078861.
  2. ^ Gupta, Ankur; Rawlings, James B. (April 2014). "Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology". AIChE Journal. 60 (4): 1253–1268. doi:10.1002/aic.14409. PMC 4946376. PMID 27429455.
  3. ^ Gill 2008을 참조해 주세요.
  4. ^ Robert & Casella 2004 를 참조해 주세요.
  5. ^ Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. (2014-09-12). Hierarchical Modeling and Analysis for Spatial Data (Second ed.). CRC Press. p. xix. ISBN 978-1-4398-1917-3.
  6. ^ Gilks, W. R.; Wild, P. (1992-01-01). "Adaptive Rejection Sampling for Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 41 (2): 337–348. doi:10.2307/2347565. JSTOR 2347565.
  7. ^ Gilks, W. R.; Best, N. G.; Tan, K. K. C. (1995-01-01). "Adaptive Rejection Metropolis Sampling within Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 44 (4): 455–472. doi:10.2307/2986138. JSTOR 2986138.
  8. ^ Lee, Se Yoon (2021). "Gibbs sampler and coordinate ascent variational inference: A set-theoretical review". Communications in Statistics - Theory and Methods: 1–21. arXiv:2008.01006. doi:10.1080/03610926.2021.1921214. S2CID 220935477.
  9. ^ Stramer 1999 를 참조해 주세요.
  10. ^ 「Green 1995」를 참조해 주세요.
  11. ^ Del Moral, Pierre (2013). Mean field simulation for Monte Carlo integration. Chapman & Hall/CRC Press. p. 626.
  12. ^ Del Moral, Pierre (2004). Feynman–Kac formulae. Genealogical and interacting particle approximations. Springer. p. 575.
  13. ^ Del Moral, Pierre; Miclo, Laurent (2000). "Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering". In Jacques Azéma; Michel Ledoux; Michel Émery; Marc Yor (eds.). Séminaire de Probabilités XXXIV (PDF). Lecture Notes in Mathematics. Vol. 1729. pp. 1–145. doi:10.1007/bfb0103798. ISBN 978-3-540-67314-9.
  14. ^ Del Moral, Pierre (2006). "Sequential Monte Carlo samplers". Journal of the Royal Statistical Society. Series B (Statistical Methodology). 68 (3): 411–436. arXiv:cond-mat/0212648. doi:10.1111/j.1467-9868.2006.00553.x. S2CID 12074789.
  15. ^ Chen, S.; Dick, Josef; Owen, Art B. (2011). "Consistency of Markov chain quasi-Monte Carlo on continuous state spaces". Annals of Statistics. 39 (2): 673–701. arXiv:1105.1896. doi:10.1214/10-AOS831.
  16. ^ Tribble, Seth D. (2007). Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences (Diss.). Stanford University. ProQuest 304808879.
  17. ^ Papageorgiou, Anargyros; Traub, J. F. (1996). "Beating Monte Carlo". Risk. 9 (6): 63–65.
  18. ^ Sobol, Ilya M (1998). "On quasi-monte carlo integrations". Mathematics and Computers in Simulation. 47 (2): 103–112. doi:10.1016/s0378-4754(98)00096-2.
  19. ^ L'Ecuyer, P.; Lécot, C.; Tuffin, B. (2008). "A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains" (PDF). Operations Research. 56 (4): 958–975. doi:10.1287/opre.1080.0556.
  20. ^ L'Ecuyer, P.; Munger, D.; Lécot, C.; Tuffin, B. (2018). "Sorting Methods and Convergence Rates for Array-RQMC: Some Empirical Comparisons". Mathematics and Computers in Simulation. 143: 191–201. doi:10.1016/j.matcom.2016.07.010.
  21. ^ a b Gelman, A.; Rubin, D.B. (1992). "Inference from iterative simulation using multiple sequences (with discussion)" (PDF). Statistical Science. 7 (4): 457–511. Bibcode:1992StaSc...7..457G. doi:10.1214/ss/1177011136.
  22. ^ Cowles, M.K.; Carlin, B.P. (1996). "Markov chain Monte Carlo convergence diagnostics: a comparative review". Journal of the American Statistical Association. 91 (434): 883–904. CiteSeerX 10.1.1.53.3445. doi:10.1080/01621459.1996.10476956.
  23. ^ Hill, S. D.; Spall, J. C. (2019). "Stationarity and Convergence of the Metropolis-Hastings Algorithm: Insights into Theoretical Aspects". IEEE Control Systems Magazine. 39 (1): 56–67. doi:10.1109/MCS.2018.2876959. S2CID 58672766.
  24. ^ Foreman-Mackey, Daniel; Hogg, David W.; Lang, Dustin; Goodman, Jonathan (2013-11-25). "emcee: The MCMC Hammer". Publications of the Astronomical Society of the Pacific. 125 (925): 306–312. doi:10.1086/670067.

원천

추가 정보