Markovský řetězec Monte Carlo - Markov chain Monte Carlo

Část série na
Bayesovské statistiky
Bayes icon.svg
Teorie
Techniky
  • Aplikace Nuvola Edu Mathematics Blue-p.svg Matematický portál

v statistika, Markovský řetězec Monte Carlo (MCMC) metody zahrnují třídu algoritmy pro odběr vzorků z a rozdělení pravděpodobnosti. Vytvořením a Markovův řetězec který má požadované rozdělení jako jeho rovnovážné rozdělení lze získat vzorek požadovaného rozdělení zaznamenáním stavů z řetězce. Čím více kroků je zahrnuto, tím více se distribuce vzorku blíží skutečnému požadovanému rozdělení. Pro konstrukci řetězců existují různé algoritmy, včetně Algoritmus Metropolis – Hastings.

Domény aplikací

Metody MCMC se primárně používají pro výpočet numerické aproximace z vícerozměrné integrály, například v Bayesovské statistiky, výpočetní fyzika,[1] výpočetní biologie[2] a výpočetní lingvistika.[3][4]

V Bayesiánských statistikách umožnil nedávný vývoj metod MCMC počítat velké objemy hierarchické modely které vyžadují integraci přes stovky až tisíce neznámých parametrů.[5]

v Vzorkování vzácných událostí, jsou také používány pro generování vzorků, které postupně naplňují oblast vzácného selhání.

Obecné vysvětlení

Konvergence Algoritmus Metropolis – Hastings. Markovský řetězec Monte Carlo se pokouší aproximovat modrou distribuci s oranžovou distribucí.

Metody Markovova řetězce Monte Carlo vytvářejí vzorky z kontinua náhodná proměnná, s hustota pravděpodobnosti úměrné známé funkci. Tyto vzorky lze použít k vyhodnocení integrálu přes tuto proměnnou očekávaná hodnota nebo rozptyl.

Prakticky, soubor řetězců se obecně vyvíjí, počínaje množinou bodů libovolně zvolených a dostatečně vzdálených od sebe. Tyto řetězy jsou stochastické procesy „chodců“, kteří se náhodně pohybují podle algoritmu, který hledá místa s přiměřeně vysokým příspěvkem k integrálu, aby se přesunuli na další, jim přiřadí vyšší pravděpodobnost.

Náhodné procházky Metody Monte Carlo jsou jakési náhodné simulace nebo Metoda Monte Carlo. Nicméně, zatímco náhodné vzorky integrand použité v konvenčním Integrace Monte Carlo jsou statisticky nezávislé, ty používané v MCMC jsou autokorelovaný. Korelace vzorků zavádí potřebu používat Markovova řetězová věta o limitu při odhadu chyby středních hodnot.

Tyto algoritmy vytvářejí Markovovy řetězy tak, že mají rovnovážné rozdělení což je úměrné dané funkci.

Snížení korelace

Zatímco metody MCMC byly vytvořeny k řešení vícerozměrných problémů lépe než obecné algoritmy Monte Carlo, když počet dimenzí stoupá, mají také tendenci trpět kletba dimenzionality: oblasti s vyšší pravděpodobností mají tendenci se protahovat a ztrácet ve zvyšujícím se objemu prostoru, který k integrálu přispívá jen málo. Jedním ze způsobů řešení tohoto problému by mohlo být zkrácení kroků nástroje Walker, aby se neustále nepokoušel opustit oblast s nejvyšší pravděpodobností, i když tímto způsobem by byl proces vysoce autokorelovaný a nákladný (tj. přesný výsledek). Sofistikovanější metody jako např Hamiltonské Monte Carlo a Wangův a Landauův algoritmus použít různé způsoby, jak omezit tuto autokorelaci, a přitom zachovat proces v regionech, které poskytují vyšší příspěvek k integrálu. Tyto algoritmy se obvykle spoléhají na složitější teorii a je obtížnější je implementovat, ale obvykle konvergují rychleji.

Příklady

