Questions: Belief Propagation Algorithm

Question 1

You run loopy belief propagation on a factor graph with cycles and it converges. What can you say about the resulting marginal probabilities?

• A. They are exact, because convergence proves the algorithm found the true marginals
• B. They are undefined, because BP cannot converge on any loopy graph
• C. They are approximate, because cycles allow information to circulate and be counted more than once
• D. They are exact only for variables not involved in any cycle

Answer: (C)

Convergence in loopy BP does not guarantee correctness. On a graph with cycles, a message traveling around a loop eventually returns to its origin, causing information to be double-counted. The algorithm treats the information as independent when it is not. The result is an approximation — often a very good one in practice (as in LDPC decoding), but not exact. Only on tree-structured graphs, where every path between nodes is unique, does BP compute exact marginals.

Question 2

On a tree-structured factor graph, why does belief propagation compute exact marginals?

• A. Tree graphs have fewer variables, so the exact computation is tractable
• B. Every path between any two nodes is unique, so messages carry truly independent information with no double-counting
• C. Factor graphs on trees have no cycles, so all variables are independent
• D. Dynamic programming guarantees exact results on any acyclic computation graph

Answer: (B)

The key is message independence. In a tree, there is exactly one path between any two nodes. When a variable x sends a message toward a factor f, that message summarizes everything 'behind' x — none of which has already influenced f through another path. Because there are no loops, information cannot circulate back. This is precisely the condition that makes the sum-product decomposition exact. Option C is wrong: variables in a tree-shaped factor graph can be highly dependent — the graph structure captures their joint distribution; 'no cycles' enables exact inference, not independence.

Question 3

Loopy belief propagation is very likely to converge on any factor graph if run for sufficiently many iterations.

• T. True
• F. False

Answer: False

Convergence is not guaranteed for loopy graphs. On graphs with short, tight cycles (especially small-diameter graphs with dense connections), messages can oscillate indefinitely. Techniques like message damping (mixing new messages with previous ones) can improve convergence behavior, but there is no general guarantee. When BP does fail to converge, practitioners typically detect this by monitoring message changes and either use damping, different scheduling, or a variational inference method instead.

Question 4

In belief propagation, a message from variable node x to factor node f is constructed by combining information from all of x's neighboring factors except f itself.

• T. True
• F. False

Answer: True

This exclusion is the core design decision in BP. If x included f's own message in what it sends back to f, the same information would flow in a loop and be double-counted. By excluding f, each message represents genuinely new information from x's perspective — everything x knows from all other sources. On a tree, this means every message is built from independent evidence, guaranteeing exactness. On a loopy graph, independence breaks down as information can reach x via f through roundabout paths.

Question 5

Explain why belief propagation is exact on trees but only approximate on loopy graphs, using the concept of message independence.

Model answer: On a tree, every path between two nodes is unique, so the messages arriving at any variable from different directions are based on completely independent subsets of the graph. When BP combines these messages to compute a belief, it is correctly weighting non-overlapping evidence. On a loopy graph, cycles create multiple paths between nodes, allowing the same piece of evidence to travel around a loop and arrive at a variable multiple times via different routes — once directly and once (or more times) via the cycle. BP has no mechanism to detect this; it counts the repeated information as if it were independent, producing incorrect (biased toward overconfidence) marginals.

This distinction is why BP is also called 'sum-product on a tree' in the exact case. The loopy case is an approximation to the Bethe free energy minimization in statistical physics, which explains why the approximation can be systematically analyzed and why it works well when cycles are long (information correlations decay over long paths). Short, dense cycles are where loopy BP breaks down most severely.