mlsanityData to 14 Oct 2026

SAT-Based Rigorous Explanations for Decision Lists

arXiv 2105.06782 ↗First posted 14 May 2021cs.AI cs.LG cs.LOcited by 40

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 40 papers in the map (data through 14 Oct 2026). Builds on 19 of its 73 references that are in the map. First posted on arXiv 14 May 2021.

Builds on

19 of 73 references.

References · 19

  1. 2017A Unified Approach to Interpreting Model Predictionscited by 6,555
  2. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,166
  3. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,070
  4. 2017Explanation in Artificial Intelligence: Insights from the Social Sciencescited by 1,206
  5. 2016The Mythos of Model Interpretabilitycited by 721
  6. 2019Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methodscited by 443
  7. 2018Abduction-Based Explanations for Machine Learning Modelscited by 160
  8. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 131
  9. 2019"How do I fool you?": Manipulating User Trust via Misleading Black Box Explanationscited by 111
  10. 2020On The Reasons Behind Decisionscited by 100
  11. 2016Scalable Bayesian Rule Listscited by 64
  12. 2014Falling Rule Listscited by 59
7 more
  1. 2020Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delaycited by 57
  2. 2017Learning Certifiably Optimal Rule Lists for Categorical Datacited by 50
  3. 2020On Explaining Decision Treescited by 49
  4. 2019Can I Trust the Explainer? Verifying Post-hoc Explanatory Methodscited by 38
  5. 2019On Validating, Repairing and Refining Heuristic ML Explanationscited by 32
  6. 2017An Optimization Approach to Learning Falling Rule Listscited by 10
  7. 2016Propositional Abduction with Implicit Hitting Setscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 10; 2023: 9; 2024: 5; 2025: 5; 2026: 8.

40 papers.

Sort:

  1. 2021On Explaining Random Forests with SATcited by 57
  2. 2022Logic-Based Explainability in Machine Learningcited by 48
  3. 2022On Tackling Explanation Redundancy in Decision Treescited by 44
  4. 2022Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networkscited by 42
  5. 2021Explanations for Monotonic Classifierscited by 39
  6. 2021On Efficiently Explaining Graph-Based Classifierscited by 37
  7. 2022On Computing Probabilistic Explanations for Decision Treescited by 35
  8. 2023The Inadequacy of Shapley Values for Explainabilitycited by 31
  9. 2022ASTERYX : A model-Agnostic SaT-basEd appRoach for sYmbolic and score-based eXplanationscited by 26
  10. 2023Formally Explaining Neural Networks within Reactive Systemscited by 24
  11. 2022Eliminating The Impossible, Whatever Remains Must Be Truecited by 23
  12. 2022Feature Necessity & Relevancy in ML Classifier Explanationscited by 23
28 more
  1. 2022On Computing Probabilistic Abductive Explanationscited by 18
  2. 2023Delivering Inflated Explanationscited by 16
  3. 2023Disproving XAI Myths with Formal Methods -- Initial Resultscited by 12
  4. 2023On Formal Feature Attribution and Its Approximationcited by 11
  5. 2025Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanationscited by 10
  6. 2023Anytime Approximate Formal Feature Attributioncited by 9
  7. 2024Abductive explanations of classifiers under constraints: Complexity and propertiescited by 7
  8. 2022On Computing Relevant Features for Explaining NBCscited by 5
  9. 2023A Uniform Language to Explain Decision Treescited by 4
  10. 2023Inapproximability of sufficient reasons for decision treescited by 3
  11. 2024Axiomatic Characterisations of Sample-based Explainerscited by 3
  12. 2026FAME: Formal Abstract Minimal Explanation for Neural Networkscited by 3
  13. 2024Logic-Based Explainability: Past, Present & Futurecited by 2
  14. 2024Automated Explanation Selection for Scientific Discoverycited by 2
  15. 2024Learning Model Agnostic Explanations via Constraint Programmingcited by 2
  16. 2023Finding Minimum-Cost Explanations for Predictions made by Tree Ensemblescited by 1
  17. 2025Uncovering Bugs in Formal Explainers: A Case Study with PyXAIcited by 1
  18. 2025Extracting Robust Register Automata from Neural Networks over Data Sequencescited by 1
  19. 2026Concept-Based Abductive and Contrastive Explanations for Behaviors of Vision Modelscited by 1
  20. 2022A Model-Agnostic SAT-based Approach for Symbolic Explanation Enumerationcited by 0
  21. 2025Interpretable DNFscited by 0
  22. 2025Efficient & Correct Predictive Equivalence for Decision Treescited by 0
  23. 2026On the Hardness of Computing Counterfactual and Semifactual Explanations in XAIcited by 0
  24. 2026Rigorous Explanations for Tree Ensemblescited by 0
  25. 2026Towards Verified and Targeted Explanations through Formal Methodscited by 0
  26. 2026Towards Rigorous Explainability by Feature Attributioncited by 0
  27. 2026Fairness of Classifiers in the Presence of Constraints between Featurescited by 0
  28. 2026ExplAIner: A Declarative Query Language for Explaining Classification Modelscited by 0