Interpretable DNFs

1 Introduction

Interpretable models are critical in machine learning applications requiring accountability of decisions [Rudin, 2019; Molnar et al., 2020]. In particular, there is a growing interest in models whose decisions can always be explained in a way that is comprehensible by a human user. In recent work on formal explainability [Shih et al., 2018; Ignatiev et al., 2019; Barcel´o et al., 2020; Audemard et al., 2021; Marques-Silva, 2024], two notions of explanation of decisions have emerged. An abductive explanation corresponds to a minimal set of features that caused the decision, whereas a contrastive explanation corresponds to a means of changing the decision with changes to a minimal set of features. A theoretical line of research, starting from a list of desirable properties rather than a particular definition, has identified abductive explanations as the basis for determining what constitutes a sufficient reason for a decision [Amgoud and Ben-Naim, 2022; Cooper and Amgoud, 2023].

In this paper, we deem a model to be interpretable if each of its decision has both a short abductive explanation and a short contrastive explanation. Observe that we are considering interpretability as an orthogonal question to explainability, which depends on whether we can efficiently find an explanation of each decision. There is a considerable literature on the question of which families of models are explainable, whether explainability means the existence of polynomial-time or efficient-in-practice algorithms to find explanations [Marques-Silva et al., 2020; MarquesSilva et al., 2021; Huang et al., 2022; Izza et al., 2022; Cooper and Marques-Silva, 2023; Carbonnel et al., 2023; Izza and Marques-Silva, 2021; Ignatiev and Marques-Silva, 2021; Ignatiev et al., 2022].

This criterion for interpretability is very restrictive. The only commonly used family of models that are interpretable in this sense are decision trees whose depth is bounded by a small constant. In contrast, linear classifiers, random forests, decision lists and neural networks may all require a linear number of features in an explanation. However, it is theoretically possible that very different families of interpretable models exist. The purpose of this paper is to study the structure of interpretable models in order to find a competitive alternative to decision trees.

We restrict our attention to classifiers which are functions of boolean features only. (However, most of our results can be extended to non-boolean features through binarisation.) In Section 2, we observe that a boolean classifier κ is interpretable if and only if both κ and its complement κ are expressible as k-DNF formulas, where k is the upper bound on the size of explanations. In Section 3, we show that such classifiers can always be expressed by short k-DNF formulas composed of at most kk terms. For small enough k, this shows that direct representation of interpretable classifiers as DNF formulas is always possible. Then, we describe in Section 4 a simple graph-based condition which guarantees that the complement of a k-DNF formula is also expressible in kDNF and use this property to define nested k-DNFs, a new family of interpretable classifiers that is orthogonal to decision trees. We study the expressivity of nested k-DNFs in Section 5. Finally, we present in Section 6 a practical algorithm for learning nested k-DNFs, and show empirically that classifiers constructed this way are competitive with decision trees on various datasets.

2 Preliminaries

We denote by F the feature space, which for most of the paper will be {0, 1}n , and by F the set of features {1, . . . , n}.

Definition 1. Given a function κ : F → {0, 1} and an input v = (v1, . . . , vn) ∈ F, a weak abductive explanation (wAXp) of (κ, v) is a subset A of F such that ∀x = (x1, . . . , xn) ∈ F, (∧i∈A(xi = vi)) ⇒ κ(x) = κ(v). A weak contrastive explanation (wCXp) of (κ, v) is a subset C of F such that ∃x ∈ F, (∧i∈F\C(xi = vi)) ∧ κ(x) ̸= κ(v). An abductive explanation (AXp) is a subset-minimal wAXp. A contrastive explanation (CXp) is a subset-minimal wCXp.

In order to give a formal definition of interpretability of a family of models, we first give a parameterized definition of interpretability of a classifier based on AXps/CXps.

Definition 2. Let k be a natural number. A function κ : F → {0, 1} is k-AXp-interpretable if for each v ∈ F, there is an AXp of (κ, v) of size at most k. A non-constant function is k-CXp-interpretable if for each v ∈ F, there is a CXp of size at most k. By convention, a constant function is deemed to be k-CXp-interpretable.

