Markov-kedjan Monte Carlo

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 maj 2021; kontroller kräver 2 redigeringar .

Inom statistik är Markov-kedjans Monte Carlo- metoder (eng. MCMC)  en klass av samplingsalgoritmer som modellerar en viss sannolikhetsfördelning . Genom att konstruera en Markov-kedja som har målfördelningen som sin jämvikt kan man få ett prov med samma fördelning genom att skriva ner kedjans tillstånd. Ju fler steg som kommer att användas, desto närmare kommer provfördelningen att vara målet. Olika algoritmer används för att bygga kretsar, till exempel Metropolis-Hastings-algoritmen.

Användningsområden

MCMCs användes ursprungligen för att lösa flera integraler numeriskt , såsom i Bayesiansk statistik , beräkningsfysik [1] , beräkningsbiologi [2] och beräkningslingvistik [3] [4] .

De senaste framstegen inom MCMC har gjort det möjligt att utföra beräkningar i stora hierarkiska modeller som kräver integration över hundratals och tusentals variabler [5] .

Vid simulering av sällsynta händelser används MCMC-metoder för att generera prover som gradvis fyller i området för sällsynta fel.

Allmän definition

Monte Carlo-metoder med Markov-kedjor skapar prov baserat på en vald kontinuerlig slumpvariabel med en känd fördelningsdensitetsfunktion . Dessa prover kan användas för att utvärdera integralen över den kvantiteten med hjälp av medelvärdet eller variansen .

I praktiken byggs vanligtvis en ensemble av kretsar, utgående från en uppsättning godtyckliga punkter som är tillräckligt långt från varandra. Dessa kedjor är stokastiska "walk"-processer där rörelserna sker slumpmässigt, enligt en algoritm. Denna algoritm letar efter regioner med det största integralvärdet och tilldelar dem de högsta sannolikheterna.

Monte Carlo slumpmässiga promenadmetoder är en av typerna av slumpmässig simulering ( Monte Carlo-metoder ). Observera att de slumpmässiga urvalen av integranden som används i Monte Carlo-metoderna är statistiskt oberoende . I MCMC är de autokorrelerade . Korrelationen av prover leder till behovet av att använda Central Limit Theorem för Markov-kedjor vid uppskattning av medelfel .

Dessa algoritmer skapar Markov-kedjor vars jämviktsfördelning är proportionell mot en given funktion.

Minskad korrelation

MCMC-metoder är bättre på att lösa flerdimensionella problem än Monte Carlo-algoritmer, men när antalet dimensioner ökar börjar de också drabbas av " dimensionernas förbannelse ". Regionerna med hög sannolikhet tenderar att sträcka ut sig och försvinna in i en ökande volym av utrymme, vilket har liten effekt på integralens värde. Detta problem kan lösas genom att minska vandringssteget för att inte gå utanför högsannolikhetsområdet. En sådan lösning är dock ganska lång (många steg krävs för att uppnå ett korrekt resultat) och leder till hög autokorrelation. Mer sofistikerade algoritmer, som Hamiltonian Monte Carlo och Wang-Landau algoritmer , använder olika sätt för att minska autokorrelation genom att hålla vandringsprocessen i de regioner som har störst inflytande på integralens värde. Dessa algoritmer är mycket mer komplexa både i termer av teorin de förlitar sig på och i termer av tillämpning, men de konvergerar snabbare.

Exempel

Random walk

• Metropolis-Hastings-algoritm : Denna metod genererar en Markov-kedja med en given densitet och nystegsfiltrering. I själva verket är detta ett allmänt schema, varav speciella fall är: den allra första och enkla MCMC (Metropolis-algoritmen), såväl som alternativen nedan.
  • Gibbs sampling : Denna metod kräver att alla villkorliga distributioner av målfördelningen är kända. Om slutsatsen från fullständigt villkorade distributioner inte är omedelbar, används andra Gibbs-samplare (se t.ex. [6] [7] [8] ). Gibbs sampling är populärt eftersom det inte kräver någon tidigare "tuning".
  • Langevin Monte Carlo och andra metoder baserade på gradienten (och möjligen andraderivatan) av logaritmen för måldensiteten. Målet med dessa metoder är att föreslå de mest rimliga stegen mot en högre sannolikhetstäthet [9] .
  • Pseudo-Marginal Metropolis-Hastings: Denna metod ersätter målfördelningens täthet med dess opartiska skattare . Metoden är tillämpbar när måldensiteten inte specificeras analytiskt (t.ex. i modeller med latenta variabler).
