Próbkowanie Monte Carlo łańcuchami Markowa

Zbieżność algorytmu Metropolisa-Hastingsa. MCMC przybliża niebieski rozkład pomarańczowym rozkładem coraz dokładniej, gdy rośnie liczba kroków

Próbkowanie Monte Carlo łańcuchami Markowa (ang. Markov Chain Monte Carlo, MCMC) – klasa algorytmów próbkowania z rozkładu prawdopodobieństwa. Poprzez budowę łańcucha Markowa o rozkładzie równowagowym pasującym do pożądanego rozkładu można wydajnie próbkować złożone rozkłady prawdopodobieństwa. Im większa liczba kroków w takim algorytmie, tym dokładniej rozkład próbki odpowiada pożądanemu rozkładowi.

Dziedziny stosowania

Algorytmy MCMC są używane głównie do obliczania przybliżeń numerycznych dla całek wielowymiarowych, na przykład w statystyce bayesowskiej, fizyce komputerowej, biologii obliczeniowej[1] i lingwistyce komputerowej[2][3].

W statystyce bayesowskiej rozwój algorytmów MCMC umożliwił wyliczanie dużych modeli hierarchicznych, wymagających całkowania po setkach lub tysiącach parametrów[4].

Przykłady

Przykłady błądzenia losowego Monte Carlo obejmuje następujące algorytmy:

  • Algorytm Metropolisa-Hastingsa – generuje błądzenie losowe w oparciu o gęstość przyjmowania i odrzucania propozycji kolejnych kroków.
  • Próbkowanie Gibbsa – ta metoda dodatkowo wymaga, aby wszystkie warunkowe rozkłady prawdopodobieństwa docelowego rozkładu były znane (z dokładnością do stałej). Gdy próbkowanie warunkowych rozkładów nie jest łatwe, inne metody próbkowania mogą być użyte[5][6][7]. Próbkowanie Gibbsa zawdzięcza swoją popularność głównie brakowi parametrów swobodnych.
  • Próbkowanie przekrojów – opiera się na obserwacji, że dystrybucje można wiernie próbkować poprzez jednorodne próbkowanie odpowiednich podzbiorów dziedziny. Metoda wykonuje dwa rodzaje kroków naprzemiennie: próbkę w pionie z rozkładu jednorodnego i próbkę w poziomie z podzbioru dziedziny dla której gęstość prawdopodobieństwa jest mniejsza od próbki pionowej.
  • Wielokrotne Metropolis – odmiana algorytmu Metropolisa–Hastingsa, która pozwala na wiele prób w każdym punkcie. Poprzez umożliwienie dłuższych kroków w każdej iteracji, częściowo rozwiązuje problem „przekleństwa wymiarowości”[8][9].
  • Odwracalny skok – kolejna odmiana algorytmu Metropolisa–Hastingsa, która pozwala na dynamiczną zmianę wymiaru przestrzeni próbkowania[10]. Algorytmy MCMC, które zmieniają wymiar są stosowane w mechanice statystycznej, gdzie dla pewnych przypadków próbkowany rozkład układu wielkiego kanonicznego (na przykład gdy liczba cząsteczek w dziedzinie jest zmienna) zmienia wymiar dziedziny.

Redukowanie korelacji

Bardziej złożone metody wykorzystują różne sposoby, aby zmniejszyć korelację pomiędzy kolejnymi próbkami. Algorytmy te mogą być trudniejsze w implementacji, ale często wykazują szybszą zbieżność (tj. mniejszą ilość kroków w celu uzyskania tej samej dokładności próbkowania).

Przykłady

Przykłady MCMC, nienależących do metod błądzenia losowego obejmują następujące algorytmy:

  • Hybrydowa metoda Monte-Carlo (HMC) – unika błądzenia losowego poprzez wprowadzenie pędu i równań hamiltonowskich, takich że energia potencjalna jest proporcjonalna do docelowego rozkładu prawdopodobieństwa. Takie podejście skutkuje szybszym poruszaniem się po dziedzinie próbkowania i daje lepszą zbieżność do docelowego rozkładu. Istnieją też warianty próbkowania przekrojów, które nie korzystają z błądzenia losowego[11].
  • MCMC Langevina i inne metody oparte na gradiencie (czasem także na drugiej pochodnej) logarytmu rozkładu warunkowego pozwalają na tworzenie propozycji, które mają większą szansę na poruszanie się w kierunku dużej gęstości prawdopodobieństwa[12].