To see that k-AXp-interpretability and k-CXpinterpretability do not coincide, consider the parity function κ which returns 1 if the sum of its n boolean features is even and 0 otherwise. For any v ∈ F, changing one feature changes the parity, which implies both that (κ, v) has a CXp of size 1 and that, on the other hand, the only AXp is of size n. Thus the existence of a small CXp does not guarantee the existence of a small AXp. On the other hand, for any κ, the existence of a small AXp (for all inputs) implies the existence of a small CXp, as we now show.

Lemma 1. A function κ that is k-AXp-interpretable is also k-CXp-interpretable.

Proof. Suppose that κ is k-AXp-interpretable. The case of constant functions is trivial, so we assume that κ is nonconstant. Thus, given an arbitrary input v ∈ F, there is another input v′ ∈ F such that κ(v′ ) ̸= κ(v). By k-AXpinterpretability, (κ, v′ ) has an AXp A of size at most k. Let yi = vi if i ∈ F \ A and yi = v′i if i ∈ A. By definition, κ(y) = κ(v′ ) ̸= κ(v). Therefore, A is a wCXp of (κ, v) and hence some subset of A is a CXp of size at most k.

Since k-CXp-interpretability follows from k-AXpinterpretability, this leads to a natural definition of interpretable models in terms of k-AXp-interpretability.

Definition 3. A family Mof models is interpretable if there is a constant k such that every classifier κ ∈ M is k-AXpinterpretable.

We now focus on the case where the feature space F is boolean. Given a boolean function κ over boolean variables (x1, . . . , xn), a literal is either a variable xi or its negation xi. A boolean formula is in disjunctive normal form (DNF) if it is a disjunction of terms, which are conjunctions of literals. For simplicity of presentation, we freely interpret terms as either sets or conjunctions of literals depending on context. A DNF formula is in k-DNF if each of its terms has size at most k. We say that a conjunction (or set) of literals is consistent if it does not contain both a variable and its negation. An implicant of κ is a consistent conjunction of literals Q such that κ maps to 1 all assignments to (x1, . . . , xn) for which Q evaluates to true. An implicant of κ is prime if it is subset-minimal.

Given a DNF formula D with variables X and a consistent set of literals Q over X, we denote by D[Q] the DNF formula with variables {xi ∈ X : xi /∈ Q and xi /∈ Q} obtained from D by removing all the terms that contain the negation of a literal in Q and replacing each remaining term t = ∧l∈S l with t[Q] = ∧l∈S\Q l. If D1 and D2 are DNF formulas that express respectively a boolean function and its complement, then for any choice of Q the formulas D1[Q] and D2[Q] also express functions that are complements to each other. The size of D, denoted by |D|, is the number of terms in D and its length ||D|| is the sum of the sizes of its terms. Throughout the paper we will use L(D) (resp. T(D)) to denote the sets of literals (resp. terms) that appear in the formula D.

For a boolean classifier κ, the prime implicants of κ (resp. κ) are in one-to-one correspondence with AXps for positive (resp. negative) decisions. The relationship between interpretability and expressibility as a k-DNF formula is made explicit by the following proposition.

Proposition 1. A binary boolean classifier κ : {0, 1}n → {0, 1} is k-AXp-interpretable if and only if both κ and its complement are expressible as k-DNFs.

Proof. The 'if' direction follows from the fact that a term that evaluates to true is a wAXp (of size k), and hence some subset will be an AXp. The 'only if' direction follows from the fact that κ (resp. κ) is equivalent to the disjunction of terms corresponding to the AXps of its positive (negative) decisions.

Using Proposition 1, it is straightforward to verify that a boolean function κ is k-AXp-interpretable if and only if both κ and κ are equivalent to the disjunction of their prime implicants of size at most k. The standard double-DNF expression of a k-AXp-interpretable classifier is the pair (Dκ,Dκ), where Dκ is the DNF formula whose terms are the prime implicants of κ of size at most k and Dκ is the DNF formula whose terms are the prime implicants of κ of size at most k.

