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 at-tributes). Our version of abduction thus falls in the “learn-ing to reason ” framework of Khardon and Roth. Such ap-proaches enable us to capture a natural notion of “plausibil-ity ” in a domain while avoiding the extremely difficult prob-lem of specifying an explicit representation of what is “plau-sible.” 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 pro-vided 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 in-deed are variants of a rule proposed by Mill.