SAT-based rigorous explanations for Decision Lists

Alexey Ignatiev, Joao Marques-Silva

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

26 Citations (Scopus)


Decision lists (DLs) find a wide range of uses for classification problems in Machine Learning (ML), being implemented in anumber of ML frameworks. DLs are often perceived as interpretable. However, building on recent results for decision trees (DTs), we argue that interpretability is an elusive goal for some DLs. As a result, for some uses of DLs, it will be important to compute (rigorous) explanations. Unfortunately, and in clear contrast with the case of DTs, this paper shows that computing explanations for DLs is computationally hard. Motivated by this result, the paper proposes propositional encodings for computing abductive explanations (AXps) and contrastive explanations (CXps) of DLs. Furthermore, the paper investigates the practical efficiency of a MARCO-like approach for enumerating explanations. The experimental results demonstrate that, for DLs used in practical settings, the use of SAT oracles offers a very efficient solution, and that complete enumeration of explanations is most often feasible.

Original languageEnglish
Title of host publicationTheory and Applications of Satisfiability Testing – SAT 2021
Subtitle of host publication24th International Conference Barcelona, Spain, July 5–9, 2021 Proceedings
EditorsChu-Min Li, Felip Manyà
Place of PublicationCham Switzerland
Number of pages19
ISBN (Electronic)9783030802233
ISBN (Print)9783030802226
Publication statusPublished - 2021
EventInternational Conference on Theory and Applications of Satisfiability Testing 2021 - Barcelona, Spain
Duration: 5 Jul 20219 Jul 2021
Conference number: 24th (Proceedings)

Publication series

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


ConferenceInternational Conference on Theory and Applications of Satisfiability Testing 2021
Abbreviated titleSAT 2021
Internet address

Cite this