mlsanityData to 14 Oct 2026

On the Computation of Necessary and Sufficient Explanations

arXiv 2203.10451 ↗First posted 20 Mar 2022cs.AI cs.LG cs.LOcited by 23

Not on the map. Why?

Abstract (arXiv)

The complete reason behind a decision is a Boolean formula that characterizes why the decision was made. This recently introduced notion has a number of applications, which include generating explanations, detecting decision bias and evaluating counterfactual queries. Prime implicants of the complete reason are known as sufficient reasons for the decision and they correspond to what is known as PI explanations and abductive explanations. In this paper, we refer to the prime implicates of a complete reason as necessary reasons for the decision. We justify this terminology semantically and show that necessary reasons correspond to what is known as contrastive explanations. We also study the computation of complete reasons for multi-class decision trees and graphs with nominal and numeric features for which we derive efficient, closed-form complete reasons. We further investigate the computation of shortest necessary and sufficient reasons for a broad class of complete reasons, which include the derived closed forms and the complete reasons for Sentential Decision Diagrams (SDDs). We provide an algorithm which can enumerate their shortest necessary reasons in output polynomial time. Enumerating shortest sufficient reasons for this class of complete reasons is hard even for a single reason. For this problem, we provide an algorithm that appears to be quite efficient as we show empirically.

Key facts. Cited by 23 papers in the map (data through 14 Oct 2026). Builds on 25 of its 52 references that are in the map. First posted on arXiv 20 Mar 2022.

Builds on

25 of 52 references.

References · 25

  1. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,070
  2. 2017Explanation in Artificial Intelligence: Insights from the Social Sciencescited by 1,206
  3. 2017Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPRcited by 1,089
  4. 2019Explaining Machine Learning Classifiers through Diverse Counterfactual Explanationscited by 614
  5. 2014OpenML: networked science in machine learningcited by 526
  6. 2019Counterfactual Visual Explanationscited by 313
  7. 2018Abduction-Based Explanations for Machine Learning Modelscited by 160
  8. 2018Explaining Explanations in AIcited by 137
  9. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 131
  10. 2020On The Reasons Behind Decisionscited by 100
  11. 2017Verifying Properties of Binarized Deep Neural Networkscited by 79
  12. 2020Model Interpretability through the Lens of Computational Complexitycited by 75
13 more
  1. 2021On Efficiently Explaining Graph-Based Classifierscited by 37
  2. 2018Contrastive Explanations with Local Foil Treescited by 34
  3. 2020On Tractable Representations of Binary Neural Networkscited by 34
  4. 2019On Validating, Repairing and Refining Heuristic ML Explanationscited by 32
  5. 2021Probabilistic Sufficient Explanationscited by 24
  6. 2016SDDs are Exponentially More Succinct than OBDDscited by 19
  7. 2021On Quantifying Literals in Boolean Logic and Its Applications to Explainable AIcited by 16
  8. 2020On Symbolically Encoding the Behavior of Random Forestscited by 15
  9. 2021Efficient Explanations for Knowledge Compilation Languagescited by 10
  10. 2018On the Relative Succinctness of Sentential Decision Diagramscited by 6
  11. 2021On the Explanatory Power of Decision Treescited by 6
  12. 2013Lower Bounds for Exact Model Counting and Applications in Probabilistic Databasescited by 5
  13. 2015New Limits for Knowledge Compilation and Applications to Exact Model Countingcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 5; 2025: 6; 2026: 9.

23 papers.

Sort:

By area:

  1. 2022Logic-Based Explainability in Machine Learningcited by 48
  2. 2023Logic for Explainable AIcited by 23
  3. 2024Local vs. Global Interpretability: A Computational Complexity Perspectivecited by 23
  4. 2024Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretationcited by 11
  5. 2026Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guaranteescited by 11
  6. 2023A New Class of Explanations for Classifiers with Non-Binary Featurescited by 8
  7. 2025SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelismcited by 8
  8. 2024Enabling MCTS Explainability for Sequential Planning Through Computation Tree Logiccited by 6
  9. 2025Change in Quantitative Bipolar Argumentation: Sufficient, Necessary, and Counterfactual Explanationscited by 4
  10. 2024Explaining Decisions in ML Models: a Parameterized Complexity Analysiscited by 3
  11. 2024Sufficient and Necessary Explanations (and What Lies in Between)cited by 3
  12. 2026FAME: Formal Abstract Minimal Explanation for Neural Networkscited by 3
11 more
  1. 2026Local-to-Global Logical Explanations for Deep Vision Modelscited by 2
  2. 2026Circuit Representations of Random Forests with Applications to XAIcited by 2
  3. 2026Unifying Formal Explanations: A Complexity-Theoretic Perspectivecited by 2
  4. 2025Feature Relevancy, Necessity and Usefulness: Complexity and Algorithmscited by 1
  5. 2025Uncovering Bugs in Formal Explainers: A Case Study with PyXAIcited by 1
  6. 2026Provably Explaining Neural Additive Modelscited by 1
  7. 2025Efficient & Correct Predictive Equivalence for Decision Treescited by 0
  8. 2025Explaining Decisions in ML Models: a Parameterized Complexity Analysis (Part I)cited by 0
  9. 2026Scaling the Explanation of Multi-Class Bayesian Network Classifierscited by 0
  10. 2026Dsat: A Native SAT Solver for Discrete Logiccited by 0
  11. 2026GLARE: A Natural Language Interface for Querying Global Explanationscited by 0