<figure><img src="image_1.png" /></figure>

HAL
open science

# On Explaining Decision Trees

Yacine Izza, Alexey Ignatiev, Joao Marques-Silva

► To cite this version:

Yacine Izza, Alexey Ignatiev, Joao Marques-Silva. On Explaining Decision Trees. 2021. hal-03312480

HAL Id: hal-03312480

https://hal.science/hal-03312480

Preprint submitted on 2 Aug 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On Explaining Decision Trees

Yacine Izza<fnref n="1" />, Alexey Ignatiev<fnref n="2" />, and Joao Marques-Silva<fnref n="3" />

¹ ANITI, Univ. Toulouse, France

² Monash Univ., Australia

³ ANITI, IRIT, CNRS, France

**Abstract.** Decision trees (DTs) epitomize what have become to be known as interpretable machine learning (ML) models. This is informally motivated by paths in DTs being often much smaller than the total number of features. This paper shows that in some settings DTs can hardly be deemed interpretable, with paths in a DT being arbitrarily larger than a PI-explanation, i.e. a subset-minimal set of feature values that entails the prediction. As a result, the paper proposes a novel model for computing PI-explanations of DTs, which enables computing one PI-explanation in polynomial time. Moreover, it is shown that enumeration of PI-explanations can be reduced to the enumeration of minimal hitting sets. Experimental results were obtained on a wide range of publicly available datasets with well-known DT-learning tools, and confirm that in most cases DTs have paths that are proper supersets of PI-explanations.

## 1 Introduction

Decision trees (DTs) are well known machine learning (ML) models, studied since at least the 1970s [22,27,14,50,52]. DTs embody what is widely regarded as an interpretable ML model [20,51,41,59,40,38,23,76,61]<fnref n="1" />. Motivated by this perception, there has been extensive work on learning DTs (and related logic ML models) with properties deemed important for interpretability, e.g. number of nodes, maximum/average depth, etc. [2,67,25,31,1,7,56,24,26,69,66,57,43,17,5,72,34,4,77,68,10,33,71,70,35,45,11,44]<fnref n="2" />. Moreover, there has been work on *distilling* or approximating complex ML models with (soft) decision trees [21,9,8,73,75,55,74]. Nevertheless, recent work highlights that interpretability should correlate with how shallow DTs are [36,41].

In contrast with earlier work, this paper investigates the limits of interpretability of DTs. Concretely, the paper proposes Boolean functions for which a minimal DT contains paths with a number of literals that is arbitrarily larger (growing with the number of features) than a PI-explanation<fnref n="3" /> of constant size. Experimental results demonstrate

<footnote n="1">¹ Interpretability is generally accepted to be a subjective concept, without a rigorous definition [36]. In this paper we measure interpretability in terms of the overall succinctness of the information provided by a model to explain a given prediction. The association of DTs with interpretability can be traced at least to Breiman [13], who summarizes the interpretability of DTs as follows: "*On interpretability, trees rate an A+*".</footnote>

<footnote n="2">² The association of DTs with interpretability is also illustrated by Interpretable AI (https://www.interpretable.ai/), which offers interpretability solutions based on optimal decision trees.</footnote>

<footnote n="3">³ A PI-explanation is a subset-minimal set of feature-value pairs that entails the prediction [60].</footnote>
that for widely used tools for constructing DT classifiers, the resulting DTs often con-
tain paths that are proper supersets of PI-explanations (which we refer as explanation-
redundant paths, in possibly irredundant DTs). Perhaps more importantly, for a signifi-
cant number of datasets, and for the obtained DTs, most of their paths are explanation-
redundant. The results also indicate that for some DTs, as much as 98% of feature space
will be explained by some path that is explanation-redundant. Motivated by these nega-
tive results, we propose a hitting set formulation for computing PI-explanations of DTs,
distinguishing explanations restricted to literals in a tree path, and explanations unre-
stricted to literals in a tree path. In addition, we propose a polynomial time algorithm
for computing a single PI-explanation for any given instance. Finally, the paper reduces
enumeration of PI-explanations of DTs to the problem of enumerating minimal hitting
sets (MHSes), and proposes a solution based on iterative calls to an NP oracle (e.g. SAT
or a 0-1 ILP) oracle.

The paper is structured as follows. Section 2 introduces the notation and definitions used in the remainder of the paper. Section 3 studies functions that elicit poor DT interpretability. Section 4 proposes a polynomial-time algorithm for computing a single PI-explanation for a DT. Section 5 proposes a solution for enumerating PI-explanations of DTs, by reducing the problem to the computation of MHSes. Section 6 studies the DTs obtained with two state-of-the-art tools, on publicly available datasets, and shows that paths in learned decision trees are often proper supersets of PI-explanations. Moreover, the experimental results confirm that run times for extracting PI-explanations are negligible. Finally, Section 7 concludes the paper.

## 2 Preliminaries

**Classification problems.** We consider a classification problem defined on a set of features $\mathcal{F} = \{1, \dots, n\}$, where each feature $i$ takes values from a (categorical) domain $D_i^4$, and $n$ denotes the number of features. Feature space is defined by $\mathbb{F} = D_1 \times D_2 \times \dots \times D_n$, each defining the range of (categorical) values of each feature $x_i$. To refer to an arbitrary point in feature space we use the notation $\mathbf{x} = (x_1, \dots, x_n)$, whereas to refer to a concrete point in feature space we use the notation $\mathbf{v} = (v_1, \dots, v_n)$, with $v_i \in D_i$, $i = 1, \dots, n$. We consider a binary classification problem, with two classes $\mathcal{K} = \{\ominus, \oplus\}^5$. (For simplicity, we will often use 0 for $\ominus$ and 1 for $\oplus$.) An *instance* (or example) denotes a pair $(\mathbf{v}, \mathbf{\pi})$, where $\mathbf{v} \in \mathbb{F}$ and $\mathbf{\pi} \in \mathcal{K}$. A machine learning model computes a function $\mu$ that maps the feature space into the set of classes: $\mu: \mathbb{F} \to \mathcal{K}$. To train an ML model (in our case we are interested in DTs), we start from a set of examples $\mathcal{E} = \{e_1, \dots, e_m\}$, where each $e_j = (v_j, \pi_j)$, such that $v_j \in \mathbb{F}$ and $\pi_j \in \mathcal{K}$, and $m$ is the number of examples.

**Decision trees.** A decision tree $\mathcal{T}$ is a directed acyclic graph having at most one path between every pair of nodes. $\mathcal{T}$ has a root node, characterized by having no incoming edges. All other nodes have one incoming edge. We consider univariate decision trees

<footnote n="4">⁴ For simplicity, most of the examples in the paper consider $D_i \triangleq \{0, 1\}$ (i.e. binary features).</footnote>

<footnote n="5">⁵ The results in the paper are readily applicable to multiple classes; the case $|\mathcal{K}| = 2$ is considered solely for simplicity.</footnote>
(as opposed to multivariate decision trees [16]); hence, a non-terminal node is associated with a single feature $x_i$, and each outgoing edge is associated with one (or more) values from $D_i$. Each terminal node is associated with a value of $\mathcal{K}$. An example of a decision tree is shown in Figure 2. The number of nodes in a DT is $r$. When $|\mathcal{K}| = 2$, a tree is characterized by two sets of paths, where each path starts at the root and ends at a terminal node. The set $\mathcal{P} = \{P_1, \dots, P_{k_1}\}$ denotes the paths ending in a $\oplus$ prediction. The set $\mathcal{Q} = \{Q_1, \dots, Q_{k_2}\}$ denotes the paths ending in a $\ominus$ prediction. We will also use $\mathcal{R} = \mathcal{P} \cup \mathcal{Q}$. A literal is of the form $x_i \bowtie v_i$, where $\bowtie \in \{=, \ne\}^6$. $x_i$ is a variable that denotes the value taken by feature $i$, whereas $v_i \in D_i$ is a constant. To model the operation of some DT learning tools [64], we allow generalized literals of the form $x_i \in S_i$, with $S_i \subseteq D_i$, such that the literal is consistent if the feature is assigned a value in $S_i$. Given this generalization, DTs correspond to multi-edge decision trees [6]. Moreover, two literals are inconsistent if they cause the feature to take values that are inconsistent. For example, the literals $(x_1 = 0)$ and $(x_1 = 1)$ are inconsistent.

Each path in $\mathcal{T}$ is associated with a consistent conjunction of literals, denoting the values assigned to the features so as to reach the terminal node in the path. We will represent the set of literals of some tree path by $\mathcal{L}(R_k)$, where $R_k$ is either a path in $\mathcal{P}$ or $\mathcal{Q}$. Each path in the tree *entails* the prediction represented by path's terminal node. Let $\pi$ denote the prediction associated with path $R_k$. Then,

$$ \forall (\mathbf{x} \in \mathbb{F}). \left[ \bigwedge_{(x_i \bowtie v_i) \in \mathcal{L}(R_k)} (x_i \bowtie v_i) \right] \rightarrow (\mu(\mathbf{x}) = \pi) \quad (1) $$

where $\mathbf{x} = (x_1, \dots, x_i, \dots, x_n)$ and $\pi \in \{\ominus, \oplus\}$. Any pair of paths in $\mathcal{R}$ must have at least one pair of inconsistent literals.

**Interpretability & DTs.** Interpretability is generally regarded as a subjective concept, without a rigorous definition [36], albeit different authors have proposed different requirements for interpretability [36,62]. Throughout this paper, we associate interpretability with irreducible sets of feature-value pairs that are sufficient for the prediction<fnref n="7" />. Moreover, as argued in Section 1, it is generally accepted that DTs epitomize interpretability. Nevertheless, there is recent work that relates DT interpretability with DTs being shallow [36,41], but also work that proposes counterfactual explanations for meeting interpretability desiderata for DTs [62].

**PI-explanations.** The paper uses the definition of PI-explanation [60], based on prime implicants of some decision function. Let us consider some ML model, computing a classification function $\mu$ on feature space $\mathbb{F}$, a point $v \in \mathbb{F}$, with prediction $\pi = \mu(v)$, and let $E$ denote a set of literals consistent with $v$ (and defined on features variables $\mathbf{x}$). We say that $E$ is a PI-explanation for $\pi$ given $v$, if the set of literals $E$ entails the prediction, and any proper subset of literals of $E$ does not entail the prediction. Formally,

<footnote n="6">⁶ The ideas described in the paper generalize to univariate DTs where features are either categorical or real- or integer-valued ordinal, and literals are of the form $x_i \bowtie v_i$, where $\bowtie \in \{<, \le, =, \ne, \ge, >\}$. The paper's main results can be extended to more general settings, but that these are beyond the scope of the paper.</footnote>

<footnote n="7">⁷ Clearly, these subsets should be succinct, as it is generally accepted that human decision makers are only able to understand explanations with a reasonably small number of features.</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 1: Example DTs</figcaption></figure>

the following conditions hold:

$$ \forall (\mathbf{x} \in \mathbb{F}). \left[ \bigwedge_{l_i \in E} (l_i) \right] \rightarrow (\mu(\mathbf{x}) = \pi) \quad (2a) $$

$$ \forall (E' \subsetneq E) \exists (\mathbf{x} \in \mathbb{F}). \left[ \bigwedge_{l_i \in E'} (l_i) \right] \wedge (\mu(\mathbf{x}) \neq \pi) \quad (2b) $$

