🔫 Variable Elimination

Variable elimination is an exact inference technique for , represented as a 🗳️ Markov Random Field or equivalently a product of 🍪 Factors, that can drastically reduce the computation time for probabilistic inference. The main idea is to eliminate variables one-by-one instead of naively summing over combinations of all variables at once.

First, we need some elimination ordering of the variables. Choosing this ordering itself is NP-hard, but there are some heuristic approaches.

1. Min-neighbors orders by fewest dependencies.
2. Min-weight orders by minimizing the product of cardinalities of dependencies.
3. Min-fill orders by minimizing the size of the next marginalized factor .

Now, to perform elimination, we perform the following for each variable from our ordering .

1. Take the product of all factors containing .
2. Marginalize out to obtain .
3. Replace factors with .

Pushing Sums §

A more intuitive alternative explanation is that we’re essentially “pushing in” our summations from the original naive solution. Consider a ⛓️ Markov Chain’s probability distribution

Our naive calculation is for is

However, note that these variables aren’t dependent on most of the summations. For example, only requires a summation over . Thus, flipping the summation order and factoring, we get

Now, we can calculate the innermost sum, , to get

which we can eliminate again using the same procedure. In this illustration, “pushing” the summation is equivalent to choosing which factors to multiply and marginalizing over them.

Complexity §

In our Markov chain example, if each random variable has unique values, each elimination here takes time, so our total runtime is instead of the naive .

However, not all distributions have such an ideal structure. In most cases, the ordering of our variables significantly affects our runtime: if we combine too many factors and need to marginalize out a big factor, the summation size grows by a factor of for each variable.

Thus, the complexity of variable elimination ifs where is the maximum size of any factor formed via factor product.