Approximate Inference: Sampling

Last lesson left variable elimination exact but fragile — on a big tangled network its intermediate factors swell until “exact” means “never finishes.” When that happens you strike a different bargain: give up the guarantee of the true answer for a good enough one, fast. Stop computing and start sampling — conjure up a pile of full assignments drawn from the net’s own distribution, count what fraction match your query, and report that fraction as the answer.

The three classic recipes — rejection sampling, likelihood weighting, and Gibbs sampling — all do this, with different trade-offs. The headline you must carry into GATE: all three are approximate. They edge closer to the true posterior as you draw more samples, but for any finite sample size they are estimates with wobble. That very trade — accept approximation to stay tractable — is why modern Bayesian ML leans on sampling: MCMC and its relatives are what tools like Stan and PyMC run to fit models far too large for exact inference.

The three methods, at a glance

Rejection sampling. Draw a full sample from the prior — sample each node in topological order from its CPT. If the sample’s evidence values match the observed ones, keep it; otherwise throw it away, and estimate the posterior from the survivors. Simple, but wasteful: when the evidence is rare, almost every sample is discarded.

Likelihood weighting. Fix the evidence variables to their observed values (do not sample them), sample the rest from their CPTs, and weight each sample by the product of the evidence-node CPT entries: w = ∏ᵢ P(Eᵢ = eᵢ | Parents(Eᵢ)). No sample is wasted, but the variance grows when you condition on many evidence nodes.

Gibbs sampling (MCMC). Start anywhere consistent with the evidence, then repeatedly pick a non-evidence variable and resample it given the current values of all the others (its Markov blanket). The chain converges to the true posterior in the limit. It handles rare evidence well, but needs a burn-in period first.

Worked example — one likelihood-weighting weight

A 3-node net A → B → E. CPTs: P(A=1) = 0.5, P(B=1 | A=1) = 0.6, P(B=1 | A=0) = 0.2, P(E=T | B=1) = 0.9, P(E=T | B=0) = 0.3. The evidence is E = T. We sample A = T from P(A), then B = F from P(B | A=T). What is the weight of this sample?

In likelihood weighting the evidence is fixed — we do not sample it. The weight is the product of the CPT entries for each evidence node, evaluated at its observed value given the parents this sample chose. Here only E is evidence, with parent B, and the sample set B = F, so:

w = P(E = T | B = F) = 0.3

That is the whole calculation — one factor per evidence node, and the sampled value of A never enters it. The sample {A=T, B=F, E=T} is recorded with weight 0.3, contributing 0.3 to the tally for any query involving A=T, B=F. Posterior estimates then use the weighted counts:

P(Q = q | E = e)  ≈   Σ samples where Q=q  w_sample
                      ──────────────────────────────
                          Σ all samples  w_sample

This “weight = product of evidence-CPT entries” pattern is the GATE DA 2024 Q32 shape.

How GATE asks this

Two recurring patterns. MCQ: a list of methods to classify as exact or approximate — variable elimination is the only exact one; rejection, likelihood weighting, and Gibbs are approximate. MSQ: properties of the sampling methods — rejection wastes samples when evidence is rare; likelihood weighting weights by the evidence-CPT product and wastes none; Gibbs resamples one variable at a time. GATE DA 2025 and 2026 both ran this MCQ.

In one breath

When exact inference is too costly, sampling estimates a Bayes-net posterior by drawing many assignments and counting: rejection sampling samples from the prior and discards mismatches (wasteful on rare evidence), likelihood weighting fixes the evidence and weights each kept sample by ∏ P(eᵢ | Parents(Eᵢ)) (no waste, variance rises with more evidence), and Gibbs sampling is an MCMC method that resamples one non-evidence variable at a time given the rest (needs burn-in) — and all three are approximate, converging to the truth only in the limit, unlike the exact variable elimination.

Practice

A question to carry forward

That closes the Artificial Intelligence chapter — and with it the deep technical spine of the whole syllabus. Look at the ground covered: probability, linear algebra, calculus, programming and data structures, databases, the full sweep of machine learning, and now search, logic, and probabilistic reasoning. That is the 85-mark core, and you have walked every inch of it.

But the GATE paper carries 15 more marks that test none of this machinery — not one Bayes net, not a single eigenvalue. They test plain reading, sound arithmetic, and everyday reasoning: the General Aptitude section every candidate sits, regardless of stream. And here is the quiet truth about those marks — they are the cheapest on the entire paper to win, and the cheapest to throw away. A topper and a borderline candidate often differ by exactly these fifteen. Here is the thread onward into the final chapters: how is that section built, which of its pieces give the most marks per hour of preparation, and how do you stop treating it as an afterthought?