Introduction
Inductive Logic Programming (ILP) is a powerful paradigm in artificial intelligence that aims to learn logical rules from examples and background knowledge (BK). By combining the reasoning capabilities of logic with the learning capabilities of machine learning, ILP systems can induce human-readable hypotheses. However, these systems face a significant hurdle: the "curse of dimensionality." The space of possible logical rules is often astronomical, making exhaustive search impossible for complex domains.
To navigate this vast hypothesis space, researchers rely on "inductive bias"—a set of constraints that guide the search toward promising rules. Traditionally, these biases are manually specified by domain experts. However, manual bias engineering is a bottleneck; it is time-consuming, error-prone, and often fails to capture subtle properties of the data. This paper introduces DISCO, a system designed to automate the discovery of inductive bias directly from background knowledge.
The DISCO Framework
DISCO (Discovering Constraints) addresses the challenge of automated bias discovery by analyzing the background knowledge before the learning process begins. Built upon the POPPER ILP system, DISCO operates in two primary stages:
1. Property Identification
In the first stage, DISCO uses Answer Set Programming (ASP) to probe the background knowledge for relational properties and functional dependencies. It systematically checks for properties such as irreflexivity (ensuring no element relates to itself), asymmetry, and mutual exclusivity (identifying pairs of predicates that never apply to the same individual, such as even and odd).
2. Constraint Generation
Once these properties are identified, DISCO translates them into meta-level constraints. These constraints are then integrated into the ILP solver's search mechanism. By identifying "where not to search," DISCO prunes entire branches of the hypothesis space that are logically inconsistent with the background knowledge. Crucially, the authors prove that DISCO is optimally sound, meaning the system only prunes rules that are guaranteed to be unsatisfiable or non-optimal, ensuring the search for the "best" solution remains complete.
Experimental Evaluation
The researchers evaluated DISCO across a diverse set of benchmarks, including classic ILP tasks like Michalski Trains, real-world data from IMDB, and complex game logic from the Inductive General Game Playing (IGGP) suite. The results demonstrate that DISCO significantly outperforms the baseline system, POPPER, in terms of learning efficiency.
Performance Gains
In many tasks, DISCO achieved dramatic reductions in learning time. For instance, in the "buttons" game task, the learning time was slashed from 686 seconds to just 25 seconds—a 96% improvement. These speedups are attributed to the massive reduction in the number of rules the system needs to consider; in some tasks, the hypothesis space was reduced by over an order of magnitude.
Scalability to Large Datasets
One of the most impressive features of DISCO is its scalability. The time taken to discover constraints scales linearly with the number of facts in the background knowledge. The authors demonstrated that DISCO could process a background knowledge base containing 8 million facts in under 50 seconds. This capability allows ILP to be applied to much larger datasets than previously possible.
Conclusion and Future Work
DISCO represents a significant step forward in automating the ILP pipeline. By treating background knowledge as a source of structural constraints rather than just a library of facts, it effectively "maps the boundaries" of the search space. This pre-search pruning leads to massive speedups and improved scalability without sacrificing the optimality of the learned programs. Future research will focus on extending these techniques to handle noisy data and more complex recursive structures beyond the current Datalog restrictions.
Summary updated