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 amb funció de massa de probabilitat conjunta , una tasca habitual és calcular les distribucions marginals de la . El marginal d'un sol es defineix per ser
on és un vector de valors possibles per a , i la notació significa que la suma s'agafa per sobre d'aquests de qui la coordenada és igual a .
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 , calculant un únic marginal utilitzant i la fórmula anterior implicaria la suma valors possibles per . Si se sap que la funció de massa de probabilitat factors d'una manera convenient, la propagació de creences permet calcular els marginals de manera molt més eficient.