Boolean Decision Rules via Column Generation

Abstract

This paper considers the learning of Boolean rules in either disjunctive normal form (DNF, OR-of-ANDs, equivalent to decision rule sets) or conjunctive normal form (CNF, AND-of-ORs) as an interpretable model for classification. An integer program is formulated to optimally trade classification accuracy for rule simplicity. Column generation (CG) is used to efficiently search over an exponential number of candidate clauses (conjunctions or disjunctions) without the need for heuristic rule mining. This approach also bounds the gap between the selected rule set and the best possible rule set on the training data. To handle large datasets, we propose an approximate CG algorithm using randomization. Compared to three recently proposed alternatives, the CG algorithm dominates the accuracy-simplicity trade-off in 7 out of 15 datasets. When maximized for accuracy, CG is competitive with rule learners designed for this purpose, sometimes finding significantly simpler solutions that are no less accurate.

Cited by in corpus (28)

• One Explanation Does Not Fit All: A Toolkit and Taxonomy of AI Explainability Techniques
• Rule Extraction in Unsupervised Anomaly Detection for Model Explainability: Application to OneClass SVM
• An Objective Metric for Explainable AI: How and Why to Estimate the Degree of Explainability
• Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead
• Model extraction from counterfactual explanations
• Generalized Linear Rule Models
• TED: Teaching AI to Explain its Decisions
• Transparency, Auditability and eXplainability of Machine Learning Models in Credit Scoring
• A Holistic Approach to Interpretability in Financial Lending: Models, Visualizations, and Summary-Explanations
• MEGEX: Data-Free Model Extraction Attack against Gradient-Based Explainable AI
• Interpretable and Fair Boolean Rule Sets via Column Generation
• Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach
• Learning Global Transparent Models Consistent with Local Contrastive Explanations
• Characterization of Overlap in Observational Studies
• Learning Fair Rule Lists
• Causal Rule Sets for Identifying Subgroups with Enhanced Treatment Effect
• Gaining Free or Low-Cost Transparency with Interpretable Partial Substitute
• LIBRE: Learning Interpretable Boolean Rule Ensembles
• Rule Covering for Interpretation and Boosting
• Controlling Neural Networks with Rule Representations
• IPBoost -- Non-Convex Boosting via Integer Programming
• Fair Decision Rules for Binary Classification
• Interpretable Companions for Black-Box Models
• Explaining the Behavior of Black-Box Prediction Algorithms with Causal Learning
• Teaching AI to Explain its Decisions Using Embeddings and Multi-Task Learning
• Computing Optimal Decision Sets with SAT
• Consumer-Driven Explanations for Machine Learning Decisions: An Empirical Study of Robustness
• Iterative Rule Extension for Logic Analysis of Data: an MILP-based heuristic to derive interpretable binary classification from large datasets