are analogous heuristics that are applicable), as an important criteria in this case is the exact form of the confactors, and not just the graphical structure of the belief network. This means that it is not feasible to compute the elimination ordering a priori. We are also investigating anarchic orderings where we eliminate a variable in some contexts, without eliminating it in every context before we partially eliminate another variable. We believe that this opportunistic elimination of variables in contexts has much potential to improve efficiency without affecting correctness.

One of the main potential benefits of this algorithm is in approximation algorithms, where the confactors allow fine-grained control over distinctions. Complementary confactors with similar probabilities can be collapsed into a simpler confactor. This can potentially lead to more compact confactor bases, and reasonable posterior ranges (Dearden and Boutilier, 1997; Poole, 1998).

The work reported in this paper has been followed up by a number of researchers. Tung (2002)
has shown how to exploit context-specific independence in clique trees. Guestrin, Venkataraman and Koller (2002) extended the contextual variable elimination to multi-agent coordination and planning.

## Acknowledgements

This work was supported by the Institute for Robotics and Intelligent Systems, Natural Sciences and Engineering Research Council of Canada Research Grant OGPOO44121 and Hong Kong Research Grants Council grant HKUST6093/99E. Thanks to Rita Sharma, Holger Hoos, Michael Horsch and the anonymous reviewers for valuable comments, and to Valerie McRae for careful proofreading.

The code is available from the first author.

## Appendix A. Details Of The Experiments A.1 Water Network

In order to construct a pseudo-natural example, we used the *water* network from the Bayesian network repository12 and modified it to let it exhibit context-specific independence. For each table, a variable was declared redundant if the differences in the probabilities for the values of this variable were less than a threshold of 0.05 from each other (thus, if we chose the midpoint of a reduced table, the original probabilities were all less than 0.025 from this midpoint). In order to discover context-specific independence, we carried out a greedy top-down algorithm to build a decision tree.

If we are building the conditional for variable Xi, we chose the variable Y to split on that results in the maximum number of pairs of numbers where the values for Xi are within the threshold 0.05 of each other. We then recursively remove redundant variables from each side, and keep splitting. Once we have built a tree, for each node, we can decide whether to use the tabular representation or a factored representation. In these experiments, we only committed to the context-based representation when the total size of the context-based representation (obtained simply by summing the sizes of the tables) was less than 51% of the tabular representation.

It should be noted that these thresholds were not chosen arbitrarily. If we used 0.03 instead of 0.05, we didn't find any context-specific independence. If we chose 0.07 instead of 0.05, then the tabular representation collapses. If we chose 80% or 99% instead of 51% as the threshold for accepting a change, we got smaller tables, but much larger run times.