  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.
