mlsanityData to 7 Oct 2026

Logic for Explainable AI

arXiv 2305.05172 ↗First posted 9 May 2023cs.AI cs.LG cs.LOcited by 23

Not on the map. Why?

Abstract (arXiv)

A central quest in explainable AI relates to understanding the decisions made by (learned) classifiers. There are three dimensions of this understanding that have been receiving significant attention in recent years. The first dimension relates to characterizing conditions on instances that are necessary and sufficient for decisions, therefore providing abstractions of instances that can be viewed as the "reasons behind decisions." The next dimension relates to characterizing minimal conditions that are sufficient for a decision, therefore identifying maximal aspects of the instance that are irrelevant to the decision. The last dimension relates to characterizing minimal conditions that are necessary for a decision, therefore identifying minimal perturbations to the instance that yield alternate decisions. We discuss in this tutorial a comprehensive, semantical and computational theory of explainability along these dimensions which is based on some recent developments in symbolic logic. The tutorial will also discuss how this theory is particularly applicable to non-symbolic classifiers such as those based on Bayesian networks, decision trees, random forests and some types of neural networks.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 38 of its 60 references that are in the map. First posted on arXiv 9 May 2023.

Builds on

38 of 60 references.

References · 38

  1. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,040
  2. 2017Explanation in Artificial Intelligence: Insights from the Social Sciencescited by 1,201
  3. 2017Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPRcited by 1,086
  4. 2019Explaining Machine Learning Classifiers through Diverse Counterfactual Explanationscited by 612
  5. 2019Counterfactual Visual Explanationscited by 312
  6. 2020Counterfactual Explanations and Algorithmic Recourses for Machine Learning: A Reviewcited by 174
  7. 2018Abduction-Based Explanations for Machine Learning Modelscited by 159
  8. 2018Explaining Explanations in AIcited by 136
  9. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 130
  10. 2020On The Reasons Behind Decisionscited by 99
  11. 2017Verifying Properties of Binarized Deep Neural Networkscited by 77
  12. 2020Model Interpretability through the Lens of Computational Complexitycited by 75
26 more
  1. 2021On Explaining Random Forests with SATcited by 57
  2. 2019Quantitative Verification of Neural Networks And its Security Applicationscited by 56
  3. 2020Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delaycited by 56
  4. 2020On Explaining Decision Treescited by 49
  5. 2022On Tackling Explanation Redundancy in Decision Treescited by 44
  6. 2021On the Computational Intelligibility of Boolean Classifierscited by 40
  7. 2021On Efficiently Explaining Graph-Based Classifierscited by 37
  8. 2018Contrastive Explanations with Local Foil Treescited by 34
  9. 2020On Tractable Representations of Binary Neural Networkscited by 34
  10. 2020Efficient Exact Verification of Binarized Neural Networkscited by 33
  11. 2019On Validating, Repairing and Refining Heuristic ML Explanationscited by 32
  12. 2021Trading Complexity for Sparsity in Random Forest Explanationscited by 32
  13. 2020Scalable Verification of Quantized Neural Networks (Technical Report)cited by 28
  14. 2022On the Computation of Necessary and Sufficient Explanationscited by 23
  15. 2022Computing Abductive Explanations for Boosted Treescited by 23
  16. 2016SDDs are Exponentially More Succinct than OBDDscited by 19
  17. 2021BDD4BNN: A BDD-based Quantitative Analysis Framework for Binarized Neural Networkscited by 17
  18. 2021On Quantifying Literals in Boolean Logic and Its Applications to Explainable AIcited by 16
  19. 2020Three Modern Roles for Logic in AIcited by 15
  20. 2020On Symbolically Encoding the Behavior of Random Forestscited by 15
  21. 2022QVIP: An ILP-based Formal Verification Approach for Quantized Neural Networkscited by 12
  22. 2021Efficient Explanations for Knowledge Compilation Languagescited by 9
  23. 2022QEBVerif: Quantization Error Bound Verification of Neural Networkscited by 9
  24. 2018On the Relative Succinctness of Sentential Decision Diagramscited by 6
  25. 2013Lower Bounds for Exact Model Counting and Applications in Probabilistic Databasescited by 5
  26. 2015New Limits for Knowledge Compilation and Applications to Exact Model Countingcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 1; 2025: 11; 2026: 10.

23 papers.

Sort:

  1. 2024Local vs. Global Interpretability: A Computational Complexity Perspectivecited by 23
  2. 2026Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guaranteescited by 10
  3. 2025Most General Explanations of Tree Ensembles (Extended Version)cited by 7
  4. 2025On the Complexity of Global Necessary Reasons to Explain Classificationcited by 3
  5. 2025Why this and not that? A Logic-based Framework for Contrastive Explanationscited by 3
  6. 2025When is the Computation of a Feature Attribution Method Tractable?cited by 2
  7. 2026Circuit Representations of Random Forests with Applications to XAIcited by 2
  8. 2023The Pros and Cons of Adversarial Robustnesscited by 1
  9. 2025Explanations are a Means to an End: Decision Theoretic Explanation Evaluationcited by 1
  10. 2025Database Views as Explanations for Relational Deep Learningcited by 1
  11. 2025Uncovering Bugs in Formal Explainers: A Case Study with PyXAIcited by 1
  12. 2025Sufficient Explanations in Databases and their Connections to Database Repairscited by 1
11 more
  1. 2026Provably Explaining Neural Additive Modelscited by 1
  2. 2026Unifying Formal Explanations: A Complexity-Theoretic Perspectivecited by 1
  3. 2025On Trustworthy Rule-Based Models and Explanationscited by 0
  4. 2025Rigorous Feature Importance Scores based on Shapley Value and Banzhaf Indexcited by 0
  5. 2025Efficient & Correct Predictive Equivalence for Decision Treescited by 0
  6. 2026A Formal Framework for the Explanation of Finite Automata Decisionscited by 0
  7. 2026Scaling the Explanation of Multi-Class Bayesian Network Classifierscited by 0
  8. 2026Towards Rigorous Explainability by Feature Attributioncited by 0
  9. 2026Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanationscited by 0
  10. 2026Dsat: A Native SAT Solver for Discrete Logiccited by 0
  11. 2026Enhancing Query Efficiency for d-DNNF Representations Through Preprocessingcited by 0