# Interpretable DNFs

arXiv: https://arxiv.org/abs/2505.21212 · HTML: https://mlsanity.com/paper/2505.21212/

## 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 (most cited first, 13 of 13)

- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Interpretable Machine Learning -- A Brief History, State-of-the-Art and Challenges](https://mlsanity.com/paper/2010.09337/) (2020)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [Explanations for Monotonic Classifiers](https://mlsanity.com/paper/2106.00154/) (2021)
- [Abductive explanations of classifiers under constraints: Complexity and properties](https://mlsanity.com/paper/2409.12154/) (2024)
- [The Query Complexity of Certification](https://mlsanity.com/paper/2201.07736/) (2022)
- [Logic-Based Explainability: Past, Present & Future](https://mlsanity.com/paper/2406.11873/) (2024)

## 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.