Decision Trees with Short Explainable Rules
Authors: Victor Feitosa Souza
Ferdinando Cicalese
Eduardo Sany Laber
Marco Molinaro
Venue: NeurIPS 2022 Accept (2022)
Keywords: decision trees
explainable models
classification
approximation algorithms

Abstract: Decision trees are widely used in many settings where interpretable models are preferred or required. As confirmed by recent empirical studies,  the interpretability/explanability of a decision tree critically depends on some of its structural parameters, like size and the  average/maximum depth of its leaves. There is indeed a vast literature on the design and analysis of decision tree algorithms that aim at optimizing these parameters.

This paper contributes to this important line of research: we propose as a novel criterion of measuring the interpretability of a decision tree, the sparsity of the set of attributes that are (on average) required to explain the classification of the examples. We give a tight characterization of the best possible guarantees achievable by a decision tree built to optimize both our new
measure (which we call the {\em explanation size})  and the more classical measures of worst-case and average depth. In particular, we give an algorithm that guarantees $O(\ln n )$-approximation (hence optimal if $P \neq NP$) for the minimization of both the average/worst-case explanation size and the average/worst-case depth. In addition to our theoretical contributions, experiments with 20 real datasets show that our algorithm has accuracy competitive with CART while producing trees that allow for much simpler explanations.  

