Differenze tra le versioni di "Algoritmo di Metropolis-Hastings"

riscrivo correggendo un importante errore
(riscrivo correggendo un importante errore)
{{torna a|Catena di Markov Monte Carlo}}
L''''algoritmo di Metropolis-Hastings''' serve a generare dei numeri x<sub>1</sub>, x<sub>2</sub>, .., x<sub>n</sub> che presentano una [[distribuzione di probabilità|distribuzione]] ''p(x)'' fissata a priori.
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.
Il metodo si basa sulla generazione di numeri di 'test' che vengono accettati o rigettati in modo da ottenere la distribuzione voluta. Il metodo sarà presentato nel caso di una sola [[variabile casuale continua]]; esso può essere facilmente esteso al caso di distribuzioni di probabilità ''P(x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>N</sub>)'' di un numero qualsiasi di variabili.
 
== Algoritmo di Metropolis ==
L'algoritmo di [[Nicholas Constantine Metropolis|Metropolis]] è realizzabile utilizzando un generatore di numeri casuali con [[variabile casuale uniforme continua|distribuzione uniforme]] in ''[0, 1]''. La procedura è la seguente:
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.
# Preso, per convenzione, l'ultimo valore x<sub>i</sub> della variabile aleatoria nella sequenza si sceglie un valore di prova x<sup>*</sup> dipendente da x<sub>i</sub> tra tutti i valori possibili della variabile random. Nel caso delle variabili random continue si può prendere x<sup>*</sup> = x<sub>i</sub> +δx dove δx è un numero distribuito uniformemente nell'intervallo ''[−δ, δ]'';
# 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.
# Sisi calcola il rapporto <math>w = <math>\frac{f(x^*)}{f(x_i)} = \frac{p(x^{*})}{p(x_i)} </math>;
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.
# Sese ''<math>w \geq 1''</math> si accetta il nuovo valore x<supmath>x^*</sup> = x<sub>x_{i+1}</submath>;
# Sese invece ''<math>w < 1''</math> il nuovo valore deve essere accettato con probabilità <math>w</math>. Si genera quindi un numero random <math>r</math> distribuito uniformemente nell'intervallo [0, 1)];
## Sese ''<math>r < w''</math> si accetta il nuovo valore x<supmath>x^*</sup> = x<sub>x_{i+1}</submath> ;
## Se invece ''r > w''altrimenti il nuovo valore viene rigettato dale momentosi chepone x<submath>x_{i+1</sub>} = x<sub>ix_i</submath>.
 
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.
 
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 delladi ''p(x)'' è necessario generare sequenze moltoabbastanza lunghe. La scelta del valoreparametro di ''δ'' può essere cruciale, se è troppo grande solo una piccola parte dei valori di prova proposti verrà accettato. Se invece ilè valoretroppo dipiccolo ''δ''la ècatena tropposi piccolomuoverà quasimolto tuttilentamente e i valori di prova propostirisulteranno sarannoestremamente accettati[[autocorrelazione|autocorrelati]].
 
Di conseguenza, essendo ''δ'' dipendente dalla forma e dalla scala di ''p(x)'', deve essere di volta in volta sceltocalibrato correttamente; 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.
 
=== 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 ==