Propagació de creences

Representació parcial d'un factor graph. Resulta útil imaginar-se que dins dels nodos factors (cuadrados) radica una funció f a (x a) {\displaystyle f_{a}(x_{a})} que expressa la interacció entre les variables que resideixen al seu veïnat.

La propagació de creences, també coneguda com a transmissió de missatges suma-producte, és un algorisme de pas de missatges per realitzar inferències sobre models gràfics, com ara xarxes bayesianes i camps aleatoris de Markov. Calcula la distribució marginal per a cada node (o variable) no observat, condicionada a qualsevol node (o variable) observat. La propagació de creences s'utilitza habitualment en la intel·ligència artificial i la teoria de la informació, i ha demostrat un èxit empíric en nombroses aplicacions, com ara codis de control de paritat de baixa densitat, codis turbo, aproximació d'energia lliure i satisfacció.

L'algorisme va ser proposat per primera vegada per Judea Pearl l'any 1982, que el va formular com un algorisme d'inferència exacta sobre arbres, més tard estès als arbres. Tot i que l'algorisme no és exacte en gràfics generals, s'ha demostrat que és un algorisme aproximat útil.

Donat un conjunt finit de variables aleatòries discretes $X_{1},\ldots ,X_{n}$ amb funció de massa de probabilitat conjunta $p$, una tasca habitual és calcular les distribucions marginals de la $X_{i}$. El marginal d'un sol $X_{i}$ es defineix per ser

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

on $\mathbf {x} '=(x'_{1},\ldots ,x'_{n})$ és un vector de valors possibles per a $X_{i}$, i la notació $\mathbf {x} ':x'_{i}=x_{i}$ significa que la suma s'agafa per sobre d'aquests $\mathbf {x} '$ de qui $i$ la coordenada és igual a $x_{i}$.

El càlcul de distribucions marginals mitjançant aquesta fórmula esdevé ràpidament computacionalment prohibitiu a mesura que creix el nombre de variables. Per exemple, donades 100 variables binàries $X_{1},\ldots ,X_{100}$, calculant un únic marginal $X_{i}$ utilitzant $p$ i la fórmula anterior implicaria la suma $2^{99}\approx 6.34\times 10^{29}$ valors possibles per $\mathbf {x} '$. Si se sap que la funció de massa de probabilitat $p$ factors d'una manera convenient, la propagació de creences permet calcular els marginals de manera molt més eficient.