- 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 asubset of variables $X\_jsubseteq\; X$ to some range (such as theinterval 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. Thejoint 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 asbelief propagation . This is much more efficient than marginalization over a general distribution (which sums over every possible value of every variable, resulting in anexponential number of summands), because the message passing approach exploits the locality properties of the factor graph.Other probabilistic models such as

Markov network s andBayesian network s can 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 model s, 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