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.[1][2] 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 ${\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.[2]
Algorithm 1, called sum-out (SO), eliminates a single variable ${\displaystyle v}$ from a set ${\displaystyle \phi }$ of potentials,[3] and returns the resulting set of potentials. The algorithm collect-relevant simply returns those potentials in ${\displaystyle \phi }$ involving variable ${\displaystyle v}$.

${\displaystyle \Psi }$ = collect-relevant(${\displaystyle v}$,${\displaystyle \phi }$)
${\displaystyle \Psi }$ = the product of all potentials in ${\displaystyle \Phi }$
${\displaystyle \tau =\sum _{v}\Psi }$

Algorithm 2, taken from,[2] 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 \phi }$ is the set C of 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}$.

Multiply evidence potentials with appropriate CPTs While σ is not empty
Remove the first variable ${\displaystyle v}$ from ${\displaystyle \sigma }$
${\displaystyle \phi }$ = sum-out${\displaystyle (v,\phi )}$
${\displaystyle p(X,E=e)}$ = the product of all potentials ${\displaystyle \Psi \in \phi }$

References

1. Zhang, N.L., Poole, D.: A Simple Approach to Bayesian Network Computations. In:7th Canadian Conference on Artificial Intelligence, pp. 171–178. Springer, New York(1994)
2. Zhang, N.L., Poole, D.:A Simple Approach to Bayesian Network Computations.In: 7th Canadian Conference on Artificial Intelligence,pp. 171--178. Springer, New York (1994)
3. Koller,D.,Friedman,N.:ProbabilisticGraphicalModels:PrinciplesandTechniques. MIT Press, Cambridge, MA (2009)