Learning Abductive Reasoning Using Random Examples

We consider a new formulation of abduction in which degrees of "plausibility" of explanations, along with the rules of the domain, are learned from concrete examples (settings of attributes). Our version of abduction thus falls in the "learning to reason" framework of Khardon and Roth. Such approaches enable us to capture a natural notion of "plausibility" in a domain while avoiding the extremely difficult problem of specifying an explicit representation of what is "plausible." We specifically consider the question of which syntactic classes of formulas have efficient algorithms for abduction. We find that the class of k-DNF explanations can be found in polynomial time for any fixed k; but, we also find evidence that even weak versions of our abduction task are intractable for the usual class of conjunctions. This evidence is provided by a connection to the usual, inductive PAC-learning model proposed by Valiant. We also consider an exception-tolerant variant of abduction. We observe that it is possible for polynomial-time algorithms to tolerate a few adversarially 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