Belief Updating by Enumerating High-Probability Independence-Based
  Assignments
  Independence-based (IB) assignments to Bayesian belief networks were
originally proposed as abductive explanations. IB assignments assign fewer
variables in abductive explanations than do schemes assigning values to all
evidentially supported variables. We use IB assignments to approximate marginal
probabilities in Bayesian belief networks. 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 the standard 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. IB assignments can be used for efficiently approximating posterior
node probabilities even in cases which do not obey the rather strict skewness
assumptions used in previous research. Two algorithms for finding the high
probability IB assignments are suggested: one by doing a best-first heuristic
search, and another by special-purpose integer linear programming. Experimental
results show that this approach is feasible for highly connected belief
networks.
