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 a través del algoritmo de suma-producto . Una de las historias de éxito importantes de los gráficos de factores y el algoritmo de suma de productos es la decodificación de códigos de corrección de errores que se acercan a la capacidad , como los códigos LDPC y 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 en el que 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 coherencia de arco para el procesamiento de restricciones.
Definición
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,
dónde , el gráfico de factores correspondiente consta de vértices variables , factorizar vértices y bordes . Las aristas dependen de la factorización de la siguiente manera: hay una arista no dirigida entre el vértice del factor y vértice variable Si . Se asume 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 .
Ejemplos de
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 el gráfico de factores tiene un ciclo . Si nos fusionamosen 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.
Transmisión de mensajes en gráficos de factores
Un algoritmo de paso de mensajes popular en los gráficos de factores es el algoritmo de producto de suma , 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 de 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 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 un 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 de suma de productos se utiliza para la inferencia estadística , por lo quees una distribución conjunta o una función de verosimilitud conjunta , y la factorización depende de las independencia condicional entre las variables.
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 de factores; la última representación se utiliza con frecuencia cuando se realizan inferencias sobre dichas redes utilizando la propagación de creencias . Por otro lado, las redes bayesianas se adaptan más naturalmente a los modelos generativos , ya que pueden representar directamente las causalidades del modelo.
Ver también
enlaces externos
- Una introducción a los gráficos de factores por Hans-Andrea Loeliger , Revista IEEE Signal Processing , enero de 2004, págs. 28–41.
- dimple una herramienta de código abierto para construir y resolver gráficos de factores en MATLAB.
- Introducción a Factor Graph. Presentación de la ETH por el Prof.Dr. Hans Loeliger
Referencias
- Clifford (1990), "Campos aleatorios de Markov en estadística", en Grimmett, GR; Galés, DJA (eds.), Trastorno en los sistemas físicos, JM Hammersley Festschrift , Oxford University Press , págs. 19–32
- Frey, Brendan J. (2003), "Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models", en Jain, Nitin (ed.), UAI'03, Actas de la XIX Conferencia sobre Incertidumbre en Inteligencia Artificial, 7 de agosto –10, Acapulco, México , Morgan Kaufmann, págs. 257–264
- Kschischang, Frank R .; Frey, Brendan J .; Loeliger, Hans-Andrea (2001), "Factor de Gráficos y el algoritmo de suma-producto" , IEEE Transactions on Information Theory , 47 (2): 498-519, doi : 10.1109 / 18.910572 , recuperados 2008-02-06 .
- Wymeersch, Henk (2007), Diseño de receptor iterativo , Cambridge University Press, ISBN 978-0-521-87315-4