Eyal Shlomo Shimony

Computation of marginal probabilities in Bayes nets is central to numerous reasoning and automatic decision making systems. This paper presents a deterministic approximation scheme for this hard problem that supplies provably correct bounds by aggregating probability mass in independence-based (IB) assignments. The scheme presented refines recent work in belief updating for Bayes networks: attempts to approximate posterior probabilities by finding a small number of the highest probability complete (or perhaps evidentially supported) assignments. Under certain assumptions, the probability mass in the union of these assignments is sufficient to obtain a good approximation. Such methods are especially useful for highly connected networks, where the maximum clique size or the cutset size make many existing algorithms intractable. Since IB assignments contain fewer assigned variables, the probability mass in each assignment is greater than in the respective complete assignment. Thus, fewer IB assignments are sufficient, and a good approximation can be obtained more efficiently. Two classes of algorithms for finding the high probability IB assignments are suggested: best-first heuristic search and a special-purpose integer linear program (ILP). Since IB assignments may be overlapping events in probability space, accumulating the mass in a set of assignments may be hard. In the ILP variant, it is easy to avoid the problem by adding equations that prohibit overlap. In the best-first search algorithm, other schemes are necessary, but experimental results suggest that using inclusion-exclusion (potentially exponential-time in the worst case) in the overlap cases is not too expensive for most problem instances.