The smallest integer k such that a boolean function κ and its complement can be expressed as k-DNF formulas is called the certificate complexity of κ [Arora and Barak, 2009, Chapter 11]. This measure is well studied in theoretical computer science and computational learning theory [Chaubal and G´al, 2021; Blanc et al., 2022], but little appears to be known about the structure of functions whose certificate complexity is bounded by a small constant.

Example 1. Decision trees are a well-known family of classifiers which have the reputation of being interpretable. Indeed, if k is the depth of a decision tree, then the corresponding classifier κDT and its complement κDT can both be expressed as k-DNFs. Given a path π from the root to a leaf, let L(π) denote the set of literals labelling the edges in the path π. We assume a binary classifier, so each leaf is labelled 0 or 1. Let P0 and P1 denote the sets of paths from the root to, respectively, leaves labelled 0 and leaves labelled 1. Then the classifier κDT corresponding to the decision tree can be expressed as the following DNF:

κDT (x) = ∨π∈P1 ∧ℓ∈L(π) ℓ. Furthermore, κDT can also be expressed as a DNF: κDT (x) = ∨π∈P0 ∧ℓ∈L(π) ℓ. Observe that both these DNFs are k-DNFs since the length of paths is at most k.

As seen in Example 1, if κ can be represented as a decision tree of depth k then κ is k-AXp-interpretable. However, the converse implication does not hold. In this paper, we are interested in identifying new families of interpretable classifiers that are orthogonal to those derived from decision trees.

Example 2. For k = 2, a characterisation of 2-DNF formulas whose complement is expressible in 2-DNF can be derived from a recent result [Carbonnel et al., 2023, Corollary 2]. Together with Proposition 1, this characterisation implies that a classifier κ is 2-AXp-interpretable if and only if it is equivalent to a DNF with one of the following forms (where the literals a, b, c, d are arbitrary and not necessarily distinct): (i) (a ∧ b) ∨ (c ∧ d), (ii) (a ∧ b) ∨ (b ∧ c) ∨ (c ∧ d), and (iii) (a∧b)∨(b∧c)∨(c∧d)∨(d∧a). Interestingly, certain DNFs of this kind cannot be represented as decision trees of depth 2 (see Example 4 for more details). However, they all satisfy a different combinatorial criterion for 2-AXp-interpretability that we describe in Section 4.

3 Short Explanations Imply Few Explanations

In this section, we show that every k-AXp-interpretable classifier is expressible as a k-DNF consisting of at most kk terms (independently of the number n of features). This result gives further justification to work directly with DNF representations of k-AXp-interpretable classifiers when k is small. In particular, this implies that if a classifier can provide an explanation of size at most k for every decision, then all decisions can be explained using only 2kk distinct explanations.

Theorem 1. Every k-AXp-interpretable classifier is expressible as a k-DNF formula that contains at most kk terms.

Proof. Let κ be a k-AXp-interpretable classifier and (Dκ,Dκ) be the standard double-DNF expression of κ. We will show that Dκ contains at most kk terms. If κ is constant then the theorem obviously holds, so let us assume that it is not. (This assumption implies in particular k > 0, |Dκ| > 0, and |Dκ| > 0.) We claim that for all integers j ≥ 0, either |Dκ| < kj or there exists a consistent set Q of j literals that is contained in at least (1/k)j · |Dκ| terms of Dκ. We will prove this claim by induction on j.

The base case j = 0 is immediate because every term in Dκ contains the empty set of literals. Now, let j be such that 1 ≤ j ≤ k and suppose that the claim holds for j - 1. If |Dκ| < kj-1 then |Dκ| < kj and we are done. Otherwise, there exists a consistent set Q′ of j - 1 literals and a set S of at least (1/k)j-1 · |Dκ| terms of Dκ such that every term in S contains Q′ . We distinguish two cases.

