Markov chain Monte Carlo

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Markov chain Monte Carlo (MCMC, česky asi Monte Carlo pomocí Markovova řetězce) je ve statistice třída algoritmů pro vzorkování z pravděpodobnostního rozdělení založená na konstrukci Markovova řetězce, který má požadované rozdělení jako svou rovnovážnou distribuci. Stav řetězce po několika krocích se pak použije jako vzorek z požadované distribuce. Kvalita vzorku se zvyšuje se zvýšením počtu kroků.

Konvergence algoritmu Metropolis-Hastings. MCMC se pokusí přiblížit k modré distribuci prostřednictvím oranžové distribuce

Metody Monte Carlo pomocí náhodné procházky tvoří velkou podtřídu MCMC metod.

Aplikační domény[editovat | editovat zdroj]

Klasifikace[editovat | editovat zdroj]

Metoda Monte Carlo s náhodnou procházkou[editovat | editovat zdroj]

Podrobnější informace naleznete v článku náhodná procházka.

Vícerozměrné integrály[editovat | editovat zdroj]

Pokud se použije metoda MCMC pro aproximaci vícerozměrného integrálu, soubor "chodců" se pohybuje náhodně. Pro každý bod, kde chodec zastaví, se hodnota integrandu v tomto bodě započítává do integrálu. Chodec pak může provést řadu průběžných kroků po okolí, hledaje místo s přiměřeně velkým přínosem pro integrál, do kterého se přesune v dalším kroku.

Metody Monte Carlo s náhodnou procházkou patří mezi náhodné simulace neboli Monte Carlo metody. Nicméně, náhodné vzorky integrandu používané při běžné Monte Carlo integraci jsou jsou statisticky nezávislé, kdežto ty používané v metodách MCMC jsou korelovány. Markovův řetězec je konstruován takovým způsobem, aby měl daný integrand jako svou rovnovážnou distribuci.

Příklady[editovat | editovat zdroj]

Příklady metod Monte Carlo s náhodnou procházkou zahrnují následující:

  • Metropolisův-Hastingsův algoritmus: Tato metoda generuje náhodnou procházku s využitím navrhované hustoty rozdělení a používá metodu pro odmítnutí některých z navrhovaných vzorků.
  • Gibbsovo vzorkování: Tato metoda vyžaduje, aby všechny podmíněné distribuce cílové distribuce byly vzorkovány přesně. Je populární, částečně proto, že nevyžaduje žádné "ladění".
  • Slice vzorkování: Tato metoda spočívá na principu, že lze vzorkovat z distribuce pomocí vzorkování rovnoměrně z oblasti pod grafem dané funkce hustoty. Metoda střídá rovnoměrné vzorkování ve svislém směru s rovnoměrným vzorkováním z vodorovného "plátku" (angl. slice) definovaném aktuální vertikální polohou.
  • Multiple-try Metropolis: Tato metoda je variantou Metropolisova-Hastingsova algoritmu, která umožňuje opakované pokusy v každém bodě. Tím, že je možné vykonat větší kroky při každé iteraci, pomáhá řešit prokletí dimenzionality.
  • Reversibilní skok: Tato metoda je variantou Metropolisova-Hastingsova algoritmu, která umožňuje návrhy, které mění dimenzionalitu prostoru.[4] MCMC metody, které mění dimenzionalitu, se již dlouho používají v aplikacích statistické fyziky, kde se pro některé problémy používá distribuce, která je velký kanonický soubor (například, když počet molekul v krabici je proměnný). Ale varianta reverzibilního skoku je užitečná, když se dělá MCMC nebo Gibbsovo vzorkování nad neparametrickým bayesovským modelem, například takovým, který zahrnuje Dirichletův proces nebo proces čínské restaurace, kde počet směsných komponent/klasterů/atd. je automaticky odvozen z dat.

Jiné metody MCMC[editovat | editovat zdroj]

Markov Chain quasi-Monte Carlo (MCQMC)[5][6]

Konvergence[editovat | editovat zdroj]

Obvykle není těžké sestavit Markovův řetěz s požadovanými vlastnostmi. Obtížnější problém je určit, kolik kroků je zapotřebí ke konvergenci k stacionárnímu rozdělení s přijatelnou chybou. Dobrý řetěz bude mít rychlé mísení: stacionární distribuce je dosaženo rychle z libovolné počáteční pozice.