Given a DT $\mathcal{T}$ and some path $R_k$, associated with some prediction $\pi$, we say that path $R_k$ is explanation-redundant (or simply redundant) if $R_k$ is not a PI-explanation of $\pi$ given the ML model $\mathcal{T}$. If we associate DT paths with instance explanations, then path explanation-redundancy will manifest itself in instance explanations. The concept of explanation-redundancy is illustrated in Example 1.

**Example 1.** Consider the DT in Figure 1a, for function $f(x_1, x_2) = x_1 \lor x_2$, and instance $(0, 1)$. The path corresponds to the explanation $\{(x_1, 0), (x_2, 1)\}$ for prediction $f(0, 1) = 1$. Clearly, this path is explanation-redundant, as a PI-explanation for prediction 1 is $(x_2, 1)$ (as is readily concluded from the function definition).

As a less abstract example, we observe that the tree in Figure 1a also models the example DT used in [78, Ch. 01, page 5]<fnref n="8" />, with $x_1$ denoting “is $y > 0.73?”, $x_2$ denoting “is $x > 0.64?”, class 1 denoting cross, and class 0 denoting circle. Hence, a PI-explanation for the instance (no,yes) with prediction “cross” is yes to question “is $x > 0.64?”, independently of the answer to question “is $y > 0.73?”. Section 3 investigates explanation-redundancy in greater detail.

**Related work.** As referenced in Section 1, there exists a growing body of work on exploiting DTs for interpretability. To our best knowledge, the assessment of paths in DTs when compared to PI-explanations has not been investigated. Recent work [18] outlines logical encodings of decision trees, but that is orthogonal to the work reported in this paper. In addition, there has been work on applying explainable AI (XAI) to decision trees [37], but with the focus of improving the quality of local (heuristic) explanations,

<footnote n="8">⁸ This DT is shown in the supplementary material.</footnote>
where the goal is to relate a local approximate model against a reference model; hence
there is no immediate relationship with PI-explanations.

3 Decision Trees May Not be Interpretable

This section shows that there exist Boolean functions for which a learned decision tree
will exhibit paths containing all features, and for which a PI-explanation has a con-
stant size. Thus, if we associate explanations with DT paths, there will be explana-
tions that are arbitrally larger (on *n*) than the actual (constant-size) PI-explanation. As
the experimental results demonstrate, and as discussed later in this section, it is fairly
frequent in practice for DT paths to include more literals that those in the associated
PI-explanations.

**Proposition 1.** *There exist functions for which an irreducible DT contains paths which are a proper superset of a PI-explanation. Furthermore, the difference in the number of literals is *n* − *k*, where *n* is the number of features and *k* is the (constant) size of a PI-explanation.*

*Proof.* Let us consider the following Boolean function $f : \{0, 1\}^n \to \{0, 1\}$ (with even $n$):

$$
f(x_1, x_2, \dots, x_{n-1}, x_n) = \bigvee_{i=1}^{n/2} x_{2i-1} \wedge x_{2i} \qquad (3)
$$

For the case $n=4$, different off-the-self DT learners will obtain the DT shown in Figure 1b. (To obtain the decision tree, we considered a dataset composed of all possible instances, and used ITI [64]<fnref n="9" />.) Furthermore, it is immediate to conclude that the decision tree shown is irreducible (i.e. no nodes can be removed while keeping accuracy). Moreover, let the target instance be $(\mathbf{v}, \pi) = ((1,0,1,1), 1)$. In this case, the explanation (i.e. the path) extracted from the DT is $(x_1 = 1) \land (x_2 = 0) \land (x_3 = 1) \land (x_4 = 1)$, which guarantees that the prediction is 1. However, it is immediate from the function definition (3), that $(x_3 = 1) \land (x_4 = 1)$ entails $f(x_1,x_2,x_3,x_4) = 1$, *independently* of the value assigned to $x_1$ and $x_2$, i.e. in this case the PI-explanation is $(x_3 = 1) \land (x_4 = 1)$. The same analysis generalizes to an arbitrary number of variables. For an instance of the form $((1,0,1,0,\dots,1,0,1,1), 1)$, the DT would indicate an explanation with *n* literals, whereas the PI-explanation has size 2, namely $(x_{n-1} = 1) \land (x_n = 1)$. □

It should be noted that the issue above does not depend on whether the DT is
redundant (e.g. in the cases shown, the DTs are *not* redundant); the reported issues
result solely from a fundamental limitation of DTs for succinctly representing cer-
tain classes of functions<fnref n="10" />. Figure 2 exemplifies that redundancy may occur even in
very simple DTs. The DT was obtained with the optimal decision tree package from

<footnote n="9">⁹ ITI is available from https://www-lrn.cs.umass.edu/iti/. We considered a number of publicly available DT learners, and reached the same conclusions (in terms of path length) in all cases.</footnote>

<footnote n="10">¹⁰ Indeed, it is well-known that DTs are not as succinct as decision lists (DLs) [52] (and so not as succinct as decision sets (DSs)). This means that there exist functions that have succint DLs or DSs, but not DTs. Although not the focus of the paper, we conjecture that similar results can be obtained for DLs and for restricted cases of DSs, among those where DSs compute functions.</footnote>
<table><caption>(a) Features for *PlayTennis* dataset</caption><thead><tr><th>Feature</th><th>Name</th><th>Domain</th><th>Values</th><th>Meaning</th></tr></thead><tbody><tr><td>x<sub>0</sub></td><td>Humidity</td><td>D<sub>0</sub></td><td>{0, 1}</td><td>normal,high</td></tr><tr><td>x<sub>1</sub></td><td>Outlook</td><td>D<sub>1</sub></td><td>{0, 1, 2}</td><td>overcast,rain,sunny</td></tr><tr><td>x<sub>2</sub></td><td>Wind</td><td>D<sub>2</sub></td><td>{0, 1}</td><td>strong,weak</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>(b) Resulting DT</figcaption></figure>

<caption>Fig. 2: Another Example DT</caption>

Interpretable AI [10,28]<fnref n="11" />, where the ⊖ and the leftmost ⊕ are predicted with 75% and 83.3% confidence, respectively. (The branch annotated with 1, 2 denotes that $x_1 \in \{1, 2\}$.) Let the instance be (Humidity, Outlook, Wind) = (high, overcast, weak). As an explanation we could use the literals in the tree path, i.e. { (Humidity = high), (Outlook = overcast) }. However, careful analysis allows us to conclude that { (Outlook = overcast) } suffices to entail the prediction ⊕, i.e. as long as 'Outlook' is 'overcast', the prediction will be ⊕ *independently* of the value of 'Humidity'.

## 4 Extracting PI-Explanations from DTs

**Deciding explanation-redundancy with NP oracles.** Let us consider a decision tree $\mathcal{T}$, with sets of paths $\mathcal{P}$ and $\mathcal{Q}$, denoting respectively the paths with prediction ⊕ and ⊖. Let us also consider an instance $(\mathbf{v}, \oplus)$, with $\mathbf{v} \in \mathbb{F}$ and $\oplus \in \mathcal{K}$ (the case for ⊖ would be similar), and let $P_k$ denote that path consistent with $\mathbf{v}$. To decide whether $P_k$ exhibits explanation-redundancy, one possible solution is to use an NP oracle.

For an instance consistent with $P_k$, we can model the prediction of the decision tree (for prediction ⊕) as follows:

$$ \bigwedge_{l_j \in \mathcal{L}(P_k)} (I_j) \models \bigvee_{P_i \in \mathcal{P}} \bigwedge_{l_s \in \mathcal{L}(P_i)} (I_s) \quad (4) $$

Hence, we require the unsatisfiability of,

$$ \bigwedge_{l_j \in \mathcal{L}(P_k)} (I_j) \wedge \bigwedge_{P_i \in \mathcal{P}} \bigvee_{l_s \in \mathcal{L}(P_i)} (\neg I_s) \quad (5) $$

Now, if there exists a literal $l_j$ that can be dropped from $P_k$ such that unsatisfiability is preserved, then $P_k$ exhibits explanation-redundancy. Hence, we need at most $m$ calls to an NP oracle to decide explanation-redundancy, where $m$ is the number of features. (This high-level procedure was proposed in earlier work in more general terms [29].) However, the special structure of a DT, makes the problem far simpler, and can be solved in polynomial time, as shown next.

<footnote n="11">¹¹ We used the well-known *PlayTennis* dataset [39].</footnote>
**Deciding explanation-redundancy in linear time.** Observe that (4) is preserved iff at least one of the features with a literal in $P_k$ has another literal that is false along any path that yields prediction $\ominus$. Thus, there is explanation-redundancy if there exists a literal from $P_k$ that can be dropped while the remaining literals in $P_k$ still guarantee that at least one literal is false along any path in $Q$. Before detailing a polynomial time algorithm for deciding explanation-redundancy, let us consider a concrete example.

**Example 2.** For the DT from Figure 1b we have,

$$ 
\begin{align*}
\mathcal{P} &= \{P_1, P_2, P_3\} \\
\mathcal{L}(P_1) &= \{(x_1 = 0), (x_3 = 1), (x_4 = 1)\} \\
\mathcal{L}(P_2) &= \{(x_1 = 1), (x_2 = 0), (x_3 = 1), (x_4 = 1)\} \\
\mathcal{L}(P_3) &= \{(x_1 = 1), (x_2 = 1)\} \\
\mathcal{Q} &= \{Q_1, Q_2, Q_3, Q_4\} \\
\mathcal{L}(Q_1) &= \{(x_1 = 0), (x_3 = 0)\} \\
\mathcal{L}(Q_2) &= \{(x_1 = 0), (x_3 = 1), (x_4 = 0)\} \\
\mathcal{L}(Q_3) &= \{(x_1 = 1), (x_2 = 0), (x_3 = 0)\} \\
\mathcal{L}(Q_4) &= \{(x_1 = 1), (x_2 = 0), (x_3 = 1), (x_4 = 0)\}
\end{align*}
$$

We consider path $P_2$ (and so any feature space point consistent with $P_2$). We can readily conclude that if literal $(x_1 = 1)$ is removed from the literals of $P_2$, all the paths in $Q$ remain inconsistent. This is true for example because $(x_3 = 1)$ and $(x_4 = 1)$. Similarly, we could drop literal $(x_2 = 0)$.

The example above naturally suggests a quadratic time (on the size $n$ of the decision tree) algorithm to decide whether a tree path exhibits explanation-redundancy. Concretely, for each literal in $P_k$, we analyze each path in $Q$ whether it is still inconsistent. If all paths in $Q$ remain inconsistent, then the literal can be dropped, and the path exhibits explanation-redundancy. Nevertheless, it is possible to devise a more efficient solution, one that runs in linear time.

The proposed algorithm analyzes the features containing literals in $P_i^{12}$, in turn allowing each to be declared *universal*, i.e. the feature can take any value. For each feature $f_j$, the algorithm recursively analyzes paths with a different prediction, checking whether each such path is inconsistent, due to some other literal. If that is the case, the path $P_i$ is explanation-redundant, at least due to feature $f_j$. The algorithm analyzes the internal nodes of $P_i$ in reverse order, starting from deepest non-terminal node in the path. (For now, we assume that $P_i$ has at most one literal on any given feature; this restriction will be lifted below.) For each non-terminal node $p_j \in P_i$, the associated feature $f_j$ is made universal, i.e. it can take *any* value. Starting at $p_j$, all child nodes not in $P_i$ are recursively visited, checking for a consistent sub-path (starting at $p_j$) to a terminal node with prediction $\ominus$. If such path exists, then $f_j$ cannot be made universal, and so it cannot be discarded from a PI-explanation. Otherwise, all sub-paths to prediction $\ominus$ are inconsistent, and so the value of $f_j$ is irrelevant for the prediction. A path is declared redundant iff at least one feature is declared redundant. With filtering (i.e. $rec = 0$), each tree node is analyzed at most once, and so the amortized

