Algoritme de propagació de creències

El algoritme de propagació de creències (en inglés: belief propagation algorithm), també conegut com el algoritme suma-producte, és un algoritme de pas de mensages per a realisar inferència sobre models gràfics tals com rets bayesianas, camps aleatoris de Markov i factor graph. És àmpliament utilisat en els camps d'inteligència artificial i teoria de l'informació i ha mostrat cert èxit experimental en aplicacions tan diferents com: anàlisis de paritat de còdics, aproximacions d'energia lliure, coloreado de grafos i satisfacibilidad booleana.

Les equacions de propagació de creències han segut redescubiertas vàries voltes. Varen ser desenrollades per Pearl en 1988 com un algoritme exacte per a realisar inferència provabilística sobre Rets Bayesianas acícliques i com una aproximació útil en Rets Bayesianas en cicles. En els inicis dels 60 Gallager les va introduir com un procediment iterativo per a la recuperació de còdics de paritat.

Siga $X=(X_1,X_2,\mathrm{...},X_N)$ un conjunt de $n$ variables aleatòries discretes, denotarem en $x_i$ la realisació de la variable aleatòria $X_i$. En funció de distribució conjunta $P(X_1=x_1,X_2=x_2,\mathrm{...},X_n=x_n)$ usualment escrita com $p(x)$ a on $x=(x_1,x_2,\mathrm{...},x_n)$.

És possible expressar $p(x)$ com un producte de funcions:

$P(x)=\frac{1}{Z}\prod _a{f}_a(x_a)$

A on $a$ és un índex sobre les $M$ funcions $f_A,f_B,\mathrm{...},f_M$ en que es descomponen $P(x)$, la funció $f_a(x_a)$ posseïx com a argument $x_a$ que és un subconjunt de les variables aleatòries $\{x_1,x_2,\mathrm{...},x_n\}$.

Llavors la distribució marginal d'una variable donada $x_i$ és simplement la suma de $P$ sobre totes les restants variables.

$P(x_i)=\sum _{X^{\prime }=X/x_i}p(X^{\prime })=\sum _{(x_1,\mathrm{...},x_{i-1},x_{i+1},\mathrm{...},x_N)}P(x_1,\mathrm{...},x_{i-1},x_i,x_{i+1},\mathrm{...},x_N)$Este enfocament es torna computacionalment prohibitivo (en sistemes de tamanys relativament menuts), suponent que $n=100$ i les variables són binarias. Llavors per a obtindre el valor marginal de $P(x_i)$computar $2^{99}$ valors possibles. Explotant l'estructura de poliárbolés, l'algoritme de propagació de creències permet el càlcul dels marginals de manera més eficient en temps llineal respecte al tamany del sistema.

Descripció de l'algoritme

Representació parcial d'un factor graph. Resulta útil imaginar-se que dins dels nodos factors (quadrats) radica una funció $f_a(x_a)$ que expressa l'interacció entre les variables que residixen en el seu veïnat

Existixen variants de l'algoritme de propagació de creències per a diferents models gràfics (Rets bayesianas, i camps aleatoris de Markov). El model gràfic usat en avant és cridat factor graph, açò no representa cap llimitació puix estos models són equivalents i és possible la conversió entre estos. Un factor graph és un grafo bipartito en dos tipos de nodos: nodos variables, usualment denotats per les lletres $i,j,k,\mathrm{...}$ i representats gràficament en círculs, i nodos factors, usualment denotats per les lletres $a,b,c,\mathrm{...}$ i representats gràficament com a quadrats, existix una aresta entre un nodo variable $i$ i un nodo funció $a$ si i solament si $i$ es troba en l'argument de $f_a(x_a)$ . Cridarem $V$ al conjunt de nodos variables i $F$ al conjunt dels nodos factors.

L'algoritme funciona enviant “mensages” entre els nodos variables i nodos factors. De forma més específica si $i\in V$ i $a\in F$ el mensage enviat des de $i$ cap a $a$ és l'evaluació d'una funció $n:V\to ℝ$ i de forma alterna el mensage enviat des de $a$ cap a $i$ és l'evaluació d'una funció $m:F\to ℝ$. Estos mensages conté l'influència d'una variable sobre una atra. El càlcul dels mensages posseïx diferent forma segons els nodos emissors i receptors.

Un mensage enviat des d'una variable $i$ a un nodo funció $a$ és el producte de tots els mensages que rep la variable $i$ dels nodos factors veïns $b$ llevat $a$.$n_{i\to a}(x_i)=\prod _{b\in N(i)/a}{m}_{b\to i}(x_i)$a on $N(i)/a$ és el conjunt dels nodos factors veïns de $i$ a excepció del nodo $a$. Si este conjunt és va buidar llavors $n_{i\to a}(x_i)$distribuïx de uniformemente sobre el conjunt de valors possibles de la variable $i$.

