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:
- Higher-Order Definitions: It is pre-equipped with definitions for common patterns such as
map/3,until/4, andif-then-else (ite/5). - 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.
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.
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
droplasttask, Metagol$_{ho}$ invented a predicate to reverse a string, drop the head, and reverse it back, then successfully integrated it into amapcall. - 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