Learning Higher-Order Programs through Predicate Invention

Andrew Cropper, Rolf Morel, Stephen H. MuggletonAAAI 2020 · DOI

Abstract

Inductive Logic Programming (ILP) typically focuses on learning first-order programs, which often results in complex, recursive code that is difficult to search for and requires extensive training data. This paper introduces Metagol$_{ho}$, a novel system that leverages higher-order logic and predicate invention to learn concise programs using abstractions like map and until. By reducing the hypothesis space, Metagol$_{ho}$ achieves significantly higher predictive accuracy and faster learning times compared to traditional first-order learners.

Introduction

Traditional ILP systems struggle with "boilerplate-heavy" code. For instance, learning to decrypt a list of words requires a first-order learner to simultaneously solve the decryption logic and the list traversal recursion. In contrast, functional programming uses higher-order functions like map to abstract away traversal. However, for an AI to utilize map(List, Result, Function), it must also "invent" the specific Function to apply. This research addresses the challenge of enabling ILP systems to learn these higher-order abstractions while automatically inventing necessary sub-programs.

Methods

The researchers extended the Meta-Interpretive Learning (MIL) framework to create Metagol$_{ho}$. The system incorporates two primary innovations:

  1. Higher-Order Definitions: It is pre-equipped with definitions for common patterns such as map/3, until/4, and if-then-else (ite/5).
  2. Higher-Order Predicate Invention: Metagol$_{ho}$ can invent brand-new predicates (e.g., f1) to serve as arguments for higher-order functions, rather than requiring these arguments to be predefined.

Theoretical analysis of sample complexity demonstrates that using higher-order abstractions shrinks the hypothesis space, allowing the learner to converge on correct solutions with fewer examples.

Evaluation and Results

The system was evaluated on three tasks: Caesar Cipher Decryption, Robot Waiter (planning), and Droplast (list processing). These tasks contrast manual recursion with abstracted iteration.

Figure 1: Comparison of predictive accuracies and learning times between Metagol and Metagol$_{ho}$ across general tasks.

Metagol$_{ho}$ consistently outperformed the standard Metagol system. In the Robot Waiter and Droplast experiments, it achieved 100% accuracy with as few as 2–5 training examples. The efficiency gains were most notable in the Droplast task, where the standard first-order Metagol failed to find any solution within the time limit due to the massive search space of recursive versions.

Figure 6: Performance on the Droplast task, where Metagol$_{ho}$ maintains 100% accuracy and near-instant learning times, while standard Metagol fails to solve the problem.

Key Insights

  • Abstraction as Inductive Bias: Higher-order predicates guide the learner to assume a structure (like map), focusing the search on specific transformation logic.
  • Predicate Invention: The system's ability to invent sub-functions is critical. In the droplast task, Metagol$_{ho}$ invented a predicate to reverse a string, drop the head, and reverse it back, then successfully integrated it into a map call.
  • Search Space Efficiency: Higher-order programs are shorter in terms of logic clauses. Since ILP search complexity is exponential relative to program length, shorter programs are found exponentially faster.

Conclusion and Future Work

Metagol$_{ho}$ demonstrates that higher-order logic significantly enhances ILP performance. Current limitations include the reliance on pre-defined abstractions like map. Future research aims to enable systems to "invent the abstractions" themselves by identifying repeated patterns in learned code to create new higher-order templates automatically.

Summary updated

BibTeX
@inproceedings{cropper2020learning,
  author = {Andrew Cropper and Rolf Morel and Stephen H. Muggleton},
  title = {{Learning Higher-Order Programs through Predicate Invention}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i09.7113},
}
Figure