Avoiding SplittingSumming Out A VariableContextual 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(X|E1=o1 &...&Es=os)
Given multiset of contextual contribution confactors
1.Incorporate evidence as in Section *.
2.While there is a factor involving a non-query variable
Select non-query 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:
Rt = {r in R+ : Y  in table of r}
Ri = {<b,t>: <b&Y=vi,t> in R+ } for each 1 <= i <= s, where dom(Y)={v1,...,vs}.
Return confactorbase R- union (R1 +g ···+g Rs) union {<bi,SUMY ti> : <bi,ti> in Rt}.
absorb(R,r) is defined in Section *.
R1 +g R2 is defined in Section *.

Contextual Variable Elimination with Absorption
 

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.

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:


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

Avoiding SplittingSumming Out A VariableContextual Variable Elimination with Absorption