Variable elimination

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)}$.^[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 ${\displaystyle v}$ from a set ${\displaystyle \phi }$ of factors,^[3] 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 }$)

${\displaystyle \Phi }$ = collect factors relevant to ${\displaystyle v}$

${\displaystyle \Psi }$ = the product of all factors in ${\displaystyle \Phi }$

${\displaystyle \tau =\sum _{v}\Psi }$

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.^[2]

${\displaystyle V_{1}}$	${\displaystyle V_{2}}$	${\displaystyle V_{3}}$	${\displaystyle V_{4}}$	${\displaystyle V_{5}}$	${\displaystyle Pr(.)}$
true	true	true	false	false	0.80
false	true	true	false	false	0.20

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.

${\displaystyle V_{2}}$	${\displaystyle V_{3}}$	${\displaystyle V_{4}}$	${\displaystyle V_{5}}$	${\displaystyle Pr(.)}$
true	true	false	false	1.0

The resulting distribution which follows the sum-out operation only helps to answer queries that do not mention ${\displaystyle V_{1}}$.^[2] Also worthy to note, the summing-out operation is commutative.

Computing a product between multiple factors results in a factor compatible with a single instantiation in each factor.^[2]

Algorithm 2 mult-factors(${\displaystyle v}$,${\displaystyle \phi }$)^[2]

${\displaystyle Z}$ = Union of all variables between product of factors ${\displaystyle f_{1}(X_{1}),...,f_{m}(X_{m})}$

${\displaystyle f}$ = a factor over ${\displaystyle f}$ where ${\displaystyle f}$ for all ${\displaystyle f}$

For each instantiation ${\displaystyle z}$

For 1 to ${\displaystyle m}$

${\displaystyle x_{1}=}$ instantiation of variables ${\displaystyle X_{1}}$ consistent with ${\displaystyle z}$

${\displaystyle f(z)=f(z)f_{i}(x_{i})}$

return ${\displaystyle f}$

Factor multiplication is not only commutative but also associative.