Tech Report CS-91-57

A Probabilistic Framework for Explanation

Solomon Eyal Shimony

August 1991

Abstract:

We present a wish list for a domain-independent theory of explanation under uncertainty, based on the research literature. We examine the prevalent explanation schemes in light of this list, and show why none of the currently used schemes are adequate for domain-independent explanation. In particular, we look at maximum a-posteriori (MAP) explanations (which suffer from the overspecification problem) and posterior probabilities (which may select inconsistent explanations).

We also consider one non-probabilistic scheme, cost-based abduction, but relate it to the probabilistic work by providing a probabilistic semantics for it, using Bayesian belief networks. We show that although this is a useful explanation scheme (a similar scheme, least-cost proofs, is used in Hobbs' and Stickel's TACITUS natural language understanding program), it makes independence assumptions that are not valid in the general case.

We then suggest a new theory, ``irrelevance-based MAPs'', a scheme where explanations are partial models, such that irrelevant variables are left unassigned. We propose and evaluate four instances of irrelevance-based MAPs: independence-based MAPs, delta independence-based MAPs, generalized delta independence-based MAPs and quasi-independence-based MAPs. We show that these schemes have the advantages of MAP explanations but do not exhibit the overspecification problem.

A best-first algorithm that generates explanations for the first two above schemes is presented. Implementations of the algorithm exhibit reasonable run-time behavior over a toy-domain set of problems, despite the fact that the problem of finding explanations is NP-hard. We demonstrate empirically that our independence-based MAP algorithm shows reasonable performance for up to medium-size problems, by experimenting on a set of randomly generated belief networks. Finally, we discuss alternate algorithms for computing irrelevance-based explanations: linear systems of inequalities and stochastic simulation.

(complete text in pdf)