Variable Elimination

Variable elimination computes $P(X | E)$ by summing out non-query, non-evidence variables one at a time.

Algorithm

Given query variable $X$, evidence $E$, and other variables $Y_1, \dots, Y_m$:

``` factors = list of all conditional probability tables, with evidence variables fixed for var in eliminate_order: relevant = factors involving var product = pointwise multiply all factors in relevant summed = sum out var from product factors = (factors not in relevant) ∪ {summed} result = pointwise multiply remaining factors return normalized result ```

Why ordering matters

Each "sum out" step can create a factor over many variables. The width of the elimination process (largest factor created) determines time and memory cost. Optimal width is the treewidth of the moralized graph — computing optimal treewidth is NP-hard but reasonable heuristics (min-degree, min-fill) usually find good orderings.

Worked intuition

Three variables $A, B, C$, all binary, with $C$ depending on both $A$ and $B$:

• Factor $\phi(A)$, $\phi(B)$, $\phi(A, B, C)$.
• Eliminate $C$ first: sum $\phi(A, B, C)$ over $C$ to get $\phi'(A, B)$. Now multiply $\phi(A) \cdot \phi(B) \cdot \phi'(A, B)$.
• Width 2: never create a factor over more than 2 variables.
• Eliminate $A$ first: combine $\phi(A)$ and $\phi(A, B, C)$ into a factor over $A, B, C$, then sum out $A$ to get a factor over $B, C$. Width 3.

Different orderings produce different intermediate factor sizes. Bad orderings can be catastrophically slow.

When exact inference is feasible

Tree-shaped graphs (any polytree): linear time exact inference. Junction trees with bounded treewidth: polynomial time.

For real-world networks with hidden Markov structure (chain graphs), variable elimination is exactly the forward-backward algorithm in HMMs — same algorithm, different domain.

When to give up on exact inference

• Treewidth grows with the size of the network.
• Graphs with very dense interactions.
• Continuous-valued variables without easy parametric forms.

For these, you fall back to sampling-based methods or variational approximations.