Variable elimination (VE) is a simple and general exact inference algorithm in probabilistic graphical models, such as Bayesian networks and Markov random fields. It can be used for inference of maximum a posteriori (MAP) state or estimation of marginal distribution over a subset of variables. The algorithm has exponential time complexity, but could be efficient in practice for the low-treewidth graphs, if the proper elimination order is used.
Contents
Factors
Enabling a key reduction in algorithmic complexity, a factor
Variable Summation
Algorithm 1, called sum-out (SO), or marginalization, eliminates a single variable
Algorithm 1 sum-out(
return
Example
Here we have a joint probability distribution. A variable,
After eliminating
The resulting distribution which follows the sum-out operation only helps to answer queries that do not mention
Factor Multiplication
Computing a product between multiple factors results in a factor compatible with a single instantiation in each factor.
Algorithm 2 mult-factors(
Factor multiplication is not only commutative but also associative.
Inference
The most common query type is in the form
Taken from, this algorithm computes
Variable Elimination Algorithm VE(
return
Ordering
Finding the optimal order in which to eliminate variables is an NP-hard problem. As such there are heuristics one may follow to better optimize performance by order:
- Minimum Degree: Eliminate the variable which results in constructing the smallest factor possible.
- Minimum Fill: By constructing an undirected graph showing variable relations expressed by all CPTs, eliminate the variable which would result in the least edges to be added post elimination.