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\_jsubseteq\; 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 number 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

* [http://www.volker-koch.com/diss/ A tutorial-style dissertation by Volker Koch]

References

* Citation
last = Frey
first = Brendan J. Frey
editor-last = jain
editor-first = Nitin
contribution = Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models
title = UAI'03, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence, August 7–10, Acapulco, Mexico
year = 2003
pages = 257–264
publisher = Morgan Kaufmann
* cite journal
last = Kschischang
first = Frank R.
coauthors = Brendan J. Frey and Hans-Andrea Loeliger
title = Factor Graphs and the Sum-Product Algorithm
journal = IEEE Transactions on Information Theory
volume = 47
issue = 2
pages = 498–519
year = 2001
url = http://citeseer.ist.psu.edu/kschischang01factor.html
doi = 10.1109/18.910572
accessdate = 2008-02-06