Variable elimination

Basic Operations

Variable Summation

Algorithm 1, called sum-out (SO), or marginalization, eliminates a single variable ${\displaystyle v}$ from a set ${\displaystyle \varphi }$ of factors, and returns the resulting set of factors. The algorithm collect-relevant simply returns those factors in ${\displaystyle \varphi }$ involving variable ${\displaystyle v}$.

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

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

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

${\displaystyle \tau =\sum _v\mathrm{\Psi }}$

return ${\displaystyle (\varphi -\mathrm{\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.

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

Factor Multiplication

Computing a product between multiple factors results in a factor compatible with a single instantiation in each factor.

Algorithm 2 mult-factors(${\displaystyle v}$,${\displaystyle \varphi }$)

${\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.

Inference

The most common query type is in the form ${\displaystyle p(X|E=e)}$ where ${\displaystyle X}$ and ${\displaystyle E}$ are disjoint subsets of ${\displaystyle U}$, and ${\displaystyle E}$ is observed taking value ${\displaystyle e}$. A basic algorithm to computing p(X|E = e) is called variable elimination (VE), first put forth in.

Taken from, this algorithm computes ${\displaystyle p(X|E=e)}$ from a discrete Bayesian network B. VE calls SO to eliminate variables one by one. More specifically, in Algorithm 2, ${\displaystyle \varphi }$ is the set C of conditional probability tables (henceforth "CPTs") for B, ${\displaystyle X}$ is a list of query variables, ${\displaystyle E}$ is a list of observed variables, ${\displaystyle e}$ is the corresponding list of observed values, and ${\displaystyle \sigma }$ is an elimination ordering for variables ${\displaystyle U-XE}$, where ${\displaystyle XE}$ denotes ${\displaystyle X\cup E}$.

Variable Elimination Algorithm VE(${\displaystyle \varphi ,X,E,e,\sigma }$)

Multiply factors with appropriate CPTs while σ is not empty

Remove the first variable ${\displaystyle v}$ from ${\displaystyle \sigma }$

${\displaystyle \varphi }$ = sum-out${\displaystyle (v,\varphi )}$

${\displaystyle p(X,E=e)}$ = the product of all factors ${\displaystyle \mathrm{\Psi }\in \varphi }$

return ${\displaystyle p(X,E=e)/\sum _{X}p(X,E=e)}$

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:

1. Minimum Degree: Eliminate the variable which results in constructing the smallest factor possible.
2. 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.