Interpretable DNFs
This work addresses the need for interpretable machine learning models, particularly for users requiring transparent decision-making, though it is incremental as it builds on existing DNF-based interpretability concepts.
The paper tackles the problem of designing interpretable classifiers by studying DNF formulas where both the classifier and its complement can be expressed with bounded term sizes, focusing on families like depth-k decision trees and novel nested k-DNFs. Experiments show that nested k-DNFs offer a competitive alternative to decision trees in terms of interpretability and accuracy.
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 $\overlineκ$ 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.