Náhodná procházka

  • Algoritmus Metropolis – Hastings: Tato metoda generuje Markovův řetězec pomocí hustoty nabídky pro nové kroky a metody pro odmítnutí některých navrhovaných tahů. Ve skutečnosti jde o obecný rámec, který obsahuje jako speciální případy úplně první a jednodušší MCMC (algoritmus Metropolis) a mnoho novějších alternativ uvedených níže.
    • Gibbsův odběr vzorků: Tato metoda vyžaduje vše podmíněné distribuce cílové distribuce, která má být vzorkována přesně. Když čerpání z plně podmíněných distribucí není přímočaré, používají se jiné vzorkovače v rámci Gibbs (např. Viz [6][7]). Gibbsovo vzorkování je populární částečně proto, že nevyžaduje žádné „vyladění“.
    • Langevinův algoritmus upravený podle metropole a další metody, které spoléhají na gradient (a případně druhou derivaci) log cílové hustoty, aby navrhly kroky, u nichž je větší pravděpodobnost, že budou ve směru vyšší hustoty pravděpodobnosti.[8]
    • Pseudo-okrajová metropole – Hastings: Tato metoda nahrazuje vyhodnocení hustoty distribuce cíle nezaujatým odhadem a je užitečná, když cílová hustota není k dispozici analyticky, např. latentní variabilní modely.
  • Odběr vzorků řezu: Tato metoda závisí na principu, že je možné vzorkovat z distribuce stejnoměrným vzorkováním z oblasti pod grafem jeho hustotní funkce. Střídá rovnoměrné vzorkování ve svislém směru s rovnoměrným vzorkováním z vodorovného „řezu“ definovaného aktuální svislou polohou.
  • Vícekrát vyzkoušejte Metropolis: Tato metoda je variantou algoritmu Metropolis – Hastings, který umožňuje více pokusů v každém bodě. Tím, že je možné podniknout větší kroky při každé iteraci, pomáhá řešit kletbu dimenzionality.
  • Reverzibilní skok: Tato metoda je variantou algoritmu Metropolis – Hastings, který umožňuje návrhy, které mění rozměrnost prostoru.[9] Metody Markovova řetězce Monte Carlo, které mění rozměrnost, se již dlouho používají statistická fyzika aplikace, kde pro některé problémy je distribuce, která je velký kanonický soubor se používá (např. když je počet molekul v rámečku proměnlivý). Varianta reverzibilního skoku je ale užitečná, když provádíte vzorkování Markovova řetězce Monte Carlo nebo Gibbs neparametrické Bayesovské modely, jako jsou modely zahrnující Dirichletův proces nebo Proces čínské restaurace, kde je počet míchacích složek / klastrů / atd. je z údajů automaticky odvozen.
  • Hamiltonovské (nebo hybridní) Monte Carlo (HMC): Snaží se vyhnout se náhodnému chování chůze zavedením pomocného zařízení hybnost vektor a implementace Hamiltonova dynamika, takže funkcí potenciální energie je cílová hustota. Po odebrání vzorků se vzorky hybnosti zahodí. Konečným výsledkem Hybrid Monte Carlo je, že se návrhy pohybují napříč vzorkovaným prostorem ve větších krocích; jsou proto méně korelované a rychleji konvergují k cílové distribuci.

Interakční částicové metody

Interakční metodiky MCMC jsou třídou metody středních polních částic pro získání náhodné vzorky ze sledu rozdělení pravděpodobnosti s rostoucí úrovní složitosti vzorkování.[10] Tyto pravděpodobnostní modely zahrnují modely stavu prostoru dráhy s rostoucím časovým horizontem, zadní distribuce w.r.t. posloupnost dílčích pozorování, zvyšující se sady úrovní omezení pro podmíněné distribuce, snižující se teplotní plány spojené s některými Boltzmann-Gibbsovými distribucemi a mnoho dalších. V zásadě lze jakýkoli vzorkovník Markovského řetězce Monte Carlo přeměnit na interagující vzorkovač Monte Carlo Markovského řetězce. Tyto interagující vzorkovače Monte Carlo řetězce Markovova řetězce lze interpretovat jako způsob paralelního běhu sekvence vzorníků Markovova řetězce Monte Carlo. Například interakce simulované žíhání Algoritmy jsou založeny na nezávislých pohybech Metropolis-Hastings, které interagují postupně s mechanismem typu převzorkování výběru. Na rozdíl od tradičních metod Markovova řetězce Monte Carlo je parametr přesnosti této třídy interagujících vzorníků Monte Carlo Markovova řetězce je pouze souvisí s počtem interagujících vzorkovačů Monte Carlo v Markovově řetězci. Tyto pokročilé metodiky částic patří do třídy modelů částic Feynman-Kac,[11][12] také nazývané Sekvenční Monte Carlo nebo částicový filtr metody v Bayesovský závěr a zpracování signálu společenství.[13] Interakční metody Markovova řetězce Monte Carlo lze také interpretovat jako výběr mutace algoritmus genetických částic s mutacemi Markovova řetězce Monte Carlo.

