Variable elimination

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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, Eis 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[edit]

  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. ^ a b c 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.: Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge, MA (2009)