Case 1: Q′ = {l : l ∈ Q′ } has non-empty intersection with every term in Dκ. Then, Q′ is an implicant of κ. The terms of Dκ are prime implicants of κ and Q′ is contained in at least one term of Dκ, so Q′ is contained in exactly one term of Dκ. This implies (1/k)j-1 · |Dκ| ≤ 1 and hence |Dκ| < kj .

Case 2: there exists a term t in Dκ whose intersection with Q′ is empty. Consider the DNF formulas Dκ[Q′ ] and Dκ[Q′ ]. Observe that t[Q′ ] is a term of Dκ[Q′ ], and s[Q′ ] is a term of Dκ[Q′ ] for all s ∈ S. (This last observation follows from the fact that every term in S is a prime implicant of κ: these terms are consistent and contain Q′ , so they cannot intersect Q′ .) If t[Q′ ] is the empty term, then Q′ is an implicant of κ; this is not possible because at least one term in Dκ contains Q′ . In addition, as Dκ[Q′ ] and Dκ[Q′ ] express functions that are complements of each other, the set {l : l ∈ t[Q′ ]} must have non-empty intersection with every term in Dκ[Q′ ] and in particular with every term in {s[Q′ ] | s ∈ S}. The term t[Q′ ] contains at most k literals, so there exists l ∈ t[Q′ ] such that at least (1/k) · |S| terms in S contain l. Then, the set of literals Q = Q′ ∪ {l} is contained in at least (1/k) · |S| ≥ (1/k) · (1/k)j-1 · |Dκ| = (1/k)j · |Dκ| terms of Dκ and the claim holds by induction.

We can now finish the proof of the theorem. Every term in Dκ is a prime implicant of κ so Dκ cannot contain the same term twice. In addition, every term in Dκ has size at most k. Then, for j = k we have either |Dκ| < kk or (1/k)k · |Dκ| ≤ 1 and the theorem follows.

The specific bound of Theorem 1 is sharp as there exist k-AXp-interpretable classifiers that cannot be expressed as a DNF formula with fewer than kk terms. A concrete example is the complement of a classifier κ corresponding to a DNF formula D with k terms of size exactly k, with all literals negative and no literal occurring twice. This function κ is k-AXp-interpretable, has kk prime implicants, and by monotonicity these implicants must be contained in distinct terms in any DNF expression of κ.

Corollary 1. Let κ : {0, 1}n → {0, 1} be a k-AXpinterpretable classifier over a set of features F. There exists a set E of at most 2kk subsets of F such that for every v ∈ {0, 1}n , E contains an AXp of size at most k of (κ, v).

Proof. Applying Theorem 1, we derive that κ and κ can be expressed as k-DNF formulas of size at most kk . The terms of these formulas are implicants of κ and κ respectively, and we can further assume that they are prime implicants. Let E be the set of all subsets of F whose features correspond exactly to a term. (Note that multiple terms may correspond to the same set of features, so E can be strictly smaller than the sum of the sizes of these formulas.) Then, for any choice of v at least one term evaluates to true and the corresponding set in E constitutes a wAXp of size at most k of (κ, v). Finally, this term corresponds to a prime implicant (of either κ or κ) so no strict subset can be a wAXp.

Another interesting consequence of Theorem 1 is that it provides an explicit characterisation of interpretable families of models (as per Definition 3).

Corollary 2. A family M of models is interpretable if and only if there exists a constant k such that every classifier κ ∈ M is expressible as a DNF formula of length at most k.

Proof. For the forward direction, if every classifier in M is j-AXp-interpretable then by Theorem 1 they are expressible as DNF formulas of length at most k = j · j j . Conversely, the complement of a DNF formula of length at most k > 0 is always expressible as a k-DNF of length at most kk+1 . Therefore, if every classifier in M is expressible as a DNF formula of length at most k thenM is interpretable.

4 InducedMatchings and Nested k-DNF

