To make "black-box" machine learning models interpretable, a common strategy is to extract symbolic, human-readable "if-then" rules from their internal structures. For instance, Ishibuchi et al. demonstrated how to extract fuzzy classification rules from trained neural networks, while Takemura developed methods to extract rule sets from complex tree ensembles like Random Forests and Gradient Boosted Decision Trees.
However, a fundamental paradox emerges: when rules are directly extracted from high-performing models, the resulting rule sets suffer from rule explosion. Because complex models learn highly nuanced decision boundaries via thousands of mathematical splits or hyperplanes, translating these boundaries directly into logic creates massive, bloated, and overlapping rule bases. As noted by Okajima et al., without a mechanism to distill these rules, the resulting system remains too complex to provide the succinct justifications required for human review. Similarly, Dash et al. point out that automated rule mining often yields an unmanageable number of redundant or low-quality formulas.
To restore true interpretability, researchers use rule set simplification. This process operates at two primary levels: local simplification (cleaning up individual rules) and global minimization (compressing the entire rule base).
Local Simplification: Pruning Redundant Literals
An individual logical rule can easily become bogged down by unnecessary conditions (called literals) that add no predictive value. For example, a rule extracted from a deep decision tree might contain multiple redundant constraints on the same feature across different branches, or include conditions that are logically implied by other parts of the rule.
Local simplification algorithms evaluate individual rules to strip away these non-essential constraints. In the IMLI framework, Ghosh et al. introduced post-processing algorithms designed to identify and remove redundant literals that emerge during incremental training or feature discretization. In high-stakes domains like medicine, Lio et al. utilized redundancy elimination to shorten individual decision paths extracted from random forests, making them digestible for clinicians without altering the underlying diagnostic logic.
[Bloated Rule] IF (Age > 50) AND (BloodPressure > 140) AND (Age > 60) THEN Risk = High
↓
[Pruned Rule] IF (Age > 60) AND (BloodPressure > 140) THEN Risk = High
This concept of local refinement is also crucial when defining distinct subpopulations. For example, Al Rahwanji et al. applied a pruning process to remove non-contributory logical conditions from discovered survival subgroups, ensuring the final definitions remained interpretable for medical experts. By focusing on pure logic rather than the arbitrary order of algorithmic splits, McTavish demonstrated that logical minimization algorithms can uncover the most succinct representation of a model's logic, ensuring fairer evaluations of feature importance.
Global Minimization: Deduplication and Rule Merging
Even if every individual rule is concise, the entire set of rules can still be highly redundant. Multiple rules might cover overlapping data points, or some rules might be minor variations of a more general principle. Global minimization aims to compress the entire rule base simultaneously.
One effective strategy is to eliminate rules that are mathematically or logically dependent on others. Benard et al. designed the SIRUS algorithm to post-process extracted rules by removing any rule that operates as a linear combination of more frequent rules, significantly reducing cognitive load without sacrificing predictive power. This idea dates back to early machine learning frameworks; Gemello et al. introduced a simplification phase where components used for initial data characterization are systematically removed if they are not strictly necessary for class discrimination.
[Rule Set A] Rule 1: IF Income = Low THEN Risk = High
Rule 2: IF Income = Low AND Debt = High THEN Risk = High (Redundant)
↓
[Minimized] Rule 1: IF Income = Low THEN Risk = High
In fuzzy logic and continuous systems, global minimization often involves merging similar concepts or intervals:
- Prioritizing Generality: Ishibuchi et al. managed rule complexity by prioritizing general rules that utilize 'Don't Care' antecedents, effectively dropping hyper-specific rules.
- Fuzzy Set Merging: Mahfouf showed that merging highly similar fuzzy sets and deleting non-informative rules transforms dense rule bases into compact, transparent sets that human experts can validate against physical principles.
- Interval Subsumption: Shiraishi et al. periodically simplified fuzzy rules back into crisp intervals, which facilitated more effective subsumption and merging of redundant logic.
This global deduplication is equally vital when mining rules from software execution traces. Lo 0001 et al. demonstrated that applying redundancy elimination to mined temporal rules can reduce the final output size by up to 82%, making the underlying API specifications manageable for human inspection.
Algorithmic Frameworks for Rule Optimization
How do we systematically find the smallest, most accurate subset of rules from billions of possible combinations? This is fundamentally a combinatorial optimization problem, typically framed as finding a Pareto-optimal balance between fidelity (how well the rules match the original model) and complexity (how short the rules are).
Accuracy / Fidelity
^
| * (Original Bloated Rule Set)
| /
| * (Optimized Pareto Frontier: High Accuracy, Low Complexity)
| /
| *
+-----------------------------------> Complexity (Rule/Literal Count)
Several mathematical frameworks are used to navigate this trade-off:
Discrete and Combinatorial Optimization
Dash et al. framed rule selection as a constrained Linear Programming (LP) problem, generating highly compact rule sets that match the accuracy of neural models while training much faster. To provide formal guarantees of transparency and fairness, Ghosh leveraged MaxSAT and Mixed Integer Linear Programming (MILP) to learn succinct rule-based classifiers that avoid the long, unreadable strings of terms typical of standard Boolean logic.
Continuous and Line Search Optimization
For continuous architectures like Logic Explained Networks (LENs), Anthony et al. applied line search optimization to find the ideal balance between rule complexity and predictive fidelity, simplifying complex logical formulas by adjusting precision thresholds and removing outliers.
Evolutionary Algorithms and Heuristics
When the search space is non-differentiable or highly non-linear, evolutionary strategies excel. Singh et al. utilized genetic algorithms to automatically prune and discover a lean set of high-impact logic rules, preventing the exponential rule explosion typical of complex systems. Alternatively, Nock employed pruning techniques based on statistical heuristics to identify and discard components that capture noise rather than generalizable patterns.
Ultimately, whether refining graph neural network explanations as done by Morris et al. or streamlining distributed data streams as done by Za'in et al., these optimization frameworks ensure that symbolic models remain small enough for human verification while preserving high predictive performance.
Key Foundational Work
An Integrated Characterization and Discrimination Scheme to Improve Learning Efficiency in Large Data Sets (1989) — contributed 1 concept elements to this direction.
Neat Explanation of Proof Trees (1985) — contributed 1 concept elements to this direction.