# A Scalable Two Stage Approach to Computing Optimal Decision Sets

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 49 references that are in the map.
- First posted on arXiv 3 Feb 2021.

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

- [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)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Reachability Analysis of Deep Neural Networks with Provable Guarantees](https://mlsanity.com/paper/1805.02242/) (2018)
- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [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)
- [IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules](https://mlsanity.com/paper/2001.01891/) (2020)

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

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [Eliminating The Impossible, Whatever Remains Must Be True](https://mlsanity.com/paper/2206.09551/) (2022)
- [Efficient Learning of Interpretable Classification Rules](https://mlsanity.com/paper/2205.06936/) (2022)
- [DeepSaDe: Learning Neural Networks that Guarantee Domain Constraint Satisfaction](https://mlsanity.com/paper/2303.01141/) (2023)
- [QUBO Decision Tree: Annealing Machine Extends Decision Tree Splitting](https://mlsanity.com/paper/2303.09772/) (2023)
- [Personalized Interpretable Classification](https://mlsanity.com/paper/2302.02528/) (2023)
- [Leveraging Association Rules for Better Predictions and Better Explanations](https://mlsanity.com/paper/2510.18628/) (2025)

## Abstract (arXiv)

Machine learning (ML) is ubiquitous in modern life. Since it is being deployed in technologies that affect our privacy and safety, it is often crucial to understand the reasoning behind its decisions, warranting the need for explainable AI. Rule-based models, such as decision trees, decision lists, and decision sets, are conventionally deemed to be the most interpretable. Recent work uses propositional satisfiability (SAT) solving (and its optimization variants) to generate minimum-size decision sets. Motivated by limited practical scalability of these earlier methods, this paper proposes a novel approach to learn minimum-size decision sets by enumerating individual rules of the target decision set independently of each other, and then solving a set cover problem to select a subset of rules. The approach makes use of modern maximum satisfiability and integer linear programming technologies. Experiments on a wide range of publicly available datasets demonstrate the advantage of the new approach over the state of the art in SAT-based decision set learning.