Markovský řetězec kvazi-Monte Carlo (MCQMC).[14][15]

Výhoda sekvence s nízkou odchylkou namísto náhodných čísel pro jednoduché nezávislé vzorkování Monte Carlo je dobře známo.[16] Tento postup, známý jako Metoda kvazi-Monte Carla (QMC),[17] poskytuje integrační chybu, která se rozpadá vyšší rychlostí než ta, která se získá IID vzorkováním, pomocí Koksma-Hlawkova nerovnost. Empiricky umožňuje snížení jak chyby odhadu, tak doby konvergence řádově.[Citace je zapotřebí ] Metoda Array-RQMC kombinuje náhodnou simulaci kvazi-Monte Carla a Markovova řetězce řetězy současně takovým způsobem, aby empirické rozdělení států v kterémkoli daném kroku je lepší aproximací skutečné distribuce řetězce než u běžných MCMC.[18] V empirických experimentech se rozptyl průměru funkce státu někdy sbíhá rychlostí nebo dokonce rychlejší, místo Sazba Monte Carlo.[19]

Konvergence

Obvykle není těžké postavit Markovův řetězec s požadovanými vlastnostmi. Složitějším problémem je určit, kolik kroků je potřeba k konvergenci na stacionární distribuci v rámci přijatelné chyby.[20] Dobrý řetězec bude mít rychlé míchání: stacionární distribuce je dosažena rychle od libovolné polohy. Standardní empirickou metodou pro posouzení konvergence je spuštění několika nezávislých simulovaných Markovových řetězců a kontrola, zda je poměr rozpětí mezi řetězci k rozptylu uvnitř řetězce pro všechny vzorkované parametry blízký 1.[20][21]

Typicky vzorkování Markovova řetězce Monte Carlo může pouze přibližovat distribuci cíle, protože vždy existuje určitý zbytkový efekt výchozí polohy. Sofistikovanější algoritmy založené na Markovově řetězci v Monte Carlu, jako je vazba z minulosti může produkovat přesné vzorky, za cenu dalšího výpočtu a neomezeného (i když konečného očekávání) provozní doba.

Mnoho metod Monte Carlo s náhodnou chůzí se pohybuje kolem rovnovážného rozdělení v relativně malých krocích, aniž by měly tendenci postupovat stejným směrem. Tyto metody lze snadno implementovat a analyzovat, ale bohužel to může trvat dlouhou dobu, než chodec prozkoumá celý prostor. Chodítko se často zdvojnásobí a pokryje již zakrytou zem.

Další úvahy o konvergenci jsou na Markovova řetězová věta o limitu. Vidět [22] pro diskusi o teorii týkající se konvergence a stacionarity algoritmu Metropolis-Hastings.

Software

Několik softwarových programů poskytuje možnosti vzorkování MCMC, například:

Viz také

Reference