Typicky, MCMC vzorkování pouze aproximuje cílovou distribuci, protože je tam vždy nějaký zbytkový efekt počáteční pozice. Sofistikovanější algoritmy založené na MCMC, jako například coupling from the past můžou produkovat přesné vzorky, za cenu dodatečného výpočtu a neomezeného (i když konečného v očekávání) času běhu.

Mnoho metod Monte Carlo s náhodnou procházkou se pohybuje po rovnovážné distribuci v relativně malých krocích, bez tendence, aby kroky pokračovaly ve stejném směru. Tyto metody jdou snadno implementovat a analyzovat, ale bohužel může trvat dlouhou dobu, než procházka prozkoumá celý prostor. Chodec se často vrací zpět a pokrývá již prozkoumaný prostor.

Související články[editovat | editovat zdroj]

Poznámky[editovat | editovat zdroj]

  1. See Gill 2008.
  2. See Robert & Casella 2004.
  3. Hierarchical Modeling and Analysis for Spatial Data, Second Edition, CRC Press, xix. ISBN 978-1-4398-1917-3. 
  4. See Green 1995.
  5. Chen, S., Josef Dick, and Art B. Owen. "Consistency of Markov chain quasi-Monte Carlo on continuous state spaces." The Annals of Statistics 39.2 (2011): 673-701.
  6. Tribble, Seth D. Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences. Diss. Stanford University, 2007.


Reference[editovat | editovat zdroj]

  • Christophe Andrieu, Nando De Freitas and Arnaud Doucet, An Introduction to MCMC for Machine Learning, 2003
  • (2007) Stochastic Simulation: Algorithms and Analysis, Stochastic Modelling and Applied Probability 57. Springer. 
  • ATZBERGER, P.. An Introduction to Monte-Carlo Methods [online]. . [1]. (anglicky) 
  • Berg, Bernd A.(2004). Markov Chain Monte Carlo Simulations and Their Statistical AnalysisWorld Scientific. 
  • Bolstad, William M.(2010). Understanding Computational Bayesian Statistics. Wiley. ISBN 0-470-04609-0. 
  •  "Explaining the Gibbs sampler"(1992). 'The American Statistician' 46: 167–174. doi:10.2307/2685208.  (Basic summary and many references.)
  •  "Sampling-Based Approaches to Calculating Marginal Densities"(1990). Journal of the American Statistical Association 85: 398–409. doi:10.1080/01621459.1990.10476213. 
  • (1995) Bayesian Data Analysis, 1st, Chapman and Hall.  (See Chapter 11.)
  •  "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images"(1984). IEEE Transactions on Pattern Analysis and Machine Intelligence 6: 721–741. 
  • (1996) Markov Chain Monte Carlo in PracticeChapman and Hall/CRC. 
  • Gill, Jeff(2008). Bayesian methods: a social and behavioral sciences approach, 2nd, Chapman and Hall/CRC. ISBN 1-58488-562-9. 
  • Green, P.J. (1995).  "Reversible-jump Markov chain Monte Carlo computation and Bayesian model determination". Biometrika 82 (4): 711–732. doi:10.1093/biomet/82.4.711. 
  • Neal, Radford M. (2003).  "Slice Sampling". Annals of Statistics 31 (3): 705–767. doi:10.1214/aos/1056562461. 
  • NEAL, Radford M.. Probabilistic Inference Using Markov Chain Monte Carlo Methods [online]. 1993. [2]. (anglicky) 
  • Robert, Christian P.(2004). Monte Carlo Statistical Methods, 2nd, Springer. ISBN 0-387-21239-6. 
  • (2007) Simulation and the Monte Carlo Method, 2nd, Wiley. ISBN 978-0-470-17794-5. 
  • Smith, R.L. (1984).  "Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions". Operations Research 32: 1296–1308. doi:10.1287/opre.32.6.1296. 
  • Spall, J.C. (April 2003).  "Estimation via Markov Chain Monte Carlo". IEEE Control Systems Magazine 23 (2): 34–45. doi:10.1109/mcs.2003.1188770. 
  •  "Langevin-Type Models II: Self-Targeting Candidates for MCMC Algorithms"(1999). Methodology and Computing in Applied Probability 1 (3): 307–328. doi:10.1023/A:1010090512027. 


Externí odkazy[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Markov chain Monte Carlo na anglické Wikipedii.