- Factor graph
mathematics, a factor graph is an - bipartite graphwhere is a set of variables and is a set of factors. A "factor" is a function mapping from a subsetof variables to some range (such as the intervalbetween 0 and 1). This graph represents the factorisation :
where is an assignment to all variables in and is the assignment of to all variables in .
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 distributionis 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 passingalgorithm 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 exponentialnumber 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.
* [http://www.volker-koch.com/diss/ A tutorial-style dissertation by Volker Koch]
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