Cautious Induction: An Alternative to Clause-at-a-Time Hypothesis Construction in Inductive Logic Programming

The hypotheses constructed by Inductive Logic Programming (ILP) systems are logic programs that comprise a finite set of definite clauses. Much of the recent work in ILP has examined the question of how to find a single, high quality clause--- that is, one which accurately explains the classification of a set of given examples. Significantly less attention has been paid to the question of how to select a set of such clauses to form a high quality hypothesis. The usual method is to select clauses in a greedy manner: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set. This paper presents a non-greedy alternative for selecting the clauses that form a hypothesis. By separating the tasks of finding rules from combining them, Cautious Induction allows higher quality hypotheses to be found, with respect to a given hypothesis quality function. This claim is supported by the development of a top-down ILP system called CILS, and with a com..