Learning Singly-Recursive Relations from Small Datasets

The inductive logic programming system LOPSTER was created to demonstrate the advantage of basing induction on logical implication rather than `-subsumption. LOPSTER's sub-unification procedures allow it to induce recursive relations using a minimum number of examples, whereas inductive logic programming algorithms based on `-subsumption require many more examples to solve induction tasks. However, LOPSTER's input examples must be carefully chosen; they must be along the same inverse resolution path. We hypothesize that an extension of LOPSTER can efficiently induce recursive relations without this requirement. We introduce a generalization of LOPSTER named CRUSTACEAN that has this capability and empirically evaluate its ability to induce recursive relations. 1 Introduction Several well-known inductive logic programming (ILP) algorithms are based on `- subsumption (e.g., Muggleton & Feng, 1990; Quinlan, 1991; Pazzani & Kibler, 1992). When inducing recursive clauses, the input exam..