Markov kæde Monte Carlo

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 13. maj 2021; checks kræver 2 redigeringer .

I statistik er Markov-kædens Monte Carlo- metoder (eng. MCMC) en klasse af samplingsalgoritmer , der modellerer en vis sandsynlighedsfordeling . Ved at konstruere en Markov-kæde , der har målfordelingen som sin ligevægt, kan man opnå en prøve med samme fordeling ved at nedskrive kædens tilstande. Jo flere trin der vil blive brugt, jo tættere vil prøvefordelingen være på målet. Forskellige algoritmer bruges til at bygge kredsløb, for eksempel Metropolis-Hastings-algoritmen. ${\displaystyle}$

Anvendelsesområder

MCMC'er blev oprindeligt brugt til at løse flere integraler numerisk , såsom i Bayesiansk statistik , beregningsfysik [1] , beregningsbiologi [2] og beregningslingvistik [3] [4] .

Nylige fremskridt inden for MCMC har gjort det muligt at udføre beregninger i store hierarkiske modeller , der kræver integration over hundreder og tusinder af variabler [5] .

I sjældne hændelsessimuleringer bruges MCMC-metoder til at generere prøver, der gradvist udfylder området med sjældne fejl.

Generel definition

Monte Carlo - metoder med Markov - kæder skaber prøver baseret på en valgt kontinuerlig tilfældig variabel med en kendt fordelingstæthedsfunktion . Disse prøver kan bruges til at evaluere integralet over denne mængde ved hjælp af middelværdien eller variansen .

I praksis er et ensemble af kredsløb normalt bygget, startende fra et sæt af vilkårlige punkter, der er tilstrækkeligt langt fra hinanden. Disse kæder er stokastiske "walk"-processer, hvor bevægelserne sker tilfældigt ifølge en algoritme. Denne algoritme leder efter regioner med den største integralværdi og tildeler dem de højeste sandsynligheder.

Monte Carlo tilfældige gangmetoder er en af typerne af tilfældig simulering ( Monte Carlo metoder ). Bemærk, at de tilfældige prøver af integranden, der anvendes i Monte Carlo-metoderne, er statistisk uafhængige . I MCMC er de autokorrelerede . Korrelationen af prøver fører til behovet for at bruge Central Limit Theorem for Markov-kæder, når man estimerer middelfejlen .

Disse algoritmer skaber Markov-kæder, hvis ligevægtsfordeling er proportional med en given funktion.

Fald i korrelation

MCMC-metoder er bedre til at løse multidimensionelle problemer end Monte Carlo-algoritmer, men efterhånden som antallet af dimensioner stiger, begynder de også at lide af " dimensionernes forbandelse ". Regionerne med høj sandsynlighed har en tendens til at strække sig ud og forsvinde i et stigende rumvolumen, hvilket har ringe indflydelse på integralets værdi. Dette problem kan løses ved at reducere gåtrinnet for ikke at gå ud over højsandsynlighedsområdet. En sådan løsning er dog ret lang (mange trin er nødvendige for at opnå et nøjagtigt resultat) og fører til høj autokorrelation. Mere sofistikerede algoritmer, såsom Hamiltonian Monte Carlo og Wang-Landau algoritmer , bruger forskellige måder til at reducere autokorrelation ved at holde vandreprocessen i de regioner med størst indflydelse på værdien af integralet. Disse algoritmer er meget mere komplekse både med hensyn til den teori, de er afhængige af, og med hensyn til anvendelse, men de konvergerer hurtigere.

Eksempler

Tilfældig gåtur

