7.3. Variable Elimination

Variable Elimination

Variable Elimination is an exact inference algorithm that computes posterior probabilities more efficiently than inference by enumeration by systematically eliminating hidden variables one at a time. It applies to Bayes Nets and any model that factorizes a joint distribution into local conditional probability tables (CPTs), while avoiding construction of the full joint distribution  .

The goal is to compute the posterior

$$P(Q\mid e)=\alpha P(Q,e),$$

where $Q$ is the query variable, $e$ is observed evidence, and $\alpha =\frac{1}{P(e)}$ is a normalization constant.

Instead of summing over all hidden variables at once, variable elimination reorders the computation to reduce intermediate complexity. The joint term is implicitly represented as a product of factors:

$$P(Q,e)=\sum _h\prod _i{f}_i,$$

where each factor $f_i$ is an unnormalized probability derived from a CPT and evidence.

Eliminating a variable X consists of two steps:

1. Join (multiply) all factors that contain $X$.
2. Sum out $X$ from the resulting factor.

Formally, if ${\mathcal{F}}_X$ is the set of factors containing $X$,

$$f_{\text{new}}(\mathbf{Y})=\sum _x\prod _{f\in {\mathcal{F}}_X}f(x,\mathbf{Y}),$$

where $\mathbf{Y}$ are the remaining variables in those factors.

This process is repeated for each hidden variable in a chosen elimination order. After all hidden variables are eliminated, the remaining factors are multiplied together and normalized to produce $P(Q\mid e)$.

The key advantage over inference by enumeration is that irrelevant terms are summed out early, keeping intermediate factor sizes small. However, the efficiency of variable elimination critically depends on the elimination order: it only outperforms enumeration if the largest intermediate factor remains manageable.