# Computing Optimal Decision Sets with SAT

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2020.

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

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [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)
- [A Scalable Two Stage Approach to Computing Optimal Decision Sets](https://mlsanity.com/paper/2102.01904/) (2021)
- [Optimizing Binary Decision Diagrams with MaxSAT for classification](https://mlsanity.com/paper/2203.11386/) (2022)
- [Multiclass Optimal Classification Trees with SVM-splits](https://mlsanity.com/paper/2111.08674/) (2021)
- [Efficient Learning of Interpretable Classification Rules](https://mlsanity.com/paper/2205.06936/) (2022)
- [A Uniform Language to Explain Decision Trees](https://mlsanity.com/paper/2310.11636/) (2023)
- [Synthesizing Pareto-Optimal Interpretations for Black-Box Models](https://mlsanity.com/paper/2108.07307/) (2021)
- [A Mathematical Programming Approach to Optimal Classification Forests](https://mlsanity.com/paper/2211.10502/) (2022)
- [Model Explanations via the Axiomatic Causal Lens](https://mlsanity.com/paper/2109.03890/) (2021)
- [Rolling Lookahead Learning for Optimal Classification Trees](https://mlsanity.com/paper/2304.10830/) (2023)
- [Generating Global and Local Explanations for Tree-Ensemble Learning Methods by Answer Set Programming](https://mlsanity.com/paper/2410.11000/) (2024)
- [An Incremental MaxSAT-based Model to Learn Interpretable and Balanced Classification Rules](https://mlsanity.com/paper/2403.16418/) (2024)
- [Locally Pareto-Optimal Interpretations for Black-Box Machine Learning Models](https://mlsanity.com/paper/2508.15220/) (2025)
- [ExplAIner: A Declarative Query Language for Explaining Classification Models](https://mlsanity.com/paper/2607.06407/) (2026)

## Abstract (arXiv)

As machine learning is increasingly used to help make decisions, there is a demand for these decisions to be explainable. Arguably, the most explainable machine learning models use decision rules. This paper focuses on decision sets, a type of model with unordered rules, which explains each prediction with a single rule. In order to be easy for humans to understand, these rules must be concise. Earlier work on generating optimal decision sets first minimizes the number of rules, and then minimizes the number of literals, but the resulting rules can often be very large. Here we consider a better measure, namely the total size of the decision set in terms of literals. So we are not driven to a small set of rules which require a large number of literals. We provide the first approach to determine minimum-size decision sets that achieve minimum empirical risk and then investigate sparse alternatives where we trade accuracy for size. By finding optimal solutions we show we can build decision set classifiers that are almost as accurate as the best heuristic methods, but far more concise, and hence more explainable.