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

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2000

Autores

Vítor Santos Costa (Autor) Outra; Ashwin Srinivasan (Autor) Outra; Rui Camacho (Autor) FEUP

Ata de Conferência Internacional

Título: Proceedings of ILP 2000

Páginas: 225-242

Tenth International Conference on Inductive Logic Programming

Londres, 24 - JULHO - 2000

Indexação

Scopus

INSPEC

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Engenharia electrotécnica, electrónica e informática

CORDIS: Ciências Tecnológicas > Engenharia > Engenharia do conhecimento

Outras Informações

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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 18