Node Splitting: A Scheme for Generating Upper Bounds in Bayesian Networks
This work improves computational efficiency for probabilistic reasoning in AI systems, though it appears incremental as it builds on existing mini-bucket methods.
The paper tackles approximate inference in Bayesian networks by reformulating the mini-bucket algorithm as exact inference on an approximate model via node splitting, which reduces search space for branch-and-bound algorithms and enables leveraging advances in exact inference to extend the reach of approximations.
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.