{{Short description|Inference algorithm for probabilistic graphical models}} '''Variable elimination''' (VE) is a simple and general exact inference algorithm in probabilistic graphical models, such as Bayesian networks and Markov random fields.<ref name="zhang">{{cite journal |last1=Zhang |first1=Nevin L. |last2=Poole |first2=David |title=A simple approach to Bayesian network computations |journal=Proceedings of the 10th Canadian Artificial Intelligence Conference |date=1994 |pages=171-178 |url=https://hdl.handle.net/1783.1/757 |access-date=26 August 2025}}</ref> It can be used for inference of maximum a posteriori (MAP) state or estimation of conditional or marginal distributions over a subset of variables. The algorithm has exponential time complexity, but could be efficient in practice for low-treewidth graphs, if the proper elimination order is used.
==Factors== Enabling a key reduction in algorithmic complexity, a factor <math>f</math>, also known as a potential, of variables <math>V</math> is a relation between each instantiation of <math>v</math> of variables <math>f</math> to a non-negative number, commonly denoted as <math>f(x)</math>.<ref name=":0">{{Cite book|title=Modeling and Reasoning with Bayesian Networks|last=Darwiche|first=Adnan|date=2009-01-01|isbn=9780511811357|doi=10.1017/cbo9780511811357}}</ref> A factor does not necessarily have a set interpretation. One may perform operations on factors of different representations such as a probability distribution or conditional distribution.<ref name=":0" /> Joint distributions often become too large to handle as the complexity of this operation is exponential. Thus variable elimination becomes more feasible when computing factorized entities.
==Basic Operations==
=== Variable Summation === Algorithm 1, called sum-out (SO), or marginalization, eliminates a single variable <math>v</math> from a set <math>\phi</math> of factors,<ref>Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge, MA (2009)</ref> and returns the resulting set of factors. The algorithm collect-relevant simply returns those factors in <math>\phi</math> involving variable <math>v</math>.
'''Algorithm 1''' sum-out(<math>v</math>,<math>\phi</math>) :<math>\Phi</math> = collect factors relevant to <math>v</math> :<math>\Psi</math> = the product of all factors in <math>\Phi</math> :<math>\tau = \sum_{v} \Psi</math> <br /> '''return''' <math>(\phi - \Phi) \cup \{\tau\}</math>
'''Example'''
Here we have a joint probability distribution. A variable, <math>v</math> can be summed out between a set of instantiations where the set <math>V-v</math> at minimum must agree over the remaining variables. The value of <math>v</math> is irrelevant when it is the variable to be summed out.<ref name=":0" /> {| class="wikitable" !<math>V_1</math> !<math>V_2</math> !<math>V_3</math> !<math>V_4</math> !<math>V_5</math> !<math>Pr(.)</math> |- |true |true |true |false |false |0.80 |- |false |true |true |false |false |0.20 |} After eliminating <math>V_1</math>, its reference is excluded and we are left with a distribution only over the remaining variables and the sum of each instantiation. {| class="wikitable" !<math>V_2</math> !<math>V_3</math> !<math>V_4</math> !<math>V_5</math> !<math>Pr(.)</math> |- |true |true |false |false |1.0 |} The resulting distribution which follows the sum-out operation only helps to answer queries that do not mention <math>V_1</math>.<ref name=":0" /> Also worthy to note, the summing-out operation is commutative.
=== Factor Multiplication === Computing a product between multiple factors results in a factor compatible with a single instantiation in each factor.<ref name=":0" />
'''Algorithm 2''' mult-factors(<math>v</math>,<math>\phi</math>)<ref name=":0" /> :<math>Z</math> = Union of all variables between product of factors <math>f_1(X_1),...,f_m(X_m)</math> :<math>f</math> = a factor over <math>f</math> where <math>f</math> for all <math>f</math> :'''For''' each instantiation <math>z</math> ::'''For''' 1 to <math>m</math> :::<math>x_1=</math> instantiation of variables <math>X_1</math> consistent with <math>z</math> :::<math>f(z) = f(z)f_i(x_i)</math> :'''return''' <math>f</math> Factor multiplication is not only commutative but also associative.
==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" />
Taken from,<ref name="zhang" /> this algorithm 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 conditional probability tables (henceforth "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>.
'''Variable Elimination Algorithm''' VE(<math>\phi, X, E, e, \sigma</math>) :Multiply factors 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 factors <math>\Psi \in \phi </math> '''return''' <math>p(X,E = e)/ \sum_{X} p(X,E = e)</math>
== Ordering == Finding the optimal order in which to eliminate variables is an NP-hard problem. As such there are heuristics one may follow to better optimize performance by order: # Minimum Degree: Eliminate the variable which results in constructing the smallest factor possible.<ref name=":0" /> # Minimum Fill: By constructing an undirected graph showing variable relations expressed by all CPTs, eliminate the variable which would result in the least edges to be added post elimination.<ref name=":0" />
== References == {{Reflist}}
Category:Graphical models