Przypisy

  1. ↑ Ankur Gupta, James B. Rawlings. Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology. „AIChE pismo”. 60 (4), s. 1253–1268, April 2014. DOI: 10.1002/aic.14409. PMID: 27429455. PMCID: PMC4946376. 
  2. ↑ Jeff Gill, Bayesian methods: a social and behavioral sciences approach, wyd. 2nd ed, Statistics in the social and behavioral sciences series, Boca Raton: Chapman & Hall/CRC, 2008, ISBN 978-1-58488-562-7, OCLC 144774105 [dostęp 2024-05-25].
  3. ↑ Christian P. Robert, George Casella, Monte Carlo statistical methods, wyd. 2. ed, Springer texts in statistics, New York, NY: Springer, 2004, ISBN 978-0-387-21239-5 [dostęp 2024-05-25].
  4. ↑ Sudipto Banerjee, Bradley P. Carlin, Alan P. Gelfand: Hierarchical Modeling and Analysis for Spatial Data. Wyd. Wyd.2. CRC Press, s. xix. ISBN 978-1-4398-1917-3.
  5. ↑ W. R. Gilks, P. Wild. Adaptive Rejection Sampling for Gibbs Sampling. „Journal of the Royal Statistical Society. Series C (Applied Statistics)”. 41 (2), s. 337–348, 1992-01-01. DOI: 10.2307/2347565. JSTOR: 2347565. 
  6. ↑ W.R. Gilks, N.G. Best, K.K.C. Tan. Adaptive Rejection Metropolis Sampling within Gibbs Sampling. „Journal of the Royal Statistical Society. Series C (Applied Statistics)”. 44 (4), s. 455–472, 1995-01-01. DOI: 10.2307/2986138. JSTOR: 2986138. 
  7. ↑ L. Martino, J. Read, D. Luengo. Independent Doubly Adaptive Rejection Metropolis Sampling Within Gibbs Sampling. „IEEE Transactions on Signal Processing”. 63 (12), s. 3123–3138, 2015-06-01. DOI: 10.1109/TSP.2015.2420537. arXiv:1205.5494. ISSN 1053-587X. Bibcode: 2015ITSP...63.3123M. 
  8. ↑ Jun S. Liu, Faming Liang, Wing Hung Wong. The Multiple-Try Method and Local Optimization in Metropolis Sampling. „Journal of the American Statistical Association”. 95 (449), s. 121–134, 2000-03-01. DOI: 10.1080/01621459.2000.10473908. ISSN 0162-1459. 
  9. ↑ Luca Martino, Jesse Read. On the flexibility of the design of multiple try Metropolis schemes. „Computational Statistics”. 28 (6), s. 2797–2823, 2013-07-11. DOI: 10.1007/s00180-013-0429-2. arXiv:1201.0646. ISSN 0943-4062. 
  10. ↑ Peter J. Green, Reversible jump Markov chain Monte Carlo computation and Bayesian model determination, „Biometrika”, 82 (4), 1995, s. 711–732, DOI: 10.1093/biomet/82.4.711, ISSN 0006-3444 [dostęp 2024-05-25] (ang.).
  11. ↑ Radford M. Neal, Slice sampling, „The Annals of Statistics”, 31 (3), 2003, s. 705–767, DOI: 10.1214/aos/1056562461, ISSN 0090-5364 [dostęp 2024-05-25].
  12. ↑ O. Stramer, R.L. Tweedie, Langevin-Type Models II: Self-Targeting Candidates for MCMC Algorithms*, „Methodology And Computing In Applied Probability”, 1 (3), 1999, s. 307–328, DOI: 10.1023/A:1010090512027, ISSN 1573-7713 (ang.).

Bibliografia

  • Christophe Andrieu, Nando De Freitas, Arnaud Doucet and Michael I. Jordan An Introduction to MCMC for Machine Learning, 2003
  • Søren Asmussen, Peter W. Glynn: Stochastic Simulation: Algorithms and Analysis. T. 57. Springer, 2007, seria: Stochastic Modelling and Applied Probability.
  • P. Atzberger: An Introduction to Monte-Carlo Methods. [dostęp 2018-11-10]. [zarchiwizowane z tego adresu (2009-02-20)].
  • Bernd A. Berg: Markov Chain Monte Carlo Simulations and Their Statistical Analysis. World Scientific, 2004.
  • William M. Bolstad: Understanding Computational Bayesian Statistics. Wiley, 2010. ISBN 0-470-04609-0.
  • George Casella, Edward I. George. Explaining the Gibbs sampler. „The American Statistician”. 46, s. 167–174, 1992. DOI: 10.2307/2685208. 
  • A.E. Gelfand, A.F.M. Smith. Sampling-Based Approaches to Calculating Marginal Densities. „Journal of the American Statistical Association”. 85, s. 398–409, 1990. DOI: 10.1080/01621459.1990.10476213. 
  • Andrew Gelman, John B. Carlin, Hal S. Stern, Donald B. Rubin: Bayesian Data Analysis. Wyd. 1. Chapman and Hall, 1995..
  • S. Geman, D. Geman. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. „IEEE Transactions on Pattern Analysis and Machine Intelligence”. 6, s. 721–741, 1984. 
  • W.R. Gilks, S. Richardson, D.J. Spiegelhalter: Markov Chain Monte Carlo in Practice. Chapman and Hall/CRC, 1996.
  • Jeff Gill: Bayesian methods: a social and behavioral sciences approach. Wyd. 2nd. Chapman and Hall/CRC, 2008. ISBN 1-58488-562-9.
  • P.J. Green. Reversible-jump Markov chain Monte Carlo computation and Bayesian model determination. „Biometrika”. 82 (4), s. 711–732, 1995. DOI: 10.1093/biomet/82.4.711. 
  • Radford M. Neal. Slice Sampling. „Annals of Statistics”. 31 (3), s. 705–767, 2003. DOI: 10.1214/aos/1056562461. JSTOR: 3448413. 
  • Radford M. Neal: Probabilistic Inference Using Markov Chain Monte Carlo Methods. 1993. [dostęp 2018-11-10].
  • Christian P. Robert, G. Casella: Monte Carlo Statistical Methods. Wyd. 2nd. Springer, 2004. ISBN 0-387-21239-6.
  • R.Y. Rubinstein, D.P. Kroese: Simulation and the Monte Carlo Method. Wyd. 2. John Wiley & Sons, 2007. ISBN 978-0-470-17794-5.
  • R.L. Smith. Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions. „Operations Research”. 32, s. 1296–1308, 1984. DOI: 10.1287/opre.32.6.1296. 
  • J.C. Spall. Estimation via Markov Chain Monte Carlo. „IEEE Control Systems Magazine”. 23 (2), s. 34–45, April 2003. DOI: 10.1109/mcs.2003.1188770. 
  • O. Stramer, R. Tweedie. Langevin-Type Models II: Self-Targeting Candidatas for MCMC Algorithms. „Methodology and Computing in Applied Probability”. 1 (3), s. 307–328, 1999. DOI: 10.1023/A:1010090512027.