thumbnail|upright=1.25|Konvergenca Metropolis-Hastingsovega algoritma. Markovska veriga Monte Carlo poskuša približati modro porazdelitev z oranžno. V statistiki metode Monte Carlo markovske verige (, metode 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-Hastingsov algoritem.

Domene aplikacije Metode MCMC večinoma uporabljamo za računanje številčnih približkov večdimenzijskih integralov, npr. v Bayesovi statistiki, računski fiziki, računski biologiji in računski lingvistiki.See Gill 2008.See Robert & Casella 2004.

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

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

Splošna razlaga 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 metode Monte Carlo. Za razliko od naključnih vzorcev integranda, ki so v običajni integraciji Monte Carlo statistično neodvisni, so tisti v MCMC avtokorelirani. Korelacije vzorcev vpeljejo potrebo po uporabi centralnega limitnega teorema markovske 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

Čeprav so bile metode MCMC ustvarjene za boljše naslavljanje večrazsežnih težav v primerjavi z generičnimi algoritmi Monte Carlo, se z rastjo števila razsežnosti tudi pri teh pojavi prekletstvo razsežnosti: 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 Hamiltonova metoda Monte Carlo in Wang-Landauov 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 Metropolis-Hastingsov 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 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. 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. Metropolisov prilagojeni 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.See Stramer 1999. Psevdomarginalni Metropolis-Hastingsov algoritem: 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

Viri

Christophe Andrieu, Nando De Freitas, Arnaud Doucet and Michael I. Jordan An Introduction to MCMC for Machine Learning, 2003

(See Chapter 11.)

Nadaljnje branje

Kategorija:Ekonometrija Kategorija:Statistika Kategorija:Algoritmi Kategorija:Strojno učenje