Factor graph

In mathematics, a factor graph is an $X,F$-bipartite graph where $X=\{X_{1},X_{2},\dots ,X_{n}\}$ is a set of variables and $F=\{f_{1},f_{2},\dots ,f_{m}\}$ is a set of factors. A factor $f_{j}$ is a function mapping from a subset of variables $X_{j}\subseteq X$ to some range (such as the interval between 0 and 1). This graph represents the factorisation

$g(\mathbf {x} )=\prod _{j=1}^{m}f_{j}(\mathbf {x_{j}} ),$

where $\mathbf {x}$ is an assignment to all variables in $X$ and $\mathbf {x_{j}}$ is the assignment of $\mathbf {x}$ to all variables in $X_{j}$.

When using a factor graph to represent a probability distribution, each factor can be thought of as small distribution over a subset of the variables. The joint distribution is made up from the product of the individual distributions. Factor graphs can be used to describe large distributions in which many pairs of variables are stochastically independent by explicitly listing only those groups of variables which are stochastically dependent.

Inference over a factor graph can be done using a message passing algorithm such as belief propagation. This is much more efficient than marginalization over a general distribution (which sums over every possible value of every variable, resulting in an exponential amount of summands), because the message passing approach exploits the locality properties of the factor graph.

Other probabilistic models such as Markov networks and Bayesian networks can be represented as factor graphs; the latter representation is frequently used when performing inference over such networks using belief propagation. On the other hand, Bayesian networks are more naturally suited for generative models, as they can directly represent the causalities of the model.

See also

• Belief propagation
• Bayesian inference
• Conditional probability
• Markov network
• Bayesian network

External links

• A tutorial-style dissertation by Volker Koch

References

• Frey, Brendan J. Frey (2003), "Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models", in Meek, Christopher; Kjærulff, Uffe (eds.), UAI'03, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence, August 7–10, Acapulco, Mexico, Morgan Kaufmann, pp. 257–264
• Kschischang, Frank R. "Factor Graphs and the Sum-Product Algorithm". IEEE Transactions on Information Theory. 47 (2): 498–519. doi:10.1109/18.910572. Retrieved 2008-02-06. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)