miniatura|300x300px|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 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.
Referències
Categoria:Aprenentatge automàtic