Algoritmo di Metropolis-Hastings: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
riscrivo correggendo un importante errore |
||
Riga 1:
{{torna a|Catena di Markov Monte Carlo}}
L''''algoritmo di Metropolis-Hastings''' è un metodo [[MCMC]] usato per generare dei valori x<sub>1</sub>, x<sub>2</sub>, .., x<sub>n</sub> che presentano una [[distribuzione di probabilità|distribuzione]] p(x) fissata a priori. Non necessita che la funzione p(x) sia nota, è sufficiente anzi che sia conosciuta una funzione f(x) proporzionale a p(x). Questo requisito così debole permette di usare l'algoritmo di Metropolis-Hastings per campionare da distribuzioni di cui l'integrale sia troppo difficile, o impossibile, da calcolare in forma analitica.
Il metodo è stato descritto da Hastings nel 1970, come generalizzazione dell''''algoritmo di Metropolis''' del 1953.
== Algoritmo di Metropolis ==
Per comprendere l'algoritmo generale è utile imparare prima quello originale, detto di Metropolis.
Il metodo si basa sulla generazione di valori "proposti" che vengono accettati o rigettati in modo da convergere alla distribuzione <math>p(x)</math> voluta. Necessita di una funzione <math>f(x) \propto p(x)</math> e di una ''proposal distribution'' <math>J(x^*|x_i)</math> simmetrica, che rispetti cioè la proprietà <math>J(x^*|x_i) = J(x_i|x^*)</math>. Le scelte più comuni per la distribuzione di proposta sono la normale <math>\mathcal N(x_i, \delta^2)</math>e l'uniforme <math>unif(x_i-\delta, x_i+\delta)</math>, dove delta è un parametro da specificare prima della partenza dell'algoritmo.
# Si calcola il rapporto w = <math> \frac{p(x^{*})}{p(x_i)} </math>;▼
# Se ''w ≥ 1'' si accetta il nuovo valore x<sup>*</sup> = x<sub>i+1</sub>▼
# Se invece ''w < 1'' il nuovo valore deve essere accettato con probabilità w. Si genera quindi un numero random r distribuito uniformemente nell'intervallo [0, 1);▼
# Se ''r ≤ w'' si accetta il nuovo valore x<sup>*</sup> = x<sub>i+1</sub> ;▼
# Se invece ''r > w'' il nuovo valore viene rigettato dal momento che x<sub>i+1</sub> = x<sub>i</sub>.▼
Ciascuna iterazione dell'algoritmo di [[Nicholas Constantine Metropolis|Metropolis]] consiste nei seguenti passaggi:
Per generare una sequenza di ''N'' elementi basta ripetere queste operazioni ''N'' volte a partire da un valore iniziale x<sub>0</sub>. Per avere una buona stima della ''p(x)'' è necessario generare sequenze molto lunghe. La scelta del valore di ''δ'' può essere cruciale, se è troppo grande solo una piccola parte dei valori di prova proposti verrà accettato. Se invece il valore di ''δ'' è troppo piccolo quasi tutti i valori di prova proposti saranno accettati.▼
# si estrae un nuovo valore <math>x^*</math> dalla distribuzione di proposta <math>J(x^*|x_i)</math>;
Di conseguenza, essendo ''δ'' dipendente dalla forma di ''p(x)'', deve essere di volta in volta scelto; per la sua stima si può procedere per approssimazione successiva in modo che, fissato un delta, il numero di valori accettati sia un terzo del totale.▼
▲#
Anche la scelta del valore iniziale è molto importante, in genere conviene partire da valori di ''x'' tali che ''p(x)'' assuma valori massimi in modo da avere una buona statistica nelle zone più probabili.▼
▲#
▲#
▲##
▲##
Per generare una sequenza di ''N'' elementi basta ripetere queste operazioni N volte a partire da un valore iniziale x<sub>0</sub>, scelto arbitrariamente.
▲
▲Di conseguenza, essendo
▲Anche la scelta del valore iniziale è molto importante, in genere conviene partire da valori di
=== Caso multivariato ===
L'algoritmo descritto sopra funziona esattamente sia nel caso uni- che multivariato, ma esiste un secondo approccio al caso multivariato, particolarmente interessante quando si va a studiare la generalizzazione di Metropolis-Hastings. Anziché generare ad ogni iterazione un nuovo vettore x* e accettarlo o respingerlo in toto, è possibile considerare a parte ogni elemento di x = (x<sub>1</sub>, ... x<sub>p</sub>) e generare a parte un nuovo valore per ciascuno di questi elementi tramite una distribuzione simmetrica J<sub>j</sub>(x*<sub>j</sub>|x<sub>j</sub>) per poi accettare o respingere questo valore singolarmente, al fine di definire x<sub>i+1</sub>.
== Algoritmo di Metropolis-Hastings ==
L'algoritmo di Metropolis richiede, per garantirne la convergenza limite, che la distribuzione di proposta sia simmetrica. Questa condizione limita di fatto il processo che genera i valori proposti al dominio dei [[random walk]]. Hastings (1970) propose una generalizzazione dell'algoritmo di Metropolis che permette la scelta di qualsiasi tipo di proposta.
{{...}}
== Voci correlate ==
| |||