Citace

  1. ^ Kasim, M.F .; Bott, A.F.A .; Tzeferacos, P .; Lamb, D.Q .; Gregori, G .; Vinko, S.M. (Září 2019). Msgstr "Načítání polí z protonové radiografie bez zdrojových profilů". Fyzický přehled E. 100. arXiv:1905.12934. doi:10.1103 / PhysRevE.100.033208.
  2. ^ Gupta, Ankur; Rawlings, James B. (duben 2014). „Porovnání metod odhadu parametrů ve stochastických chemických kinetických modelech: příklady v biologii systémů“. AIChE Journal. 60 (4): 1253–1268. doi:10,1002 / aic.14409. PMC  4946376. PMID  27429455.
  3. ^ Viz Gill 2008.
  4. ^ Viz Robert & Casella 2004.
  5. ^ Banerjee, Sudipto; Carlin, Bradley P .; Gelfand, Alan P. (09.09.2014). Hierarchické modelování a analýza prostorových dat (Druhé vydání.). CRC Press. p. xix. ISBN  978-1-4398-1917-3.
  6. ^ Gilks, W. R .; Wild, P. (01.01.1992). "Adaptivní odmítnutí vzorkování pro vzorkování Gibbs". 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. (01.01.1995). "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. ^ Viz Stramer 1999.
  9. ^ Viz Green 1995.
  10. ^ Del Moral, Pierre (2013). Střední simulace pole pro integraci Monte Carlo. Chapman & Hall / CRC Press. p. 626.
  11. ^ Del Moral, Pierre (2004). Feynman-Kacovy vzorce. Genealogické a interagující aproximace částic. Springer. p. 575.
  12. ^ Del Moral, Pierre; Miclo, Laurent (2000). „Větvení a interakce aproximací částicových systémů Feynman-Kac vzorců s aplikacemi pro nelineární filtrování“. V Jacques Azéma; Michel Ledoux; Michel Émery; Marc Yor (eds.). Séminaire de Probabilités XXXIV (PDF). Přednášky z matematiky. 1729. s. 1–145. doi:10.1007 / bfb0103798. ISBN  978-3-540-67314-9.
  13. ^ Del Moral, Pierre (2006). "Sekvenční vzorníky Monte Carlo". Journal of the Royal Statistical Society. Řada B (statistická metodika). 68 (3): 411–436. arXiv:cond-mat / 0212648. doi:10.1111 / j.1467-9868.2006.00553.x.
  14. ^ Chen, S .; Dick, Josef; Owen, článek B. (2011). „Konzistence kvazi-Monte Carlova řetězce Markov v nepřetržitých státních prostorech“. Annals of Statistics. 39 (2): 673–701. doi:10.1214 / 10-AOS831.
  15. ^ Tribble, Seth D. (2007). Markovovy řetězové algoritmy Monte Carlo využívající zcela rovnoměrně distribuované jízdní sekvence (Disiss.) Stanfordská Univerzita. ProQuest  304808879.
  16. ^ Papageorgiou, Anargyros; Traub, J. F. (1996). „Bití Monte Carla“. Riziko. 9 (6): 63–65.
  17. ^ Sobol, Ilya M (1998). "K integraci kvazi-monte carlo". Matematika a počítače v simulaci. 47 (2): 103–112. doi:10.1016 / s0378-4754 (98) 00096-2.
  18. ^ L'Ecuyer, P .; Lécot, C .; Tuffin, B. (2008). „Randomizovaná metoda simulace kvazi-Monte Carla pro Markovovy řetězce“ (PDF). Operační výzkum. 56 (4): 958–975. doi:10.1287 / opre.1080.0556.
  19. ^ L'Ecuyer, P .; Munger, D .; Lécot, C .; Tuffin, B. (2018). "Metody třídění a konvergenční sazby pro Array-RQMC: Některá empirická srovnání". Matematika a počítače v simulaci. 143: 191–201. doi:10.1016 / j.matcom.2016.07.010.
  20. ^ A b Gelman, A .; Rubin, D.B. (1992). "Odvození z iterativní simulace pomocí více sekvencí (s diskusí)" (PDF). Statistická věda. 7 (4): 457–511. Bibcode:1992StaSc ... 7..457G. doi:10.1214 / ss / 1177011136.
  21. ^ Cowles, M.K .; Carlin, B.P. (1996). „Diagnostika konvergence Markovského řetězce Monte Carlo: srovnávací přehled“. Journal of the American Statistical Association. 91 (434): 883–904. CiteSeerX  10.1.1.53.3445. doi:10.1080/01621459.1996.10476956.
  22. ^ Hill, S. D .; Spall, J. C. (2019). „Stacionarita a konvergence algoritmu Metropolis-Hastings: Pohledy do teoretických aspektů“. Časopis IEEE Control Systems. 39 (1): 56–67. doi:10.1109 / MCS.2018.2876959.
  23. ^ „závislosti a inspirace na softwaru greta“. greta-stats.org/. Citováno 2020-04-13.
  24. ^ Enright, AJ; Van Dongen, S; Ouzounis, CA (1. dubna 2002). „Efektivní algoritmus pro rozsáhlou detekci proteinových rodin“. Výzkum nukleových kyselin. 30 (7): 1575–84. doi:10.1093 / nar / 30.7.1575. PMC  101833. PMID  11917018.
  25. ^ Azad, A; Pavlopoulos, GA; Ouzounis, CA; Kyrpides, NC; Buluç, A (6. dubna 2018). „HipMCL: vysoce výkonná paralelní implementace Markovova klastrového algoritmu pro rozsáhlé sítě“. Výzkum nukleových kyselin. 46 (6): e33. doi:10.1093 / nar / gkx1313. PMC  5888241. PMID  29315405.

Zdroje

Další čtení