LIME: A System for Learning Relations

Abstract

This paper describes the design of the inductive logic programming system L ime . Instead of employing a greedy covering approach to constructing clauses, L ime employs a Bayesian heuristic to evaluate logic programs as hypotheses. The notion of a simple clause is introduced. These sets of literals may be viewed as subparts of clauses that are efiectively independent in terms of variables used. Instead of growing a clause one literal at a time, L ime efficiently combines simple clauses to construct a set of gainful candidate clauses. Subsets of these candidate clauses are evaluated via the Bayesian heuristic to find the final hypothesis. Details of the algorithms and data structures of L ime are discussed. L ime ’s handling of recursive logic programs is also described. Experimental results to illustrate how L ime achieves its design goals of better noise handling, learning from fixed set of examples (and from only positive data), and of learning recursive logic programs are provided. Experimental results comparing L ime with FOIL and PROGOL in the KRK domain in the presence of noise are presented. It is also shown that the already good noise handling performance of L ime further improves when learning recursive definitions in the presence of noise.