Gráfico de fator - Factor graph

Um gráfico de fator é um gráfico bipartido que representa a fatoração de uma função. Na teoria da probabilidade e suas aplicações, os gráficos de fator são usados ​​para representar a fatoração de uma função de distribuição de probabilidade, permitindo cálculos eficientes, como o cálculo de distribuições marginais por meio do algoritmo de soma-produto . Uma das histórias de sucesso importantes dos gráficos de fator e do algoritmo de soma-produto é a decodificação de códigos de correção de erros que se aproximam da capacidade , como códigos LDPC e turbo .

Os gráficos de fator generalizam os gráficos de restrição . Um fator cujo valor é 0 ou 1 é chamado de restrição. Um gráfico de restrição é um gráfico de fator em que todos os fatores são restrições. O algoritmo de produto máximo para gráficos de fator pode ser visto como uma generalização do algoritmo de consistência de arco para processamento de restrição.

Definição

Um gráfico de fator é um gráfico bipartido que representa a fatoração de uma função. Dada a fatoração de uma função , ${\ displaystyle g (X_ {1}, X_ {2}, \ dots, X_ {n})}$

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

onde , o gráfico de fator correspondente consiste em vértices variáveis , vértices de fator e arestas . As arestas dependem da fatoração da seguinte maneira: há uma aresta não direcionada entre o vértice do fator e o vértice variável se . A função é assumida tacitamente a ser valorizado verdadeira : . ${\ displaystyle S_ {j} \ subseteq \ {X_ {1}, X_ {2}, \ dots, X_ {n} \}}$${\ displaystyle G = (X, F, E)}$${\ displaystyle X = \ {X_ {1}, X_ {2}, \ dots, 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}}$

Os gráficos de fator podem ser combinados com algoritmos de passagem de mensagem para calcular com eficiência certas características da função , como as distribuições marginais . ${\ displaystyle g (X_ {1}, X_ {2}, \ dots, X_ {n})}$

Exemplos

Considere uma função que fatora da seguinte forma:

${\ 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})}$,

com um gráfico de fator correspondente mostrado à direita. Observe que o gráfico de fator tem um ciclo . Se nos fundirmos em um único fator, o gráfico de fator resultante será uma árvore . Esta é uma distinção importante, pois os algoritmos de passagem de mensagens são geralmente exatos para árvores, mas apenas aproximados para gráficos com ciclos. ${\ displaystyle f_ {2} (X_ {1}, X_ {2}) f_ {3} (X_ {1}, X_ {2})}$

Transmissão de mensagens em gráficos de fator

Um algoritmo popular de passagem de mensagens em gráficos de fator é o algoritmo de soma-produto , que calcula com eficiência todos os marginais das variáveis ​​individuais da função. Em particular, o marginal da variável é definido como ${\ displaystyle X_ {k}}$

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

onde a notação significa que a soma passa por todas as variáveis, exceto . As mensagens do algoritmo soma-produto são calculadas conceitualmente nos vértices e passadas ao longo das arestas. Uma mensagem de ou para um vértice de variável é sempre uma função dessa variável particular. Por exemplo, quando uma variável é binária, as mensagens sobre as arestas incidentes ao vértice correspondente podem ser representadas como vetores de comprimento 2: a primeira entrada é a mensagem avaliada em 0, a segunda entrada é a mensagem avaliada em 1. Quando um a variável pertence ao campo dos números reais , as mensagens podem ser funções arbitrárias e é necessário ter um cuidado especial na sua representação. ${\ displaystyle X _ {\ bar {k}}}$ ${\ displaystyle X_ {k}}$

Na prática, o algoritmo soma-produto é usado para inferência estatística , sendo uma distribuição conjunta ou uma função de verossimilhança conjunta , e a fatoração depende das independências condicionais entre as variáveis. ${\ displaystyle g (X_ {1}, X_ {2}, \ dots, X_ {n})}$

O teorema de Hammersley-Clifford mostra que outros modelos probabilísticos, como redes Bayesianas e redes de Markov, podem ser representados como grafos de fatores; a última representação é freqüentemente usada ao realizar inferência sobre tais redes usando propagação de crenças . Por outro lado, as redes bayesianas são mais naturalmente adequadas para modelos generativos , pois podem representar diretamente as causalidades do modelo.

Veja também

• Propagação de crenças
• Inferência bayesiana
• Programação bayesiana
• Probabilidade Condicional
• Rede Markov
• Rede bayesiana
• Teorema de Hammersley-Clifford

links externos

• Loeliger, Hans-Andrea (janeiro de 2004), "An Introduction to Factor Graphs]" (PDF) , IEEE Signal Processing Magazine , 21 (1): 28-41, Bibcode : 2004ISPM ... 21 ... 28L , doi : 10.1109 / MSP.2004.1267047
• covinha uma ferramenta de código aberto para construir e resolver gráficos de fator no MATLAB.
• Loeliger, Hans-Andrea (2008), Uma introdução aos gráficos de fator (PDF)

Referências

• Clifford (1990), "Markov random fields in statistics", em Grimmett, GR; Welsh, DJA (eds.), Disorder in Physical Systems, JM Hammersley Festschrift (postscript) , Oxford University Press , pp. 19-32, ISBN 9780198532156
• Frey, Brendan J. (2003), "Extending Factor Graphs so to Unify Directed and Undirected Graphical Models" , em Jain, Nitin (ed.), UAI'03, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence , Morgan Kaufmann , pp. 257-264, arXiv : 1212.2486 , ISBN 0127056645
• Kschischang, Frank R .; Frey, Brendan J .; Loeliger, Hans-Andrea (2001), "Factor Graphs and the Sum-Product Algorithm", IEEE Transactions on Information Theory , 47 (2): 498-519, CiteSeerX  10.1.1.54.1570 , doi : 10.1109 / 18.910572 .
• Wymeersch, Henk (2007), Iterative Receiver Design , Cambridge University Press, ISBN 978-0-521-87315-4