Metodi di approssimazione di Monte Carlo Quale dovresti scegliere e quando?

Approssimazione di Monte Carlo quale metodo e quando?

È Trasformazione Inversa, Random Walk Metropolis-Hastings o Gibbs? Un’analisi focalizzata sulle basi matematiche, implementazione in Python da zero e vantaggi/svantaggi di ciascun metodo

Foto di Joakim Honkasalo su Unsplash

Introduzione al Campionamento di Approssimazione

Per la maggior parte dei modelli probabilistici di interesse pratico, l’inferenza esatta è inaffidabile, quindi dobbiamo ricorrere a qualche forma di approssimazione.

— Pattern Recognition and Machine Learning¹

Dato che l’inferenza deterministica è spesso inaffidabile con modelli probabilistici come abbiamo appena visto, ci rivolgiamo ora a metodi di approssimazione basati sul campionamento numerico, noti come tecniche Monte Carlo. La domanda chiave che esamineremo con questi metodi è il calcolo dell’aspettativa di una funzione target f(z) data una distribuzione di probabilità p(z). Ricordiamo che la semplice definizione di aspettativa è data come integrale:

Fonte: PRML¹ Eq. 11.1

Come vedremo, questi integrali sono troppo complessi dal punto di vista computazionale, quindi ci rivolgeremo a metodi di campionamento in questo articolo.

In questo articolo, esamineremo 3 metodi di campionamento principali: trasformazione inversa, Markov chain Monte Carlo (MCMC) e Campionamento Gibbs. Comprendendo le proprietà statistiche sottostanti e i requisiti computazionali di questi metodi, impareremo che:

  • Il campionamento tramite trasformazione inversa è il migliore per simulare dati con elevata accuratezza da distribuzioni note e semplici, in particolare in basse dimensioni.
  • Il Random Walk Metropolis-Hastings è il migliore per distribuzioni complesse, multimodali o sconosciute, dove l’esplorazione globale e/o la convergenza sono una priorità; in particolare, l’algoritmo Metropolis – un’istanza specifica di Metropolis-Hastings – può essere utilizzato per distribuzioni simmetriche.
  • Il Campionamento Gibbs è il migliore per problemi ad alta dimensionalità in cui le distribuzioni condizionali sono facili da campionare e l’efficienza è una priorità.

Indice

  1. Trasformazione Inversa del Campionamento • Come funziona l’algoritmo? • Implementazione in Python • Prerequisiti • Vantaggi e svantaggi
  2. Markov Chain Monte Carlo • Algoritmo Metropolis-Hastings • Istanza speciale: Algoritmo Metropolis per Distribuzioni Simmetriche • Vantaggi/Svantaggi
  3. Gibbs • Algoritmo • Condizioni • Relazione di Gibbs con Metropolis-Hastings
  4. Confronto: Vantaggi/Svantaggi di Trasformazione vs. Met-Hastings vs. Gibbs

1. Metodo di Trasformazione: CDF Inversa

La Trasformazione Inversa del Campionamento, come suggerisce il nome, utilizza la funzione di distribuzione cumulativa inversa (CDF) di una distribuzione target per generare numeri casuali che seguono una distribuzione desiderata. L’idea di base è:

  1. Generare un numero casuale uniforme: Estraiamo un numero U da una distribuzione uniforme tra 0 e 1.
  2. Applicare la CDF Inversa: Utilizzando l’inverso della CDF della distribuzione target, trasformiamo U in un campione che segue la distribuzione target.

Ecco una rapida illustrazione di come i campioni (blu) vengono estratti dalla distribuzione (rossa):

La CDF Inversa è un metodo semplice e generalizzabile dal punto di vista computazionale per campionare da distribuzioni per le quali conosciamo la CDF, come la distribuzione normale, esponenziale, gamma o beta.

PDF, CDF e Inverse CDF

(Da sinistra a destra): PDF, CDF e Inverse CDF della distribuzione normale standard

In termini intuitivi, la CDF è il valore cumulativo della PDF, che è uguale all’integrale della PDF; quindi si prende l’inverso della funzione CDF per ottenere l’inverso finale della CDF utilizzato per questo metodo.

Formalmente, se a è una variabile casuale, allora la CDF di a è data da:

