mlsanityData to 14 Oct 2026

Interpretable DNFs

arXiv 2505.21212 ↗First posted 27 May 2025cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

A classifier is considered interpretable if each of its decisions has an explanation which is small enough to be easily understood by a human user. A DNF formula can be seen as a binary classifier kappa over boolean domains. The size of an explanation of a positive decision taken by a DNF kappa is bounded by the size of the terms in kappa, since we can explain a positive decision by giving a term of kappa that evaluates to true. Since both positive and negative decisions must be explained, we consider that interpretable DNFs are those kappa for which both kappa and overlinekappa can be expressed as DNFs composed of terms of bounded size. In this paper, we study the family of k-DNFs whose complements can also be expressed as k-DNFs. We compare two such families, namely depth-k decision trees and nested k-DNFs, a novel family of models. Experiments indicate that nested k-DNFs are an interesting alternative to decision trees in terms of interpretability and accuracy.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 13 of its 26 references that are in the map. First posted on arXiv 27 May 2025.

Builds on

13 of 26 references.

References · 13

  1. 2018Abduction-Based Explanations for Machine Learning Modelscited by 160
  2. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 131
  3. 2020Interpretable Machine Learning -- A Brief History, State-of-the-Art and Challengescited by 120
  4. 2020Model Interpretability through the Lens of Computational Complexitycited by 75
  5. 2020Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delaycited by 57
  6. 2021On Explaining Random Forests with SATcited by 57
  7. 2022On Tackling Explanation Redundancy in Decision Treescited by 44
  8. 2021On the Computational Intelligibility of Boolean Classifierscited by 40
  9. 2021SAT-Based Rigorous Explanations for Decision Listscited by 40
  10. 2021Explanations for Monotonic Classifierscited by 39
  11. 2024Abductive explanations of classifiers under constraints: Complexity and propertiescited by 7
  12. 2022The Query Complexity of Certificationcited by 3
1 more
  1. 2024Logic-Based Explainability: Past, Present & Futurecited by 2

Built on by

Not cited yet.