Learning CNF Theories Using MDL and Predicate Invention

Arcchit Jain, Clément Gautrais, Angelika Kimmig, Luc De Raedt

Introduction

Learning logical theories from examples is a fundamental challenge in machine learning. While most research has historically focused on Disjunctive Normal Form (DNF) or specific logic programs like Prolog, learning Conjunctive Normal Form (CNF) theories—conjunctions of constraints—remains computationally difficult. This difficulty is compounded when dealing with "partial" data, where the truth values of variables are not fully known for every example.

Mistle (Minimal SAT Theory Learner) is a novel algorithm designed to bridge this gap. By integrating frequent pattern mining with the Minimum Description Length (MDL) principle and "predicate invention," Mistle generates compact, human-readable theories that excel in both data description and classification tasks.

The Mistle Framework

Mistle is built on the MDL principle: the optimal theory is the one that minimizes the total length of the theory description plus the data encoded with that theory. This approach allows Mistle to balance model complexity with empirical fit, effectively handling the trade-off between compression and generalization.

Table 1: Comparison of key features between Mistle and existing logical theory learners.

As shown in Table 1, Mistle distinguishes itself from existing tools like KRIMP and Mining4SAT by its ability to generalize theories, learn from partial data, and perform predicate invention. The algorithm follows a structured four-step process:

  1. Initialization: Starting with a specific theory that forbids patterns seen in negative examples.
  2. Compression via Mining: Utilizing the DCI_Closed algorithm to identify frequent sub-clauses.
  3. Logical Operators: Applying operators such as the W-operator (for predicate invention) and the V-operator (for generalization via inverse resolution) to simplify the theory.
  4. Pruning: Removing clauses that do not contribute to predictive power or compression.

Experimental Results

The authors evaluated Mistle using synthetic data to test ground-truth recovery and 17 UCI datasets to assess real-world performance.

Performance on Synthetic Data

In synthetic tests, Mistle demonstrated remarkable robustness. It recovered original theories with near-perfect accuracy, even in the presence of significant missing data.

Figure 1: Mistle's accuracy remains high across varying numbers of examples, missingness levels, and variables.

As illustrated in Figure 1, the algorithm's accuracy remains stable as the number of variables increases and is highly resilient to the "missingness parameter," maintaining high performance even when a large portion of the data is incomplete.

Real-World Benchmarks

On UCI datasets, Mistle achieved a mean compression rate of 90.8%, significantly outperforming KRIMP (42.5%) and Mining4SAT (22.6%). While its classification accuracy was slightly lower than KRIMP on some noisy datasets (82.4% vs 85.6%), Mistle produced theories that were orders of magnitude smaller and far more interpretable. For instance, on the TicTacToe dataset, Mistle achieved 100% accuracy by identifying the eight logical ways to win the game.

Conclusion and Future Work

Mistle represents a significant step forward in learning interpretable logical theories. By treating predicate invention as a compression mechanism, it aligns inductive logic programming with information theory. Future work aims to address current computational overheads and extend the framework to First-Order Logic, enabling the learning of complex relations beyond simple propositional assignments.

Summary updated

Abstract

We revisit the problem of learning logical theories from examples, one of the most quintessential problems in machine learning. More specifically, we develop an approach to learn CNF-formulae from satisfiability. This is a setting in which the examples correspond to partial interpretations and an example is classified as positive when it is logically consistent with the theory. We present a novel algorithm, called Mistle -- Minimal SAT Theory Learner, for learning such theories. The distinguishing features are that 1) Mistle performs predicate invention and inverse resolution, 2) is based on the MDL principle to compress the data, and 3) combines this with frequent pattern mining to find the most interesting theories. The experiments demonstrate that Mistle can learn CNF theories accurately and works well in tasks involving compression and classification.
BibTeX
@inproceedings{jain2021learning,
  author = {Arcchit Jain and Clément Gautrais and Angelika Kimmig and Luc De Raedt},
  title = {{Learning CNF Theories Using MDL and Predicate Invention}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/358},
}

Loading related content...

Figure