In this section we describe a simple criterion for a classifier described by a k-DNF formula to be k-AXp-interpretable. This criterion is orthogonal to expressibility as a decision tree of depth k, and we will show in the subsequent section that it defines a remarkably expressive family of classifiers.

Let D be a DNF formula that expresses a boolean function κ. A transversal of D is a subset of L(D) that intersects every term in D. If we let TD denote the set of all minimal transversals of D, then κ has the following canonical expression as a DNF:

Note that the canonical DNF expression of κ may include inconsistent terms. If D does not contain two terms t1, t2 such that t1 ⊂ t2, then the canonical complement of the canonical complement of D is D itself 1 . From this perspective, it is clear that the function expressed by a given k-DNF formula D is k-AXp-interpretable if all minimal transversals of D have cardinality at most k.

Let GD = (V, E) be the bipartite graph with V = L(D) ∪ T(D) and {l, t} ∈ E if and only if l ∈ t. An induced matching of GD is a subset M ⊆ E such that no two edges in M share an endpoint and no edge in E intersects two distinct edges in M. We denote by mim(GD) the maximum number of edges in an induced matching of GD.

Lemma 2. Let D be a k-DNF formula expressing a boolean function κ. If mim(GD) ≤ k, then κ is k-AXp-interpretable.

Proof. We show that every minimal transversal of D has cardinality at most k. Suppose for the sake of contradiction that D has a minimal transversal T of size q > k. By minimality, for every literal l ∈ T there exists a term tl ∈ T(D) such that tl ∩ T = {l}. Then, the set of edges {{l, tl} | l ∈ T} is an induced matching of GD of size q > k. This is not possible because mim(GD) ≤ k.

Example 3. Consider the majority function on 2k - 1 arguments defined by κmaj(x1, . . . , x2k-1) ≡ (∑2k-1 i=1 xi ≥ k). This function κmaj is k-AXp-interpretable since it is the disjunction of all terms composed of exactly k positive literals and its complement is the disjunction of all terms composed of exactly k negative literals.

The graphs associated with these formulas do not contain induced matchings of size larger than k, so κmaj satisfies the criterion for k-AXp-interpretability given by Lemma 2. However, it is well known that any decision tree representing κmaj must have depth at least 2k - 1, as any path starting from the root that alternates between positive and negative literals cannot reach a leaf before all variables have been assigned.

1 This is a well-known property of hypergraph dualisation, see e.g. [Berge, 1989, Chapter 2].

The simple condition provided by Lemma 2 already defines a new family of k-AXp-interpretable classifiers, those expressible by k-DNF formulas with no induced matchings of size k+1. From a practical viewpoint, the interest of this family is limited because its definition is not constructive: without a clear structure, it is difficult to design efficient heuristics for learning formulas of this kind directly from data.

We address this issue by defining a smaller family of classifiers whose structure is more explicit. Consider k2 literals ℓi,j (1 ≤ i, j ≤ k). We can view {ℓi,j} as a k × k matrix:

We will define a k-DNF D composed of m terms (where m is arbitrary) whose complement is also expressible as a k-DNF. For each p = 1, . . . ,m, let rpi (i = 1, . . . , k) be k integers between 0 and k such that ∑ki=1 rpi ≤ k. Then define D as follows:

The condition that ∑ki=1 rpi ≤ k for each p = 1, . . . ,m ensures that D is a k-DNF. We call such a DNF a nested kDNF. The term

of D is the conjunction of, for each i = 1, . . . , k, the rpi leftmost elements in row i of the matrix L.

Proposition 2. Every boolean function expressible as a nested k-DNF formula is k-AXp-interpretable.

Proof. Let D = ∨mp=1 ∧ki=1 ∧rpi j=1 ℓi,j be a nested k-DNF formula. Towards a contradiction, suppose that there exists an induced matching M of size k + 1 in GD. By the pigeonhole principle, at least two literals that appear in M belong to the same row iM of L. Two terms are matched with these two literals, and the term with the largest value for rpiM must contain both. This is impossible because M is an induced matching. Applying Lemma 2, the function expressed by D is therefore k-AXp-interpretable.

