Factor graph


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 ofmathbf{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


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Factor-critical graph — In graph theory, a mathematical discipline, factor critical graph is a graph with n vertices in which any subset of n − 1 vertices has a perfect matching. For example, any odd length cycle graph is factor critical.Factor critical graphs must… …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • graph — /graf, grahf/, n. 1. a diagram representing a system of connections or interrelations among two or more things by a number of distinctive dots, lines, bars, etc. 2. Math. a. a series of points, discrete or continuous, as in forming a curve or… …   Universalium

  • Compressibility factor — Thermodynamics …   Wikipedia

  • Bipartite graph — In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V ; that is, U and V are independent sets.… …   Wikipedia

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • Matching (graph theory) — In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… …   Wikipedia

  • Feynman graph — A Feynman graph is a graph suitable to be a Feynman diagram in a particular application of quantum field theory. (The most common use is when each field has quanta (particles) associated with it as the quantum of the electromagnetic field is a… …   Wikipedia