Lanțul Markov Monte Carlo

Metodele Monte Carlo bazate pe lanțul Markov ( MCMC ) sunt o clasă de algoritmi pentru eșantionarea din distribuții de probabilitate bazate pe construcția unui lanț Markov având distribuția dorită ca distribuție de echilibru (sau staționară) . După simularea unui număr mare de pași în lanț, valorile extrase pot fi apoi utilizate ca eșantion al distribuției dorite.

De obicei, nu este dificil să construim un lanț Markov cu proprietățile dorite, dar nu este întotdeauna posibil să se determine a priori câți pași sunt necesari pentru a converge cu o eroare acceptabilă la distribuția staționară ^[1] . Un MCMC este mult mai bun cu cât timpul său de amestecare este mai scurt, adică convergența către distribuția staționară, pornind de la o poziție arbitrară ^[2] .

Istorie și aplicații

Aplicarea tipică a acestor metode poate fi descrisă ca eșantionare dintr-o distribuție multidimensională a probabilității, din care este cunoscută doar o funcție proporțională cu funcția densității probabilității . Dacă am avea o funcție cu valoare pozitivă, o metodă MCMC poate fi, prin urmare, utilizată pentru a estima integrala acesteia și este mai eficientă decât o metodă simplă Monte Carlo în cazul problemelor în multe dimensiuni. În acest context, s-a născut algoritmul Metropolis , primul exemplu de lanț Markov Monte Carlo, propus în 1953 de echipa lui Nicholas Metropolis , care a lucrat la programul atomic american și responsabil, printre altele, de dezvoltarea primului Metode Monte Carlo. ^[3] .

Algoritmul Metropolis constă dintr-o plimbare aleatorie ( mers aleator) cu o corecție pentru care fiecare nouă valoare extrasă poate fi respinsă dacă corespunde unei valori cu funcție de integrand mai mică față de punctul anterior, cu o probabilitate egală cu un minus raportul între aceste valori. Acest lucru face ca procesul aleatoriu să fie concentrat în zonele în care integrarea are valori mai mari, de unde și eficacitatea sa. Dimpotrivă, cu toate acestea, în metodele Monte Carlo simple, unde valorile eșantionate sunt independente din punct de vedere statistic , în algoritmul Metropolis (și în lanțurile Markov Monte Carlo în general) sunt autocorelate .

În 1970, Hastings a publicat o generalizare a algoritmului Metropolis (care a câștigat numele de algoritm Metropolis-Hastings ), care utilizează un proces aleator de bază ( distribuția propunerii ), nu neapărat de tipul mersului aleator. Un caz particular al algoritmului Metropolis-Hastings este eșantionarea Gibbs , numită în onoarea fizicianului Willard Gibbs , și care a devenit faimoasă în comunitatea statistică în anii 1990 datorită validității sale ca instrument de eșantionare din distribuții a posteriori în domeniu. statisticilor bayesiene ^[3] .

Integralele multidimensionale apar adesea în statistica bayesiană , fizica calculațională, biologia computațională și lingvistica calculațională, și astfel metodele MCMC sunt utilizate pe scară largă în aceste domenii ^{[4] [5]} .

Probleme legate de MCMC

Lanțurile Monte Carlo Markov sunt construite pentru a concentra cel mai mare efort de calcul posibil în zonele cu densitatea maximă a probabilității țintă, dar din moment ce aceste zone nu sunt cunoscute în prealabil, primele observații ale lanțului vor fi neapărat în apropierea punctului de plecare, ales în mod arbitrar, în zonele de densitate doar relativ mai mari decât cea inițială. Din acest motiv, eșantionul final ar fi, de asemenea, puternic distorsionat de observațiile inițiale, care trebuie deci aruncate în sensul estimărilor. Partea inițială a lanțului, care trebuie aruncată, se numește prin ardere sau încălzire ( încălzire ) prin analogie.

În ciuda acestei precauții, din punct de vedere stochastic există întotdeauna un efect rezidual în funcție de alegerea poziției de plecare. Acest efect este adesea neglijabil în practică, dar teoretic, eșantionarea tipică a MCMC poate aproxima doar distribuția țintă. Algoritmi bazați pe eșantionare MCMC mai sofisticate, așa-numita „cuplare din trecut” (cuplarea din trecut) poate produce eșantioane exacte, deși la prețul unei complexități mai mari a procesării numerice și a unui timp de execuție nedefinit (valoarea așteptată a , dar necunoscut înainte de execuție).

