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

• Type: Article in International Conference Proceedings Book
• Date: 2000

Authors

Vítor Santos Costa (Author) Other; Ashwin Srinivasan (Author) Other; Rui Camacho (Author) FEUP

Conference proceedings International

Title: Proceedings of ILP 2000

Pages: 225-242

Tenth International Conference on Inductive Logic Programming

Londres, 24 - JULHO - 2000

Indexing

Scopus

INSPEC

Scientific classification

FOS: Engineering and technology > Electrical engineering, Electronic engineering, Information engineering

CORDIS: Technological sciences > Engineering > Knowledge engineering

Other information

DOI: 10.1007/3-540-44960-4_14

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 18