Variable elimination

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.

Inference

The most common query type is in the form $p(X|E=e)$ where $X$ and $E$ are disjoint subsets of $U$, and $E$ is observed taking value $e$. A basic algorithm to computing p(X|E = e) is called variable elimination (VE), first put forth in.
Algorithm 1, called sum-out (SO), eliminates a single variable $v$ from a set $\phi$ of potentials, and returns the resulting set of potentials. The algorithm collect-relevant simply returns those potentials in $\phi$ involving variable $v$.

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

$\Phi$ = collect-relevant($v$,$\phi$)

$\Psi$ = the product of all potentials in $\Phi$

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

return $(\phi -\Psi )\cup \{\tau \}$

Algorithm 2, taken from, computes $p(X|E=e)$ from a discrete Bayesian network B. VE calls SO to eliminate variables one by one. More specifically, in Algorithm 2, $\phi$ is the set C of CPTs for B, $X$ is a list of query variables, $E$is a list of observed variables, $e$ is the corresponding list of observed values, and $\sigma$ is an elimination ordering for variables $U-XE$, where $XE$ denotes $X\cup E$.

Algorithm 2 VE($\phi ,X,E,e,\sigma$)

Multiply evidence potentials with appropriate CPTs While σ is not empty

Remove the first variable $v$ from $\sigma$

$\phi$ = sum-out$(v,\phi )$

$p(X,E=e)$ = the product of all potentials $\Psi \in \phi$

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