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\u27s 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