confactors is exponentially smaller than the tables (where added variables are only relevant in narrow contexts). There are other cases where the table size for the confactors is the same as the table size in VE, and where the overhead for manipulating contexts will not make CVE competitive with the table-based methods.

Boutilier et al. (1996) present two algorithms to exploit structure. For the network transformation and clustering method, the example of Figure 1 is the worst case; no structure can be exploited after triangulation of the resulting graph. (The tree for E in Figure 3 is structurally identical to the tree for X(1) in Figure 2 of (Boutilier et al., 1996)). The structured cutset conditioning algorithm does well on this example. However, if the example is changed so that there are multiple (disconnected) copies of the same graph, the cutset conditioning algorithm is exponential in the number of copies, whereas the probabilistic partial evaluation algorithm is linear11.

This algorithm is most closely related to the tree-based algorithms for solving MDPs (Boutilier et al., 1995), but these work with much more restricted networks and with stringent assumptions on what is observable. CVE is simpler than the analogous algorithm by Boutilier (1997) for structured MDP with correlated action effects that represents conditional probabilities as trees. Section 4.12 shows why we can do better than the tree-based algorithms.

Poole (1997) gave an earlier version of rule-based VE, but it is more complicated in that it distinguished between the head and the body of rules as part of the inference (although the confactors for X correspond to the rules with X in the head). CVE is much more efficient than the rule-based VE
as it allows for faster indexing of tables. The notion of *absorption* was introduced by Zhang (1998), which motivated the work in a very different way. Zhang and Poole (1999) give a mathematical analysis of how context-specific independence can be exploited in terms of partial functions. The union-product is a formalization of the operation we are using between confactors. The current paper extends all of these in giving a specific algorithm showing how to combine the confactors and tables, gives a more general analysis of when we need to do confactor splitting and when we don't need to, gives a more sophisticated method to initialize absorption (maintaining the confactors for a variable) and gives a much more detailed empirical evaluation (with a new implementation). The ability to handle ones is also improved.

Finally the representation should be contrasted with that of Geiger and Heckerman (1996).

They use a similarity network that gives a global decomposition of a belief network; for different contexts they allow for different belief networks. We allow for a local decomposition of conditional probabilities. The algorithms are not very similar.

## 8. Conclusion

This paper has presented a method for computing posterior probabilities in belief networks that exhibit context-specific independence. This algorithm is an instance of variable elimination, but when we sum out a variable the tables produced may depend on different sets of variables in different contexts.

The main open problem is in finding good heuristics for elimination orderings (Bertelè and Brioschi, 1972). Finding a good elimination ordering is related to finding good triangulations in building compact junction trees, for which there are good heuristics (Kjærulff, 1990; Becker and Geiger, 1996). These are not directly applicable to contextual variable elimination (although there