Bozhena Bidyuk, Rina Dechter
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.
Subjects: 3. Automated Reasoning; 3.4 Probabilistic Reasoning