PRML, Eq. 11.5–11.6

Una CDF F ha le seguenti proprietà chiave:

  • F è continua
  • F è non decrescente
  • F ha un range 0 ≤ cdf(a) ≤ 1 per tutti gli a ∈ R

Come funziona l’algoritmo Inverse CDF?

L’algoritmo consiste nei seguenti ingredienti:

Input:

  • U: U è una variabile casuale uniforme estratta tra 0 e 1.
  • Questo serve come probabilità di input per la Inverse CDF ed è ciò che verrà trasformato in un campione dalla distribuzione desiderata.

Parametro:

  • F: la CDF della distribuzione target.
  • Con F, possiamo semplicemente calcolarne l’inverso, F^-1, e usarlo per mappare un valore di input nel dominio desiderato

Output:

  • x: un campione casuale estratto dalla distribuzione target.
  • Questo viene generato applicando la Inverse CDF al numero casuale della distribuzione uniforme (input).

Implementazione in Python

Ora, implementiamo questo metodo da zero. Utilizzeremo la funzione esponenziale poiché sarà facile visualizzare i nostri campioni estratti dalla Inverse CDF e confrontarli con la distribuzione esatta:

PDF della funzione esponenziale (distribuzione target)

Attraverso le tecniche standard di integrazione del calcolo, troviamo che la CDF target F(x) è:

CDF della funzione esponenziale

L’inverso di questa CDF è:

Inverse CDF della funzione esponenziale

Genereremo 5000 campioni utilizzando il metodo Inverse CDF:

import numpy as npimport matplotlib.pyplot as plt# Inverse CDF per la distribuzione esponenziale con lambda = 1def inverse_cdf(p):    return -np.log(1 - p)# Genera 1000 valori campione utilizzando Inverse CDFuniform_samples = np.random.uniform(0, 1, 1000)transformed_samples = inverse_cdf(uniform_samples)# Genera valori x e PDF verax_values = np.linspace(0, np.max(transformed_samples), 1000)pdf_values = np.exp(-x_values)

Requisiti per il funzionamento dell’algoritmo CDF inverso

Il metodo CDF inverso si basa su una supposizione fondamentale:

  • La CDF F è invertibile: La CDF F deve essere invertibile, il che significa che ogni input per F deve avere un output univoco

Questa restrizione esclude diverse funzioni. Ad esempio, di seguito sono riportati alcuni tipi di funzioni comuni ma non invertibili (e quindi non compatibili con il CDF inverso):

  1. Funzioni costanti: Qualsiasi funzione costante nella forma f(x) = c, dove c è una costante, non è invertibile poiché ogni input viene mappato sullo stesso output e quindi la funzione non è uno-a-uno.
I punti rossi mostrano due dei molti valori di x che vengono mappati sullo stesso valore di y in f(x) = 5, rendendola non invertibile

2. Certune funzioni quadratiche: Ad esempio, f(x) = x^2 non è invertibile poiché è molti-a-uno (considera f(x) = 1, x potrebbe essere 1 o -1).

I punti rossi mostrano una delle molte coppie di valori di x che vengono mappati sullo stesso valore di y in f(x) = x²

3. Certune funzioni trigonometriche: Ad esempio, f(x) = sin(x) non è invertibile sull’intero dominio poiché è periodica, anche se con domini restritti può essere resa invertibile.

I punti rossi mostrano uno dei molti insiemi di valori di x che vengono mappati sullo stesso valore di y in f(x) = sin(x) a causa della sua periodicità sul dominio dato

Perché funziona il CDF inverso?

L’idea chiave è che una variabile casuale uniformemente distribuita tra 0 e 1 può essere trasformata in una variabile casuale con una certa distribuzione applicando l’inversa della CDF della distribuzione target, che si presume essere nota e trattabile.

Vantaggi

  1. Semplicità algoritmica: è molto facile da implementare con dati a bassa dimensione, avendo quindi un’ampia area di applicazione in diversi campi e compiti.
  2. Precisione campionaria: assumendo che la CDF e la sua inversione rappresentino esattamente la distribuzione target, il metodo produce una precisione relativamente alta rispetto ad altri metodi come MCMC che vedremo prossimamente.

