Tree Approximation for Belief Updating

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.

Authors

• Robert Mateescu Rina Dechter
• and Kalev Kask University of California

Keywords

No keywords are indexed for this paper.