| | | Conclusion |
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.
| | | Conclusion |