<footnote n="12">¹² As before, we assume a path $P_i$ with prediction $\ominus$.</footnote>
<table><caption>Algorithm 1: Deciding path redundancy</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>foreach</td><td>R<sub>k</sub> ∈ T do</td></tr><tr><td>2</td><td></td><td>A ← AggrFeatureNodes(T, R<sub>k</sub>);</td></tr><tr><td>3</td><td></td><td>N ← PathNodes(T, R<sub>k</sub>);</td></tr><tr><td>4</td><td></td><td>isPathRed ← false;</td></tr><tr><td>5</td><td>foreach</td><td>f ∈ PathFeatures(T, R<sub>k</sub>) do</td></tr><tr><td>6</td><td></td><td>isFeatRed ← true;</td></tr><tr><td>7</td><td></td><td>SetUniversal(T, f);</td></tr><tr><td>8</td><td>foreach</td><td>n ∈ A(f) do</td></tr><tr><td>9</td><td></td><td>if not CHKDOWN(T, N, R<sub>k</sub>, n, 0) then</td></tr><tr><td>10</td><td></td><td>isFeatRed ← false;</td></tr><tr><td>11</td><td></td><td>break;</td></tr><tr><td>12</td><td></td><td>if isFeatRed then</td></tr><tr><td>13</td><td></td><td>isPathRed ← true;</td></tr><tr><td>14</td><td></td><td>break;</td></tr><tr><td>15</td><td></td><td>ReportPath(R<sub>k</sub>, isPathRed);</td></tr></tbody></table>

run time of the algorithm over all features is $O(|T|)$. If a feature is tested more than once along $P_i$, the algorithm requires minor modifications. In this case, a decision about whether feature $f_i$ can take any value, can only be made once all nodes involving $f_i$ have been analyzed and, for all such nodes, the feature $f_i$ has been declared redundant. Algorithms 1 and 2 summarize the two main steps of the proposed algorithm. The auxiliary functions serve to test/set whether a feature is universal (i.e. whether it can take any value of its domain) (resp. Universal/SetUniversal), aggregate the nodes associated with a given feature along some path (AggrFeatureNodes), list the nodes in a given path (PathNodes), get the prediction of some path (Prediction), list the child nodes of some node in the tree (ChildNodes), get the feature associated with a node (Feature), check whether some node is terminal (IsTerminal) and, finally, whether the sub-paths starting at some node can reach a prediction other than the one associated with the target path $R_k$ (HasPaths). Finally, the argument rec of CHKDOWN is a flag that serves to avoid re-visiting already visited paths. For removing redundant features this filtering does not apply, as clarified below.

**Example 3.** We consider again the DT from Figure 1b and path $P_2$, where $\mathcal{L}(P_2) = \{(x_1 = 1), (x_2 = 0), (x_3 = 1), (x_4 = 1)\}$, and prediction 1. The nodes of $P_2$ are analyzed in the order $\langle x_4, x_3, x_2, x_1 \rangle$. Clearly, the sub-path consistent with $(x_4 = 0)$ yields prediction 0. Hence, feature $x_4$ (associated with literal $x_4 = 1$) is not redundant. For $x_3$, we consider (only) the sub-path corresponding to $(x_3 = 0)$. Again, the prediction is 0, and so the feature $x_3$ is not redundant. For feature $x_2$, the only sub-path corresponds to $(x_2 = 1)$, for which the prediction remains unchanged. Hence, $x_2$ can take any value, and so it is declared redundant. As a result, $P_2$ is also declared redundant. It is helpful to analyze the execution of the algorithm for $x_1$. The sub-paths consistent with $(x_1 = 1)$ correspond to $P_1$, $Q_1$ and $Q_2$. Hence, due to $Q_1$ and $Q_2$, it might seem that $x_1$ might
<table><caption>Algorithm 2: Inconsistent sub-path lookup</caption><thead><tr><th></th><th>Function CHKDOWN (<i>T</i>, <i>N</i>, <i>R</i><sub>k</sub>, <i>n</i>, <i>rec</i>)</th></tr></thead><tbody><tr><td>1</td><td><i>π</i> &larr; Prediction(<i>T</i>, <i>R</i><sub>k</sub>);</td></tr><tr><td>2</td><td><i>C</i> &larr; ChildNodes(<i>T</i>, <i>n</i>);</td></tr><tr><td>3</td><td><b>foreach</b> <i>c</i> &isin; <i>C</i> <b>do</b></td></tr><tr><td>4</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<b>if</b> <i>c</i> &isin; <i>N</i> and <i>rec</i> = 0 <b>then</b> <b>continue</b>;</td></tr><tr><td>5</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<b>if</b> <b>not</b> HasPaths(<i>T</i>, <i>c</i>, <i>π</i>) <b>then</b> <b>continue</b>;</td></tr><tr><td>6</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<b>if</b> IsTerminal(<i>T</i>, <i>c</i>) <b>then</b></td></tr><tr><td>7</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<b>return</b> <b>false</b>;</td></tr><tr><td>8</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>g</i> &larr; Feature(<i>T</i>, <i>c</i>);</td></tr><tr><td>9</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<b>if</b> <b>not</b> Universal(<i>T</i>, <i>g</i>) <b>then</b> <b>continue</b>;</td></tr><tr><td>10</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<b>if</b> <b>not</b> CHKDOWN(<i>T</i>, <i>N</i>, <i>R</i><sub>k</sub>, <i>c</i>, <i>rec</i>) <b>then</b></td></tr><tr><td>11</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<b>return</b> <b>false</b>;</td></tr><tr><td>12</td><td><b>return</b> <b>true</b>;</td></tr></tbody></table>

be irredundant. However, both $Q_1$ and $Q_2$ are inconsistent with other non-redundant literals of $P_2$, concretely $x_3 = 1$ and $x_4 = 1$. Hence, $x_1$ is declared redundant.

**Extracting one PI-explanation.** One approach to find a PI-explanation is to use recent work based on compilation [60] or iterative entailment checks with an NP oracle [29]. However, a computationally simpler solution is based on the ideas described above.

Features are analyzed as proposed in Algorithms 1 and 2. However, a feature already declared as redundant signifies that it can take *any* value from its domain. This may allow inconsistent paths with prediction $\ominus$ to become consistent, thus preventing some other feature from being declared redundant. One consequence is that the filtering of paths exploited in Algorithms 1 and 2 is not longer applicable. Concretely, the analysis of each feature requires visiting all of the sub-paths starting in any of the path nodes testing the feature. Algorithm 2 can still be used, in this case by setting `rec` to 1, i.e. all sub-paths will be analyzed. The worst-case complexity of the resulting algorithm is $O(|T|)$ for each feature, thus yielding $O(|T|^2)$ for the complete algorithm. Finally, we can conclude that an algorithm for finding one PI-explanation for each path in $T$ runs in $O(|T|^3)$.

**Example 4.** We consider the DT from Figure 1b and analyze path $P_2$ (and so *any* instance consistent with $P_2$). Literals are analyzed in reverse path order. (In this case, aggregation of nodes by feature is optional, as long as a decision with respect to a feature is delayed until all nodes associated with the feature have been analyzed, and keeping track whether non-irredundancy applies to all nodes.) As before, the literal $(x_4 = 1)$ is not redundant; otherwise $Q_4$ would be consistent. Similarly, the literal $(x_3 = 1)$ is not redundant; otherwise $Q_3$ would be consistent. In contrast, the feature $x_2$ can be made universal, as this does not change the prediction, i.e. $P_2$ is consistent with the prediction, and the other literals $(x_3 = 1)$ and $(x_4 = 1)$ block the paths in $Q$. A similar analysis applies in the case of feature $x_1$. In this case, the algorithm analyzes all paths
<figure><img src="image_5.png" /><figcaption>Fig. 3: Path-restricted vs. path-unrestricted explanations</figcaption></figure>

(since Algorithm 2 is invoked with rec = 1). Due to the literals $(x_3 = 1)$ and $(x_4 = 1)$, all paths in $\mathcal{Q}$ are inconsistent. As a result, feature $x_1$ can be declared redundant, and a PI-explanation for $P_2$ is thus $\{(x_3 = 1), (x_4 = 1)\}$.

**Path-restricted vs. path-unrestricted explanations.** For the algorithms described earlier we also need to decide the set of literals to consider. One option is the set of literals specified by the instance. Another option is the set of literals specific to the tree path consistent with the instance. If we are interested in finding PI-explanations for the prediction, given the instance, then we should consider the literals specified by the instance. However, if we want to report explanations that relate with the tree path consistent with the instance, then we should consider only the literals in the tree path. Clearly, path-restricted PI-explanations are a subset of path-unrestricted PI-explanations. The following example illustrates the differences between the two approaches.

*Example 5.* We consider the example DT shown in Figure 3. Given the point $(x_1, x_2, x_3, x_4) = (1, 1, 1, 1)$, the consistent path in the DT consists of the literals $\{(x_1 = 1), (x_3 = 1)\}$. The only PI-explanation that is restricted to this path is the path itself: $\{(x_1 = 1), (x_3 = 1)\}$. However, if we enable path-unrestricted explanations, we will also obtain the PI-explanation $\{(x_2 = 1), (x_3 = 1), (x_4 = 1)\}$, which is not even shown as (part of) a path in the decision tree.

# 5 Enumeration of PI-Explanations

The enumeration of multiple (or all) PI-explanations can help human decision makers to develop a better understanding of some prediction, but also of the underlying ML model. Recent work [60] compiles a decision function into a Sentential Decision Diagram (SDD), from which the enumeration of PI-explanations can be instrumented. Moreover, from a compiled representation of the PI-explanations, each PI-explanation can be reported in polynomial time. The downside is that these representation are worst-case exponential in the size of the original ML model. Another line of work for computing PI-explanations is based on iterative entailment checks using an NP-oracle [29]. However, this recent work does not address the enumeration of PI-explanations. This section develops a solution for the enumeration of PI-explanations in the case of DTs, by reduction to the enumeration of minimal hitting sets (MHSes).
We consider the situation where the prediction is $\oplus$ for some point v in feature space, which is consistent with some tree path $P_k \in \mathcal{P}$. As a result, each path in $\mathcal{Q}$ is inconsistent with at least one literal, among those either associated with v or with $P_k$. Let the set of literals considered be R. For each path $Q_s \in \mathcal{Q}$, let $L_s$ denote the set of literals in R that are inconsistent with $Q_s$. For a subset S of R to entail the prediction, it must hit each set of literals $L_s$. Among the possible sets S, each subset-minimal set is a PI-explanation. Thus, we can list the PI-explanations (starting from the literals taken from v or from $P_k$) by enumerating minimal hitting sets.

**Example 6.** For $P_2$ in the DT of Figure 1, the sets to hit are:

$$ 
\begin{array}{l}
Q_1: \{(x_1 = 1), (x_3 = 1)\} \quad Q_2: \{(x_1 = 1), (x_4 = 1)\} \\
Q_3: \{(x_3 = 1)\} \quad Q_4: \{(x_4 = 1)\}
\end{array}
$$

In this case, the only MHS is $\{(x_3 = 1), (x_4 = 1)\}$, representing a single PI-explanation $\{(x_3 = 1), (x_4 = 1)\}$.

