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 .
- 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: .
- Set the observed variables in all factors to their observed values.
- While is not empty,
- Remove the first variable z from .
- . Endwhile
- Set h=multiplication of all factors in
combination (by ) of all factors in .
/* h is a function of variables in X. */
- 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 .