Variable elimination (VE) is a simple and general exact inference algorithm in probabilistic graphical models, such as Bayesian networks and Markov random fields.
[1] It can be used for inference of maximum a posteriori (MAP) state or estimation of conditional or marginal distributions over a subset of variables.
The algorithm has exponential time complexity, but could be efficient in practice for low-treewidth graphs, if the proper elimination order is used.
Enabling a key reduction in algorithmic complexity, a factor
to a non-negative number, commonly denoted as
[2] A factor does not necessarily have a set interpretation.
One may perform operations on factors of different representations such as a probability distribution or conditional distribution.
[2] Joint distributions often become too large to handle as the complexity of this operation is exponential.
Thus variable elimination becomes more feasible when computing factorized entities.
Algorithm 1, called sum-out (SO), or marginalization, eliminates a single variable
The algorithm collect-relevant simply returns those factors in
Example Here we have a joint probability distribution.
at minimum must agree over the remaining variables.
, its reference is excluded and we are left with a distribution only over the remaining variables and the sum of each instantiation.
The resulting distribution which follows the sum-out operation only helps to answer queries that do not mention
[2] Also worthy to note, the summing-out operation is commutative.
)[2] Factor multiplication is not only commutative but also associative.
The most common query type is in the form
is observed taking value
A basic algorithm to computing p(X|E = e) is called variable elimination (VE), first put forth in.
from a discrete Bayesian network B.
VE calls SO to eliminate variables one by one.
is the set C of conditional probability tables (henceforth "CPTs") for B,
is a list of query variables,
is the corresponding list of observed values, and
Variable Elimination Algorithm VE(
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: