mlsanityData to 7 Oct 2026

Efficient Explanations for Knowledge Compilation Languages

arXiv 2107.01654 ↗First posted 4 Jul 2021cs.AIcited by 9

Not on the map. Why?

Abstract (arXiv)

Knowledge compilation (KC) languages find a growing number of practical uses, including in Constraint Programming (CP) and in Machine Learning (ML). In most applications, one natural question is how to explain the decisions made by models represented by a KC language. This paper shows that for many of the best known KC languages, well-known classes of explanations can be computed in polynomial time. These classes include deterministic decomposable negation normal form (d-DNNF), and so any KC language that is strictly less succinct than d-DNNF. Furthermore, the paper also investigates the conditions under which polynomial time computation of explanations can be extended to KC languages more succinct than d-DNNF.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 18 of its 62 references that are in the map. First posted on arXiv 4 Jul 2021.

Builds on

18 of 62 references.

References · 18

  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. 2018A Survey Of Methods For Explaining Black Box Modelscited by 970
  5. 2016The Mythos of Model Interpretabilitycited by 716
  6. 2014OpenML: networked science in machine learningcited by 523
  7. 2018Abduction-Based Explanations for Machine Learning Modelscited by 159
  8. 2017PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparisoncited by 139
  9. 2018Explaining Explanations in AIcited by 136
  10. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 130
  11. 2019Towards Explainable Artificial Intelligencecited by 106
  12. 2020On The Reasons Behind Decisionscited by 99
6 more
  1. 2020Model Interpretability through the Lens of Computational Complexitycited by 75
  2. 2019Explanation in Human-AI Systems: A Literature Meta-Review, Synopsis of Key Ideas and Publications, and Bibliography for Explainable AIcited by 63
  3. 2021On Guaranteed Optimal Robust Explanations for NLP Modelscited by 54
  4. 2018The Challenge of Crafting Intelligible Intelligencecited by 46
  5. 2021On the Computational Intelligibility of Boolean Classifierscited by 40
  6. 2016SDDs are Exponentially More Succinct than OBDDscited by 19

Built on by

Cited by year

Citing papers per year: 2022: 5; 2023: 2; 2024: 0; 2025: 2.

9 papers.

  1. 2022Logic-Based Explainability in Machine Learningcited by 47
  2. 2022On Tackling Explanation Redundancy in Decision Treescited by 44
  3. 2022On the Computation of Necessary and Sufficient Explanationscited by 23
  4. 2023Logic for Explainable AIcited by 23
  5. 2022Tractable Boolean and Arithmetic Circuitscited by 9
  6. 2023A New Class of Explanations for Classifiers with Non-Binary Featurescited by 8
  7. 2022On Deciding Feature Membership in Explanations of SDD & Related Classifierscited by 2
  8. 2025Feature Relevancy, Necessity and Usefulness: Complexity and Algorithmscited by 1
  9. 2025Leveraging Association Rules for Better Predictions and Better Explanationscited by 0