I metodi Monte Carlo basati su Catena di Markov (MCMC) sono una classe di algoritmi per il campionamento da distribuzioni di probabilità basata sulla costruzione di una catena di Markov avente come distribuzione di equilibrio (o stazionaria) la distribuzione desiderata. Dopo aver simulato un grande numero di passi della catena si può quindi usare i valori estratti come campione della distribuzione desiderata.

Solitamente non è difficile costruire una catena di Markov con le proprietà desiderate, ma non è sempre possibile determinare a priori quanti passi sono necessari per convergere con un errore accettabile alla distribuzione stazionaria^[1]. Una MCMC è tanto migliore quanto minore è il suo tempo di mixing, ossia di convergenza alla distribuzione stazionaria, partendo da una posizione arbitraria^[2].

L'applicazione tipica di questi metodi può essere descritta come il campionamento da una distribuzione di probabilità multidimensionale di cui si conosce solamente una funzione proporzionale alla funzione di densità di probabilità. Qualora si avesse una funzione a valori positivi, un metodo MCMC può essere quindi utilizzato per stimarne l'integrale, e risulta più efficiente di un metodo Monte Carlo semplice nel caso di problemi in molte dimensioni. In questo contesto è nato il l'algoritmo di Metropolis, primo esempio di Catena di Markov Monte Carlo, proposto nel 1953 dall'equipe di Nicholas Metropolis, che lavorava al programma atomico americano e responsabili tra l'altro dello sviluppo dei primi metodi Monte Carlo^[3].

L'algoritmo di Metropolis consiste in una passeggiata aleatoria (random walk) con una correzione per cui ogni nuovo valore estratto può essere rigettato se corrisponde a un valore della funzione integranda minore rispetto al punto precedente, con una probabilità uguale a uno meno il rapporto tra questi valori. Questo fa sì che il processo aleatorio si concentri nelle zone dove l'integrando ha valori più alti, da qui l'efficacia. All'opposto che nei metodi Monte Carlo semplici, però, dove i valori campionati sono statisticamente indipendenti, nell'algoritmo di Metropolis (e nelle catene di Markov Monte Carlo in generale) sono autocorrelati.

Nel 1970 Hastings pubblicò una generalizzazione dell'algoritmo di Metropolis (che guadagnò il nome di algoritmo di Metropolis-Hastings) che utilizza un processo aleatorio di base (proposal distribution) non necessariamente di tipo random walk. Un particolare caso dell'algoritmo di Metropolis-Hastings è il campionamento di Gibbs, nominato così in onore del fisico Willard Gibbs, e divenuto famoso nella comunità statistica negli anni '90 grazie alla sua validità come strumento per campionare dalle distribuzioni a posteriori nel campo della statistica bayesiana^[3].

Integrali multidimensionali spesso si presentano in statistica bayesiana, fisica computazionale, biologia computazionale e linguistica computazionale, e in tal modo i metodi MCMC sono ampiamente utilizzati in questi campi^[4][5].

Le catene di Markov Monte Carlo sono costruite per concentrare il maggior possibile sforzo computazionale nelle zone di massima densità di probabilità bersaglio, ma siccome queste zone non sono conosciute in anticipo, le prime osservazioni della catena si troveranno necessariamente nelle vicinanze del punto iniziale, scelto arbitrariamente, in zone di densità solo relativamente maggiori a quella iniziale. Per questa ragione il campione finale sarebbe anche pesantemente distorto dalle osservazioni iniziali, che devono quindi essere scartate ai fini dalle stime. La parte iniziale della catena, da scartare, viene chiamata di burn-in o warm-up (riscaldamento) per analogia.

