A note on two simple transformations for improving the efficiency of and ILP system

Abstract

Inductive Logic Programming (ILP) systems have had noteworthy successes in extracting comprehensible and accurate models for data drawn from a number of scientific and engineering domains. These results suggest that ILP methods could enhance the model-construction capabilities of software tools being developed for the emerging discipline of knowledge discovery from databases.'' One significant concern in the use of ILP for this purpose is that of efficiency. The performance of modern ILP systems is principally affected by two issues: (1) they often have to search through very large numbers of possible rules (usually in the form of definite clauses); (2) they have to score each rule on the data\ (usually in the form of ground facts) to estimate goodness''. Stochastic and greedy a\ pproaches have been proposed to alleviate the complexity arising from each of these issu\ es. While these techniques can result in order-of-magnitude improvements in the worst-case search complexity of an ILP system, they do so at the expense o\ f exactness. As this may be unacceptable in some situations, we examine two meth\ ods that result in admissible transformations of clauses examined in a search. While the methods do not alter the size of the search space (that is, the number of clauses examined), they can alleviate\ the theorem-proving effort required to estimate goodness. The first transformation simply involves eliminating literals using a weak test for redundancy. The sec\ ond involves partitioning the set of literals within a clause into groups that can be executed independently of each other. The efficacy of these transformations are evaluated empirically on a number of well-known ILP datasets. The results suggest that the transformations can provide, under some circumstances, significant gains as the complexity of clauses sought increases.