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, który ma rozkład równowagowy taki jak szukana dystrybucja, 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.

Błądzenie losowe Monte Carlo jest istotną dużą podklasą takich procesów próbkowania.

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 nowe badania algorytmów MCMC były kluczowym krokiem potrzebnym do wyliczania dużych modeli hierarchicznych, które wymagają całkowania w dziedzinach setek parametrów swobodnych[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. ↑ Gill 2008 ↓.
  3. ↑ Robert i Casella 2004 ↓.
  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. ↑ Green 1995 ↓.
  11. ↑ Neal 2003 ↓.
  12. ↑ Stramer i Tweedie 1999 ↓.

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. (See Chapter 11.)
  • 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.