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 result-ing approximation scheme allows adjustable levels of accu-racy and efficiency, in anytime style. Empirical evaluation against competing algorithms such as iterative belief propa-gation and Gibbs sampling demonstrates the potential of the MC approximation scheme for several classes of problems. Introduction and related work Probabilistic reasoning using Belief networks, computing