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 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 ${\displaystyle f}$, also known as a potential, of variables ${\displaystyle V}$ is a relation between each instantiation of ${\displaystyle v}$ of variables ${\displaystyle f}$ to a non-negative number, commonly denoted as ${\displaystyle f(x)}$. 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. 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 ${\displaystyle v}$ from a set ${\displaystyle \phi }$ of factors, and returns the resulting set of factors. The algorithm collect-relevant simply returns those factors in ${\displaystyle \phi }$ involving variable ${\displaystyle v}$.

Algorithm 1 sum-out(${\displaystyle v}$,${\displaystyle \phi }$)

return ${\displaystyle (\phi -\Phi )\cup \{\tau \}}$

Example

Here we have a joint probability distribution. A variable, ${\displaystyle v}$ can be summed out between a set of instantiations where the set ${\displaystyle V-v}$ at minimum must agree over the remaining variables. The value of ${\displaystyle v}$ is irrelevant when it is the variable to be summed out.

After eliminating ${\displaystyle V_{1}}$, its reference is excluded and we are left with a distribution only over the remaining variables and the sum of each instantiation.