Learning abductive reasoning using random examples

We consider a new formulation of abduction. Our formulation differs from the existing approaches in that it does not cast the “plausibility ” of ex-planations in terms of either syntactic minimality or an explicitly given prior distribution. Instead, “plausibility, ” along with the rules of the domain, is learned from concrete examples (settings of at-tributes). Our version of abduction thus falls in the “learning to reason ” framework of Khardon and Roth. Such approaches enable us to capture a natu-ral notion of “plausibility ” in a domain while avoid-ing the problem of specifying an explicit represen-tation of what is “plausible, ” a task that humans find extremely difficult. In this work, we specifically consider the question of which syntactic classes of formulas have effi-cient algorithms for abduction. It turns out that while the representation of the query is irrelevant to the computational complexity of our problem, the representation of the explanation critically affects its tractability. We find that the class of k-DNF ex-planations can be found in polynomial time for any fixed k; but, we also find evidence that even very weak versions of our abduction task are intractable for the usual class of conjunctive explanations. This evidence is provided by a connection to the usual, inductive PAC-learning model proposed by Valiant. We also briefly consider an exception-tolerant vari-ant of abduction. We observe that it is possible for polynomial-time algorithms to tolerate a few adver-sarially chosen exceptions, again for the class of k-DNF explanations. All of the algorithms we study are particularly simple, and indeed are variants of a rule proposed by Mill