Propagación de creencias

La propagación de creencias , también conocida como paso de mensajes suma-producto , 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, condicionada 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 éxito empírico en numerosas aplicaciones, incluyendo 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 , extendido posteriormente a poliárboles . ^{[ 3 ]} Si bien el algoritmo no es exacto en grafos generales, se ha demostrado que es un algoritmo aproximado útil. ^{[ 4 ]}

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

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

dónde${\displaystyle \mathbf {x} '=(x'_{1},\ldots ,x'_{n})}$es un vector de posibles valores para el${\displaystyle X_{i}}$y la notación${\displaystyle \mathbf {x} ':x'_{i}=x_{i}}$significa que la suma se toma sobre esos${\displaystyle \mathbf {x} '}$cuyo${\displaystyle i}$La coordenada es igual a${\displaystyle x_{i}}$.

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

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 que corresponden a variables.${\displaystyle V}$y factores${\displaystyle F}$, con aristas entre las variables y los factores en los que aparecen. Podemos escribir la función de masa conjunta:

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

dónde${\displaystyle \mathbf {x} _{a}}$es el vector de nodos variables vecinos al nodo factor.${\displaystyle a}$Cualquier red bayesiana o campo aleatorio de Markov puede representarse como un grafo factorial utilizando un factor para cada nodo con sus padres o un factor para cada nodo con su vecindario, respectivamente. ^{[ 6 ]}

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

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

• Un mensaje${\displaystyle \mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R} }$desde un nodo factor${\displaystyle a}$a un nodo variable${\displaystyle v}$se define como el producto del factor con mensajes de todos los demás nodos, marginalizado sobre todas las variables excepto la asociada con${\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)}$$para${\displaystyle x_{v}\in \operatorname {Dom} (v)}$, dónde${\displaystyle N(a)}$es el conjunto de nodos vecinos (variables) a${\displaystyle a}$. Si${\displaystyle N(a)\setminus \{v\}}$está vacío, entonces${\displaystyle \mu _{a\to v}(x_{v})=f_{a}(x_{v})}$, ya que en este caso${\displaystyle x_{v}=x_{a}}$.

Como muestra 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. Por esta razón, la propagación de creencias a veces se denomina paso de mensajes suma-producto o algoritmo suma-producto .

En una ejecución típica, cada mensaje se actualiza iterativamente a partir del valor anterior de los mensajes vecinos. Se pueden utilizar diferentes esquemas de actualización. En el caso de que el modelo gráfico sea un árbol, se alcanza un esquema óptimo tras calcular cada mensaje exactamente una vez (véase la siguiente subsección). Cuando el grafo de factores presenta ciclos, no existe un esquema óptimo, y lo habitual es actualizar todos los mensajes simultáneamente en cada iteración.

