Factor graph

A factor graph is a bipartite graph representing the factorization of a function. In probability theory and its applications, factor graphs are used to represent factorization of a probability distribution function, enabling efficient computations, such as the computation of marginal distributions through the sum-product algorithm. One of the important success stories of factor graphs and the sum-product algorithm is the decoding of capacity-approaching error-correcting codes, such as LDPC and turbo codes. A factor graph is a bipartite graph representing the factorization of a function. In probability theory and its applications, factor graphs are used to represent factorization of a probability distribution function, enabling efficient computations, such as the computation of marginal distributions through the sum-product algorithm. One of the important success stories of factor graphs and the sum-product algorithm is the decoding of capacity-approaching error-correcting codes, such as LDPC and turbo codes. Factor graphs generalize constraint graphs. A factor whose value is either 0 or 1 is called a constraint. A constraint graph is a factor graph where all factors are constraints. The max-product algorithm for factor graphs can be viewed as a generalization of the arc-consistency algorithm for constraint processing. A factor graph is a bipartite graph representing the factorization of a function. Given a factorization of a function g ( X 1 , X 2 , … , X n ) {displaystyle g(X_{1},X_{2},dots ,X_{n})} , where S j ⊆ { X 1 , X 2 , … , X n } {displaystyle S_{j}subseteq {X_{1},X_{2},dots ,X_{n}}} , the corresponding factor graph G = ( X , F , E ) {displaystyle G=(X,F,E)} consists of variable vertices X = { X 1 , X 2 , … , X n } {displaystyle X={X_{1},X_{2},dots ,X_{n}}} , factor vertices F = { f 1 , f 2 , … , f m } {displaystyle F={f_{1},f_{2},dots ,f_{m}}} , and edges E {displaystyle E} . The edges depend on the factorization as follows: there is an undirected edge between factor vertex f j {displaystyle f_{j}} and variable vertex X k {displaystyle X_{k}} iff X k ∈ S j {displaystyle X_{k}in S_{j}} . The function is tacitly assumed to be real-valued: g ( X 1 , X 2 , … , X n ) ∈ R {displaystyle g(X_{1},X_{2},dots ,X_{n})in mathbb {R} } . Factor graphs can be combined with message passing algorithms to efficiently compute certain characteristics of the function g ( X 1 , X 2 , … , X n ) {displaystyle g(X_{1},X_{2},dots ,X_{n})} , such as the marginal distributions.