**Example 7.** For the DT in Figure 3, and by considering the literals from the point v = (1, 1, 1, 1), the sets to hit are then:

$$ 
\begin{array}{l}
Q_1: \{(x_1 = 1), (x_2 = 1)\} \quad Q_2: \{(x_1 = 1), (x_4 = 1)\} \\
Q_3: \{(x_3 = 1)\}
\end{array}
$$

The MHSes are $\{(x_1 = 1), (x_3 = 1)\}$ and $\{(x_2 = 1), (x_4 = 1), (x_3 = 1)\}$, each denoting a path-unrestricted PI-explanation.

# 6 Experimental Results

This section presents a summary of experimental evaluation of the explanation-redundancy of two state-of-the-art heuristic DT classifiers. Concretely, we use the well-known DT training tools ITI (Incremental Tree Induction) [64,30] and IAI (Interpretable AI) [10,28]. ITI is run with the pruning option enabled, which helps avoiding overfitting and aims at constructing shallow DTs. To enforce IAI to produce shallow DTs and achieve high accuracy, it is set to use the optimal tree classifier method with the maximal depth of 6¹³. The experiments consider datasets with categorical (non-binarized) data, which both ITI and IAI can handle<fnref n="14" />. The assessment is performed on a selection of 80 publicly available datasets, which originate from UCI Machine Learning Repository [63], Penn Machine Learning Benchmarks [48], and OpenML repository [46]. (Due to space restrictions, we report the results only for 30 datasets but the results shown extend to the complete benchmark set, and are included in the supplementary materials.) The number of features (data instances, resp.) in the benchmark suite vary from 2 to 118 (106 to 58000, resp.) with the average being 31.2 (6045.3, resp.).

<footnote n="13">¹³ Our results confirm that larger maximal depths would in most cases increase the percentage of redundant paths. A smaller maximal depth would not improve accuracy.</footnote>

