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.
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:
- Initialization: Starting with a specific theory that forbids patterns seen in negative examples.
- Compression via Mining: Utilizing the DCI_Closed algorithm to identify frequent sub-clauses.
- 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.
- 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.
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