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 $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.^[2]
Algorithm 1, called sum-out (SO), eliminates a single variable $v$ from a set $\phi$ of potentials,^[3] 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,^[2] 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)$

References

↑ 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.0 2.1 2.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)
↑ Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge, MA (2009)