Simple Algorithm
Artificial Intelligence · Deep Layer · 30 min

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?

DerivationProof of 3: an approximate posterior finds satisfying assignments
  1. P(u∣Am=true)=[u satisfies ϕ]#SAT(ϕ)P(\mathbf u\mid A_m=\text{true})=\frac{[\mathbf u\ \text{satisfies}\ \phi]}{\#\mathrm{SAT}(\phi)}

    Take the 3-SAT network of the Hidden Layer lesson, with evidence Am=trueA_m=\text{true}. If the formula ϕ\phi is satisfiable, the posterior over the variable nodes is uniform on its satisfying assignments:

  2. p^≥12 ⇒ p≥12−ε>0,p^<12 ⇒ 1−p>12−ε>0\hat p\ge\tfrac12\ \Rightarrow\ p\ge\tfrac12-\varepsilon>0,\qquad \hat p<\tfrac12\ \Rightarrow\ 1-p>\tfrac12-\varepsilon>0

    Fix the variables one at a time. With the values chosen so far added as evidence, ask the approximator for p^≈p=P(Ui=true∣Am,u<i)\hat p\approx p=P(U_i=\text{true}\mid A_m,u_{<i}) and set ui=trueu_i=\text{true} exactly when p^≥12\hat p\ge\tfrac12. Since ε<12\varepsilon<\tfrac12:

  3. 3-SAT ≤p ε-absolute posterior approximation,ε<12\text{3-SAT}\ \le_p\ \varepsilon\text{-absolute posterior approximation},\qquad\varepsilon<\tfrac12

    Either way the chosen value has positive posterior probability, so the partial assignment still extends to a satisfying one. After nn calls, check the assignment: it satisfies ϕ\phi whenever ϕ\phi 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 sij=ci∩cjs_{ij}=c_i\cap c_j:

δi→j(sij)=∑ci∖sijψi(ci)∏k∈N(i)∖{j}δk→i(ski),βi(ci)=ψi(ci)∏k∈N(i)δk→i(ski) ∝ P(ci,e).\delta_{i\to j}(s_{ij})=\sum_{c_i\setminus s_{ij}}\psi_i(c_i)\prod_{k\in N(i)\setminus\{j\}}\delta_{k\to i}(s_{ki}),\qquad \beta_i(c_i)=\psi_i(c_i)\prod_{k\in N(i)}\delta_{k\to i}(s_{ki})\ \propto\ P(c_i,\mathbf e).

One pass toward a root and one pass back compute each of the 2(m−1)2(m-1) messages of an mm-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.

Check your understanding

An Ising model on a k×kk\times k grid of binary variables, with arbitrary pairwise potentials. How does the cost of exact inference by the best elimination ordering grow?

  1. Exponentially in k2k^2, the number of variables
  2. Polynomially, because every node has at most four neighbors
  3. Linearly, because the grid is planar
  4. Exponentially in kk, the side length, because the treewidth is kk
Show the answer

D. Exponentially in kk, the side length, because the treewidth is kk

Eliminating row by row keeps a frontier of about kk variables, so factors have about 2k+12^{k+1} entries and the cost is roughly k2 2kk^2\,2^{k}. No ordering does better than treewidth kk. A 20×2020\times20 grid is easy; a 100×100100\times100 grid is hopeless for exact methods.

Belief propagation: exact on trees, approximate on loops

Write the distribution as a factor graph, P(x)∝∏afa(xa)P(\mathbf x)\propto\prod_af_a(\mathbf x_a), with an edge between each factor aa and each variable ii in its scope. Sum-product belief propagation passes messages along the edges:

mi→a(xi)=∏b∈N(i)∖amb→i(xi),ma→i(xi)=∑xa∖xifa(xa)∏j∈N(a)∖imj→a(xj),m_{i\to a}(x_i)=\prod_{b\in N(i)\setminus a}m_{b\to i}(x_i),\qquad m_{a\to i}(x_i)=\sum_{\mathbf x_a\setminus x_i}f_a(\mathbf x_a)\prod_{j\in N(a)\setminus i}m_{j\to a}(x_j),

and reads off beliefs bi(xi)∝∏a∈N(i)ma→i(xi)b_i(x_i)\propto\prod_{a\in N(i)}m_{a\to i}(x_i). On a polytree, this is Pearl's (1988) algorithm.

DerivationBP is exact on trees
  1. P(xi)∝∑x∖xi∏bfb(xb)=∏a∈N(i)[∑xTa∖xi ∏b∈Tafb(xb)]P(x_i)\propto\sum_{\mathbf x\setminus x_i}\prod_bf_b(\mathbf x_b)=\prod_{a\in N(i)}\Big[\sum_{\mathbf x_{T_a}\setminus x_i}\ \prod_{b\in T_a}f_b(\mathbf x_b)\Big]

    Root the tree at xix_i. Removing xix_i splits the tree into subtrees TaT_a, one behind each neighboring factor aa, which share no variables, so the distributive law splits the sum:

  2. [⋯]=∑xa∖xifa(xa)∏j∈N(a)∖imj→a(xj)=ma→i(xi)\Big[\cdots\Big]=\sum_{\mathbf x_a\setminus x_i}f_a(\mathbf x_a)\prod_{j\in N(a)\setminus i}m_{j\to a}(x_j)=m_{a\to i}(x_i)

    By induction on the height of the subtree, each bracket equals ma→i(xi)m_{a\to i}(x_i): it splits again over aa's other neighbors jj, and each of those contributes the sum over its own subtree, which is mj→a(xj)m_{j\to a}(x_j).

  3. bi(xi)∝∏a∈N(i)ma→i(xi)=P(xi)b_i(x_i)\propto\prod_{a\in N(i)}m_{a\to i}(x_i)=P(x_i)

    A sweep from the leaves to a root and back computes every message once, 2∣E∣2|E| 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 {ba,bi}\{b_a,b_i\}, where did_i is the number of factors that contain xix_i:

