Un gráfico de factores 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 de factores 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 mediante el algoritmo suma-producto . Una de las historias de éxito importantes de los gráficos de factores 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 LDPC y códigos turbo .
Los gráficos de factores generalizan los gráficos de restricciones . Un factor cuyo valor es 0 o 1 se llama restricción. Un gráfico de restricciones es un gráfico de factores donde todos los factores son restricciones. El algoritmo de producto máximo para gráficos de factores puede verse como una generalización del algoritmo de consistencia de arco para el procesamiento de restricciones.
Un gráfico de factores es un gráfico bipartito que representa la factorización de una función. Dada una factorización de una función ,
donde , el gráfico de factores correspondiente consta de vértices variables , vértices de factores y aristas . Las aristas dependen de la factorización de la siguiente manera: hay una arista no dirigida entre el vértice del factor y el vértice de la variable si . Se supone tácitamente que la función tiene un valor real : .
Los gráficos de factores 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 .
Considere una función que factoriza de la siguiente manera:
con un gráfico de factores correspondiente que se muestra a la derecha. Observe que la gráfica 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 los árboles, pero sólo aproximados para los gráficos con ciclos.
Un algoritmo de paso de mensajes popular en gráficos de factores 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
donde la notación significa que la suma abarca 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 de variable es siempre 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 La variable pertenece al campo de los números reales , los mensajes pueden ser funciones arbitrarias y se debe tener especial cuidado en su representación.
En la práctica, el algoritmo suma-producto se utiliza para la inferencia estadística , mediante el cual es una distribución conjunta o una función de probabilidad conjunta , y la factorización depende de las independencias condicionales entre las variables.
El teorema de Hammersley-Clifford muestra que otros modelos probabilísticos, como las redes bayesianas y las redes de Markov, se pueden representar como gráficos de factores; la última representación se utiliza con frecuencia al realizar inferencias sobre dichas redes mediante la propagación de creencias . Por otro lado, las redes bayesianas son más adecuadas para modelos generativos , ya que pueden representar directamente las causalidades del modelo.
