Variable Elimination

Variable elimination is an exact inference algorithm that computes marginal distributions in graphical models by systematically summing out (marginalizing) variables one at a time.

1. Problem

Given a joint distribution that factorizes over a graphical model, compute a marginal such as

$$p(x_q) = \sum_{x_1}\sum_{x_2}\cdots\sum_{x_{D \setminus q}} p(x_1, \dots, x_D)$$

Naively summing over all configurations is exponential in $D$.

2. Key Idea

Exploit the factorization of the joint distribution to push sums inside products. Only sum over a variable when all factors involving it have been collected.

3. Algorithm

  1. Choose an elimination ordering for the non-query variables
  2. For each variable $x_d$ in the ordering:
    • Collect all factors that involve $x_d$
    • Multiply them together
    • Sum out $x_d$ to produce a new factor over the remaining variables
  3. Multiply all remaining factors to get $p(x_q)$

4. Complexity

The cost depends on the elimination ordering. The largest intermediate factor determines the computational cost. For tree-structured graphs, an optimal ordering exists with cost $O(DK^2)$ where $K$ is the number of states per variable.

5. Connection to Forward Algorithm

The Forward-Backward Algorithm for HMMs is a special case of variable elimination on a chain graph, where variables are eliminated left-to-right.