Tech Report CS-90-02

Probabilistic Semantics for Cost-Based Abduction

Eugene Charniak and Solomon E. Shimony

February 1990


Cost-based abduction attempts to find the best explanation for a set of facts by finding a minimal-cost proof for the facts. The costs are computed by summing the cost of the assumptions necessary for the proof plus the cost of the rules. We examine existing methods for constructing explanations (proofs) as a minimization problem on a DAG. We then define a probabilistic semantics for the costs, and prove the equivalence of the cost-minimization problem to the Bayesian-network-MAP solution of the system.

(complete text in pdf)