Metropolis-Hastings-algoritme : Denne metode genererer en Markov-kæde ved hjælp af en given tæthed og ny trinfiltrering. Faktisk er dette en generel ordning, hvis særlige tilfælde er: den allerførste og enkle MCMC (Metropolis-algoritme), såvel som alternativerne nedenfor.
- Gibbs sampling : Denne metode kræver, at alle betingede fordelinger af målfordelingen er kendt. Hvis slutningen fra fuldt betingede fordelinger ikke er øjeblikkelig, så bruges andre Gibbs samplere (se f.eks . [6] [7] [8] ). Gibbs sampling er populær, fordi den ikke kræver nogen forudgående "tuning".
- Langevin Monte Carlo og andre metoder baseret på gradienten (og muligvis den anden afledede) af logaritmen af måltætheden. Målet med disse metoder er at foreslå de mest plausible trin mod en højere sandsynlighedstæthed [9] .
- Pseudo-Marginal Metropolis-Hastings: Denne metode erstatter tætheden af målfordelingen med dens upartiske estimator . Metoden er anvendelig, når måltætheden ikke er specificeret analytisk (f.eks. i modeller med latente variable).
Lagdelt prøveudtagning : Denne metode er baseret påprincippet om, at en prøve af en vis fordeling kan konstrueres ved ensartet prøveudtagning af området under plottet af tæthedsfunktionen af denne fordeling. Denne metode erstatter ensartet prøveudtagning i lodret retning med ensartet prøvetagning af det vandrette "lag" defineret af den aktuelle lodrette position.
Multiple-try Metropolis-algoritme: Dette er en variation af Metropolis-Hastings-algoritmen, der tillader flere forsøg på hvert punkt. Ved at tage større skridt ved hver iteration hjælper algoritmen med at slippe af med "dimensionernes forbandelse" [10] [11] .

Reversible-jump-metode: en anden version af Metropolis-Hastings-algoritmen, der tillader ændringer i rumdimensionen [12] . Sådanne Markov-kædemetoder har været brugt i lang tid i anvendt statistisk fysik , hvor der i nogle problemer var en fordeling kaldet " grand canonical ensemble " (for eksempel med et variabelt antal molekyler i et lukket kar). Den reversible hop-metode er anvendelig, når der bruges MCMC- eller Gibbs-sampling på ikke-parametriske Bayesianske modeller, hvor antallet af blandingskomponenter (klynger) automatisk forudsiges ud fra dataene (f.eks. Dirichlet-proces eller "kinesisk restaurant-proces").
Hamiltonsk (hybrid) Monte Carlo-metode: Denne metode forsøger at undgå tilfældig gang ved at indføre en ekstra "momentvektor" og anvende Hamiltonsk dynamik, hvor den potentielle energifunktion er måltætheden. Momentprøver kasseres efter prøveudtagning. Det endelige resultat af algoritmen er, at bevægelsen gennem prøverummet udføres i store trin. De er således mindre korrelerede og konvergerer hurtigere til målfordelingen.

Metoder til interagerende partikler

Interaktive MSMS-metoder er en klasse af middelfeltspartikelmetoder til at opnå prøver af pseudo-tilfældige tal fra en sekvens af sandsynlighedsfordelinger med et stigende niveau af prøveudtagningskompleksitet [13] .

Disse probabilistiske modeller inkluderer:

sti rumtilstandsmodeller med stigende tidshorisont
posteriore (med hensyn til partielle observationer) fordelinger
stigende niveau af restriktioner for betingede fordelinger
faldende temperaturplot forbundet med Boltzmann-Gibbs-fordelinger
og meget mere

Generelt kan alle MCMC-samplere gøres interaktive. Disse kan igen bruges som en måde at køre en sekvens af almindelige samplere parallelt. For eksempel er interaktive simulerings-annealing-algoritmer baseret på uafhængige Metropolis-Hastings-bevægelser, der sekventielt interagerer med den selektive resampling-mekanisme. I modsætning til de klassiske MCMC-metoder afhænger nøjagtighedsparameteren for interaktive samplere her kun af deres antal. Interagerende partikelmetoder tilhører klassen af Feynman-Katz-partikelmodeller [14] [15] , også kaldet "sekventielle Monte Carlo" eller "partikelfiltermetoder" i Bayesiansk inferensteori og signalbehandling [16] . Interaktive MSMS-metoder kan også forstås som cyklusser i den genetiske partikelalgoritme med mutationer i form af klassiske MSMS-mutationer.

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

Brugen af sekvenser med lav uoverensstemmelse i stedet for tilfældige tal til simpel uafhængig Monte Carlo-sampling har klare fordele [19] . En sådan erstatning bruges i quasi-Monte Carlo ( QMC ) metoden [20] . Ifølge Coxma-Hlavka-uligheden er integrationsfejlen i denne metode meget mindre end ved sampling af uafhængige identisk distribuerede tilfældige variabler (IID). Dette gør det muligt at reducere både estimeringsfejlen og konvergenstiden med en størrelsesorden.

