An Anytime Scheme for Bounding Posterior Beliefs

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Uncertainty in AI

This paper presents an any-time scheme for computing lower and upper bounds on posterior marginals in Bayesian networks. The scheme draws from two previously proposed methods, bounded conditioning and bound propagation. Following the principles of cutset conditioning, our method enumerates a subset of cutset tuples and applies exact reasoning in the network instances conditioned on those tuples. The probability mass of the remaining tuples is bounded using a variant of bound propagation. We show that our new scheme improves on the earlier schemes.