On the Importance of Elimination Heuristics in Lazy Propagation

Belief update in a Bayesian network using Lazy Propagation (LP) proceeds by message passing over a junction tree (JT). In the process of computing a message, a set of variables is eliminated. As the JT provides only a partial order on the elimination of variables, it is necessary to identify elimination orders on-line. This paper considers the importance of elimination heuristics in LP when using Variable Elimination (VE) as the message and single marginal computation algorithm. It considers well-known cost measures for selecting the next variable to eliminate and a new cost measure. The empirical evaluation examines dierent heuristics as well as sequences of cost measures, and was conducted on real-world and randomly generated Bayesian networks. The results show that for most cases performance is robust relative to the cost measure used and in some cases the elimination heuristic can have a signicant impact on performance, especially for JTs that are non-optimal