Exact Inference — Variable Elimination

The inference task

Given a Bayesian network, a query variable $X$, evidence $\mathbf E = \mathbf e$ and the remaining hidden variables $\mathbf Y$, compute the posterior

$$P(X\mid\mathbf e) = \alpha\,P(X, \mathbf e) = \alpha\sum_{\mathbf y}P(X, \mathbf e, \mathbf y),$$

where $\alpha$ is the normalisation constant $1/P(\mathbf e)$. In practice we compute the unnormalised values for each value of $X$ and rescale them to sum to 1 — we never need $P(\mathbf e)$ separately.

Inference by enumeration

Write the joint as the product of CPT entries and sum over the hidden variables. For the alarm network:

$$P(B\mid j, m) = \alpha\,P(B)\sum_e P(e)\sum_a P(a\mid B, e)\,P(j\mid a)\,P(m\mid a).$$

Moving factors outside the sums where possible helps, but the depth-first evaluation still recomputes the same sub-products: $P(j\mid a)P(m\mid a)$ is evaluated for every value of $e$. Time is $O(n\,2^n)$ for $n$ Boolean variables (space is linear).

Variable elimination

Variable elimination (VE) evaluates the same expression right to left, storing intermediate results as factors — tables indexed by their variables.

1. Create a factor for each CPT, with evidence variables fixed to their observed values (they are no longer variables of the factor).
2. For each hidden variable $H$ in some order:
   • take all factors that mention $H$ and form their pointwise product;
   • sum out $H$ from the product, giving a new factor over the remaining variables;
   • put the new factor back in the pool.
3. Multiply the remaining factors (all over the query variable) and normalise.

Factor operations

Pointwise product: $f_1(A, B) \times f_2(B, C) = f(A, B, C)$ with $f(a, b, c) = f_1(a, b)\,f_2(b, c)$. The variables are the union, so the size is exponential in the number of variables.

Summing out: $f'(B, C) = \sum_a f(a, B, C)$ — adds the entries that agree on $B, C$.

Elimination order

Correctness does not depend on the order, but the cost does: it is dominated by the largest factor created. Eliminating a variable connected to $k$ others creates a factor over $k$ variables ($2^k$ entries). Finding the best order is NP-hard; greedy heuristics eliminate the variable that creates the smallest factor (min-degree / min-fill).

Irrelevant variables

Every variable that is not an ancestor of a query or evidence variable is irrelevant and can be removed before inference — summing out a leaf gives $\sum_x P(x\mid\text{parents}) = 1$. For $P(J\mid b)$ in the alarm network, $M$ drops out.

Complexity

Hardness follows because a Bayesian network can encode 3-SAT: a query is positive iff the formula is satisfiable. For large or densely connected networks we therefore turn to approximate inference by sampling. Clustering (join-tree) algorithms generalise VE to answer all single-variable posteriors at once.

Quick revision