Publications

BibTex format

@article{Cropper:2018:10.1007/s10994-018-5712-6,
author = {Cropper, A and Muggleton, SH},
doi = {10.1007/s10994-018-5712-6},
journal = {Machine Learning},
pages = {1--21},
title = {Learning efficient logic programs},
url = {http://dx.doi.org/10.1007/s10994-018-5712-6},
year = {2018}
}

Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - © 2018 The Author(s) When machine learning programs from data, we ideally want to learn efficient rather than inefficient programs. However, existing inductive logic programming (ILP) techniques cannot distinguish between the efficiencies of programs, such as permutation sort (n!) and merge sort (Formula presented.). To address this limitation, we introduce Metaopt, an ILP system which iteratively learns lower cost logic programs, each time further restricting the hypothesis space. We prove that given sufficiently large numbers of examples, Metaopt converges on minimal cost programs, and our experiments show that in practice only small numbers of examples are needed. To learn minimal time-complexity programs, including non-deterministic programs, we introduce a cost function called tree cost which measures the size of the SLD-tree searched when a program is given a goal. Our experiments on programming puzzles, robot strategies, and real-world string transformation problems show that Metaopt learns minimal cost programs. To our knowledge, Metaopt is the first machine learning approach that, given sufficient numbers of training examples, is guaranteed to learn minimal cost logic programs, including minimal time-complexity programs.
AU  - Cropper,A
AU  - Muggleton,SH
DO  - 10.1007/s10994-018-5712-6
EP  - 21
PY  - 2018///
SN  - 0885-6125
SP  - 1
TI  - Learning efficient logic programs
T2  - Machine Learning
UR  - http://dx.doi.org/10.1007/s10994-018-5712-6
ER  -

Download

ProfessorStephenMuggleton

Contact

Assistant

Location

Summary

Citation

BibTex format

RIS format (EndNote, RefMan)