The 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 {, } subset R* where b1 and b2 are compatible, { remove and from R*; split on b2 putting residual confactors in R*; split on b1, putting residual confactors in R*; add to R*; } for every in R* such that Y appears in t { remove from R*; add to R-; } while R* is not empty { if { ,..., } subset R* { remove ,..., from R*; add to R-; } else if {, } subset R* where b1 and b2 are compatible and b1 != b2 { remove and from R*; split on b2, putting all created confactors in R*; split 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.

 The Abstract Contextual Variable Elimination Algorithm