Learning efficient logic programs
| Autor: | Andrew Cropper, Stephen H. Muggleton |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Class (computer programming)
Bubble sort Theoretical computer science Computer science business.industry media_common.quotation_subject 02 engineering and technology Machine learning computer.software_genre Resource (project management) Artificial Intelligence 020204 information systems 0202 electrical engineering electronic engineering information engineering sort 020201 artificial intelligence & image processing Simplicity Artificial intelligence business Time complexity computer Software media_common |
| Zdroj: | IJCAI |
| Popis: | 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 sortO(nlog n). 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 calledtree costwhich 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|