OnesContextual Variable EliminationExtracting the AnswerThe Abstract Contextual Variable Elimination Algorithm

The Abstract Contextual Variable Elimination Algorithm

The contextual variable elimination algorithm, is given in Figure *. A more refined version that does less splitting is given in Section *.
To compute P(X|E1=o1 &...&Es=os)
Given multiset R of confactors
1.Incorporate evidence as in Section *.
2.while there is a non-query variable to be eliminated
{
Select non-query variable Y to eliminate;
Call R := eliminate(Y,R);
}
3.Compute posterior probability for X as in Section *
Procedure eliminate(Y,R):
partition R into:
R- = those confactors in R that don't involve Y;
R* = {r in R : r  involves  Y };
while there is {<b1 ,T1>, <b2 ,T2>} subset R* where b1 and b2 are compatible,
{
remove <b1 ,T1> and <b2 ,T2> from R*;
split <b1 ,T1> on b2 putting residual confactors in R*;
split <b2 ,T2> on b1, putting residual confactors in R*;
add <b1&b2 ,T1×tT2> to R*;
}
for every <b,t> in R* such that Y appears in t
{
remove <b,t> from R*;
add <b,SUMY t> to R-;
}
while R* is not empty
{
if {<b &Y=v1,T1> ,..., <b &Y=vk,Tk>} subset R*
{
remove <b &Y=v1,T1> ,..., <b &Y=vk,Tk> from R*;
add <b ,T1+t...+tTk> to R-;
}
else if {<b1 &Y=vi ,T1>, <b2 &Y=vj ,T2>} subset R* where b1 and b2 are compatible and b1 != b2
{
remove <b1 &Y=vi ,T1> and <b2 &Y=vj ,T2> from R*;
split <b1 &Y=vi ,T1> on b2, putting all created confactors in R*;
split <b2 &Y=vj ,T2> on b1, putting all created confactors in R*;
}
}
Return R-.
×t is defined in Section *.
+t is defined in Section *.
All set operations are assumed to be on multisets.

Contextual Variable Elimination
 

The elimination procedure is called once for each non-query, non-observed variable. The order in which the variables are selected is called the elimination ordering. This algorithm does not imply that the elimination ordering has to be given a priori. The other choice points are the order in which to do multiplication, and the splitting ordering.

Note that in the eliminate algorithm, all set operations are assumed to be on multisets. It is possible, and not uncommon, to get multiple copies of the same confactor. One example where this happens is when there is a naive Bayes model with variable C with no parents, and variables Y1,...,Yn each with only C as a parent. Often the conditional probabilities of some of the Yi's are the same as they represent repeated identical sensors. If these identical sensors observe the same value, then we will get identical confactors, none of which can be removed without affecting the answer.

To see the correctness of the procedure, note that all of the local operations preserve the program invariants; we still need to check that the algorithm halts. After the first while-loop of eliminate, the contexts of the confactors in R* are mutually exclusive and covering by the second part of the loop invariant. For all complete contexts on the variables that remain after Y is eliminated, there is either a compatible confactor with Y in the table, or there is a compatible confactor with Y=vi for every value vi. The splitting of the second while loop of eliminate preserves the mutual exclusiveness of the bodies of the confactors in R* and when splitting a confactor, the set of created confactors covers the same context as the original confactor. If there are confactors in R*, and the if-condition does not hold, then there must be a pair of confactors where the else-if condition holds. Thus, each time through the second while-loop, the number of confactors in R- increases or the number of confactors in R* increases and these are both bounded in size by the size of the corresponding factor. Thus eliminate must stop, and when it does Y is eliminated in all contexts.

David Poole and Nevin Lianwen Zhang,Exploiting Contextual Independence In Probabilistic Inference, Journal of Artificial Intelligence Research, 18, 2003, 263-313.

OnesContextual Variable EliminationExtracting the AnswerThe Abstract Contextual Variable Elimination Algorithm