|
Abstract:
Cost-based abduction (CBA) is an important AI formalism for representing knowledge under uncertainty. In CBA, the data to be explained is treated as a goal that is necessarily true, and it is to be proven through a set of hypotheses. Each hypothesis has a cost, called the assumability cost. In order to use this hypothesis to complete the proof of the goal we have to pay the associated cost to assume that this hypothesis is true. The optimal solution for a given CBA instance is the one that is associated with the least cost proof. The proof cost is the sum of all hypotheses that need to be assumed to complete the proof. The least cost proof for the goal is taken as the best explanation for the evidence. Finding the least cost proof for a given CBA system is an NP-Hard problem. Current methods suffer from exponential complexity, in the worst case, with the growth of the problem size. They also suffer from the noise associated with the observed hypotheses. Computational Intelligence (CI) approaches can provide us with scalable and noise tolerant methods for solving CBA instances. In this work, we present CI approaches to CBA. We use High Order Recurrent Neural Networks (HORNs) to solve CBA instances. Our objective is to go from a standard CBA form to a set of HORN connections through an intermediate representation of Penalty Logic. We present three methods to achieve such an objective, each method is an improvement over its predecessor in terms of the solution quality, time consumed and network size produced for the same CBA instance. Our results indicate that HORNs have a very high potential for solving CBA systems. Results for a randomly generated set of CBA instances for each method are presented. A comparison between each pair of methods is performed to illustrate the improvement from each method to the other.