• Layered sampling : Denna metod är baserad på principen att ett prov med en viss fördelning kan konstrueras genom att likformigt ta prover av området underplotten av densitetsfunktionen för den fördelningen. Denna metod ersätter enhetlig provtagning i vertikal riktning med enhetlig provtagning av det horisontella "skiktet" som definieras av den aktuella vertikala positionen.
• Metropolis-algoritm för flera försök : Detta är en variant av Metropolis-Hastings-algoritmen som tillåter flera försök vid varje punkt. Genom att ta större steg vid varje iteration hjälper algoritmen till att bli av med "dimensionernas förbannelse" [10] [11] .

• Reversible-jump-metod: en annan version av Metropolis-Hastings-algoritmen som tillåter ändringar i rymddimensionen [12] . Sådana Markov-kedjemetoder har använts under lång tid i tillämpad statistisk fysik , där det i vissa problem fanns en fördelning som kallas " grand canonical ensemble " (till exempel med ett variabelt antal molekyler i ett slutet kärl). Den reversibla hoppmetoden är tillämpbar när man använder MCMC- eller Gibbs-sampling på icke-parametriska Bayesianska modeller, där antalet blandningskomponenter (kluster) automatiskt förutsägs från data (t.ex. Dirichlet-processen eller "kinesisk restaurangprocess").
• Hamiltonsk (hybrid) Monte Carlo-metod: Denna metod försöker undvika slumpmässig promenad genom att introducera en extra "momentvektor" och tillämpa Hamiltonsk dynamik där den potentiella energifunktionen  är måltätheten. Momentprover kasseras efter provtagning. Det slutliga resultatet av algoritmen är att rörelsen genom provrummet sker i stora steg. Således är de mindre korrelerade och konvergerar till målfördelningen snabbare.

Metoder för att interagera partiklar

Interaktiva MSMS-metoder är en klass av medelfältspartikelmetoder för att erhålla prover av pseudoslumptal från en sekvens av sannolikhetsfördelningar med en ökande nivå av provtagningskomplexitet [13] .

Dessa probabilistiska modeller inkluderar:

• banrumstillståndsmodeller med ökande tidshorisont
• posterior (med avseende på partiella observationer) distributioner
• ökande nivå av restriktioner för villkorade utdelningar
• sjunkande temperaturdiagram associerade med Boltzmann-Gibbs distributioner
• och mycket mer

I allmänhet kan alla MCMC-samplare göras interaktiva. Dessa kan i sin tur användas som ett sätt att köra en sekvens av vanliga provtagare parallellt. Till exempel är interaktiva simuleringsglödgningsalgoritmer baserade på oberoende Metropolis-Hastings-rörelser som sekventiellt interagerar med den selektiva omsamplingsmekanismen. I motsats till de klassiska MCMC-metoderna beror noggrannhetsparametern för interaktiva provtagare här endast på deras antal. Interagerande partikelmetoder tillhör klassen av Feynman-Katz-partikelmodeller [14] [15] , även kallade "sekventiella Monte Carlo" eller "partikelfiltermetoder" i Bayesiansk slutledningsteori och signalbehandling [16] . Interaktiva MSMS-metoder kan också förstås som cykler i den genetiska partikelalgoritmen med mutationer i form av klassiska MSMS-mutationer.

Markov Chain Quasi-Monte Carlo (MCQMC) [17] [18]