Un mensage enviat des d'un nodo factor $a$ cap a un nodo variable $i$ és el producte de la funció $f_a(x_a)$ evaluada en el veïnat de $a$ a excepció de $i$ que esta marginalizado al valor $x_i$.$m_{a\to i}(x_i)=\sum _{x_a/x_i}{f}_a(x_a)\prod _{j\in N(a)/i}{n}_{j\to i}(x_j)$Si $N(a)/i$ és buit llavors $m_{a\to i}(x_i)=f_a(x_i)$. La suma sobre $x_a/x_i$ és la suma sobretot el conjunt de tots els possibles valors de les variables veïnes de $a$ a excepció de $i$ que es troba marginalizada al valor $x_i$.

Inicialment el conjunt de mensages inicials es trien de manera aleatòria, després seguint cert esquema iterativo d'actualisació (usualment prendre un nodo aleatori i actualisar els mensages als seus veïns) en respectes als mensages anteriors es computen els nous mensages. Si el model gràfic posseïx forma d'arbre, existix un esquema d'actualisació que garantisa convergència (vore següent secció). Si es complix que el procés convergix, usualment que els mensages deixen de canviar, que no es garantisa en grafos generals, és possible obtindre la distribució marginal computada per la propagació de creències.

La distribució marginal estimada de cada nodo variable és proporcional al producte dels mensages dels nodos veïns.$P(x_i)=\frac{1}{{\alpha }_v}\prod _{a\in N(i)}{m}_{a\to i}(x_i)$En el cas dels nodos funció la distribució conjunta de les variables que són part del seu veïnat és proporcional al mensage rebut pel nodo.$P(x_a)=\frac{1}{{\alpha }_f}{f}_a(x_a)\prod _{a\in N(i)}{n}_{i\to a}(x_i)$a on ${\alpha }_v$ i ${\alpha }_f$ són constants de normalisació${\alpha }_v=\sum _{x_i}\prod _{a\in N(i)}{m}_{a\to i}(x_i)$${\alpha }_f=\sum _{x_a}f(x_a)\prod _{i\in N(a)}{n}_{i\to a}(x_i)$

Propagació de creències sobre arbres

Erro al crear miniatura:

Factor Graph que representa la següent funció de provabilitat conjunta:$p(x)=p_a(x_1,x_2)p_b(x_2,x_3,x_4)p_c(x_4)$

En el cas de que el model gràfic siga un arbre, l'algoritme de propagació de creències computa de manera exacta els marginals, seguint un esquema específic d'actualisació de mensage, este esquema termina després de 2 iteraciones. L'esquema d'actualisació es descriu a continuació:

Abans de començar, és seleccionat un nodo com a nodo raïl i qualsevol nodo no raïl que es troba conectat a un sol nodo és cridat full.

En la primera iteración els mensages són inicialment computats en els fulls i “pugen” en l'estructura fins a alcançar la raïl. L'estructura d'arbre garantisa que és possible obtindre tots els mensages dels veïns de cada nodo, llevat d'un d'ells, que serà el que rebrà el mensage.

La segona iteración es compon d'enviar els mensages de forma contrària, començant en la raïl i fent-los “descendir” fins als fulls. L'algoritme termina quan tots els fulls hagen rebut el seu mensage.

Com a eixemple concret del càlcul exacte dels marginals en arbres considerem la distribució de provabilitat donada en la figura superior. Usant repetidament les equacions de propagació de creències trobem que:

$P(x_1)=\alpha m_{a\to i}(x_1)$

$P(x_1)=\alpha \sum _{x_2}{f}_a(x_1,x_2)n_{2\to a}(x_2)$

$P(x_1)=\alpha \sum _{x_2}{f}_a(x_1,x_2)m_{b\to 2}(x_2)$

$P(x_1)=\alpha \sum _{x_2}\sum _{x_3}\sum _{x_4}{f}_a(x_1,x_2)f_b(x_2,x_3,x_4)n_{3\to b}(x_3)n_{4\to b}(x_4)$

$P(x_1)=\alpha \sum _{x_2}\sum _{x_3}\sum _{x_4}{f}_a(x_1,x_2)f_b(x_2,x_3,x_4)m_{c\to 4}(x_4)$

$P(x_1)=\alpha \sum _{x_2}\sum _{x_3}\sum _{x_4}{f}_a(x_1,x_2)f_b(x_2,x_3,x_4)f_c(x_4)$

Que és exactament la definició de provabilitat marginal i el seu factor de normalisació $\alpha$.