Computing optimal decision sets with SAT

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

Abstract

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
PublisherSpringer
Pages952-970
Number of pages19
ISBN (Electronic)9783030584757
ISBN (Print)9783030584740
DOIs
Publication statusPublished - 2020
EventInternational Conference on Principles and Practice of Constraint Programming 2020 - Louvain-la-Neuve, Belgium
Duration: 7 Sep 202011 Sep 2020
Conference number: 26th
https://link.springer.com/book/10.1007/978-3-030-58475-7 (Proceedings)
https://cp2020.a4cp.org (Website)

Publication series

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

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2020
Abbreviated titleCP2020
CountryBelgium
CityLouvain-la-Neuve
Period7/09/2011/09/20
Internet address

Cite this

Yu, J., Ignatiev, A., Stuckey, P. J., & Le Bodic, P. (2020). Computing optimal decision sets with SAT. In H. Simonis (Ed.), Principles and Practice of Constraint Programming: 26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings (pp. 952-970). (Lecture Notes in Computer Science ; Vol. 12333). Springer. https://doi.org/10.1007/978-3-030-58475-7_55