SAT-Based Rigorous Explanations for Decision Lists
  Decision lists (DLs) find a wide range of uses for classification problems in
Machine Learning (ML), being implemented in a number 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.