Pe măsură ce numărul dimensiunilor problemei crește, chiar și algoritmii MCMC suferă blestemul dimensionalității : regiunile cu densitate mai mare tind să se întindă și să se distanțeze, într-un spațiu de volum în creștere. Algoritmi mai avansați, cum ar fi HMC , sunt mai potriviți pentru acest tip de problemă, deoarece, cu prețul unei complexități și costuri de calcul mai mari, sunt capabili să concentreze valorile extrase mai eficient în zona densității mai mari, fără renunțând la distanțarea valorilor eșantionate între ele (și, prin urmare, menținerea scăzută a autocorelației).

În ciuda acestui fapt, lanțurile Monte Carlo Markov ar putea prezenta probleme de convergență în cazul distribuțiilor obiective deosebit de complexe sau care încalcă condițiile de ergodicitate ale procesului adoptat. Pentru a detecta această problemă este bine să simulați diferite lanțuri cu puncte de plecare îndepărtate și apoi să verificați dacă acestea duc la aceeași distribuție, dar soluția necesită un algoritm adecvat. Majoritatea algoritmilor MCMC au parametri care trebuie specificați, iar valoarea atribuită acestora trebuie să fie potrivită pentru problema cu care se confruntă, pentru a obține o variabilitate scăzută pentru estimările bazate pe eșantionul Monte Carlo.

Lista algoritmilor

• Algoritm Metropolis-Hastings .
• Eșantionare Gibbs : necesită ca toate distribuțiile condiționate ale distribuției țintă să fie cunoscute în mod corespunzător și să poată fi utilizate pentru a le preleva. Această metodă a devenit populară deoarece, în cazul în care este posibil să o aplicați, nu este necesar să setați în prealabil niciun parametru legat de algoritm.
• eșantionarea „felii” : Depinde de principiul că este posibilă eșantionarea uniformă a unei distribuții din regiunea subtendută de curba funcției sale de densitate. Această metodă alternează o eșantionare uniformă în direcția verticală cu una din „stratul” identificat de poziția verticală actuală.
• Multiple-încercați Metropolis : Aceasta este o variantă a algoritmului Metropolis-Hastings , care permite mai multe încercări în orice punct. Acest lucru permite algoritmului să seteze pași mai mari într-o formă sistematică, permițând astfel să se confrunte cu probleme cu dimensionalitate intrinsec mare.

• metoda supra-relaxării : Monte Carlo O versiune a acestei tehnici poate fi privită ca o variație a eșantionării Gibbs (eșantionare Gibbs); uneori evită repetarea căii.
• Metoda Monte Carlo hibridă ( Monte Carlo hibridă / hamiltoniană , HMC): implementează dinamica hamiltoniană în lanțul Markov prin creșterea spațiului investigat cu un spațiu de moment auxiliar. Densitatea țintă devine apoi funcția de energie potențială și momentul este extras treptat dintr-o distribuție predeterminată condiționată la punctul x _i , moment în care se calculează o traiectorie de energie constantă care este oprită după o cantitate arbitrară de timp. La sfârșitul eșantionării, momentul în care datele sunt eliminate. Rezultatul final este de a prelungi pașii propuși, păstrându-i în același timp în regiunile cu densitate mare.
• No U-Turn Sampling (NUTS): Varianta metodei HMC care evită în continuare repetițiile de către lanț, prin calcularea într-un mod adaptativ a timpului traiectoriilor.
• Metoda Langevin MCMC și alte metode bazate pe metoda gradientului (posibil în derivată secundară) a logaritmului distribuției țintă, propun căi care sunt de preferință în direcția densității probabilității mai mari. ^[6]

Metode bazate pe modificarea dimensiunii

Metoda saltului reversibil este o variantă a metodei Metropolis-Hastings care permite propunerea de pași care modifică dimensionalitatea spațiului parametric pe care operează mersul aleator. Această metodă a fost propusă în 1995 de statisticianul Peter Green de la Universitatea din Bristol . ^[7] Metodele MCMC care modifică dimensionalitatea au fost folosite de mult în aplicațiile de fizică statistică , unde distribuțiile bazate pe marele set canonic au fost utilizate pentru diverse probleme (de exemplu, când numărul de molecule dintr-o cutie este variabil). Un fel de variantă a metodei săriturilor reversibile este necesară în cazul eșantionării MCMC sau Gibbs pe modele bayesiene non-parametrice , cum ar fi cele implicate în procesul Dirichlet ^[8] (un proces stocastic care poate fi considerat o distribuție de probabilitate al cărui domeniu este el însuși o distribuție aleatorie) sau cel al procesului de restaurant chinezesc , unde numărul de componente, clustere etc. se deduce automat din date.

Notă

Bibliografie

• Christophe Andrieu și colab., „An Introduction to MCMC for Machine Learning” , 2003
• Bernd A. Berg. „Simulațiile Markov Chain Monte Carlo și analiza lor statistică”. Singapore, World Scientific 2004.
• George Casella și Edward I. George. „Explicarea probei Gibbs”. The American Statistician , 46: 167–174, 1992. (Un rezumat introductiv al metodelor de eșantionare Gibbs, cu exemple și referințe.)
• AE Gelfand și AFM Smith. „Abordări bazate pe eșantionare pentru calcularea densităților marginale”. J. American Statistical Association , 85: 398-409, 1990.
• Andrew Gelman , John B. Carlin, Hal S. Stern și Donald B. Rubin. Analiza Bayesiană a Datelor . Londra: Chapman și Hall. Prima ediție, 1995. (Capitolul 11.)
• S. Geman și D. Geman. „Relaxare stochastică, distribuții Gibbs și restaurarea bayesiană a imaginilor”. IEEE Transactions on Pattern Analysis and Machine Intelligence , 6: 721-741, 1984.
• Radford M. Neal, Inferință probabilistică folosind lanțul Markov Metode Monte Carlo , 1993.
• Gilks ​​WR, Richardson S. și Spiegelhalter DJ „Markov Chain Monte Carlo in Practice”. Chapman & Hall / CRC , 1996.
• CP Robert și G. Casella. „Metode statistice Monte Carlo” (ediția a doua). New York: Springer-Verlag, 2004.
• RY Rubinstein și DP Kroese. Simulare și metoda Monte Carlo (ediția a doua). New York: John Wiley & Sons, 2007. ISBN 978-0-470-17794-5
• RL Smith „Proceduri Monte Carlo eficiente pentru generarea de puncte distribuite uniform peste regiuni delimitate”, Cercetări operaționale , Vol. 32, pp. 1296-1308, 1984.
• Asmussen și Glynn „Simulare stocastică: algoritmi și analiză”, Springer. Serie: Modelare stochastică și probabilitate aplicată, Vol. 57, 2007.
• P. Atzberger, „O introducere la metodele Monte-Carlo”. [1] .
• Bolstad, William M. (2010) Understanding Computational Bayesian Statistics, John Wiley.

Elemente conexe

• Inferența bayesiană
• Filtru de particule

Lecturi suplimentare

• Diaconis, Persi , „Revoluția lanțului Markov de la Monte Carlo” , Bull. Amer. Matematica. Soc. (2009)
• WH Press, SA Teukolsky, WT Vetterling și BP Flannery, secțiunea 15.8. Markov Chain Monte Carlo , în Rețete numerice: arta calculelor științifice , 3rd, New York, Cambridge University Press, 2007, ISBN 978-0-521-88068-8 .
• Richey, Matthew , „Evoluția metodei lanțului Markov Monte Carlo”, The American Mathematical Monthly, mai 2010, 383-413

linkuri externe

• O prezentare introductivă a eșantionării MCMC și a altor metode , de Alexander Mantzaris
• O demonstrație vizuală a metodelor de eșantionare MCMC (Java applet) , de Laird Breyer
• Un exemplu de jucărie de eșantionare MCMC , de Zhiyuan Weng
• MCL - un algoritm de tip cluster pentru grafice , de Stijn van Dongen

Portal IT

Portalul de matematică

Portalul de statistici