Learning Logic Programs Though Divide, Constrain, and Conquer

Andrew CropperAAAI 2022 · DOI

Introduction

Inductive Logic Programming (ILP) aims to learn human-readable rules from examples, essentially "programming by example." Historically, ILP has faced a trade-off between scalability and expressivity. Classic "Divide-and-Conquer" systems scale well but struggle with complex features like recursion. Modern "Constraint-Driven" systems are expressive but suffer from exponential search space growth as programs become larger.

The DCC Framework

The Divide, Constrain, and Conquer (DCC) algorithm bridges this gap. It decomposes complex programming tasks into smaller sub-problems, reuses failures to prune the global search space, and iteratively builds the final program.

Three Phases of DCC

  1. Divide: Positive examples are partitioned into small "chunks."
  2. Constrain: DCC utilizes Learning From Failures (LFF). If a candidate rule fails on a small chunk, it generates a constraint. Since a rule failing on a subset will also fail on the whole dataset, these "failure lessons" effectively prune the search space for the entire problem.
  3. Conquer: Chunks are gradually merged. The accumulated constraints ensure that the search space for larger tasks remains manageable.

DCC also incorporates laziness (reusing rules that explain multiple examples) and compression (merging chunks explained by the same hypothesis) to optimize performance.

Experimental Evaluation

The system was evaluated on three domains:

  • Michalski Trains: Identifying train attributes, including complex variants (trains3, trains4).
  • Inductive General Game Playing (IGGP): Learning game rules (e.g., Rock Paper Scissors, Coins).
  • Program Synthesis: Learning recursive Prolog programs for list manipulation (e.g., dropk, sumlist).

Results and Discussion

DCC demonstrates significant improvements in both accuracy and scalability compared to state-of-the-art systems like POPPER, ALEPH, and METAGOL.

Predictive accuracy comparison across benchmarks showing DCC's superior performance on complex tasks.

On the most challenging tasks, such as trains4, DCC maintained 100% accuracy, while POPPER and ALEPH dropped to 42% and 39%, respectively. In the coins game, DCC achieved 86% accuracy, significantly outperforming the 17% achieved by all other systems.

Learning time comparison (in seconds) across benchmarks.

The efficiency gains are equally notable. For the trains1 task, DCC's optimizations reduced learning time to just 8 seconds, whereas METAGOL timed out at 300 seconds. DCC successfully learns programs with more literals and rules than previous constraint-driven systems, which typically fail beyond 5-6 rules.

Conclusion

DCC proves that failures are valuable. By solving for individual examples first, the system establishes lower bounds on program size and prunes impossible search paths. As an "anytime" algorithm, it provides robust performance even under time constraints, making it a powerful tool for learning complex, recursive logic programs.

Summary updated

BibTeX
@inproceedings{cropper2022learning,
  author = {Andrew Cropper},
  title = {{Learning Logic Programs Though Divide, Constrain, and Conquer}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i6.20596},
}
Figure