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,\dots ,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 _{{𝐱}^{\prime }:x{\text{'}}_i=x_i}p({𝐱}^{\prime })$

on ${𝐱}^{\prime }=(x{\text{'}}_1,\dots ,x{\text{'}}_n)$ és un vector de valors possibles per a $X_i$, i la notació ${𝐱}^{\prime }:x{\text{'}}_i=x_i$ significa que la suma s'agafa per sobre d'aquests ${𝐱}^{\prime }$ 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,\dots ,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 ${𝐱}^{\prime }$. 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.