Induction of first-order decision lists: Results on learning the past tense of English

This paper presents a method for inducing logic programs from examples that learns a new class of concepts called rst-order decision lists, dened as ordered lists of clauses each ending in a cut. The method, called Foidl, is based on Foil (Quinlan, 1990) but employs intensional background knowledge and avoids the need for explicit negative ex-amples. It is particularly useful for problems that involve rules with specic exceptions, such as learning the past-tense of English verbs, a task widely studied in the context of the symbolic/connectionist debate. Foidl is able to learn concise, accurate programs for this problem from signicantly fewer examples than previous methods (both connectionist and symbolic). 1