¿BP descabellado dar las mismas soluciones como un dechado de Gibbs?

Question

La literatura en MCMC y LBP nunca se refieren al hecho de que los dos métodos tienen un aspecto (en expectativa) exactamente el mismo. Para ilustrar, considere primero un simple modelo de Ising, es decir, una gráfica de un modelo en el que todas las variables son booleanas. Podemos denotar estas variables como $\{ X_i | X \in \{0,1\}, i \in (1,...,n)\}$ y podemos escribir la distribución conjunta en cierta forma factorizada como: $$ P(X) = \frac{1}{Z}\prod_{\alpha} \Psi_\alpha(X_\alpha) $$ Donde $\alpha$ es algún subconjunto de las variables y $\Psi_\alpha$ es una función potencial sobre estas variables. Suponiendo que estamos interesados en calcular la distribución marginal de un conjunto de variables podemos ejecutar Loopy de BP para calcular estos o podemos ejecutar un muestreador de Gibbs para simular de $P$ muestras $\{X^{(1)},...,X^{(m)}\}$ y calcular el marginal como: $X_i = \frac{1}{m}\sum_{j=1}^m X^{(j)}_i$.

Por ahora, considere la posibilidad de ejecutar un número infinito de Gibbs, samplers, al mismo tiempo, suele ser computacionalmente intratable, ya que sería necesario para mantener un número infinito de conjuntos muestra. Sin embargo, para distribuciones discretas podemos representar estas muestras de manera eficiente con un solo vector. En nuestro modelo de Ising, por ejemplo, podemos representar los conjuntos de muestras con un conjunto de vectores 2D $\{V_i | V \in \mathbb{R}^2, i \in (1,...,n)\}$. La primera componente del vector de $V_i$ da la proporción de las cadenas donde $X_i = 1$ y el segundo componente indica la proporción donde $X_i = 0$ (por supuesto que sólo necesita 1 dimensión para representar esto, pero no importa). Así que, asumiendo inicializamos las variables de nuestro Gibbs muestreadores de manera uniforme, a continuación, todos estos vectores sería igual a $[0.5, 0.5]$. Luego se puede continuar con el ordinario de Gibbs actualizaciones: el bucle a través de cada una de las variables (vectores) y volver a la muestra de acuerdo a los vecinos de los potenciales (condicionales). Después de una quemadura en el período de estos vectores representan el conjunto de muestras que se extraen de la distribución estacionaria $P$, entonces podemos calcular la distribución marginal para cada una de las variables por un promedio de estos vectores.

Ahora, otros que el promedio de paso, este procedimiento es idéntico a la loopy de BP. Y, de hecho, el promedio no es probable que la materia, ya que estos valores tienden a converger en mosts de los casos.

Si, de hecho, loopy de BP es exactamente el mismo como un "infinito" muestreador de Gibbs por qué es la literatura sobre estos dos métodos muy diferentes. Todos los Loopy BP análisis parece estar preocupado con la forma en que se minimiza el Bethe energía libre, mientras que el de Gibbs de la literatura se centra en la mezcla de tasas y la ergodicity de la cadena de Markov. También, sería simplemente el promedio de los mensajes en un Loopy BP inferencia procedimiento de proporcionar una estimación correcta en los casos donde las actualizaciones son oscilantes? Podrían los avances en el muestreo de Gibbs de la literatura, tales como el bloque de Gibbs, ser utilizado en Loopy BP esquemas para la velocidad de convergencia? Por último, si Loopy BP converge a una solución incorrecta, ¿eso implica que el Gibbs de la cadena no es ergodic?

Answer 1

Son diferentes

Considere la posibilidad de BP actualización de ecuaciones $$M_{i}(x)\propto \prod_j m_{ij}(x)$$ $$m_{ij}(x) \propto \sum_y \psi(x,y) \prod_{k \ne i} m_{jk}(y)$$

La primera nota es que las cantidades que se actualizan en los bordes, en lugar de los nodos. Ahora, tenga en cuenta el efecto de la $k \ne i$ part. Esto asegura que las actualizaciones son "no retroceso". Así, cuando las cantidades de entrar en el nodo $i$ cambiar, este desemboca en el nodo $j$, pero luego no fluya de nuevo en el nodo $i$ en el tercer paso. En contraste, con el muestreo de Gibbs puede actualizar el nodo $i$ a tiempo 1, que afecta a los vecinos de valor de nodo $j$ en el tiempo 2, y este cambio viene de nuevo a afectar nodo $i$ en el momento del paso 3. Desde este inmediata bucle de retroalimentación no está presente en BP, en un grafo sin ciclos, los valores de dejar de cambiar después de un número finito de actualizaciones.

Ingenuo medio campo mantiene unidos en nodos del grafo a diferencia de BP, por lo que NMF actualizaciones son más similares a los de muestreo de Gibbs.

Otra cosa a tener en cuenta es que, a menos grafo es un árbol, la creencia de propagación converge a la respuesta equivocada. Considerar ferromagnéticos modelo de Ising en un bucle gráfico, 0 campo magnético. Si usted hace la fuerza de acoplamiento muy grande, la creencia de propagación se convergen a 0 o a 1, mientras que la respuesta correcta es de 0,5

Tan lejos como un promedio de los valores de pa cuando BP es oscilante-sí, la gente lo ha hecho y que ayuda con la convergencia, sin embargo, que no es demasiado útil, porque la convergencia y la calidad de los resultados de BP están correlacionados. En otras palabras, usted podría obligar a BP a converger, pero entonces los resultados pueden ser inexactos.

Bloque de Gibbs es similar en espíritu a Clúster Creencia de la Propagación y de la Generalizada Creencia de Propagación, que permiten la actualización de varias variables simultáneamente.

Para el análisis de BP convergencia puede considerar el análisis por Joris Mooij ( Condiciones suficientes para la convergencia de Loopy Creencia de Propagación). Básicamente, la creencia de propagación se mete en problemas cuando la ramificación factor de no-retroceso de paseo aleatorio en el gráfico se vuelve demasiado grande. Por otro lado, el polinomio de tiempo de mezcla de Gibbs sampler está más estrechamente relacionados con el factor de ramificación de un auto-evitar caminar en el gráfico que siempre es menor.