Al alcanzarse la convergencia (si esta se produjo), la distribución marginal estimada de cada nodo es proporcional al producto de todos los mensajes de los factores adyacentes (sin 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 y 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 de que el grafo de factores sea acíclico (es decir, un árbol o un bosque), estas marginales estimadas convergen a las marginales verdaderas en un número finito de iteraciones. Esto se puede demostrar por inducción matemática .

En el caso de que el grafo de factores sea un árbol , el algoritmo de propagación de creencias calculará las distribuciones marginales exactas. 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 que no sea la raíz y que esté conectado a un solo nodo se denomina hoja .

En la primera etapa, los mensajes se transmiten hacia el interior: comenzando por las hojas, cada nodo envía un mensaje a lo largo de la arista (única) hacia el nodo raíz. La estructura de árbol garantiza que es posible obtener mensajes de todos los demás nodos adyacentes antes de transmitir el mensaje. Este proceso continúa hasta que la raíz haya obtenido mensajes de todos sus nodos adyacentes.

El segundo paso consiste en enviar los mensajes de vuelta: comenzando desde la raíz, los mensajes se envían en sentido inverso. El algoritmo finaliza cuando todas las hojas han recibido sus mensajes.

Aunque fue diseñado originalmente para modelos gráficos acíclicos , el algoritmo de propagación de creencias puede utilizarse en grafos generales . En estos casos, se le denomina a veces propagación de creencias en bucle , ya que los grafos suelen contener ciclos o bucles. La inicialización y la programación de las actualizaciones de mensajes deben ajustarse ligeramente (en comparación con la programación descrita anteriormente para grafos acíclicos), dado que los grafos podrían no contener hojas. En su lugar, se inicializan todos los mensajes variables a 1 y se utilizan las mismas definiciones de mensajes anteriores, actualizando todos los mensajes en cada iteración (aunque los mensajes provenientes de hojas conocidas o subgrafos con estructura de árbol podrían no necesitar actualización tras un número suficiente de 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 anterior en un número de iteraciones igual al diámetro del árbol.

Las condiciones precisas bajo las cuales converge la propagación de creencias en bucle aún no se comprenden bien; se sabe que en grafos que contienen un solo bucle converge en la mayoría de los casos, pero las probabilidades obtenidas podrían ser incorrectas. ^{[ 7 ]} Existen varias condiciones suficientes (pero no necesarias) para la convergencia de la propagación de creencias en bucle a un único punto fijo. ^{[ 8 ]} Existen grafos que no convergen o que oscilan entre múltiples estados en iteraciones repetidas. Técnicas como los diagramas 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 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 del árbol de unión , que consiste simplemente en la propagación de creencias sobre un grafo modificado que garantiza ser un árbol. La premisa básica es eliminar los ciclos agrupándolos en nodos individuales.

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

${\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 destacar que los problemas de inferencia como la marginalización y la maximización son NP-difíciles de resolver de forma 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 de la propagación de creencias se puede reducir mediante el uso del algoritmo de la Isla (a un pequeño costo en la complejidad temporal ).

El algoritmo 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 gráfica de factores) puede considerarse 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 grafos con ciclos es un punto estacionario de una aproximación de energía libre. ^{[ 10 ]}

Los algoritmos de propagación de creencias se presentan normalmente como ecuaciones de actualización de mensajes en un grafo factorial, que involucran mensajes entre nodos variables y sus nodos factoriales vecinos y viceversa. Considerar los mensajes entre regiones en un grafo es una forma de generalizar el algoritmo de propagación de creencias. ^{[ 10 ]} Existen varias formas de definir el conjunto de regiones en un grafo 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 clústeres 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 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 la satisfacibilidad ^{[ 1 ]} y la coloración de grafos .

El método variacional de clústeres y los algoritmos de propagación de encuestas son dos mejoras distintas a la propagación de creencias. El nombre de propagación generalizada de encuestas (GSP, por sus siglas en inglés) está pendiente de asignación para el algoritmo que combine ambas generalizaciones.

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 fundamental 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 simétrica definida positiva (matriz de covarianza inversa, también conocida como matriz de precisión ) y b es el vector de desplazamiento.

De forma equivalente, se puede demostrar que, utilizando el modelo gaussiano, la solución del problema de marginalización es equivalente al problema de asignación 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 ). Posteriormente, Su y Wu establecieron las condiciones de convergencia necesarias y suficientes para GaBP síncrono y GaBP amortiguado, así como otra condición de convergencia suficiente para GaBP asíncrono. Para cada caso, la condición de convergencia implica verificar que 1) un conjunto (determinado por A) no sea vacío, 2) el radio espectral de cierta matriz sea menor que uno, y 3) 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 puede considerarse un algoritmo iterativo para resolver el sistema de ecuaciones lineales 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 sobrerrelajación sucesiva y otros ^{[ 19 ]} . Además, se ha demostrado que el algoritmo GaBP es inmune a los problemas numéricos del método del gradiente conjugado precondicionado ^{[ 20 ]} .

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

${\displaystyle \forall x_{v}\in \operatorname {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${\displaystyle P(X_{v})}$es la probabilidad de error previa en la variable${\displaystyle v}$,

${\displaystyle \forall x_{v}\in \operatorname {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índromes 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,${\displaystyle x_{i}\in \{0,1\}}$, esos mensajes pueden simplificarse para provocar una reducción exponencial de${\displaystyle 2^{|\{v\}|+|N(v)|}}$en la complejidad. ^{[ 22 ] [ 23 ]}

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

${\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 {\tfrac {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})}$

• Bickson, Danny. (2009). Página de recursos sobre propagación de creencias gaussianas : página web que contiene publicaciones recientes, así como 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. Consultado el 2 de diciembre de 2023 .
• Coughlan, James. (2009). Una introducción tutorial a la propagación de creencias .
• Löliger, Hans-Andrea (2004). "Una introducción a los grafos factoriales". IEEE Signal Processing Magazine . 21 (1): 28– 41. Bibcode : 2004ISPM...21...28L . doi : 10.1109/MSP.2004.1267047 . S2CID 7722934 . 
• Mackenzie, Dana (2005). " La velocidad de comunicación 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). «Comprender la propagación de creencias y sus generalizaciones» . En Lakemeyer, Gerhard; Nebel, Bernhard (eds.). Explorando la inteligencia artificial en el nuevo milenio . Morgan Kaufmann. pp. 239–269 . ISBN  978-1-55860-811-5Consultado 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 .