The Automatic Computer Scientist

Andrew CropperAAAI 2023 · DOI

Abstract

While algorithms are the backbone of modern technology, their design remains a predominantly manual and grueling task for human computer scientists. This paper explores the research of Andrew Cropper into automating this process using Inductive Logic Programming (ILP). By introducing systems like Metagol and Popper, this research addresses the fundamental challenges of recursion, computational efficiency, and predicate invention. The results demonstrate a significant leap in the scalability of automated programming, with the Popper system achieving performance speeds 100 times faster than previous state-of-the-art methods.

Introduction

From sleep tracking to imaging black holes, algorithms are the primary engines of modern innovation. However, the discovery of novel, efficient algorithms is a bottleneck in technological progress. Traditional Machine Learning (ML) excels at statistical pattern recognition but often lacks the symbolic logic and rigorous efficiency required for complex algorithmic discovery. Inductive Logic Programming (ILP) offers a solution by combining logic programming with machine learning to induce programs from data. This paper summarizes the development of the "Automatic Computer Scientist," focusing on overcoming the historical limitations of ILP to create a system capable of autonomous algorithmic design.

The Grand Challenges of Automated Programming

To effectively automate the work of a computer scientist, an ILP system must overcome three "grand challenges":

  1. Recursion: The ability to learn programs that call themselves is essential for creating generalizable loops and handling dynamic data structures.
  2. Efficiency: In computer science, a "correct" program is not necessarily a good one. A system must be able to distinguish between a slow, naive solution (e.g., $O(n!)$) and an optimal one (e.g., $O(n \log n)$).
  3. Predicate Invention: For a system to solve complex problems, it must be able to "invent" its own high-level concepts or sub-routines—such as reverse or sort—and reuse them as building blocks for more sophisticated tasks.

Methodological Framework

Metagol: Logic and Efficiency

Metagol was developed to address the challenges of recursion and efficiency. It utilizes metarules—higher-order logical templates—to guide the search for recursive programs. Unlike earlier systems that might settle for any functional code, Metagol incorporates a technique that guarantees the discovery of the most computationally efficient program for a given problem. Furthermore, it utilizes predicate invention, allowing the AI to create and store new sub-functions for future use.

Popper: Learning From Failures (LFF)

To solve the scalability issues inherent in searching through the vast space of possible programs, the Popper system introduced the Learning From Failures (LFF) paradigm. Popper frames the search for a program as a Constraint Satisfaction Problem (CSP).

When the system tests a hypothesis and it fails—either because it is too general or too specific—it does not simply move to the next candidate. Instead, it generates a logical constraint that explains why the program failed. This allows the system to prune entire branches of the search space, eliminating thousands of potentially failing programs simultaneously. This "failure as a teacher" approach transforms the search process from an exhaustive hunt into a directed, logical elimination.

Evaluation and Results

Benchmarking

The systems were evaluated using a variety of benchmarks, including programming puzzles, algorithmic tasks (such as robot strategies and sorting), and string transformation programs. These tests were designed to measure the systems' ability to invent predicates and handle complex logic.

Key Findings

  • Scalability: Popper represents a massive leap in performance, capable of learning programs that are 10 times larger than those handled by previous systems.
  • Speed: By leveraging the LFF paradigm, Popper discovers solutions 100 times faster than previous state-of-the-art ILP approaches.
  • Functional Autonomy: The systems successfully demonstrated predicate invention, automatically creating reusable list operations like droplast when solving complex puzzles, mimicking the modular thinking of a human programmer.
  • Efficiency as a Constraint: By treating algorithmic complexity (Big O notation) as a primary constraint, the research ensures that the "Automatic Computer Scientist" prioritizes optimal solutions over merely functional ones.

Conclusion and Future Directions

The development of Metagol and Popper marks a significant milestone in the quest to automate computer science. By integrating symbolic logic with efficient search constraints, these systems have moved closer to the creative and rigorous standards of human algorithm design. While the complexity of programs discovered is currently limited compared to the vast library of human-designed algorithms, the trajectory of this research suggests a future where AI can significantly accelerate the discovery of the next generation of computational tools. Future work will likely focus on expanding these systems to handle increasingly complex data structures and further bridging the gap between automated logic and human-like creative leaps.

Summary updated

BibTeX
@inproceedings{cropper2023automatic,
  author = {Andrew Cropper},
  title = {{The Automatic Computer Scientist}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i13.26801},
}
Figure