Utente:Rbattistin/Sandbox5

I metodi Monte Carlo basati su Catena di Markov (MCMC) (i quali includono i metodi Monte Carlo del tipo random walk) 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 la distribuzione desiderata. Lo stato della catena dopo un grande numero di passi è quindi usata come un campione della distribuzione desiderata.

Solitamente non è difficile costruire una catena di Markov con le proprietà desiderate. Il difficile è determinare quanti passi sono necessari per convergere con un errore accettabile alla distribuzione stazionaria. Una buona catena ha un "rimescolamento rapido" (rapid mixing), quantificato in termine di tempo di mescolamento della catena di Markov, quando garantisce il rapido raggiungimento della distribuzione stazionaria partendo da una posizione arbitraria.

Poiché sussiste sempre qualche effetto residuo dipendente dalla scelta della posizione di partenza, 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, cfr. http://en.wikipedia.org/wiki/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 (ossia limitato ma non predicibile).

L'applicazione più comune di questi algoritmi è il calcolo numerico degli integrali multidimensionali. Questi metodi sono basati su un insieme statistico di "passeggiatori" che si muovono in maniera aleatoria. Ad ogni punto dove il "passeggiatore" arriva, il valore dell'integrando è valutato in relazione all'integrale. Il "passeggiatore" successivamente si sposta nella regione attorno al punto e contestualmente viene valutato l'integrando ricercando un nuovo punto ove il contributo all'integrale sia maggiore rispetto a quello trovato precedentemente, quindi si sposta in quest'ultimo nuovo punto (cfr. Metodo Monte Carlo per l'integrazione). In effetti questa tecnica di passeggiata aleatoria (random walk) è un tipo di simulazione aleatoria o metodo Monte Carlo. Tuttavia, mentre nel metodo convenzionale di integrazione del metodo Monte Carlo i valori dell'integrando campionati casualmente sono statisticamente indipendenti, quelli usati in MCMC sono correlati. Una catena di Markov è costruita in modo tale che l'integrando sia la distribuzione di equilibrio.

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. Per esempio cfr. Gill and Robert & Casella.

Algoritmi di passeggiata aleatoria (random walk)

Molti metodi MCMC convergono aleatoriamente attorno alla distribuzione di equilibrio in un relativamente piccolo numero di passi. Questi metodi sono facili da implementare e da analizzare, ma sfortunatamente possono richiedere un lungo tempo per percorrere tutto lo spazio. Inoltre tratti del percorso vengono spesso ripetuti. Ecco un elenco di vari metodi MCMC:

• algoritmo di Metropolis–Hastings: Genera un percorso aleatorio usando una densità proposta e una tecnica per rigettare le mosse proposte.
• campionamento di Gibbs: Richiede che tutte le distribuzioni condizionate della distribuzione bersaglio possano essere campionate esattamente. Il qualche misura questo metodo è divenuto popolare in quanto, nel caso in cui sia possibile applicarlo, esso non richiede alcun adattamento.
• 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''): E' una variante dell'algoritmo di Metropolis–Hastings che permette tentativi multipli ad 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.

Metodi per ridurre le ripetizioni nella passeggiata aleatoria

Algoritmi più sofisticati impiegano vari metodi per prevenire ripetizioni di percorso durante la passeggiata aleatoria. Questi algoritmi possono essere di più difficile implementazione ma possono esibire una convergenza più rapida (cioè meno passaggi per ottenere un risultato accurato).

• 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 Monte Carlo, MCM): Prova ad evitare il comportamento del cammino aleatorio mediante l'introduzione di un vettore momento ausiliario ed implementando dinamiche hamiltoniane la densità bersaglio è la funzione di dell'energia potenziale. I campioni di momento vengono scartati dopo il campionamento. Il risultato finale è di allungare i passi proposti e rendendoli meno correlati tra loro e tali da convergere più rapidamente alla distribuzione bersaglio.
• Varianti del metodo di campionamento a strati evitano percorsi aleatori.ref>Radford M. Neal, "Slice Sampling". The Annals of Statistics, 31(3):705–767, 2003.</ref>
• Il metodo MCMC di Langevin ed altri metodi basati sul metodo del gradiente (eventualmente in derivata seconda) del logaritmo della distribuzione a posteriori, evitano i percorsi aleatori proponendo percorsi che sono preferibilmente nella direzione di più alta densità di probabilità.

Metodi basati sul cambiamento di dimensione

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 Brisol. 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 (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.

Voci correlate

• Inferenza bayesiana
• Particle filter

Bibliografia

• 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 ISBN 0-470-04609-8Template:Please check ISBN

Letture unteriori

• Diaconis, Persi, "The Markov chain Monte Carlo revolution", Bull. Amer. Math. Soc. (2009)
• Numerical Recipes: The Art of Scientific Computing, Cambridge University Press, 2007.
• Richey, Matthew, "The Evolution of Markov Chain Monte Carlo Methods", The American Mathematical Monthly, May 2010, 383-413

Collegamenti esterni

• 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

[[Categoria:Statistica computazionale]]