Learning large logic programs by going beyond entailment
This addresses a key bottleneck in ILP for domains like robot planning and string transformations, offering a novel approach to scale program learning.
The paper tackles the challenge of learning large logic programs in inductive logic programming by moving beyond binary entailment to use example-dependent loss functions for partial coverage, resulting in a system that learns programs 20 times larger and outperforms existing systems in accuracy and speed.
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.