AAAI Conference 2002 Conference Paper
Tree Approximation for Belief Updating
- Robert Mateescu
- and Kalev Kask
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.