Genereremo 5000 campioni utilizzando il metodo Inverse CDF:
import numpy as np
import matplotlib.pyplot as plt# Inverse CDF for the exponential distribution with lambda = 1
def inverse_cdf(p):
return -np.log(1 - p)
# Generate 1000 sample values using inverse CDF
uniform_samples = np.random.uniform(0, 1, 1000)
transformed_samples = inverse_cdf(uniform_samples)
# Generate x values and true PDF
x_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 parte da un presupposto chiave:
- CDF F è invertibile: La CDF F deve essere invertibileil che significa che ogni input a F deve avere un output univoco
Questo vincolo esclude una serie di funzioni. Ad esempio, di seguito sono riportati alcuni tipi di funzioni comuni ma non invertibile (e quindi lo farebbe non funziona con CDF inverso):
- Funzioni costanti: Qualsiasi funzione costante nella forma di f(x) = c Dove C è una costante non è invertibile poiché ogni input è associato allo stesso output e quindi la funzione lo è non uno a uno.
2. Alcune funzioni quadratiche: Per esempio f(x) = x^2 non è invertibile poiché è molti-a-uno (considerare f(x) = 1, X potrebbe essere 1 O -1).
3. Alcune funzioni trigonometriche: Per esempio f(x) = peccato(x) non è invertibile su tutto il loro dominio poiché sono periodici, sebbene con domini limitati possono essere resi invertibili.
Perché la CDF inversa funziona?
L’idea chiave è che a variabile casuale distribuita uniformemente tra 0 e 1 può essere trasformato in a variabile casuale con una certa distribuzione applicando l’inverso del CDF della distribuzione target, che si presume sia noto e trattabile.
Vantaggi
- Semplicità algoritmica: è molto facile da implementare con dati di dimensione inferiore, avendo così un’ampia area di applicazione in diversi campi e compiti.
- Precisione del campione: presupponendo che la CDF e la sua inversione rappresentino l’esatta distribuzione target, il metodo produce una precisione relativamente elevata rispetto ad altri metodi come MCMC che vedremo presto.
Svantaggi
- Complessità computazionale: Per alcune distribuzioni, la CDF inversa potrebbe non avere un’espressione in forma chiusa, rendendo il calcolo impegnativo o costoso.
- Difficoltà con elevata dimensionalità: Può essere difficile da applicare in spazi ad alta dimensione, specialmente con dipendenze tra variabili.
- Vincolo di invertibilità: Ogni volta che un CDF non è invertibile, questo metodo diventa non valido. Ciò esclude una serie di funzioni come abbiamo visto sopra.
- Limitato alle distribuzioni conosciute: La CDF inversa richiede la forma esatta della CDF, limitandone l’applicazione solo alle distribuzioni conosciute.
Tenendo conto di tutte queste limitazioni, ci sono solo poche categorie di distribuzioni a cui possiamo applicare la CDF inversa. In realtà, con i Big Data e le distribuzioni sconosciute, questo metodo può diventare rapidamente non disponibile.
Tenendo presenti questi vantaggi e svantaggi, esaminiamo ora un altro quadro di campionamento casuale che affronta queste limitazioni: Catena Markov Monte Carlo (MCMC).
Come abbiamo visto poco fa, il metodo di trasformazione CDF inversa lo è altamente limitatosoprattutto con alta dimensionalità spazi campione. Markov Chain Monte Carlo (MCMC), d’altro canto, si adatta bene alla dimensionalità, consentendoci di campionare da una famiglia di distribuzioni molto più ampia.
Come funziona l’algoritmo Metropolis-Hastings?
In termini intuitivi, l’algoritmo funziona nei seguenti passaggi: Simile al CDF inverso, abbiamo a distribuzione degli obiettivi da cui stiamo campionando. Serve però un ingrediente aggiuntivo: lo stato attuale z*E q(z|z*) dipende da z*creando una catena di Markov con i campioni z¹, z², z³,. Ogni campione viene accettato nella catena solo se soddisfa un determinato criterio, che definiremo di seguito poiché questo criterio differisce a seconda delle variazioni dell’algoritmo.
Formalizziamolo in una struttura più algoritmica.
L’algoritmo viene eseguito in cicli e ogni ciclo segue questi passaggi:
- Genera un campione z* dalla distribuzione della proposta.
- Accetta il campione con probabilità Quindi accetteremo questo valore con an probabilità di accettazione, che in Metropolis-Hastings è definito come:
Dove
- z* è lo stato attuale.
- z^T è il nuovo stato proposto.
- p(z*) è la probabilità dello stato z* secondo la distribuzione desiderata.
- p(z^T) è la probabilità di stato z^T secondo la distribuzione desiderata.
La logica dietro questa soglia di accettazione è che garantisce che il Stati più probabili (secondo la distribuzione desiderata) sono visitato più spesso.
Ora, questa è la versione più generalizzata dell’algoritmo; se è noto che la distribuzione delle proposte è simmetrica, il che significa che la probabilità di proporre una mossa dallo stato X A X′ equivale a proporre una mossa da X‘ A X, cioè Q(X’|X) = Q(x|x′), allora possiamo usare un caso speciale di Metropolis-Hastings che richiede una soglia di accettazione più semplice.
Algoritmo di metropoli per distribuzioni simmetriche
Questo è un algoritmo MCMC specifico che scegliamo di utilizzare se la distribuzione delle proposte è simmetricacioè q(z⁰ | z¹) = q(z¹ | z⁰) per tutti i valori di 1 e 0, interpretato come “la probabilità di transizione da qualsiasi stato A allo stato B è uguale alla probabilità di transizione da B ad A”. Quindi ogni passo dell’algoritmo diventa:
- Genera un campione z* dalla distribuzione della proposta.
- Accetta il campione con probabilità:
Metropolis-Hastings e algoritmi di Metropolis
Diamo un’occhiata agli algoritmi fianco a fianco. Come abbiamo visto prima, l’unica differenza è la soglia di accettazione; tutti gli altri passaggi degli algoritmi funzionano in modo identico:
Vantaggi
- Convergenza alla distribuzione di equilibrio: In alcuni casi, la passeggiata casuale può convergere verso una distribuzione di equilibrio desiderata, anche se probabilmente richiede molto tempo negli spazi ad alta dimensione.
- Basso costo computazionale: La passeggiata casuale spesso richiede meno risorse computazionali rispetto ad altri metodi di campionamento complessi, rendendolo adatto a problemi in cui l’efficienza computazionale è una priorità.
- Versatilità di applicazione: A causa della sua elevata somiglianza con i modelli naturali, Random Walk ha applicazioni in un’ampia varietà di campi:
• Fisica: Moto browniano delle molecole nei liquidi e nei gas.
• Analisi di rete
• Mercati finanziari: per modellare i movimenti dei prezzi delle azioni
• Genetica delle popolazioni
Svantaggi:
- Sensibile all’inizializzazione: Le prestazioni dell’algoritmo possono essere sensibili alla scelta dei valori iniziali, soprattutto se i valori inizializzati sono lontani dalle aree ad alta densità.
- Trappole della località: A seconda della complessità della distribuzione della proposta, l’algoritmo potrebbe rimanere bloccato negli ottimi locali e avere difficoltà a spostarsi verso altre aree lungo la distribuzione.
Ora, tenendo presente l’algoritmo Metropolis-Hastings, diamo un’occhiata a un altro suo esempio speciale: il campionamento di Gibbs.
Gibbs Sampling è un’istanza speciale di Metropolis-Hastings dove ogni passo è sempre accettato. Diamo prima un’occhiata all’algoritmo di campionamento di Gibbs stesso.
Come funziona l’algoritmo di Gibbs?
L’idea è relativamente semplice ed è meglio illustrata ingrandendo innanzitutto un microesempio che coinvolge il campionamento da una distribuzione p(z1, z2, z3) su 3 variabili. L’algoritmo verrebbe eseguito nei seguenti passaggi:
- Al momento opportuno T, inizializzare i valori iniziali su:
2. Disegna il nuovo valore per z1:
3. Disegna un nuovo valore per la seconda posizione, z2 dal condizionale:
4. Infine traccia un nuovo valore per l’ultima posizione, z3:
5. Ripetere questo processo, scorrendo le tre variabili z1…z3 fino a raggiungere una certa soglia soddisfacente.
Algoritmo generalizzato
Formalmente, l’algoritmo è rappresentato prima dall’inizializzazione delle posizioni di partenza e poi dall’assunzione T passaggi consecutivi
Condizioni affinché Gibbs possa campionare correttamente da una distribuzione target
- Invarianza. La distribuzione degli obiettivi p(z) è invariante per ogni passo di Gibbs, e quindi p(z) è invariante dell’intera catena di Markov.
- Ergodicità. Se le distribuzioni condizionali sono tutte diverse da zero, allora l’ergodicità è implicita a partire da qualsiasi punto z lo spazio è raggiungibile in un numero finito di passi.
- Burn-in sufficiente. Come abbiamo visto con qualsiasi metodo che richiede un’inizializzazione casuale, i primi campioni dipendono dall’inizializzazione e la dipendenza si indebolisce dopo molte iterazioni.
Come si collega tutto questo a Metropolis-Hastings?
In Metropolis-Hastings, abbiamo definito la soglia di accettazione come:
Pertanto, i passaggi della proposta di Metropolis-Hastings vengono sempre accettati, come abbiamo visto nell’algoritmo di Gibbs.
Variazioni
Poiché il metodo Gibbs aggiorna una variabile alla volta, esistono forti dipendenze tra campioni consecutivi. Per superare questo problema, potremmo utilizzare una strategia intermedia da cui campionare gruppi di variabili invece di variabili individuali, conosciuto come bloccando Gibbs.
Allo stesso modo, per la natura delle catene di Markov, gli esempi tracciati successivamente saranno correlati. Per generare campioni indipendenti, potremmo utilizzare il sottocampionamento all’interno della sequenza.
Ora che abbiamo esaminato il funzionamento di ciascun algoritmo e le sue aree di applicazione, riassumiamo le caratteristiche distintive di ciascun metodo.
1. Campionamento con trasformazione inversa
- Dimensione dei dati: Ideale 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.
- Valuta di evitare se: Campionamento di variabili/distribuzioni ad alta dimensione.
- Il più grande vantaggio: Alta precisione se il CDF riflette accuratamente la distribuzione target.
- Requisiti: La CDF deve essere conosciuta e invertibile.
2. Metropolis-Hastings (MCMC)
- Dimensione dei dati: Scalabile e adatto a set di dati di grandi dimensioni.
- Tempo: Può richiedere un utilizzo intensivo del calcolo, a seconda della complessità della distribuzione target.
- Complessità dei dati: Ideale per distribuzioni complesse o multimodali.
- I maggiori vantaggi:
– Può campionare da una distribuzione senza conoscerne la costante di normalizzazione (la forma completa)
– Ottimo per esplorare la struttura globale di una distribuzione e garantisce la convergenza - Svantaggio: Può soffrire di una convergenza molto lenta con
– distribuzione target complessa o multimodale, poiché l’algoritmo potrebbe rimanere bloccato in modalità locali e avere difficoltà nella transizione tra di esse;
– le variabili sono altamente correlate;
– spazi ad alta dimensionalità;
– Valori iniziali inadeguati o scelte relative alla dimensione del passo
3. Campionamento di Gibbs
- Dimensione dei dati: Adatto sia per set di dati piccoli che grandi.
- Tempo: Spesso più efficiente di Random Walk Metropolis-Hastings poiché non richiede passaggi di accettazione/rifiuto.
- Complessità dei dati: ideale quando si ha a che fare con distribuzioni ad alta dimensione in cui è possibile campionare dalla distribuzione condizionale di ciascuna variabile.
- I maggiori vantaggi:
– Può facilmente calcolare distribuzioni condizionali;
– Meno incline alle trappole dei minimi locali rispetto a Random Walk. - Requisiti:
– Ergodicità della catena di Markov
– Le distribuzioni condizionali complete devono essere conosciute e trattabili
