Abstract
Inductive Logic Programming (ILP) systems often struggle with noisy training data, leading to overfitting or failure to find solutions for complex tasks involving recursion and predicate invention. We present MAXSYNTH, a novel ILP system that leverages the Minimal Description Length (MDL) principle and MaxSAT optimization to learn robust logic programs. By treating misclassifications as a complexity cost, MAXSYNTH effectively balances program simplicity and predictive accuracy. Our evaluation across diverse domains demonstrates that MAXSYNTH significantly outperforms state-of-the-art systems in accuracy, noise robustness, and computational efficiency.
Introduction
Traditional Inductive Logic Programming (ILP) aims to induce human-readable logical rules from examples. However, these systems are notoriously sensitive to noise; even a small percentage of mislabeled examples can cause them to produce overly complex, overfitted models or fail entirely. This "glass jaw" is particularly problematic when learning sophisticated structures like recursive rules or invented predicates.
To address this, we introduce MAXSYNTH, a system designed to learn complex logic programs from imperfect data. By integrating the Minimal Description Length (MDL) principle into the "Learning From Failures" (LFF) framework, MAXSYNTH finds optimal programs that generalize well even in high-noise environments.
Methodology
The core of MAXSYNTH is an optimization-based approach to program synthesis that moves beyond greedy, rule-at-a-time learning.
The MDL Cost Function
MAXSYNTH employs an MDL-based objective function to guide its search. Instead of requiring a perfect fit for all training examples, it minimizes the total cost:
Cost = Program Size + False Positives + False Negatives
This approach acts as a mathematical Occam’s Razor, penalizing overly complex rules and allowing the system to ignore noisy outliers if explaining them would disproportionately increase program complexity.
MaxSAT Optimization and Pruning
The search for the optimal program is formulated as a Maximum Satisfiability (MaxSAT) problem. By using high-performance MaxSAT solvers, MAXSYNTH performs a global search over the program space. To maintain efficiency, the authors derived new "optimally sound" pruning constraints. Unlike traditional pruning, these constraints provide mathematical guarantees that allow the system to safely discard large portions of the search space that cannot possibly contain the MDL-optimal program, leading to significant speedups.
Experimental Evaluation
We evaluated MAXSYNTH against state-of-the-art ILP systems, ALEPH and POPPER, across five diverse domains:
- IGGP: Learning game rules (e.g., Rock-Paper-Scissors).
- Program Synthesis: Recursive list operations (e.g.,
sort,reverse,dropk). - Zendo: Inducing hidden arrangement rules.
- Real-world Datasets: Alzheimer’s drug design and the Wn18RR knowledge base.
Results and Analysis
MAXSYNTH demonstrated superior performance in both predictive accuracy and robustness to noise. While traditional systems often struggle once noise exceeds 10%, MAXSYNTH scales remarkably well, handling up to 30-40% noise in training data.
As shown in the table above, MAXSYNTH maintains high accuracy across most tasks even as noise increases. For instance, on the zendo4 task with 20% noise, MAXSYNTH achieves 94% accuracy, significantly higher than its competitors. It also successfully learned recursive programs like sort and reverse even when examples were corrupted.
Furthermore, MAXSYNTH exhibits remarkable efficiency. The introduction of noisy constraints reduced learning times by up to 99% in some tasks compared to unconstrained searches.
Conclusion
MAXSYNTH represents a significant advancement in noise-robust ILP. By combining MDL with global MaxSAT optimization, it successfully learns recursive programs from data with high noise levels that typically cause traditional systems to fail. Future work will explore alternative cost functions to further improve generalization and scale the system to even larger datasets.
Summary updated