Contextual Variable Elimination

Contextual Variable Elimination

The general idea of contextual variable elimination (CVE) is to represent conditional probabilities in terms of confactors, and use the VE algorithm with the confactor representation rather than with tables. The units of manipulation are thus finer grained than the factors in VE or the members of the buckets of BEBA; what is analogous to a factor or a member of a bucket consists of multisets of confactors. Given a variable to eliminate, we can ignore (distribute out) all of the confactors that don't involve this variable. Where there is some contextual independence that goes beyond conditional independence of variables, the savings can be substantial. If there is no contextual independence, all of the confactors have empty contexts, and this algorithm reduces to VE.

This section introduces an abstract nondeterministic version of CVE. Section * presents a more concrete version where we explain how to resolve much of the nondeterminism.

The input to CVE is:

a multiset of confactors that consists of the union of the confactors that represent the conditional probability distribution of each variable given its predecessors
a set of query variables
an observation that is a conjunction of assignments of values to some of the variables

We first consider the case with no observations. Observations are considered in Section *.

Initially and after the elimination of each variable, we maintain a multiset of confactors with the following program invariant:

The probability of a context c on the non-eliminated variables can be obtained by multiplying the values of context c associated with confactors that are applicable in context c. For each complete context on the non-eliminated variables and for each variable there is at least one confactor containing that variable that is applicable in that context⁷.

The algorithm will not sum out a variable in all contexts in one step. Rather it will sum out a variable in different contexts separately. Intermediate to being fully summed out, a variable will be summed out in some contexts and not in others. The remaining variables should be interpreted relative to whether the variable has been summed out in context c.

Like VE, the abstract algorithm is made up of the primitive operations of summing out a variable and multiplying confactors, and also includes a primitive operation of confactor splitting that enables the other two operations. All of these operations locally preserve this program invariant. They are described in the next subsections.

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

Contextual Variable Elimination