Node Splitting: A Scheme for Generating Upper Bounds in Bayesian Networks

Abstract

We formulate in this paper the mini-bucket algorithm for approximate inference in terms of exact inference on an approximate model produced by splitting nodes in a Bayesian network. The new formulation leads to a number of theoretical and practical implications. First, we show that branchand- bound search algorithms that use minibucket bounds may operate in a drastically reduced search space. Second, we show that the proposed formulation inspires new minibucket heuristics and allows us to analyze existing heuristics from a new perspective. Finally, we show that this new formulation allows mini-bucket approximations to benefit from recent advances in exact inference, allowing one to significantly increase the reach of these approximations.

Appears in Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence (UAI2007)

References in corpus (5)

• On the optimality of tree-reweighted max-product message-passing
• Iterative Join-Graph Propagation
• A Variational Approach for Approximating Bayesian Networks by Edge Deletion
• Systematic vs. Non-systematic Algorithms for Solving the MPE Task
• Empirical Evaluation of Approximation Algorithms for Probabilistic Decoding