Belief propagation, also known as sum–product message passing, is a message-passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node (or variable), conditional on any observed nodes (or variables). Belief propagation is commonly used in artificial intelligence and information theory, and has demonstrated empirical success in numerous applications, including low-density parity-check codes, turbo codes, free energy approximation, and satisfiability.

The algorithm was first proposed by Judea Pearl in 1982, who formulated it as an exact inference algorithm on trees, later extended to polytrees. While the algorithm is not exact on general graphs, it has been shown to be a useful approximate algorithm.

Given a finite set of discrete random variables ${\displaystyle X_{1},\ldots ,X_{n}}$ with joint probability mass function ${\displaystyle p}$, a common task is to compute the marginal distributions of the ${\displaystyle X_{i}}$. The marginal of a single ${\displaystyle X_{i}}$ is defined to be

where ${\displaystyle \mathbf {x} '=(x'_{1},\ldots ,x'_{n})}$ is a vector of possible values for the ${\displaystyle X_{i}}$, and the notation ${\displaystyle \mathbf {x} ':x'_{i}=x_{i}}$ means that the sum is taken over those ${\displaystyle \mathbf {x} '}$ whose ${\displaystyle i}$th coordinate is equal to ${\displaystyle x_{i}}$.

Computing marginal distributions using this formula quickly becomes computationally prohibitive as the number of variables grows. For example, given 100 binary variables ${\displaystyle X_{1},\ldots ,X_{100}}$, computing a single marginal ${\displaystyle X_{i}}$ using ${\displaystyle p}$ and the above formula would involve summing over ${\displaystyle 2^{99}\approx 6.34\times 10^{29}}$ possible values for ${\displaystyle \mathbf {x} '}$. If it is known that the probability mass function ${\displaystyle p}$ factors in a convenient way, belief propagation allows the marginals to be computed much more efficiently.

Variants of the belief propagation algorithm exist for several types of graphical models (Bayesian networks and Markov random fields in particular). We describe here the variant that operates on a factor graph. A factor graph is a bipartite graph containing nodes corresponding to variables ${\displaystyle V}$ and factors ${\displaystyle F}$, with edges between variables and the factors in which they appear. We can write the joint mass function:

where ${\displaystyle \mathbf {x} _{a}}$ is the vector of neighboring variable nodes to the factor node ${\displaystyle a}$. Any Bayesian network or Markov random field can be represented as a factor graph by using a factor for each node with its parents or a factor for each node with its neighborhood respectively.

The algorithm works by passing real valued functions called messages along the edges between the nodes. More precisely, if ${\displaystyle v}$ is a variable node and ${\displaystyle a}$ is a factor node connected to ${\displaystyle v}$ in the factor graph, then the messages ${\displaystyle \mu _{v\to a}}$ from ${\displaystyle v}$ to ${\displaystyle a}$ and the messages ${\displaystyle \mu _{a\to v}}$ from ${\displaystyle a}$ to ${\displaystyle v}$ are real-valued functions ${\displaystyle \mu _{v\to a},\mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R} }$, whose domain is the set of values that can be taken by the random variable associated with ${\displaystyle v}$, denoted ${\displaystyle \operatorname {Dom} (v)}$. These messages contain the "influence" that one variable exerts on another. The messages are computed differently depending on whether the node receiving the message is a variable node or a factor node. Keeping the same notation: