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ó.^[1]

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

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

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

on ${\displaystyle \mathbf {x} '=(x'_{1},\ldots ,x'_{n})}$ és un vector de valors possibles per a ${\displaystyle X_{i}}$, i la notació ${\displaystyle \mathbf {x} ':x'_{i}=x_{i}}$ significa que la suma s'agafa per sobre d'aquests ${\displaystyle \mathbf {x} '}$ de qui ${\displaystyle i}$ la coordenada és igual a ${\displaystyle 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 ${\displaystyle X_{1},\ldots ,X_{100}}$, calculant un únic marginal ${\displaystyle X_{i}}$ utilitzant ${\displaystyle p}$ i la fórmula anterior implicaria la suma ${\displaystyle 2^{99}\approx 6.34\times 10^{29}}$ valors possibles per ${\displaystyle \mathbf {x} '}$. Si se sap que la funció de massa de probabilitat ${\displaystyle p}$ factors d'una manera convenient, la propagació de creences permet calcular els marginals de manera molt més eficient.