Gráfica factorial

Un gráfico factorial es un gráfico bipartito que representa la factorización de una función . En la teoría de la probabilidad y sus aplicaciones, los gráficos factoriales se utilizan para representar la factorización de una función de distribución de probabilidad , lo que permite cálculos eficientes, como el cálculo de distribuciones marginales a través del algoritmo de suma-producto . Una de las historias de éxito importantes de los gráficos factoriales y el algoritmo de suma-producto es la decodificación de códigos de corrección de errores que se aproximan a la capacidad , como los códigos LDPC y turbo .

Los gráficos factoriales generalizan los gráficos de restricciones . Un factor cuyo valor es 0 o 1 se denomina restricción. Un gráfico de restricciones es un gráfico factorial en el que todos los factores son restricciones. El algoritmo de producto máximo para gráficos factoriales se puede considerar como una generalización del algoritmo de consistencia de arco para el procesamiento de restricciones.

Un gráfico factorial es un gráfico bipartito que representa la factorización de una función. Dada una factorización de una función ,${\displaystyle g(X_{1},X_{2},\puntos ,X_{n})}$

${\displaystyle g(X_{1},X_{2},\puntos ,X_{n})=\prod _{j=1}^{m}f_{j}(S_{j}),}$

donde , el gráfico factorial correspondiente consta de vértices variables , vértices factoriales y aristas . Las aristas dependen de la factorización de la siguiente manera: hay una arista no dirigida entre el vértice factorial y el vértice variable si . Se supone tácitamente que la función tiene un valor real : .${\displaystyle S_{j}\subseteq \{X_{1},X_{2},\puntos ,X_{n}\}}$${\displaystyle G=(X,F,E)}$${\displaystyle X=\{X_{1},X_{2},\puntos ,X_{n}\}}$ ${\displaystyle F=\{f_{1},f_{2},\dots ,f_{m}\}}$${\displaystyle E}$${\displaystyle f_{j}}$${\displaystyle X_{k}}$${\displaystyle X_{k}\in S_{j}}$${\displaystyle g(X_{1},X_{2},\dots ,X_{n})\in \mathbb {R} }$

Los gráficos factoriales se pueden combinar con algoritmos de paso de mensajes para calcular de manera eficiente ciertas características de la función , como las distribuciones marginales .${\displaystyle g(X_{1},X_{2},\dots ,X_{n})}$

Consideremos una función que se factoriza de la siguiente manera:

${\displaystyle g(X_{1},X_{2},X_{3})=f_{1}(X_{1})f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})f_{4}(X_{2},X_{3})}$,

con un gráfico de factores correspondiente que se muestra a la derecha. Observe que el gráfico de factores tiene un ciclo . Si fusionamos en un solo factor, el gráfico de factores resultante será un árbol . Esta es una distinción importante, ya que los algoritmos de paso de mensajes suelen ser exactos para árboles, pero solo aproximados para gráficos con ciclos.${\displaystyle f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})}$

Un algoritmo popular de transmisión de mensajes en gráficos factoriales es el algoritmo de suma-producto, que calcula de manera eficiente todos los marginales de las variables individuales de la función. En particular, el marginal de la variable se define como${\displaystyle X_{k}}$

${\displaystyle g_{k}(X_{k})=\sum _{X_{\bar {k}}}g(X_{1},X_{2},\dots ,X_{n})}$

donde la notación significa que la suma se aplica a todas las variables, excepto . Los mensajes del algoritmo suma-producto se calculan conceptualmente en los vértices y se pasan a lo largo de los bordes. Un mensaje desde o hacia un vértice variable siempre es una función de esa variable en particular. Por ejemplo, cuando una variable es binaria, los mensajes sobre los bordes incidentes al vértice correspondiente se pueden representar como vectores de 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 se debe tener especial cuidado en su representación.${\displaystyle X_{\bar {k}}}$ ${\displaystyle X_{k}}$

En la práctica, se utiliza el algoritmo suma-producto para la inferencia estadística , donde es una distribución conjunta o una función de verosimilitud conjunta , y la factorización depende de las independencias condicionales entre las variables.${\displaystyle g(X_{1},X_{2},\dots ,X_{n})}$

El teorema de Hammersley-Clifford muestra que otros modelos probabilísticos, como las redes bayesianas y las redes de Markov , pueden representarse como gráficos factoriales; esta última representación se utiliza con frecuencia cuando se realizan inferencias sobre dichas redes mediante la propagación de creencias . Por otro lado, las redes bayesianas son más adecuadas para los modelos generativos , ya que pueden representar directamente las causalidades del modelo.

• Propagación de creencias
• Inferencia bayesiana
• Programación bayesiana
• Probabilidad condicional
• Red de Markov
• Red bayesiana
• Teorema de Hammersley-Clifford

• Loeliger, Hans-Andrea (enero de 2004), "Introducción a los gráficos factoriales" (PDF) , IEEE Signal Processing Magazine , 21 (1): 28–41, Bibcode :2004ISPM...21...28L, doi :10.1109/MSP.2004.1267047, S2CID  7722934
• hoyuelo Archivado el 6 de enero de 2016 en Wayback Machine una herramienta de código abierto para construir y resolver gráficos de factores en MATLAB.
• Loeliger, Hans-Andrea (2008), Introducción a los gráficos factoriales (PDF)

• Clifford (1990), "Campos aleatorios de Markov en estadística", en Grimmett, GR; Welsh, DJA (eds.), Desorden en sistemas físicos, JM Hammersley Festschrift (posdata) , Oxford University Press , págs. 19-32, ISBN 9780198532156
• Frey, Brendan J. (2003), "Extensión de gráficos factoriales para unificar modelos gráficos dirigidos y no dirigidos", en Jain, Nitin (ed.), UAI'03, Actas de la 19.ª Conferencia sobre incertidumbre en inteligencia artificial , Morgan Kaufmann, págs. 257–264, arXiv : 1212.2486 , ISBN 0127056645
• Kschischang, Frank R. ; Frey, Brendan J.; Loeliger, Hans-Andrea (2001), "Gráficos factoriales y el algoritmo suma-producto", IEEE Transactions on Information Theory , 47 (2): 498–519, CiteSeerX  10.1.1.54.1570 , doi :10.1109/18.910572.
• Wymeersch, Henk (2007), Diseño iterativo de receptores, Cambridge University Press, ISBN 978-0-521-87315-4