Exploiting Case-Based Independence for Approximating Marginal Probabilities

Document Type


Publication Date



Computing marginal probabilities in Bayes networks is a hard problem. Deterministic anytime approximation schemes accumulate the probability mass in a small number of value assignments to the network variables. Under certain assumptions, the probability mass in the assignments is sufficient to obtain a good approximation. Such methods are especially useful for highly connected networks, where the topology makes the exact algorithms intractable. Bayes networks often possess a fine independence structure not evident from the topology, but apparent in local conditional distributions. Independence-based (IB) assignments, originally proposed as a theory of abduction, take advantage of such independence, and thus contain fewer assigned variables-and more probability mass. We present several algorithms that use IB assignments for approximating marginal probabilities. Experimental results suggest that this approach is feasible for highly connected belief networks. Abstract © Elsevier


The "Link to Full Text" button on this page loads the open access article version of record, hosted at Elsevier. The publisher retains permissions to re-use and distribute this article.



Source Publication

International Journal of Approximate Reasoning