Example 4. Observe that all k-DNF formulas with q terms are nested if q ≤ k. Indeed, for any such formula D we can set L to be a k × k matrix of literals whose ith row contains the literals of the ith term of D (possibly with repetition if the term has fewer than k literals). Then, for p ≤ q we set rpi = k if p = i, and rpi = 0 otherwise. These parameters will produce exactly the formula D. In general, such formulas are not expressible as decision trees of depth smaller than k2 [Durdymyradov and Moshkov, 2024].

On the other hand, the function κmaj of Example 3 is not expressible as a nested k-DNF. We proceed again by contradiction. If κmaj could be represented by a nested k-DNF generated from a k ×k matrix L, then L would contain only positive literals. Let L1 be set of the literals in the first column of L, and J the other positive literals. All terms generated from L must contain at least one literal from L1. If |J| ≥ k, then there is a term consisting of k positive literals not occurring in the first column, and which therefore could not be generated. Hence, we must have |L1| = k and |J| = k - 1. Without loss of generality, assume L1 = {x1, . . . , xk} and J = {xk+1, . . . , x2k-1}. For each i = 1, . . . , k, the term xi ∧xj∈J xj must be generated from L by taking literals from a single row, since it contains a single literal from the first column of L. It follows that the columns 2, 3, . . . , k of L contain only elements of J. Since |J| = k - 1, the second column of L must contain at least one repeated element. Without loss of generality, assume that this repeated element is xk+1 and that it occurs in the two rows whose first elements are x1 and x2. But then, for k ≥ 3, it is impossible to generate the term x1x2xk+2 . . . x2k-1, since all terms containing x1 and x2 must also contain xk+1.

5 Expressivity of Nested k-DNFs

In machine learning, it is important that the language of models M used in the learning phase be sufficiently rich to capture all functions we might wish to learn. Consider a classifier κ that is a function of only k variables x1, . . . , xk. Both κ and its complement κ can be expressed as k-DNFs. This is because κ (respectively, κ) is the disjunction of the terms corresponding to the assignments to the variables x1, . . . , xk for which κ(x1, . . . , xk) = 1 (respectively, κ(x1, . . . , xk) = 1). All functions of k variables can be expressed as depth-k decision trees (with xi associated with all decision nodes at depth i - 1), so an obvious question is whether the same is true for nested k-DNFs. We answer this question positively in the following proposition.

Proposition 3. Every boolean function κ of k boolean variables can be expressed as a nested k-DNF.

Proof. If κ is the constant function 1, then it can be trivially expressed as a nested k-DNF that contains a single term with zero literals. We can therefore assume that κ is equal to 0 for some assignment to the k variables x1, . . . , xk. Without loss of generality, we assume that κ(0, . . . , 0) = 0. Let the k × k matrix of literals {ℓij} be

The classifier κ can be expressed as the disjunction of terms corresponding to assignments for which κ is equal to 1. Any such term t contains h positive literals, where h ≥ 1 (since a DNF satisfying κ(0, . . . , 0) = 0 cannot contain the term x1 · · · xk). Let xij (j = 1, . . . , h) be these positive literals. Let rij = ij+1 - ij (j = 1, . . . , h - 1), rih = k + i1 - ih and ri = 0 for all i /∈ {i1, . . . , ih}. Then t is the conjunction of the leftmost rij literals in row i (for i = 1, . . . , k) of the above matrix L. Since each term t of κ can be constructed in this way, κ is a nested k-DNF.

✩

✩

✪

✪

A consequence of Proposition 3 is that nested k-DNF formulas can always be constructed to fit any consistent dataset provided that k is large enough. In particular, the least integer k such that a boolean function or its complement can be represented as a nested k-DNF formula is a well-defined measure that cannot exceed the number of variables (as is the case for decision trees of depth k).

