Variable Elimination Algorithm
Introduction
Variable elimination algorithm is the most fundamental algorithm for probabilistic graphic model inference. Depending on the variable elimination order, the computation cost of variable elimination could unaffordable.
In this blog post, I would mainly like to discuss the complexity analysis of the variable elimination algorithm.
Variable Elimination
Variable elimination is necessary for the inference of probabilistic graphic models with discrete variables. For example, if we have a Bayesian network consisting of three variables
Variable Elimination Algorithm
Eliminate variable
where
The variable elimination (algorithm) does multiplication and summation for factor product and marginalization, respectively.
Notice that if all the variables are discrete variables, all the factors and factor products can just be represented as factor or probability tables.
If there are multiple variables to eliminate, we will have to eliminate the variables one by one for each step. Suppose at the elimination step
where the variables involved in the factor product are
Variable Elimination Algorithm Complexity
Suppose all the variables are discrete variables and none of the variables have been observed, let’s analyze the complexity of the variable elimination algorithm.
We first denote
For example, if
and
We then look at the factor product step, which is just computing the factor table for
The factor table for
We then look at the factor product step, which is just computing the factor table for
In the “best scenario” where
Now that we have analyzed the complexity for one single step, i.e., eliminating one variable, in the algorithm, we need to further analyze the complexity for eliminating multiple variables in the network. Suppose at the first step, we have
Here we denote that the total number of factors that ever exist during variable elimination, the original factors and the new factors generated from marginalization, is
So the number of multiplications required to eliminate
Note that
Similarly, the number of additions required to eliminate
So the total complexity for the variable elimination algorithm is
Because
Here is an extreme example. We have

Example Bayesian Network
Let’s first consider the elimination order
How about the elimination order
Therefore, the variable elimination algorithm complexity is
Variable Elimination Order
Determine the optimal variable elimination order is also NP-hard. There are a couple of heuristic variable elimination order determination algorithms which works well in practice, such as min-neighbors, min-weight, min-fill, etc. However, I will skip delve into this in this blog post.
References
Variable Elimination Algorithm
https://leimao.github.io/blog/Variable-Elimination-Algorithm/