AcknowledgementsTopComparison With Other ProposalsConclusion


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 [2]. Finding a good elimination ordering is related to finding good triangulations in building compact junction trees, for which there are good heuristics [19][1]. These are not directly applicable to contextual variable elimination (although there 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 [10][26].

The work reported in this paper has been followed up by a number of researchers. [30] has shown how to exploit context-specific independence in clique trees. [15] extended the contextual variable elimination to multi-agent coordination and planning.

David Poole and Nevin Lianwen Zhang,Exploiting Contextual Independence In Probabilistic Inference, Journal of Artificial Intelligence Research, 18, 2003, 263-313.

AcknowledgementsTopComparison With Other ProposalsConclusion