Array-RQMC-metoden introducerer QMC-baseret Markov-kædemodellering ved at simulere kæder samtidigt. Ved hvert trin giver den empiriske fordeling af disse tilstande en mere nøjagtig tilnærmelse til fordelingsfunktionen end ved brug af MCMC [21] . I empiriske eksperimenter har konvergensen af variansen af middeltilstandsfunktionen nogle gange en hastighed af størrelsesordenen eller endda hurtigere end Monte Carlo-metoden [22] . $n$ $n$ $O(n^{-2})$ $O(n^{-1})$

Konvergens

Det er normalt ikke svært at konstruere en Markov-kæde med de nødvendige egenskaber. Det er sværere at bestemme, hvor mange trin der kræves for at konvergere til en stationær fordeling med en acceptabel fejl [23] . En god kæde har blandeegenskaben: En stationær fordeling opnås hurtigt for enhver startposition. Den klassiske empiriske metode til at opnå konvergens er at køre flere uafhængigt modellerede Markov-kæder og kontrollere, at varianserne uden for og inde i kæden er omtrent lige store [23] [24] .

Typisk kan MCMC-prøvetagning kun tilnærme målfordelingen, da der altid er en resteffekt af startpositionen. Mere komplekse algoritmer baseret på MCMC, såsom kobling fra fortiden, kan modtage nøjagtige prøver, hvilket påvirker antallet af beregninger og tidsforbruget.

Mange Monte Carlo tilfældige gangmetoder bevæger sig i små trin, startende fra en ligevægtsfordeling uden tendens til at skyde en vej i én retning. Disse metoder er nemme at anvende og analysere, men det tager lang tid at udforske hele rummet ved hjælp af en gåtur (vandring vender ofte tilbage til allerede gennemkørte områder).

Yderligere overvejelser om konvergens er indeholdt i Central Limit Theorem for Markov-kæder, se [25] for en diskussion af teorien relateret til konvergensen og stationariteten af Metropolis-Hastings-algoritmen.

Software

Software til at arbejde med MSMS-sampling:

pakker, der bruger dialekter af BUGS-modelsproget
- WinBUGS / OpenBUGS / MultiBUGS
- JAGS
- FRIGTIG
greta , Bayesiansk statistisk modelleringssprog
MCSim
PyMC3
pymcmcstat
R (programmeringssprog) med adaptMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan osv.
Stan
TensorFlow Probability (sandsynlighedsprogrammeringsbibliotek indbygget i TensorFlow )
MCL (klyngealgoritme til grafer og HipMCL (alternativ version)) [26]
emcee ( Python implementering af affin invariant MCMC ensemble sampler )
Keanu Java-bibliotek til multipurpose probabilistisk programmering
Zeus Implementering af Layered Ensemble Sampling i Python
Turing.jl- pakke til multipurpose probabilistisk programmering i Julia
Mamba.jl framework til msms metode i Julia

Noter

Citater

