Efficient Learning of Interpretable Classification Rules

Abstract

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.

arXiv comment41 Pages, Published in JAIR Vol. 74 (2022)

References in corpus (14)

• A Unified Approach to Interpreting Model Predictions
• Towards A Rigorous Science of Interpretable Machine Learning
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Revisiting Small Batch Training for Deep Neural Networks
• Local Rule-Based Explanations of Black Box Decision Systems
• Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods
• Post-hoc explanation of black-box classifiers using confident itemsets
• Learning Certifiably Optimal Rule Lists for Categorical Data
• Lagrangian Relaxation for MAP Estimation in Graphical Models
• Rule Extraction Algorithm for Deep Neural Networks: A Review
• MLIC: A MaxSAT-Based framework for learning interpretable classification rules
• SAT-based Encodings for Optimal Decision Trees with Explicit Paths