Learning Big Logical Rules by Joining Small Rules

Céline Hocquette, Andreas Niskanen, Rolf Morel, Matti Järvisalo, Andrew CropperIJCAI 2024

Abstract

Inductive Logic Programming (ILP) is a powerful paradigm for learning explainable, symbolic rules from small datasets. However, traditional ILP systems suffer from a "size problem," where the search space for logical rules grows exponentially with the number of conditions (literals). This paper introduces JOINER, a novel framework that overcomes this limitation by decomposing the learning of large rules into the generation and subsequent "joining" of smaller, non-splittable rule fragments using efficient SAT solvers.

The Challenge of Complexity in ILP

While deep learning excels with massive data, ILP is uniquely suited for domains where data is scarce but logic is complex, such as drug design or game strategy. Despite its potential, most state-of-the-art ILP systems fail when a rule requires more than 10 literals. Real-world patterns—like the specific chemical signature of a medicinal compound—often exceed this threshold. Existing systems typically time out or fail because they attempt to construct these massive rules in a single, exhaustive search.

The JOINER Architecture

JOINER addresses the scaling problem through a two-stage process inspired by divide-and-conquer strategies:

  1. Generating Small Rule Fragments: Instead of searching for a single perfect rule, JOINER identifies small, "non-splittable" rules. These are fragments where variables are tightly interconnected. While these fragments may be imperfect on their own, they capture essential components of the target logic.
  2. The Join Stage: JOINER utilizes Boolean satisfiability (SAT) and Maximum Satisfiability (MaxSAT) solvers to find the optimal conjunction of these fragments. The goal is to identify a subset of small rules whose intersection covers the maximum number of positive examples while entailing zero negative examples.

To further optimize the search, JOINER introduces a splittability constraint. By defining and pruning "splittable" rules during the generation phase, the system avoids redundant work that the Join stage can handle more efficiently, significantly reducing the search space.

Experimental Evaluation

JOINER was evaluated across several challenging domains, including Inductive General Game Playing (IGGP), relational movie data (IMDB), and visual reasoning tasks like Zendo.

Figure 3: Examples of Zendo structures, a domain requiring complex logical rules that JOINER successfully learns.

In the Zendo domain, for instance, the system must induce rules governing the placement and color of blocks. These rules are often highly complex, requiring the coordination of many different conditions.

Key Results

JOINER demonstrates a significant leap in the capability of ILP systems:

  • Scaling to 100+ Literals: JOINER successfully learned rules with over 100 literals in Zendo and string transformation tasks, where previous leaders like ALEPH and COMBO failed beyond 10 literals.
  • Superior Accuracy: Across 42 tasks, JOINER consistently outperformed existing approaches. In the pharma1 task, JOINER achieved 100% accuracy with a rule of size 17, while competing systems remained at baseline performance (50%).
  • Efficiency: The system proved an optimal solution for the iggp-rps task in just 20 seconds, compared to over 7 minutes for the previous state-of-the-art.
Figure 5: Performance comparison showing the significant accuracy improvement achieved by incorporating the join stage across various tasks.

As shown in the performance comparison, the addition of the Join stage allows the system to reach 100% accuracy on many tasks where the baseline (without the join stage) struggles to exceed 50%.

Conclusion and Future Work

JOINER proves that decomposing complex logical search into manageable sub-problems is a viable path for scaling symbolic AI. While currently optimized for "clean" data, future iterations aim to incorporate Minimal Description Length (MDL) principles to handle noise and integrate predicate invention to create even more compact and powerful logical models.

Summary updated

BibTeX
@inproceedings{hocquette2024learning,
  author = {Céline Hocquette and Andreas Niskanen and Rolf Morel and Matti Järvisalo and Andrew Cropper},
  title = {{Learning Big Logical Rules by Joining Small Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure