Monte Carlo Markovska veriga

V statistiki metode Monte Carlo Markovske verige (angleško Monte Carlo Markov Chain, MCMC) sestavljajo razred algoritmov za vzorčenje iz verjetnostne porazdelitve. Z grajenjem Markovske verige, ki ima za želeno porazdelitev svojo ravnotežnostno porazdelitev, lahko pridobimo vzorec želene porazdelitve z zapisovanjem stanj z verige. Več korakov kot vključimo, bližje bo porazdelitev vzorca dejanski želeni porazdelitvi. Za grajenje verige obstajajo različni algoritmi, npr. Metropolis–Hastings algoritem.

Konvergenca Metropolis–Hastings algoritma. Monte Carlo Markovska veriga poskuša približati modro porazdelitev z oranžno.

Domene aplikacije

uredi

MCMC metode večinoma uporabljamo za računanje številčnih približkov večdimenzijskih integralov, npr. v Bayesianski statistiki, računski fiziki,[1] računski biologiji[2] in računski lingvistiki.[3][4]

V Bayesianski statistiki je nedaven razvoj MCMC metod omogočil računanje velikih hierarhičnih modelov, ki zahtevajo integracije čez stotine ali tisoče neznanih parametrov.[5]

V vzorčenju redkih dogodkov se uporabljajo za ustvarjanje vzorcev, ki postopoma naselijo redko območje napake.[navedi vir]

Splošna razlaga

uredi

Metode MCMC ustvarjajo vzorce z neprekinjene naključne spremenljivke z verjetnostno gostoto proporcionalno znani funkciji. Te vzorce lahko uporabljamo za ovrednotenje integrala te spremenljivke kot pričakovno vrednost ali varianco.

V praksi se razvije skupina verig, začenši od zbirke točk, ki so naključno izbrane in dovolj narazen druga od druge. Te verige so stohastični procesi »walkerjev«, ki se premikajo naključno glede na algoritem, ki išče točke z razmeroma visokim prispevkom integralu, da se premakne v naslednje točke in jim dodeli višjo verjetnost.

Random walk Monte Carlo metode so vrsta naključne simulacije ali Monte Carlo metode. Za razliko od naključnih vzorcev integranda, ki so v običajni Monte Carlo integraciji statistično neodvisni, so tisti v MCMC avtokorelirani. Korelacije vzorcev vpeljejo potrebo po uporabi centralnega limitnega teorema Markovskee verige pri ocenjevanju napak sredinskih vrednosti.

Ti algoritmi tvorijo Markovske verige na ta način, da imajo ravnotežno porazdelitev, ki je proporcionalna dani funkciji.

Zmanjševanje korelacije

uredi

Čeprav so bile MCMC metode ustvarjene za boljše naslavljanje večdimenzionalnih težav v primerjavi z generičnimi Monte Carlo algoritmi, se, ko število dimenzij zraste, tudi pri teh pojavi prekletstvo dimenzionalnosti: regije večje verjetnosti se raztegnejo in izgubijo v rastoči prostornini prostora, ki malo prispeva k integralu. En način za reševanje te težave bi bilo lahko krajšanje korakov walkerja, tako da ne poskuša neprestano zapustiti regijo največje verjetnosti. Toda na ta način bi bil proces visoko avtokoreliran in drag (tj. veliko korakov bi bilo potrebno za natančen rezultat). Bolj sofisticirane metode, kot je Hamiltonov Monte Carlo in Wang in Landau algoritem uporabljajo različne načine za zmanjševanje te avtokorelacije, hkrati pa uspevajo z obdržanjem procesa v regijah, ki dajo višji prispek k integralu. Ti algoritmi se običajno zanašajo na bolj zapleteno teorijo in jih je težje izvesti, vendar običajno konvergirajo hitreje.

Primeri

uredi

Random walk

uredi
  • Metropolis–Hastings algoritem: ta metoda ustvari Markovsko verigo s predlagano gostoto za nove korake in metodo za zavrnitve nekaterih predlaganih premikov. To je pravzaprav splošen okvir, ki vključuje kot posebne primere čisto prve in preprostejše MCMC (Metropolis algoritem) in veliko več najnovejših alternativ, naštetih spodaj.
    • Gibbsovo vzorčenje: ko je ciljna porazdelitev večdimenzionalna, Gibbsov algoritem vzorčenja[6] posodobi vsako koordinato s svoje polne pogojne porazdelitve pri danih drugih koordinatah. Gibbsovo vzorčenje lahko obravnavamo kot posebni primer Metropolis-Hastings algoritma s stopnjo sprejemanja enakomerno enako 1. Ko črpanje iz polnih pogojnih porazdelitev ni jasno so uporabljena druga vzorčenja.[7][8] Gibbsovo vzorčenje je priljubljeno deloma zato, ker ne zahteva nobenega »tuninga«. Struktura algoritma Gibbsovega vzorčenja močno spominja strukturo povečanja koordinat variacijskega sklepanja, saj oba algoritma uporabljata polne pogojne porazdelitve v postopku posodabljanja.[9]
    • Metropolis-prilagojen Langevinov algoritem in druge metode, ki se zanašajo na naklon (in mogoče druge odvode) logaritemske ciljne gostote, da predlagajo korake, ki za katere je bolj verjetno, da bodo v smeri višje gostote verjetnosti.[10]
    • Psevdo-marginalni Metropolis Hastings: ta metoda nadomešča vrednotenje gostote ciljne porazdelitve z nepristransko oceno in je uporabna, ko ciljna gostota in na voljo na analitičen način, npr. modeli z latentnimi spremenljivkami.
  • Vzorčenje z rezinami: ta metoda je odvisna od načela, da je možno vzorčiti s porazdelitve z enakomernim vzorčenjem z regije pod grafom funkcije gostote. Izmenjuje enakomerno vzorčenje v navpični smeri z enakomernim vzorčenjem z vodoravne »rezine«, ki jo opredeljuje trenutna navpična pozicija.

Sklici

uredi
  1. Kasim, M.F.; Bott, A.F.A.; Tzeferacos, P.; Lamb, D.Q.; Gregori, G.; Vinko, S.M. (september 2019). »Retrieving fields from proton radiography without source profiles«. Physical Review E. 100 (3): 033208. arXiv:1905.12934. Bibcode:2019PhRvE.100c3208K. doi:10.1103/PhysRevE.100.033208. PMID 31639953. S2CID 170078861.{{navedi časopis}}: Vzdrževanje CS1: samodejni prevod datuma (povezava)
  2. Gupta, Ankur; Rawlings, James B. (april 2014). »Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology«. AIChE Journal. 60 (4): 1253–1268. doi:10.1002/aic.14409. PMC 4946376. PMID 27429455.{{navedi časopis}}: Vzdrževanje CS1: samodejni prevod datuma (povezava)
  3. See Gill 2008.
  4. See Robert & Casella 2004.
  5. Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. (12. september 2014). Hierarchical Modeling and Analysis for Spatial Data (Second izd.). CRC Press. str. xix. ISBN 978-1-4398-1917-3.
  6. Geman, Stuart; Geman, Donald (november 1984). »Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images«. IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-6 (6): 721–741. doi:10.1109/TPAMI.1984.4767596. ISSN 0162-8828. PMID 22499653.{{navedi časopis}}: Vzdrževanje CS1: samodejni prevod datuma (povezava)
  7. Gilks, W. R.; Wild, P. (1. januar 1992). »Adaptive Rejection Sampling for Gibbs Sampling«. Journal of the Royal Statistical Society. Series C (Applied Statistics). 41 (2): 337–348. doi:10.2307/2347565. JSTOR 2347565.
  8. Gilks, W. R.; Best, N. G.; Tan, K. K. C. (1. januar 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.
  9. Lee, Se Yoon (2021). »Gibbs sampler and coordinate ascent variational inference: A set-theoretical review«. Communications in Statistics - Theory and Methods. 51 (6): 1–21. arXiv:2008.01006. doi:10.1080/03610926.2021.1921214. S2CID 220935477.
  10. See Stramer 1999.

Nadaljnje branje

uredi