In statistica e in fisica statistica, un campionamento di Gibbs o un campionatore di Gibbs è un algoritmo MCMC per ottenere una sequenza di campioni casuali da una distribuzione di probabilità multivariata (cioè dalla distribuzione di probabilità congiunta di due o più variabili casuali) quando il campionamento diretto si dimostra difficoltoso. Questa sequenza può essere usata per approssimare la distribuzione congiunta (ad esempio per generare un istogramma della distribuzione); per approssimare la distribuzione marginale di una delle variabili, o di vari sottoinsiemi delle variabili (per esempio, parametri sconosciuti oppure variabili latenti); oppure ancora per calcolare un integrale (come il valore atteso di una delle variabili).
Il campionamento di Gibbs è comunemente usato come uno strumento per eseguire inferenza statistica, specialmente inferenza bayesiana. Per sua natura è un algoritmo casuale (cioè un algoritmo che fa uso di numeri casuali, e quindi può produrre risultati distinti ogni volta che viene eseguito), ed è un'alternativa agli algoritmi deterministici impiegati nell'inferenza statistica come l'algoritmo variazionale bayesiano o il metodo della massima verosimiglianza.
Introduzione Il campionamento di Gibbs prende nome dal fisico J. W. Gibbs, in relazione all'analogia tra l'algoritmo di campionamento e la fisica statistica. L'algoritmo fu descritto dai fratelli Stuart e Donald Geman nel 1984, più di otto decadi dopo la morte di Gibbs.
Il campionamento di Gibbs è applicabile quando la distribuzione congiunta non è nota esplicitamente oppure è difficile da campionare direttamente, ma è nota la distribuzione condizionata di ogni variabile e che si presuppone essere più facile da campionare. Il campionamento di Gibbs genera a turno per ogni variabile un campione dalla loro distribuzione condizionata sui valori correnti delle restanti variabili. Può essere dimostrato che la sequenza di campioni costituisce una catena di Markov e che la distribuzione stazionaria di tale catena è di fatto la distribuzione congiunta cercata.
Nella sua versione base il campionamento di Gibbs è un caso speciale dell'algoritmo di Metropolis-Hastings. Tuttavia, nelle sue versioni estese (cfr. più sotto), può essere inglobato in un contesto di riferimento generale per il campionamento di grandi insiemi di variabili mediante il campionamento di singole variabili (o in vari casi, di gruppi di variabili) a turno, e può incorporare l'algoritmo di Metropolis-Hastings (o metodi simili come il campionamento a strati) per implementare uno o più passi di campionamento.
Il campionamento di Gibbs è particolarmente adatto per campionare la distribuzione a posteriori di una rete bayesiana in quanto tale genere di rete è specificata tipicamente mediante una collezione di distribuzioni condizionate.
Implementazione Supponiamo di voler ottenere valori da una distribuzione congiunta ; si conosce per ciascuna componente di la probabilità condizionata .
Denotiamo l'elemento -esimo come e procediamo come segue:
Per assegniamo a un valore arbitrario nel supporto della probabilità condizionata . Per ogni campione , campioniamo ogni variabile dalla distribuzione condizionata . Campioniamo cioè ogni variabile della distribuzione da quest'ultima ma condizionandola su tutte le altre variabili, facendo uso dei loro valori più recenti ed aggiornando la variabile al suo nuovo valore non appena questo è stato campionato.
Il campione estratto in tal modo approssima la distribuzione congiunta di tutte le variabili. Inoltre, la distribuzione marginale di qualsiasi sottoinsieme di variabili può essere approssimata semplicemente esaminando i valori estratti per quel sottoinsieme di variabili, ignorando le restanti. In aggiunta, il valore atteso di qualsiasi variabile può essere approssimato con una media campionaria.
I valori iniziali delle variabili possono essere determinati casualmente o mediante qualche altro algoritmo come quello di expectation-maximization. Non è di fatto necessario determinare un valore iniziale per la prima variabile campionata. È pratica comune ignorare i valori campionati nella parte iniziale (il cosiddetto periodo di burn-in ossia di "riscaldamento") e in seguito prendere in considerazione solo un campione ogni n quando vengono richieste delle medie dei valori attesi. Per esempio, i primi 1000 campioni possono essere ignorati e successivamente utilizzarne solo un valore ogni 100 per il calcolo ad esempio di una media, scartando tutti gli altri. I motivi per procedere in questo modo sono che: I campioni consecutivi non sono indipendenti tra loro ma formano una catena di Markov con un certo grado di correlazione; La distribuzione stazionaria della catena di Markov è la distribuzione congiunta sopra le variabili desiderata, ma può richiedere tempo affinché venga raggiunta la stazionarietà. Talvolta, per determinare il grado di autocorrelazione tra i campioni e il valore di n (il valore del periodo dei campioni conservati per i calcoli) sono richiesti degli algoritmi aggiuntivi e comunque è necessaria una certa pratica. Il procedimento di simulated annealing viene spesso usato per ridurre l'effetto di random walk nella parte iniziale del processo di campionamento (cioè la tendenza a vagare lentamente nello spazio di campionamento, con un elevato grado di autocorrelazione tra i campioni, piuttosto che muoversi rapidamente, come desiderato). Altre tecniche che possono ridurre l'autocorrelazione sono il campionamento di Gibbs collassato il sovrarilassamento ordinato; cfr. più sotto.
La relazione tra distribuzione condizionata e distribuzione congiunta In aggiunta a quando detto finora, la distribuzione condizionata di una variabile date tutte le altre è proporzionale alla distribuzione congiunta:
Il segno di proporzionalità in questo caso significa che il denominatore non è una funzione di e perciò è il medesimo per tutti i valori di . In pratica, per determinare la natura della distribuzione condizionata del fattore è più semplice fattorizzare la distribuzione congiunta in accordo alle distribuzioni condizionate individuali definite tramite il modello grafico delle variabili (ossia il grafo associato alla struttura di indipendenza condizionata tra le varie variabili casuali in gioco, cfr. anche [grafo aleatorio]), ignorare tutti i fattori che non sono funzioni di (i quali tutti assieme, ed assieme con il denominatore sopra definito, costituiscono la costante di normalizzazione), e quindi alla fine reimpostare la costante di normalizzazione secondo la necessità. In pratica, questo significa fare una delle tre scelte: Se la distribuzione è discreta, vengono calcolate le probabilità individuali di tutti i possibili valori di , e quindi sommate per trovare la costante di normalizzazione. Se la distribuzione è continua e di una forma nota, la costante di normalizzazione è di conseguenza nota anch'essa. Negli altri casi, siccome molti metodi di campionamento non la richiedono, solitamente la costante di normalizzazione può essere ignorata.
Fondamento matematico Il campionamento di Gibbs, nella forma dell'algoritmo descritto sopra, definisce una catena di Markov reversibile con la distribuzione invariante desiderata . Questo può essere provato nel modo seguente: definiamo se per tutti gli e sia la probabilità di un salto da a . Allora, le probabilità di transizione sono
In tal modo
in quanto è una relazione di equivalenza. Perciò le equazioni di bilancio dettagliato sono soddisfatte, implicando che la catena è reversibile e che possiede una distribuzione invariante .
In pratica, il suffisso non è scelto a caso e la catena è ciclica nei suffissi posti in un certo ordine. In generale questo equivale ad un processo di Markov non stazionario, ma ogni singolo passo sarà ancora reversibile e il processo complessivamente avrà ancora la distribuzione stazionaria desiderata (fintanto che la catena può accedere a tutti gli stati nell'ordine prefissato).
Varianti ed estensioni Esistono numerose varianti del campionamento base di Gibbs. L'obiettivo di queste varianti è ridurre l'autocorrelazione tra i campioni in modo sufficiente da giustificare il costo associato all'elaborazione aggiuntiva.
Campionamento di Gibbs a blocchi Un campionamaneto di Gibbs a blocchi raggruppa assieme due o più variabili e campiona la loro distribuzione congiunta condizionata su tutte le variabili restanti, piuttosto che campionare da ogni singola variabile individualmente. Per esempio, in un modello di Makov nascosto, un campionamento di Gibbs a blocchi può campionare da tutte le variabili latenti costruendo la catena di Markov in un solo colpo mediante l'algoritmo forward-backward.
Campionamento di Gibbs collassato Un campionamento di Gibbs collassato integra marginalizzando sopra una o più variabili quando esegue il campionamento per altre variabili. Per esempio, immaginiamo che un modello consista di tre variabili A, B e C. Un semplice campionamento di Gibbs campionerebbe p(A|B,C), da p(B|A,C) e da p(C|A,B). Un campionamento di Gibbs collassato può sostituire il passo di campionamento per A con un campione preso dalla distribuzione marginale p(A|C), con in questo caso la variabile B integrata al di fuori (dell'ambito di integrazione delle altre due variabili). In alternativa, la variabile B può essere interamente fuori collassata ovvero esclusa dalla fase di calcolo, campionando da p(A|C) e da p(C|A) e non campionando del tutto da B. La distribuzione di una variabile A che è generata quando di collassa una variabile B che parametrizza la distribuzione di A è chiamata distribuzione composta; il campionamento da questa distribuzione è generalmente trattabile quando B è la variabile coniugata a priori per la variabile A, in particolare quando le distribuzioni di A e di B sono membri della famiglia esponenziale. Per ulteriori informazioni cfr. l'articolo sulle distribuzioni composte oppure Liu (1994).
L'implementazione di un campionamento di Gibbs collassato Collasso delle distribuzioni di Dirichlet Nei modelli bayesiani gerarchici con variabili categoriali, come il modello di allocazione di Dirichlet latente e vari altri modelli usati nell'elaborazione del linguaggio naturale, è pratica comune "fuori collassare" le distribuzioni di Dirichlet che tipicamente sono usate come distribuzione a priori per le variabili categoriali. Il risultato di questo collasso introduce dipendenze tra tutte le variabili categoriali dipendenti su una data distribuzione a priori di Dirichlet, e la distribuzione congiunta di queste variabili dopo il collasso è una distribuzione di Dirichlet multinomiale. La distribuzione condizionale di una data variabile categoriale in questa distribuzione, condizionata sulle altre variabili, assume una forma estremamente semplice che rende il campionamento di Gibbs anche più facile rispetto al caso in cui il collasso non fosse stato fatto. Le regole sono le seguenti: Fuori collassare una distribuzione a priori di Dirichlet influisce solo sui nodi genitori e figli della distribuzione a priori. Poiché il nodo generitore è spesso una costante, tipicamente è solo dei nodi figli che ci si deve preoccupare. Fuori collassare una distribuzione a priori di Dirichlet introduce dipendenze tra tutte le variabili categoriali figlie dipendenti su tale distribuzione a priori, ma non introduce nessuna dipendenza ulteriore tra variabili categoriali figlie. (Questo è importante tenerlo a mente, per esempio, ci sono distribuzioni a priori di Dirichlet multiple collegate tra loro da qualche distribuzione a priori più generale. Ogni distribuzione a priori di Dirichlet può essere collassata indipendentemente ed influisce solo sulle distribuzioni figlie).