Abstract
Inductive Logic Programming (ILP) systems often struggle to learn rules involving universal quantification, such as "all objects satisfy a property." This paper introduces NOPI (Negation and Predicate Invention), a system that overcomes this limitation by defining a new class of "polar programs" and a "polar subsumption" relation. These innovations allow NOPI to efficiently search for non-monotonic logic programs, achieving state-of-the-art performance in accuracy and speed across complex domains like Zendo, graph theory, and set operations.
Introduction: The Challenge of Universal Quantification
In Inductive Logic Programming (ILP), the goal is to learn human-readable rules from examples. However, most ILP systems struggle with universal quantification. For instance, if the target rule is "all cones are red," a standard system might learn a series of specific rules like "there are two red cones" or "there are three red cones," failing to capture the general "all" concept.
To express "all $X$ are $Y$," logic requires negation: "there does not exist an $X$ that is not $Y$." While adding negation seems straightforward, it introduces two significant hurdles:
- Search Space Explosion: Negation vastly increases the number of possible rules the system must evaluate.
- Broken Pruning: Standard ILP relies on "subsumption" to prune the search space. In non-monotonic logic (logic with negation), these pruning rules often fail, making the search computationally intractable.
The NOPI Framework
The authors address these challenges by introducing NOPI, which builds upon the "Learning From Failures" (LFF) framework. NOPI incorporates several key innovations:
Polar Programs
The authors define a fragment of logic programs where every head predicate symbol has a consistent "polarity" (either positive or negative). This structure captures the expressiveness of Datalog with stratified negation while maintaining mathematical properties that facilitate efficient searching.
Polar Subsumption
This is the core technical contribution. The authors prove a new subsumption relation that remains valid even with negation. By "flipping" the comparison logic for negative rules, the system can soundly prune the search space without missing optimal solutions.
Predicate Invention (PI)
NOPI can create its own intermediate concepts. To learn "all cones are red," NOPI might invent a predicate inv1 meaning "a cone that is not red" and then define the final rule as the negation of inv1. This combination of negation and PI is what enables the representation of universal quantification ($\forall \equiv \neg \exists \neg$).
Experimental Evaluation
NOPI was evaluated across four diverse domains:
- Zendo (Z): Pattern discovery in block structures (e.g., "all objects are red").
- Graphs (G): Graph theory problems like "dominating set" or "connectedness."
- Sets (S): Operations like symmetric difference and mutual distinctness.
- Basic (B): Standard non-monotonic tasks like defining a leap year.
Key Results
- Superior Accuracy: NOPI achieved 100% accuracy on almost all tasks in the Zendo, Graph, and Set domains, significantly outperforming baseline systems like POPPER, ALEPH, and METAGOL.
- Efficiency: The polar constraints were highly effective; for instance, in the "symmetric difference" task, NOPI was 57% faster than a version without these specific pruning constraints.
- Complex Rule Discovery: NOPI successfully learned rules with multiple layers of negation and invented predicates, such as "the largest object is red," which exceeds the capabilities of current literature.
Discussion and Future Work
The core insight of NOPI is that universal quantification is naturally represented by combining negation with predicate invention. By forcing programs to be "polar," the authors restrict the language just enough to make learning efficient without losing representational power.
However, there are limitations. NOPI currently spends approximately 30% of its time building polar constraints, an implementation bottleneck. Furthermore, on simple tasks that do not require negation or PI, NOPI can be slower than simpler systems due to the expanded search space (the "Blumer bound" problem). Future work aims to develop mechanisms for the system to automatically detect problem complexity and adjust its search strategy accordingly.
Summary updated