mlsanityData to 7 Oct 2026

Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay

arXiv 2008.05803 ↗First posted 13 Aug 2020cs.LG stat.MLcited by 56

Not on the map. Why?

Abstract (arXiv)

Recent work proposed the computation of so-called PI-explanations of Naive Bayes Classifiers (NBCs). PI-explanations are subset-minimal sets of feature-value pairs that are sufficient for the prediction, and have been computed with state-of-the-art exact algorithms that are worst-case exponential in time and space. In contrast, we show that the computation of one PI-explanation for an NBC can be achieved in log-linear time, and that the same result also applies to the more general class of linear classifiers. Furthermore, we show that the enumeration of PI-explanations can be obtained with polynomial delay. Experimental results demonstrate the performance gains of the new algorithms when compared with earlier work. The experimental results also investigate ways to measure the quality of heuristic explanations

Key facts. Cited by 56 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Aug 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 10; 2023: 7; 2024: 7; 2025: 10; 2026: 13.

56 papers.

Sort:

  1. 2022From Anecdotal Evidence to Quantitative Evaluation Methods: A Systematic Review on Evaluating Explainable AIcited by 299
  2. 2021On Explaining Random Forests with SATcited by 57
  3. 2022Logic-Based Explainability in Machine Learningcited by 47
  4. 2022On Tackling Explanation Redundancy in Decision Treescited by 44
  5. 2021On the Computational Intelligibility of Boolean Classifierscited by 40
  6. 2021SAT-Based Rigorous Explanations for Decision Listscited by 40
  7. 2021Explanations for Monotonic Classifierscited by 39
  8. 2021On Efficiently Explaining Graph-Based Classifierscited by 37
  9. 2022On Computing Probabilistic Explanations for Decision Treescited by 35
  10. 2021Trading Complexity for Sparsity in Random Forest Explanationscited by 32
  11. 2022VeriX: Towards Verified Explainability of Deep Neural Networkscited by 30
  12. 2023The Inadequacy of Shapley Values for Explainabilitycited by 30
38 more
  1. 2021Foundations of Symbolic Languages for Model Interpretabilitycited by 26
  2. 2021Probabilistic Sufficient Explanationscited by 24
  3. 2023Formally Explaining Neural Networks within Reactive Systemscited by 24
  4. 2022Eliminating The Impossible, Whatever Remains Must Be Truecited by 23
  5. 2023Logic for Explainable AIcited by 23
  6. 2024Local vs. Global Interpretability: A Computational Complexity Perspectivecited by 23
  7. 2022Feature Necessity & Relevancy in ML Classifier Explanationscited by 22
  8. 2022On Computing Probabilistic Abductive Explanationscited by 18
  9. 2025Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanationscited by 13
  10. 2023Disproving XAI Myths with Formal Methods -- Initial Resultscited by 12
  11. 2023On Formal Feature Attribution and Its Approximationcited by 11
  12. 2024Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretationcited by 11
  13. 2025Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasonscited by 11
  14. 2023Axiomatic Aggregations of Abductive Explanationscited by 10
  15. 2025Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanationscited by 10
  16. 2025Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspectivecited by 10
  17. 2026Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guaranteescited by 10
  18. 2023Anytime Approximate Formal Feature Attributioncited by 9
  19. 2022On Computing Relevant Features for Explaining NBCscited by 5
  20. 2024Logic-based Explanations for Linear Support Vector Classifiers with Reject Optioncited by 3
  21. 2025On the Complexity of Global Necessary Reasons to Explain Classificationcited by 3
  22. 2025Additive Models Explained: A Computational Complexity Approachcited by 3
  23. 2026FAME: Formal Abstract Minimal Explanation for Neural Networkscited by 3
  24. 2024Logic-Based Explainability: Past, Present & Futurecited by 2
  25. 2024Learning Model Agnostic Explanations via Constraint Programmingcited by 2
  26. 2026Generalizing Logic-based Explanations for Machine Learning Classifiers via Optimizationcited by 2
  27. 2021Model Explanations via the Axiomatic Causal Lenscited by 1
  28. 2024AIDE: Antithetical, Intent-based, and Diverse Example-Based Explanationscited by 1
  29. 2024Efficient Contrastive Explanations on Demandcited by 1
  30. 2025Uncovering Bugs in Formal Explainers: A Case Study with PyXAIcited by 1
  31. 2026Provably Explaining Neural Additive Modelscited by 1
  32. 2026Unifying Formal Explanations: A Complexity-Theoretic Perspectivecited by 1
  33. 2026Binary Spiking Neural Networks as Causal Modelscited by 1
  34. 2022A Model-Agnostic SAT-based Approach for Symbolic Explanation Enumerationcited by 0
  35. 2025Fixed Point Explainabilitycited by 0
  36. 2025Interpretable DNFscited by 0
  37. 2025Efficient & Correct Predictive Equivalence for Decision Treescited by 0
  38. 2026On the Hardness of Computing Counterfactual and Semifactual Explanations in XAIcited by 0

50 most cited of 56 All 56 (JSON)