The Variable Elimination Algorithm

Based on the discussions of the previous section, we present a simple algorithm for computing . The algorithm is based on the intuitions underlying D'Ambrosio's symbolic probabilistic inference (SPI) [31,24], and first appeared in Zhang and Poole [36]. It is essentially Dechter [9]'s bucket elimination algorithm for belief assessment.

The algorithm is called variable elimination (VE ) because it sums out variables from a list of factors one by one. An ordering by which variables outside to be summed out is required as an input. It is called an elimination ordering.

Procedure VE

• Inputs: --- The list of conditional probabilities in a BN;
  X --- A list of query variables;
  Y --- A list of observed variables;
  --- The corresponding list of observed values;
  --- An elimination ordering for variables outside .
• Output: .

1. Set the observed variables in all factors to their corresponding observed values.
2. While is not empty,
   1. Remove the first variable z from ,
   2. Call sum-out. Endwhile

3. Set h= the multiplication of all the factors on .
   /* h is a function of variables in X. */
4. Return . /* Renormalization */

Proof: Consider the following modifications to the procedure. First remove step 1. Then the factor h produced at step 3 will be 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.

Let be a function of variable y and of variables in A. We use to denote . Let , , and be three functions of y and other variables. It is evident that

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

According to Theorem 1, after the modifications the factor produced at step 3 is simply the marginal probability . Consequently, the output is exactly .

The complexity of VE can be measured by the number of numerical multiplications and numerical summations it performs. An optimal elimination ordering is one that results in the least complexity. The problem of finding an optimal elimination ordering is NP-complete [1]. Commonly used heuristics include minimum deficiency search [3] and maximum cardinality search [35]. Kjærulff [21] has empirically shown that minimum deficiency search is the best existing heuristic. We use minimum deficiency search in our experiments because we also found it to be better than the maximum cardinality search.

• VE versus Clique Tree Propagation