On the use of stochastic local search techniques to revise first-order logic theories from examples

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

Authors

Paes, A (Author) Other; Zaverucha, G (Author) Other; Costa, VS (Author) FCUP

Journal

Title: Machine Learning

Vol. 106

Pages: 197-241

ISSN: 0885-6125

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 4 Citations

Other information

Authenticus ID: P-00M-CZP

DOI: 10.1007/s10994-016-5595-3

Abstract (EN): Theory Revision from Examples is the process of repairing incorrect theories and/or improving incomplete theories from a set of examples. This process usually results in more accurate and comprehensible theories than purely inductive learning. However, so far, progress on the use of theory revision techniques has been limited by the large search space they yield. In this article, we argue that it is possible to reduce the search space of a theory revision system by introducing stochastic local search. More precisely, we introduce a number of stochastic local search components at the key steps of the revision process, and implement them on a state-of-the-art revision system that makes use of the most specific clause to constrain the search space. We show that with the use of these SLS techniques it is possible for the revision system to be executed in a feasible time, while still improving the initial theory and in a number of cases even reaching better accuracies than the deterministic revision process. Moreover, in some cases the revision process can be faster and still achieve better accuracies than an ILP system learning from an empty initial hypothesis or assuming an initial theory to be correct.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 45