An Anytime Scheme for Bounding Posterior BeliefBozhena Bidyuk and Rina Dechter
This report 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 bounds propagation algorithm . 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.