Propagación de creencias

Algoritmo para inferencia estadística sobre modelos gráficos

La propagación de creencias , también conocida como transmisión de mensajes de suma-producto , es un algoritmo de transmisión de mensajes para realizar inferencias en modelos gráficos , como redes bayesianas y campos aleatorios de Markov . Calcula la distribución marginal para cada nodo (o variable) no observado, condicional a cualquier nodo (o variable) observado. La propagación de creencias se utiliza comúnmente en inteligencia artificial y teoría de la información , y ha demostrado un éxito empírico en numerosas aplicaciones, incluidos códigos de verificación de paridad de baja densidad , códigos turbo , aproximación de energía libre y satisfacibilidad . ^[1]

El algoritmo fue propuesto por primera vez por Judea Pearl en 1982, ^[2] quien lo formuló como un algoritmo de inferencia exacto en árboles , que luego se extendió a poliárboles . ^[3] Si bien el algoritmo no es exacto en gráficos generales, se ha demostrado que es un algoritmo aproximado útil. ^[4]

Motivación

Dado un conjunto finito de variables aleatorias discretas con función de masa de probabilidad conjunta , una tarea común es calcular las distribuciones marginales de las . La marginal de una sola se define como ${\displaystyle X_{1},\ldots ,X_{n}}$ ${\displaystyle p}$ ${\displaystyle X_{i}}$ ${\displaystyle X_{i}}$

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

donde es un vector de valores posibles para , y la notación significa que la suma se toma sobre aquellos cuya coordenada ésima es igual a . ${\displaystyle \mathbf {x} '=(x'_{1},\ldots ,x'_{n})}$ ${\displaystyle X_{i}}$ ${\displaystyle \mathbf {x} ':x'_{i}=x_{i}}$ ${\displaystyle \mathbf {x} '}$ ${\displaystyle i}$ ${\displaystyle x_{i}}$

Calcular distribuciones marginales utilizando esta fórmula rápidamente se vuelve prohibitivo a medida que aumenta el número de variables. Por ejemplo, dadas 100 variables binarias , calcular una única distribuciones marginales utilizando y la fórmula anterior implicaría sumar los posibles valores para . Si se sabe que la función de masa de probabilidad factoriza de una manera conveniente, la propagación de creencias permite calcular las distribuciones marginales de manera mucho más eficiente. ${\displaystyle X_{1},\ldots ,X_{100}}$ ${\displaystyle X_{i}}$ ${\displaystyle p}$ ${\displaystyle 2^{99}\approx 6.34\times 10^{29}}$ ${\displaystyle \mathbf {x} '}$ ${\displaystyle p}$

Descripción del algoritmo suma-producto

Existen variantes del algoritmo de propagación de creencias para varios tipos de modelos gráficos ( redes bayesianas y campos aleatorios de Markov ^[5] en particular). Aquí describimos la variante que opera sobre un grafo factorial . Un grafo factorial es un grafo bipartito que contiene nodos correspondientes a variables y factores , con aristas entre las variables y los factores en los que aparecen. Podemos escribir la función de masa conjunta: ${\displaystyle V}$ ${\displaystyle F}$

${\displaystyle p(\mathbf {x} )=\prod _{a\in F}f_{a}(\mathbf {x} _{a})}$

donde es el vector de nodos variables vecinos al nodo factor . Cualquier red bayesiana o campo aleatorio de Markov se puede representar como un gráfico factorial utilizando un factor para cada nodo con sus padres o un factor para cada nodo con su vecindad respectivamente. ^[6] ${\displaystyle \mathbf {x} _{a}}$ ${\displaystyle a}$

El algoritmo funciona pasando funciones de valor real llamadas mensajes a lo largo de los bordes entre los nodos ocultos. Más precisamente, si es un nodo variable y es un nodo factor conectado a en el gráfico factorial, entonces los mensajes de a y los mensajes de a son funciones de valor real , cuyo dominio es el conjunto de valores que puede tomar la variable aleatoria asociada a , denotada . Estos mensajes contienen la "influencia" que una variable ejerce sobre otra. Los mensajes se calculan de manera diferente dependiendo de si el nodo que recibe el mensaje es un nodo variable o un nodo factorial. Manteniendo la misma notación: ${\displaystyle v}$ ${\displaystyle a}$ ${\displaystyle v}$ ${\displaystyle \mu _{v\to a}}$ ${\displaystyle v}$ ${\displaystyle a}$ ${\displaystyle \mu _{a\to v}}$ ${\displaystyle a}$ ${\displaystyle v}$ ${\displaystyle \mu _{v\to a},\mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R} }$ ${\displaystyle v}$ ${\displaystyle \operatorname {Dom} (v)}$