Nonostante questo accorgimento, da un punto di vista stocastico sussiste sempre qualche effetto residuo dipendente dalla scelta della posizione di partenza. Questo effetto è nella pratica spesso trascurabile, ma teoricamente il campionamento MCMC tipico può solo approssimare la distribuzione bersaglio. Algoritmi basati su campionamenti MCMC più sofisticati come il cosiddetto "accoppiamento dal passato" (coupling from the past) possono produrre campioni esatti, seppure al prezzo di una maggiore complessità di elaborazione numerica e di un tempo di esecuzione indefinito (di valore atteso finito, ma sconosciuto prima dell'esecuzione).

Al crescere del numero di dimensioni del problema, anche gli algoritmi MCMC soffrono la maledizione della dimensionalità: le regioni di maggior densità tendono ad allungarsi e distanziarsi, all'interno di uno spazio di sempre maggior volume. Algoritmi più avanzati, come l'HMC, sono più adatti a questo genere di problemi perché, al costo di una maggior complessità e costo computazionale, riescono a concentrare più efficacemente i valori estratti all'interno della zona di maggior densità, senza rinunciare a distanziare i valori campionati tra loro (e quindi mantenendo bassa l'autocorrelazione).

Nonostante questo, le catene di Markov Monte Carlo potrebbero esibire problemi di convergenza nel caso di distribuzioni obbiettivo particolarmente complesse, oppure che violano le condizioni stesse di ergodicità del processo adottato. Per rilevare questo problema è bene simulare diverse catene con punti di partenza distanti tra loro e in seguito controllare che risultino nella stessa distribuzione, ma la soluzione richiede un algoritmo adeguato. La maggior parte degli algoritmi MCMC prevede dei parametri che necessitano di essere specificati, e il valore che gli viene attribuito deve essere adatto al problema affrontato, in modo da ottenere una bassa variabilità per le stime basate sul campione Monte Carlo.

• algoritmo di Metropolis-Hastings.
• campionamento di Gibbs: Richiede che tutte le distribuzioni condizionate della distribuzione bersaglio siano conosciute propriamente e possano essere usate per campionarvi. Questo metodo è divenuto popolare in quanto, nel caso in cui sia possibile applicarlo, esso non richiede che si prestabilisca alcun parametro relativo all'algoritmo.
• campionamento per "strati" ("slices"): Dipende sul principio che è possibile campionare uniformemente una distribuzione dalla regione sottesa dalla curva della sua funzione di densità. Questo metodo alterna un campionamento uniforme nella direzione verticale con uno dallo "strato" individuato dalla posizione verticale corrente.
• Metropolis a tentativi multipli (''Multiple-try Metropolis''): È una variante dell'algoritmo di Metropolis-Hastings che permette tentativi multipli a ogni punto. Questo permette all'algoritmo di impostare passi più grandi in forma sistematica consentendo in tal modo di affrontare problemi aventi dimensionalità intrinsecamente ampie.
• metodo del sovra-rilassamento: Una versione Monte Carlo di questa tecnica può essere vista come una variazione del campionamento di Gibbs (Gibbs sampling); esso qualche volta evita ripetizioni del percorso.
• metodo di Monte Carlo ibrido (Hybrid/Hamiltonian Monte Carlo, HMC): Implementa dinamiche hamiltoniane nella catena di Markov aumentando lo spazio indagato con uno spazio ausiliario dei momenti. La densità bersaglio quindi diventa la funzione di energia potenziale e il momento viene via via sorteggiato da una distribuzione prestabilita condizionata al punto x_i , a quel punto viene calcolata una traiettoria di energia costante che viene fermata dopo una quantità di tempo arbitrario. Alla fine del campionamento i dati sui momenti vengono scartati. Il risultato finale è di allungare i passi proposti mantenendoli però all'interno delle regioni di alta densità.
• No U-Turn Sampling (NUTS): Variante del metodo HMC che evita ulteriormente ripetizioni da parte della catena, calcolando in maniera adattiva il tempo delle traiettorie.
• Il metodo MCMC di Langevin ed altri metodi basati sul metodo del gradiente (eventualmente in derivata seconda) del logaritmo della distribuzione obbiettivo, propongono percorsi che sono preferibilmente nella direzione di più alta densità di probabilità.^[6]