Användningen av låga diskrepanssekvenser istället för slumptal för enkel oberoende Monte Carlo-sampling har klara fördelar [19] . En sådan ersättning används i quasi-Monte Carlo-metoden ( QMC ) [20] . Enligt Coxma-Hlavka-olikheten är integrationsfelet i denna metod mycket mindre än vid sampling av oberoende identiskt fördelade slumpvariabler (IID). Detta gör det möjligt att reducera både uppskattningsfelet och konvergenstiden med en storleksordning.

Array-RQMC-metoden introducerar QMC-baserad Markov-kedjemodellering genom att simulera kedjor samtidigt. Vid varje steg ger den empiriska fördelningen av dessa tillstånd en mer exakt approximation av fördelningsfunktionen än när man använder MCMC [21] . I empiriska experiment har konvergensen av variansen av medeltillståndsfunktionen ibland en hastighet av storleksordningen eller till och med snabbare än den för Monte Carlo-metoden [22] .

Konvergens

Det är vanligtvis inte svårt att konstruera en Markov-kedja med de egenskaper som krävs. Det är svårare att avgöra hur många steg som krävs för att konvergera till en stationär fördelning med ett acceptabelt fel [23] . En bra kedja har blandningsegenskapen: en stationär fördelning uppnås snabbt för alla startpositioner. Den klassiska empiriska metoden för att uppnå konvergens är att köra flera oberoende modellerade Markov-kedjor och kontrollera att varianserna utanför och inuti kedjan är ungefär lika [23] [24] .

Vanligtvis kan MCMC-sampling endast approximera målfördelningen, eftersom det alltid finns en kvarvarande effekt av startpositionen. Mer komplexa algoritmer baserade på MCMC, såsom koppling från det förflutna, kan ta emot korrekta sampel, vilket påverkar antalet beräkningar och den tid som spenderas.

Många Monte Carlo slumpmässiga vandringsmetoder rör sig i små steg, utgående från en jämviktsfördelning utan någon tendens att spola en väg i en riktning. Dessa metoder är lätta att tillämpa och analysera, men det tar lång tid att utforska hela utrymmet med hjälp av en promenad (vandring går ofta tillbaka till redan genomkorsade områden).

Ytterligare överväganden om konvergens finns i Central Limit Theorem för Markov-kedjor, se [25] för en diskussion av teorin relaterad till konvergensen och stationariteten hos Metropolis-Hastings-algoritmen.

Programvara

Programvara för att arbeta med MSMS-sampling:

• paket som använder dialekter av modellspråket BUGS
  • WinBUGS / OpenBUGS / MultiBUGS
  • JAGS
  • VIG
• greta , Bayesianskt statistiskt modelleringsspråk
• MCSim
• PyMC3
• pymcmcstat
• R (programmeringsspråk) med adaptMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan, etc.
• Stan
• TensorFlow Probability (probabilistiskt programmeringsbibliotek inbyggt i TensorFlow )
• MCL (klusteralgoritm för grafer och HipMCL (alternativ version)) [26]
• emcee ( Python- implementering av affin invariant MCMC ensemble sampler )
• Keanu Java-bibliotek för multipurpose probabilistisk programmering
• Zeus Implementering av Layered Ensemble Sampling i Python
• Turing.jl- paket för multipurpose probabilistisk programmering i Julia
• Mamba.jl ramverk för msms-metoden i Julia

Anteckningar

Citat

