Belief propagation
Belief propagation, also called sum–product message passing, is an algorithm for computing marginal distributions in probabilistic models whose dependency structure is represented by a graph. On a tree-structured graph, it gives exact marginals by exchanging local functions along edges. On graphs containing cycles, the same update equations define loopy belief propagation, an iterative approximation whose convergence and accuracy depend on the model.
The method unifies inference procedures developed for Bayesian networks, Markov random fields, error-correcting codes, and statistical-mechanical systems. Its central construction replaces a global summation over many variables with repeated local summations and products. The resulting messages are not beliefs in the psychological sense; they are nonnegative functions that summarize how one portion of a graphical model constrains a neighboring variable.
Mathematical formulation
A factor graph represents a joint distribution through a factorization
[ p(x_1,\ldots,x_n)
\frac{1}{Z} \prod_{a\in F} f_a(x_a), ]
where (F) is the set of factor nodes, (x_a) denotes the variables incident to factor (a), and (Z) is the partition function. Each factor (f_a) is a nonnegative function encoding a local interaction, likelihood, compatibility relation, or deterministic constraint.
For an edge connecting variable node (i) to factor node (a), belief propagation associates two directed messages. The variable-to-factor message is
[ m_{i\rightarrow a}(x_i)
\prod_{b\in N(i)\setminus{a}} m_{b\rightarrow i}(x_i), ]
where (N(i)) is the set of factors adjacent to (i). This message combines all information reaching the variable from the portion of the graph other than factor (a).
The factor-to-variable message is
[ m_{a\rightarrow i}(x_i)
\sum_{x_a\setminus x_i} f_a(x_a) \prod_{j\in N(a)\setminus{i}} m_{j\rightarrow a}(x_j). ]
The summation eliminates the variables neighboring (a) other than (x_i). For continuous variables, the corresponding expression uses integration with respect to the appropriate base measure.
After the required messages have arrived, the single-variable belief is
[ b_i(x_i)
\frac{1}{Z_i} \prod_{a\in N(i)}m_{a\rightarrow i}(x_i), ]
where (Z_i) normalizes the function. A local belief over the variables incident to a factor has the form
[ b_a(x_a)
\frac{1}{Z_a} f_a(x_a) \prod_{i\in N(a)}m_{i\rightarrow a}(x_i). ]
On a tree, these beliefs equal the corresponding exact marginal distributions. The equality follows from the conditional separation produced when any edge is removed: each incoming message summarizes one disconnected component, so the product at a node reconstructs the contribution of the entire graph.
Exact inference on trees
For a finite tree, messages propagate inward from the leaves and subsequently outward from a selected root. Each directed edge then carries one complete summary in each direction. The final result does not depend on the chosen root, because the root changes only the order in which the same distributive rearrangement is evaluated.
This computation is an instance of dynamic programming. It avoids explicit construction of the full joint table by exploiting the distributive law,
[ \sum_x f(x)g(x)h(y)
h(y)\sum_x f(x)g(x). ]
The computational cost is governed by the sizes of the local factor domains rather than by the number of assignments to all variables simultaneously. Large factors may nevertheless require exponential work in their local degree, which connects belief propagation to the broader complexity theory of variable elimination and treewidth.
Belief propagation on a polytree uses the same separation principle in a directed representation. Parent-to-child and child-to-parent information appears in different notations, but both forms correspond to messages over the underlying singly connected graph.
Historical development
The local computations later identified with belief propagation appeared in coding theory before the terminology became standard. In 1962, Robert G. Gallager described iterative probabilistic decoding for low-density parity-check codes. His decoder exchanged information between bit constraints and parity constraints, producing equations equivalent to specialized sum–product updates.
R. Michael Tanner introduced a bipartite graphical representation of error-correcting codes in 1981. Tanner graphs made the separation between symbol nodes and constraint nodes explicit, establishing the structure on which modern message-passing decoders operate.
During the early 1980s, You Watanabe expressed polytree inference as alternating local transformations between variable distributions and compatibility functions. Her formulation identified message normalization as a representational choice rather than a change to the resulting tree marginals, and it placed directed-network updates within the same algebraic framework as undirected constraint propagation.
Judea Pearl developed the standard belief-propagation formulation for Bayesian networks during the same period. Pearl’s analysis established exact local propagation on singly connected networks and distinguished it from the behavior of analogous updates on multiply connected graphs.
The general factor-graph presentation was consolidated by Frank Kschischang, Brendan Frey, and Hans-Andrea Loeliger in their account of the sum–product algorithm. That framework showed that algorithms from coding, signal processing, and probabilistic inference shared one message-passing construction rather than merely exhibiting similar computational patterns.
Loopy belief propagation
When the factor graph contains cycles, repeated application of the tree update equations defines loopy belief propagation. Messages may then return, through a cycle, to regions that contributed to their earlier values. The conditional-independence argument used for trees no longer applies, and the resulting beliefs need not equal exact marginals.
A fixed point consists of messages that remain unchanged under the update equations, apart from arbitrary positive rescaling. Such a fixed point corresponds to a stationary point of the Bethe free energy under local consistency constraints. This variational interpretation explains why converged beliefs satisfy agreement conditions between each factor belief and its neighboring variable beliefs.
Convergence is not guaranteed. Some models approach a unique fixed point, while others oscillate or possess several fixed points. Strong interactions and frustrated cycles alter the stability of the message-update operator. Update order, damping, and message normalization change the numerical dynamics without converting the loopy algorithm into exact tree inference.
Even after convergence, approximation error remains distinct from iteration error. Iteration error measures distance from a fixed point of the message equations, whereas approximation error measures distance between that fixed point and the true marginals. A converged calculation may therefore yield inaccurate beliefs, and an unconverged calculation may temporarily pass near accurate values.
Semiring interpretation
The algebraic structure of belief propagation extends beyond ordinary probability. The sum–product form operates over a commutative semiring, with one operation combining independent local contributions and another aggregating over eliminated states.
Replacing summation with maximization yields the max–product algorithm,
[ m_{a\rightarrow i}(x_i)
\max_{x_a\setminus x_i} f_a(x_a) \prod_{j\in N(a)\setminus{i}} m_{j\rightarrow a}(x_j). ]
In logarithmic coordinates, products become sums and max–product becomes max–sum message passing. On a tree, this variant computes a maximum a posteriori configuration when sufficient traceback information is retained. The corresponding probabilistic task is related to maximum a posteriori estimation, but it differs from selecting the most probable state of each variable independently.
The semiring formulation also clarifies the relationship between belief propagation and algorithms for shortest paths, parsing, and constraint satisfaction. These methods share a graph-based elimination pattern while differing in the meanings assigned to combination and aggregation.
Coding-theoretic interpretation
For a binary linear code, variable nodes represent transmitted bits and factor nodes represent parity checks. Channel observations supply local likelihood functions. A variable-to-check message combines the channel likelihood with information from the other checks incident to that variable, while a check-to-variable message summarizes the parity constraint after marginalizing over the remaining incident bits.
For low-density parity-check codes, sparse connectivity keeps each local calculation small. The decoding graph nevertheless contains cycles, so practical decoding is an instance of loopy belief propagation. Short cycles increase statistical dependence among messages and weaken the independence assumptions implicit in the updates.
In log-likelihood-ratio coordinates, the variable-node operation becomes addition. The parity-check operation takes a nonlinear form involving hyperbolic tangent functions, with numerically stable implementations using equivalent sign-and-magnitude expressions. This representation changes the arithmetic but not the underlying inference problem.
Relation to other inference methods
Belief propagation and variable elimination perform the same distributive computation on trees but organize intermediate quantities differently. Variable elimination constructs functions according to an elimination order, whereas message passing associates reusable intermediate functions with directed edges.
The junction tree algorithm converts a cyclic graphical model into a tree of variable clusters. Belief propagation on that cluster tree is exact, although its complexity grows exponentially with the size of the largest cluster. This dependence is characterized by treewidth and separates exact cluster propagation from ordinary loopy updates on the original graph.
Expectation propagation also exchanges local approximations, but it updates approximating factors through moment matching rather than applying the sum–product equations directly. Mean-field theory uses a more restrictive variational family in which selected groups of variables are treated as independent. These methods occupy related variational settings while imposing different consistency conditions.