Node Splitting: A Scheme for Generating Upper Bounds in Bayesian Networks
Arthur Choi, Mark Chavira, Adnan Darwiche
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.
PDF Link: /papers/07/p57-choi.pdf
AUTHOR = "Arthur Choi
and Mark Chavira and Adnan Darwiche",
TITLE = "Node Splitting: A Scheme for Generating Upper Bounds in Bayesian Networks",
BOOKTITLE = "Proceedings of the Twenty-Third Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-07)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2007",
PAGES = "57--66"