Improving inductive logic programming by using simulated annealing

Publication Type:
Journal Article
Citation:
Information Sciences, 2008, 178 (6), pp. 1423 - 1441
Issue Date:
2008-03-15
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013007914OK.pdfPublished Version284.7 kB
Adobe PDF
In Inductive Logic Programming (ILP), algorithms that are purely of the bottom-up or top-down type encounter several problems in practice. Since a majority of them are greedy ones, these algorithms stop when finding clauses in local optima, according to the "quality" measure used for evaluating the results. Moreover, when learning clauses one by one, the induced clauses become less and less interesting as the algorithm is progressing to cover few remaining examples. In this paper, we propose a simulated annealing framework to overcome these problems. Using a refinement operator, we define neighborhood relations on clauses and on hypotheses (i.e. sets of clauses). With these relations and appropriate quality measures, we show how to induce clauses (in a coverage approach), or to induce hypotheses directly by using simulated annealing algorithms. We discuss the necessary conditions on the refinement operators and the evaluation measures to increase the effectiveness of the algorithm. Implementations (included a parallelized version of the algorithm) are described and experimentation results in terms of convergence of the method and in terms of accuracy are presented. © 2007 Elsevier Inc. All rights reserved.
Please use this identifier to cite or link to this item: