Exploiting Contextual Independence In Probabilistic Inference -- Contextual Variable Elimination with Absorption

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(X|E₁=o₁ &...&E_s=o_s)

Given

multiset of contextual contribution confactors

Incorporate evidence as in Section *.

While there is a factor involving a non-query variable

Select non-query variable Y to eliminate;

Call eliminate(Y).

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₁,...,v_s}.

Return confactorbase R^- union (R₁ +_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₁ +_g R₂ 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:

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, 263-313.

Contextual Variable Elimination with Absorption