L'algoritmo Monte Carlo hamiltoniano (Hamiltonian Monte Carlo o HMC), originariamente noto anche come Monte Carlo ibrido, è un metodo Monte Carlo basato su catena di Markov utile a generare una sequenza di campioni casuali la cui distribuzione di probabilità converge verso una distribuzione-obiettivo difficile da campionare direttamente. Tale sequenza può essere utilizzata per stimare integrali della distribuzione-obiettivo, come valori attesi e momenti.

L'HMC rappresenta un'istanza dell'algoritmo Metropolis-Hastings, con un'evoluzione della dinamica hamiltoniana simulata utilizzando un integratore numerico reversibile nel tempo capace anche di preservare il volume (tipicamente il leapfrog) utile a proporre uno spostamento verso un nuovo punto nello spazio degli stati. Rispetto all'utilizzo di una distribuzione proposta ottenuta mediante passeggiata aleatoria gaussiana dell'algoritmo Metropolis-Hastings, l'Hamiltonian Monte Carlo riduce la correlazione tra stati campionati successivi proponendo spostamenti verso stati distanti che mantengono un'alta probabilità di accettazione grazie a proprietà approssimate di conservazione dell'energia della dinamica hamiltoniana simulata quando si utilizza un integratore simplettico. La ridotta correlazione comporta che sono necessari meno campioni della catena di Markov per approssimare gli integrali rispetto alla distribuzione-obiettivo per un errore di Monte Carlo prefissato.

L'algoritmo è stato originariamente proposto da Simon Duane, Anthony Kennedy, Brian Pendleton e Duncan Roweth nel 1987 per calcoli in cromodinamica quantistica su reticolo. Nel 1996, Radford M. Neal ha mostrato come il metodo potesse essere utilizzato per una classe più ampia di problemi statistici relativi, in particolare, alle reti neurali artificiali. Tuttavia l'onere di dover fornire all'algoritmo gradienti del grafico del modello ha ritardato una sua più ampia adozione in statistica e in altre discipline quantitative, fino a quando a metà degli anni 2010 gli sviluppatori del linguaggio probabilistico Stan hanno implementato HMC in combinazione con la differenziazione automatica.

Algoritmo Si supponga che la distribuzione-obiettivo da campionare sia per ( ) e che sia quindi richiesta una catena di campioni .

Le equazioni di Hamilton sono le seguenti:

dove

dove è l'energia potenziale. L'energia potenziale per un obiettivo è definita come segue:

che deriva dal fattore di Boltzmann. Si noti che la hamiltoniana è adimensionale in questa formulazione perché il peso di probabilità esponenziale deve essere ben definito. Ad esempio, nelle simulazioni a temperatura finita , il fattore (dove è la costante di Boltzmann) viene assorbito direttamente in e .

L'algoritmo richiede un numero intero positivo come numero di salti (passi di leapfrog) e un numero positivo per la dimensione del passo . Supponendo che la catena sia arrivata a , sia . In primo luogo, si estrae da un momento gaussiano casuale . Successivamente, la particella procederà secondo la dinamica hamiltoniana per un tempo , questo si calcola risolvendo numericamente le equazioni di Hamilton usando l'algoritmo leapfrog. I vettori di posizione e quantità di moto dopo il tempo utilizzando l'algoritmo leapfrog sono:

Tali equazioni devono essere applicate a e per volte al fine di ottenere e .

L'algoritmo leapfrog è una soluzione approssimata per il problema del moto di particelle classiche non interagenti. Se esatta, la soluzione non cambierà mai la distribuzione di energia iniziale generata casualmente, poiché l'energia si conserva per ciascuna particella in presenza di un classico campo di energia potenziale. Per raggiungere una distribuzione di equilibrio termodinamico, le particelle devono avere qualche forma di interazione, ad esempio, attraverso un bagno termico tutt'attorno, in modo che l'intero sistema possa assumere energie diverse con probabilità che seguono la distribuzione di Boltzmann.

Un modo per spostare il sistema verso una distribuzione di equilibrio termodinamico è modificare lo stato delle particelle utilizzando l'algoritmo di Metropolis-Hastings. Quindi, prima si applica il passo leapfrog, poi un passo Metropolis-Hastings.

La transizione da a è

dove e sono le -esime componenti dei vettori posizione e momento, rispettivamente, e è l'hamiltoniana. Sia una matrice di massa simmetrica e definita positiva, allora l'hamiltoniana è:

Un aggiornamento completo consiste innanzitutto nel campionamento casuale delle quantità di moto (indipendentemente dalle iterazioni precedenti), seguito dall'integrazione delle equazioni di moto (ad esempio con il leapfrog), estraendo infine la nuova configurazione tramite il passo di accettazione/rifiuto di Metropolis-Hastings. Questo meccanismo di aggiornamento viene ripetuto per produrre .

Campionatore NUTS Il campionatore No U-Turn Sampler (NUTS) è un'estensione che controlla il numero di passi automaticamente. Regolare è fondamentale. Ad esempio, nel caso unidimensionale di , il potenziale è , che corrisponde al potenziale di un oscillatore armonico semplice. Se è troppo grande, la particella oscillerà e quindi sprecherà tempo di calcolo. Se è troppo piccola, la particella si comporterà come una passeggiata casuale.

In termini generali, NUTS segue la dinamica hamiltoniana sia in avanti sia all'indietro nel tempo in modo casuale, fino al momento in cui viene soddisfatta una condizione di inversione a U. Quando ciò accade, viene scelto un punto casuale del percorso per il campione MCMC e il processo viene ripetuto da tale nuovo punto.

Più in dettaglio, viene costruito un albero binario per tener traccia del percorso dei passi del leapfrog. Per produrre un campione MCMC, viene eseguita una procedura iterativa. Viene campionata una variabile-slice . Siano e , rispettivamente, la posizione e la quantità di moto della particella a, da muovere in avanti. Allo stesso modo, siano e posizione e la quantità di moto per la particella b, da muovere all'indietro. In ogni iterazione, l'albero binario seleziona casualmente e uniformemente se muovere in avanti nel tempo la particella a o muovere all'indietro la particella b. Inoltre, a ogni iterazione, il numero di passi leapfrog aumenta di un fattore 2. Ad esempio, nella prima iterazione, la particella a si muove in avanti nel tempo usando 1 passo leapfrog. Nell'iterazione successiva, la particella b si muove all'indietro nel tempo usando 2 passi di leapfrog.

La procedura continua a iterare finché non viene soddisfatta la condizione di inversione a U, ovvero

o quando l'hamiltoniano diventa impreciso

oppure

dove, ad esempio, .

Una volta soddisfatta la condizione di inversione a U, per generare il successivo campione MCMC, , si campiona uniformemente il cammino del leapfrog tracciato dall'albero binario il quale soddisfa la condizione seguente

.

Di solito questo requisito viene soddisfatto se i restanti parametri HMC hanno valori ragionevoli.

Note

Bibliografia

Voci correlate

Metodo Monte Carlo dinamico Turing.jl, un linguaggio di programmazione probabilistico in Julia che implementa il metodo HMC.

Collegamenti esterni

Categoria:Statistica bayesiana Categoria:Teoria della probabilità Categoria:Statistica computazionale Categoria:Apprendimento automatico