Integrity constraints in ILP using a Monte Carlo approach

• Type: Article in International Scientific Journal
• Date: 1997

Authors

Jorge, A (Author) FEP; Brazdil, PB (Author) FEP

Journal

Title: Lecture Notes in Computer Science

Vol. 47

Pages: 229-244

ISSN: 0302-9743

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 3 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-001-CH8

DOI: 10.1007/3-540-63494-0_58

Abstract (EN): Many state-of-the-art ILP systems require large numbers of negative examples to avoid overgeneralization. This is a considerable disadvantage for many ILP applications, namely inductive program synthesis where relativelly small and sparse example sets are a more realistic scenario. Integrity constraints are first order clauses that can play the role of negative examples in an inductive process. One integrity constraint can replace a long list of ground negative examples. However, checking the consistency of a program with a set of integrity constraints usually involves heavy theorem-proving. We propose an efficient constraint satisfaction algorithm that applies to a wide variety of useful integrity constraints and uses a Monte Carlo strategy. It looks for inconsistencies by random generation of queries to the program. This method allows the use of integrity constraints instead of (or together with) negative examples. As a consequence programs to induce can be specified more rapidly by the user and the ILP system tends to obtain more accurate definitions. Average running times are not greatly affected by the use of integrity constraints compared to ground negative examples.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 16