• Un mensaje de un nodo variable a un nodo factorial se define mediante for , donde es el conjunto de nodos factoriales vecinos de . Si está vacío, se establece en la distribución uniforme sobre . ${\displaystyle \mu _{v\to a}:\operatorname {Dom} (v)\to \mathbb {R} }$ ${\displaystyle v}$ ${\displaystyle a}$ $${\displaystyle \mu _{v\to a}(x_{v})=\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\to v}(x_{v})}$$ ${\displaystyle x_{v}\in \operatorname {Dom} (v)}$ ${\displaystyle N(v)}$ ${\displaystyle v}$ ${\displaystyle N(v)\setminus \{a\}}$ ${\displaystyle \mu _{v\to a}(x_{v})}$ ${\displaystyle \operatorname {Dom} (v)}$

• Un mensaje de un nodo de factor a un nodo de variable se define como el producto del factor con mensajes de todos los demás nodos, marginados sobre todas las variables excepto el asociado con , para , donde es el conjunto de nodos vecinos (variables) a . Si está vacío, entonces , ya que en este caso . ${\displaystyle \mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R} }$ ${\displaystyle a}$ ${\displaystyle v}$ ${\displaystyle v}$ $${\displaystyle \mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}\left(f_{a}(\mathbf {x} '_{a})\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}})\right)}$$ ${\displaystyle x_{v}\in \operatorname {Dom} (v)}$ ${\displaystyle N(a)}$ ${\displaystyle a}$ ${\displaystyle N(a)\setminus \{v\}}$ ${\displaystyle \mu _{a\to v}(x_{v})=f_{a}(x_{v})}$ ${\displaystyle x_{v}=x_{a}}$

Como lo demuestra la fórmula anterior: la marginalización completa se reduce a una suma de productos de términos más simples que los que aparecen en la distribución conjunta completa. Esta es la razón por la que la propagación de creencias a veces se denomina transmisión de mensajes de suma-producto o algoritmo de suma-producto .

En una ejecución típica, cada mensaje se actualizará iterativamente a partir del valor anterior de los mensajes vecinos. Se pueden utilizar diferentes programaciones para actualizar los mensajes. En el caso en que el modelo gráfico sea un árbol, una programación óptima converge después de calcular cada mensaje exactamente una vez (consulte la siguiente subsección). Cuando el gráfico de factores tiene ciclos, no existe una programación óptima de este tipo y una opción típica es actualizar todos los mensajes simultáneamente en cada iteración.

Tras la convergencia (si se produjo la convergencia), la distribución marginal estimada de cada nodo es proporcional al producto de todos los mensajes de los factores adyacentes (falta la constante de normalización):

${\displaystyle p_{X_{v}}(x_{v})\propto \prod _{a\in N(v)}\mu _{a\to v}(x_{v}).}$

Asimismo, la distribución marginal conjunta estimada del conjunto de variables pertenecientes a un factor es proporcional al producto del factor por los mensajes de las variables:

${\displaystyle p_{X_{a}}(\mathbf {x} _{a})\propto f_{a}(\mathbf {x} _{a})\prod _{v\in N(a)}\mu _{v\to a}(x_{v}).}$

En el caso en que el gráfico de factores sea acíclico (es decir, un árbol o un bosque), estos valores marginales estimados convergen en realidad a los valores marginales verdaderos en un número finito de iteraciones. Esto se puede demostrar mediante inducción matemática .

Algoritmo exacto para árboles

En el caso en que el gráfico de factores sea un árbol , el algoritmo de propagación de creencias calculará los valores marginales exactos. Además, con una programación adecuada de las actualizaciones de mensajes, finalizará después de dos pasadas completas por el árbol. Esta programación óptima se puede describir de la siguiente manera:

Antes de comenzar, el gráfico se orienta designando un nodo como raíz ; cualquier nodo no raíz que esté conectado a solo otro nodo se denomina hoja .

En el primer paso, los mensajes se transmiten hacia el interior: comenzando por las hojas, cada nodo transmite un mensaje a lo largo del borde (único) hacia el nodo raíz. La estructura de árbol garantiza que sea posible obtener mensajes de todos los demás nodos adyacentes antes de transmitir el mensaje. Esto continúa hasta que la raíz haya obtenido mensajes de todos sus nodos adyacentes.

El segundo paso consiste en pasar los mensajes de vuelta al exterior: comenzando por la raíz, los mensajes se pasan en dirección inversa. El algoritmo se completa cuando todas las hojas han recibido sus mensajes.

Algoritmo aproximado para gráficos generales

Aunque originalmente fue diseñado para modelos gráficos acíclicos , el algoritmo de Propagación de Creencias se puede utilizar en grafos generales . El algoritmo a veces se denomina propagación de creencias en bucle , porque los grafos suelen contener ciclos o bucles. La inicialización y programación de las actualizaciones de mensajes se debe ajustar ligeramente (en comparación con la programación descrita anteriormente para grafos acíclicos) porque los grafos pueden no contener hojas. En cambio, uno inicializa todos los mensajes variables a 1 y usa las mismas definiciones de mensajes anteriores, actualizando todos los mensajes en cada iteración (aunque los mensajes que provienen de hojas conocidas o subgrafos estructurados en árbol pueden ya no necesitar actualización después de suficientes iteraciones). Es fácil demostrar que en un árbol, las definiciones de mensajes de este procedimiento modificado convergerán al conjunto de definiciones de mensajes dado anteriormente dentro de un número de iteraciones igual al diámetro del árbol.

Las condiciones precisas bajo las cuales convergerá la propagación de creencias en bucles aún no se comprenden bien; se sabe que en los gráficos que contienen un solo bucle converge en la mayoría de los casos, pero las probabilidades obtenidas pueden ser incorrectas. ^[7] Existen varias condiciones suficientes (pero no necesarias) para la convergencia de la propagación de creencias en bucles a un único punto fijo. ^[8] Existen gráficos que no convergerán o que oscilarán entre múltiples estados a lo largo de iteraciones repetidas. Técnicas como los gráficos EXIT pueden proporcionar una visualización aproximada del progreso de la propagación de creencias y una prueba aproximada de convergencia.

Existen otros métodos aproximados de marginalización, incluidos los métodos variacionales y los métodos de Monte Carlo .

Un método de marginalización exacta en grafos generales se denomina algoritmo de árbol de unión , que consiste simplemente en la propagación de creencias en un grafo modificado que se garantiza que es un árbol. La premisa básica es eliminar los ciclos agrupándolos en nodos individuales.

Problemas relacionados con algoritmos y complejidad

Un algoritmo similar se conoce comúnmente como algoritmo de Viterbi , pero también se lo conoce como un caso especial del algoritmo de máximo producto o de mínima suma, que resuelve el problema relacionado de maximización o explicación más probable. En lugar de intentar resolver el marginal, el objetivo aquí es encontrar los valores que maximizan la función global (es decir, los valores más probables en un entorno probabilístico), y se puede definir utilizando el argumento max : ${\displaystyle \mathbf {x} }$

${\displaystyle \operatorname {*} {\arg \max }_{\mathbf {x} }g(\mathbf {x} ).}$

Un algoritmo que resuelve este problema es casi idéntico a la propagación de creencias, con las sumas reemplazadas por máximos en las definiciones. ^[9]

Cabe señalar que los problemas de inferencia como la marginalización y la maximización son NP-difíciles de resolver de manera exacta y aproximada (al menos para el error relativo ) en un modelo gráfico. Más precisamente, el problema de marginalización definido anteriormente es #P-completo y el de maximización es NP-completo .

El uso de memoria para la propagación de creencias se puede reducir mediante el uso del algoritmo de la Isla (con un pequeño costo en complejidad de tiempo).

Relación con la energía libre

El algoritmo de suma-producto está relacionado con el cálculo de la energía libre en termodinámica . Sea Z la función de partición . Una distribución de probabilidad

${\displaystyle P(\mathbf {X} )={\frac {1}{Z}}\prod _{f_{j}}f_{j}(x_{j})}$

(según la representación del gráfico de factores) puede verse como una medida de la energía interna presente en un sistema, calculada como

${\displaystyle E(\mathbf {X} )=-\log \prod _{f_{j}}f_{j}(x_{j}).}$

La energía libre del sistema es entonces

${\displaystyle F=U-H=\sum _{\mathbf {X} }P(\mathbf {X} )E(\mathbf {X} )+\sum _{\mathbf {X} }P(\mathbf {X} )\log P(\mathbf {X} ).}$

Se puede demostrar entonces que los puntos de convergencia del algoritmo suma-producto representan los puntos donde se minimiza la energía libre en dicho sistema. De manera similar, se puede demostrar que un punto fijo del algoritmo iterativo de propagación de creencias en gráficos con ciclos es un punto estacionario de una aproximación de energía libre. ^[10]

Propagación generalizada de creencias (GBP)

Los algoritmos de propagación de creencias se presentan normalmente como ecuaciones de actualización de mensajes en un gráfico factorial, que involucran mensajes entre nodos variables y sus nodos factoriales vecinos y viceversa. Considerar mensajes entre regiones en un gráfico es una forma de generalizar el algoritmo de propagación de creencias. ^[10] Existen varias formas de definir el conjunto de regiones en un gráfico que pueden intercambiar mensajes. Un método utiliza ideas introducidas por Kikuchi en la literatura de física, ^{[11] [12] [13]} y se conoce como el método de variación de grupos de Kikuchi. ^[14]

También se pueden lograr mejoras en el rendimiento de los algoritmos de propagación de creencias rompiendo la simetría de las réplicas en las distribuciones de los campos (mensajes). Esta generalización conduce a un nuevo tipo de algoritmo llamado propagación por encuesta (SP), que ha demostrado ser muy eficiente en problemas NP-completos como la satisfacibilidad ^[1] y la coloración de grafos .

El método variacional de conglomerados y los algoritmos de propagación por encuesta son dos mejoras diferentes de la propagación de creencias. El nombre de propagación por encuesta generalizada (GSP) está pendiente de ser asignado al algoritmo que fusiona ambas generalizaciones.

Propagación de creencias gaussianas (GaBP)

La propagación de creencias gaussiana es una variante del algoritmo de propagación de creencias cuando las distribuciones subyacentes son gaussianas . El primer trabajo que analizó este modelo especial fue el trabajo seminal de Weiss y Freeman. ^[15]

El algoritmo GaBP resuelve el siguiente problema de marginalización:

${\displaystyle P(x_{i})={\frac {1}{Z}}\int _{j\neq i}\exp(-{\tfrac {1}{2}}x^{T}Ax+b^{T}x)\,dx_{j}}$

donde Z es una constante de normalización, A es una matriz definida positiva simétrica (matriz de covarianza inversa también conocida como matriz de precisión ) y b es el vector de desplazamiento.

De manera equivalente, se puede demostrar que utilizando el modelo gaussiano, la solución del problema de marginalización es equivalente al problema de asignación de MAP :

${\displaystyle {\underset {x}{\operatorname {argmax} }}\ P(x)={\frac {1}{Z}}\exp(-{\tfrac {1}{2}}x^{T}Ax+b^{T}x).}$

Este problema también es equivalente al siguiente problema de minimización de la forma cuadrática:

${\displaystyle {\underset {x}{\operatorname {min} }}\ 1/2x^{T}Ax-b^{T}x.}$

Lo cual también es equivalente al sistema lineal de ecuaciones.

${\displaystyle Ax=b.}$

La convergencia del algoritmo GaBP es más fácil de analizar (en relación con el caso general de BP) y existen dos condiciones de convergencia suficientes conocidas. La primera fue formulada por Weiss et al. en el año 2000, cuando la matriz de información A es diagonalmente dominante . La segunda condición de convergencia fue formulada por Johnson et al. ^[16] en 2006, cuando el radio espectral de la matriz

${\displaystyle \rho (I-|D^{-1/2}AD^{-1/2}|)<1\,}$

donde D = diag( A ). Más tarde, Su y Wu establecieron las condiciones de convergencia necesarias y suficientes para GaBP sincrónico y GaBP amortiguado, así como otra condición de convergencia suficiente para GaBP asincrónico. Para cada caso, la condición de convergencia implica verificar 1) que un conjunto (determinado por A) no esté vacío, 2) que el radio espectral de una determinada matriz sea menor que uno, y 3) que no se produzca el problema de singularidad (al convertir el mensaje BP en creencia). ^[17]