Svantaggi

  1. Complessità computazionale: per alcune distribuzioni, l’inversa della CDF potrebbe non avere una forma chiusa, rendendo il calcolo impegnativo o costoso.
  2. Difficoltà con l’alta dimensionalità: può essere difficile applicarlo in spazi ad alta dimensionalità, soprattutto con dipendenze tra le variabili.
  3. Restrizione di invertibilità: ogni volta che una CDF non è invertibile, questo metodo diventa invalido. Questo esclude diverse funzioni come abbiamo visto precedentemente.
  4. Limitato alle distribuzioni conosciute: il CDF inverso richiede la forma esatta della CDF, limitando la sua applicazione solo alle distribuzioni conosciute.

Considerando tutte queste limitazioni, ci sono solo poche categorie di distribuzioni a cui possiamo applicare la CDF inversa. In realtà, con Big Data e distribuzioni sconosciute, questo metodo può diventare rapidamente non disponibile.

Con questi vantaggi e svantaggi in mente, diamo ora un’occhiata a un altro framework di campionamento casuale che affronta queste limitazioni: Markov Chain Monte Carlo (MCMC).

2. Markov Chain Monte Carlo (MCMC)

Come abbiamo appena visto, il metodo di trasformazione della CDF inversa è altamente limitato, specialmente con spazi campionari ad alta dimensionalità. Markov Chain Monte Carlo (MCMC), d’altra parte, scala bene con la dimensionalità, consentendoci di campionare un’ampia famiglia di distribuzioni.

Un esempio di Metropolis-Hastings che esplora una Gaussiana mista (sinistra), generando campioni (destra)

Come funziona l’algoritmo di Metropolis-Hastings?

In termini intuitivi, l’algoritmo funziona nei seguenti passaggi: Simile alla CDF inversa, abbiamo una distribuzione target da cui stiamo campionando. Tuttavia, abbiamo bisogno di un ingrediente aggiuntivo: lo stato corrente z*, e q(z|z*) dipende da z*, creando una catena di Markov con campioni z¹, z², z³,. Ogni campione viene accettato nella catena solo se soddisfa un certo criterio, che definiremo di seguito poiché questo criterio varia tra le variazioni dell’algoritmo.

Formalizziamolo in una struttura algoritmica più formale.

L’algoritmo viene eseguito in cicli, e ogni ciclo segue questi passaggi:

  1. Genera un campione z* dalla distribuzione proposta.
  2. Accetta il campione con probabilità Poi accetteremo questo valore con una probabilità di accettazione, che in Metropolis-Hastings è definita come:
PRML¹ Eq 11.44

dove

  • z* è lo stato corrente.
  • z^T è il nuovo stato proposto.
  • p(z*) è la probabilità dello stato z* secondo la distribuzione desiderata.
  • p(z^T) è la probabilità dello stato z^T secondo la distribuzione desiderata.

La logica dietro questa soglia di accettazione è che garantisce che gli stati più probabili (secondo la distribuzione desiderata) vengano visitati più spesso.

Ora, questa è la versione più generalizzata dell’algoritmo; se si sa che la distribuzione proposta è simmetrica, il che significa che la probabilità di proporre una transizione dallo stato x a x′ è la stessa della probabilità di proporre una transizione da x′ a x, cioè q(x′|x) = q(x|x′), allora possiamo utilizzare un caso speciale di Metropolis-Hastings che richiede una soglia di accettazione più semplice.

Algoritmo di Metropolis per Distribuzioni Simmetriche

Si tratta di un algoritmo specifico di MCMC che scegliamo di utilizzare se la distribuzione proposta è simmetrica, cioè q(z⁰ | z¹) = q(z¹ | z⁰) per tutti i valori di 1 e 0, interpretati come “la probabilità di passare da uno stato A a uno stato B è uguale alla probabilità di passare da B a A”. Quindi, ogni passo dell’algoritmo diventa:

  1. Genera un campione z* dalla distribuzione proposta.
  2. Accetta il campione con probabilità:
Soglia di accettazione dell'algoritmo di Metropolis. Src: PRML¹ Eq. 11.33

Metropolis-Hastings e Metropolis Algorithms

