Tree Approximation for Belief Updating

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Probabilistic and Causal Reasoning

The paper presents a parameterized approximation scheme for probabilistic inference. The scheme, called Mini-Clustering (MC), extends the partition-based approximation offered by mini-bucket elimination, to tree decompositions. The benefit of this extension is that all single-variable beliefs are computed (approximately) at once, using a two-phase message-passing process along the cluster tree. The resulting approximation scheme allows adjustable levels of accuracy and efficiency, in anytime style. Empirical evaluation against competing algorithms such as iterative belief propagation and Gibbs sampling demonstrates the potential of the MC approximation scheme for several classes of problems.