Exact Inference: Variable Elimination

Last lesson left the Bayes net storing the joint distribution — one probability for every complete combination of values the variables can take — in a compact form. It also left a warning. Querying the net, as in “given the alarm, what is the chance of a burglary?”, means summing that joint over every variable you did not happen to observe, and on a big net that sum has exponentially many terms.

Variable elimination is the routine that performs the sum exactly — no sampling, no approximation. It sweeps the unwanted variables out one at a time and, crucially, never writes down the whole joint in the first place.

It is slower than sampling on giant networks, but precise. For exam-sized nets of two to four nodes it is the right tool, and a single elimination step is usually all GATE asks you to perform. The same sum-product engine runs inside probabilistic-programming libraries and diagnosis systems whenever an exact answer is affordable — so the hand-trace you practise here is a scaled-down version of what those tools do.

The procedure

To compute P(Query | Evidence):

1. Write the joint as a product of factors taken from the CPTs — the conditional probability tables the net already stores, one per node, each listing that node’s probabilities given its parents. A “factor” is just such a table treated as a function you can multiply and sum over.
2. Fix the evidence variables to their observed values.
3. Pick a hidden (non-query, non-evidence) variable and sum it out: replace every factor that contains it with one factor that is the sum over that variable’s values.
4. Repeat until only the query variable remains.
5. Normalise so the surviving distribution sums to 1.

The answer is exact (up to floating-point error). That is the headline property — VE is not a sampling method.

But if VE computes the very same sum that brute force does, why is it any faster? This is the question that makes the whole procedure click, and the answer is a single line of school algebra: you can pull a factor outside a sum that does not mention it. Written out for the chain A → B → C, the brute-force sum is

Σ_A Σ_B P(A) · P(B|A) · P(C|B)

and since P(C|B) contains no A, the inner sum can slide past it:

Σ_B P(C|B) · [ Σ_A P(A) · P(B|A) ]

The bracketed part is a small table over B alone. Compute it once, reuse it for every value of C, and the work drops. Brute force multiplies out every combination and then adds; VE adds as early as it can and keeps each intermediate table as narrow as possible. Same arithmetic, different order — and the order is the entire saving.

Worked example — eliminate one variable

A chain A → B → C. Given P(A=1) = 0.5, P(B=1 | A=1) = 0.7, P(B=1 | A=0) = 0.2, P(C=1 | B=1) = 0.9, P(C=1 | B=0) = 0.4. Find P(C=1) by summing out A and B.

The factorisation is P(A, B, C) = P(A) · P(B | A) · P(C | B), and we want P(C=1) = Σ_A Σ_B P(A) · P(B | A) · P(C=1 | B). Sum the variables out one at a time.

Step 1 — eliminate A. Collapse P(A) · P(B | A) into a single factor over B:

P(B=1) = P(B=1 | A=1)·P(A=1) + P(B=1 | A=0)·P(A=0)
       = 0.7 · 0.5            + 0.2 · 0.5
       = 0.35                 + 0.10              =  0.45

P(B=0) = 1 − 0.45  =  0.55

Step 2 — eliminate B. Combine that new P(B) with P(C=1 | B):

P(C=1) = P(C=1 | B=1)·P(B=1) + P(C=1 | B=0)·P(B=0)
       = 0.9 · 0.45           + 0.4 · 0.55
       = 0.405                + 0.220             =  0.625

So P(C=1) = 0.625 — exactly, no sampling involved, and above 0.5 just as the leaning CPTs suggested. Each elimination step is one weighted sum over the values of the variable being removed, and you never built the full three-variable joint.

How GATE asks this

Two patterns. MSQ: which of the listed methods compute exact posteriors — the probability of the query after the evidence has been folded in — on a Bayes net? Variable elimination yes; enumeration of the joint yes; rejection / likelihood-weighting / Gibbs no — they are sampling. NAT: perform one elimination step on a 3-node chain or v-structure and report the marginal. GATE DA 2025 ran an MSQ asking exactly this classification.

In one breath

Variable elimination computes an exact posterior on a Bayes net by writing the joint as a product of CPT factors, fixing the evidence, then summing out each hidden variable one at a time (replacing every factor that mentions it with the sum-over-its-values), and finally normalising — so it never expands the full 2ⁿ joint, the answer is exact up to floating-point, and it sits firmly on the exact side of the ledger (with full enumeration) opposite the approximate sampling methods.

Practice

A question to carry forward

Variable elimination is exact, and on a small net it is fast. But its cost has a hidden teeth. As you sum out variables on a large, tangled network, the intermediate factors can swell — combining a variable’s many neighbours into ever-wider tables — until the careful summing-out is no cheaper than the full joint it set out to avoid. On a dense net of fifty variables, “exact” can mean “will not finish this century.”

So when exactness becomes unaffordable, you strike a different bargain: give up the guarantee of the true answer in exchange for a good enough one, fast. Instead of computing the probability, you estimate it — by conjuring up thousands of random scenarios consistent with the net and simply counting how often the thing you care about happens. Here is the thread onward, and the chapter’s last step: how do you draw such samples from a Bayes net, what three classic recipes turn that counting into a posterior estimate — and what is the price you always pay for trading exact arithmetic for random draws?