One criterion for comparing families of models M is to estimate the number of distinct functions that can be represented byM. Let NDT (k, n) and Nnested(k, n) be, respectively, the number of functions representable by a depth-k decision tree or by a nested k-DNF, where n is the total number of variables. Recall that nested k-DNF formulas can be function of at most k2 variables, whereas decision trees of depth k may depend on (up to) 2k - 1 variables. For this reason, it is expected that if n is large enough compared to k then Nnested(k, n) will necessarily be smaller than NDT (k, n). We show that the opposite is true when n is not much larger than k. Informally, nested k-DNF formulas involve fewer features than decision trees of depth k but can express a greater variety of dependencies between those features.

Proof. Every function representable by a decision tree of depth k can be represented by a complete tree with 2k leaves. Each of the 2k -1 internal nodes is associated with a variable and each of the 2k leaves is associated with a class. There are n2k-1 22k such decision trees, so NDT (k, n) ≤ n2k-1 22k .

We consider a fixed matrix L composed of k2 distinct positive literals ℓi,j . By the stars and bars theorem, the number of distinct terms of the form ∧ki=1 ∧ri j=1 ℓi,j where ∑ki=1 ri = k is exactly C 2k-1 k-1 = 1/2 · C 2k k . Using the inequality C 2k k ≥ 22k /√π(k + 1/3), we deduce that Nnested (k, n) is bounded below by 222k-1 /k for k ≥ 4, since each of the 1/2·C 2k k terms may or may not occur in the nested k-DNF formula. It follows that Nnested (k, n) > NDT (k, n) if n ≤ 22k-1 /k-1 .

Figure 1 provides a summary of the relationship between the major classes of k-AXp-interpretable classifiers.

6 Experiments

In this section, we present a heuristic algorithm for finding nested k-DNFs, distinguished by its intuitive and straightforward design 2 . It is worth noting that alternative algorithms could also be considered. Next, we provide an experimental comparison with the depth-k decision trees obtained by CART [Breiman et al., 1984].

6.1 Heuristic algorithm

The heuristic consists of three steps: constructing the matrix, constructing the nested k-DNF, and a pruning phase. In Algorithm 1, we show how to construct the k × k matrix L by proceeding row by row, where k is less than or equal to the total number of features n. The idea is to create a matrix that will allow us, in the next step, to generate a large number of distinct and consistent terms. To achieve this, the literal ℓi,j (0 ≤ i, j ≤ k - 1) is selected such that the j + 1 leftmost elements in row i of the matrix L are highly representative of class 1 while being minimally representative of class 0. A key condition is that ℓi,j must differ from the j preceding literals in row i and their negations (to avoid redundancy or inconsistency). Additionally, to encourage diversity between different rows, we exclude all literals in the first limit = k-j columns (of the already-chosen rows) from the list of candidate literals for ℓi,j, provided that at least one literal remains available for selection. The value of limit is reduced accordingly if the number 2(n - j) of available literals is less than or equal to the number i × (k - j) of literals we would like to forbid.

Secondly, we construct the nested k-DNF by evaluating one term at a time, starting with terms of size k and decreasing down to size 1. A term is considered for evaluation if it is consistent (i.e. it does not contain both a literal and its negation). We decide to select a term if P ̸= 0 and Q < P, where P (respectively, Q) represents the number of examples in class 1 (respectively, class 0) that satisfy this term and are not already covered by the selected terms. Furthermore, a term is also chosen if it covers at least one example from class 1 and does not cover any example from class 0 (irrespective of whether examples have already been covered). The process stops when either all examples in class 1 are covered or there are no more terms to evaluate. Finally, we perform pruning, where we determine whether to retain each term. The same evaluation as before is applied using P and Q (i.e. we remove a term if P = 0 or Q ≥ P ). This time, we compare each term against all other terms, not just the previously selected terms.

6.2 Datasets

A collection of datasets from the UCI repository and Kaggle are considered, which have been used to evaluate a wide range of learning algorithms. These datasets contain various feature types, which are converted into boolean features for binary classification as in [Demirovic et al., 2023]. We employ the datasets in their original form, without any preprocessing techniques applied. Table 1 shows, for each dataset, the number of data examples and the number of boolean features.