↑ Kasim, M.F.; Bott, A.F.A.; Tzeferacos, P.; Lam, DQ; Gregory, G.; Vinko, SM Hentning af felter fra protonradiografi uden kildeprofiler (engelsk) // Physical Review E : journal. - 2019. - September ( bind 100 ). - doi : 10.1103/PhysRevE.100.033208 . - arXiv : 1905.12934 .
↑ Gupta, Ankur; Rawlings, James B. Sammenligning af parameterestimeringsmetoder i stokastiske kemiske kinetiske modeller: Eksempler i systembiologi // AIChE Journal: tidsskrift. - 2014. - April ( bind 60 , nr. 4 ). - S. 1253-1268 . - doi : 10.1002/aic.14409 . — PMID 27429455 .
↑ Se Gill 2008.
↑ Se Robert & Casella 2004.
↑ Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. Hierarkisk modellering og analyse for rumlige data . - Sekund. - CRC Press , 2014. - P. xix. — ISBN 978-1-4398-1917-3 .
↑ Gilks, WR; Wild, P. Adaptive Rejection Sampling for Gibbs Sampling // Journal of the Royal Statistical Society. Serie C (Anvendt statistik) : journal. - 1992. - 1. januar ( bind 41 , nr. 2 ). - S. 337-348 . - doi : 10.2307/2347565 . — .
↑ Gilks, WR; Bedst, NG; Tan, KKC Adaptive Rejection Metropolis Sampling indenfor Gibbs Sampling // Journal of the Royal Statistical Society. Serie C (Anvendt statistik) : journal. - 1995. - 1. januar ( bind 44 , nr. 4 ). - S. 455-472 . - doi : 10.2307/2986138 . — .
↑ Martino, L.; Read, J.; Luengo, D. Uafhængig dobbelt adaptiv afvisning Metropolis Sampling inden for Gibbs Sampling // IEEE- transaktioner på signalbehandling : journal. - 2015. - 1. juni ( bind 63 , nr. 12 ). - s. 3123-3138 . — ISSN 1053-587X . - doi : 10.1109/TSP.2015.2420537 . - . - arXiv : 1205.5494 .
↑ Se Stramer 1999.
↑ Liu, Jun S.; Liang, Faming; Wong, Wing Hung. Multiple-Try Method and Local Optimization in Metropolis Sampling // Journal of the American Statistical Association : tidsskrift. - 2000. - 1. marts ( bd. 95 , nr. 449 ). - S. 121-134 . — ISSN 0162-1459 . - doi : 10.1080/01621459.2000.10473908 .
↑ Martino, Luca; Læs, Jesse. Om fleksibiliteten i designet af flere forsøg Metropolis-ordninger // Computational Statistics : journal. - 2013. - 11. juli ( bind 28 , nr. 6 ). - P. 2797-2823 . — ISSN 0943-4062 . - doi : 10.1007/s00180-013-0429-2 . - arXiv : 1201.0646 .
↑ Se Green 1995.
↑ Del Moral, Pierre. Middelfeltsimulering til Monte Carlo - integration . - Chapman & Hall/CRC Press, 2013. - S. 626. . - Monografier om statistik og anvendt sandsynlighed.
↑ Del Moral, Pierre. Feynman-Kac formel. Genealogiske og interagerende partikeltilnærmelser . - Springer, 2004. - S. 575. . - "Serie: Sandsynlighed og applikationer".
↑ 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. — (Forelæsningsnotater i matematik). — ISBN 978-3-540-67314-9 . - doi : 10.1007/bfb0103798 .
↑ Del Moral, Pierre. Sekventielle Monte Carlo-samplere - P. Del Moral - A. Doucet - A. Jasra - 2006 - Journal of the Royal Statistical Society: Series B (Statistical Methodology) - Wiley Online Library (engelsk) // Journal of the Royal Statistical Society. Serie B (statistisk metode) : journal. - 2006. - Bd. 68 , nr. 3 . - S. 411-436 . doi : 10.1111 / j.1467-9868.2006.00553.x . - arXiv : cond-mat/0212648 .
↑ Chen, S.; Dick, Joseph; Owen, Art B. Konsistens af Markov-kæden kvasi-Monte Carlo på kontinuerlige tilstandsrum (engelsk) // Annals of Statistics : journal. - 2011. - Bd. 39 , nr. 2 . - s. 673-701 . - doi : 10.1214/10-AOS831 .
↑ Tribble, Seth D. (2007). Markov-kæde Monte Carlo-algoritmer ved hjælp af fuldstændig ensartet fordelte køresekvenser (Diss.). Stanford University. Skabelon:ProQuest .
↑ Papageorgiou, Anargyros; Traub, JF Slår Monte Carlo // Risiko. - 1996. - T. 9 , nr. 6 . - S. 63-65 .
↑ Sobol, Ilya M. Om quasi-monte carlo integrationer // Mathematics and Computers in Simulation. - 1998. - T. 47 , nr. 2 . - S. 103-112 . - doi : 10.1016/s0378-4754(98)00096-2 .
↑ L'Ecuyer, P.; Lecot, C.; Tuffin, B. A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains // Operations Research : journal. - 2008. - Bd. 56 , nr. 4 . - S. 958-975 . doi : 10.1287 / opre.1080.0556 .
↑ L'Ecuyer, P.; Munger, D.; Lecot, C.; Tuffin, B. Sorteringsmetoder og konvergenshastigheder for Array-RQMC: Nogle empiriske sammenligninger // Mathematics and Computers in Simulation: journal. - 2018. - Bd. 143 . - S. 191-201 . - doi : 10.1016/j.matcom.2016.07.010 .
↑ 1 2 Gelman, A.; Rubin, DB Konklusioner fra iterativ simulering ved hjælp af flere sekvenser (med diskussion ) // Statistical Science : journal. - 1992. - Bd. 7 , nr. 4 . - S. 457-511 . - doi : 10.1214/ss/1177011136 . - .
↑ Cowles, M.K.; Carlin, BP Markov-kæden Monte Carlo konvergensdiagnostik: en komparativ gennemgang // Journal of the American Statistical Association : tidsskrift. - 1996. - Bd. 91 , nr. 434 . - S. 883-904 . - doi : 10.1080/01621459.1996.10476956 .
↑ Hill, SD; Spall, JC Stationarity and Convergence of the Metropolis-Hastings Algorithm: Insights into Theoretical Aspects // IEEE Control Systems Magazine: tidsskrift. - 2019. - Bd. 39 , nr. 1 . - S. 56-67 . - doi : 10.1109/MCS.2018.2876959 .
↑ Azad, A; Pavlopoulos, G.A.; Ouzounis, CA; Kyrpides, N.C.; Buluç, A. HipMCL: en højtydende parallel implementering af Markov-klyngealgoritmen til storskala netværk // Nukleinsyreforskning : journal. - 2018. - 6. april ( bd. 46 , nr. 6 ). —P.e33 . _ doi : 10.1093 / nar/gkx1313 . — PMID 29315405 .