<footnote n="14">¹⁴ Other known DT learning tools, including scikit-learn [47] and DL8.5 [1,2] can only handle numerical and binary features, respectively, and so could not be included in the experiments.</footnote>
<table><caption>Table 1: Explanation-redundancy in decision trees obtained with IAI and ITI.</caption><thead><tr><th rowspan="2">Dataset</th><th rowspan="2">(#F)</th><th rowspan="2">#S)</th><th colspan="7">IAI</th><th colspan="7">ITI</th></tr><tr><th>D</th><th>#N</th><th>%A</th><th>#P</th><th>%R</th><th>%C</th><th>%m</th><th>%M</th><th>%avg</th><th>D</th><th>#N</th><th>%A</th><th>#P</th><th>%R</th><th>%C</th><th>%m</th><th>%M</th><th>%avg</th></tr></thead><tbody><tr><td>adult</td><td>(12</td><td>6061)</td><td>6</td><td>83</td><td>78</td><td>42</td><td>33</td><td>25</td><td>20</td><td>40</td><td>25</td><td>17</td><td>509</td><td>73</td><td>255</td><td>75</td><td>91</td><td>10</td><td>66</td><td>22</td></tr><tr><td>anneal</td><td>(38</td><td>886)</td><td>6</td><td>29</td><td>99</td><td>15</td><td>26</td><td>16</td><td>16</td><td>33</td><td>21</td><td>9</td><td>31</td><td>100</td><td>16</td><td>25</td><td>4</td><td>12</td><td>20</td><td>16</td></tr><tr><td>backache</td><td>(32</td><td>180)</td><td>4</td><td>17</td><td>72</td><td>9</td><td>33</td><td>39</td><td>25</td><td>33</td><td>30</td><td>3</td><td>9</td><td>91</td><td>5</td><td>80</td><td>87</td><td>50</td><td>66</td><td>54</td></tr><tr><td>bank</td><td>(19</td><td>36293)</td><td>6</td><td>113</td><td>88</td><td>57</td><td>5</td><td>12</td><td>20</td><td>18</td><td>19</td><td>1467</td><td>86</td><td>734</td><td>69</td><td>64</td><td>7</td><td>63</td><td>27</td></tr><tr><td>biodegradation</td><td>(41</td><td>1052)</td><td>5</td><td>19</td><td>65</td><td>10</td><td>30</td><td>1</td><td>25</td><td>50</td><td>33</td><td>8</td><td>71</td><td>76</td><td>36</td><td>50</td><td>8</td><td>14</td><td>40</td><td>21</td></tr><tr><td>cancer</td><td>(9</td><td>449)</td><td>6</td><td>37</td><td>87</td><td>19</td><td>36</td><td>9</td><td>20</td><td>25</td><td>21</td><td>5</td><td>21</td><td>84</td><td>11</td><td>54</td><td>10</td><td>25</td><td>50</td><td>37</td></tr><tr><td>car</td><td>(6</td><td>1728)</td><td>6</td><td>43</td><td>96</td><td>22</td><td>86</td><td>89</td><td>20</td><td>80</td><td>45</td><td>11</td><td>57</td><td>98</td><td>29</td><td>65</td><td>41</td><td>16</td><td>50</td><td>30</td></tr><tr><td>colic</td><td>(22</td><td>357)</td><td>6</td><td>55</td><td>81</td><td>28</td><td>46</td><td>6</td><td>16</td><td>33</td><td>20</td><td>4</td><td>17</td><td>80</td><td>9</td><td>33</td><td>27</td><td>25</td><td>25</td><td>25</td></tr><tr><td>compas</td><td>(11</td><td>1155)</td><td>6</td><td>77</td><td>34</td><td>39</td><td>17</td><td>8</td><td>16</td><td>20</td><td>17</td><td>15</td><td>183</td><td>37</td><td>92</td><td>66</td><td>43</td><td>12</td><td>60</td><td>27</td></tr><tr><td>contraceptive</td><td>(9</td><td>1425)</td><td>6</td><td>99</td><td>49</td><td>50</td><td>8</td><td>2</td><td>20</td><td>60</td><td>37</td><td>17</td><td>385</td><td>48</td><td>193</td><td>27</td><td>32</td><td>12</td><td>66</td><td>21</td></tr><tr><td>dermatology</td><td>(34</td><td>366)</td><td>6</td><td>33</td><td>90</td><td>17</td><td>23</td><td>3</td><td>16</td><td>33</td><td>21</td><td>7</td><td>17</td><td>95</td><td>9</td><td>22</td><td>0</td><td>14</td><td>20</td><td>17</td></tr><tr><td>divorce</td><td>(54</td><td>150)</td><td>5</td><td>15</td><td>90</td><td>8</td><td>50</td><td>19</td><td>20</td><td>33</td><td>24</td><td>2</td><td>5</td><td>96</td><td>3</td><td>33</td><td>16</td><td>50</td><td>50</td><td>50</td></tr><tr><td>german</td><td>(21</td><td>1000)</td><td>6</td><td>25</td><td>61</td><td>13</td><td>38</td><td>10</td><td>20</td><td>40</td><td>29</td><td>10</td><td>99</td><td>72</td><td>50</td><td>46</td><td>13</td><td>12</td><td>40</td><td>22</td></tr><tr><td>heart-c</td><td>(13</td><td>302)</td><td>6</td><td>43</td><td>65</td><td>22</td><td>36</td><td>18</td><td>20</td><td>33</td><td>22</td><td>4</td><td>15</td><td>75</td><td>8</td><td>87</td><td>81</td><td>25</td><td>50</td><td>34</td></tr><tr><td>heart-h</td><td>(13</td><td>293)</td><td>6</td><td>37</td><td>59</td><td>19</td><td>31</td><td>4</td><td>20</td><td>40</td><td>24</td><td>8</td><td>25</td><td>77</td><td>13</td><td>61</td><td>60</td><td>20</td><td>50</td><td>32</td></tr><tr><td>kr-vs-kp</td><td>(36</td><td>3196)</td><td>6</td><td>49</td><td>96</td><td>25</td><td>80</td><td>75</td><td>16</td><td>60</td><td>33</td><td>13</td><td>67</td><td>99</td><td>34</td><td>79</td><td>43</td><td>7</td><td>70</td><td>35</td></tr><tr><td>lending</td><td>(9</td><td>5082)</td><td>6</td><td>45</td><td>73</td><td>23</td><td>73</td><td>80</td><td>16</td><td>50</td><td>25</td><td>14</td><td>507</td><td>65</td><td>254</td><td>69</td><td>80</td><td>12</td><td>75</td><td>25</td></tr><tr><td>letter</td><td>(16</td><td>18668)</td><td>6</td><td>127</td><td>58</td><td>64</td><td>1</td><td>0</td><td>20</td><td>20</td><td>20</td><td>46</td><td>4857</td><td>68</td><td>2429</td><td>6</td><td>7</td><td>6</td><td>25</td><td>9</td></tr><tr><td>lymphography</td><td>(18</td><td>148)</td><td>6</td><td>61</td><td>76</td><td>31</td><td>35</td><td>25</td><td>16</td><td>33</td><td>21</td><td>6</td><td>21</td><td>86</td><td>11</td><td>9</td><td>0</td><td>16</td><td>16</td><td>16</td></tr><tr><td>mortality</td><td>(118</td><td>13442)</td><td>6</td><td>111</td><td>74</td><td>56</td><td>8</td><td>14</td><td>16</td><td>20</td><td>17</td><td>26</td><td>865</td><td>76</td><td>433</td><td>61</td><td>61</td><td>7</td><td>54</td><td>19</td></tr><tr><td>mushroom</td><td>(22</td><td>8124)</td><td>6</td><td>39</td><td>100</td><td>20</td><td>80</td><td>44</td><td>16</td><td>33</td><td>24</td><td>5</td><td>23</td><td>100</td><td>12</td><td>50</td><td>31</td><td>20</td><td>40</td><td>25</td></tr><tr><td>pendigits</td><td>(16</td><td>10992)</td><td>6</td><td>121</td><td>88</td><td>61</td><td>0</td><td>0</td><td>—</td><td>—</td><td>—</td><td>38</td><td>937</td><td>85</td><td>469</td><td>25</td><td>86</td><td>6</td><td>25</td><td>11</td></tr><tr><td>promoters</td><td>(58</td><td>106)</td><td>1</td><td>3</td><td>90</td><td>2</td><td>0</td><td>0</td><td>—</td><td>—</td><td>—</td><td>3</td><td>9</td><td>81</td><td>5</td><td>20</td><td>14</td><td>33</td><td>33</td><td>33</td></tr><tr><td>recidivism</td><td>(15</td><td>3998)</td><td>6</td><td>105</td><td>61</td><td>53</td><td>28</td><td>22</td><td>16</td><td>33</td><td>18</td><td>15</td><td>611</td><td>51</td><td>306</td><td>53</td><td>38</td><td>9</td><td>44</td><td>16</td></tr><tr><td>seismic_bumps</td><td>(18</td><td>2578)</td><td>6</td><td>37</td><td>89</td><td>19</td><td>42</td><td>19</td><td>20</td><td>33</td><td>24</td><td>8</td><td>39</td><td>93</td><td>20</td><td>60</td><td>79</td><td>20</td><td>60</td><td>42</td></tr><tr><td>shuttle</td><td>(9</td><td>58000)</td><td>6</td><td>63</td><td>99</td><td>32</td><td>28</td><td>7</td><td>20</td><td>33</td><td>23</td><td>23</td><td>159</td><td>99</td><td>80</td><td>33</td><td>9</td><td>14</td><td>50</td><td>30</td></tr><tr><td>soybean</td><td>(35</td><td>623)</td><td>6</td><td>63</td><td>88</td><td>32</td><td>9</td><td>5</td><td>25</td><td>25</td><td>25</td><td>16</td><td>71</td><td>89</td><td>36</td><td>22</td><td>1</td><td>9</td><td>12</td><td>10</td></tr><tr><td>spambase</td><td>(57</td><td>4210)</td><td>6</td><td>63</td><td>75</td><td>32</td><td>37</td><td>12</td><td>16</td><td>33</td><td>19</td><td>15</td><td>143</td><td>91</td><td>72</td><td>76</td><td>98</td><td>7</td><td>58</td><td>25</td></tr><tr><td>spect</td><td>(22</td><td>228)</td><td>6</td><td>45</td><td>82</td><td>23</td><td>60</td><td>51</td><td>20</td><td>50</td><td>35</td><td>6</td><td>15</td><td>86</td><td>8</td><td>87</td><td>98</td><td>50</td><td>83</td><td>65</td></tr><tr><td>splice</td><td>(2</td><td>3178)</td><td>3</td><td>7</td><td>50</td><td>4</td><td>0</td><td>0</td><td>—</td><td>—</td><td>—</td><td>88</td><td>177</td><td>55</td><td>89</td><td>0</td><td>0</td><td>—</td><td>—</td><td>—</td></tr></tbody></table>

The experiments are performed on a MacBook Pro with a Dual-Core Intel Core i5 2.3GHz CPU with 8GByte RAM running macOS Catalina. The polynomial-time explanation-redundancy check and a single PI-explanation extraction proposed in Section 4 are implemented in Perl. (An implementation using the Glucose SAT solver was instrumental in validating the results, but for the DTs considered, it was in general slower by at least one order of magnitude.) Performance-wise, training DTs with IAI takes from 4sec to 2310sec with the average run time per dataset being 70sec. In contrast, the time spent on eliminating explanation-redundancy is negligible, taking from 0.026sec to 0.4sec per tree, with an average time of 0.06sec. ITI runs much faster than IAI and takes from 0.1sec to 2sec with 0.1sec on average; the elimination of explanation redundancy is slightly more time consuming than for IAI, taking from 0.025sec to 5.4sec with 0.29sec on average. This slowdown results from DTs learned with ITI being deeper on average, and features being tested multiple times.

The summary of results is detailed in Table 1. For each dataset, the table reports the number of features and also instances as #F and #S, respectively. Thereafter, it shows tree statistics for IAI and ITI, namely, tree depth *D*, number of nodes *#N*, test accuracy *%A* and number of paths *#P*. The percentage of explanation-redundant paths is given as %R while the percentage of data instances (measured for the entire feature space) covered by redundant paths is %C. Focusing solely on the explanation-redundant paths, a single PI-explanation is extracted and the average (min. or max., resp.) percentage of redundant literals per path is denoted by %avg (%m and %M, resp.). Observe that despite the shallowness of the trees produced by IAI and ITI, for the majority of datasets and with a few exceptions, the paths in trees trained by both tools exhibit significant
explanation-redundancy. In particular, on average, 32.1% (46.9%, resp.) of paths are
explanation-redundant for the trees obtained by IAI (ITI, resp.). For some DTs, obtained
with either IAI and ITI, more than 85% of tree paths are redundant. Also, redundant
paths of the trees of IAI (ITI, resp.) cover on average 20.1% (37.7%, resp.) of feature
space. Moreover, in some cases, up to 89% and 98% of the entire feature space is
covered by the redundant paths for IAI and ITI, respectively. This means that DTs
produced by IAI and ITI are unable to provide a user with a succinct explanation for
the *vast majority* of data instances. In addition, the average number of redundant literals
in redundant paths for both IAI and ITI varies from 16% to 65%, but for some DTs it
exceeds 80%.

To summarize, the numbers shown for the selected datasets and for the state-of-
the-art DT training tools contrast the common belief in the inherent interpretability of
decision tree classifiers. Perhaps as importantly, the performance figures confirm that
the elimination of explanation-redundancy in the DTs produced with available tools has
negligible computational cost.

7 Conclusions

Decision trees are most often associated with interpretability. This paper shows that in some situations, paths in a decision tree may include many literals that are irrelevant for an explanation, and that this holds true even for irreducible decision trees. Moreover, the paper proposes a linear time test to decide whether a decision tree path contains irrelevant literals, and uses such test to devise a polynomial time algorithm for computing one PI-explanation of a decision tree. Furthermore, the paper shows the connection between enumerating the PI-explanations of DTs and the enumeration of minimal hitting sets. Experimental results obtained on publicly available datasets, using state-of-the-art decision tree learners, show that in practice induced paths in decision trees may contain irrelevant literals, even when the decision tree is irreducible. For the decision trees considered in the experiments, the run times of the proposed algorithms are either negligible or comparable to tree learning times.

References

1. G. Aglin, S. Nijssen, and P. Schaus. Learning optimal decision trees using caching branch-and-bound search. In AAAI, pages 3146–3153, 2020.

2. G. Aglin, S. Nijssen, and P. Schaus. PyDL8.5: a library for learning optimal decision trees. In *IJCAI*, pages 5222–5224, 2020.

3. E. Alpaydin. *Machine Learning: The New AI*. MIT Press, 2016.

4. E. Angelino, N. Larus-Stone, D. Alabi, M. Seltzer, and C. Rudin. Learning certifiably optimal rule lists. In *KDD*, pages 35–44, 2017.

5. E. Angelino, N. Larus-Stone, D. Alabi, M. Seltzer, and C. Rudin. Learning certifiably optimal rule lists for categorical data. *J. Mach. Learn. Res.*, 18:234:1–234:78, 2017.

6. R. Appuswamy, M. Franceschetti, N. Karamchandani, and K. Zeger. Network coding for computing: Cut-set bounds. *IEEE Trans. Inf. Theory*, 57(2):1015–1030, 2011.

7. F. Avellaneda. Efficient inference of optimal decision trees. In AAAI, pages 3195–3202, 2020.
8. O. Bastani, C. Kim, and H. Bastani. Interpretability via model extraction. CoRR, abs/1706.09773, 2017.

9. O. Bastani, C. Kim, and H. Bastani. Interpreting blackbox models via model extraction. CoRR, abs/1705.08504, 2017.

10. D. Bertsimas and J. Dunn. Optimal classification trees. Mach. Learn., 106(7):1039-1082, 2017.

11. C. Bessiere, E. Hebrard, and B. O'Sullivan. Minimising decision tree size as combinatorial optimisation. In CP, pages 173-187, 2009.

12. M. Bramer. *Principles of Data Mining, Third Edition*. Springer, 2016.

13. L. Breiman. Statistical modeling: The two cultures. *Statistical science*, 16(3):199-231, 2001.

14. L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. *Classification and Regression Trees*. Wadsworth, 1984.

15. L. A. Breslow and D. W. Aha. Simplifying decision trees: A survey. *Knowledge Eng. Review*, 12(1):1-40, 1997.

16. C. E. Brodley and P. E. Utgoff. Multivariate decision trees. *Mach. Learn.*, 19(1):45-77, 1995.

17. C. Chen and C. Rudin. An optimization approach to learning falling rule lists. In *AISTATS*, pages 604-612, 2018.

18. A. Choi, A. Shih, A. Goyanka, and A. Darwiche. On symbolically encoding the behavior of random forests. CoRR, abs/2007.01493, 2020.

19. P. A. Flach. *Machine Learning - The Art and Science of Algorithms that Make Sense of Data*. CUP, 2012.

20. A. A. Freitas. Comprehensible classification models: a position paper. *SIGKDD Explorations*, 15(1):1-10, 2013.

21. N. Frosst and G. E. Hinton. Distilling a neural network into a soft decision tree. In *CEXAI*, 2017.

22. M. R. Garey. Optimal binary identification procedures. *SIAM Journal on Applied Mathematics*, 23(2):173-186, 1972.

23. R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi. A survey of methods for explaining black box models. *ACM Comput. Surv.*, 51(5):93:1-93:42, 2019.

24. A. Holzinger, G. Langs, H. Denk, K. Zatloukal, and H. Müller. Causability and explainability of artificial intelligence in medicine. *WIRE Data Min. Knowl. Discov.*, 9(4), 2019.

25. H. Hu, M. Siala, E. Hebrard, and M. Huguet. Learning optimal decision trees with MaxSAT and its integration in adaboost. In *IJCAI*, pages 1170-1176, 2020.

26. X. Hu, C. Rudin, and M. Seltzer. Optimal sparse decision trees. In *NeurIPS*, pages 7265-7273, 2019.

27. L. Hyafil and R. L. Rivest. Constructing optimal binary decision trees is np-complete. *Inf. Process. Lett.*, 5(1):15-17, 1976.

28. IAI. Interpretable AI. https://www.interpretable.ai/, 2020.

29. A. Ignatiev, N. Narodytska, and J. Marques-Silva. Abduction-based explanations for machine learning models. In AAAI, pages 1511-1519, 2019.

30. Incremental Decision Tree Induction. https://www-lrn.cs.umass.edu/iti/, 2020.

31. M. Janota and A. Morgado. SAT-based encodings for optimal decision trees with explicit paths. In SAT, pages 501-518, 2020.

32. S. B. Kotsiantis. Decision trees: a recent overview. *Artif. Intell. Rev.*, 39(4):261-283, 2013.

33. H. Lakkaraju, S. H. Bach, and J. Leskovec. Interpretable decision sets: A joint framework for description and prediction. In *KDD*, pages 1675-1684, 2016.

34. H. Lakkaraju, E. Kamar, R. Caruana, and J. Leskovec. Interpretable & explorable approximations of black box models. CoRR, abs/1707.01154, 2017.

35. B. Letham, C. Rudin, T. H. McCormick, and D. Madigan. An interpretable stroke prediction model using rules and bayesian analysis. In AAAI, 2013.
36. Z. C. Lipton. The mythos of model interpretability. *Commun. ACM*, 61(10):36–43, 2018.

37. S. M. Lundberg, G. Erion, H. Chen, A. DeGrave, J. M. Prutkin, B. Nair, R. Katz, J. Himmelfarb, N. Bansal, and S.-I. Lee. From local explanations to global understanding with explainable AI for trees. *Nature machine intelligence*, 2(1):2522–5839, 2020.

38. T. Miller. Explanation in artificial intelligence: Insights from the social sciences. *Artif. Intell.*, 267:1–38, 2019.

39. T. M. Mitchell. *Machine learning*. McGraw-Hill, 1997.

40. C. Molnar. *Interpretable Machine Learning*. 2019. https://christophm.github.io/interpretable-ml-book/.

41. G. Montavon, W. Samek, and K. Müller. Methods for interpreting and understanding deep neural networks. *Digit. Signal Process.*, 73:1–15, 2018.

42. B. M. E. Moret. Decision trees and diagrams. *ACM Comput. Surv.*, 14(4):593–623, 1982.

43. N. Narodytska, A. Ignatiev, F. Pereira, and J. Marques-Silva. Learning optimal decision trees with SAT. In *IJCAI*, pages 1362–1368, 2018.

44. S. Nijssen and É. Fromont. Mining optimal decision trees from itemset lattices. In *KDD*, pages 530–539, 2007.

45. S. Nijssen and É. Fromont. Optimal constraint-based decision tree induction from itemset lattices. *Data Min. Knowl. Discov.*, 21(1):9–51, 2010.

46. OpenML: Machine learning, better, together. https://www.openml.org/, 2020.

47. F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. VanderPlas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in python. *J. Mach. Learn. Res.*, 12:2825–2830, 2011.

48. Penn Machine Learning Benchmarks. https://github.com/EpistasisLab/penn-ml-benchmarks, 2020.

49. D. Poole and A. K. Mackworth. *Artificial Intelligence - Foundations of Computational Agents*. CUP, 2017.

50. J. R. Quinlan. Induction of decision trees. *Mach. Learn.*, 1(1):81–106, 1986.

51. M. T. Ribeiro, S. Singh, and C. Guestrin. Model-agnostic interpretability of machine learning. *CoRR*, abs/1606.05386, 2016.

52. R. L. Rivest. Learning decision lists. *Mach. Learn.*, 2(3):229–246, 1987.

53. L. Rokach and O. Maimon. Top-down induction of decision trees classifiers - a survey. *IEEE Trans. Syst. Man Cybern. Part C*, 35(4):476–487, 2005.

54. L. Rokach and O. Maimon. *Data Mining with Decision Trees - Theory and Applications*. WorldScientific, 2007.

55. A. M. Roth, N. Topin, P. Jamshidi, and M. Veloso. Conservative Q-improvement: Reinforcement learning for an interpretable decision-tree policy. *CoRR*, abs/1907.01180, 2019.

56. C. Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. *Nature Machine Intelligence*, 1(5):206–215, 2019.

57. C. Rudin and S. Ertekin. Learning customized and optimized lists of rules with mathematical programming. *Math. Program. Comput.*, 10(4):659–702, 2018.

58. S. J. Russell and P. Norvig. *Artificial Intelligence - A Modern Approach*. Pearson Education, 2010.

59. W. Samek, G. Montavon, A. Vedaldi, L. K. Hansen, and K. Müller, editors. *Explainable AI: Interpreting, Explaining and Visualizing Deep Learning*. Springer, 2019.

60. A. Shih, A. Choi, and A. Darwiche. A symbolic approach to explaining bayesian network classifiers. In *IJCAI*, pages 5103–5111, 2018.

61. A. Silva, M. C. Gombolay, T. W. Killian, I. D. J. Jimenez, and S. Son. Optimization methods for interpretable differentiable decision trees applied to reinforcement learning. In *AISTATS*, pages 1855–1865, 2020.
62. K. Sokol and P. A. Flach. Desiderata for interpretability: Explaining decision tree predictions with counterfactuals. In AAAI, pages 10035–10036, 2019.

63. UCI Machine Learning Repository. https://archive.ics.uci.edu/ml, 2020.

64. P. E. Utgoff, N. C. Berkman, and J. A. Clouse. Decision tree induction based on efficient tree restructuring. Mach. Learn., 29(1):5–44, 1997.

65. G. Valdes, J. M. Luna, E. Eaton, C. B. Simone II, L. H. Ungar, and T. D. Solberg. Mediboost: a patient stratification tool for interpretable decision making in the era of precision medicine. Nature Scientific reports, 6:37854, 2016.

66. H. Verhaeghe, S. Nijssen, G. Pesant, C. Quimper, and P. Schaus. Learning optimal decision trees using constraint programming. In BNAIC, 2019.

67. H. Verhaeghe, S. Nijssen, G. Pesant, C. Quimper, and P. Schaus. Learning optimal decision trees using constraint programming. In IJCAI, pages 4765–4769, 2020.

68. S. Verwer and Y. Zhang. Learning decision trees with flexible constraints and objectives using integer optimization. In CPAIOR, volume 10335, pages 94–103, 2017.

69. S. Verwer and Y. Zhang. Learning optimal classification trees using a binary linear program formulation. In AAAI, pages 1625–1632, 2019.

70. F. Wang and C. Rudin. Falling rule lists. In AISTATS, 2015.

71. T. Wang, C. Rudin, F. Doshi-Velez, Y. Liu, E. Klampfl, and P. MacNeille. Bayesian rule sets for interpretable classification. In ICDM, pages 1269–1274, 2016.

72. T. Wang, C. Rudin, F. Doshi-Velez, Y. Liu, E. Klampfl, and P. MacNeille. A bayesian framework for learning rule sets for interpretable classification. J. Mach. Learn. Res., 18:70:1–70:37, 2017.

73. M. Wu, M. C. Hughes, S. Parbhoo, M. Zazzi, V. Roth, and F. Doshi-Velez. Beyond sparsity: Tree regularization of deep models for interpretability. In AAAI, pages 1670–1678, 2018.

74. M. Wu, S. Parbhoo, M. C. Hughes, R. Kindle, L. A. Celi, M. Zazzi, V. Roth, and F. Doshi-Velez. Regional tree regularization for interpretability in deep neural networks. In AAAI, pages 6413–6421, 2020.

75. M. Wu, S. Parbhoo, M. C. Hughes, V. Roth, and F. Doshi-Velez. Optimizing for interpretability in deep neural networks with tree regularization. CoRR, abs/1908.05254, 2019.

76. F. Xu, H. Uszkoreit, Y. Du, W. Fan, D. Zhao, and J. Zhu. Explainable AI: A brief survey on history, research areas, approaches and challenges. In NLPCC, pages 563–574, 2019.

77. H. Yang, C. Rudin, and M. Seltzer. Scalable bayesian rule lists. In ICML, volume 70, pages 3921–3930, 2017.

78. Z.-H. Zhou. Ensemble methods: foundations and algorithms. CRC press, 2012.

# A Case Studies

## A.1 Analysis of DT from Russel&Norvig's Book

**Decision Tree** This case study considers the decision tree (DT) shown in Figure 4, taken from [58, Ch. 18, page 702]. The example consists in deciding whether to wait for a table at a restaurant. Six features are used in the DT, namely:

- Alternate: whether there is a suitable alternative restaurant nearby.

- Bar: whether the restaurant has a comfortable bar area to wait in.

- Fri/Sat: true on Fridays and Saturdays.

- Hungry: whether the people are hungry.

- Patrons: how many people are in the restaurant (values are None, Some, and Full).

- Type: the kind of restaurant (French, Italian, Thai, or burger).
<figure><img src="image_6.png" /><figcaption>Fig. 4: Example of decision tree from Russel&Norvig's Book.</figcaption></figure>

**Redundancy Analysis Results** Analysis of the paths in the DT shown in Figure 4 yields the following results.

- path (*Patrons=None*) is explanation-irredundant.

- path (*Patrons=Ful* and *Hungry=None*) is explanation-irredundant.

- path (*Patrons=Ful* and *Hungry=Yes* and *Type=Italian*) is explanation-redundant. If the values of *Patrons* and *Type* are fixed, then the value of *Hungry* is irrelevant for the prediction.

- path (*Patrons=Ful* and *Hungry=Yes* and *Type=Thai* and *Fri/Sat=None*) is explanation-redundant. If the values of *Patrons*, *Type* and *Fri/Sat* are fixed, then the value of *Hungry* is irrelevant for the prediction.

- path (*Patrons=Some*) is explanation-irredundant.

- path (*Patrons=Ful* and *Hungry=Yes* and *Type=Frencg*) is explanation-irredundant.

- path (*Patrons=Ful* and *Hungry=Yes* and *Type=Thai* and *Fri/Sat=Yes*) is explanation-irredundant.

- path (*Patrons=Ful* and *Hungry=Yes* and *Type=Burger*) is explanation-irredundant.

As result, 2 out of 8 paths exhibit explanation-redundancy. Thus, we conclude that the DT exhibits 25% of explanation-redundancy.

## A.2 Analysis of DT from Poole&Mackworth's Book

**Decision Tree** This case study considers the decision tree shown in Figure 5, taken from [49, Ch. 07, page 298]. The example consists in predicting whether a person reads an article posted to a bulletin board given properties of the article. There are three features in the decision tree:

- Author: whether the author is known or not.

- Thread: whether the article started a new thread or was a follow-up.

- Length: the length of the article (short or long).
<figure><img src="image_7.png" /><figcaption>Fig. 5: Example of decision tree from Poole&Mackworth's Book.</figcaption></figure>

**Redundancy Analysis Results** Analysis of the paths in the DT shown in Figure 5 yields the following results.

- path (*Length*=long) is explanation-irredundant.

- path (*Length*=short and *Thread*=follow-up and *Author*=unknown) is explanation-redundant. If values of *Thread* and *Author* are fixed, then the value of *Length* is irrelevant for the prediction.

- path (*Length*=short and *Thread*=new) is explanation-irredundant.

- path (*Length*=short and *Thread*=follow-up and *Author*=known) is explanation-redundant. If the values of *Length* and *Author* are fixed, then the value of *Thread* is irrelevant for the prediction.

Accordingly, 2 out of 4 paths exhibit explanation-redundancy. Therefore, we say that the DT exhibits 50% of explanation-redundancy.

## A.3 Analysis of DT from Z.-H. Zhou's book

**Decision Tree** This case study considers the decision tree shown in Figure 6, taken from [78, Ch. 01, page 5]. The example consists in predicting the type of a drawing, to be chosen among the classes *cross* and *circle*. Two features are used, namely:

- $x > 0.64 \in \{\text{Y}, \text{N}\}$.

- $y > 0.73 \in \{\text{Y}, \text{N}\}$.

**Redundancy Analysis Results** Analysis of the paths in the DT shown in Figure 6 yields the following results.

- path ($y > 0.73$) is explanation-irredundant.

- path ($y \le 0.73$ and $x > 0.64$) is explanation-redundant. If the value of $y$ is fixed, then the value of $x$ is irrelevant for the prediction.

- path ($y \le 0.73$ and $x \le 0.64$) is explanation-irredundant.

As a result, 1 out of 3 paths exhibit explanation-redundancy. Thus, we say that the DT exhibits 33.33% of explanation-redundancy.
<figure><img src="image_8.png" /><figcaption>Fig. 6: Example of decision tree from Zhou's book [78].</figcaption></figure>

## A.4 Additional Examples

It is interesting to note that the DTs used in a number of books and surveys exhibit explanation-redundancy. A non-exhaustive list of references includes [42,15,53,54,58,19,32,3,12,65,49].

## B Full Table of Results

Table 2 presents the experimental results obtained on an extended set of datasets.

<table><thead><tr><th rowspan="2">Dataset</th><th rowspan="2">(#F)</th><th rowspan="2">#S)</th><th colspan="10">IAI</th><th rowspan="2">D</th><th rowspan="2">#N</th></tr><tr><th>D</th><th>#N</th><th>%A</th><th>#P</th><th>%R</th><th>%C</th><th>%m</th><th>%M</th><th>%avg</th></tr></thead><tbody><tr><td>IndiansDiabetes</td><td>8</td><td>768</td><td>6</td><td>33</td><td>67</td><td>17</td><td>35</td><td>2</td><td>20</td><td>25</td><td>21</td><td>21</td><td>67</td></tr><tr><td>adult_data</td><td>12</td><td>6061</td><td>6</td><td>83</td><td>78</td><td>42</td><td>33</td><td>25</td><td>20</td><td>40</td><td>25</td><td>17</td><td>509</td></tr><tr><td>anneal</td><td>38</td><td>886</td><td>6</td><td>29</td><td>99</td><td>15</td><td>26</td><td>16</td><td>16</td><td>33</td><td>21</td><td>9</td><td>31</td></tr><tr><td>appendicitis</td><td>7</td><td>106</td><td>2</td><td>7</td><td>68</td><td>4</td><td>0</td><td>0</td><td>—</td><td>—</td><td>—</td><td>3</td><td>7</td></tr><tr><td>australian</td><td>14</td><td>690</td><td>6</td><td>45</td><td>61</td><td>23</td><td>17</td><td>8</td><td>20</td><td>33</td><td>23</td><td>7</td><td>33</td></tr><tr><td>auto</td><td>25</td><td>202</td><td>6</td><td>33</td><td>53</td><td>17</td><td>23</td><td>1</td><td>16</td><td>33</td><td>23</td><td>10</td><td>47</td></tr><tr><td>backache</td><td>32</td><td>180</td><td>4</td><td>17</td><td>72</td><td>9</td><td>33</td><td>39</td><td>25</td><td>33</td><td>30</td><td>3</td><td>9</td></tr><tr><td>balance</td><td>4</td><td>625</td><td>6</td><td>93</td><td>81</td><td>47</td><td>61</td><td>41</td><td>25</td><td>50</td><td>27</td><td>12</td><td>105</td></tr><tr><td>bank</td><td>19</td><td>36293</td><td>6</td><td>113</td><td>88</td><td>57</td><td>5</td><td>12</td><td>16</td><td>20</td><td>18</td><td>19</td><td>1467</td></tr><tr><td>banknote</td><td>4</td><td>1348</td><td>3</td><td>9</td><td>67</td><td>5</td><td>20</td><td>0</td><td>66</td><td>66</td><td>66</td><td>35</td><td>71</td></tr><tr><td>biodegradation</td><td>41</td><td>1052</td><td>5</td><td>19</td><td>65</td><td>10</td><td>30</td><td>1</td><td>25</td><td>50</td><td>33</td><td>8</td><td>71</td></tr><tr><td>biomed</td><td>8</td><td>209</td><td>3</td><td>9</td><td>66</td><td>5</td><td>20</td><td>1</td><td>50</td><td>50</td><td>50</td><td>8</td><td>33</td></tr><tr><td>breast-cancer</td><td>9</td><td>272</td><td>6</td><td>61</td><td>74</td><td>31</td><td>41</td><td>13</td><td>16</td><td>33</td><td>20</td><td>7</td><td>25</td></tr><tr><td>bupa</td><td>6</td><td>341</td><td>6</td><td>47</td><td>62</td><td>24</td><td>29</td><td>5</td><td>20</td><td>33</td><td>25</td><td>24</td><td>49</td></tr><tr><td>cancer</td><td>9</td><td>449</td><td>6</td><td>37</td><td>87</td><td>19</td><td>36</td><td>9</td><td>20</td><td>25</td><td>21</td><td>5</td><td>21</td></tr><tr><td>car</td><td>6</td><td>1728</td><td>6</td><td>43</td><td>96</td><td>22</td><td>86</td><td>89</td><td>20</td><td>80</td><td>45</td><td>11</td><td>57</td></tr><tr><td>cars</td><td>8</td><td>392</td><td>2</td><td>5</td><td>100</td><td>3</td><td>0</td><td>0</td><td>—</td><td>—</td><td>—</td><td>14</td><td>45</td></tr><tr><td>cleveland-nominal</td><td>7</td><td>187</td><td>6</td><td>81</td><td>31</td><td>41</td><td>24</td><td>15</td><td>16</td><td>33</td><td>20</td><td>7</td><td>65</td></tr><tr><td>cloud</td><td>7</td><td>108</td><td>3</td><td>9</td><td>31</td><td>5</td><td>0</td><td>0</td><td>—</td><td>—</td><td>—</td><td>10</td><td>21</td></tr><tr><td>colic</td><td>22</td><td>357</td><td>6</td><td>55</td><td>81</td><td>28</td><td>46</td><td>6</td><td>16</td><td>33</td><td>20</td><td>4</td><td>17</td></tr><tr><td>compas</td><td>11</td><td>1155</td><td>6</td><td>77</td><td>34</td><td>39</td><td>17</td><td>8</td><td>16</td><td>20</td><td>17</td><td>15</td><td>183</td></tr></tbody></table>
<table>
  <tr>
    <td>contraceptive</td>
    <td>9</td>
    <td>1425</td>
    <td>6</td>
    <td>99</td>
    <td>49</td>
    <td>50</td>
    <td>8</td>
    <td>2</td>
    <td>20</td>
    <td>60</td>
    <td>37</td>
    <td>17</td>
    <td>385</td>
  </tr>
  <tr>
    <td>corral</td>
    <td>6</td>
    <td>64</td>
    <td>6</td>
    <td>19</td>
    <td>92</td>
    <td>10</td>
    <td>80</td>
    <td>50</td>
    <td>20</td>
    <td>66</td>
    <td>42</td>
    <td>4</td>
    <td>13</td>
  </tr>
  <tr>
    <td>dermatology</td>
    <td>34</td>
    <td>366</td>
    <td>6</td>
    <td>33</td>
    <td>90</td>
    <td>17</td>
    <td>23</td>
    <td>3</td>
    <td>16</td>
    <td>33</td>
    <td>21</td>
    <td>7</td>
    <td>17</td>
  </tr>
  <tr>
    <td>divorce</td>
    <td>54</td>
    <td>150</td>
    <td>5</td>
    <td>15</td>
    <td>90</td>
    <td>8</td>
    <td>50</td>
    <td>19</td>
    <td>20</td>
    <td>33</td>
    <td>24</td>
    <td>2</td>
    <td>5</td>
  </tr>
  <tr>
    <td>ecoli</td>
    <td>7</td>
    <td>327</td>
    <td>6</td>
    <td>45</td>
    <td>75</td>
    <td>23</td>
    <td>4</td>
    <td>5</td>
    <td>20</td>
    <td>20</td>
    <td>20</td>
    <td>53</td>
    <td>109</td>
  </tr>
  <tr>
    <td>german_data</td>
    <td>21</td>
    <td>1000</td>
    <td>6</td>
    <td>25</td>
    <td>61</td>
    <td>13</td>
    <td>38</td>
    <td>10</td>
    <td>20</td>
    <td>40</td>
    <td>29</td>
    <td>10</td>
    <td>99</td>
  </tr>
  <tr>
    <td>glass</td>
    <td>9</td>
    <td>204</td>
    <td>6</td>
    <td>35</td>
    <td>53</td>
    <td>18</td>
    <td>0</td>
    <td>0</td>
    <td>—</td>
    <td>—</td>
    <td>—</td>
    <td>27</td>
    <td>65</td>
  </tr>
  <tr>
    <td>glass2</td>
    <td>9</td>
    <td>162</td>
    <td>3</td>
    <td>11</td>
    <td>66</td>
    <td>6</td>
    <td>0</td>
    <td>0</td>
    <td>—</td>
    <td>—</td>
    <td>—</td>
    <td>7</td>
    <td>15</td>
  </tr>
  <tr>
    <td>haberman</td>
    <td>3</td>
    <td>289</td>
    <td>6</td>
    <td>55</td>
    <td>58</td>
    <td>28</td>
    <td>14</td>
    <td>4</td>
    <td>33</td>
    <td>33</td>
    <td>33</td>
    <td>12</td>
    <td>35</td>
  </tr>
  <tr>
    <td>hayes-roth</td>
    <td>4</td>
    <td>93</td>
    <td>6</td>
    <td>23</td>
    <td>78</td>
    <td>12</td>
    <td>25</td>
    <td>32</td>
    <td>50</td>
    <td>66</td>
    <td>61</td>
    <td>6</td>
    <td>17</td>
  </tr>
  <tr>
    <td>heart-c</td>
    <td>13</td>
    <td>302</td>
    <td>6</td>
    <td>43</td>
    <td>65</td>
    <td>22</td>
    <td>36</td>
    <td>18</td>
    <td>20</td>
    <td>33</td>
    <td>22</td>
    <td>4</td>
    <td>15</td>
  </tr>
  <tr>
    <td>heart-h</td>
    <td>13</td>
    <td>293</td>
    <td>6</td>
    <td>37</td>
    <td>59</td>
    <td>19</td>
    <td>31</td>
    <td>4</td>
    <td>20</td>
    <td>40</td>
    <td>24</td>
    <td>8</td>
    <td>25</td>
  </tr>
  <tr>
    <td>heart-statlog</td>
    <td>13</td>
    <td>270</td>
    <td>6</td>
    <td>33</td>
    <td>55</td>
    <td>17</td>
    <td>29</td>
    <td>5</td>
    <td>20</td>
    <td>33</td>
    <td>30</td>
    <td>4</td>
    <td>13</td>
  </tr>
  <tr>
    <td>hepatitis</td>
    <td>19</td>
    <td>155</td>
    <td>5</td>
    <td>17</td>
    <td>77</td>
    <td>9</td>
    <td>33</td>
    <td>6</td>
    <td>20</td>
    <td>33</td>
    <td>24</td>
    <td>3</td>
    <td>11</td>
  </tr>
  <tr>
    <td>house-votes-84</td>
    <td>16</td>
    <td>298</td>
    <td>6</td>
    <td>49</td>
    <td>91</td>
    <td>25</td>
    <td>68</td>
    <td>67</td>
    <td>16</td>
    <td>50</td>
    <td>27</td>
    <td>3</td>
    <td>9</td>
  </tr>
  <tr>
    <td>hungarian</td>
    <td>13</td>
    <td>293</td>
    <td>6</td>
    <td>33</td>
    <td>69</td>
    <td>17</td>
    <td>29</td>
    <td>2</td>
    <td>25</td>
    <td>40</td>
    <td>31</td>
    <td>4</td>
    <td>19</td>
  </tr>
  <tr>
    <td>ionosphere</td>
    <td>34</td>
    <td>350</td>
    <td>4</td>
    <td>9</td>
    <td>70</td>
    <td>5</td>
    <td>60</td>
    <td>3</td>
    <td>33</td>
    <td>50</td>
    <td>38</td>
    <td>5</td>
    <td>17</td>
  </tr>
  <tr>
    <td>iris</td>
    <td>4</td>
    <td>149</td>
    <td>5</td>
    <td>23</td>
    <td>90</td>
    <td>12</td>
    <td>41</td>
    <td>25</td>
    <td>25</td>
    <td>33</td>
    <td>30</td>
    <td>10</td>
    <td>21</td>
  </tr>
  <tr>
    <td>irish</td>
    <td>5</td>
    <td>470</td>
    <td>4</td>
    <td>13</td>
    <td>97</td>
    <td>7</td>
    <td>71</td>
    <td>54</td>
    <td>33</td>
    <td>50</td>
    <td>36</td>
    <td>3</td>
    <td>7</td>
  </tr>
  <tr>
    <td>kr-vs-kp</td>
    <td>36</td>
    <td>3196</td>
    <td>6</td>
    <td>49</td>
    <td>96</td>
    <td>25</td>
    <td>80</td>
    <td>75</td>
    <td>16</td>
    <td>60</td>
    <td>33</td>
    <td>13</td>
    <td>67</td>
  </tr>
  <tr>
    <td>lending_data</td>
    <td>9</td>
    <td>5082</td>
    <td>6</td>
    <td>45</td>
    <td>73</td>
    <td>23</td>
    <td>73</td>
    <td>80</td>
    <td>16</td>
    <td>50</td>
    <td>25</td>
    <td>14</td>
    <td>507</td>
  </tr>
  <tr>
    <td>letter</td>
    <td>16</td>
    <td>18668</td>
    <td>6</td>
    <td>127</td>
    <td>58</td>
    <td>64</td>
    <td>1</td>
    <td>0</td>
    <td>20</td>
    <td>20</td>
    <td>20</td>
    <td>46</td>
    <td>4857</td>
  </tr>
  <tr>
    <td>lupus</td>
    <td>3</td>
    <td>87</td>
    <td>2</td>
    <td>7</td>
    <td>44</td>
    <td>4</td>
    <td>0</td>
    <td>0</td>
    <td>—</td>
    <td>—</td>
    <td>—</td>
    <td>1</td>
    <td>3</td>
  </tr>
  <tr>
    <td>lymphography</td>
    <td>18</td>
    <td>148</td>
    <td>6</td>
    <td>61</td>
    <td>76</td>
    <td>31</td>
    <td>35</td>
    <td>25</td>
    <td>16</td>
    <td>33</td>
    <td>21</td>
    <td>6</td>
    <td>21</td>
  </tr>
  <tr>
    <td>messidor</td>
    <td>19</td>
    <td>1146</td>
    <td>3</td>
    <td>7</td>
    <td>50</td>
    <td>4</td>
    <td>50</td>
    <td>1</td>
    <td>50</td>
    <td>66</td>
    <td>58</td>
    <td>22</td>
    <td>107</td>
  </tr>
  <tr>
    <td>meteo</td>
    <td>4</td>
    <td>14</td>
    <td>5</td>
    <td>13</td>
    <td>33</td>
    <td>7</td>
    <td>42</td>
    <td>33</td>
    <td>33</td>
    <td>50</td>
    <td>38</td>
    <td>1</td>
    <td>3</td>
  </tr>
  <tr>
    <td>molecular-biology_promoters</td>
    <td>58</td>
    <td>106</td>
    <td>6</td>
    <td>17</td>
    <td>86</td>
    <td>9</td>
    <td>33</td>
    <td>19</td>
    <td>16</td>
    <td>33</td>
    <td>23</td>
    <td>3</td>
    <td>9</td>
  </tr>
  <tr>
    <td>monk1</td>
    <td>6</td>
    <td>124</td>
    <td>4</td>
    <td>17</td>
    <td>100</td>
    <td>9</td>
    <td>66</td>
    <td>41</td>
    <td>25</td>
    <td>50</td>
    <td>36</td>
    <td>5</td>
    <td>13</td>
  </tr>
  <tr>
    <td>monk2</td>
    <td>6</td>
    <td>169</td>
    <td>6</td>
    <td>67</td>
    <td>82</td>
    <td>34</td>
    <td>64</td>
    <td>49</td>
    <td>16</td>
    <td>66</td>
    <td>32</td>
    <td>5</td>
    <td>25</td>
  </tr>
  <tr>
    <td>monk3</td>
    <td>6</td>
    <td>122</td>
    <td>6</td>
    <td>35</td>
    <td>80</td>
    <td>18</td>
    <td>61</td>
    <td>36</td>
    <td>20</td>
    <td>60</td>
    <td>37</td>
    <td>2</td>
    <td>5</td>
  </tr>
  <tr>
    <td>mortality</td>
    <td>118</td>
    <td>13442</td>
    <td>6</td>
    <td>111</td>
    <td>74</td>
    <td>56</td>
    <td>8</td>
    <td>14</td>
    <td>16</td>
    <td>20</td>
    <td>17</td>
    <td>26</td>
    <td>865</td>
  </tr>
  <tr>
    <td>mouse</td>
    <td>5</td>
    <td>57</td>
    <td>3</td>
    <td>9</td>
    <td>83</td>
    <td>5</td>
    <td>20</td>
    <td>0</td>
    <td>33</td>
    <td>33</td>
    <td>33</td>
    <td>2</td>
    <td>5</td>
  </tr>
  <tr>
    <td>mushroom</td>
    <td>22</td>
    <td>8124</td>
    <td>6</td>
    <td>39</td>
    <td>100</td>
    <td>20</td>
    <td>80</td>
    <td>44</td>
    <td>16</td>
    <td>33</td>
    <td>24</td>
    <td>5</td>
    <td>23</td>
  </tr>
  <tr>
    <td>mux6</td>
    <td>6</td>
    <td>64</td>
    <td>6</td>
    <td>55</td>
    <td>61</td>
    <td>28</td>
    <td>85</td>
    <td>78</td>
    <td>20</td>
    <td>50</td>
    <td>37</td>
    <td>4</td>
    <td>15</td>
  </tr>
  <tr>
    <td>new-thyroid</td>
    <td>5</td>
    <td>215</td>
    <td>3</td>
    <td>11</td>
    <td>95</td>
    <td>6</td>
    <td>33</td>
    <td>4</td>
    <td>33</td>
    <td>33</td>
    <td>33</td>
    <td>14</td>
    <td>29</td>
  </tr>
  <tr>
    <td>pendigits</td>
    <td>16</td>
    <td>10992</td>
    <td>6</td>
    <td>121</td>
    <td>88</td>
    <td>61</td>
    <td>0</td>
    <td>0</td>
    <td>—</td>
    <td>—</td>
    <td>—</td>
    <td>38</td>
    <td>937</td>
  </tr>
  <tr>
    <td>postoperative-patient-data</td>
    <td>8</td>
    <td>78</td>
    <td>6</td>
    <td>43</td>
    <td>50</td>
    <td>22</td>
    <td>59</td>
    <td>44</td>
    <td>16</td>
    <td>50</td>
    <td>25</td>
    <td>6</td>
    <td>15</td>
  </tr>
  <tr>
    <td>primary-tumor</td>
    <td>15</td>
    <td>228</td>
    <td>6</td>
    <td>55</td>
    <td>71</td>
    <td>28</td>
    <td>35</td>
    <td>21</td>
    <td>16</td>
    <td>33</td>
    <td>21</td>
    <td>6</td>
    <td>21</td>
  </tr>
  <tr>
    <td>promoters</td>
    <td>58</td>
    <td>106</td>
    <td>1</td>
    <td>3</td>
    <td>90</td>
    <td>2</td>
    <td>0</td>
    <td>0</td>
    <td>—</td>
    <td>—</td>
    <td>—</td>
    <td>3</td>
    <td>9</td>
  </tr>
  <tr>
    <td>recidivism_data</td>
    <td>15</td>
    <td>3998</td>
    <td>6</td>
    <td>105</td>
    <td>61</td>
    <td>53</td>
    <td>28</td>
    <td>22</td>
    <td>16</td>
    <td>33</td>
    <td>18</td>
    <td>15</td>
    <td>611</td>
  </tr>
  <tr>
    <td>schizo</td>
    <td>14</td>
    <td>340</td>
    <td>6</td>
    <td>17</td>
    <td>55</td>
    <td>9</td>
    <td>55</td>
    <td>5</td>
    <td>50</td>
    <td>66</td>
    <td>58</td>
    <td>13</td>
    <td>51</td>
  </tr>
  <tr>
    <td>segmentation</td>
    <td>19</td>
    <td>210</td>
    <td>4</td>
    <td>15</td>
    <td>38</td>
    <td>8</td>
    <td>0</td>
    <td>0</td>
    <td>—</td>
    <td>—</td>
    <td>—</td>
    <td>27</td>
    <td>57</td>
  </tr>
  <tr>
    <td>seismic_bumps</td>
    <td>18</td>
    <td>2578</td>
    <td>6</td>
    <td>37</td>
    <td>89</td>
    <td>19</td>
    <td>42</td>
    <td>19</td>
    <td>20</td>
    <td>33</td>
    <td>24</td>
    <td>8</td>
    <td>39</td>
  </tr>
  <tr>
    <td>shuttle</td>
    <td>9</td>
    <td>58000</td>
    <td>6</td>
    <td>63</td>
    <td>99</td>
    <td>32</td>
    <td>28</td>
    <td>7</td>
    <td>20</td>
    <td>33</td>
    <td>23</td>
    <td>23</td>
    <td>159</td>
  </tr>
  <tr>
    <td>soybean</td>
    <td>35</td>
    <td>623</td>
    <td>6</td>
    <td>63</td>
    <td>88</td>
    <td>32</td>
    <td>9</td>
    <td>5</td>
    <td>25</td>
    <td>25</td>
    <td>25</td>
    <td>16</td>
    <td>71</td>
  </tr>
</table>
Explanations for Decision Trees 21

<table><caption>Table 2: Explanation-redundancy in decision trees obtained with IAI and ICI</caption><tr><td>spambase</td><td>57</td><td>4210</td><td>6</td><td>63</td><td>75</td><td>32</td><td>37</td><td>12</td><td>16</td><td>33</td><td>19</td><td>15</td><td>143</td></tr><tr><td>spect</td><td>22</td><td>228</td><td>6</td><td>45</td><td>82</td><td>23</td><td>60</td><td>51</td><td>20</td><td>50</td><td>35</td><td>6</td><td>15</td></tr><tr><td>splice</td><td>2</td><td>3178</td><td>3</td><td>7</td><td>50</td><td>4</td><td>0</td><td>0</td><td>—</td><td>—</td><td>—</td><td>88</td><td>177</td></tr><tr><td>student-mat</td><td>32</td><td>395</td><td>6</td><td>109</td><td>35</td><td>55</td><td>9</td><td>3</td><td>20</td><td>25</td><td>21</td><td>22</td><td>177</td></tr><tr><td>student-por</td><td>32</td><td>649</td><td>6</td><td>119</td><td>30</td><td>60</td><td>1</td><td>0</td><td>20</td><td>20</td><td>20</td><td>22</td><td>259</td></tr><tr><td>tae</td><td>5</td><td>110</td><td>6</td><td>43</td><td>40</td><td>22</td><td>9</td><td>6</td><td>25</td><td>33</td><td>29</td><td>8</td><td>23</td></tr><tr><td>titanic</td><td>3</td><td>24</td><td>2</td><td>5</td><td>40</td><td>3</td><td>33</td><td>25</td><td>50</td><td>50</td><td>50</td><td>2</td><td>5</td></tr><tr><td>tram_2000_side_16x16</td><td>256</td><td>2000</td><td>1</td><td>3</td><td>100</td><td>2</td><td>0</td><td>0</td><td>—</td><td>—</td><td>—</td><td>1</td><td>3</td></tr><tr><td>uci_mammo_data</td><td>13</td><td>126</td><td>6</td><td>53</td><td>11</td><td>27</td><td>51</td><td>43</td><td>16</td><td>40</td><td>24</td><td>9</td><td>23</td></tr><tr><td>vehicle</td><td>18</td><td>846</td><td>6</td><td>79</td><td>49</td><td>40</td><td>10</td><td>0</td><td>16</td><td>20</td><td>19</td><td>24</td><td>141</td></tr><tr><td>wdbc</td><td>30</td><td>569</td><td>2</td><td>7</td><td>87</td><td>4</td><td>0</td><td>0</td><td>—</td><td>—</td><td>—</td><td>57</td><td>115</td></tr><tr><td>wpbc</td><td>33</td><td>198</td><td>2</td><td>5</td><td>57</td><td>3</td><td>33</td><td>0</td><td>50</td><td>50</td><td>50</td><td>2</td><td>5</td></tr><tr><td>yeast</td><td>9</td><td>1462</td><td>6</td><td>45</td><td>49</td><td>23</td><td>4</td><td>0</td><td>25</td><td>25</td><td>25</td><td>64</td><td>493</td></tr><tr><td>zoo</td><td>16</td><td>59</td><td>6</td><td>23</td><td>91</td><td>12</td><td>33</td><td>7</td><td>16</td><td>33</td><td>21</td><td>6</td><td>13</td></tr></table>