Gráfico del factor

En la teoría de probabilidad y sus aplicaciones, un gráfico del factor es un tipo particular del modelo gráfico, con aplicaciones en la inferencia de Bayesian, que permite el cálculo eficiente de distribuciones marginales a través del algoritmo del producto de la suma. Una de las historias de éxito importantes de gráficos del factor y el algoritmo del producto de la suma es el descifre de códigos se acercan a la capacidad que corrigen el error, como códigos del turbo y LDPC.

Un gráfico del factor es un ejemplo de un hipergráfico, en esto una flecha (es decir, un nodo del factor) puede unir más de un nodo (normal)

Definición

Un gráfico del factor es un gráfico bipartito que representa el factorization de una función. Considerando un factorization de una función,

:

donde, el gráfico del factor correspondiente consiste en vértices variables

, vértices del factor y bordes. Los bordes dependen del factorization así: hay un borde no dirigido entre vértice del factor y vértice variable cuando. Se supone tácitamente que la función se valore del modo verdadero:.

Los gráficos del factor se pueden combinar con el mensaje que pasa algoritmos para calcular eficazmente ciertas características de la función, como las distribuciones marginales.

Ejemplos

Considere una función que descompone en factores así:

:,

con un gráfico del factor correspondiente mostrado a la derecha. Observe que el gráfico del factor tiene un ciclo. Si nos combinamos en un factor solo, el gráfico del factor que resulta será un árbol. Esto es una distinción importante, ya que el mensaje que pasa algoritmos es por lo general exacto para árboles, pero sólo se acerca para gráficos con ciclos.

Mensaje que pasa gráficos del factor

Un mensaje popular que pasa el algoritmo en gráficos del factor es el algoritmo del producto de la suma, que eficazmente calcula todo el marginals de las variables individuales de la función. En particular, la marginal de la variable se define como

:

donde la nota significa que la adición revisa todas las variables, excepto. Los mensajes del algoritmo del producto de la suma conceptualmente se calculan en los vértices y se hacen pasar los bordes. Un mensaje de o a un vértice variable siempre es una función de esa variable particular. Por ejemplo, cuando una variable es binaria, los mensajes

sobre el incidente de bordes al vértice correspondiente se puede representar como vectores de la longitud 2: la primera entrada es el mensaje evaluado en 0, la segunda entrada es el mensaje evaluado en 1. Cuando una variable pertenece al campo de números reales, los mensajes pueden ser funciones arbitrarias, y el cuidado especial se tiene que tomar en su representación.

En la práctica, el algoritmo del producto de la suma se usa para la inferencia estadística, por lo cual es una distribución conjunta o una función de probabilidad conjunta, y el factorization depende de las independencias condicionales entre las variables.

El teorema de Hammersley-Clifford muestra que otros modelos probabilistic como redes de Markov y redes de Bayesian se pueden representar como gráficos del factor; la representación última con frecuencia se usa realizando la inferencia sobre tales redes usando la propagación de la creencia. la otra mano, las redes de Bayesian más naturalmente se satisfacen para modelos generativos, ya que pueden representar directamente las causalidades del modelo.

Véase también

Enlaces externos



Buscar