Factor graph

Not to be confused withGraph factorization.

Afactor graphis abipartite graphrepresenting thefactorizationof afunction.Inprobability theoryand its applications, factor graphs are used to represent factorization of aprobability distribution function,enabling efficient computations, such as the computation ofmarginal distributionsthrough thesum–product algorithm.One of the important success stories of factor graphs and the sum–product algorithm is thedecodingof capacity-approachingerror-correcting codes,such asLDPCandturbo codes.

Factor graphs generalizeconstraint graphs.A factor whose value is either 0 or 1 is called a constraint. A constraint graph is a factor graph where all factors are constraints. The max-product algorithm for factor graphs can be viewed as a generalization of thearc-consistency algorithmfor constraint processing.

Definition

A factor graph is abipartite graphrepresenting thefactorizationof a function. Given a factorization of a function$g(X_{1},X_{2},\dots,X_{n})$,

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

where$S_{j}\subseteq \{X_{1},X_{2},\dots,X_{n}\}$,the corresponding factor graph$G=(X,F,E)$consists of variable vertices $X=\{X_{1},X_{2},\dots,X_{n}\}$,factorvertices$F=\{f_{1},f_{2},\dots,f_{m}\}$,and edges$E$.The edges depend on the factorization as follows: there is an undirected edge between factor vertex$f_{j}$and variable vertex$X_{k}$if$X_{k}\in S_{j}$.The function is tacitly assumed to bereal-valued:$g(X_{1},X_{2},\dots,X_{n})\in \mathbb {R}$.

Factor graphs can be combined with message passing algorithms to efficiently compute certain characteristics of the function$g(X_{1},X_{2},\dots,X_{n})$,such as themarginal distributions.

Examples

An example factor graph

Consider a function that factorizes as follows:

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

with a corresponding factor graph shown on the right. Observe that the factor graph has acycle.If we merge$f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})$into a single factor, the resulting factor graph will be atree.This is an important distinction, as message passing algorithms are usually exact for trees, but only approximate for graphs with cycles.

Message passing on factor graphs

A popular message passing algorithm on factor graphs is the sum–product algorithm, which efficiently computes all the marginals of the individual variables of the function. In particular, the marginal of variable$X_{k}$is defined as

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

where the notation$X_{\bar {k}}$means that the summation goes over all the variables,except$X_{k}$.The messages of the sum–product algorithm are conceptually computed in the vertices and passed along the edges. A message from or to a variable vertex is always afunctionof that particular variable. For instance, when a variable is binary, the messages over the edges incident to the corresponding vertex can be represented as vectors of length 2: the first entry is the message evaluated in 0, the second entry is the message evaluated in 1. When a variable belongs to the field ofreal numbers,messages can be arbitrary functions, and special care needs to be taken in their representation.

In practice, the sum–product algorithm is used forstatistical inference,whereby$g(X_{1},X_{2},\dots,X_{n})$is a jointdistributionor a jointlikelihood function,and the factorization depends on theconditional independenciesamong the variables.

TheHammersley–Clifford theoremshows that other probabilistic models such asBayesian networksandMarkov networkscan be represented as factor graphs; the latter representation is frequently used when performing inference over such networks usingbelief propagation.On the other hand, Bayesian networks are more naturally suited forgenerative models,as they can directly represent the causalities of the model.

See also

• Belief propagation
• Bayesian inference
• Bayesian programming
• Conditional probability
• Markov network
• Bayesian network
• Hammersley–Clifford theorem

External links

• Loeliger, Hans-Andrea (January 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,S2CID7722934
• dimpleArchived2016-01-06 at theWayback Machinean open-source tool for building and solving factor graphs in MATLAB.
• Loeliger, Hans-Andrea (2008),An introduction to Factor Graphs(PDF)

References

• Clifford (1990), "Markov random fields in statistics", in Grimmett, G.R.; Welsh, D.J.A. (eds.),Disorder in Physical Systems, J.M. Hammersley Festschrift(postscript),Oxford University Press,pp. 19–32,ISBN9780198532156
• Frey, Brendan J. (2003),"Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models",in Jain, Nitin (ed.),UAI'03, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence,Morgan Kaufmann, pp. 257–264,arXiv:1212.2486,ISBN0127056645
• 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,CiteSeerX10.1.1.54.1570,doi:10.1109/18.910572.
• Wymeersch, Henk (2007),Iterative Receiver Design,Cambridge University Press,ISBN978-0-521-87315-4