6.3 Results

As a first test, the proposed heuristic successfully found the 2-DNF with 2 terms that perfectly match the full truth-table

2 The code is available in this GitHub repository

Algorithm 1 Construct matrix

Input: k, dataset Output: matrix L 1: for i = 0 to k -1 do 2: for j = 0 to k - 1 do 3: if i = 0 then 4: limit = 0 5: else 6: limit = min(k - j, ⌈(2(n - j)/i) - 1⌉) 7: end if \\ Ec1(t): nb. examples in class 1 that satisfy t \\ Ec0(t): nb. examples in class 0 that satisfy t 8: Calculate G = Ec1(ℓi,0...ℓi,j) -Ec0(ℓi,0...ℓi,j) for each literal not in Li,0:j ∪Li,0:j ∪L0:i,0:limit 9: Take as ℓi,j the literal that gives the greatest G 10: end for 11: end for 12: return matrix L

generated from κ(a, b, c, d) = (a ∧ b) ∨ (c ∧ d). In contrast, the CART algorithm required a depth of 4 to create a decision tree that fits the data exactly, as mentioned in Example 2.

The rest of our experimental assessment was performed on the datasets described above. For a given dataset, 80% of the dataset was used for training and 20% for testing, except for the Monks datasets, where the test set is provided separately and consists of 432 examples, consisting of all possible combinations of the feature-values. The average performance across five split experiments is reported. For each of the two training algorithms, the experiment is run 10 times and the average accuracy is computed on the test set. Table 2 shows the accuracy of our nested k-DNFs (column DNF) and the decision trees generated by CART with a fixed maximum depth of k (column DT). Given the asymmetry of nested kDNFs with respect to complementation, we repeated the experiment, learning a nested k-DNF model for κ rather than κ: results are reported in column DNF.

The aim in using different datasets for experimentation is to assess whether the proposed heuristic can actually find a nested k-DNF that accurately represents the underlying structure of the data, as decision trees do. The results indicate variability in accuracy across different datasets, with nested k-DNFs outperforming depth-k decision trees in some cases, and vice versa in others. Overall, the results achieved by both depth-k decision trees and nested k-DNFs are comparable. Thus, nested k-DNFs emerge as a promising alternative to decision trees, with these initial results highlighting the potential of this family of models.

7 Conclusion and FutureWork

A machine-learning model can be deemed interpretable if each of its decisions has an explanation that is intelligible by a human user. We formalized this definition of interpretability based on abductive or counterfactual explanations of size at most a small constant k. In the case of binary classifiers over boolean domains, we showed that this definition is equivalent to the classifier and its complement both being expressible as k-DNFs. Depth-k decision trees are the most well-known example of a family of models satisfying this definition. Decision trees are widely used either directly or as surrogate models to provide explanations. This paper investigated the existence of other families of interpretable models.

We introduced a graph-theoretical sufficient condition for interpretability in terms of maximum induced matchings of DNF formulas, before giving a novel concrete family of interpretable models which we call nested k-DNFs. We showed experimentally that a simple heuristic algorithm produces nested k-DNFs whose accuracy is comparable with depth-k decision trees found by CART.

An intriguing open question is whether there exist more general families of interpretable DNFs that could achieve better accuracy than decision trees. In contrast to decision trees of depth k, the property of a function being expressible as a nested k-DNF is not invariant under complementation in general. In addition, nested k-DNFs cannot contain more than k2 distinct literals. These limitations come from our definitions and do not arise from fundamental technical reasons, so we believe there is ample room for further improvement.

Finally, our observations during the experiments revealed some variability in the test accuracy of the nested k-DNFs across different runs. This observation suggests that significantly better results could be achieved by using more sophisticated heuristics. In particular, it would be interesting to compare optimal nested k-DNFs and optimal depth-k decision trees.

Acknowledgments

This work was funded by the French National Research Agency (ANR) grant no. ANR-23-CE25-0009.