en>Yobot: WP:CHECKWIKI error fixes using AWB (9814)

2013-12-23T08:20:26Z

WP:CHECKWIKI error fixes using AWB (9814)

New page

'''Variable elimination''' (VE) is a simple and general [[Bayesian inference|exact inference]] algorithm in [[probabilistic graphical model]]s, such as [[Bayesian network]]s and [[Markov random field]]s.<ref>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)</ref><ref name="zhang">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)</ref> 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 <math>p(X|E = e)</math> where <math>X</math> and <math>E</math> are disjoint subsets of <math>U</math>, and <math>E</math> is observed taking value <math>e</math>. A basic algorithm to computing p(X|E = e) is called ''variable elimination'' (VE), first put forth in.<ref name="zhang" />
<br />
Algorithm 1, called sum-out (SO), eliminates a single variable <math>v</math> from a set <math>\phi</math> of potentials,<ref>Koller,D.,Friedman,N.:ProbabilisticGraphicalModels:PrinciplesandTechniques. MIT Press, Cambridge, MA (2009)</ref> and returns the resulting set of potentials. The algorithm collect-relevant simply returns those potentials in <math>\phi</math> involving variable <math>v</math>.

'''Algorithm 1''' sum-out(<math>v</math>,<math>\phi</math>)
:<math>\Psi</math> = collect-relevant(<math>v</math>,<math>\phi</math>)
:<math>\Psi</math> = the product of all potentials in <math>\Phi</math>
:<math>\tau = \sum_{v} \Psi</math>
<br />
'''return''' <math>(\phi - \Psi) \cup \{\tau\}</math>

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

'''Algorithm 2''' VE(<math>\phi, X, E, e, \sigma</math>)
:Multiply evidence potentials with appropriate CPTs While σ is not empty
:Remove the first variable <math>v</math> from <math>\sigma</math>
:<math>\phi</math> = sum-out<math>(v,\phi)</math>
:<math>p(X, E = e)</math> = the product of all potentials <math>\Psi \in \phi </math>
'''return''' <math>p(X,E = e)/ \sum_{X} p(X,E = e)</math>

== References ==
{{Reflist}}

[[Category:Graphical models]]

{{statistics-stub}}
{{comp-sci-stub}}

Nonlinear realization - Revision history

en>Yobot: WP:CHECKWIKI error fixes using AWB (9814)