1. ↑ Kasim, M.F.; Bott, A.F.A.; Tzeferacos, P.; Lamm, DQ; Gregori, G.; Vinko, SM Att hämta fält från protonröntgen utan källprofiler  (engelska)  // Physical Review E  : journal. - 2019. - September ( vol. 100 ). - doi : 10.1103/PhysRevE.100.033208 . - arXiv : 1905.12934 .
2. ↑ Gupta, Ankur; Rawlings, James B. Jämförelse av parameteruppskattningsmetoder i stokastiska kemiska kinetiska modeller: exempel i systembiologi  //  AIChE Journal : journal. - 2014. - April ( vol. 60 , nr 4 ). - P. 1253-1268 . - doi : 10.1002/aic.14409 . — PMID 27429455 .
3. ↑ Se Gill 2008.
4. ↑ Se Robert & Casella 2004.
5. ↑ Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. Hierarkisk modellering och analys för rumsliga data  . — För det andra. - CRC Press , 2014. - P. xix. — ISBN 978-1-4398-1917-3 .
6. ↑ Gilks, WR; Wild, P. Adaptive Rejection Sampling for Gibbs Sampling  //  Journal of the Royal Statistical Society. Serie C (tillämpad statistik) : journal. - 1992. - 1 januari ( vol. 41 , nr 2 ). - s. 337-348 . - doi : 10.2307/2347565 . — .
7. ↑ Gilks, WR; Bästa, NG; Tan, KKC Adaptive Rejection Metropolis Sampling inom Gibbs Sampling  //  Journal of the Royal Statistical Society. Serie C (tillämpad statistik) : journal. - 1995. - 1 januari ( vol. 44 , nr 4 ). - s. 455-472 . - doi : 10.2307/2986138 . — .
8. ↑ Martino, L.; Read, J.; Luengo, D. Oberoende dubbelt adaptiv avstötningsmetropolsampling inom Gibbs sampling  // IEEE  -transaktioner på signalbehandling : journal. - 2015. - 1 juni ( vol. 63 , nr 12 ). - P. 3123-3138 . — ISSN 1053-587X . - doi : 10.1109/TSP.2015.2420537 . - . - arXiv : 1205.5494 .
9. ↑ Se Stramer 1999.
10. ↑ Liu, Jun S.; Liang, Faming; Wong, Wing Hung. Multiple-Try Method and Local Optimization in Metropolis Sampling  //  Journal of the American Statistical Association  : tidskrift. - 2000. - 1 mars ( vol. 95 , nr 449 ). - S. 121-134 . — ISSN 0162-1459 . - doi : 10.1080/01621459.2000.10473908 .
11. ↑ Martino, Luca; Läs, Jesse. Om flexibiliteten i utformningen av multipla försök Metropolis-scheman  //  Computational Statistics : journal. - 2013. - 11 juli ( vol. 28 , nr 6 ). - P. 2797-2823 . — ISSN 0943-4062 . - doi : 10.1007/s00180-013-0429-2 . - arXiv : 1201.0646 .
12. ↑ Se Green 1995.
13. ↑ Del Moral, Pierre. Medelfältsimulering för Monte Carlo - integration  . - Chapman & Hall/CRC Press, 2013. - S. 626. . - Monografier om statistik och tillämpad sannolikhet.
14. ↑ Del Moral, Pierre. Feynman-Kac formel.  Genealogiska och interagerande partikelapproximationer . - Springer, 2004. - S. 575. . - "Serie: Sannolikhet och tillämpningar".
15. ↑ Del Moral, Pierre; Miclo, Laurent. Séminaire de Probabilités XXXIV / Jacques Azéma, Michel Ledoux, Michel Émery, Marc Yor. - 2000. - T. 1729. - S. 1-145. — (Föreläsningsanteckningar i matematik). — ISBN 978-3-540-67314-9 . - doi : 10.1007/bfb0103798 .
16. ↑ Del Moral, Pierre. Sekventiella Monte Carlo-samplare - P. Del Moral - A. Doucet - A. Jasra - 2006 - Journal of the Royal Statistical Society: Series B (Statistical Methodology) - Wiley Online Library  (engelska)  // Journal of the Royal Statistical Society. Serie B (Statistisk metod) : journal. - 2006. - Vol. 68 , nr. 3 . - s. 411-436 . doi : 10.1111 / j.1467-9868.2006.00553.x . - arXiv : cond-mat/0212648 .
17. ↑ Chen, S.; Dick, Joseph; Owen, Art B. Konsekvens av Markov-kedjan kvasi-Monte Carlo på kontinuerliga tillståndsrum  (engelska)  // Annals of Statistics : journal. - 2011. - Vol. 39 , nr. 2 . - s. 673-701 . - doi : 10.1214/10-AOS831 .
18. ↑ Tribble, Seth D. (2007). Markov-kedjan Monte Carlo-algoritmer använder helt enhetligt fördelade körsekvenser (Diss.). Stanford University. Mall:ProQuest .
19. ↑ Papageorgiou, Anargyros; Traub, JF Slår Monte Carlo // Risk. - 1996. - T. 9 , nr 6 . - S. 63-65 .
20. ↑ Sobol, Ilya M. Om quasi-monte carlo integrationer // Matematik och datorer i simulering. - 1998. - T. 47 , nr 2 . - S. 103-112 . - doi : 10.1016/s0378-4754(98)00096-2 .
21. ↑ L'Ecuyer, P.; Lecot, C.; Tuffin, B. En randomiserad Quasi-Monte Carlo-simuleringsmetod för Markov-kedjor   // Operations Research : journal. - 2008. - Vol. 56 , nr. 4 . - P. 958-975 . doi : 10.1287 / opre.1080.0556 .
22. ↑ L'Ecuyer, P.; Munger, D.; Lecot, C.; Tuffin, B. Sorteringsmetoder och konvergenshastigheter för Array-RQMC: Några empiriska jämförelser  //  Mathematics and Computers in Simulation : journal. - 2018. - Vol. 143 . - S. 191-201 . - doi : 10.1016/j.matcom.2016.07.010 .
23. ↑ 1 2 Gelman, A.; Rubin, DB Slutledning från iterativ simulering med flera sekvenser (med diskussion  )  // Statistical Science : journal. - 1992. - Vol. 7 , nr. 4 . - s. 457-511 . - doi : 10.1214/ss/1177011136 . - .
24. ↑ Cowles, M.K.; Carlin, BP Markovkedjan Monte Carlo konvergensdiagnostik: en jämförande recension  //  Journal of the American Statistical Association  : journal. - 1996. - Vol. 91 , nr. 434 . - P. 883-904 . - doi : 10.1080/01621459.1996.10476956 .
25. ↑ Hill, SD; Spall, JC Stationarity and Convergence of the Metropolis-Hastings Algorithm: Insights into Theoretical Aspects  //  IEEE Control Systems Magazine: tidskrift. - 2019. - Vol. 39 , nr. 1 . - S. 56-67 . - doi : 10.1109/MCS.2018.2876959 .
26. ↑ Azad, A; Pavlopoulos, G.A.; Ouzounis, CA; Kyrpides, N.C.; Buluç, A. HipMCL: en högpresterande parallell implementering av Markov-klustringsalgoritmen för storskaliga nätverk  //  Nucleic Acids Research : journal. - 2018. - 6 april ( vol. 46 , nr 6 ). —P.e33 . _ doi : 10.1093 / nar/gkx1313 . — PMID 29315405 .