Guardiamo gli algoritmi uno accanto all’altro. Come abbiamo visto in precedenza, l’unica differenza è la soglia di accettazione; tutti gli altri passaggi degli algoritmi vengono eseguiti in modo identico:

Metropolis vs Metropolis-Hastings Algorithm

Vantaggi

  1. Convergenza alla distribuzione di equilibrio: In alcuni casi, il random walk può convergere a una distribuzione di equilibrio desiderata, anche se probabilmente richiede molto tempo in spazi ad alta dimensionalità.
  2. Basso costo computazionale: Il random walk spesso richiede meno risorse computazionali rispetto ad altri metodi di campionamento complessi, rendendolo adatto per problemi in cui l’efficienza computazionale è una priorità.
  3. Versatilità di applicazione: Grazie alla sua alta somiglianza ai modelli che si verificano naturalmente, il random walk trova applicazioni in una vasta gamma di campi:
    • Fisica: Movimento browniano di molecole in liquidi e gas.
    • Analisi di reti
    • Mercati finanziari: per modellare le fluttuazioni dei prezzi delle azioni
    • Genetica delle popolazioni

Svantaggi:

  1. Sensibilità all’inizializzazione: Le prestazioni dell’algoritmo possono essere sensibili alla scelta dei valori iniziali, specialmente se i valori inizializzati sono lontani dalle aree ad alta densità.
  2. Trappole di località: A seconda della complessità della distribuzione di proposta, l’algoritmo potrebbe rimanere bloccato in ottimi locali e avere difficoltà a attraversare altre aree lungo la distribuzione.

Ora, tenendo a mente l’algoritmo Metropolis-Hastings, vediamo un’altra sua istanza speciale: il Gibbs Sampling.

3. Gibbs Sampling

Il Gibbs Sampling è una particolare istanza del Metropolis-Hastings in cui ogni passo viene sempre accettato. Vediamo prima l’algoritmo del Gibbs Sampling stesso.

Come funziona l’algoritmo del Gibbs?

L’idea è relativamente semplice e viene meglio illustrata focalizzandoci su un micro esempio che coinvolge il campionamento da una distribuzione p(z1, z2, z3) su 3 variabili. L’algoritmo viene eseguito nei seguenti passaggi:

  1. All’istante T, inizializza i valori di partenza a:
PRML¹

2. Estrarre il nuovo valore per z1:

PRML¹ Eq 11.46

3. Estrarre un nuovo valore per la seconda posizione, z2, dalla condizionale:

PRML¹ Eq 11.47

4. Infine, estra un nuovo valore per l’ultima posizione, z3:

PRML¹ Eq 11.48

5. Ripetere questo processo, ciclando attraverso le tre variabili z1…z3 fino a raggiungere una determinata soglia soddisfacente.

Algoritmo generalizzato

Formalmente, l’algoritmo è rappresentato inizializzando prima le posizioni di partenza e quindi effettuando T passi consecutivi

Fonte dell'immagine: PRML¹ Ch11.3 Gibbs Sampling

Condizioni per il campionamento di Gibbs per estrarre correttamente da una distribuzione target

  1. Invarianza. La distribuzione target p(z) è invariante ad ogni passo di Gibbs, e quindi p(z) è invariante per l’intera catena di Markov.
  2. Ergodicità. Se le distribuzioni condizionali sono tutte diverse da zero, allora l’ergodicità è implicata poiché ogni punto nello spazio z è raggiungibile in un numero finito di passi.
  3. Sufficiente fase di burn-in. Come abbiamo visto con qualsiasi metodo che richiede una inizializzazione casuale, i primi campioni dipendono dall’inizializzazione e questa dipendenza si indebolisce dopo molte iterazioni.

Come si relaziona questo con Metropolis-Hastings?

In Metropolis-Hastings, abbiamo definito la soglia di accettazione come:

Quindi, i passi di proposta di Metropolis-Hastings vengono sempre accettati, come abbiamo visto nell’algoritmo di Gibbs.

Variazioni

Dato che il metodo di Gibbs aggiorna una variabile alla volta, ci sono forti dipendenze tra campioni consecutivi. Per superare questo problema, potremmo utilizzare una strategia intermedia per estrarre da gruppi di variabili invece che da variabili individuali, conosciuta come blocking Gibbs.

