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.
The most common query type is in the form where and are disjoint subsets of , and is observed taking value . 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 from a set of potentials, and returns the resulting set of potentials. The algorithm collect-relevant simply returns those potentials in involving variable .
Algorithm 1 sum-out(,)
- = collect-relevant(,)
- = the product of all potentials in
Algorithm 2, taken from, computes from a discrete Bayesian network B. VE calls SO to eliminate variables one by one. More specifically, in Algorithm 2, is the set C of CPTs for B, is a list of query variables, is a list of observed variables, is the corresponding list of observed values, and is an elimination ordering for variables , where denotes .
Algorithm 2 VE()
- Multiply evidence potentials with appropriate CPTs While σ is not empty
- Remove the first variable from
- = sum-out
- = the product of all potentials
- 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)
- 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)
|This statistics-related article is a stub. You can help Wikipedia by expanding it.|
|This computer science article is a stub. You can help Wikipedia by expanding it.|