Belief propagation

Nel campo dell'intelligenza artificiale, l'algoritmo belief propagation, noto anche come sum–product message passing, è un algoritmo a passaggio di messaggi (message-passing) per fare inferenza su modelli grafici, quali le reti bayesiane e le reti markoviane.

L'algoritmo calcola la distribuzione marginale per ciascuno dei nodi (ossia variabili) non osservati, sotto il condizionamento di quelli osservati (ovvero le relative variabili). L'algoritmo belief propagation viene tipicamente utilizzato nei settori della teoria dell'informazione e del ragionamento automatico e, sotto il profilo empirico, si è dimostrato di successo in numerose applicazioni, fra le quali la soddisfacibilità^[1].

L'algoritmo è stato proposto in prima istanza da J. Pearl nel 1982,^[2] che lo ha formulato come algoritmo di inferenza esatta su alberi ed è stato poi esteso ai polialberi ^[3] . Pur non risultando esatto nel caso di strutture di grafo arbitrarie più complesse, esso si è dimostrato utile come algoritmo di inferenza approssimata^[4].

Se ${\displaystyle X=\{X_{i}\}}$ è un insieme di variabili discrete con distribuzione congiunta ${\displaystyle p}$, la distribuzione marginale di un solo elemento ${\displaystyle X_{i}}$ risulta semplicemente come la somma di ${\displaystyle p}$ su tutte le altre variabili:

${\displaystyle p_{X_{i}}(x_{i})=\sum _{\mathbf {x} ':x'_{i}=x_{i}}p(\mathbf {x} ').}$

Tuttavia, al crescere del numero delle variabili questo calcolo diventa presto proibitivo: con 100 variabili binarie, si deve sommare sui 2⁹⁹ ≈ 6.338 × 10²⁹ possibili valori. Sfruttando la struttura del grafo sottostante, come quella ad albero, la propagazione delle probabilità permette di calcolare le marginali in modo molto più efficiente.

Esistono diverse varianti dell'algoritmo per i differenti tipi di grafi (in particolare reti bayesiane e markoviane^[5]). Si descriverà nel seguito la variante per grafi fattorizzati. Un grafo fattorizzato è un grafo bipartito contenente nodi corrispondenti a variabili ${\displaystyle V}$ e a fattori ${\displaystyle F}$, con archi fra le variabili e i fattori nei quali esse occorrono. Si può quindi scrivere la congiunta come segue:

${\displaystyle p(\mathbf {x} )=\prod _{a\in F}f_{a}(\mathbf {x} _{a})}$

dove ${\displaystyle x_{a}}$ è il vettore dei nodi vicini del fattore ${\displaystyle a}$. Qualunque rete bayesiana o markoviana può essere rappresentata come grafo fattorizzato.

L'algoritmo prevede il “passaggio” di funzioni a valore reale, chiamate messaggi, lungo i collegamenti fra i nodi nascosti. Più precisamente, se ${\displaystyle v}$ è un nodo-variabile e ${\displaystyle a}$ è un nodo nodo-fattore connesso a v nel grafo, i messaggi da ${\displaystyle v}$ ad ${\displaystyle a}$, (denotati da ${\displaystyle \mu _{v\to a}}$) e da ${\displaystyle a}$ a ${\displaystyle v}$ (${\displaystyle \mu _{a\to v}}$), sono funzioni a valori reali con dominio ${\displaystyle Dom(v)}$, l'insieme dei valori che può assumere la variabile casuale associata a ${\displaystyle v}$. Tali messaggi contengono le influenze che una variabile esercita sull'altra. I messaggi vengono calcolati in base al fatto che il nodo ricevente sia un nodo-variabile o un nodo-fattore. Mantenendo la notazione precedente:

• Un messaggio da un nodo-variabile ${\displaystyle v}$ a un nodo-fattore ${\displaystyle a}$ è il prodotto dei messaggi di tutti gli altri nodi-fattore vicini (eccetto il destinatario; viceversa, si può dire che il destinatario invia un messaggio con la funzione costante pari a ${\displaystyle 1}$):

${\displaystyle \forall x_{v}\in Dom(v),\;\mu _{v\to a}(x_{v})=\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\to v}(x_{v}).}$

dove ${\displaystyle N(v)}$ è l'insieme dei nodi fattore vicini a ${\displaystyle v}$. Se ${\displaystyle N(v)\setminus \{a\}}$ è vuoto, allora ${\displaystyle \mu _{v\to a}(x_{v})}$ è fissato alla distribuzione uniforme su ${\displaystyle Dom(v)}$.

• Un messaggio da un nodo-fattore ${\displaystyle a}$ a un nodo-variabile ${\displaystyle v}$ è il prodotto del fattore con i messaggi di tutti gli altri nodi: si marginalizzano tutte le variabili tranne quella associata a ${\displaystyle v}$:

${\displaystyle \forall x_{v}\in Dom(v),\;\mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}f_{a}(\mathbf {x} '_{a})\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}}).}$

dove ${\displaystyle N(a)}$ è l'insieme dei nodi-variabile vicini rispetto ad a. Se ${\displaystyle N(a)\setminus \{v\}}$ è vuoto allora ${\displaystyle \mu _{a\to v}(x_{v})=f_{a}(x_{v})}$ poiché in questo caso ${\displaystyle x_{v}=x_{a}}$.

Come mostrato dalla formula precedente la marginalizzazione completa si riduce a una somma di prodotti di termini più semplici di quelli che occorrono nella distribuzione congiunta completa. Questa è la ragione per cui l'algoritmo viene chiamato a volte message passing somma-prodotto o algoritmo somma-prodotto.

In a tipica esecuzione, ciascun messaggio sarà aggiornato iterativamente a partire dai valori precedenti dei messaggi del vicinato. Per l'aggiornamento dei messaggi si possono usare diverse schedulazioni. Nel caso in cui il modello grafico sia un albero, una schedulazione ottimale converge dopo aver calcolato ogni messaggio esattamente una volta. Quando il grafo dei fattori ha dei cicli, tale schedulazione ottimale non esiste e una scelta tipica è quella di aggiornare tutti i messaggi simultaneamente a ogni iterazione.

Al momento della convergenza (se la convergenza è avvenuta), la distribuzione marginale stimata di ogni nodo è proporzionale al prodotto di tutti i messaggi dei fattori vicini (manca solo la costante di normalizzazione):

${\displaystyle p_{X_{v}}(x_{v})\propto \prod _{a\in N(v)}\mu _{a\to v}(x_{v}).}$

Analogamente, la distribuzione marginale congiunta stimata dell'insieme di variabili appartenenti a un dato fattore è proporzionale al prodotto del fattore e dei messaggi dalle variabili:

${\displaystyle p_{X_{a}}(\mathbf {x} _{a})\propto f_{a}(\mathbf {x} _{a})\prod _{v\in N(a)}\mu _{v\to a}(x_{v}).}$

Nel caso in cui il grafo dei fattori sia aciclico (ad esempio un albero o una foresta), queste distribuzioni marginali stimate convergono proprio verso le distribuzioni marginali effettive in un numero finito di iterazioni. Questo può essere dimostrato per induzione.