Constraint-Driven Learning of Logic Programs

Rolf MorelAAAI 2021 · DOI

Abstract

Inductive Logic Programming (ILP) is a subfield of machine learning concerned with the synthesis of logic programs from examples. Despite its potential for learning interpretable and recursive models, ILP systems often struggle with the vast search space of possible programs. This paper presents a "Learning From Failures" (LFF) framework and its implementation, Popper. By leveraging logical constraints to prune the hypothesis space, Popper achieves a balance between expressivity and scalability, outperforming existing state-of-the-art systems in complex program synthesis tasks.

Introduction

The fundamental goal of Inductive Logic Programming (ILP) is to automatically generate a logic program—a set of rules—that correctly classifies a given set of positive and negative examples. For instance, given examples of sorted and unsorted lists, an ILP system should be able to synthesize the logic for a sorting algorithm. However, the field faces two primary hurdles: ensuring the functional correctness of synthesized programs and managing the "hypothesis space," which is the astronomically large set of all possible programs.

Historically, ILP systems have been divided into two categories: those that are computationally efficient but limited in expressivity (often unable to handle recursion), and those that are highly expressive but fail to scale when the data domain becomes large. This research introduces a middle ground through a constraint-driven approach that maintains expressivity without sacrificing performance.

The Learning From Failures (LFF) Framework

The core contribution of this work is the Learning From Failures (LFF) framework, implemented in the Popper system. Popper operates through a three-stage iterative loop designed to efficiently navigate the search space:

  1. Generate: An Answer Set Programming (ASP) solver generates a potential program (a hypothesis). A key innovation here is that the solver focuses exclusively on the syntax of the program, remaining "ignorant" of the actual data. This decoupling prevents the solver from being overwhelmed by large data domains.
  2. Test: The generated hypothesis is executed against the training examples using a Prolog engine to check for correctness.
  3. Constrain: If the hypothesis fails—either by failing to cover a positive example or by incorrectly covering a negative one—the system derives logical constraints. These constraints are then fed back into the ASP solver for the next iteration.

Pruning via Subsumption and Failure Explanation

Popper does not merely ban a single failing program. Instead, it uses subsumption to prune entire classes of related programs. If a program is found to be too general (covering negative examples), the system can prune all even more general versions of that program. Conversely, if a program is too specific (missing positive examples), all more specific versions are eliminated.

Furthermore, the system utilizes Failure Explanation. By identifying the specific sub-programs or "literals" responsible for a failure, Popper can eliminate significantly larger chunks of the hypothesis space in a single iteration. This process effectively externalizes the conflict-driven learning found in modern SAT solvers, making the search process both transparent and highly efficient.

Evaluation

Popper was evaluated against state-of-the-art ILP systems, including ILASP and Metagol, across several classic domains:

  • Number Theory: Learning mathematical properties and relations.
  • Robot Strategies: Synthesizing rules for autonomous agent behavior.
  • List Transformations: Common programming tasks such as reversing or sorting lists.

Key Results

Experimental results demonstrate that Popper consistently outperforms ILASP and Metagol in terms of both speed and the complexity of the programs it can learn. Because Popper does not encode the full example domain into the ASP formula, it demonstrates superior scalability, handling infinite domains and complex data structures that typically cause other SAT-based systems to fail. The inclusion of failure explanations was shown to drastically reduce both the size of the hypothesis space and the total time required for learning.

Conclusion and Future Work

Popper represents a significant step forward in making ILP systems practical for real-world synthesis tasks. By treating failure as a highly informative signal for pruning, the LFF framework allows for the efficient discovery of complex, recursive logic programs.

Future research will focus on two primary enhancements to the Popper system:

  1. Refinement Types: Integrating functional correctness guarantees (e.g., ensuring an output list matches the length of an input list) directly into the constraints.
  2. Complexity Bounds: Developing constraints to eliminate programs that are correct but computationally inefficient, ensuring that synthesized solutions meet specific performance criteria.

These advancements aim to push ILP toward solving synthesis problems that are currently beyond the reach of the state-of-the-art.

Summary updated

BibTeX
@inproceedings{morel2021constraint,
  author = {Rolf Morel},
  title = {{Constraint-Driven Learning of Logic Programs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i18.17860},
}
Figure