Grafo con fattori

Un grafo con fattori (da factor graph) è un grafo bipartito che rappresenta la fattorizzazione di una funzione. In teoria della probabilità e sue applicazioni, i grafi con fattori vengono utilizzati per rappresentare la fattorizzazione di una funzione di distribuzione di probabilità, consentendo di rendere efficienti diversi calcoli, come quello delle distribuzioni marginali tramite l'algoritmo somma-prodotto.

Una delle più importanti applicazioni di successo dei grafi con fattori e dell'algoritmo somma-prodotto è la decodifica dei codici di correzione degli errori, come i codici LDPC e turbo.

I grafi con fattori generalizzano i grafi di vincoli. Un fattore il cui valore è $0$ o $1$ è chiamato vincolo. Un grafo con vincoli è un grafo con fattori in cui tutti i fattori sono vincoli. L'algoritmo del prodotto massimo per i grafi con fattori può essere visto come una generalizzazione dell'algoritmo di coerenza degli archi usato nel ragionamento su vincoli.

Definizione

Formalmente, un grafo con fattori è un grafo bipartito che rappresenta la fattorizzazione di una funzione.

Data una funzione $g(X_{1},X_{2},\dots ,X_{n})$, fattorizzata come

$g(X_{1},X_{2},\dots ,X_{n})=\prod _{j=1}^{m}f_{j}(S_{j}),$

dove $S_{j}\subseteq \{X_{1},X_{2},\dots ,X_{n}\}$, il grafo con fattori corrispondente $G=(X,F,E)$ sarà costituito da nodi-variabile $X=\{X_{1},X_{2},\dots ,X_{n}\}$, nodi-fattore $F=\{f_{1},f_{2},\dots ,f_{m}\}$ e da archi $E$. Gli archi dipendono dalla fattorizzazione nel modo seguente: se $X_{k}\in S_{j}$ ci sarà un arco non orientato che connette il nodo del fattore $f_{j}$ e il nodo della variabile $X_{k}$. Si assume che la funzione sia a valori reali: $g(X_{1},X_{2},\dots ,X_{n})\in \mathbb {R}$ .

Sui grafi con fattori si possono usare algoritmi a passaggio di messaggi per calcolare in modo efficiente caratteristiche di interesse relative alla funzione $g(X_{1},X_{2},\dots ,X_{n})$, come ad esempio le distribuzioni marginali.

Esempi

Esempio di grafo con fattori

Si consideri una funzione fattorizzata come segue:

$g(X_{1},X_{2},X_{3})=f_{1}(X_{1})f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})f_{4}(X_{2},X_{3})$ ,

con grafo con fattori corrispondente mostrato sulla destra. Si osservi che esso contiene un ciclo. Fondendo $f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})$ in un singolo fattore, il grafo con fattori risultante sarà un albero. Si tratta di una distinzione importante, poiché gli algoritmi message passing forniscono solitamente soluzioni esatte per gli alberi, ma solo approssimative per i grafi con cicli.

Passaggio di messaggi su grafi con fattori

Un algoritmo di passaggio di messaggi comunemente in uso sui grafi fattori è l'algoritmo somma-prodotto, che calcola in modo efficiente tutte le distribuzioni marginali delle singole variabili della funzione. In particolare, la distribuzione marginale della variabile $X_{k}$ è definita come

$g_{k}(X_{k})=\sum _{X_{\bar {k}}}g(X_{1},X_{2},\dots ,X_{n})$

dove la notazione $X_{\bar {k}}$ indica che la sommatoria riguarda tutte le variabili, tranne $X_{k}$. Concettualmente, i messaggi dell'algoritmo somma-prodotto vengono calcolati nei nodi e sono trasmessi lungo gli archi. Un messaggio da o verso un nodo-variabile è sempre una funzione di quella particolare variabile. Ad esempio, se una variabile è binaria, i messaggi attraverso gli archi incidenti nel nodo corrispondente possono essere rappresentati come vettori di lunghezza 2: la prima componente è il messaggio valutato in 0, la seconda è il messaggio valutato in 1. Se la variabile è continua, i messaggi possono essere funzioni arbitrarie e occorrerà prestare particolare attenzione alla loro rappresentazione.

Sul fronte pratico, l'algoritmo somma-prodotto viene utilizzato per fare inferenza statistica, per cui $g(X_{1},X_{2},\dots ,X_{n})$ è una distribuzione congiunta o una funzione di verosimiglianza congiunta e la fattorizzazione dipenderà dalle relazioni di indipendenza condizionata tra le variabili.

Il teorema di Hammersley-Clifford dimostra che altri modelli probabilistici, come le reti bayesiane e le reti di Markov, possono essere rappresentati come grafi con fattori; quest'ultima rappresentazione è frequentemente utilizzata quando si fa inferenza su tali reti utilizzando l'algoritmo belief propagation. D'altro canto, le reti bayesiane sono più adatte a supportare modelli generativi, in quanto possono rappresentare direttamente le relazioni di causalità del modello.

Bibliografia

• Clifford, Markov random fields in statistics (ps), in Grimmett, G.R.; Welsh, D.J.A. (a cura di), Disorder in Physical Systems, J.M. Hammersley Festschrift, OUP, 1990, pp. 19–32, ISBN 9780198532156.
• Frey, Brendan J., Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models, UAI'03, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence, 2003, ISBN 0127056645, arXiv:1212.2486.
• Kschischang, Frank R.; Frey, Brendan J.; Loeliger, Hans-Andrea, Factor Graphs and the Sum-Product Algorithm, vol. 47, 2001, DOI:10.1109/18.910572.
• Wymeersch, Henk, Iterative Receiver Design, in IEEE Transactions on Information Theory, CUP, 2007, ISBN 978-0-521-87315-4.

Voci correlate

• Belief propagation
• Inferenza bayesiana
• Probabilità condizionata
• Rete bayesiana

Collegamenti esterni

• Loeliger, Hans-Andrea, An Introduction to Factor Graphs (PDF), in IEEE Signal Processing Magazine, vol. 21, n. 1, pp. 28–41, Bibcode:2004ISPM...21...28L, DOI:10.1109/MSP.2004.1267047.
• dimple: strumento open-source per costruire e risolvere grafi con fattori in MATLAB., su dimple.probprog.org (archiviato dall'url originale il 6 gennaio 2016).
• Loeliger, Hans-Andrea, An introduction to Factor Graphs (PDF), 2008.