Il metodo reversible-jump è una variante del metodo di Metropolis-Hastings che permette la proposta di passi che cambiano la dimensionalità dello spazio parametrico su cui opera la passeggiata aleatoria. Questo metodo fu proposto nel 1995 dallo statistico Peter Green dell'Università di Bristol.^[7] Metodi MCMC che cambiano dimensionalità sono stati a lungo usati in applicazioni di fisica statistica, dove venivano usati per i vari problemi distribuzioni basate sull'insieme gran canonico (ad esempio quando il numero di molecole in una scatola è variabile). Qualche variante di sorta del metodo reversible-jump è richiesta nel caso di campionamenti MCMC o di Gibbs sopra modelli bayesiani non parametrici come quelli implicati nel processo di Dirichlet^[8] (un processo stocastico che può essere pensato come una distribuzione di probabilità il cui dominio è esso stesso una distribuzione casuale) o quello del Chinese restaurant process, dove il numero di componenti, cluster, ecc. è automaticamente dedotto dai dati.

• Christophe Andrieu et al., "An Introduction to MCMC for Machine Learning", 2003
• Bernd A. Berg. "Markov Chain Monte Carlo Simulations and Their Statistical Analysis". Singapore, World Scientific 2004.
• George Casella and Edward I. George. "Explaining the Gibbs sampler". The American Statistician, 46:167–174, 1992. (Un riassunto introduttivo al metodi di campionamento di Gibbs, con esempi e riferimenti bibliografici.)
• A.E. Gelfand and A.F.M. Smith. "Sampling-Based Approaches to Calculating Marginal Densities". J. American Statistical Association, 85:398–409, 1990.
• Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin. Bayesian Data Analysis. London: Chapman and Hall. First edition, 1995. (Capitolo 11.)
• S. Geman and D. Geman. "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images". IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721–741, 1984.
• Radford M. Neal, Probabilistic Inference Using Markov Chain Monte Carlo Methods, 1993.
• Gilks W.R., Richardson S. and Spiegelhalter D.J. "Markov Chain Monte Carlo in Practice". Chapman & Hall/CRC, 1996.
• C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (seconda edizione). New York: Springer-Verlag, 2004.
• R. Y. Rubinstein and D. P. Kroese. Simulation and the Monte Carlo Method (seconda edizione). New York: John Wiley & Sons, 2007. ISBN 978-0-470-17794-5
• R. L. Smith "Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions", Operations Research, Vol. 32, pp. 1296–1308, 1984.
• Asmussen and Glynn "Stochastic Simulation: Algorithms and Analysis", Springer. Series: Stochastic Modelling and Applied Probability, Vol. 57, 2007.
• P. Atzberger, "An Introduction to Monte-Carlo Methods." [1].
• Bolstad, William M. (2010) Understanding Computational Bayesian Statistics, John Wiley.

• Diaconis, Persi, "The Markov chain Monte Carlo revolution", Bull. Amer. Math. Soc. (2009)
• WH Press, SA Teukolsky, WT Vetterling e BP Flannery, Section 15.8. Markov Chain Monte Carlo, in Numerical Recipes: The Art of Scientific Computing, 3rd, New York, Cambridge University Press, 2007, ISBN 978-0-521-88068-8. URL consultato il 4 giugno 2012 (archiviato dall'url originale l'11 agosto 2011).
• Richey, Matthew, "The Evolution of Markov Chain Monte Carlo Methods", The American Mathematical Monthly, May 2010, 383-413

• Inferenza bayesiana
• Particle filter

• Una panoramica introduttiva al campionamento MCMC ed altri metodi, by Alexander Mantzaris
• Una dimostrazione visiva dei metodi di campionamento MCMC (applet Java), by Laird Breyer
• A Toy Example of MCMC sampling, by Zhiyuan Weng
• MCL - un algoritmo di tipo cluster per grafi, by Stijn van Dongen

Portale Informatica

Portale Matematica

Portale Statistica