A Connectionist Approach to Cost-Based Abduction


Cost-based abduction (CBA) is an important NP-hard problem in automated reasoning. in this formalism, evidence to be explained is treated as a goal to be proven. Proofs have costs based on how much needs to be assumed to complete the proof, and the set of assumptions needed to complete the leastcost proof are taken as the best explanation for the given evidence. in this paper, we present a connectionist approach to cost-based abduction. We begin by reviewing high order recurrent networks (HORN) and their use in combinatorial optimization. We then formally define the cost-based abduction problem and describe previous work on this problem. This is followed by a description of how HORN's can be applied to the CBA problem and experimental results on a 60-hypothesis, 65-rule CBA problem. We conclude with some remarks on the potential advantages of the connectionist approach.


Electrical and Computer Engineering

Keywords and Phrases

Bayesian Belief Network; High Order Network; Neural Network; Probabilistic Reasoning; Recurrent Network; Explanation

Document Type

Article - Journal

Document Version


File Type





© 2005 Yang's Scientific Research Institute, LLC., All rights reserved.

Publication Date

01 Jun 2005