La propagación de creencias , también conocida como paso de mensajes de producto de suma , es un algoritmo de paso 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 usa comúnmente en inteligencia artificial y teoría de la información y ha demostrado é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 exacta en árboles , que luego se extendió a polytrees . [3] Si bien no es exacto en los gráficos generales, se ha demostrado que es un algoritmo aproximado útil. [4]
Si X = { X i } es un conjunto de variables aleatorias discretas con una función de masa conjunta p , la distribución marginal de un solo X i es simplemente la suma de p sobre todas las demás variables:
Sin embargo, esto rápidamente se vuelve prohibitivo desde el punto de vista computacional: si hay 100 variables binarias, entonces es necesario sumar más de 2 99 ≈ 6,338 × 10 29 valores posibles. Al explotar la estructura del polytree, la propagación de creencias permite que los marginales se calculen de manera mucho más eficiente.
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). Describimos aquí la variante que opera sobre un gráfico de factores . Un gráfico de factores es un gráfico bipartito que contiene los nodos correspondientes a las variables V y los factores F , con aristas entre las variables y los factores en los que aparecen. Podemos escribir la función de masa conjunta:
donde x a es el vector de los nodos variables vecinos al nodo factor a . Cualquier red bayesiana o campo aleatorio de Markov se puede representar como un gráfico de factores utilizando un factor para cada nodo con sus padres o un factor para cada nodo con su vecindad, respectivamente. [6]
El algoritmo funciona pasando funciones de valor real llamadas mensajes junto con los bordes entre los nodos ocultos. Más precisamente, si v es un nodo variable y a es un nodo factor conectado av en el gráfico de factores, los mensajes de v a a , (denotados por) y de la a a la v (), son funciones de valor real cuyo dominio es Dom ( v ), el conjunto de valores que puede tomar la variable aleatoria asociada con v . 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 factor. Manteniendo la misma notación:
- Un mensaje de un nodo variable v a un nodo de factor a es el producto de los mensajes de todos los demás nodos de factor vecinos (excepto el receptor; alternativamente, se puede decir que el receptor envía como mensaje la función constante igual a "1"):
- donde N ( v ) es el conjunto de nodos vecinos (factor) a v . Si está vacío, entonces se establece en la distribución uniforme.
- Un mensaje de un nodo de factor a a un nodo variable v es el producto del factor con mensajes de todos los demás nodos, marginados sobre todas las variables excepto la asociada con v :
- donde N ( a ) es el conjunto de nodos vecinos (variables) a a . Si está vacío entonces , ya que en este caso .
Como muestra la fórmula anterior: la marginació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. Ésta es la razón por la que se denomina algoritmo de suma de productos.
En una ejecución típica, cada mensaje se actualizará de forma iterativa a partir del valor anterior de los mensajes vecinos. Se puede utilizar una programación diferente para actualizar los mensajes. En el caso de que el modelo gráfico sea un árbol, una programación óptima permite alcanzar la convergencia luego de computar cada mensaje una sola vez (ver siguiente subsección). Cuando el gráfico de factores tiene ciclos, no existe una programación óptima y una opción típica es actualizar todos los mensajes simultáneamente en cada iteración.
Tras la convergencia (si ocurrió 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):
Asimismo, la distribución marginal conjunta estimada del conjunto de variables pertenecientes a un factor es proporcional al producto del factor y los mensajes de las variables:
En el caso de que el gráfico de factores sea acíclico (es decir, un árbol o un bosque), estos marginales estimados en realidad convergen a los verdaderos marginales en un número finito de iteraciones. Esto se puede demostrar por inducción matemática .
Algoritmo exacto para árboles
En el caso de que el gráfico de factores sea un árbol , el algoritmo de propagación de creencias calculará los márgenes exactos. Además, con la programación adecuada de las actualizaciones del mensaje, finalizará después de 2 pasos. 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 solo a otro nodo se denomina hoja .
En el primer paso, los mensajes se pasan hacia adentro: comenzando en las hojas, cada nodo pasa un mensaje a lo largo del borde (único) hacia el nodo raíz. La estructura de árbol garantiza que es posible obtener mensajes de todos los demás nodos adyacentes antes de pasar el mensaje. Esto continúa hasta que la raíz haya obtenido mensajes de todos sus nodos contiguos.
El segundo paso implica devolver los mensajes: comenzando en la raíz, los mensajes se pasan en la dirección inversa. El algoritmo se completa cuando todas las hojas han recibido sus mensajes.
Algoritmo aproximado para gráficos generales
Curiosamente, aunque originalmente fue diseñado para modelos gráficos acíclicos, se encontró que el algoritmo de propagación de creencias se puede utilizar en gráficos generales . El algoritmo a veces se denomina propagación de creencias disparatadas , porque los gráficos suelen contener ciclos o ciclos. La inicialización y programación de las actualizaciones de mensajes deben ajustarse ligeramente (en comparación con la programación descrita anteriormente para gráficos acíclicos) porque es posible que los gráficos no contengan hojas. En cambio, uno inicializa todos los mensajes variables a 1 y usa las mismas definiciones de mensaje anteriores, actualizando todos los mensajes en cada iteración (aunque los mensajes que provienen de hojas conocidas o subgrafos estructurados en árbol pueden no necesitar actualizarse después de suficientes iteraciones). Es fácil mostrar que en un árbol, las definiciones de mensaje de este procedimiento modificado convergerán al conjunto de definiciones de mensaje dadas 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 descabelladas todavía 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 disparatadas a un único punto fijo. [8] Existen gráficos que no convergerán o que oscilarán entre múltiples estados en 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 para la marginación, incluidos los métodos variacionales y los métodos de Monte Carlo .
Un método de marginación exacta en los gráficos generales se llama algoritmo del árbol de unión , que es simplemente la propagación de creencias en un gráfico modificado que se garantiza que es un árbol. La premisa básica es eliminar los ciclos agrupándolos en nodos únicos.
Problemas relacionados con el algoritmo y la complejidad
Un algoritmo similar se conoce comúnmente como el algoritmo de Viterbi , pero también se conoce como un caso especial del algoritmo max-product o min-sum, 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 valoresque maximiza la función global (es decir, los valores más probables en un entorno probabilístico), y se puede definir usando el arg max :
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]
Vale la pena señalar que los problemas de inferencia como la marginació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 marginación definido anteriormente es # P-completo y la maximización es NP-completo .
El uso de memoria de la propagación de creencias se puede reducir mediante el uso del algoritmo Island (a un pequeño costo en la complejidad del tiempo).
Relación con la energía libre
El algoritmo de suma-producto está relacionado con el cálculo de energía libre en termodinámica . Sea Z la función de partición . Una distribución de probabilidad
(según la representación del gráfico de factores) se puede ver como una medida de la energía interna presente en un sistema, calculada como
La energía libre del sistema es entonces
Entonces se puede demostrar que los puntos de convergencia del algoritmo de suma-producto representan los puntos donde se minimiza la energía libre en tal sistema. De manera similar, se puede demostrar que un punto fijo del algoritmo de propagación de creencias iterativas en gráficos con ciclos es un punto estacionario de una aproximación de energía libre. [10]
Propagación de creencias generalizadas (GBP)
Los algoritmos de propagación de creencias se presentan normalmente como ecuaciones de actualización de mensajes en un gráfico de factores, que involucran mensajes entre los nodos variables y sus nodos de factores vecinos y viceversa. Considerar los mensajes entre regiones en un gráfico es una forma de generalizar el algoritmo de propagación de creencias. [10] Hay varias formas de definir el conjunto de regiones en un gráfico que puede intercambiar mensajes. Un método utiliza ideas introducidas por Kikuchi en la literatura de física, [11] [12] [13] y se conoce como 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 de encuestas (SP), que ha demostrado ser muy eficiente en problemas NP-completos como satisfacibilidad [1] y coloración de gráficos .
El método de variación de conglomerados y los algoritmos de propagación de encuestas son dos mejoras diferentes para la propagación de creencias. El nombre de propagación de encuestas generalizadas (GSP) está a la espera de ser asignado al algoritmo que fusiona ambas generalizaciones.
Propagación de creencias gaussianas (GaBP)
La propagación de creencias gaussianas es una variante del algoritmo de propagación de creencias cuando las distribuciones subyacentes son gaussianas . El primer trabajo que analiza este modelo especial fue el trabajo fundamental de Weiss y Freeman. [15]
El algoritmo GaBP resuelve el siguiente problema de marginación:
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 marginación es equivalente al problema de asignación de MAP :
Este problema también es equivalente al siguiente problema de minimización de la forma cuadrática:
Que también es equivalente al sistema lineal de ecuaciones.
La convergencia del algoritmo GaBP es más fácil de analizar (en relación con el caso general de BP) y hay dos condiciones de convergencia suficientes conocidas. El primero fue formulado 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
donde D = diag ( A ). Posteriormente, 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) el radio espectral de una determinada matriz sea menor que uno, y 3) el problema de la singularidad (al convertir el mensaje de BP en creencia ) no se produce. [17]
El algoritmo GaBP se vinculó al dominio del álgebra lineal, [18] y se demostró que el algoritmo GaBP puede verse como un algoritmo iterativo para resolver el sistema lineal de ecuaciones Ax = b donde A es la matriz de información yb es el cambio vector. Empíricamente, se muestra que el algoritmo GaBP converge más rápido que los métodos iterativos clásicos como el método Jacobi, el método 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]
Decodificación de PA 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 . Hay una forma equivalente, [21] que calcula, dónde es el síndrome de la palabra en clave 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
- dónde es la probabilidad de error anterior en la variable
Este decodificador basado en síndrome no requiere información sobre los bits recibidos, por lo que se puede adaptar 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 causar una reducción exponencial de en la complejidad [22] [23]
Definir razón logarítmica de verosimilitud , , luego
- dónde
La razón logarítmica de verosimilitud posterior puede estimarse como
Referencias
- ↑ a b Braunstein, A .; Mézard, M .; Zecchina, R. (2005). "Propagación de encuestas: un algoritmo de satisfacibilidad". Estructuras y algoritmos aleatorios . 27 (2): 201–226. arXiv : cs / 0212002 . doi : 10.1002 / rsa.20057 .
- ^ Pearl, Judea (1982). "Reverendo Bayes en motores de inferencia: un enfoque jerárquico distribuido" (PDF) . Actas de la Segunda Conferencia Nacional de Inteligencia Artificial . AAAI-82: Pittsburgh, PA . Menlo Park, California: AAAI Press. págs. 133-136 . Consultado el 28 de marzo de 2009 .
- ^ 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 . 1 . págs. 190-193 . Consultado el 20 de marzo de 2016 .
- ^ 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.
- ^ Yedidia, JS; Freeman, WT; Y. (enero de 2003). "Comprensión de 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. Consultado el 30 de marzo de 2009 .
- ^ 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 Machine Learning . 1 . págs. 5-9. doi : 10.1561 / 2200000001 .
- ^ Weiss, Yair (2000). "Corrección de la propagación de probabilidad local en modelos gráficos con bucles". Computación neuronal . 12 (1): 1–41. doi : 10.1162 / 089976600300015880 . PMID 10636932 .
- ^ Mooij, J; Kappen, H (2007). "Condiciones suficientes para la convergencia del algoritmo suma-producto". Transacciones IEEE sobre teoría de la información . 53 (12): 4422–4437. arXiv : cs / 0504030 . doi : 10.1109 / TIT.2007.909166 .
- ^ Löliger, Hans-Andrea (2004). "Introducción a los gráficos de factores". Revista de procesamiento de señales IEEE . 21 (1): 28–41. Código Bibliográfico : 2004ISPM ... 21 ... 28L . doi : 10.1109 / msp.2004.1267047 .
- ^ a b Yedidia, JS; Freeman, WT; Weiss, Y .; Y. (julio de 2005). "Construcción de aproximaciones de energía libre y algoritmos de propagación de creencias generalizadas" . Transacciones IEEE sobre teoría de la información . 51 (7): 2282–2312. CiteSeerX 10.1.1.3.5650 . doi : 10.1109 / TIT.2005.850085 . Consultado el 28 de marzo de 2009 .
- ^ Kikuchi, Ryoichi (15 de marzo de 1951). "Una teoría de los fenómenos cooperativos". Revisión física . 81 (6): 988–1003. Código Bibliográfico : 1951PhRv ... 81..988K . doi : 10.1103 / PhysRev.81.988 .
- ^ Kurata, Michio; Kikuchi, Ryoichi; Watari, Tatsuro (1953). "Una teoría de los fenómenos cooperativos. III. Discusiones detalladas del método de variación de clúster". La Revista de Física Química . 21 (3): 434–448. Código bibliográfico : 1953JChPh..21..434K . doi : 10.1063 / 1.1698926 .
- ^ Kikuchi, Ryoichi; Pincel, Stephen G. (1967). "Mejora del método de variación de clústeres". La Revista de Física Química . 47 (1): 195-203. Código bibliográfico : 1967JChPh..47..195K . doi : 10.1063 / 1.1711845 .
- ^ Pelizzola, Alessandro (2005). "Método de variación de clústeres en física estadística y modelos gráficos probabilísticos". Revista de Física A: Matemática y General . 38 (33): R309 – R339. arXiv : cond-mat / 0508216 . Código Bibliográfico : 2005JPhA ... 38R.309P . doi : 10.1088 / 0305-4470 / 38/33 / R01 . ISSN 0305-4470 .[ enlace muerto permanente ]
- ^ 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". Computación neuronal . 13 (10): 2173-2200. CiteSeerX 10.1.1.44.794 . doi : 10.1162 / 089976601750541769 . PMID 11570995 .
- ^ Malioutov, Dmitry M .; Johnson, Jason K .; Willsky, Alan S. (octubre de 2006). "Walk-sums y propagación de creencias en modelos gráficos gaussianos" . Revista de investigación sobre aprendizaje automático . 7 : 2031–2064 . Consultado el 28 de marzo de 2009 .
- ^ Su, Qinliang; Wu, Yik-Chung (marzo de 2015). "Sobre las condiciones de convergencia de la propagación de la creencia gaussiana". IEEE Trans. Proceso de señal. 63 (5): 1144-1155. Código bibliográfico : 2015ITSP ... 63.1144S . doi : 10.1109 / TSP.2015.2389755 .
- ^ 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. en Informar. 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.
- ^ Detección lineal a través de la propagación de creencias. Danny Bickson, Danny Dolev, Ori Shental, Paul H. Siegel y Jack K. Wolf. En la 45ª Conferencia Anual de 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 la Wayback Machine
- ^ Maximización de la utilidad de red distribuida 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.
- ^ Dave, Maulik A. (1 de diciembre de 2006). "Revisión de" teoría de la información, inferencia y algoritmos de aprendizaje por David JC MacKay ", Cambridge University Press, 2003". Noticias ACM SIGACT . 37 (4): 34. doi : 10.1145 / 1189056.1189063 . ISSN 0163-5700 .
- ^ Filler, Tomas (17 de noviembre de 2009). "Simplificación del algoritmo de propagación de creencias" (PDF) .
- ^ 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". Cartas de revisión física . 122 (20). arXiv : 1811.07835 . doi : 10.1103 / physrevlett.122.200501 . ISSN 0031-9007 . PMID 31172756 .
Otras lecturas
- Bickson, Danny. (2009). Página de recursos de propagación de creencias gaussianas: página web que contiene publicaciones recientes, así como el código fuente de Matlab.
- Obispo, Christopher M. (2006). "Capítulo 8: Modelos gráficos" (PDF) . Reconocimiento de patrones y aprendizaje automático . Saltador. págs. 359–418. ISBN 978-0-387-31073-2. Consultado el 20 de marzo de 2014 .
- Coughlan, James. (2009). Una introducción tutorial a la propagación de creencias .
- Löliger, Hans-Andrea (2004). "Introducción a los gráficos de factores". Revista de procesamiento de señales IEEE . 21 (1): 28–41. Código Bibliográfico : 2004ISPM ... 21 ... 28L . doi : 10.1109 / MSP.2004.1267047 .
- Mackenzie, Dana (2005). " La velocidad de comunicación se acerca a la velocidad terminal ", New Scientist . 9 de julio de 2005. Edición 2507 (es necesario registrarse)
- Wymeersch, Henk (2007). Diseño de receptor iterativo . Prensa de la Universidad de Cambridge. ISBN 978-0-521-87315-4.
- Yedidia, JS; Freeman, WT; Weiss, Y. (enero de 2003). "Comprensión de 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. Consultado 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 de propagación de creencias generalizadas" . Transacciones IEEE sobre teoría de la información . 51 (7): 2282–2312. CiteSeerX 10.1.1.3.5650 . doi : 10.1109 / TIT.2005.850085 .