Propagació de creences

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ó.

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.

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.