Källor

• Christophe Andrieu, Nando De Freitas, Arnaud Doucet och Michael I. Jordan An Introduction to MCMC for Machine Learning , 2003
• Asmussen, Sören; Glynn, Peter W. Stokastisk simulering: Algoritmer och  analys . - Springer, 2007. - Vol. 57. - (Stokastisk modellering och tillämpad sannolikhet).
• Atzberger, P. An Introduction to Monte-Carlo Methods (länk ej tillgänglig) . Hämtad 4 maj 2020. Arkiverad från originalet 20 februari 2009. (obestämd) 
• Berg, Bernd A. Markov Kedja Monte Carlo-simuleringar och deras statistiska analys  . — World Scientific , 2004.
• Bolstad, William M. Understanding Computational Bayesian Statistics  . - Wiley, 2010. - ISBN 978-0-470-04609-8 .
• Casella, George; George, Edward I. Explaining the Gibbs sampler // The American Statistician. - 1992. - T. 46 , nr 3 . - S. 167-174 . - doi : 10.2307/2685208 . — .
• Gelfand, AE; Smith, AFM Sampling-Based Approaches to Calculating Marginal Densities  //  Journal of the American Statistical Association  : journal. - 1990. - Vol. 85 , nr. 410 . - s. 398-409 . - doi : 10.1080/01621459.1990.10476213 .
• Gelman, Andrew; Carlin, John B.; Stern, Hal S.; Rubin, Donald B. Bayesiansk dataanalys. — 1:a. - Chapman & Hall , 1995. (Se kapitel 11.)
• Geman, S.; Geman, D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images  // IEEE-transaktioner på mönsteranalys och  maskinintelligens : journal. - 1984. - Vol. 6 , nr. 6 . - s. 721-741 . - doi : 10.1109/TPAMI.1984.4767596 .
• Gilks, W.R.; Richardson, S.; Spiegelhalter, DJ Markov Chain Monte Carlo i praktiken. - Chapman & Hall /CRC, 1996.
• Gill, Jeff. Bayesianska metoder: ett samhälls- och beteendevetenskapligt  tillvägagångssätt . — 2:a. - Chapman & Hall / CRC, 2008. - ISBN 978-1-58488-562-7 .
• Green, PJ Reversible-jump Markov-kedjan Monte Carlo-beräkning och Bayesian modellbestämning  (engelska)  // Biometrika  : journal. - 1995. - Vol. 82 , nr. 4 . - s. 711-732 . - doi : 10.1093/biomet/82.4.711 .
• Neal, Radford M. Slice Sampling // Annals of Statistics. - 2003. - T. 31 , nr 3 . - S. 705-767 . - doi : 10.1214/aos/1056562461 . — .
• Neal, Radford M. Probabilistic Inference Using Markov Chain Monte Carlo Methods (1993). (obestämd)
• Robert, Christian P.; Casella, G. Monte Carlo Statistiska metoder . — 2:a. - Springer, 2004. - ISBN 978-0-387-21239-5 .
• Rubinstein, R.Y.; Kroese, D.P.Simulering och Monte Carlo-metoden. — 2:a. - Wiley , 2007. - ISBN 978-0-470-17794-5 .
• Smith, RL Effektiva Monte Carlo-procedurer för att generera poäng enhetligt fördelade över avgränsade regioner   // Operations Research : journal. - 1984. - Vol. 32 , nr. 6 . - P. 1296-1308 . doi : 10.1287 / opre.32.6.1296 .
• Spall, JC Uppskattning via Markov Chain Monte Carlo // IEEE Control Systems Magazine. - 2003. - April ( vol. 23 , nr 2 ). - S. 34-45 . - doi : 10.1109/mcs.2003.1188770 .
• Stramer, O.; Tweedie, R. Langevin-Type Models II: Self-targeting Candidates for MCMC Algorithms  //  Methodology and Computing in Applied Probability: journal. - 1999. - Vol. 1 , nej. 3 . - s. 307-328 . - doi : 10.1023/A:1010090512027 .

