Computing optimal decision sets with SAT

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

18 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings
EditorsHelmut Simonis
Place of PublicationCham Switzerland
Number of pages19
ISBN (Electronic)9783030584757
ISBN (Print)9783030584740
Publication statusPublished - 2020
EventInternational Conference on Principles and Practice of Constraint Programming 2020 - Louvain-la-Neuve, Belgium
Duration: 7 Sept 202011 Sept 2020
Conference number: 26th (Proceedings) (Website)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Principles and Practice of Constraint Programming 2020
Abbreviated titleCP2020
Internet address

Cite this