Exact & Approximate Inference
Variable elimination, belief propagation and MCMC.
Exact inference in Bayesian networks is #P-hard, and once there is evidence even approximating a posterior to within ±0.4 is NP-hard. Yet inference runs every day in diagnosis, error-correcting codes and speech recognition. The way out is structure: junction trees make exact inference exponential only in the treewidth, belief propagation is exact on trees and often accurate beyond them, and Monte Carlo methods come with error bars, if you know where to look for them.
What you’ll learn
- State the hardness results for exact and approximate inference, prove that absolute-error approximation with evidence is NP-hard, and identify the regimes that are easy.
- Relate variable elimination to triangulation and treewidth, and compute all clique marginals with a calibrated junction tree.
- Derive sum-product belief propagation, prove that it is exact on trees, and characterize loopy BP's fixed points through the Bethe free energy.
- Bound the sample sizes of Monte Carlo inference with Hoeffding and Chernoff bounds, the effective sample size and the Chatterjee–Diaconis criterion, and explain when Gibbs sampling mixes slowly.
How hard is inference?
Take the 3-SAT network of the Hidden Layer lesson, with evidence . If the formula is satisfiable, the posterior over the variable nodes is uniform on its satisfying assignments:
Fix the variables one at a time. With the values chosen so far added as evidence, ask the approximator for and set exactly when . Since :
Either way the chosen value has positive posterior probability, so the partial assignment still extends to a satisfying one. After calls, check the assignment: it satisfies whenever is satisfiable. ∎
Tractability therefore has to come from somewhere specific: low treewidth, which governs variable elimination (next step); local structure, such as determinism and context-specific independence, exploited by compiling the network into an arithmetic circuit (Darwiche, 2003) or by weighted model counting with SAT technology (Chavira & Darwiche, 2008); or approximation with guarantees that hold for the class of models at hand.
Treewidth and junction trees
VE answers one query. The junction tree algorithm answers all single-clique queries at once: triangulate the moral graph, arrange its maximal cliques into a tree with the running-intersection property, assign each CPT (restricted to the evidence) to a clique that contains its family, and pass messages over the separators :
One pass toward a root and one pass back compute each of the messages of an -clique tree once, so every clique marginal costs about twice one run of VE (Lauritzen & Spiegelhalter, 1988). Treewidth also appears to be a genuine barrier rather than an artifact of one algorithm: Chandrasekaran, Srebro & Harsha (2008) showed, under complexity-theoretic assumptions, that low treewidth is the only graph property that guarantees tractable inference for arbitrary potentials.
An Ising model on a grid of binary variables, with arbitrary pairwise potentials. How does the cost of exact inference by the best elimination ordering grow?
- Exponentially in , the number of variables
- Polynomially, because every node has at most four neighbors
- Linearly, because the grid is planar
- Exponentially in , the side length, because the treewidth is
Show the answer
D. Exponentially in , the side length, because the treewidth is
Eliminating row by row keeps a frontier of about variables, so factors have about entries and the cost is roughly . No ordering does better than treewidth . A grid is easy; a grid is hopeless for exact methods.
Belief propagation: exact on trees, approximate on loops
Write the distribution as a factor graph, , with an edge between each factor and each variable in its scope. Sum-product belief propagation passes messages along the edges:
and reads off beliefs . On a polytree, this is Pearl's (1988) algorithm.
Root the tree at . Removing splits the tree into subtrees , one behind each neighboring factor , which share no variables, so the distributive law splits the sum:
By induction on the height of the subtree, each bracket equals : it splits again over 's other neighbors , and each of those contributes the sum over its own subtree, which is .
A sweep from the leaves to a root and back computes every message once, in all, and gives the exact marginal at every variable at once: VE run for all queries simultaneously, with shared work. ∎
On a graph with cycles the same updates can simply be iterated: loopy BP. Nothing guarantees convergence or correctness, yet the method is remarkably useful. Turbo codes and LDPC codes, which come close to channel capacity, are decoded by loopy BP; McEliece, MacKay & Cheng (1998) showed that turbo decoding is an instance of it. Yedidia, Freeman & Weiss (2005) explained its fixed points: they are exactly the stationary points of the Bethe free energy, minimized over locally consistent beliefs , where is the number of factors that contain :
On a tree, holds exactly, and the minimum of is . On loopy graphs it is an approximation, which is why loopy BP double-counts evidence that travels around a cycle. Sufficient conditions for convergence bound the strength of the interactions (Mooij & Kappen, 2007), and in Gaussian models the means are exact whenever BP converges (Weiss & Freeman, 2001).
Monte Carlo with error bars
Likelihood weighting is importance sampling: draw from a proposal, weight by where is the unnormalized target, and use the self-normalized estimate . It is consistent, and its accuracy is governed by how far is from the target . The effective sample size measures it:
Without evidence, you estimate a marginal by forward sampling and want an error of at most with probability . By Hoeffding's bound , how many thousand samples suffice?
Show the answer
18 thousand
, and . For a relative error of 10% on a small probability , the Chernoff bound asks for about samples instead: for in the alarm network, about half a million.
Gibbs sampling, the simplest MCMC method for networks, avoids weights altogether. Each single-site update is a Metropolis–Hastings step that is always accepted, so it leaves invariant; with strictly positive CPTs the chain is irreducible and aperiodic, and ergodic averages converge. The catch is the mixing time. Two binary variables that agree with probability switch between their two modes only about once every sweeps, and for an Ising model on a grid with free boundary conditions, below the critical temperature, the mixing time grows exponentially with the side length. The standard remedies are blocking (resampling strongly coupled variables jointly, for example a whole chain by forward–backward), Rao–Blackwellization (summing some variables out exactly), and tempering.
Key takeaways
- Exact inference is #P-complete; relative approximation is NP-hard; with evidence, absolute approximation within any is NP-hard. Without evidence, forward sampling needs only samples.
- Variable elimination and junction trees cost with the best ordering; a calibrated junction tree yields every clique marginal for about twice the cost of one query.
- Belief propagation is exact on trees, where it is variable elimination for all queries at once. Loopy BP's fixed points are stationary points of the Bethe free energy; it decodes turbo and LDPC codes but can be wrong (78.4% instead of 70.8% on the sprinkler network) or fail to converge.
- Importance sampling needs roughly samples, and the effective sample size diagnoses weight degeneracy. Gibbs sampling is exact in the limit but can mix exponentially slowly when variables are strongly coupled.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Unless NP-hard problems have efficient randomized algorithms, which of these tasks is the only one that can be done in (randomized) polynomial time for every Bayesian network?
- Estimating within for arbitrary evidence
- Estimating within a factor of 2
- Estimating within with probability 95%, with no evidence
- Deciding whether
Show the answer
C. Estimating within with probability 95%, with no evidence
Forward sampling with about 18,400 samples achieves it, whatever the network, by Hoeffding's inequality. With evidence, absolute approximation within any is NP-hard, and any relative approximation decides the NP-complete question .
What does calibrating a junction tree (one inward and one outward pass of messages) give you?
- Only the marginal of the root clique
- The joint marginal of every clique, at roughly twice the cost of one variable elimination
- Approximate marginals whose error depends on the number of cycles
- The most likely joint assignment
Show the answer
B. The joint marginal of every clique, at roughly twice the cost of one variable elimination
After both passes, each clique belief is , exactly. The tree is built from a triangulation, so there are no cycles left to cause error.
Which statement about loopy belief propagation is correct?
- It always converges, but to approximate marginals
- Its fixed points are exact marginals whenever it converges
- Its fixed points are stationary points of the Bethe free energy, which is exact on trees
- It is exact on any graph with a single cycle
Show the answer
C. Its fixed points are stationary points of the Bethe free energy, which is exact on trees
Yedidia, Freeman and Weiss showed the correspondence. On trees the Bethe free energy equals the true free energy, so BP is exact there; on loopy graphs it is an approximation, and convergence itself is not guaranteed.
Four importance samples have weights . What is their effective sample size?
- 4
- About 1.06
- About 2
- 25
Show the answer
B. About 1.06
. One sample carries 97% of the weight, so the estimate is essentially that single draw.
Further reading
- P. Dagum & M. Luby, "Approximating probabilistic inference in Bayesian belief networks is NP-hard," Artificial Intelligence 60(1), 141–153 (1993).
- S. L. Lauritzen & D. J. Spiegelhalter, "Local computations with probabilities on graphical structures and their application to expert systems," Journal of the Royal Statistical Society B 50(2), 157–224 (1988).
- J. S. Yedidia, W. T. Freeman & Y. Weiss, "Constructing free-energy approximations and generalized belief propagation algorithms," IEEE Transactions on Information Theory 51(7), 2282–2312 (2005).
- S. Chatterjee & P. Diaconis, "The sample size required in importance sampling," Annals of Applied Probability 28(2), 1099–1135 (2018).
- D. Koller & N. Friedman, Probabilistic Graphical Models: Principles and Techniques (MIT Press, 2009), chapters 9–12.