Decision Trees with Short Explainable Rules
Victor F. C. Souza
Departamento de Informática
Pontifical Catholic University of Rio de Janeiro Rio de Janeiro, RJ Brazil vf vfsouza@inf puc-pio...... br
Ferdinando Cicalese Department of Computer Science
University of Verona
Verona - Italy
ferdinando. ceicaleseeuniiin it
Eduardo Sany Laber Departamento de Informática
Pontifical Catholic University of Rio de Janeiro Rio de Janeiro, RJ - Brazil
laber@inf. puc-rio.....
Marco Molinaro
Microsoft Research & Pontifical Catholic University of Rio de Janeiro mmol inaro@mi crosoft. com
Abstract
Decision are widely used in many settings where interpretable models are preferred or required. As confirmed by recent empirical studies, the interpretabil- ity/explainability of a decision tree critically depends on some of its structural parameters, like size and the average/maximum depth of its leaves. There is indeed vast literature on the design and analysis of decision tree algorithms that aim optimizing these parameters.
This paper contributes this important line of research: propose novel criterion of measuring the interpretability of decision tree, the sparsity the set attributes that are (on average) required to explain the classification of the examples. We give a tight characterization of the best possible guarantees achievable by a decision tree built optimize both size) and the more classical measures of worst-case and average depth. In particular, give algorithm that guarantees OIn n) approximatio (hence optimal if explanation size our theoretical contributions,
measure (which call the explanation
P + N P) for the minimization of both the average/worst-caat and the average/worst-case depth. In addition experiments with 20 real datasets show that our algorithm has accuracy competitive with CART while producing trees that allow for much simpler explanations.
Introduction
Machine learning models and algorithms appear and more frequently in systems that make decisions with an impact in our lives. Thus, is highly desirable that the output of these methods
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

are interpretable so that we can use them more comfortably eventually, question its applicability [13].'
Decision trees are used in many settings as a tool to provide explainability. However, their explainabil- ity greatly depends on the depths of its leaves, as empirically demonstrated by [46]. In fact, based on empirical data from survey with 98 questions answered by 69 respondents, the authors conclude that "question depth" (the depth of the deepest leaf that is required when answering questions about tree) turns out to be the most important parameter. Essentially, users prefer trees where the information about the most common items are given at the top of the tree. Minimizing the average/worst-con depth indeed has been a classic goal for decision tree algorithms (see the Related Work section below).
However, another very important component for explainability is having decision rules that are sparse, namely, that use few different attributes possible to classify an object make a prediction. For decision trees, this means that the path to any given leaf should test only a small number of different attributes. Figure shows two trees for the Sensorless dataset [7] with similar accuracy. While the trees have the same size, the rightmost one gives much more concise classification rules. As a spoiler, the left tree was constructed using CART and the right one using the algorithm we propose in this paper. To exemplify their differences, let us consider the leaves that are marked in the figure with a thick rectangle. Both are assigned the same class and cover the maximum number of examples in the training set (upproximately 11,500 example each). Despite this similar behaviour, the explanations for their classifications are quite different (the D, denote the attributes):
CART:
D1 E [-0.11, 0.07] AND Dg > -0.01 AND
D10 0.03
New algorithm:
D [-0.01, 0.03]
Define the explanation size of leaf as the number of distinct attributes tested on the path from the root to this leaf. The above example shows that having trees whose leaves have small explanation size yields significantly simpler (hence easier to interpret/explain) rules. However, to the best of our knowledge there is no prior work considering decision trees optimized with respect to the explanation size.
D.1-1111
D.y
Dus 0.0L
Byc-dn:
Byr 0.00
0,c0.02
0.88
0,c0.02
Duc 0.00
Duc0:2
Dycom
Figure 1: The left and right decision trees are built, respectively, by CART and the algorithm proposed in this paper for the Sensorless dataset. The maximum depth was set Internal nodes associated with the same attribute have the same color. The colors inside leaf indicate the attributes that are used obtain its classification.
Our contributions. In this work propose the explanation size as novel measure to capture the interpretability of a decision tree. In particular, we initiate principled study of decision trees with small explanation size by focusing on: (i) the trade-off that optimizing this criterion imposes on other desirable metrics (c.g., average/worst wwtte//wowttccsseeeo depth); (ii) the design of efficient algorithms for building such trees that guarantee good performance practice.
Our first result is that it is possible to essentially obtain a best-of-both worlds terms of average/worst case depth and explanation size: We show that there is always binary decision tree that has the smallest average explanation size possible but also has average depth not much larger than that of the
We use the words interpretability and explainability in broad sense: for a detailed discussion of the different concepts related to the topic (see, for example, [41]).

---

relate our work with those from the optimal tree for the latter metric (Item 2 of Theorem 1). The same result also holds when considering worst-case explanation size and depth (Item 1 of Theorem 1). Remarkably, the latter (worst-case bound) turns out to be tight. Theorem 2 shows it matches a necessary trade-off between optimizing explanation size and depth, i.e., improving the bound on the depth in Theorem can only be attained at the cost of logarithmic factor loss in the explanation size.
Despite having strong theoretical guarantees, the construction obtain these trees is too wasteful to be used in practice. Thus, our second contribution is an algorithm that still yields a tree that provably approximates both optimal average/worst-co but has enough flexibility that it can be employed to obtain good performance in practice. To demonstrate the applicability of our proposal, we compare it against CART [11], a quite popular method to build decision trees, on 20 real classification datasets. Our method leads to much more (resp. more) interpretable trees in terms of explanation size (resp. average depth), while having a performance similar to CART in terms of accuracy and speed.
explanation size and depth (Theorem 3)
2 Related work
Our work can be connected with an active line of research that proposes interpretable models for machine learning [13], in particular more interpretable rule-based models (e.g. decision lists, sets, and trees) [37, 30, 21, 9]. Our interpretability metric is closely related to rule sizes considered in the rule learning literature, e.g., [31, 47]. In addition,
vast literature of methods with provable guarantees that are designed to build decision trees of "low complexity" (e.g. depth of leaves, number of nodes, etc.) [23, 22, 18, 8, 24].
More interpretable rule-based models. There body of work that aims to understand what makes rule model more comprehensible via experiments with end users [4, 29, 46). The paper [4] compares the comprehensibility of classifiers that are learned by decision trees and rule-learning algorithms, based on subjective comparisons of classifier pairs by 100 Computer Science students. They conclude that decision trees are more comprehensible. In [29], based on experiments with business students, it is concluded that decision tables are more interpretable than decision trees and propositional "if-then" rules. One potential limitation of this study is that these students had no experience with the representation formats, it is not clear whether this conclusion can be extended for more experienced users. The work of [46] reports a survey with 69 respondents that was carried out to understand what makes a decision tree more interpretable. Among their findings is that the depth of the leaves required by users during the experiments had one of the biggest and most consistent impact the usability of decision trees across multiple tasks (classify, explain, validate, and discover).
There are some recent works that try to optimize interpretabilty metrics when building rule-based models [37, 10, 56, 30, 40, 9]. We briefly discuss those that focus on decision trees. The paper [30] contends that splits that have at least one of its parts/child nodes being class- hous-hooogeeeuus (roughly this means that most examples have the same class) are important for interpretability. and propose a splitting criterion that tries to balance this homogeneity and the depth of the leaves. In contrast to work, no provable guarantees are provided. The works [10, 56) employ Integer Linear Programming to build trees of a given maximum depth, while [40] employs Dynamic Programming techniques to develop an optimization framework that allows the construction of decision trees with few leaves that optimize variety of objective functions such as F-score and AUC. These methods, while interesting, are much more complex to implement than ours and they do not run in polynomial time, which may compromise their application on large datasets.
Decision trees with provable guarantees. There is a vast literature dedicated to the problem of building decision trees with "low complexity", where the complexity of a tree can be measured in different ways, including worst-case/average leaf depth and number of nodes, among others [12]. It is known that building decision tree that minimizes the worst-case average leaf depth, among those that fit the training data, does not admit an o(log n) approximation unless P=NP [16, 36). When the goal is minimizing the number of nodes, the problem is even harder to approximate [3, 26). Regarding upper bounds, several algorithms with the optimal (within constants) Olog n approoxximtioo are known for minimizing the worst-case and average depth [23, 22, 17, 18, 8, 24, 32, 39, 44]. What distinguishes each method is the generality of its guarantee; for example, some consider scenarios
3

---

that include tests with noisy outcomes [32], while others consider items/examples with non-uniform weights and tests with non-uniform costs [18, 44].
We remark that the method we propose here also allows the use of non-uniform weights on the examples, which can be used, for instance, to prioritize models that yield simpler explanations for some classes of particular interest, by setting high weights for examples in these classes. The key difference between our method and the existing ones is that ours is the only one that provides theoretical guarantees on the explanation size.
3 Model
We describe the model used throughout for the theoretical analyses. For that, we adopt terminology similar to that employed by some closely related works [1, 18). On an instance Z, there is set of ordinal attributes A and a set of objects O, where each object E described by the value it takes on each attribute E A; we denote this value by a(o). Each object also has class c(o) in some set C. In order to classify an object o, we are allowed to use threshold tests of the form "Is a(o) < t?" for some attribute a and threshold value t.
(threshold) decision tree I' is rooted tree where each internal node v is associated with a threshold test "Is a(o) < t?" and the edges from a node to its children are associated to the two possible outcomes "a(o) < t" and "a(o) 2 f". We also refer to this test by the atrributethresholld pair (a, t). Each leaf & of T is associated with a class in C. Given a decision tree T, we say that an object reaches a node y of T if agrees with all outcomes associated with the path from the root of T to v. For each E O, we use E(o) to denote the unique leaf reached by object Finally, we consider the exact classification model, namely a decision tree must correctly classify all objects of the instance, i.e., each object E O reaches some leaf associated to its correct class c(o).
We now formalize the measures of interpretability that were mentioned in the introduction.
Depth and explanation size of a tree. We start recalling the classical notions of worst-case and average tree depth. Given decision tree T, the depth of leaf é the number of tests/internal-nodes on the path from the root of T to l, and is denoted by (epth(f). The worst-case depth of the tree T is obtained by considering the maximum depth over its leaves, namely
depth wo
max depth(E).
REleal(T)
To measure the average depth of the tree, in addition to the datum above, as part of the input each object o has a non -egnnveeevve weight w()) E R,, indicating its likelihoo/impootancc.. Letting w be the sum of the weights of all objects that reach leaf l, the average depth of the tree T is then the weighted sum the depth of its leaves, namely
depth (T)
Σ &Eleaf(T)
w(() depth
We now consider the novel measures of qualityiineeppreaablity of a tree using the notion explanation size. The explanation size of leaf f, denoted by expl(E), is the number of different attributes on the tests on the path from the root of T to f. As an example, the explanation size of the leaf marked with thick rectangle on the left tree of Figure tree T are then given as before by the largest and the weighted sum of the explanation sizes of its leaves, respectively:
3. The worst-case and average explanation size of
expl (T)
max expl((), TElat(T)
expla0g (T)
Σ (Elea((T
w(() expl(
Our goal is to obtain trees with as small worst-case/average depth and explanation size as possible. We use depth;, we = depth (7) to denote the smallest possible worst-case depth of a decision tree that solves instance and define the optimal values expl depthagg and expl analogously.

---

Tradeoff between depth and explanation size
Our goal obtain trees that simultancously have both small worst-case/average depth and explana- tion size. However, is this even possible? It is conceivable that in order to obtain trees with small depth, one may be required to use several different attributes along the paths to effectively classify the objects; but this would make the tree have large explanation size. Conversely, in a tree with small explanation size, the few attributes along path may need to be used many times in order to correctly classify the objects, leading to a large tree depth.
Perhaps surprisingly, we show that there are trees that simultaneously have optimal explanation size and almost optimal depth.
Theorem 1. Given an instance of the classificution problem, the following holds:
1. (Worst-case metrics) There exists a binary tree T for which simultaneousty
explare expl depth (T') S depth + log n.
2. (Average metrics) There exists binary tree IT for which simultuaeeussy explavg (T) expla
depthavg (T) - 2 depthavg + W log n.,
where W is the sum of the weights of the object in the instance.
We remark that these additive bounds on the worst-case and average depth imply O(log n.) multiplica- tive approximations as well.
Observation The bounds from Theorem imply
3 3log n
depth we (7)
depth
log
depth ang (T) 5 3 log depthagg
where is the number of classes.
While the proof of Theorem 1 is deferred to Appendix B, we give here the main ideas behind it. We will consider here only the worst-case metric (Item 1), since the proof is simpler and more transparent.
To show the existence of our desired tree we make use of multiway trees, i.e., a decision tree where multiway tests are used rather than threshold tests. A multiway test associated with attribute a splits the objects based on all possible values of this attribute. As an example, if an attribute a takes distinct values for the objects in the instance and use the root of a multiway tree, then the root will have children.
The starting point for the construction of the tree in Theorem is the equivalence between optimal binary trees and optimal multiway trees in terms of worst-case explanation size. While this is formally proved in Lemmas 2 and 3, for an intuitive view of this equivalence first notice that there is multiway tree M that simultaneously optimal in terms of worst-case depth and worst-case explanation size, since each attribute only needs to be used once in path. Also, this optimal multiway tree M* has worst-case explanation size (equivalently worst-case depth) at most that of the best binary tree, namely depth expl (M*) S expl since intuitively multiway tests are more informative than binary tests. Conversely, we can transform an optimal multiway tree M into a binary decision tree T by simulating each multiway test an attribute a by using multiple threshold tests "Is a()) t" with varying (but same attribute a). Since explanation size only counts the number of distinct attributes used along path, the tree T' so created has exactly the same explanation sizes as M and hence expl (M*) = expl, (T) 2 expl" Thus, we have the equivalence exppl,...MM) = exple
To prove Theorem 1, we start with the optimal multiway tree M and convert it into binary tree, as above. However, the conversion in the previous paragraph is not enough: while preserves the explanation size, it may greatly increase the depth of the leaves when using multiple threshold tests to simulate a multiway test (possibly yielding depth > depth The key idea is to use much more efficient simulation that is based alphabetic codes, classic notion from coding theory [28].
5

---

The following result from [2, Chp. 2. p. 341], rephrased in the terminology of decision trees, gives a sufficient condition for the existence of such codes with prescribed code-lengths d; s.
Lemma 1. Consider an instance of the classification problem with n. objects but only I attribute. Then for any positive integers di,..., dn such that -;=1 2-th S there exists a binary threshold decision tree with n leaves at depths d1,...d, such that the i-th object reaches the leaf at depth di.
Then for each node v of M (corresponding to an attribute a, and with children ch1, chz, ..2....... .). we consider all objects that reach a child ch, as a "single object" (with the corresponding value in attribute a) and applying the previous lemma we replace v by a binary tree where the leaf corresponding n(v) n(cht) 1 1, where n (node) is the
to the objects in ch, end up in a leaf at depth (in A) & = [log number of objects that reach given node in M The final tree obtained, call it T, still has the same explanation sizes as M so we (7) = expl" Moreover, in terms of worst-case depth, any root-to-leaf path P in 7 has a correponndng path Par- vo, P2,............................. in M* and the length of P at most
PPa---11
([1os
r((ss) n(v(41) +1) < logn + (lenghh of Pas-
By looking at the longest such path get
depth (2) < logn + 2 de (M*) S log + 2 depth where the last inequality holds because of the optimality of M with respect to worst-case depth. This gives Item 1 of Theorem 1.
The average-case part of the theorem (Item 2) uses similar ideas, but in addition relies on entropy- based calculations to argue about the average depth of the constructed tree.
Observation 2. Theorem I is an existential result and the construction outlined above cannot be done in polytime, since it relies on the availability of an optimal multiway tree. However, one can obtain in polytime tree that is simultaneously (respectively average) explanation size and depth by replacing the optimal multiway tree by one that approximates within factor of (log n) the worst-case (resp. average) depth, which can be found in polytime (see, e.g., [18] and references therein quoted).
Oloo n.) approximation for both worst-case
Although guaranteeing asymptotically the desired optimal approximation, the construction leading to such trees might be wasteful in practice involves the use of distinct alphabetic codes to turn each multiway tests into a short sequences of threshold tests. Therefore, we present alternative approach Section 5 that achieves the same approximation guarantee and has also very good performance in practice.
4.1 Lower bound
Given these positive results, natural question is whether it is possible obtain tree that is optimal for both depth and explanation size. The next result answers this in the negative, and shows that in a way the worst-case bound in Theorem 1 cannot be improved.
Theorem 2. Fix c and n Z cst for a sufficiently large constant cst. Then for every a e logín/2) - 1)}, there is classification instance with n examples and e classes such that 2loge 2 loge
every binary decision tree T for this instance has either
depth (T) > 2 depth
or
log (") expl
expl (T)
4a
Remark 1. To get a more concrete idea for this lower bound, consider setting a at its upper limit, namely a loge this case we obtain that every tree with depth (T) S 1 log depth
loge
must have (T) 2 2((1 - log.) log c) expl which is 22log n) explinc if we set c log Comparing this against Theorem I and Observation we see an interesting and subtle phenomenon: while you can have a tree with depth < the approximation the depth to constant factor smaller then you must lose a logarithmic factor in the approximation in the explanation size.
log n
3 3log log depthine and optimal expl (T)) ) if you require
factor

---

5 An efficient and practical algorithm
In this section we design an algorithm, which we name Short Explanaible Rules (SER-DT), that always yields trees of approximately optimal wverage/worst-can explanation size and depth. Impor- tantly, our method has enough flexibility that it can be tuned trade-off accuracy and interpretability, as shown in our computational experiments (Section 6).
Similar other algorithms in the area, ours chooses in each step split that creates subtrees with "small impurity". However, unlike most such algorithms, it is not completely greedy and allows for the desired extra flexibility in the choices.
To describe the algorithm, consider a set of objects S S O and let S(a, i) (respectively S(a, S i) and S(a, > i)) be the set of objects in S with value equal (respectively at most and larger than) i on attribute a. Moreover, let w(S)= := Eees wo() denote its total weight. Let o, o' be a pair of objects S such that c(o) J c(o'). We will refer to such a pair as misclassified pair because if both o and of reach the same leaf in the decision tree then one of them will be surely misclassified.
We use P(S) to denote the number of misclassified pairs in S. This quantity can be thought of as a measure of the amount of work that is needed to reach correct classification of all objects in S and it has been previously used in [19, 22, 18]. To take into account also the importncc//weighe of set S we define (Sm == P(S)- wS)) as the weighted pair-wise misclassification of S.
As pre-processing step, before executing SER-DT, each weight w=() smaller than replaced with
) is where Wmin is the smallest positive weight among the objects in O. This idea (from [35]) is important to guarantee a logarithmic dependence on instead of wr woO).. After this preprocessing, SER-DT is called for the set of objects O.
The pseudo-code description of SER-DT is presented in Algorithm 1, First SER-DT tries to any balanced test that reduces the weighted pair-wise misclassification of the current set of objects (in the worst case) by at least a factor. In any path of the tree built by SER-DT the amount of these balanced tests is at most logarithmic, so they can be easily handled in our analysis. If no balanced test exists, then the algorithm finds an attribute a" and value t* such that in the ternary split S(a", < t), S(a",t") S(a", >> (²), only the middle set S(a", (²)) has weighted pair-wise misclassification larger than the desired (wpm()) (S). This 3-way partition is obtained by using two binary splits. Then, the algorithm recurses
each set. A critical issue is to show that in this case some progress is also achieved with the problematic subproblem on S(a", ,t' where vpm(S((a., t*) > wpm In fact, the choice of the attribute a" is such that, the instance S(a", .t') has the minimum weighted pair- wise misclassification among all the attributes and other possible tripartitions. As a result, we can employ lower bound on the optimum Lemmaa 8 in appendix) that allows to absorb the cost of the subtree for the subproblem S(a", t) in the logarithmic guarantee.
Algorithm SER-DT (S : set of objects)
1: if all objects in S are assigned to the same class, create a lcaf assigned to such class and return
2: if there is a test 7 that splits S into S and S such that max max/upm(S*)) upm((*), upm(S*) < >Pp(()) then
3: Use any such test, say (a, t), as the root of the decision tree and S(a, > t)
4: Recurse the children S(a,
5: else
6: Let a" be an attrihute in argmin (max (max upm(S i))3
7: Let t" be the smallest value of the attribute a" such that the "left child" S(a", S t*) satisfies
upm(S(a" "et(S(aasst" t²)) 2 wpm(S).
8: Use two binary tests to simulate the 3-way split S(a", , t"), S(a", t²), S(a" "aa".>10 t²). More precisely,
the root a test attribute a" that splits S into the sets S(a" (t) and Sia" 2 (*). Then, apply test on the right child the root, currently associated with S(a" (*), creating two new children with objects S(a",, (*)) and S(a", ; > (*)
9:
Recurse on each of the three leaf nodes in the current tree
10:
end if
The following is the promised guarantee for the average/worst-cass depth and explanation size of the trees produced by the algorithm.
7

---

Theorem 3. Given an instance I, the algorithm SER-DT produces a tree T that satisfies
1. (Worst-casy metrics)
depthavg (T) I O (log n) deptharg
explang (T) O (log n) explang
2. (Average metrics)
depth (T)) S O (log n) depth
expl (T) & O (log n) expl
We remark that, the light of the inapproximability results from [36, 16]² this theorem says that SER-DT (with the preprocessing step) guarantees the best possible approximation obtainable by polynomial algorithm with respect to both the measures under consideration: worst/average depth and worst/average explanation size.
6 Experiments
In this section, we report the experiments that were carried out to evaluate how our proposed algorithm SER-DT performs in practice.
ToA
02
0.5
1.0
0.1
0.6
FactorEag3
FaceorBag
Figure The left (resp. right) image shows the average accuracy (resp. explang) over the 20 datasets as function of FactorExpl.
We considered the 20 datasets that appear on Column 1 of Table 1 (see Appendix for their main characteristics). For all of them, 70% of the examples were used for training and the remaining 30% for testing. Moreover, all the examples (objects) were considered equally important (weight=1/size of training set). During preprocessing step converted all categorical attributes into binary attributes via one-hot-encoding. See also Appendix for more details on the experimental setup.
Recall that in (Line 2) of algorithm SER-DT DT any test that splits the current set of objects into subsets of small enough wpm could be used. We use this flexibility to select a test among these that should further help in obtaining small explanation sizes and high accuracy in practice. To explain our selection, recall the Gini impurity measure employed by CART. For a set of examples (objects) S, each of them labeled with class in {1, (1,...,ch, .c. the Gini impurity is given by
S
2
Gini(S) =1 Σ
S
==1
where S; the set of examples of class i. Moreover, the weighted Gini impurity Gini(7, v) induced by a test r that divides the set of examples S that reach a node v into S and S is given by
|SL Gini + [S] Gini
[S
Gini Cini(T,P)
[S|
Let FactorExpl be hyper-paranen parameer in the range [0, 1]. Because are interested in trees that induce accurate classifiers with short explanation rules, expand a given leaf v, in Line 2 of the algorithm we select, among the permissible tests the test that minimizes
AdjustedGiniExpl v) I(r, x Gini(T,
"The hardness of approximation holds also for instances with only binary attributes. In this case explanation size coincides with depth every test can be considered threshold A permissible must satisfy Gini(7, v) < Gini (Examples that reach v), in addition to respect the condition of Line 2

---

where I(T,V)) = FactorExpl if the attribute associated with test has already appeared in the path from the root to v. and I(T, 1/ otherwise. Since FactorExpl is used to favour attributes that have already appeared in the path, when FactorExpl is set to low value we expect to obtain trees with short explanations but also with lower accuracy, as the effect of the Gini impurity is reduced.
In terms of stopping rules, we do not expand a leaf y if it is either located at depth 6 or if there is no test for which Gini(T, 2) is smaller than Gini (Examples thaat reach v)). As post-processing step, whenever two sibling leaves are assigned the same class, we delete them both and leave their parent leaf.
In our first experiment we study how the accuracy and the interpretabilityy measures of the trees produced by our algorithm behave when FactorExpl is varied. Figure 2 shows the average accuracy (left image) and the average explanation size explaeg (right image) as a function of FactorExpl. More precisely, for the left image, the y-value associated with point x: corresponds the average accuracy on the testing set, calculated over the 20 datasets, when our algorithm is executed with FactorExpl z. For the right image the same logic holds. As expected, the larger the FactorExpl the larger the accuracy and the explarg' The interesting finding, however, is that the accuracy increases relatively slow, for FactorExpl close to I, compared with the growth in explagg (see the Table 5 in the appendix for experiments with FactorExpl in the range (0.95,0.99]). This suggests that possible obtain trees that are significantly more interpretable without sacrificing the accuracy.
Table 1: Test Accuracy, explang and expl for FactorExpl 0.97. Each entry is the average of 10 runs using different seeds to select the examples in the training and testing set. Boldface values indicate difference of more than 1% (columns 2,3) or a gain of least 25% favour of SER-DT (columns 4,5,6 and 7).
Test Accuracy
explase
expl
Dataset
SER-DT
CART
SER-DT
CART
SER-DT
CART
94.8%
94,7%
4,78
5,24
6.0
6.0
audit risk avila
99.9%
99.9%
1,00
1,00
1.0
1.0
61,5%
63,2%
3,06
4.22
4,9
5,4
banknote
97.6%
98.1%
2.44
2,55
3,8
3,4
bankruptcy polish
96,6%
96.9%
2,56
4.63
5,6
5,9
cardiotocography
89.5%
89,8%
4,30
5,30
5,9
6,0
collins
13.2%
15,6%
2,13
4.76
4,4
5,9
default credit card
82,0%
81,9%
1,45
4,29
4,5
6,0
dry bean eeg eye state
90.1%
89,8%
3,32
4.45
5.1
6.0
74.1%
73,6%
3,69
4,29
5,9
6.0
htru2
97.7%
97.7%
1,20
2,03
4.3
4.9
94,2%
93.6%
1.75
1,76
3,1
3,4
letter recognition
44,9%
47,9%
3,34
5,50
5,5
6,0
mice
99,9%
99,9%
3,05
3,05
3,6
3,6
obs network
91,7%
89.5%
3,48
4,26
5.3
5,9
occupancy room
99.4%
99.3%
4.18
4,54
5.3
5.7
online shoppers intention
89.3%
89,8%
3,30
4,00
5.1
6.0
pen digits poker hand sensorless Average
88,6%
86,9%
4.76
5,31
5,8
6,0
52,9%
55,0%
1,80
4,30
3,8
5,1
87,4%
80.1%
2,94
4,03
4.9
5,5
82,3%
82,2%
2.93
3.97
4.69
5.19
In our second experiment we compare the results our method, using FactorExpl = 0.97 with CART [11]. The value 0.97 is motivated by the above observation. To expand a leaf v, recall that CART selects the test 7 for which Gini (T, //) is minimum and it only expands v if there is test 7 for which Cini(T,v) < Gini (Examples that reach v). To provide fair comparison with our algorithm we set the maximum depth to and applied the same aforementioned post- post-processing. Table shows the accuracy the testing explanation size exply.c for all datasets. Each entry in this table is the average of ten runs, where in each of them different seed used split dataset into training and testing
well the average explanation size explang and the worst-case
We notice that the accuracy of our method is very close that obtained by CART, while the gain in terms of the interpretability metries is significant. On 7 datasets (bold-faced columns 2 and 3)

---

observe a difference larger than 1% on the accuracies; on 3 of them our algorithm outperforms CART while on the remaining 4, CART is better. In terms of the average explanation size, our algorithm is at least as good as CART for all datasets, and for 9 of them (bold-faced on columns and 5) it improves the explang ang by least 25%. For the expl the gain also clear. For all datasets, our algorithm is at least as good as CART. Moreover, for 3 of them (bold-faced on columns 6 and 7), it provides a gain of at least 25%. Boxplots for the experiments in Table are provided in Section E.5 of the appendix.
Banknote,
In Appendix E we compare CART and SER-DT in terms of depth aeg and depth For depth SER-DT performs better than CART while for depth the results are similar. The result for depth not surprising since set as the maximum depth in our experiments. Regarding running time, the algorithms present similar behaviour, as it can be verified in Appendix E. This is somehow expected since both consist of mostly a greedy split selection at each node.
In the appendix we also present additional experiments and analyses. we evaluate the impact of applying post-pruning to both CART and SER-DT. Moreover, in Section E.7, we show comparisons of SER-DT with one of the state of the art decision tree methods that optimize the average depth, namely the EC2 algorithm from [22]: the experiments suggest that SER-DT performs significantly better than EC2 on all metrics.
particular, in Section E.8,
7 Conclusion
In this work, we proposed the explanation size as a new metric to capture intrepretability of decision trees and initiated a principled study of it. We presented upper and lower bound on the trade-off of simultaneously optimizing this new metric and metries related to depths of the leaves.
We also proposed practical algorithm that provably approximates the average explanation size and the average depth and showed, via experiments over 20 datasets, that competitive with the widely used CART algorithms in terms of accuracy while being much better in terms of producing trees with short explanation size.
On the basis both the theoretical analysis (approximation guarantee) and the performance demon- strated in the empirical studies, believe that our algorithm (or some variation based its ideas) can be used to generate accurate and highly interpretable trees for practical applications.
Acknowledgments and Disclosure of Funding
This study was financed part by the Coordenação de Aperfeigoamento de Pessoal de Nível Superior Brasil (CAPES) Finance Code 001. The work of the third author is partially supported by CNPq (grant 307572/2017-0), by FAPERJ, grant E- 2220228233/018 and by the Air Force Office of Scientific Research under award number 2A9550-22-1-0475.
The fourth author is supported by Bolsa de Produtividade Pesquisa #312751/2021-4 from CNPq.
and FAPERJ grant Jovem Cientista do Nosso Estado.
10

---

References
[1] Micah Adler and Brent Heeringa. Approximating optimal binary decision trees. Algorithmica, 62(3-4):1112-1121 2012.
[2] Rudolf Ahlswede and Ingo Wegener. Search problems. John Wiley & Sons, Inc., 1987.
[3] Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, and Toniann Pitassi. Learnability and automatizability. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 621-630. IEEE Computer Society, 2004.
[4] Hiva Allahyari and Niklas Lavesson. User-oriented assessment of classification model under- standability. Anders Kofod- Petersen, Fredrik Heintz, and Helge Langseth, editors, Eleventh Scandinavian Conference on Artificial Intelligence, (SCAI) 2011. Trondheim, Norway, May 24th 26th, 2011, volume 227 of Frontiers in Artificial Intelligence and Applications, pages 11-19. IOS Press, 2011.
[5] E. Alpaydin and Fevzi Alimoglu. Pen-Based Recognition of Handwritten Digits. UCI Machine Learning Repository, 1998.
[6] Banknote Authentication. UCI Machine Learning Repository, 2013.
[7] Martyna Bator. Dataset for Sensorless Drive Diagnosis. UCI Machine Learning Repository, 2015.
[8] Gowtham Bellala, Suresh K. Bhavnani, and Clayton Scott. Group-based active query selec- tion for rapid diagnosis in time-critical situations. IEEE Transactions on Information Theory, 2012.
[9] Clément Bénard, Gérard Biau, Sébastien Da Veiga, and Erwan Scornet. Interpretable random forests via rule extraction. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 937-
945. PMLR, 2021.
[10] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Mach. Learn., 106(7):1039- 1082, 2017.
[11] Leo Breiman, Jerome Friedman, Charles Stone, and R Olshen. Classification and Regression Trees. Chapman & Hall/CRC, Philadelphia, PA, jan 1984.
[12] Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: survey. Theor. Comput. Sci., 288(1):21 2002.
[13] Nadia Burkart and Marco F. Huber. A survey on the explainability of supervised machine learning. J. Artif. Intell. Res,, 70:245-317, 2021.
[14] D. Campos and J. Bernardes. Cardiotocography, UCI Machine Learning Repository, 2010.
[15] Robert Cattral and Franz Oppacher. Poker Hand. UCI Machine Learning Repository, 2006.
[16] Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Pranjal Awasthi, and Mukesh K. Mohania. Decision trees for entity identification: Approximation algorithms and hardness results. ACM Trans. Algorithms, 15):11::111:222, 2011.
[17] Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Marco Molinaro. On greedy algorithms for decision trees. In Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, Algorithms and Computation 21st International Symposium. ISAAC, 2010. Jeju Island, Korea, December 15-17, 2010, Proceedings. Part II, volume 6507 of Lecture Notes in Computer Science pages 206-217. Springer, 2010.

---

[18] Ferdinando Cicalese, Eduardo Sany Laber, and Aline Medeiros Saettler. Diagnosis determina- tion: decision trees optimizing simultaneously worst and expected testing cost. Proceedings of the 31th International Conference on Machine Learning, ICMI. 2014, Beijing, China, 21-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, pages 414 4224 JMI.- R.org, 2014.
[19] Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. In Proceedings of the 18th International Conference on Neural Information Processing Systems, NIPS'05, page 2357242, Cambridge, MA, USA, 2005. MIT Press.
[20] R.A. Fisher. Iris. UCI Machine Learning Repository, 1988.
[21] Rafael García Leiva, Antonio Fernández Anta, Vincenzo Mancuso, and Paolo Casari. A novel hyperparameter-feee approach to decision tree construction that avoids overfitting by design. IEEE Access, 7:99978 99987, 2019.
[22] Daniel Golovin, Andreas Krause, and Debajyoti Ray. Near-optimal bayesian active learning with noisy observations. In John D. Lafferty, Christopher K. I. Williams, John Shawe-Taylor, Richard S. Zemel, and Aron Culotta, editors, Advances Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, pages 766-774. Curran Associates, Inc., 2010.
[23] Andrew Guillory and Jeff A. Bilmes. Average-case active learning with costs. In Ricard Gavaldà, Gábor Lugosi, Thomas Zeugmann, and Sandra Zilles, editors, Algorithmic Learning Theory, 20th International Conference, (ALT) 2009, Porto, Portugal, October 3-5, 2009. Proceedings, volume 5809 of Lecture Notes in Computer Science, pages 141-155. Springer, 2009.
[24] Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, and R. Ravi. Approximation algorithms for optimal decision trees and adaptive (tsp) problems. CoRR, abs/1003.0722 2010.
[25] Te Sun Han and Kingo Kobayashi. Mathematics of information and coding, volume 203. American Mathematical Soc., 2002.
[26] Thomas R. Hancock, Tao Jiang. Ming Li, and John Tromp. Lower bounds on learning decision lists and trees. Inf. Comput., 126(2):1 14-122, 1996.
[27] Clara Higuera, Katheleen Gardiner, and Krzysztof Cios. Self-organizing feature maps identify proteins critical to learning mouse model of down syndrome. PloS one, 10:e0129122 29162, 06 2015.
[28] T. C. Hu and A. C. Tucker. Optimal computer search trees and variable-length alphabetical codes. SIAM Journal on Applied Mathematics, 21(4):514 532, December 1971.
[29] Johan Huysmans, Karel Dejaeger, Christophe Mues, Jan Vanthienen, and Bart Baesens. An empirical evaluation of the comprehensibility of decision table, tree and rule based predictive models. Decis. Support Syst., 51(1):141-154, 2011.
[30] Sangheum Hwang, Hyeon Gyu Yeo, and Jung-Sik Hong. new splitting criterion for better interpretable trees. IEEE Access, (66762-62774- 2020.
[31] Alexey Ignatiev, Filipe Pereira, Nina Narodytska, and João Marques-Silva. A sat-based approach to learn explainable decision sets. In Didier Galmiche, Stephan Schulz, and Roberto Sebastiani, editors, Automated Reasoning - 9th International Joint Conference, (IJCAR) 2018. Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK. July 14-17, 2018, Proceedings, volume 10900 of Lecture Notes in Computer Science pages
Springer, 2018
[32] Su Jia, Fatemeh Navidi, Ravi, et Optimal decision tree with noisy outcomes. Advances in neural information processing systems, 32, 2019.
[33] Colonna. Juan, Eduardo Nakamura, Marco Cristo, and Marcelo Gordo. Anuran Calls (MFCCs). UCI Machine Learning Repository, 2017.
12

---

[34] Murat Koklu and Iiker Ali Ozkan. Multiclass classification of dry beans using computer vision and machine learning techniques. Computers and Electronics in Agriculture. 174: 174:105507, 2020.
[35] S. Rao Kosaraju, Teresa M. Przytycka, and Ryan S. Borgstrom. On an optimal split tree problem. In Proceedings of the 6th International Workshop on Algorithms and Data Structures, WADS '99, pages 157-168, London, UK, 1999. Springer- Verlag.
[36] Eduardo Sany Laber and Loana Tito Nogueira. On the hardness of the minimum height decision tree problem. Discret. Appl. Math., 144(1-2):209-211 212, 2004.
[37] Himabindu Lakkaraju, Stephen H. Bach, and Jure Leskovec. Interpretable decision sets: A joint framework for description and prediction. In Balaji Krishnapuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi, editors, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 1675 1684. ACM, 2016.
[38]
Letter Recognition, UCI Machine Learning Repository, 1990.
[39] Ray Li, Percy Liang, and Stephen Mussmann. A tight analysis of greedy yields subexponential time approximation for uniform decision tree. In Shuchi Chawla, editor. Proceedings of the 2020 (CCM-IAAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 102-121. SIAM, 2020.
[40] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo I. Seltzer. Generalized and scalable optimal sparse decision trees. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6150-6160, PMLR, 2020.
[41] Zachary C. Lipton. The mythos of model interpretabilityy: In machine learning, the concept of interpretability both important and slippery. Queue, 16(3):11-57, jun 2018.
[42] R. J. Lyon, B. W. Stappers, S. Cooper, J. M. Brooke, and J. D. Knowles. Fifty years of pulsar candidate selection: from simple filters to new principled real-time classification approach. Monthly Notices of the Royal Astronomical Society, (1):1):
04 2016.
[43] Michael Mitzemmacher and Eli Upfal. Probability and computing: Randomization and
probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
[44] Fatemeh Navidi, Prabhanjan Kambadur, and Viswanath Nagarajan. Adaptive submodular
ranking and routing. Operations Research, 68(3):856-877, 2020.
[45] Hooda. Nishtha. Audit Data. UCI Machine Learning Repository, 2018.
[46] Rok Piltaver, Mitja Lustrek, Matjaz Gams, and Sanda Martincic-Ipsic. What makes classification trees comprehensible? Expert Syst. Appl., 62:333-346, -366, 2016.
[47] Hugo Manuel Proença and Matthijs van Leeuwen. Interpretable multiclass classification by mdl-based rule lists. Information Scieces, 512:1372-1393 2020.
[48] Ross Quinlan. C4.5: programs for machine learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993.
[49] Ananth R. Room occupancy estimation data set. Kaggle.
[50] Adel Rajab. Burst Header Packet (BHP) flooding attack on Optical Burst Switching (OBS) Network. UCI Machine Learning Repository, 2017.
[51] Oliver Roesler. EEG Eye State. UCI Machine Learning Repository, 2013.
[52] C. Okan Sakar, S. Polat, Mete Katircioglu, and Yomi Kastro. Real-time prediction of online shoppers' purchasing intention using multilayer perceptron and Istm recurrent neural networks. Neural Computing and Applications. 31, 10 2019.
13

---

[53] C. De Stefano, M. Maniaci, F. Fontanella, and A. Scotto di Freca. Reliable writer identification in medieval manuscripts through page layout features: The "avila" bible case. Engineering Applications of Artificial Intelligence, 72:99-110, 2018.
[54] Sebastian Tomezak. Polish companies bankruptcy data. UCI Machine Learning Repository, 2016.
[55] Joaguin Vanschoren. collins dataset. OpenML.
[56] Sicco Verwer and Yingqian Zhang. Learning optimal classification trees using binary linear program formulation. The Thirty-Third AAAI Conference on Artificial Intelligence, (AAAD. 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI
2019, Honolulu, Hawaii, USA, January 27 February 1, 2019, pages 1625 1625-1632. AAAI Press, 2019.
[57] I-Cheng Yeh and Che hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2, Part 1):2473-2480, 2009.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [No] We have not identified clear limitation of our work. That said, we will be happy discuss in revised version some potential limitation that the referees point to us.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All the proofs can be found in the supplementary material
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material supplementary material we include the url for our anonymous repository.
URL)? [Yes] In the
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] is explained in the experimental section.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] In the supplementary material we present boxplots for our experiments.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] We give the specification of the PC employed in our experiments in the supplementary material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We use public datasets, we are citing all of them
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "w5bHfYptqB", "reviewer": "Reviewer_9pFt", "summary": "This paper studies the interpretable decision tree by a metric called \"explanation size\", then presents some theoretical results about this size in relating to the tree depth in the average and worst cases.  The paper proposes a practical algorithm using adjusted Gini-index for tree splitting, based on a hyperparameter that differentiates whether using the existing split variable or using a new variable. Numerical experiments are conducted for multiple datasets. ", "questions": "1. For the example in Section 6,  FactorExpl  is set to be 0.97. In general, how this hyperparameter should be tuned? \n\n2. For the above hyperparameter, is there significant room to have better choices so that the explanation size drops more, while the performance may stay competitive or even better in generalization? \n\n3. How tight are the theoretical bounds in Section 4?\n ", "limitations": "The algorithm based on adjusted Gini-index seems to be a plausible approach, but the results as illustrated in Section 6 do not show significant lifting power. In Figure 2, when FactorExpl = 0.97, explanation size drops a bit dramatic, but performance also drops in a non-negligible way. It is desirable to see more convincing results with competitive performance. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. Interpretable decision tree has been an interesting topic, which is usually measured by the tree depth or the number of terminal nodes. Explanation size is a new interesting metric in measuring the splitting rule complexity. \n\n2. This paper presents some theoretical bounds in relating explanation size to tree depth in average and worst cases. But it is not clear how tight these bounds are. (They seem to be rather loose bounds).\n\n3. The authors propose a practical algorithm based on an adjusted Gini-index, which also sounds reasonable. It is desirable to see how effective such algorithm may construct the interpretable decision trees that are smaller explanation size while maintain competitive prediction performance. The numerical results on Section 6 are not very convincing in the performance comparison. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vyQLyeX7ITA", "reviewer": "Reviewer_Bn48", "summary": "The paper proposes explanation size as a novel measure to capture the interpretability of a decision tree. The explanation size of a leaf is defined as the number of distinct attributes occurring in nodes from the root to the leaf. This is an intuitively sensible notion, as it captures the size of the decision rule corresponding to the leaf. The metric is then lifted to whole trees by either considering the average or worst-case explanation size among all leafs.\n\nAs the first major contribution, the authors give a tight characterization of best possible guarantees achievable by a decision tree on the trade-off of simultaneously optimizing explanation size and the traditional criterion of tree depth. In particular, a theorem is given that states that for all datasets there are trees which have optimal explanation size and a depth within a factor of 2 of the optimal depth plus a logarithmic term in the sample size. This is complemented by a lower bound that shows that there are problem inputs for which depth and explanation size are different for all binary trees by a logarithmic factor in sample size. While not mentioned explicitly, these results seem to refer to trees that achieve zero classification error.\n\nMoreover, the authors present a greedy top-down tree induction algorithm called Short Explainable Rules (SER-DT) that aims to find minimum explanation size trees by using a novel splitting criterion called weighted pairwise misclassification. This algorithm guarantees an O(ln n) approximation for binary decision trees of approximately optimal average / worst-case explanation size and depth, and the experiments over 20 datasets indicate that the new algorithm is competitive with the commonly used CART algorithm. ", "questions": "Why is there no comparison between the proposed algorithm and algorithms from the literature that optimize depth? Given the demonstrated compatibility of small depth and small explanation size, this seems like a relevant baseline.\n \nWhat is the significance of the example weights in the problem definition? Most commonly, we consider unweighted prediction problems, which are equivalent to using constant weights. The theorem as given allows us to choose these constant weights arbitrarily small, in effect letting the log n term vanish. This seems counterintuitive.\n", "limitations": "Besides the above mentioned limitations in terms of comparison to other tree optimisation paradigms, there is also a lack of guarantees / discussion for the tradeoff between explanation size and accuracy – once such a tradeoff is allowed by considering, as usual, no perfect classification.\n", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The introduced explanation size is a simple, apparently useful, yet, to my knowledge, novel metric to measure the interpretability of decision trees. However, note that this notion is closely related to rule sizes (as in number of queries in a rule), which is considered in the rule learning literature, e.g.,\n* Ignatiev, Alexey, Filipe Pereira, Nina Narodytska, and Joao Marques-Silva. “A SAT-Based Approach to Learn Explainable Decision Sets.” In International Joint Conference on Automated Reasoning, 627–45. Springer, 2018.\n* Proença, Hugo M., and Matthijs van Leeuwen. “Interpretable Multiclass Classification by MDL-Based Rule Lists.” Information Sciences 512 (February 2020): 1372–93.\n* Probably has been considered in early rule learning work as well; I recommend checking the survey “Seperate-and-conquer Rule Learning” by Furnkranz for an overview of work from the 1990s.\n \nThe presented algorithm is simple yet shown theoretically and practically to achieve its goal. It would be useful though to discuss why the proposed splitting criterion based on reducing the number of discrepancy pairs leads to this result, as this as well as the other steps of the algorithm do not seem to directly relate to explanation size. In this context it would also be useful to discuss the relation to tree optimization that minimizes the total size of the tree (number of nodes), e.g.,\n\n* Bessiere, Christian, Emmanuel Hebrard, and Barry O’Sullivan. “Minimising Decision Tree Size as Combinatorial Optimisation.” In International Conference on Principles and Practice of Constraint Programming, 173–87. Springer, 2009.\n \nRelated to that, the empirical study, while overall showing good accuracy/explanation size trade-offs relative to CAR, does not contain a comparison with a method that directly optimizes depth, which seems relevant given the theoretical results of the paper, and the cited empirical work that assesses that depth is indicative of interpretability. A further caveat is that theoretical and empirical results might relate to different variants of the algorithm: the parameter FactrorExpl seems to not play a role in the theoretical analysis. However, it is tuned for the experiments.\n \nThis relates to the clarity of the presentation, which is overall good. However, there are some missing implicit definitions and assumptions. Most importantly, the underlying problem definition seems to assume that the resulting trees have to perfectly classify the given training data. This is a reasonable definition. However, it is different from the usual ML problem, in which either tree pruning or other forms of regularization are applied, allowing the returned tree to have non-zero classification error. See for example:\n\n* Hu, Xiyang, Cynthia Rudin, and Margo Seltzer. “Optimal Sparse Decision Trees.” In 33rd Conference on Neural Information Processing Systems, 9, 2019.\n \nWith this definition, it is also implicitly assumed that the there are perfectly classifying trees, which is not necessarily guaranteed in the usual statistical settings.\n \nOther minor issues the term “n” is used without definition (e.g., Theorem 1), and, as mentioned, the hyper-parameter “FactorExpl”, which seems to be introduced as an afterthought in the empirical section.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SJjCG9ZvYwq", "reviewer": "Reviewer_RMFa", "summary": "The paper introduces a metric for evaluating decision trees based on explanation size. Using this metric, The authors establish theoretical bounds on identifying trees with both optimal depth and explanation size, and develop an algorithm, SER-DT, for regularizing decision trees based on explanation size. The proposed algorithm shows improvement in reducing explanation while maintaining similar performance when compared to a competing method.\n", "questions": "* Why is there such high variance in accuracy results (Table 1) between SER-DT and CART? Why is the reported accuracy is higher for SER-DT than CART for a number of datasets (e.g. dry bean, eeg eye estate)? This seems to imply that regularizing for explanation length actually increases performance.\n* How was FactorExpl=0.97 chosen for the experiments? Are there any guidelines for selecting this parameter in practice?", "limitations": "Limitations have been adequately discussed in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n**Strengths:**\n* The proposed definition of explanation size is natural and intuitive. Decision trees are used in a number of applications for their interpretable properties; the proposed method improves on this interpretability and therefore could be of high interest to the community.\n* The paper has a good theoretical exploration of the tradeoff between tree depth and explanation size.\n\n**Weaknesses:**\n* Comparisons with Pruning algorithms. While the experiments include comparisons with CART, the paper could be improved by including comparisons with methods that reduce tree complexity, such as pruning.\n* High variance of results in Table 1 for test accuracy (see questions below). It would be beneficial if the authors could clarify these points. Error bars and/or significance testing in Table 1 would be helpful.\n\n**Miscellaneous Minor Issues / Suggestions:**\n* In table 1, it would be helpful to define what the bolded results indicate in the table caption.\n* Typo in Line 85: \"interpretabilty\"\n* Typo in Line 212: \"Explanaible\"\n* Typo in Line 302: \"intrepretability\"\n* Grammar in Line 303: \"upper and lower bound\"\n\n**Summary:**\nThe paper introduces a novel approach to improving decision tree interpretability. While the paper has room for improvement regarding experimental results and comparisons with pruning methods, the strong theoretical analysis makes me lean towards acceptance.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept