Abstract
The goal of Inductive Logic Programming (ILP) is to learn a program that explains a set of examples in the context of some pre-existing background knowledge. Until recently, most research on ILP targeted learning Prolog programs. Our own ILASP system instead learns Answer Set Programs, including normal rules, choice rules and hard and weak constraints. Learning such expressive programs widens the applicability of ILP considerably; for example, enabling preference learning, learning common-sense knowledge, including defaults and exceptions, and learning non-deterministic theories. In this paper, we first give a general overview of ILASP's learning framework and its capabilities. This is followed by a comprehensive summary of the evolution of the ILASP system, presenting the strengths and weaknesses of each version, with a particular emphasis on scalability.
Introduction
While Answer Set Programming (ASP) is a dominant paradigm for solving combinatorial and knowledge-intensive problems, writing these specifications is notoriously difficult for non-experts. Traditional Inductive Logic Programming (ILP) aims to automate the "learning" of programs from data, but most existing systems are limited to learning Prolog-style definite logic programs.
Prolog struggles with non-monotonic reasoning—handling defaults and exceptions—and cannot easily represent preferences or non-deterministic theories. The ILASP system addresses this gap by enabling the learning of the full expressive range of ASP. This allows for the automated discovery of logical specifications that include common-sense knowledge, complex constraints, and user preferences.
The ILASP Framework
ILASP defines a learning task through three primary components: Background Knowledge ($B$), a Mode Bias ($M$) defining the search space of possible rules, and a set of Examples ($E$). A key innovation of ILASP is the variety of examples it can process, which goes far beyond the simple positive/negative tuples of traditional ILP:
- Positive and Negative Examples: These are partial interpretations that must (or must not) be part of the program's answer sets.
- Context-dependent Examples: These allow examples to carry their own local background knowledge. This is essential for learning general concepts like "Hamiltonian graphs" from specific graph instances, as the background knowledge for one graph (its edges) should not interfere with another.
- Ordering Examples: These enable the system to learn weak constraints, effectively capturing user preferences by observing which solutions are favored over others.
The system has evolved through several algorithmic iterations to improve scalability. ILASP1 and ILASP2 were early batch learners that mapped tasks to large ASP programs solved by the Clingo solver. ILASP2i introduced an iterative approach that identifies a subset of "relevant examples." By focusing only on the examples needed to distinguish between hypotheses, it avoids grounding the entire dataset at once, leading to significant performance gains. ILASP3 was later designed for noisy data, translating examples into "coverage constraints" on the solution space, allowing the system to find an optimal program that balances program length against the penalty of mislabeled examples.
Applications and Datasets
The versatility of ILASP has been demonstrated across several domains rather than a single benchmark:
- Graph Theory: Learning definitions for properties like Hamiltonian graphs (see Figure 1).
- Preference Learning: Learning journey preferences (e.g., minimizing walking distance vs. avoiding high-crime areas) using ordering examples.
- Natural Language Processing: Applications in sentence chunking and machine comprehension.
- Other Domains: Event detection, game rule learning, and automata induction.
Key Insights and Results
ILASP's success stems from several core ideas:
- Brave vs. Cautious Reasoning: The authors prove that learning general ASP programs requires a combination of both brave reasoning (an example is covered by at least one answer set) and cautious reasoning (an example is covered by all answer sets).
- Conflict-Driven Learning: The system identifies "conflicts"—reasons why a hypothesis fails—and converts them into constraints that guide the solver toward an optimal solution.
- Optimization via Weak Constraints: Support for ordering examples moves ILP into the realm of optimization, allowing the system to learn what "best" means in a specific context.
In terms of performance, ILASP2i is over two orders of magnitude faster than ILASP2 on tasks with hundreds of examples. ILASP3 provides robust handling of large, noisy datasets where previous versions would fail or time out. The system successfully learns complex structures like choice rules and recursive definitions that are beyond the reach of most other ILP systems.
Conclusion and Future Work
The primary bottleneck for ILASP remains the size of the rule space. Current efforts like FastLAS aim to address this by identifying an "optimal-sufficient subset" of rules. Future work on ILASP4 aims to further refine the conflict-driven approach using "necessary" constraints to speed up iterations, while also lifting current restrictions on recursion and predicate invention.
Summary updated