Kilder

Christophe Andrieu, Nando De Freitas, Arnaud Doucet og Michael I. Jordan An Introduction to MCMC for Machine Learning , 2003
Asmussen, Søren; Glynn, Peter W. Stokastisk simulering: Algoritmer og analyse . - Springer, 2007. - Vol. 57. - (Stokastisk modellering og anvendt sandsynlighed).
Atzberger, P. En introduktion til Monte-Carlo-metoder (link utilgængeligt) . Hentet 4. maj 2020. Arkiveret fra originalen 20. februar 2009. (ubestemt)
Berg, Bernd A. Markov Kæde Monte Carlo-simuleringer og deres statistiske analyse . - World Scientific , 2004.
Bolstad, William M. Understanding Computational Bayesian Statistics . - Wiley, 2010. - ISBN 978-0-470-04609-8 .
Casella, George; George, Edward I. Forklaring af Gibbs-prøvetageren // Den amerikanske statistiker. - 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 : tidsskrift. - 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 dataanalyse. — 1. - Chapman & Hall , 1995. (Se kapitel 11.)
Geman, S.; Geman, D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images // IEEE-transaktioner på mønsteranalyse og maskinintelligens : journal. - 1984. - Bd. 6 , nr. 6 . - s. 721-741 . - doi : 10.1109/TPAMI.1984.4767596 .
Gilks, W.R.; Richardson, S.; Spiegelhalter, DJ Markov Chain Monte Carlo i praksis. - Chapman & Hall /CRC, 1996.
Gill, Jeff. Bayesianske metoder: en samfunds- og adfærdsvidenskabelig tilgang . — 2. - Chapman & Hall / CRC, 2008. - ISBN 978-1-58488-562-7 .
Green, PJ Reversible-jump Markov-kæde Monte Carlo-beregning og Bayesiansk modelbestemmelse (engelsk) // Biometrika : journal. - 1995. - Bd. 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). (ubestemt)
Robert, Christian P.; Casella, G. Monte Carlo Statistiske metoder . — 2. - Springer, 2004. - ISBN 978-0-387-21239-5 .
Rubinstein, R.Y.; Kroese, D.P.Simulering og Monte Carlo-metoden. — 2. - Wiley , 2007. - ISBN 978-0-470-17794-5 .
Smith, RL Effektive Monte Carlo-procedurer til at generere point ensartet fordelt over afgrænsede regioner // Operationsforskning : journal. - 1984. - Bd. 32 , nr. 6 . - S. 1296-1308 . doi : 10.1287 / opre.32.6.1296 .
Spall, JC Estimation via Markov Chain Monte Carlo // IEEE Control Systems Magazine. - 2003. - April ( bind 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. - Bd. 1 , nr. 3 . - s. 307-328 . - doi : 10.1023/A:1010090512027 .

Litteratur

Diaconis, Persi. Markov-kæden Monte Carlo-revolutionen // Bulletin of the American Mathematical Society . - 2009. - April ( bd. 46 , nr. 2 ). - S. 179-205 . - doi : 10.1090/s0273-0979-08-01238-x .
Press, W.H.; Teukolsky, SA; Vetterling, WT & Flannery, BP (2007), afsnit 15.8. Markov Chain Monte Carlo , Numerical Recipes: The Art of Scientific Computing (3. udgave), 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 ( bind 117 , nr. 5 ). - s. 383-413 . doi : 10.4169 / 000298910x485923 .