en>Srleffler: +Category:Supply chain management; +Category:Production and manufacturing; +Category:Project management using HotCat

2014-11-14T23:14:11Z

+Category:Supply chain management; +Category:Production and manufacturing; +Category:Project management using HotCat

82.128.185.150: /* Manufacturing */

2013-11-02T20:18:06Z

Manufacturing

New page

{{Distinguish|Graph factorization}}

In [[probability theory]] and its applications, a '''factor graph''' is a particular type of [[graphical model]], with applications in [[Bayesian inference]], that enables efficient computation of [[marginal distribution]]s through the [[sum-product algorithm]]. One of the important success stories of factor graphs and the [[sum-product algorithm]] is the [[code|decoding]] of capacity-approaching [[error-correcting code]]s, such as [[LDPC]] and [[turbo codes]].

A factor graph is an example of a [[hypergraph]], in that an ''arrow'' (i.e., a factor node) can connect more than one (normal) node.

When there are no free variables, the factor graph of a function ''f'' is equivalent to the [[constraint graph]] of ''f'', which is an instance to a [[constraint satisfaction problem]].

==Definition==
A factor graph is a [[bipartite graph]] representing the [[factorization]] of a function. Given a factorization of a function <math>g(X_1,X_2,\dots,X_n)</math>,
:<math>g(X_1,X_2,\dots,X_n) = \prod_{j=1}^m f_j(S_j),</math>

where <math> S_j \subseteq \{X_1,X_2,\dots,X_n\}</math>, the corresponding factor graph <math> G=(X,F,E)</math> consists of variable vertices
<math>X=\{X_1,X_2,\dots,X_n\}</math>, factor [[vertex (graph theory)|vertices]] <math>F=\{f_1,f_2,\dots,f_m\}</math>, and edges <math>E</math>. The edges depend on the factorization as follows: there is an undirected edge between factor vertex <math> f_j </math> and variable vertex <math> X_k </math> when <math> X_k \in S_j</math>. The function is tacitly assumed to be real-valued: <math>g(X_1,X_2,\dots,X_n) \in \Bbb{R} </math>.

Factor graphs can be combined with message passing algorithms to efficiently compute certain characteristics of the function <math>g(X_1,X_2,\dots,X_n)</math>, such as the [[marginal distribution]]s.

==Examples==
[[File:factorgraph.jpg|300px|right|thumb|An example factor graph]]

Consider a function that factorizes as follows:
:<math>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)</math>,

with a corresponding factor graph shown on the right. Observe that the factor graph has a [[cycle (graph theory)|cycle]]. If we merge <math> f_2(X_1,X_2)f_3(X_1,X_2) </math> into a single factor, the resulting factor graph will be a [[tree (graph theory)|tree]]. 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 <math> X_k </math> is defined as
:<math> g_k(X_k) = \sum_{X_{\bar{k}}} g(X_1,X_2,\dots,X_n)</math>
where the notation <math>X_{\bar{k}} </math> means that the summation goes over all the variables, ''except'' <math> X_k </math>. 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 a [[Function (mathematics)|function]] of 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 of [[real numbers]], messages can be arbitrary functions, and special care needs to be taken in their representation.

In practice, the sum-product algorithm is used for [[statistical inference]], whereby <math> g(X_1,X_2,\dots,X_n)</math> is a joint [[Probability distribution|distribution]] or a joint [[likelihood function]], and the factorization depends on the [[conditional independence|conditional independencies]] among the variables.

The [[Hammersley–Clifford theorem]] shows that other probabilistic models such as [[Markov network]]s and [[Bayesian network]]s 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 model]]s, 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==
* [http://www.volker-koch.com/diss/ A tutorial-style dissertation by Volker Koch]
* [http://www.robots.ox.ac.uk/~parg/mlrg/papers/factorgraphs.pdf An Introduction to Factor Graphs] by [[Hans-Andrea Loeliger]], ''[[IEEE Signal Processing Magazine]],'' January 2004, pp. 28–41.
* [http://dimple.probprog.org/ dimple] an open-source tool for building and solving factor graphs in MATLAB.
* [http://people.binf.ku.dk/~thamelry/MLSB08/hal.pdf An introduction to Factor Graph. Presentation from the ETH by Prof. Dr. Hans Loeliger]
{{No footnotes|date=September 2010}}

==References==
* {{Citation|contribution=Markov random fields in statistics|last=Clifford|year=1990|editor1-last=Grimmett|editor1-first=G.R.|editor2-last=Welsh|editor2-first=D.J.A.|title=Disorder in Physical Systems, J.M. Hammersley Festschrift|pages=19–32|publisher=[[Oxford University Press]]|url=http://www.statslab.cam.ac.uk/~grg/books/hammfest/3-pdc.ps}}
* {{Citation
| last = Frey
| first = Brendan J.
| 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 }}
* {{Citation
| last1 = Kschischang
| first1 = Frank R.
| authorlink1=Frank Kschischang
| first2 = Brendan J. |last2=Frey |first3= Hans-Andrea |last3=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
| postscript = . }}
* {{Citation
| last = Wymeersch
| first = Henk
| title = Iterative Receiver Design
| year = 2007
| publisher = Cambridge University Press
| url = http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=9780521873154
| isbn = 0-521-87315-0 }}

{{DEFAULTSORT:Factor Graph}}
[[Category:Graphical models]]
[[Category:Markov networks]]
[[Category:Application-specific graphs]]

Lead time - Revision history

en>Srleffler: +Category:Supply chain management; +Category:Production and manufacturing; +Category:Project management using HotCat

82.128.185.150: /* Manufacturing */