Interpretable DNFs

2025/05/27 by Martin Cooper, Cooper, Martin C., Imane Bousdira +3
Computer Science · #05C62 #68T27 #Adversarial Robustness in Machine Learning #Artificial Intelligence (cs.AI) #F.4.1 #FOS: Computer and information sciences #I.2.6 #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.2505.21212

openalex publication_date 2025/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 κ over boolean domains. The size of an explanation of a positive decision taken by a DNF κ is bounded by the size of the terms in κ, since we can explain a positive decision by giving a term of κ that evaluates to true. Since both positive and negative decisions must be explained, we consider that interpretable DNFs are those κ for which both κ and κ 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.

Citations

• Abductive explanations of classifiers under constraints: Complexity and properties
• Logic-Based Explainability: Past, Present & Future
• The Query Complexity of Certification
• Explanations for Monotonic Classifiers
• On Explaining Random Forests with SAT
• SAT-Based Rigorous Explanations for Decision Lists
• On the Computational Intelligibility of Boolean Classifiers
• Model Interpretability through the Lens of Computational Complexity
• Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay
• Abduction-Based Explanations for Machine Learning Models
• A Symbolic Approach to Explaining Bayesian Network Classifiers

Related

• Provably Precise, Succinct and Efficient Explanations for Decision Trees
• On Explaining Decision Trees
• Bayes Point Rule Set Learning
• A canonical generalization of OBDD
• Learning Accurate and Interpretable Decision Rule Sets from Neural Networks