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 5 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 4.7.

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 context7.

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.

## 4.1 Multiplying Contextual Factors

If we have two confactors with the same context:
-b, t1
-b, t2 we can replace them with their product:

## -B, T1 ⊗Tt2.
