Learning Higher-Order Logic Programs through Abstraction and Invention

Andrew Cropper, Stephen H. MuggletonIJCAI 2016

Abstract

Inductive Logic Programming (ILP) faces significant challenges with sample complexity and search space efficiency when restricted to first-order representations. This paper introduces Metagol$_{AI}$, a framework that utilizes higher-order logic to learn more compact and generalizable programs. By combining "Abstraction"—the use of higher-order templates like map and until—with "Invention"—the creation of new predicates to satisfy those templates—Metagol$_{AI}$ significantly outperforms traditional first-order ILP systems in terms of learning speed and predictive accuracy on complex procedural tasks.

Introduction

Inductive Programming (IP) aims to enable machines to learn general programs from a limited set of examples. A primary hurdle is the search space: learning programs using only basic first-order logic often results in long, textually complex rules. In machine learning, such complexity increases sample requirements and search time. This research explores whether higher-order concepts, similar to those used by human programmers (e.g., filter or fold), can make the learning process more efficient.

Methodology: Abstraction and Invention

Metagol$_{AI}$ extends the Meta-Interpretive Learning (MIL) framework. In standard MIL, a system uses metarules as templates to construct programs. Metagol$_{AI}$ introduces two key advancements:

  1. Abstraction: The system's background knowledge is extended with higher-order definitions such as until/4, map/3, and ifthenelse/5. These serve as high-level skeletons for the target program.
  2. Invention: When the system employs an abstraction, it must "invent" the specific logic required to fill that template for the given data.
The iterative process of alternating between abstraction and invention steps in Metagol$_{AI}$.

Technically, Metagol$_{AI}$ is a generalized meta-interpreter implemented in Prolog. It interleaves the selection of a high-level abstraction with the recursive definition of the sub-components needed to make that abstraction functional for the specific task.

Experimental Evaluation

The researchers evaluated Metagol$_{AI}$ on three symbolic logic tasks requiring procedural reasoning:

  • Robot Waiter: A robot learns a strategy to move along a table, turn over empty cups, and pour tea (T) or coffee (C) based on guest preference.
  • Chess Strategy: Learning to advance a pawn wall to the 8th rank while managing other pieces.
  • Drop Lasts: A list-processing task to remove the last element from every sublist within a nested list.
The Robot Waiter task: (a) initial state with empty cups and (b) final state after the robot has served the correct beverages.

These tasks represent "small data" challenges, where the system is provided with only 1 to 5 positive examples.

Key Insights and Results

Theoretical Compactness

The core insight is that higher-order programs are shorter. The authors demonstrate mathematically that reducing the number of clauses in a target program leads to an exponential reduction in the hypothesis space, making the search far more efficient.

Performance Gains

  • Sample Efficiency: In the Chess task, Metagol$_{AI}$ achieved nearly 100% accuracy with only 2 examples, while first-order versions struggled to reach 60% even with 5 examples.
  • Computational Speed: In the "Drop Lasts" task, first-order systems failed to find a solution within a 10-minute timeout. Metagol$_{AI}$ found a compact higher-order solution almost instantly.
  • Generalization: Programs using abstractions like until naturally generalize to different table lengths or list sizes, unlike specific "unrolled" recursive rules.

Conclusion and Future Work

Metagol$_{AI}$ demonstrates that higher-order logic is a powerful tool for Inductive Logic Programming. By interleaving abstraction and invention, the system achieves superior efficiency and generalization. Future research will focus on supporting the negation of invented predicates and exploring more relational higher-order constructs, such as a closure operator for transitive relationships.

Summary updated

BibTeX
@inproceedings{cropper2016learning,
  author = {Andrew Cropper and Stephen H. Muggleton},
  title = {{Learning Higher-Order Logic Programs through Abstraction and Invention}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure