¿Cómo se explica el algoritmo de propagación de creencias en las redes bayesianas? La tecnología cambia la vida futura

Tomaré un ejemplo bastante simple para mostrar cómo funciona la propagación de creencias. Supongo que ya sabe cómo encontrar el producto factorial y cómo marginar (sumar) una variable del factor.
Es más fácil entender BP en gráficos de factores (podemos convertir cualquier red de Markov en un gráfico de factores).
Un gráfico de factores es un gráfico bipartito no dirigido donde tenemos nodos variables en un lado, y nodos de factores en el otro lado, y hay un borde entre el nodo variable [matemáticas] A [/ matemáticas] y el nodo de factores [matemáticas] F [/ matemáticas ] si la variable [matemática] A [/ matemática] aparece en el factor [matemática] F [/ matemática]. A continuación, llamaré a los nodos variables como simples nodos y factorizaré los nodos como características.
Consideremos un gráfico de factor simple como se muestra a continuación:
Supongamos que queremos calcular las probabilidades marginales de [matemática] A [/ matemática], [matemática] B [/ matemática] y [matemática] C [/ matemática] sin usar BP, luego primero tenemos que calcular la distribución conjunta y luego sumar variables
La distribución conjunta se puede encontrar multiplicando dos características [matemática] F1 [/ matemática] y [matemática] F2 [/ matemática]. Obtenemos la distribución conjunta como:
Aquí, como podemos ver, P (A = 0) = 14/42 = 1/3 , P (B = 0) = 12/42 = 2/7 , P (C = 0) = 12/42 = 2/7 .
Calculemos estos marginales usando BP en un gráfico de factor dado. En BP,
cada nodo envía un mensaje a su función vecina y cada función envía un mensaje a su nodo vecino. Básicamente, un mensaje es la creencia acerca de la probabilidad de algún nodo de estar en estado 0 o 1 (por eso lo llamamos propagación de creencias), y es solo una tabla de 2 entradas que especifica la probabilidad no normalizada de un nodo. De ahora en adelante, especificaré el mensaje o cualquier tabla potencial como un vector de fila, de modo que la última variable en factor cambie más rápido. Por ejemplo, [math] \ phi (A, B) [/ math] puede escribirse como [1 2 2 4] . Tenga en cuenta que en cualquier momento, podemos dividir la tabla completa por constante para simplificar los cálculos.

Un nodo [math] n [/ math] envía un mensaje a una función [math] f [/ math] multiplicando todos los mensajes que [math] n [/ math] obtiene de sus funciones vecinas excepto [math] f [/ math] . Intuitivamente, el nodo [matemática] n [/ matemática] le dice a la característica [matemática] f [/ matemática] lo que otras características piensan acerca de la probabilidad del nodo [matemática] n [/ matemática] de ser 0 o 1.

Tenga en cuenta que en nuestro ejemplo, el nodo A está conectado solo a la función F1, lo que significa que no tiene nada que decir a F1 sobre lo que otros piensan al respecto. Por lo tanto, siempre envía un mensaje de [1 1], es decir, ambos estados son igualmente probables. Similar es el caso con C a F2.

Un factor [math] f [/ math] envía un mensaje a un nodo [math] n [/ math] multiplicando todos los mensajes que [math] f [/ math] recibe de sus nodos vecinos excepto [math] n [/ math] , y luego multiplicando el producto resultante con su propia tabla de potencial, y finalmente sumando todas las variables excepto [math] n [/ math].

Dejaremos de transmitir este mensaje cuando los mensajes no cambien en las iteraciones.
Ahora comencemos el algoritmo de BP en un gráfico de factor dado:

Todos los nodos comienzan el proceso. Como no han recibido ningún mensaje de los factores, envían el mensaje [1 1] a todos los factores.
Ahora calculamos el mensaje de F1 a A. Para esto, multiplicamos todos los mensajes a F1 excepto a partir de A. Dado que solo hay otro mensaje (de B), no necesitamos multiplicar nada. Ahora multiplicamos este mensaje de B con la tabla potencial de F1 para obtener [1 2 2 4] , y finalmente después de sumar B, recibimos el mensaje de F1 a A como [3 6] = [1 2] .
Del mismo modo, el mensaje de F1 a B es [1 2] , F2 a B es [4 5] y F2 a C es
[1 2] .
Ahora, nuevamente, los nodos envían mensajes a los factores. Como ya dije que el mensaje de A a F1 y de C a F2 siempre será [1 1] , necesitamos calcular el mensaje de B a F1 y de B a F2.
El mensaje de B a F1 es la multiplicación de todos los mensajes a B, excepto de F1 a B. Como solo tenemos un mensaje restante para B, es decir, de F2 a B, no necesitamos multiplicar nada y simplemente enviar [4 5] desde B a F1. De manera similar, B envía [1 2] a F2.
Ahora nuevamente los factores envían mensajes a los nodos. Para calcular el mensaje de F1 a A, primero multiplicamos la tabla de potencial de F1 con el mensaje de B a F1, y obtenemos [4 10 8 20] , y después de sumar B, obtenemos [14 28] = [1 2] .
Del mismo modo, el mensaje de F1 a B es [1 2] , F2 a B es [4 5] y F2 a C es
[4 10] = [2 5]
Ahora nuevamente los nodos envían mensajes a los factores. El mensaje de B a F1 es [4 5] y de B a F2 es [1 2] .
Ahora los factores envían mensajes a los nodos, el mensaje de F1 a A es el mismo que el mensaje anterior, es decir, [1 2] . Del mismo modo F1 a B es igual que el anterior, es decir
[1 2] , de F2 a B también es igual que el anterior, es decir [4 5] , y F2 a C también es igual, es decir, [2 5]
Como podemos ver, los mensajes de los factores a los nodos son exactamente los mismos que en la iteración anterior (paso 2), podemos detenernos aquí.
Ahora para calcular el marginal de cada nodo, solo tenemos que multiplicar todos los mensajes a ese nodo.
Entonces [matemáticas] \ phi (A) [/ matemáticas] = [1 2] , [matemáticas] \ phi (B) [/ matemáticas] = [1 2] * [4 5] = [4 10] = [2 5 ] , [matemáticas] \ phi (C) [/ matemáticas] = [2 5] .
De estos potenciales no normalizados, podemos obtener las probabilidades respectivas:
P (A = 0) = 1/3 , P (B = 0) = 2/7 , P (C = 0) = 2/7 , que son exactamente lo mismo que calculamos anteriormente a través de la distribución conjunta.