Variable EliminationOpen in Colab

Variable Elimination

Variable elimination is the workhorse algorithm for exact inference in Bayesian Networks. Given a query like P(Disease∣Symptoms)P(\text{Disease} \mid \text{Symptoms}), it computes the answer by summing out every non-query variable, but does so factor by factor, in a chosen order, instead of building the full joint table.

Why not sum the full joint distribution

The naive approach (build the full joint P(X1,…,Xn)P(X_1, \ldots, X_n) and marginalize) costs O(2n)O(2^n) for nn binary variables. Variable elimination exploits the network's factorization to keep intermediate tables small: it interleaves multiplication and summation so no factor ever has to mention more variables than necessary.

The variable elimination procedure

To compute P(Q∣E=e)P(Q \mid E = e) (query QQ, evidence EE):

  1. Set evidence: for each observed variable Ei=eiE_i = e_i, replace its CPT with a factor restricted to Ei=eiE_i = e_i.
  2. Choose an elimination ordering Z1,Z2,…,ZkZ_1, Z_2, \ldots, Z_k over the hidden variables (all except QQ). Good orderings keep intermediate factors small.
  3. For each ZiZ_i in order: a. Collect all factors that mention ZiZ_i. b. Multiply them into one big factor: fnew(…)=∏jfj(…)f_\text{new}(\ldots) = \prod_j f_j(\ldots). c. Sum out ZiZ_i: g(…)=∑zifnew(…,Zi=zi)g(\ldots) = \sum_{z_i} f_\text{new}(\ldots, Z_i = z_i). Replace the original factors with gg.
  4. Multiply remaining factors and normalize to get P(Q∣E=e)P(Q \mid E = e).

A worked example

Network: Rain → Sprinkler, Rain → Wet, Sprinkler → Wet. Query: P(Wet∣Rain=T)P(\text{Wet} \mid \text{Rain=T}).

Step 1: set evidence. Restrict every factor that mentions Rain to Rain = T:

  • P(Rain)P(\text{Rain}) → constant P(Rain=T)=0.2P(\text{Rain=T}) = 0.2
  • P(Sprinkler∣Rain)P(\text{Sprinkler} \mid \text{Rain}) → P(Sprinkler∣Rain=T)P(\text{Sprinkler} \mid \text{Rain=T}), a factor over Sprinkler only
  • P(Wet∣Sprinkler,Rain)P(\text{Wet} \mid \text{Sprinkler}, \text{Rain}) → P(Wet∣Sprinkler,Rain=T)P(\text{Wet} \mid \text{Sprinkler}, \text{Rain=T}), a factor over (Wet, Sprinkler)

Step 2: ordering. Only one hidden variable: Sprinkler.

Step 3: eliminate Sprinkler. Using CPT values: P(S=T∣R=T)=0.01P(S=T \mid R=T) = 0.01, P(W=T∣S=T,R=T)=0.99P(W=T \mid S=T, R=T) = 0.99, P(W=T∣S=F,R=T)=0.80P(W=T \mid S=F, R=T) = 0.80. Multiply the two factors that mention Sprinkler, then sum over its two values:

g(Wet=T)=∑s∈{T,F}P(s∣R=T)  P(W=T∣s,R=T)g(\text{Wet=T}) = \sum_{s \in \{T, F\}} P(s \mid R=T)\; P(W=T \mid s, R=T) =0.01×0.99+0.99×0.80=0.0099+0.7920=0.8019= 0.01 \times 0.99 + 0.99 \times 0.80 = 0.0099 + 0.7920 = 0.8019

Step 4: normalize. Compute g(Wet=F)=0.01×0.01+0.99×0.20=0.1981g(\text{Wet=F}) = 0.01 \times 0.01 + 0.99 \times 0.20 = 0.1981. These sum to 1.0001.000, so no further normalization is needed: P(Wet=T∣Rain=T)≈0.802P(\text{Wet=T} \mid \text{Rain=T}) \approx 0.802. Even with the sprinkler being off 99% of the time when it rains, the rain itself makes the grass likely wet.

Watch it run

The example above has only one hidden variable, so there is no ordering to get wrong. Add a Slippery node (Wet → Slippery) and query P(Slippery)P(\text{Slippery}) with nothing observed, and all three of Rain, Sprinkler and Wet must be summed out — now the order matters. The CPTs are the canonical sprinkler numbers, extended with P(S=T∣R=F)=0.4P(S{=}T \mid R{=}F) = 0.4, P(W=T∣S=T,R=F)=0.9P(W{=}T \mid S{=}T, R{=}F) = 0.9, P(W=T∣S=F,R=F)=0P(W{=}T \mid S{=}F, R{=}F) = 0 and P(L=T∣W=T)=0.7P(L{=}T \mid W{=}T) = 0.7:

Variable elimination — multiply, sum out, and why the order is the whole game

1/12

The sprinkler network with one node added: Rain → Sprinkler, Rain → Wet, Sprinkler → Wet, Wet → Slippery. The query is P(Slippery) with nothing observed, so Rain, Sprinkler and Wet all have to be summed out. Building the full joint would mean a 16-row table; variable elimination never builds it.

python
1def eliminate(factors, query, order):
2 for Z in order:
3 # every factor that mentions Z
4 rel = [f for f in factors if Z in f.vars]
5 factors = [f for f in factors
6 if Z not in f.vars]
7 prod = reduce(multiply, rel)
8 factors.append(sum_out(prod, Z))
9 result = reduce(multiply, factors)
10 return normalize(result)
11
12def multiply(f, g):
13 vars = union(f.vars, g.vars)
14 return Factor(vars, [f[a] * g[a]
15 for a in assignments(vars)])
16
17def sum_out(f, Z):
18 vars = [v for v in f.vars if v != Z]
19 return Factor(vars, [sum(f[a + {Z: z}]
20 for z in (T, F))
21 for a in assignments(vars)])
state
P(R) — 1 var, 2 rows
Rvalue
T0.2000
F0.8000
P(S|R) — 2 vars, 4 rows
RSvalue
TT0.0100
TF0.9900
FT0.4000
FF0.6000
P(W|S,R) — 3 vars, 8 rows
SRWvalue
TTT0.9900
TTF0.0100
TFT0.9000
TFF0.1000
FTT0.8000
FTF0.2000
FFT0.0000
FFF1.0000
P(L|W) — 2 vars, 4 rows
WLvalue
TT0.7000
TF0.3000
FT0.0000
FF1.0000

Index convention: T rows first. P(W=T | S=F, R=F) = 0 — with neither rain nor sprinkler the grass is dry.

Exact inference on a four-node Bayesian network, factor by factor: collect the factors mentioning a variable, multiply them, sum the variable out, repeat. Watch the intermediate tables grow and shrink — that size is the entire cost of the algorithm. The final step re-runs the same query under a worse elimination order and gets a bit-identical answer from a table twice as large, which is why elimination-order heuristics exist at all.

What to notice as you step:

  • Only the factors mentioning the eliminated variable take part. Everything else is left alone. That locality is the whole saving over building the joint.
  • Watch the row counts, not the probabilities. The cost of the algorithm is the size of the largest intermediate factor, and you can see it swell on the multiply and shrink on the sum-out.
  • The last step re-runs the same query in a worse order. The answer is identical to the last digit — variable elimination is exact under any ordering, but the largest table doubles. On four binary variables that is a shrug; the same effect on a real network is the difference between seconds and never finishing, which is what the next section is about.

Complexity and the elimination order

The cost is exponential in the size of the largest intermediate factor, which depends on the elimination order. The best achievable maximum factor size (minus one) is the graph's treewidth, so variable elimination is tractable for tree-like networks and expensive for densely connected ones.

Choosing an order

Finding the optimal elimination order is NP-hard, but greedy heuristics work well in practice: at each step, eliminate the variable that creates the smallest new factor (min-fill or min-degree heuristics).

For graphs where exact inference is intractable, switch to approximate methods — sampling (likelihood weighting, Gibbs/MCMC) or loopy belief propagation.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Referenced by
Variable EliminationBayesian NetworksHidden Markov Models