El algoritmo GaBP se vinculó al dominio del álgebra lineal ^[18] y se demostró que el algoritmo GaBP puede considerarse un algoritmo iterativo para resolver el sistema lineal de ecuaciones Ax = b donde A es la matriz de información y b es el vector de desplazamiento. Empíricamente, se ha demostrado que el algoritmo GaBP converge más rápido que los métodos iterativos clásicos como el método de Jacobi, el método de Gauss-Seidel , la sobre-relajación sucesiva y otros. ^[19] Además, se ha demostrado que el algoritmo GaBP es inmune a los problemas numéricos del método de gradiente conjugado preacondicionado ^[20].

Descodificación de la presión arterial basada en el síndrome

La descripción anterior del algoritmo BP se denomina decodificación basada en palabras de código, que calcula la probabilidad marginal aproximada , dada la palabra de código recibida . Existe una forma equivalente, ^[21] que calcula , donde es el síndrome de la palabra de código recibida y es el error decodificado. El vector de entrada decodificado es . Esta variación solo cambia la interpretación de la función de masa . Explícitamente, los mensajes son ${\displaystyle P(x|X)}$ ${\displaystyle X}$ ${\displaystyle P(e|s)}$ ${\displaystyle s}$ ${\displaystyle X}$ ${\displaystyle e}$ ${\displaystyle x=X+e}$ ${\displaystyle f_{a}(X_{a})}$

