   Contextual Variable Elimination with Absorption 
Contextual Variable Elimination with Absorption
A version of contextual variable elimination
that uses absorption, is given in
Figure *. This is the algorithm used in the
experimental results of Section *.
To compute P(XE_{1}=o_{1} &...&E_{s}=o_{s}) 
 Given   multiset of contextual contribution confactors 
 1.  Incorporate evidence as in Section *. 
 2.  While there is a factor involving a nonquery variable 
    Select nonquery variable Y to eliminate; 
    Call eliminate(Y). 
 3.  Compute posterior probability for X as in Section *

Procedure eliminate(Y): 
 partition the confactorbase R into: 
  R^{} those confactors that don't involve Y 
  R^{+} = {r in R : r is a confactor for Y} 
  R^{*} = {r in R : r involves Y and r is not a confactor for Y}; 
 for each r in R^{*} 
  do R^{+} < absorb(R^{+},r); 
 partition R^{+} into: 
  R^{t} = {r in R^{+} : Y in table of r} 
  R_{i} = {<b,t>: <b&Y=v_{i},t> in R^{+} } for each
1 <= i <= s, where dom(Y)={v_{1},...,v_{s}}. 
 Return confactorbase R^{} union (R_{1} +_{g} ···+_{g} R_{s}) union {<b_{i},SUM_{Y} t_{i}> : <b_{i},t_{i}> in R^{t}}.

absorb(R,r) is defined in Section *. 
R_{1} +_{g} R_{2} is defined in Section *.

Contextual Variable Elimination with Absorption
The elimination procedure is called once for
each nonquery, nonobserved 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.
One of the main issues in implementing this algorithm is efficient
indexing for the confactors. We want to be able to quickly find the
confactors for Y, the confactors that contain Y, and the
compatible confactors during addition and absorption. If we are given
a prior elimination ordering, we can use the idea of bucket
elimination [11], namely that a confactor can be placed
in the bucket of the earliest variable in the elimination
ordering. When we eliminate Y, all of the confactors that contain
Y are in Y's bucket. If we don't have a prior elimination
ordering, we can keep an inverted list of the confactors (for each
variable, we have a list of all of the confactors that are for that
variable and a list of the confactors that contain that variable). We
then have to maintain these lists as we create new confactors and
delete old ones. We also want to be able to index the confactors so that
we can quickly find other confactors that contain the variable to be
eliminated and have compatible contexts. In our implementation, we
compared all of the confactors that contain the variable to be
eliminated, and rejected those with incompatible contexts. Ideally, we
should be able to do better than this, but how to do it is an open
question.
There are a number of choice points in this algorithm:
 the elimination
ordering.
 the splitting ordering; when computing residuals, which order
should the variables be split on. This is discussed in Section
*.
 the order that the elements of R^{*} are absorbed. This
has an impact similar to the choice of multiplication ordering for VE
(when we have to multiply a number of factors, which order should they
be done); sometimes we can have smaller intermediate factors if the
choice is done appropriately.
David Poole
and Nevin Lianwen
Zhang,Exploiting Contextual
Independence In Probabilistic Inference, Journal of
Artificial Intelligence Research, 18, 2003, 263313.
   Contextual Variable Elimination with Absorption 