Litteratur

• Diaconis, Persi. Markovkedjan Monte Carlo revolution  // Bulletin of the American Mathematical Society  . - 2009. - April ( vol. 46 , nr 2 ). - S. 179-205 . - doi : 10.1090/s0273-0979-08-01238-x .
• Press, W.H.; Teukolsky, SA; Vetterling, WT & Flannery, BP (2007), avsnitt 15.8. Markov Chain Monte Carlo , Numeriska recept: The Art of Scientific Computing (3:e upplagan), Cambridge University Press , ISBN 978-0-521-88068-8 
• Richey, Matthew. The Evolution of Markov Chain Monte Carlo Methods  //  The American Mathematical Monthly . - 2010. - Maj ( vol. 117 , nr 5 ). - s. 383-413 . doi : 10.4169 / 000298910x485923 .

Länkar

• MCMC-provtagning och andra metoder i en grundläggande översikt , av Alexander Mantzaris ( originallänk — nu trasig ).
• PyMC  - Python-modul som implementerar Bayesianska statistiska modeller och anpassningsalgoritmer, inklusive Markov-kedjan Monte Carlo.
• IA2RMS är en Matlab-kod för "Independent Double Adaptive Rejection Metropolis Sampling"-metoden, Martino, Read & Luengo (2015 ), för att dra från de fullvillkorade densiteterna i en Gibbs-sampler.