FBethe(b)=∑a∑xaba(xa)ln⁡ba(xa)fa(xa)−∑i(di−1)∑xibi(xi)ln⁡bi(xi).F_{\mathrm{Bethe}}(b)=\sum_a\sum_{\mathbf x_a}b_a(\mathbf x_a)\ln\frac{b_a(\mathbf x_a)}{f_a(\mathbf x_a)}-\sum_i(d_i-1)\sum_{x_i}b_i(x_i)\ln b_i(x_i).

On a tree, P(x)=∏aba(xa)∏ibi(xi)1−diP(\mathbf x)=\prod_ab_a(\mathbf x_a)\prod_ib_i(x_i)^{1-d_i} holds exactly, and the minimum of FBetheF_{\mathrm{Bethe}} is −ln⁡Z-\ln Z. 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 xk∼q\mathbf x_k\sim q from a proposal, weight by wk=p~(xk)/q(xk)w_k=\tilde p(\mathbf x_k)/q(\mathbf x_k) where p~(x)=P(x,e)\tilde p(\mathbf x)=P(\mathbf x,\mathbf e) is the unnormalized target, and use the self-normalized estimate μ^=∑kwkf(xk)/∑kwk\hat\mu=\sum_kw_kf(\mathbf x_k)/\sum_kw_k. It is consistent, and its accuracy is governed by how far qq is from the target p=P(⋅∣e)p=P(\cdot\mid\mathbf e). The effective sample size measures it:

ESS=(∑kwk)2∑kwk2 ≈ N1+χ2(p ∥ q),χ2(p ∥ q)=Var⁡q[p(x)q(x)].\mathrm{ESS}=\frac{\big(\sum_kw_k\big)^2}{\sum_kw_k^2}\ \approx\ \frac{N}{1+\chi^2(p\,\|\,q)},\qquad \chi^2(p\,\|\,q)=\Var_q\Big[\frac{p(\mathbf x)}{q(\mathbf x)}\Big].
Predict before you look

Without evidence, you estimate a marginal P(X=x)P(X=x) by forward sampling and want an error of at most 0.010.01 with probability 95%95\%. By Hoeffding's bound N≥ln⁡(2/δ)/(2ε2)N\ge\ln(2/\delta)/(2\varepsilon^2), how many thousand samples suffice?

Show the answer

18 thousand

ln⁡(2/0.05)=ln⁡40≈3.69\ln(2/0.05)=\ln40\approx3.69, and 3.69/(2×10−4)≈18,4003.69/(2\times10^{-4})\approx18{,}400. For a relative error of 10% on a small probability pp, the Chernoff bound asks for about 3ln⁡(2/δ)/(ε2p)3\ln(2/\delta)/(\varepsilon^2p) samples instead: for P(j,m)=0.00208P(j,m)=0.00208 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 P(x∣e)P(\mathbf x\mid\mathbf e) 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 1−η1-\eta switch between their two modes only about once every 1/η1/\eta 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 ε<12\varepsilon<\tfrac12 is NP-hard. Without evidence, forward sampling needs only ln⁡(2/δ)/(2ε2)\ln(2/\delta)/(2\varepsilon^2) samples.
  • Variable elimination and junction trees cost O(n d tw+1)\order{n\,d^{\,\mathrm{tw}+1}} 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 eDKL(p∥q)e^{\KL(p\|q)} samples, and the effective sample size (∑w)2/∑w2(\sum w)^2/\sum w^2 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.

Question 1

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?

  1. Estimating P(X=x∣e)P(X=x\mid\mathbf e) within ±0.1\pm0.1 for arbitrary evidence
  2. Estimating P(X=x)P(X=x) within a factor of 2
  3. Estimating P(X=x)P(X=x) within ±0.01\pm0.01 with probability 95%, with no evidence
  4. Deciding whether P(X=x)>0P(X=x)>0
Show the answer

C. Estimating P(X=x)P(X=x) within ±0.01\pm0.01 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 ε<12\varepsilon<\tfrac12 is NP-hard, and any relative approximation decides the NP-complete question P(X=x)>0P(X=x)>0.

Question 2

What does calibrating a junction tree (one inward and one outward pass of messages) give you?

  1. Only the marginal of the root clique
  2. The joint marginal of every clique, at roughly twice the cost of one variable elimination
  3. Approximate marginals whose error depends on the number of cycles
  4. 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 βi∝P(ci,e)\beta_i\propto P(c_i,\mathbf e), exactly. The tree is built from a triangulation, so there are no cycles left to cause error.

Question 3

Which statement about loopy belief propagation is correct?

  1. It always converges, but to approximate marginals
  2. Its fixed points are exact marginals whenever it converges
  3. Its fixed points are stationary points of the Bethe free energy, which is exact on trees
  4. 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.

Question 4

Four importance samples have weights 1,1,1,971,1,1,97. What is their effective sample size?

  1. 4
  2. About 1.06
  3. About 2
  4. 25
Show the answer

B. About 1.06

ESS=(1+1+1+97)2/(1+1+1+972)=10,000/9,412≈1.06\mathrm{ESS}=(1+1+1+97)^2/(1+1+1+97^2)=10{,}000/9{,}412\approx1.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.