Is it the same as backpropagation?

No. Belief propagation performs probabilistic inference; backpropagation computes derivatives through a computational graph.

Can it handle observed variables?

Yes. Evidence is incorporated into the relevant factors or local information before messages are propagated.

Does it return the most likely joint assignment?

The sum-product form computes marginals. Related max-product or max-sum methods address different optimization questions and should be distinguished.

AI Glossary / Graphs and symbolic AI / Advanced

Belief propagation

Definition

Belief propagation is a message-passing method for computing marginal probabilities in a probabilistic graphical model. Nodes or factors exchange compact summaries of information, allowing evidence in one part of the model to affect probability estimates elsewhere.

What it means

A graphical model represents how variables depend on one another. Directly listing every joint possibility can be expensive, while the graph's structure may allow the calculation to be broken into smaller pieces. Belief propagation exploits that structure.

The sum-product form combines local factors and sums over variables that are not needed in a particular message. After receiving the relevant messages, a variable can calculate its marginal distribution, normalized to sum to one.

On suitable tree-structured models, this procedure gives exact marginals. Applied directly to graphs with cycles, it becomes loopy belief propagation, which is generally an approximation and may not converge. “Belief” here refers to computed distributions, not subjective awareness or Dempster - Shafer belief functions.

How it works

Messages summarize the contribution of one region of the graph to the variables shared with another region. In a factor graph, variable-to-factor messages combine incoming information from other adjacent factors. Factor-to-variable messages multiply the local factor by incoming messages and sum over the other variables involved.

The recipient's previous contribution is excluded when constructing a message back toward it. On a tree, information can be collected from the leaves and then distributed outward without endlessly circulating around a cycle. Appropriate scheduling ensures each required message has the information it needs.

Loops complicate this reasoning because information can return through another path. Iterative updates may still produce useful approximations, but convergence and accuracy need assessment. Transforming a general model into a junction tree can support exact inference at the cost of larger grouped factors, potentially making computation expensive.

Three practical examples

A diagnostic model combines observations from conditionally related indicators to estimate the state of an underlying component.
An error-correcting-code decoder uses a factor graph to exchange information about possible transmitted bits and parity constraints.
A structured prediction experiment estimates local label probabilities while accounting for relationships among neighboring variables.

Think of it this way

Think of departments sending summarized evidence through a reporting tree. Each summary represents information from a particular branch, allowing the central calculation to combine branches without reading every raw record repeatedly.

The analogy breaks down if the same report circulates through several departments and returns as apparently independent evidence. Graph cycles require care for a similar reason, although the precise behavior is governed by the model's equations rather than organizational intuition.

Worked example

Combining two conditionally independent observations

Let H mean that an invented component is in a high-load state, with prior probability 0.2. Indicator A reports positive with probability 0.8 under H and 0.1 otherwise. Indicator B reports positive with probability 0.6 under H and 0.2 otherwise. Assume A and B are conditionally independent given H.

When both indicators are positive, their likelihood messages to H are [0.8, 0.1] and [0.6, 0.2] for the H and not-H alternatives. Multiplying with the prior gives unnormalized weights 0.2 × 0.8 × 0.6 = 0.096 and 0.8 × 0.1 × 0.2 = 0.016.

Normalize by their sum, 0.112. The posterior probability of H is 0.096/0.112, approximately 0.857. This small tree calculation illustrates how local messages combine. If the indicators share additional dependence not represented by H, the multiplication would not be justified by the stated model.

Illustrative case study

Fictional case: Larch Monitoring builds a graphical model for equipment status. Its first version uses a tree and matches exact enumeration on small test cases. The team later adds connections representing additional dependencies and keeps the same iterative message-passing interface.

The outputs still look plausible, but some runs fail to stabilize. Developers explicitly label the new procedure as loopy inference, monitor convergence and compare selected small cases with exact results. They review the model and update schedule rather than treating every returned number as an exact posterior.

The lesson is that a graph change can alter the mathematical status of an inference method even when the surrounding software interface remains unchanged.

Common misconceptions and mistakes

Every message is an ordinary normalized probability distribution. Messages may be unnormalized functions whose scale is handled during the calculation.
Belief propagation learns the model automatically. Inference uses specified factors; learning those factors is a separate task.
A loop-free Bayesian graph automatically makes every inference trivial. The relevant graphical structure and factor sizes matter.
Convergence of loopy updates proves exactness. A stable approximation can still differ from the exact marginals.
Message passing always means a graph neural network. Learned neural messages and probabilistic sum-product inference are distinct constructions.

Business use

Belief propagation can make structured uncertainty calculations practical when a model's dependencies support efficient local computation. Its business value comes from using relationships among observations rather than treating every signal independently.

Document the factors, evidence and graph structure, and state whether the reported results are exact under the model or approximate. Test sensitivity to uncertain parameters and inspect convergence for loopy implementations. A precise inference algorithm still depends on a defensible model, including assumptions about which observations share underlying causes.

Check your understanding

Iterative belief propagation on a cyclic graph stops changing after several rounds. Has it necessarily found the exact marginal probabilities?

Answer: No. Convergence alone does not establish exactness. The result remains subject to the properties and limitations of the chosen loopy-inference method.

Related terms

Learn next

Draw one hidden binary variable connected to two observed indicators and calculate the posterior by direct multiplication and normalization. Label the corresponding likelihood messages. Then add a dependency between the indicators and explain why the original tree calculation no longer captures the same joint model.

Binary variable

Sources

Carnegie Mellon probabilistic graphical models course, Exact Inference, explains message passing and tree structure: https://www.cs.cmu.edu/~epxing/Class/10708-19/notes/lecture-04/

The companion variational-inference lecture distinguishes exact tree inference from loopy approximation: https://www.cs.cmu.edu/~epxing/Class/10708-19/notes/lecture-12/

AIMA glossary provides the terminology context: https://github.com/aimacode/aima-glossary/blob/master/glossary.md?plain=1

Previous: Belief function Next: Belief revision