Exact Inference - Enumeration and Variable Elimination

Inference in a Bayesian network means computing the posterior distribution P(X | e) of a query variable X given observed evidence e, summing over the remaining hidden variables Y:

P(X | e) = α P(X, e) = α Σ_y P(X, e, y)

Every term P(X, e, y) is one entry of the full joint distribution, which the network gives as a product of CPT entries.

This lesson uses the sprinkler network from the previous lesson:

Query: the grass is wet. How likely is it that it rained? We want P(R | w).

Inference by enumeration

Write out the sum directly:

P(R, w) = Σ_c Σ_s P(c) P(s | c) P(R | c) P(w | s, R)

For R = true, the four terms are:

So P(r, w) = 0.4581. The same sum for R = false gives P(¬r, w) = 0.2035. Normalising:

P(r | w) = 0.4581 / (0.4581 + 0.2035) = 0.4581 / 0.6616 ≈ 0.692.

Enumeration is simple but wasteful: with n Boolean variables it touches O(2ⁿ) terms, and it recomputes the same sub-products many times. In the table, P(c) P(r | c) is computed twice for each value of C.

Variable elimination

Variable elimination (VE) does the same sum, but pushes each summation as far to the right as possible and stores intermediate results in tables called factors:

P(R, w) = Σ_c P(c) P(R | c) Σ_s P(s | c) P(w | s, R)

Two operations on factors are needed:

• Pointwise product: multiply two factors to get a factor over the union of their variables. For example, f(A, B) × g(B, C) = h(A, B, C), where h(a, b, c) = f(a, b) g(b, c).
• Summing out a variable: add up the entries of a factor over all values of that variable, which removes it. Σ_b h(A, B, C) = h′(A, C).

Step 1: eliminate S. Multiply the factors that mention S, P(S | C) and P(w | S, R), and sum out S:

f₁(C, R) = Σ_s P(s | C) P(w | s, R)

Step 2: eliminate C. Multiply the factors that mention C, P(C), P(R | C) and f₁(C, R), and sum out C:

f₂(R) = Σ_c P(c) P(R | c) f₁(c, R)

• f₂(r) = 0.5 × 0.8 × 0.909 + 0.5 × 0.2 × 0.945 = 0.3636 + 0.0945 = 0.4581
• f₂(¬r) = 0.5 × 0.2 × 0.135 + 0.5 × 0.8 × 0.475 = 0.0135 + 0.19 = 0.2035

Step 3: normalise. P(R | w) = α ⟨0.4581, 0.2035⟩ = ⟨0.692, 0.308⟩, the same answer as enumeration.

from itertools import product

# A factor is (variables, table) where table maps a tuple of values to a number.
def make(vars_, fn):
    return (vars_, {vals: fn(*vals) for vals in product([True, False], repeat=len(vars_))})

def multiply(f, g):
    vs = f[0] + tuple(v for v in g[0] if v not in f[0])
    def val(*vals):
        a = dict(zip(vs, vals))
        return f[1][tuple(a[v] for v in f[0])] * g[1][tuple(a[v] for v in g[0])]
    return make(vs, val)

def sum_out(var, f):
    vs = tuple(v for v in f[0] if v != var)
    def val(*vals):
        a = dict(zip(vs, vals))
        return sum(f[1][tuple(a[v] if v != var else x for v in f[0])] for x in (True, False))
    return make(vs, val)

pS = {True: 0.1, False: 0.5}
pR = {True: 0.8, False: 0.2}
pW = {(True, True): 0.99, (True, False): 0.90, (False, True): 0.90, (False, False): 0.05}

fC = make(("C",), lambda c: 0.5)
fS = make(("S", "C"), lambda s, c: pS[c] if s else 1 - pS[c])
fR = make(("R", "C"), lambda r, c: pR[c] if r else 1 - pR[c])
fW = make(("S", "R"), lambda s, r: pW[(s, r)])          # evidence w = true is already fixed

f1 = sum_out("S", multiply(fS, fW))
print("f1(C, R):", {k: round(v, 4) for k, v in f1[1].items()}, "over", f1[0])
f2 = sum_out("C", multiply(multiply(fC, fR), f1))
print("f2(R):", {k: round(v, 4) for k, v in f2[1].items()})
total = sum(f2[1].values())
print(f"P(w) = {total:.4f}, P(r | w) = {f2[1][(True,)] / total:.4f}")

f1(C, R): {(True, True): 0.909, (True, False): 0.135, (False, True): 0.945, (False, False): 0.475} over ('C', 'R')
f2(R): {(True,): 0.4581, (False,): 0.2035}
P(w) = 0.6616, P(r | w) = 0.6924

Elimination order and complexity

VE gives the same answer for any order of elimination, but the cost depends on the order, because the cost is dominated by the largest factor created along the way (a factor over k Boolean variables has 2ᵏ entries).

• For polytrees (networks with at most one undirected path between any two nodes, i.e. no undirected cycles), VE takes time linear in the size of the network with a good order.
• In general, exact inference in Bayesian networks is NP-hard (it includes propositional satisfiability as a special case). This is why approximate methods (next lesson) are needed for large networks.
• Irrelevant variables can be dropped before starting: any variable that is not an ancestor of the query or evidence variables sums to 1 and can be removed. To compute P(R | c) in the sprinkler network, S and W are irrelevant.

Practice questions