${\displaystyle \forall x_{v}\in Dom(v),\;\mu _{v\to a}(x_{v})=P(X_{v})\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\to v}(x_{v}).}$

¿Dónde está la probabilidad de error anterior en la variable? ${\displaystyle P(X_{v})}$ ${\displaystyle v}$ ${\displaystyle \forall x_{v}\in Dom(v),\;\mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}\delta ({\text{syndrome}}({\mathbf {x} }'_{v})={\mathbf {s} })\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}}).}$

Este decodificador basado en síndrome no requiere información sobre los bits recibidos, por lo que puede adaptarse a códigos cuánticos, donde la única información es el síndrome de medición.

En el caso binario, esos mensajes se pueden simplificar para provocar una reducción exponencial de la complejidad ^{[22] [23]} ${\displaystyle x_{i}\in \{0,1\}}$ ${\displaystyle 2^{|\{v\}|+|N(v)|}}$

Defina la razón de verosimilitud logarítmica , , entonces ${\displaystyle l_{v}=\log {\frac {u_{v\to a}(x_{v}=0)}{u_{v\to a}(x_{v}=1)}}}$ ${\displaystyle L_{a}=\log {\frac {u_{a\to v}(x_{v}=0)}{u_{a\to v}(x_{v}=1)}}}$

${\displaystyle v\to a:l_{v}=l_{v}^{(0)}+\sum _{a^{*}\in N(v)\setminus \{a\}}(L_{a^{*}})}$

${\displaystyle a\to v:L_{a}=(-1)^{s_{a}}2\tanh ^{-1}\prod _{v^{*}\in N(a)\setminus \{v\}}\tanh(l_{v^{*}}/2)}$

dónde ${\displaystyle l_{v}^{(0)}=\log(P(x_{v}=0)/P(x_{v}=1))={\text{const}}}$

La razón de verosimilitud logarítmica posterior se puede estimar como ${\displaystyle l_{v}=l_{v}^{(0)}+\sum _{a\in N(v)}(L_{a})}$

Referencias

1. Braunstein, A.; Mézard, M.; Zecchina, R. (2005). "Propagación de encuestas: un algoritmo para la satisfacibilidad". Random Structures & Algorithms . 27 (2): 201–226. arXiv : cs/0212002 . doi :10.1002/rsa.20057. S2CID  6601396.
2. Pearl, Judea (1982). "Reverend Bayes on inference engine: A distributed hierarchical approach" (PDF) . Actas de la Segunda Conferencia Nacional sobre Inteligencia Artificial . AAAI-82: Pittsburgh, PA. Menlo Park, California: AAAI Press. pp. 133–136 . Consultado el 28 de marzo de 2009 .
3. Kim, Jin H.; Pearl, Judea (1983). "Un modelo computacional para el razonamiento causal y diagnóstico combinado en sistemas de inferencia" (PDF) . Actas de la Octava Conferencia Conjunta Internacional sobre Inteligencia Artificial . IJCAI-83: ​​Karlsruhe, Alemania. Vol. 1. págs. 190–193 . Consultado el 20 de marzo de 2016 .
4. Pearl, Judea (1988). Razonamiento probabilístico en sistemas inteligentes: redes de inferencia plausible (2.ª ed.). San Francisco, CA: Morgan Kaufmann. ISBN 978-1-55860-479-7.
5. Yedidia, JS; Freeman, WT; Y. (enero de 2003). "Entender la propagación de creencias y sus generalizaciones". En Lakemeyer, Gerhard; Nebel, Bernhard (eds.). Explorando la inteligencia artificial en el nuevo milenio . Morgan Kaufmann. págs. 239–236. ISBN 978-1-55860-811-5. Recuperado el 30 de marzo de 2009 .
6. Wainwright, MJ; Jordan, MI (2007). "2.1 Distribuciones de probabilidad en gráficos". Modelos gráficos, familias exponenciales e inferencia variacional . Fundamentos y tendencias en aprendizaje automático. Vol. 1. págs. 5–9. doi :10.1561/2200000001.
7. Weiss, Yair (2000). "Corrección de la propagación de probabilidad local en modelos gráficos con bucles". Neural Computation . 12 (1): 1–41. doi :10.1162/089976600300015880. PMID  10636932. S2CID  15402308.
8. Mooij, J; Kappen, H (2007). "Condiciones suficientes para la convergencia del algoritmo suma-producto". IEEE Transactions on Information Theory . 53 (12): 4422–4437. arXiv : cs/0504030 . doi :10.1109/TIT.2007.909166. S2CID  57228.
9. Löliger, Hans-Andrea (2004). "Introducción a los gráficos factoriales". Revista IEEE de procesamiento de señales . 21 (1): 28–41. Código Bibliográfico :2004ISPM...21...28L. doi :10.1109/msp.2004.1267047. S2CID  7722934.
10. Yedidia, JS; Freeman, WT; Weiss, Y.; Y. (julio de 2005). "Construcción de aproximaciones de energía libre y algoritmos generalizados de propagación de creencias". IEEE Transactions on Information Theory . 51 (7): 2282–2312. CiteSeerX 10.1.1.3.5650 . doi :10.1109/TIT.2005.850085. S2CID  52835993 . Consultado el 28 de marzo de 2009 . 
11. Kikuchi, Ryoichi (15 de marzo de 1951). "Una teoría de los fenómenos cooperativos". Physical Review . 81 (6): 988–1003. Bibcode :1951PhRv...81..988K. doi :10.1103/PhysRev.81.988.
12. Kurata, Michio; Kikuchi, Ryoichi; Watari, Tatsuro (1953). "Una teoría de fenómenos cooperativos. III. Discusiones detalladas del método de variación de conglomerados". Revista de física química . 21 (3): 434–448. Código Bibliográfico :1953JChPh..21..434K. doi : 10.1063/1.1698926 .
13. Kikuchi, Ryoichi; Brush, Stephen G. (1967). "Mejora del método de variación de grupos". The Journal of Chemical Physics . 47 (1): 195–203. Código Bibliográfico :1967JChPh..47..195K. doi :10.1063/1.1711845.
14. Pelizzola, Alessandro (2005). "Método de variación de conglomerados en física estadística y modelos gráficos probabilísticos". Journal of Physics A: Mathematical and General . 38 (33): R309–R339. arXiv : cond-mat/0508216 . Bibcode :2005JPhA...38R.309P. doi :10.1088/0305-4470/38/33/R01. ISSN  0305-4470. S2CID  942.
15. Weiss, Yair; Freeman, William T. (octubre de 2001). "Corrección de la propagación de creencias en modelos gráficos gaussianos de topología arbitraria". Neural Computation . 13 (10): 2173–2200. CiteSeerX 10.1.1.44.794 . doi :10.1162/089976601750541769. PMID  11570995. S2CID  10624764. 
16. Malioutov, Dmitry M.; Johnson, Jason K.; Willsky, Alan S. (octubre de 2006). "Walk-sums and belief propagation in Gaussian graphical models" (Sumas de recorrido y propagación de creencias en modelos gráficos gaussianos). Journal of Machine Learning Research (Revista de investigación sobre aprendizaje automático ). 7 : 2031–2064 . Consultado el 28 de marzo de 2009 .
17. Su, Qinliang; Wu, Yik-Chung (marzo de 2015). "Sobre las condiciones de convergencia de la propagación de creencias gaussianas". IEEE Trans. Signal Process. 63 (5): 1144–1155. Bibcode :2015ITSP...63.1144S. doi :10.1109/TSP.2015.2389755. S2CID  12055229.
18. Solucionador de propagación de creencias gaussianas para sistemas de ecuaciones lineales. Por O. Shental, D. Bickson, PH Siegel, JK Wolf y D. Dolev, IEEE Int. Symp. on Inform. Theory (ISIT), Toronto, Canadá, julio de 2008. http://www.cs.huji.ac.il/labs/danss/p2p/gabp/ Archivado el 14 de junio de 2011 en Wayback Machine.
19. Detección lineal mediante propagación de creencias. Danny Bickson, Danny Dolev, Ori Shental, Paul H. Siegel y Jack K. Wolf. En la 45.ª Conferencia anual Allerton sobre comunicación, control y computación, Allerton House, Illinois, 7 de septiembre. http://www.cs.huji.ac.il/labs/danss/p2p/gabp/ Archivado el 14 de junio de 2011 en Wayback Machine.
20. Maximización de la utilidad de redes distribuidas a gran escala. D. Bickson, Y. Tock, A. Zymnis, S. Boyd y D. Dolev. En el Simposio internacional sobre teoría de la información (ISIT), julio de 2009. http://www.cs.huji.ac.il/labs/danss/p2p/gabp/ Archivado el 14 de junio de 2011 en Wayback Machine.
21. Dave, Maulik A. (1 de diciembre de 2006). "Revisión de "Information Theory, Inference, and Learning Algorithms de David JC MacKay", Cambridge University Press, 2003". Noticias de ACM SIGACT . 37 (4): 34–36. doi :10.1145/1189056.1189063. ISSN  0163-5700. S2CID  10570465.
22. Filler, Tomas (17 de noviembre de 2009). "Simplificación del algoritmo de propagación de creencias" (PDF) .
23. Liu, Ye-Hua; Poulin, David (22 de mayo de 2019). "Decodificadores de propagación de creencias neuronales para códigos de corrección de errores cuánticos". Physical Review Letters . 122 (20): 200501. arXiv : 1811.07835 . doi :10.1103/physrevlett.122.200501. ISSN  0031-9007. PMID  31172756. S2CID  53959182.

Lectura adicional

• Bickson, Danny. (2009). Página de recursos sobre propagación de creencias gaussianas: página web que contiene publicaciones recientes, así como el código fuente de Matlab.
• Bishop, Christopher M. (2006). "Capítulo 8: modelos gráficos" (PDF) . Reconocimiento de patrones y aprendizaje automático . Springer. pp. 359–418. ISBN 978-0-387-31073-2. Recuperado el 2 de diciembre de 2023 .
• Coughlan, James. (2009). Una introducción tutorial a la propagación de creencias.
• Löliger, Hans-Andrea (2004). "Introducción a los grafos factoriales". Revista IEEE de procesamiento de señales . 21 (1): 28–41. Bibcode :2004ISPM...21...28L. doi :10.1109/MSP.2004.1267047. S2CID  7722934.
• Mackenzie, Dana (2005). "La velocidad de las comunicaciones se acerca a la velocidad terminal", New Scientist . 9 de julio de 2005. Número 2507 (Se requiere registro)
• Wymeersch, Henk (2007). Diseño iterativo de receptores. Cambridge University Press. ISBN 978-0-521-87315-4.
• Yedidia, JS; Freeman, WT; Weiss, Y. (enero de 2003). "Entender la propagación de creencias y sus generalizaciones". En Lakemeyer, Gerhard; Nebel, Bernhard (eds.). Explorando la inteligencia artificial en el nuevo milenio . Morgan Kaufmann. págs. 239–269. ISBN 978-1-55860-811-5. Recuperado el 30 de marzo de 2009 .
• Yedidia, JS; Freeman, WT; Weiss, Y. (julio de 2005). "Construcción de aproximaciones de energía libre y algoritmos generalizados de propagación de creencias". IEEE Transactions on Information Theory . 51 (7): 2282–2312. CiteSeerX  10.1.1.3.5650 . doi :10.1109/TIT.2005.850085. S2CID  52835993.