# Learning Certifiably Optimal Rule Lists for Categorical Data

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2017.

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

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [TalkToModel: Explaining Machine Learning Models with Interactive Natural Language Conversations](https://mlsanity.com/paper/2207.04154/) (2022)
- [Leveraging Explanations in Interactive Machine Learning: An Overview](https://mlsanity.com/paper/2207.14526/) (2022)
- [Entropy-based Logic Explanations of Neural Networks](https://mlsanity.com/paper/2106.06804/) (2021)
- [GLocalX -- From Local to Global Explanations of Black Box AI Models](https://mlsanity.com/paper/2101.07685/) (2021)
- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [Augmenting Interpretable Models with LLMs during Training](https://mlsanity.com/paper/2209.11799/) (2022)
- [A Path to Simpler Models Starts With Noise](https://mlsanity.com/paper/2310.19726/) (2023)
- [Characterizing the risk of fairwashing](https://mlsanity.com/paper/2106.07504/) (2021)
- [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022)
- [FADE: FAir Double Ensemble Learning for Observable and Counterfactual Outcomes](https://mlsanity.com/paper/2109.00173/) (2021)
- [The Impact of Algorithmic Risk Assessments on Human Predictions and its Analysis via Crowdsourcing Studies](https://mlsanity.com/paper/2109.01443/) (2021)
- [Fast Interpretable Greedy-Tree Sums](https://mlsanity.com/paper/2201.11931/) (2022)
- [Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach](https://mlsanity.com/paper/2206.03718/) (2022)
- [Self-explaining deep models with logic rule reasoning](https://mlsanity.com/paper/2210.07024/) (2022)
- [Computing the Collection of Good Models for Rule Lists](https://mlsanity.com/paper/2204.11285/) (2022)
- [Learning Interpretable, High-Performing Policies for Autonomous Driving](https://mlsanity.com/paper/2202.02352/) (2022)
- [Interpretable and Fair Boolean Rule Sets via Column Generation](https://mlsanity.com/paper/2111.08466/) (2021)
- [Efficient Exploration of the Rashomon Set of Rule Set Models](https://mlsanity.com/paper/2406.03059/) (2024)
- [Differentiable Rule Induction with Learned Relational Features](https://mlsanity.com/paper/2201.06515/) (2022)
- [Explainable AI and Adoption of Financial Algorithmic Advisors: an Experimental Study](https://mlsanity.com/paper/2101.02555/) (2021)
- [A Scalable Two Stage Approach to Computing Optimal Decision Sets](https://mlsanity.com/paper/2102.01904/) (2021)
- [Probabilistic Dataset Reconstruction from Interpretable Models](https://mlsanity.com/paper/2308.15099/) (2023)
- [Better Short than Greedy: Interpretable Models through Optimal Rule Boosting](https://mlsanity.com/paper/2101.08380/) (2021)
- [Explainable Global Fairness Verification of Tree-Based Classifiers](https://mlsanity.com/paper/2209.13179/) (2022)
- [Robust subgroup discovery](https://mlsanity.com/paper/2103.13686/) (2021)
- [Fair Decision Rules for Binary Classification](https://mlsanity.com/paper/2107.01325/) (2021)
- [Mixed integer linear optimization formulations for learning optimal binary classification trees](https://mlsanity.com/paper/2206.04857/) (2022)
- [A Scalable, Interpretable, Verifiable & Differentiable Logic Gate Convolutional Neural Network Architecture From Truth Tables](https://mlsanity.com/paper/2208.08609/) (2022)

## Abstract (arXiv)

We present the design and implementation of a custom discrete optimization technique for building rule lists over a categorical feature space. Our algorithm produces rule lists with optimal training performance, according to the regularized empirical risk, with a certificate of optimality. By leveraging algorithmic bounds, efficient data structures, and computational reuse, we achieve several orders of magnitude speedup in time and a massive reduction of memory consumption. We demonstrate that our approach produces optimal rule lists on practical problems in seconds. Our results indicate that it is possible to construct optimal sparse rule lists that are approximately as accurate as the COMPAS proprietary risk prediction tool on data from Broward County, Florida, but that are completely interpretable. This framework is a novel alternative to CART and other decision tree methods for interpretable modeling.