A SAT-based approach to learn explainable decision sets

Alexey Ignatiev, Filipe Pereira, Nina Narodytska, Joao Marques-Silva

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

20 Citations (Scopus)


The successes of machine learning in recent years have triggered a fast growing range of applications. In important settings, including safety critical applications and when transparency of decisions is paramount, accurate predictions do not suffice; one expects the machine learning model to also explain the predictions made, in forms understandable by human decision makers. Recent work proposed explainable models based on decision sets which can be viewed as unordered sets of rules, respecting some sort of rule non-overlap constraint. This paper investigates existing solutions for computing decision sets and identifies a number of drawbacks, related with rule overlap and succinctness of explanations, the accuracy of achieved results, but also the efficiency of proposed approaches. To address these drawbacks, the paper develops novel SAT-based solutions for learning decision sets. Experimental results on computing decision sets for representative datasets demonstrate that SAT enables solutions that are not only the most efficient, but also offer stronger guarantees in terms of rule non-overlap.

Original languageEnglish
Title of host publicationAutomated Reasoning
Subtitle of host publication9th International Joint Conference, IJCAR 2018 Held as Part of the Federated Logic Conference, FloC 2018 Oxford, UK, July 14–17, 2018 Proceedings
EditorsDidier Galmiche, Stephan Schulz, Roberto Sebastiani
Place of PublicationCham Switzerland
Number of pages19
ISBN (Electronic)9783319942056
ISBN (Print)9783319942049
Publication statusPublished - 2018
Externally publishedYes
EventInternational Joint Conference on Automated Reasoning 2018 - Oxford, United Kingdom
Duration: 14 Jul 201817 Jul 2018
Conference number: 9th

Publication series

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


ConferenceInternational Joint Conference on Automated Reasoning 2018
Abbreviated titleIJCAR 2018
CountryUnited Kingdom
Internet address

Cite this