Abstract
Traditional Inductive Logic Programming (ILP) systems typically rely on an "Occamist bias," which prioritizes the discovery of the shortest possible program that explains a given set of examples. However, in many practical domains—such as robotics, program synthesis, and real-time systems—textual brevity does not necessarily correlate with computational or operational efficiency. This paper introduces $Metagol_O$, a system designed to learn logic programs optimized for resource efficiency (e.g., execution time or action cost) rather than mere symbolic length.
Introduction
In the field of Inductive Logic Programming (ILP), the objective is to find a hypothesis—a logic program—that accounts for a set of provided examples. Historically, the search for these hypotheses has been guided by Occam’s Razor: the simplest explanation is usually the best. In algorithmic terms, this translates to searching for the program with the fewest rules or literals.
While effective for generalization, this bias ignores the resource complexity of the resulting program. For instance, a standard ILP learner might prefer a short implementation of Bubble Sort ($O(n^2)$) over a slightly longer implementation of Quick Sort ($O(n \log n)$) simply because the former uses fewer symbols. In robotics, this discrepancy is critical; a robot requires strategies that minimize physical actions, battery consumption, and time, rather than just code length. This research bridges the gap between learning "correct" programs and learning "efficient" ones.
The $Metagol_O$ Framework
$Metagol_O$ builds upon Meta-Interpretive Learning (MIL), a framework where a learner uses higher-order logic templates, known as metarules, to construct a program. The system introduces three key innovations to optimize for resource usage:
1. Resource Complexity Definition
Unlike standard learners that count symbols, $Metagol_O$ defines resource complexity as the total cost of all predicates invoked to solve a set of examples. For example, if a robot's "move" action is assigned a cost of 1 unit, a strategy requiring 10 moves is considered more complex than one requiring 5, regardless of the number of lines of code used to define the strategy.
2. Iterative Descent Search
Standard MIL systems ($Metagol_D$) use iterative deepening to find the shortest program. $Metagol_O$ replaces this with an Iterative Descent Search strategy:
- Initial Bound: The system first finds the shortest possible program ($H_1$) that solves the problem. This provides an initial upper bound for resource cost.
- Optimization Loop: The system then searches for a new program ($H_i$) that remains textually simple but enforces a maximum resource bound strictly lower than that of the previous program ($H_{i-1}$).
- Convergence: This process repeats until no program can be found that further reduces the resource cost, ensuring the final output is the most efficient within the search space.
3. Declarative Bias
The system operates within the $H^2_2$ fragment of Datalog. This fragment consists of programs with predicates of maximum arity 2 and at most 2 literals in the body. Despite these constraints, the fragment is known to be Turing expressive, providing a robust foundation for complex program synthesis.
Experimental Evaluation
The author evaluated $Metagol_O$ using two simulated robotic environments designed to test physical action optimization:
- Robot Postman: A navigation task where the agent must deliver items across various locations.
- Robot Mail Sorter: A task requiring the organization of items based on specific destination criteria.
In both scenarios, the goal was to discover strategies that minimize the number of physical movements. The experimental results demonstrated that $Metagol_O$ successfully converged on optimal resource-complexity strategies. Furthermore, the results were in strict agreement with theoretical optimal predictions, proving that the algorithm consistently identifies the most efficient program relative to the defined costs.
Discussion and Key Insights
Efficiency as a Primary Objective
A central insight of this work is that "quality" in machine learning should be an objective function that explicitly includes execution cost. This is particularly vital when logic programs interface with the physical world, where every "action" in the code corresponds to a real-world cost.
The Utility of the Shortest Program
Interestingly, $Metagol_O$ does not abandon the Occamist bias entirely. Instead, it uses the shortest program as a strategic starting point. Because the hypothesis space grows exponentially with program length, the shortest program is the most computationally efficient to find and serves as a necessary "ceiling" to begin the optimization process.
Provable Convergence
Unlike many heuristic-based policy optimization methods found in Reinforcement Learning, the $Metagol_O$ approach provides a provably convergent method for finding optimal strategies within the defined logic space. This offers a level of reliability and interpretability essential for safety-critical applications.
Limitations and Future Work
While promising, the current scope of $Metagol_O$ is limited to the $H^2_2$ Datalog fragment. Future research aims to generalize the framework to include "normal" logic programs, which allow for negation. Additionally, while the current experiments focus on robotic movement, the author suggests that classic computer science challenges—such as sorting—could be addressed by representing them as robot manipulations on a Turing machine tape. Finally, reducing the dependency on manually provided metarules remains a key area for future development to expand the types of programs the system can synthesize autonomously.
Summary updated