In modo simile, a causa della natura delle catene di Markov, gli esempi estratti consecutivamente saranno correlati. Per generare campioni indipendenti, potremmo utilizzare il sub-sampling all’interno della sequenza.

4. Pro/Contro: Inverse CDF vs Metropolis-Hastings vs Gibbs

Ora che abbiamo esaminato come funziona ciascun algoritmo e le sue aree di applicazione, riassumiamo le caratteristiche distintive di ciascun metodo.

1. Campionamento per trasformazione inversa

  • Dimensione dei dati: Ottimo per set di dati di dimensioni moderate.
  • Tempo: Generalmente efficiente per distribuzioni univariate.
  • Complessità dei dati: Utilizzare per distribuzioni semplici in cui la funzione di distribuzione cumulativa (CDF) e la sua inversa sono note e facili da calcolare.
  • Da evitare se: Si stanno campionando variabili/distribuzioni ad alta dimensionalità.
  • Vantaggio principale: Alta precisione se la CDF riflette accuratamente la distribuzione target.
  • Requisiti: La CDF deve essere nota e invertibile.

2. Metropolis-Hastings (MCMC)

  • Dimensione dei dati: Scalabile e adatto per set di dati di grandi dimensioni.
  • Tempo: Può richiedere molto tempo di calcolo, a seconda della complessità della distribuzione target.
  • Complessità dei dati: Ideale per distribuzioni complesse o multimodali.
  • Vantaggi principali: – Può campionare da una distribuzione senza conoscere la sua costante di normalizzazione (la forma completa);- Ottimo per esplorare la struttura globale di una distribuzione e garantisce la convergenza.
  • Svantaggio: Può soffrire di convergenza molto lenta con – distribuzione target complessa o multimodale, poiché l’algoritmo potrebbe rimanere bloccato in modi locali e avere difficoltà a passare tra di essi;- variabili altamente correlate;- spazi ad alta dimensionalità;- scelte iniziali o dimensioni dei passi non ottimali

3. Gibbs Sampling

  • Dimensione dei dati: Adatto sia per set di dati piccoli che grandi.
  • Tempo: Spesso più efficiente rispetto a Random Walk Metropolis-Hastings poiché non richiede passi di accettazione/rifiuto.
  • Complessità dei dati: Meglio utilizzato quando si tratta di distribuzioni ad alta dimensionalità in cui è possibile estrarre dalla distribuzione condizionale di ogni variabile.
  • Vantaggi principali: – È possibile calcolare facilmente le distribuzioni condizionali;- Meno incline a trappole di minimi locali rispetto a Random Walk.
  • Requisiti: – Ergodicità della catena di Markov – Le distribuzioni condizionali complete devono essere note e trattabili

In sintesi:

Tabella riassuntiva dei pro e dei contro di inverse CDF, Metropolis-Hastings e Gibbs

Conclusioni

Grazie per essere arrivato fin qui! In questo articolo, abbiamo analizzato 3 metodi chiave di approssimazione campionante: inverse CDF, Metropolis Hastings MCMC e Gibbs Sampling MCMC. Abbiamo esplorato come funziona ciascun algoritmo, i loro rispettivi vantaggi e svantaggi e gli scenari tipici di utilizzo.

Inverse CDF fornisce un metodo diretto per campionare da una distribuzione nota quando la sua CDF è invertibile. È computazionalmente efficiente, ma meno adatto per distribuzioni ad alta dimensionalità o complesse.Metropolis Hastings MCMC offre un approccio più generale che consente di campionare da distribuzioni difficili da gestire in altri modi. Tuttavia, richiede più risorse computazionali e può essere sensibile ai parametri di sintonia come la distribuzione di proposta.Gibbs Sampling MCMC è particolarmente efficiente quando la distribuzione congiunta è complessa ma può essere scomposta in distribuzioni condizionali più semplici. È ampiamente utilizzato nell’apprendimento automatico, anche se può essere lento a convergere e richiedere molta memoria per problemi ad alta dimensionalità.

[1] Bishop, C. M. (2016). Pattern Recognition and Machine Learning (Softcover reprint of the original 1st edition 2006 (corrected at 8th printing 2009)). Springer New York.

*Salvo diversa indicazione, tutte le immagini sono create dall’autore.