Variable elimination

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. 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]\displaystyle{ f }[/math], also known as a potential, of variables [math]\displaystyle{ V }[/math] is a relation between each instantiation of [math]\displaystyle{ v }[/math] of variables [math]\displaystyle{ f }[/math] to a non-negative number, commonly denoted as [math]\displaystyle{ f(x) }[/math]. 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. 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]\displaystyle{ v }[/math] from a set [math]\displaystyle{ \phi }[/math] of factors, and returns the resulting set of factors. The algorithm collect-relevant simply returns those factors in [math]\displaystyle{ \phi }[/math] involving variable [math]\displaystyle{ v }[/math].

Algorithm 1 sum-out([math]\displaystyle{ v }[/math],[math]\displaystyle{ \phi }[/math])

[math]\displaystyle{ \Phi }[/math] = collect factors relevant to [math]\displaystyle{ v }[/math]

[math]\displaystyle{ \Psi }[/math] = the product of all factors in [math]\displaystyle{ \Phi }[/math]

[math]\displaystyle{ \tau = \sum_{v} \Psi }[/math]

return [math]\displaystyle{ (\phi - \Phi) \cup \{\tau\} }[/math]

Example

Here we have a joint probability distribution. A variable, [math]\displaystyle{ v }[/math] can be summed out between a set of instantiations where the set [math]\displaystyle{ V-v }[/math] at minimum must agree over the remaining variables. The value of [math]\displaystyle{ v }[/math] is irrelevant when it is the variable to be summed out.

[math]\displaystyle{ V_1 }[/math]	[math]\displaystyle{ V_2 }[/math]	[math]\displaystyle{ V_3 }[/math]	[math]\displaystyle{ V_4 }[/math]	[math]\displaystyle{ V_5 }[/math]	[math]\displaystyle{ Pr(.) }[/math]
true	true	true	false	false	0.80
false	true	true	false	false	0.20

After eliminating [math]\displaystyle{ 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.

[math]\displaystyle{ V_2 }[/math]	[math]\displaystyle{ V_3 }[/math]	[math]\displaystyle{ V_4 }[/math]	[math]\displaystyle{ V_5 }[/math]	[math]\displaystyle{ 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]\displaystyle{ V_1 }[/math]. 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.

Algorithm 2 mult-factors([math]\displaystyle{ v }[/math],[math]\displaystyle{ \phi }[/math])

[math]\displaystyle{ Z }[/math] = Union of all variables between product of factors [math]\displaystyle{ f_1(X_1),...,f_m(X_m) }[/math]

[math]\displaystyle{ f }[/math] = a factor over [math]\displaystyle{ f }[/math] where [math]\displaystyle{ f }[/math] for all [math]\displaystyle{ f }[/math]

For each instantiation [math]\displaystyle{ z }[/math]

For 1 to [math]\displaystyle{ m }[/math]

[math]\displaystyle{ x_1= }[/math] instantiation of variables [math]\displaystyle{ X_1 }[/math] consistent with [math]\displaystyle{ z }[/math]

[math]\displaystyle{ f(z) = f(z)f_i(x_i) }[/math]

return [math]\displaystyle{ f }[/math]

Factor multiplication is not only commutative but also associative.

Inference

The most common query type is in the form [math]\displaystyle{ p(X|E = e) }[/math] where [math]\displaystyle{ X }[/math] and [math]\displaystyle{ E }[/math] are disjoint subsets of [math]\displaystyle{ U }[/math], and [math]\displaystyle{ E }[/math] is observed taking value [math]\displaystyle{ e }[/math]. A basic algorithm to computing p(X|E = e) is called variable elimination (VE), first put forth in.

Taken from, this algorithm computes [math]\displaystyle{ 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]\displaystyle{ \phi }[/math] is the set C of conditional probability tables (henceforth "CPTs") for B, [math]\displaystyle{ X }[/math] is a list of query variables, [math]\displaystyle{ E }[/math] is a list of observed variables, [math]\displaystyle{ e }[/math] is the corresponding list of observed values, and [math]\displaystyle{ \sigma }[/math] is an elimination ordering for variables [math]\displaystyle{ U - XE }[/math], where [math]\displaystyle{ XE }[/math] denotes [math]\displaystyle{ X \cup E }[/math].

Variable Elimination Algorithm VE([math]\displaystyle{ \phi, X, E, e, \sigma }[/math])

Multiply factors with appropriate CPTs while σ is not empty

Remove the first variable [math]\displaystyle{ v }[/math] from [math]\displaystyle{ \sigma }[/math]

[math]\displaystyle{ \phi }[/math] = sum-out[math]\displaystyle{ (v,\phi) }[/math]

[math]\displaystyle{ p(X, E = e) }[/math] = the product of all factors [math]\displaystyle{ \Psi \in \phi }[/math]

return [math]\displaystyle{ 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:

1. Minimum Degree: Eliminate the variable which results in constructing the smallest factor possible.
2. 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.