Learning Recursive Relations with Randomly Selected Small Training Sets

Abstract

We evaluate CRUSTACEAN, an inductive logic programming algorithm that uses inverse implication to induce recursive clauses from examples. This approach is well suited for learning a class of self-recursive clauses, which commonly appear in logic programs, because it searches for common substructures among the examples. However, little evidence exists that inverse implication approaches perform well when given only randomly selected positive and negative examples. We show that CRUSTACEAN learns recursive relations with higher accuracies than GOLEM, yet with reasonable efficiency. We also demonstrate that increasing the number of randomly selected positive and negative examples increases its accuracy on randomly selected test examples, increases the frequency in which it outputs the target relation, and reduces its number of outputs. We also prove a theorem that defines the class of logic programs for which our approach is complete.