L'algoritmo dell'albero di giunzione, noto anche come algoritmo di Lauritzen-Spiegelhalter, è un metodo di inferenza esatta utilizzato nell'ambito dei modelli grafici probabilistici, come le reti bayesiane e i campi casuali di Markov. Il suo scopo principale è calcolare le probabilità marginali a posteriori di variabili non osservate, dato un insieme di evidenze.
L'algoritmo trasforma un grafo orientato o non orientato in un albero i cui nodi (chiamati cluster o cricche) contengono sottoinsiemi di variabili della rete originale. Una volta ottenuto l'albero di giunzione, l'inferenza viene eseguita tramite un protocollo di passaggio dei messaggi (message passing).
Fondamenti matematici Sia dato un insieme di variabili casuali e una distribuzione di probabilità congiunta fattorizzata secondo un grafo. L'obiettivo è calcolare , dove è il sottoinsieme delle variabili osservate.
L'albero di giunzione soddisfa la proprietà dell'intersezione corrente (o proprietà dell'albero di giunzione): se una variabile appartiene a due nodi dell'albero e , essa deve appartenere a tutti i nodi sul cammino unico che collega a . Questo garantisce la coerenza locale e globale delle distribuzioni marginali.
Fasi dell'algoritmo La costruzione dell'albero di giunzione e il successivo calcolo dell'inferenza si articolano in cinque fasi principali:
1. Moralizzazione Se il grafo di partenza è una rete bayesiana (diretto), deve essere convertito in un grafo non orientato. Per ogni nodo, vengono inseriti archi non orientati tra tutti i suoi genitori ("sposando" i genitori, da cui il termine "moralizzazione") e vengono rimossi i versi delle frecce. Il grafo risultante è detto grafo morale .
2. Triangolazione Il grafo morale viene triangolato inserendo archi aggiuntivi (archi di corda) in modo che non vi siano cicli non orientati di lunghezza maggiore o uguale a 4 senza una corda. Un grafo triangolato è anche detto grafo cordale. La triangolazione è un problema NP-difficile se si vuole minimizzare la dimensione delle cricche risultanti; tipicamente si usano euristiche come l'eliminazione dei nodi a grado minimo.
3. Costruzione dell'albero di giunzione Dato il grafo triangolato: Si identificano tutte le cricche massimali . Si costruisce un grafo delle cricche in cui i pesi degli archi rappresentano la cardinalità dell'intersezione tra le cricche: (chiamati separatori). Si calcola il massimo albero ricoprente (Maximum Spanning Tree) di questo grafo utilizzando l'algoritmo di Kruskal o di Prim. L'albero risultante è l'albero di giunzione.
4. Inizializzazione del potenziale A ogni cricca e a ogni separatore viene associata una funzione di potenziale, rispettivamente e . Inizialmente, . Ogni funzione di probabilità condizionata (CPT) o potenziale del grafo originale viene assegnata a una (e una sola) cricca che contiene le variabili della funzione stessa. Il potenziale della cricca è il prodotto delle funzioni ad essa assegnate:
5. Passaggio dei messaggi (calibrazione) L'inferenza avviene mediante l'aggiornamento dei potenziali lungo l'albero attraverso il protocollo di Shafer-Shenoy o in quello di Hugin. Nel protocollo Hugin, il passaggio di un messaggio dalla cricca alla cricca tramite il separatore segue le seguenti formule:
Si calcola il nuovo potenziale del separatore proiettando il potenziale di :
Si aggiorna il potenziale della cricca :
L'algoritmo esegue una fase di raccolta (Collect Evidence) verso una cricca radice e una fase di distribuzione (Distribute Evidence) dalla radice alle foglie. Al termine, l'albero è detto calibrato.
Complessità computazionale La complessità temporale e spaziale dell'algoritmo dell'albero di giunzione è dominata dalla dimensione della cricca più grande nel grafo triangolato. Sia la tree-width del grafo (ovvero la dimensione della cricca più grande meno uno), la complessità è dell'ordine di:
dove è il numero massimo di stati (cardinalità) delle variabili discrete e è la dimensione della cricca. Pertanto, l'algoritmo è efficiente per grafi con tree-width ridotta, ma diventa intrattabile su grafi densamente connessi.
Note
Voci correlate Belief propagation Campo casuale di Markov Cricca (teoria dei grafi) Eliminazione di variabili Modello grafico Rete bayesiana Treewidth
Categoria:Ragionamento probabilistico Categoria:Algoritmi Categoria:Teoria dei grafi Categoria:Informatica