Compile the Hypothesis Space: Do it Once, Use it Often

• Tipo: Artigo em Revista Científica Internacional
• Data: 2008

Autores

Nuno A Fonseca (Autor) Outra; Rui Camacho (Autor) FEUP; Ricardo Rocha (Autor) FCUP; Vitor Santos Costa (Autor) FCUP

Revista

Título: Fundamenta Informaticae

Vol. 89

Páginas: 45-67

ISSN: 0169-2968

Editora: IOS PRESS

Indexação

ISI Web of Knowledge - 3 Citações

Scopus - 4 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-004-39W

Abstract (EN): Inductive Logic Programming (ILP) is a powerful and well-developed abstraction for multi-relational data mining techniques. Despite the considerable success of ILP, deployed ILP systems still have efficiency problems when applied to complex problems. In this paper we propose a novel technique that avoids the procedure of deducing each example to evaluate each constructed clause. The technique is based on the Mode Directed Inverse Entailment approach to ILP, where a bottom clause is generated for each example and the generated clauses are subsets of the literals of such bottom clause. We propose to store in a prefix-tree all clauses that can be generated from all bottom clauses together with some extra information. We show that this information is sufficient to estimate the number of examples that can be deduced from a clause and present an ILP algorithm that exploits this representation. We also present an extension of the algorithm where each prefix-tree is computed only once (compiled) per example. The evaluation of hypotheses requires only basic and efficient operations on trees. This proposal avoids re-computation of hypothesis' value in theory-level search, in cross-validation evaluation procedures and in parameter tuning. Both proposals are empirically evaluated on real applications and considerable speedups were observed.

Idioma: Inglês

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

Nº de páginas: 23