# Boolean Decision Rules via Column Generation

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

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2018.

## Built on by (most cited first, 30 of 80)

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Benchmarking and Survey of Explanation Methods for Black Box Models](https://mlsanity.com/paper/2102.13076/) (2021)
- [Leveraging Explanations in Interactive Machine Learning: An Overview](https://mlsanity.com/paper/2207.14526/) (2022)
- [The Who in XAI: How AI Background Shapes Perceptions of AI Explanations](https://mlsanity.com/paper/2107.13509/) (2021)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [MEGEX: Data-Free Model Extraction Attack against Gradient-Based Explainable AI](https://mlsanity.com/paper/2107.08909/) (2021)
- [Learning Accurate and Interpretable Decision Rule Sets from Neural Networks](https://mlsanity.com/paper/2103.02826/) (2021)
- [A Holistic Approach to Interpretability in Financial Lending: Models, Visualizations, and Summary-Explanations](https://mlsanity.com/paper/2106.02605/) (2021)
- [Controlling Neural Networks with Rule Representations](https://mlsanity.com/paper/2106.07804/) (2021)
- [From Black Boxes to Conversations: Incorporating XAI in a Conversational Agent](https://mlsanity.com/paper/2209.02552/) (2022)
- [Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach](https://mlsanity.com/paper/2206.03718/) (2022)
- [Explaining Network Intrusion Detection System Using Explainable AI Framework](https://mlsanity.com/paper/2103.07110/) (2021)
- [Efficient Decompositional Rule Extraction for Deep Neural Networks](https://mlsanity.com/paper/2111.12628/) (2021)
- [Interpretable Clustering via Multi-Polytope Machines](https://mlsanity.com/paper/2112.05653/) (2021)
- [Interpretable and Fair Boolean Rule Sets via Column Generation](https://mlsanity.com/paper/2111.08466/) (2021)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Scalable Optimal Multiway-Split Decision Trees with Constraints](https://mlsanity.com/paper/2302.06812/) (2023)
- [AI Explainability 360: Impact and Design](https://mlsanity.com/paper/2109.12151/) (2021)
- [Differentiable Rule Induction with Learned Relational Features](https://mlsanity.com/paper/2201.06515/) (2022)
- [A Scalable Two Stage Approach to Computing Optimal Decision Sets](https://mlsanity.com/paper/2102.01904/) (2021)
- [Efficient learning of large sets of locally optimal classification rules](https://mlsanity.com/paper/2301.09936/) (2023)
- [Truly Unordered Probabilistic Rule Sets for Multi-class Classification](https://mlsanity.com/paper/2206.08804/) (2022)
- [Interpretable Regional Descriptors: Hyperbox-Based Local Explanations](https://mlsanity.com/paper/2305.02780/) (2023)
- [Zero-shot learning approach to adaptive Cybersecurity using Explainable AI](https://mlsanity.com/paper/2106.14647/) (2021)
- [Visual Exploration of Machine Learning Model Behavior with Hierarchical Surrogate Rule Sets](https://mlsanity.com/paper/2201.07724/) (2022)
- [User Driven Model Adjustment via Boolean Rule Explanations](https://mlsanity.com/paper/2203.15071/) (2022)
- [Finding Interpretable Class-Specific Patterns through Efficient Neural Search](https://mlsanity.com/paper/2312.04311/) (2023)
- [Learning Cut Generating Functions for Integer Programming](https://mlsanity.com/paper/2405.13992/) (2024)
- [Rule Generation for Classification: Scalability, Interpretability, and Fairness](https://mlsanity.com/paper/2104.10751/) (2021)
- [Fair Decision Rules for Binary Classification](https://mlsanity.com/paper/2107.01325/) (2021)

## Abstract (arXiv)

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.