Methods for Constructing Balanced Elimination Trees and Other Recursive Decompositions

Kevin Grant, Michael C. Horsch

A conditioning graph is a form of recursive factorization which minimizes the memory requirements and simplifies the implementation of inference in Bayesian networks. The time complexity for inference in conditioning graphs has been shown to be O(n exp(d)) where d is the depth of the underlying elimination tree. We demonstrate in this paper techniques for building small elimination trees. We give a simple method for deriving elimination trees for Darwiche et al.'s dtrees. We also give two new heuristics for building small elimination trees. We show that these heuristics, combined with a constructive process for building e-trees produces the smaller trees.

Subjects: 3.4 Probabilistic Reasoning; 15.1 Belief Revision

Submitted: Feb 15, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.