# Efficient Learning of Interpretable Classification Rules

arXiv: https://arxiv.org/abs/2205.06936 · HTML: https://mlsanity.com/paper/2205.06936/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 96 references that are in the map.
- First posted on arXiv 14 May 2022.

## Builds on (most cited first, 28 of 28)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [Improving fairness in machine learning systems: What do industry practitioners need?](https://mlsanity.com/paper/1812.05239/) (2018)
- [Techniques for Interpretable Machine Learning](https://mlsanity.com/paper/1808.00033/) (2018)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [Local Rule-Based Explanations of Black Box Decision Systems](https://mlsanity.com/paper/1805.10820/) (2018)
- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [Revisiting Small Batch Training for Deep Neural Networks](https://mlsanity.com/paper/1804.07612/) (2018)
- [Falling Rule Lists](https://mlsanity.com/paper/1411.5899/) (2014)
- [Interpretable & Explorable Approximations of Black Box Models](https://mlsanity.com/paper/1707.01154/) (2017)
- [On Explaining Decision Trees](https://mlsanity.com/paper/2010.11034/) (2020)
- [Enhancing Robustness of Machine Learning Systems via Data Transformations](https://mlsanity.com/paper/1704.02654/) (2017)
- [Rule Extraction Algorithm for Deep Neural Networks: A Review](https://mlsanity.com/paper/1610.05267/) (2016)
- [Post-hoc explanation of black-box classifiers using confident itemsets](https://mlsanity.com/paper/2005.01992/) (2020)
- [Computing Optimal Decision Sets with SAT](https://mlsanity.com/paper/2007.15140/) (2020)
- [MLIC: A MaxSAT-Based framework for learning interpretable classification rules](https://mlsanity.com/paper/1812.01843/) (2018)
- [On Breast Cancer Detection: An Application of Machine Learning Algorithms on the Wisconsin Diagnostic Dataset](https://mlsanity.com/paper/1711.07831/) (2017)
- [LoRMIkA: Local rule-based model interpretability with k-optimal associations](https://mlsanity.com/paper/1908.03840/) (2019)
- [IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules](https://mlsanity.com/paper/2001.01891/) (2020)
- [A Scalable Two Stage Approach to Computing Optimal Decision Sets](https://mlsanity.com/paper/2102.01904/) (2021)
- [Law and Adversarial Machine Learning](https://mlsanity.com/paper/1810.10731/) (2018)
- [Rule Induction in Knowledge Graphs Using Linear Programming](https://mlsanity.com/paper/2110.08245/) (2021)
- [Optimal Decision Lists using SAT](https://mlsanity.com/paper/2010.09919/) (2020)

## Built on by (most cited first, 5 of 5)

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [Lightweight Deepfake Detection Based on Multi-Feature Fusion](https://mlsanity.com/paper/2502.11763/) (2025)
- [Concise and interpretable multi-label rule sets](https://mlsanity.com/paper/2210.01533/) (2022)
- ["Who experiences large model decay and why?" A Hierarchical Framework for Diagnosing Heterogeneous Performance Drift](https://mlsanity.com/paper/2506.00756/) (2025)
- [On Trustworthy Rule-Based Models and Explanations](https://mlsanity.com/paper/2507.07576/) (2025)

## Abstract (arXiv)

Machine learning has become omnipresent with applications in various safety-critical domains such as medical, law, and transportation. In these domains, high-stake decisions provided by machine learning necessitate researchers to design interpretable models, where the prediction is understandable to a human. In interpretable machine learning, rule-based classifiers are particularly effective in representing the decision boundary through a set of rules comprising input features. The interpretability of rule-based classifiers is in general related to the size of the rules, where smaller rules are considered more interpretable. To learn such a classifier, the brute-force direct approach is to consider an optimization problem that tries to learn the smallest classification rule that has close to maximum accuracy. This optimization problem is computationally intractable due to its combinatorial nature and thus, the problem is not scalable in large datasets. To this end, in this paper we study the triangular relationship among the accuracy, interpretability, and scalability of learning rule-based classifiers. The contribution of this paper is an interpretable learning framework IMLI, that is based on maximum satisfiability (MaxSAT) for synthesizing classification rules expressible in proposition logic. Despite the progress of MaxSAT solving in the last decade, the straightforward MaxSAT-based solution cannot scale. Therefore, we incorporate an efficient incremental learning technique inside the MaxSAT formulation by integrating mini-batch learning and iterative rule-learning. In our experiments, IMLI achieves the best balance among prediction accuracy, interpretability, and scalability. As an application, we deploy IMLI in learning popular interpretable classifiers such as decision lists and decision sets.