Fueron desarrolladas por Pearl en 1988 como un algoritmo exacto para realizar inferencia probabilística sobre Redes Bayesianas acíclicas y como una aproximación útil en Redes Bayesianas con ciclos.Este enfoque se vuelve computacionalmente prohibitivo (en sistemas de tamaños relativamente pequeños), suponiendo queEl modelo gráfico usado en adelante es llamado factor graph, esto no representa ninguna limitación pues estos modelos son equivalentes y es posible la conversión entre estos.y representados gráficamente como cuadrados, existe una arista entre un nodo variableEstos mensajes contiene la influencia de una variable sobre otra.El cálculo de los mensajes posee diferente forma según los nodos emisores y receptores.es el producto de todos los mensajes que recibe la variableSi el modelo gráfico posee forma de árbol, existe un esquema de actualización que garantiza convergencia (ver siguiente sección).Si se cumple que el proceso converge, usualmente que los mensajes dejen de cambiar, que no se garantiza en grafos generales, es posible obtener la distribución marginal computada por la propagación de creencias.En la primera iteración los mensajes son inicialmente computados en las hojas y “suben” en la estructura hasta alcanzar la raíz.La segunda iteración se compone de enviar los mensajes de forma contraria, comenzando en la raíz y haciéndolos “descender” hasta las hojas.El algoritmo termina cuando todas las hojas hayan recibido su mensaje.El algoritmo de propagación de creencias fue diseñado para modelos gráficos acíclicos (árboles), se ha comprobado que es posible usarlo en grafos generales, este algoritmo usualmente es llamado algoritmo “cíclico” de propagación de creencias debido a que estos grafos contienen ciclos.La inicialización y los esquemas de actualización son diferentes del esquema anterior visto en árboles, debido a que estos grafos pueden no contener hojas.Existen varias condiciones suficientes, pero no necesarias, sobre la convergencia en un grafo con ciclos; también se conocen grafos en los cuales no resulta posible la convergencia.Un método para el computo de marginales en grafos generales es el algoritmo junction tree.La propagación de creencias computa, o en grafos generales aproxima, probabilidades marginales.colores, las ecuaciones de BP siempre convergen a marginales uniformes, esta es la solución correcta pero no brinda ninguna información útil.Por esto se han desarrollado varias aplicaciones para la aproximación a este valor.de prueba y su correspondiente energía libre variacional definida por:Cuando el tamaño del sistema posee dimensiones grandes este procedimiento se vuelve intratable.para el factor graph, es posible computar la energía libre en la aproximación de campo medio.Existen varias maneras de definir las regiones del modelo gráfico que intercambiaran mensajes; una de ellas plantea que una región es un conjunto de variables y nodos factores tal que si un nodo factor pertenece a una región, entonces las variables en su vecindario también pertenecen a esta región.Esta generalización permitió la creación de un nuevo tipo de algoritmo llamado Survey Propagation el cual ha probado ser muy útil en problemas en la clase NP-Completos como satisfacibilidad booleana[17] y cubrimiento mínimo en grafos.El primer trabajo en analizar este modelo especial fue realizado por Weiss y Freeman.Equivalentemente puede ser mostrado que usando el modelo gaussiano, la solución al problema de marginalización es equivalente al problema MAP.Que es a la vez equivalente al sistema de ecuación linearLa primera de estas fue formulada por Weiss y colaboradores en el 2000, que garantiza la convergencia cuando la matriz A es diagonalmente dominante, y la segunda fue formulada por Johnson y colaboradores en 2006 que asegura la convergencia cuando el radio espectral de la matriz cumpleExperimentos muestran que la propagación de creencias con distribución gaussiana converge más rápido que otros métodos iterativos clásicos como el método de Jacobi, el método de Gauss-Seidel[23] y posee buena tolerancia a los problemas numéricos del método del gradiente conjugado de precondición.
Representación parcial de un factor graph. Resulta útil imaginarse que dentro de los nodos factores (cuadrados) radica una función
que expresa la interacción entre las variables que residen en su vecindad
Factor Graph que representa la siguiente función de probabilidad conjunta:
Propagación de creencias con decimación aplicada al problema de coloreado de grafo con 3 colores y distintos grados de conectividad. La figura muestra la probabilidad de encontrar una asignación de colores válida en función del grado de conectividad. La propagación de creencias basada en la decimación es capaz de encontrar soluciones para valores mayores de
, donde la propagación de creencias estima de forma incorrecta los marginales o no converge.
Las regiones son conjuntos de variables y nodos factores de un factor graph, tal que todas las variables conectadas a un nodo factor incluido se encuentran incluidas. Los conjuntos compuestos por los nodos {1,2} y {B, C, 2, 3, 4} pueden ser regiones pero el conjunto {B,3} no, pues los nodos {2,4} no pertenecen a este conjunto
