Next: An Example Up: Exploiting Causal Independence in Previous: Tidy Heterogeneous Factorizations

# Causal Independence and Inference

Our task is to compute in a BN. According to Proposition 6, we can do this in the deputation of the BN.

An elimination ordering consisting of the variables outside is legitimate if each deputy variable appears before the corresponding new regular variable e. Such an ordering can be found using, with minor adaptations, minimum deficiency search or maximum cardinality search.

The following algorithm computes in the deputation BN. It is called VE1 because it is an extension of VE .

Procedure VE1
• Inputs: --- The list of homogeneous factors
` `in the deputation BN;
` ` --- The list of heterogeneous factors
` `in the deputation BN;
` ` X --- A list of query variables;
` ` Y --- A list of observed variables;
` ` --- The corresponding list of observed values;
` ` --- A legitimate elimination ordering.

• Output: .

1. Set the observed variables in all factors to their observed values.
2. While is not empty,
• Remove the first variable z from .

• . Endwhile
3. Set h=multiplication of all factors in
` ` combination (by ) of all factors in .
/* h is a function of variables in X. */
4. Return . /* renormalization */

Proof: Consider the following modifications to the algorithm. First remove step 1. Then the factor h produced at step 3 is a function of variables in X and Y. Add a new step after step 3 that sets the observed variables in h to their observed values. We shall first show that the modifications do not change the output of the algorithm and then show that the output of the modified algorithm is .

Let , , and be three functions of y and other variables. It is evident that

If y is a regular variable, we also have

Consequently, the modifications do not change the output of the procedure.

Since the elimination ordering is legitimate, it is always the case that if a deputy variable has not been summed out, neither has the corresponding new regular variable e. Let , ..., be the remaining variables in at any time during the execution of the algorithm. Then, implies . This and the fact that the factorization represented by a deputation BN is tidy enable us to repeatedly apply Theorem 3 and conclude that, after the modifications, the factor created at step 3 is simply the marginal probability . Consequently, the output is .

Next: An Example Up: Exploiting Causal Independence in Previous: Tidy Heterogeneous Factorizations

David Poole
Fri Dec 6 15:09:32 PST 1996