Published on Tue Apr 21 2020

Learning large logic programs by going beyond entailment

Andrew Cropper, Sebastijan Dumančić

A major challenge in inductive logic programming (ILP) is learning large programs. We argue that a key limitation of existing systems is that they use entailment to guide the hypothesis search. This approach is limited because a hypothesis either entails an example or does not, and there is

0
0
0
Abstract

A major challenge in inductive logic programming (ILP) is learning large programs. We argue that a key limitation of existing systems is that they use entailment to guide the hypothesis search. This approach is limited because entailment is a binary decision: a hypothesis either entails an example or does not, and there is no intermediate position. To address this limitation, we go beyond entailment and use \emph{example-dependent} loss functions to guide the search, where a hypothesis can partially cover an example. We implement our idea in Brute, a new ILP system which uses best-first search, guided by an example-dependent loss function, to incrementally build programs. Our experiments on three diverse program synthesis domains (robot planning, string transformations, and ASCII art), show that Brute can substantially outperform existing ILP systems, both in terms of predictive accuracies and learning times, and can learn programs 20 times larger than state-of-the-art systems.

Sun Jan 03 2021
Artificial Intelligence
Learning General Policies from Small Examples Without Supervision
Generalized planning is concerned with the computation of general policies that solve multiple instances of a planning domain all at once. The new formulation is very simple and can be cast in terms that are more standard in machine learning.
0
0
0
Mon Feb 22 2021
Artificial Intelligence
Program Synthesis Guided Reinforcement Learning
A key challenge for reinforcement learning is solving long-horizon planning and control problems. We propose an approach that averages program synthesis to automatically generate the guiding program. Our approach significantly outperforms several baselines, and performs essentially as well as an oracle given an effective program.
0
0
0
Thu Apr 18 2019
Artificial Intelligence
Playgol: learning programs through play
Children learn though play. We introduce the analogous idea of learning programs through play. In this approach, a program induction system is given a set of tasks and initial background knowledge. Before solving the tasks, the learner enters an unsupervised playing stage where it creates its own programs.
0
0
0
Wed Apr 21 2021
Artificial Intelligence
Exploiting Learned Policies in Focal Search
0
0
0
Fri Sep 09 2011
Artificial Intelligence
Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators
In many domains, the performance of a planner can be improved by discovering and exploiting information about the domain that is not explicitly encoded in the initial PDDL formulation. We have successfully used such an approach in the fourth international planning competition IPC-4.
0
0
0
Mon Sep 25 2017
Artificial Intelligence
Glass-Box Program Synthesis: A Machine Learning Approach
We present an intelligent search system which learns, given the partial program and the glass-box problem, the probabilities over the space of programs. We empirically demonstrate that our informed search procedure leads to significant improvements compared to brute-force program search, both in terms of accuracy and time.
0
0
0