mlsanityData to 7 Oct 2026

Feature Necessity & Relevancy in ML Classifier Explanations

arXiv 2210.15675 ↗First posted 27 Oct 2022cs.LG cs.AIcited by 22

Not on the map. Why?

Abstract (arXiv)

Given a machine learning (ML) model and a prediction, explanations can be defined as sets of features which are sufficient for the prediction. In some applications, and besides asking for an explanation, it is also critical to understand whether sensitive features can occur in some explanation, or whether a non-interesting feature must occur in all explanations. This paper starts by relating such queries respectively with the problems of relevancy and necessity in logic-based abduction. The paper then proves membership and hardness results for several families of ML classifiers. Afterwards the paper proposes concrete algorithms for two classes of classifiers. The experimental results confirm the scalability of the proposed algorithms.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 23 of its 71 references that are in the map. First posted on arXiv 27 Oct 2022.

Builds on

23 of 71 references.

References · 23

  1. 2017A Unified Approach to Interpreting Model Predictionscited by 6,488
  2. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,040
  3. 2017Explanation in Artificial Intelligence: Insights from the Social Sciencescited by 1,201
  4. 2018Abduction-Based Explanations for Machine Learning Modelscited by 159
  5. 2017PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparisoncited by 139
  6. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 130
  7. 2019Unconstrained Monotonic Neural Networkscited by 91
  8. 2020Model Interpretability through the Lens of Computational Complexitycited by 75
  9. 2017Deep Lattice Networks and Partial Monotonic Functionscited by 62
  10. 2021On Explaining Random Forests with SATcited by 57
  11. 2020Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delaycited by 56
  12. 2021On Guaranteed Optimal Robust Explanations for NLP Modelscited by 54
11 more
  1. 2020Certified Monotonic Neural Networkscited by 51
  2. 2022On Tackling Explanation Redundancy in Decision Treescited by 44
  3. 2021On the Computational Intelligibility of Boolean Classifierscited by 40
  4. 2021SAT-Based Rigorous Explanations for Decision Listscited by 40
  5. 2021Explanations for Monotonic Classifierscited by 39
  6. 2022On Computing Probabilistic Explanations for Decision Treescited by 35
  7. 2020Counterexample-Guided Learning of Monotonic Neural Networkscited by 34
  8. 2021Provably efficient, succinct, and precise explanationscited by 32
  9. 2021Foundations of Symbolic Languages for Model Interpretabilitycited by 26
  10. 2022ASTERYX : A model-Agnostic SaT-basEd appRoach for sYmbolic and score-based eXplanationscited by 26
  11. 2021On Quantifying Literals in Boolean Logic and Its Applications to Explainable AIcited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 10; 2024: 4; 2025: 6; 2026: 2.

22 papers.

Sort:

  1. 2023The Inadequacy of Shapley Values for Explainabilitycited by 30
  2. 2023Formally Explaining Neural Networks within Reactive Systemscited by 24
  3. 2024Local vs. Global Interpretability: A Computational Complexity Perspectivecited by 23
  4. 2024Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementationcited by 20
  5. 2023From Robustness to Explainability and Back Againcited by 14
  6. 2025Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanationscited by 13
  7. 2023Disproving XAI Myths with Formal Methods -- Initial Resultscited by 12
  8. 2023On Formal Feature Attribution and Its Approximationcited by 11
  9. 2024Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretationcited by 11
  10. 2023Anytime Approximate Formal Feature Attributioncited by 9
  11. 2023A Refutation of Shapley Values for Explainabilitycited by 4
  12. 2023Refutation of Shapley Values for XAI -- Additional Evidencecited by 4
10 more
  1. 2023A Uniform Language to Explain Decision Treescited by 4
  2. 2025Shapley Revisited: Tractable Responsibility Measures for Query Answerscited by 4
  3. 2025Additive Models Explained: A Computational Complexity Approachcited by 3
  4. 2024Logic-Based Explainability: Past, Present & Futurecited by 2
  5. 2025Feature Relevancy, Necessity and Usefulness: Complexity and Algorithmscited by 1
  6. 2025Uncovering Bugs in Formal Explainers: A Case Study with PyXAIcited by 1
  7. 2023On Logic-Based Explainability with Partially Specified Inputscited by 0
  8. 2025Efficient & Correct Predictive Equivalence for Decision Treescited by 0
  9. 2026Rigorous Explanations for Tree Ensemblescited by 0
  10. 2026ExplAIner: A Declarative Query Language for Explaining Classification Modelscited by 0