# Variable elimination

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Variable_elimination
> Markdown URL: https://mediated.wiki/source/Variable_elimination.md
> Source: https://en.wikipedia.org/wiki/Variable_elimination
> Source revision: 1307950835
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Inference algorithm for probabilistic graphical models}}
'''Variable elimination''' (VE) is a simple and general [exact inference](/source/Bayesian_inference) algorithm in [probabilistic graphical model](/source/probabilistic_graphical_model)s, such as [Bayesian network](/source/Bayesian_network)s and [Markov random field](/source/Markov_random_field)s.<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](/source/maximum_a_posteriori) (MAP) state or estimation of [conditional](/source/conditional_distribution) or [marginal distribution](/source/marginal_distribution)s over a subset of variables. The algorithm has exponential time complexity, but could be efficient in practice for low-[treewidth](/source/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](/source/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](/source/Minimum_degree_algorithm): 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

---
Adapted from the Wikipedia article [Variable elimination](https://en.wikipedia.org/wiki/Variable_elimination) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Variable_elimination?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.