Succinct Explanations with Cascading Decision Trees
Authors: JIALU ZHANG
Mark Santolucito
Ruzica Piskac
Venue:  (2021)
Keywords: Decision Trees
Explainability
Interpretability

Abstract: Classic decision tree learning is a binary classification algorithm that constructs models with first-class transparency - every classification has a directly derivable explanation. However, learning decision trees on modern datasets generates large trees, which in turn generate decision paths of excessive depth, obscuring the explanation of classifications. To improve the comprehensibility of classifications, we propose a new decision tree model that we call Cascading Decision Trees. Cascading Decision Trees shorten the size of explanations of classifications, without sacrificing model performance overall. Our key insight is to separate the notion of a decision path and an explanation path. Utilizing this insight, instead of having one monolithic decision tree, we build several smaller decision subtrees and cascade them in sequence. Our cascading decision subtrees are designed to specifically target explanations for positive classifications. This way each subtree identifies the smallest set of features that can classify as many positive samples as possible, without misclassifying any negative samples. Applying cascading decision trees to new samples results in a significantly shorter and succinct explanation, if one of the subtrees detects a positive classification. In that case, we immediately stop and report the decision path of only the current subtree to the user as an explanation for the classification. We evaluate our algorithm on standard datasets, as well as new real-world applications and find that our model shortens the explanation depth by over 40.8\% for positive classifications compared to the classic decision tree model.


Under review as a conference paper at ICLR 2021
SUCCINCT EXPLANATIONS WITH CASCADING DECI- SION TREES
Anonymous authors Paper under double-blind review
ABSTRACT
Classic decision tree learning is binary classification algorithm that constructs models with first-class transparency every classification has a directly derivable explanation. However, learning decision trees modern datasets generates large trees, which in turn generate decision paths of excessive depth, obscuring the ex- planation of classifications. To improve the comprehensibility of classifications, we propose a new decision tree model that we call Cascading Decision Trees. Cascading Decision Trees shorten the size of explanations of classifications, with- out sacrificing model performance overall. Our key insight is to separate the no- tion of decision path and an explanation path. Utilizing this insight, instead of having one monolithic decision tree, we build several smaller decision subtrees and cascade them in sequence. Our cascading decision subtrees are designed specifically target explanations for positive classifications. This way each subtree identifies the smallest set of features that can classify as many positive samples possible, without misclassifying any negative samples. Applying cascading decision trees to new samples results in significantly shorter and succinet ex- planation, if one of the subtrees detects a positive classification. In that case, we immediately stop and report the decision path of only the current subtree to the explanation for the classification. We evaluate our algorithm standard datasets, as well as new real-world applications and find that our model shortens the explanation depth by over 40.8% for positive classifications compared the classic decision tree model.
INTRODUCTION
Binary classification is the process of classifying the given input set into two classes based on some classification criteria. Binary classification widely used in everyday life: for example, a typical application for binary classification is determining whether a patient has some disease by analyzing their comprehensive medical record. Existing work on binary classification mainly uses the accuracy of prediction as the main criterion for evaluating model performance. However, in order for model to be useful in real-world applications, it is imperative that users are able to understand and explain the logic underlying model predictions. Model comprehensibility!! in some real-world applications, especially in the medical and scientific domains, is of the utmost importance. In these cases, users need understand the classification model scientifically explain the reasons behind the classifi- cation or even rely on the model itself to discover the possible solution to the target problem.
It is difficult to provide explainability without sacrificing classification accuracy using current mod- els. "Black-bor box" models such as deep neural network, random forests, and ensembles of classifiers tend to have the highest accuracy in binary classification (Feitas (2014); Doilovi et al., (2018). How- ever, their opaque structure hinders understandability. making the logic behind the predictions diffi cult to trace. This lack of transparency may further discourage users from using the model Augasta & Kathirvalavakumar 2012); : Van Assche & Blockeel (2007).
Decision tree models, on the other hand, have transparent decision making steps. A traversal of features on the decision path from the root to the leaf node is presented to users as rule. Therefore, compared to other models, the decision tree model has historically been characterized as having
In this paper, comprehensibility and interpretability are used interchangeably.

---

Under review as a conference paper at ICLR 2021
high comprchensibility Freitas (2014); Doilovi et al. (2018) However, whether models generated by classic decision trees provide enough comprehensibility has been challenged: "decision trees
[...] can grow so large that no human understand them verify their correctness" Caruana et al. 1999), or they may contain subtrees with redundant attribute conditions, resulting in potential misinterpretation of the root cause for model predictions Freitas) (2014).
The work presented in this paper introduces an algorithm for deriving succinct explanations for positive classifications, while maintaining the overall prediction accuracy. To this end, we introduce a novel cascading decision tree model. A cascading decision tree is a sequence of several smaller decision trees (subtrees) with the predefined tree depth. After every subtree sequentially follows another subtree. mimicking in this way a cascading waterfall, thus the name. The sequence ends when the subtree does not contain any leaves describing positively classified samples. Fig. Fig.Zdepp depicts one such cascading decision tree.
The main idea behind cascading decision trees that, while most algorithms for constructing deci- sion trees are greedy and they try to classify many samples soon as possible, such classification results in large explanation paths for the samples in the lower levels of the tree. Instead, we construct subtree of the predefined depth. That subtree contains a short explanation for the samples it man- aged to classify. However, the subtree with a short depth will misclassify samples. We next repeat the process the training set with the samples that were previously classified positively removed. This way, the samples classified as positive in the second subtree will have a much shorter expla- nation path than they would in the original decision tree. In the cascading decision tree model, an explanation path for positively classified sample is the path that starts in the root of the corresponding subtree.
We target explanations for only positive classifications, based on real-world motivation. In the medical domain, positive classification result indicates that a person has the disease for which the test is being done NIH (2020). The positive classification is also combined with additional testings needed for a full diagnosis CDC (2020). Note that, if practical application arises, our cascading decision trees model could easily be changed to target the negative classifications.
Reducing the size and the depth of a decision tree to improve comprehensibility has been studied, both from theoretical and practical perspective. However, constructing such optimally small decision trees is an NP-complete problem HHyfill & Rivest (1976), and the main drawback of these approaches is that the model is computationally too expensive to train. Even when using the state- of-the-art libraries Aglin et al. (2020); Verwer & Zhang (209)). we observed that complexity. To illustrate this on example, to Iearn model on the lonosphere dataset (from the UCI Machine Learning Repository), the BinOCT tool needs approximately 10 minutes, while our approach com- pletes this task in 1.1 seconds.
We demonstrate the applicability of the cascading decision tree model in two ways. First, we use our model to perform standard binary classification on three numerical datasets from the UCI Machine Learning Repository. Second, we apply our model to a new application of binary classification, namely continuous integration (CI) build status prediction (Santolucito et al. (2018). Overall, report that compared to the classical decision tree algorithm, our approach shortens the explanation depth for positive classifications by more than 40.8% while maintaining the prediction accuracy.
2 MOTIVATING EXAMPLES
In this section we demonstrate how cascading decision trees can generate shorter and more succinet explanation.
The following simple synthetic example is contrived to illustrate our tool's 's basic functionality. Given the dataset in T classical decision tree will construct model shown in Fig. [ Using the same dataset, our cascading decision trees algorithm generates a model with three subtrees in shown in Fig. 2 Let's assume that there is new sample, ''Samplel1,, with the feature vector (F, F, F, T). Both models classify "Sample 11 1" with the same prediction result, "Positive". However, the expla- nations extracted from these two models are different.
In the classic decision tree model (Fig. D. "Sample 1" falls into node (9). Thus, the explanation path here is "Feature1 F", "Feature2 F and "Feature3 F", with the explanation depth of three.
2

---

Under review as a conference paper at ICLR 2021
Table 1: Synthetic Dataset for Binary Classification.
Featurel
Feature2
Feature.3
Feature4
Label
Sample1
Positive
Sample2
Positive
Sample3
F
Positive
Sample4
T
F
Positive
Sumple5
F
F
T
Positive
Sumple6
F
T
F
Positive
Sample7
T
F
F
Negative
Sample8
F
F
Negative
Sample9
F
T
F
Negative
SampleI0
F
F
Negative
(I) Featunel
(2) Fealure2
(3) Featurc3
True
True
Fabs
Folse
(5) $1
S7)
(7) $8.59
(4) Frature2
True
False
$6,510
Figure I: An example of full classic decision on dataset given in Table with green boxes as Positive nodes, red boxes as Negative nodes, and gray boxes as Mixed nodes.
(1) Featurel
Halse
(2) Feature2
(3) Feature3
True
True
False
False
(4) $1.52.$3.54
S7
(6) $8,59
$5,56,510
(8) Featured
True
False
(10) S5
Feature3
True
False
88.59
86,87.100
(13) Fenture3
True
False
Fenturel
True
False
(16)
(17) $6,510
Figure 2:
An example of Cascading Decision Trees on dataset given in Table] with maximum depth of three in each subtree.
Using the cascading decision tree model (Fig. "Sample11" 1" first falls into node (7) in the first subtree. Node (7) is not classifying positive samples, "Samplel1" is passed to the second subtree and eventually falls into node (10). This way, the explanation path Saampllllll 1" is "Feature4 T"., with explanation depth of only one.
3

---

Under review as a conference paper at ICLR 2021
3 RELATED WORK
The cascading decision trees algorithm pursues a different goal than existing ensemble methods, such Bagging [Breiman| (199)) and Boosting [Schapire| (9900). Ensemble methods for decision trees combine multiple weaker classifiers into a larger classifier with the goal of increasing overall accuracy, while cascading decision trees focus on shortening explanations. Bagging divides the dataset into multiple, smaller datasets, generates the classifier for each dataset and produces the final classification via a voting process. Boosting algorithms iteratively learn weak classifiers, gives them weights, and adds them one after another to generate final strong classifier. The combination strategies of these ensemble methods obfuscate the traceability of a classic decision tree, which is the source of simple explanations for classifications Zhao & Sudha Ram (2004). The limited model comprehensibility of Bagging and Boosting is also shared by other ensemble methods, which makes their output difficult to interpret.
Ensemble Methods.
Oblique Decision Trees. Oblique decision trees Murthy et al. (1994) extend the classic decision tree model by allowing each decision node to combine checks against multiple features. This series of work contains a rich family of models such as multivariate decision trees Brodley & Utgoff (1995), loose and tight coupling Gama& & Brazdil (2000), and constrained cascade generalization of decision trees ZZhoo & Sudha Ram (2004). However, compared to cascading decision trees, this oblique design is not only the training stage computationally expensive [ee & Jaakkola (2020), but also makes the explaining a classification in the decision-making stage opaque and hard to interpret
& Sudha Ram (2004).
Optimal Decision Trees. Optimal decision tree algorithms learn models with the optimal prediction
accuracy under the constraints of the predefined depth of the tree. However, learning an fixed depth optimal decision tree without heuristics is an NP-complete problem [Hyafil & Rivest (1776). The main drawback of using this approach in practice is that the model is too computationally ly expensive to train. For example, the state-of-the -frt-e-rrttt-tttoo optimal decision trees implementations Aglln et al. (2020);
Verwer& & Zhang (2019) need ten minutes to train the ionosphere datase On the same dataset, we show in our evaluation (Sec. 5) that our cascading decision trees learning process terminated in seconds with competitive accuracy (ef. Verwer & Zhang (2019)). In addition, instead of being a direct competitor, optimal decision tree learner could be used as the base decision tree inducer in our algorithm to potentially improve the prediction accuracy, though at the cost of training time.
Model Interpretability. The comprehensibility of classification models, including decision tree models, has been extensively explored Doilovi et al.] (2018). Specifically, Quinlan| (987) demon- strated that small models are more interpretable than larger ones in the decision tree. Similarly, Huysmans et al. (201T) ran a user study to illustrate that larger representations result in a decrease in both the accuracy of user's 's answers and users confidence in the model itself. This work supports the motivation that minimizing explanations is a valuable direction to explore.
4 METHODOLOGY
Formalism. For interpretability, we take inspiration from the LIME system Ribeiro et al. (2016) which states that interpretable explanations should "provide qualitative understanding between joint values of input variables and the resulting predicted response value". In our work, we specifically focus on binary classification, and only target explanations for positive classifications. An explana- tion in our system should capture the essence of the positive classification. That is, the explanation identifies the key input values that contributed to the positive classification. The classification should still be the same, no matter the state of the input values not included in the explanation. It is possi- ble the sample will be classified positively in different way, but as long as the input values in the explanation are unchanged, the classification will still be positive.
To define a valid explanation, we consider dataset of samples with binary labels. Without loss of generality (as we consider only the decision tree setting), let (x. (2", C.) denote sample as an n-dimensional Boolean vector and its ground-truit truth classification respectively. The number of classes is |C| in our application we consider only binary classification, where |C| = 2, though
4

---

Under review as a conference paper at ICLR 2021
the definition of valid explanations generalizes to larger |C]. Given test set T {(x, y)}. we can learn a model M 2" + C which maps imput vectors of samples to a classification. An explanatory model, M 2 + E expands upon the model M additionally map input vectors to explanations, E. An explantation & : 2 is a Boolean vector, where every true element means that the feature at the corresponding index in the input vector is necessary part of the classification result. The size of an explanation, |&| Eien. E[i]. is the number of true elements in the explanation vector.
We define the validity of an explanation via array multiplication. An explanation, &, is valid over an input vector x, when any part of the input vector not captured by the explanation may be modified without changing the classification result of the model.
isV Valid(E, x) + Vz E 2". (x) = (E x + +
Example 1 A trivial explanation is always available for any sample- the explanation that every ele- ment of the sample vector is important. From Fig. for input vector "Sample5", a valid explanation is E [1,1, 1, This means that as long as no features change, the classification remains the same.
Example 2 In general, shorter explanation can be extracted from classic decision trees. As an example, the explanation of "Sample5" from the decision tree in Fig. Tis the explanation that keeps only the elements in the decision path of the tree: & = [1, 1, 1, This is the commonly accepted approach to explanations of decision tree classifications.
Example 3 An even shorter explanation is possible with cascading decision trees. Looking again to "Sample5" as classified by the cascading decision tree in Fig. 2 valid explanation keeps only "Feature 4" - & [0, O, 0, 1]. Although changes to "Feature 1-3" may change the decision path, the classification remains the same as long as "Feature 4" unchanged.
A explanatory model is valid if and only if the provided explanation is valid for all possible inputs, that is: Vr E 2". isV alid( (M*(()++++)))))))) (z). We note that a valid explanatory model only needs to correctly explain its classifications for all inputs not correctly classify all inputs.
The above definition a valid explanation is always true of the decision path of a classic decision tree. This aligns with the notion that the decision path of a classification in classic decision tree is a valid explanation for the resultant classification of a sample. As we will show, this definition of valid explanation is also always true of the shortened "explanation path" propose with our cascading decision trees. Cascading decision trees provide explanations only over samples classified as positive, though the definition is more general.
Building Cascading Decision Trees. The cascading decision trees algorithm is described through pseudocode in Algorithm|] I Our insight in the training process it is the goal of each cascading decision subtree to identify the smallest set of features that can classify as many Positive samples as possible, without misclassifying any Negative ive samples. Specifically, the procedure Fit builds classic decision tree, cl f, our training set, TR and adds it to the cascading tree list initially this list is empty. For every leaf node we compute the mi mixed value, which is the percentage of samples from TR classified by this leaf node that are also Pos i live samples. Positive nodes are leaf nodes with a mi xed value greater than the threshold (we use 80% in this paper). If clf has no Posi insitti t ve nodes, it means we have learned sufficiently good classifier and we stop (Line 11). Otherwise, we first remove samples truly classified by Pos it viee nodes in this elf from TR, and then obtain new TR to use in the next iteration of the loop (Line 14).
Our cascading decision trees a presented here has no pruning phase. However, our al- gorithm is generic enough to be combined with any pruning techniques Esposito et al. (1997) and different goodness measurement for decision nodes split, such as entropy Shannon (1948) and gini impurity Havrda et al.) (1967).
The time complexity of cascading decision tree algorithm is bounded by the size of the training set. Suppose the training time for building classic decision trees is function of the number of the training samples, n and the number of features k. We use the decision tree module in scikit-learr as our base classic decision tree inducer, which is built upon the CART Breiman et al. (1984) method. Since features are recursively reused in every decision node based on numerical splitting criterion,
5

---

Under review as a conference paper at ICLR 2021
Algorithm Build Cascading Decision Trees Classifier
Input:
TR :Laabeledd Training Set
Input: 0 ::Threshold
Input: depth :Maximum depth of each decision subtree
Output: cascadingT :A list of cascading decision subtrees
1: procedure FIT(TR, 0, depth)
2: done = False
3: rascadingI
4: while done F False do
5: c =l==caasiDeccisiooTTee.iiii depth)
6:
cascodiing/ree..ppenndll/
7:
done True
8:
for leaf.N ode in fl do
9:
(miiee((eea] Node) >= 0) then
10:
done = False
11:
(done = True) then
12:
Break
13:
else
14:
TR filter (clf-predice pre.icc(ssmppplle..... 0) Positive, TR) return eascading ree
depth of the decision tree bounded by the number the training samples n in our model. Therefore, the time complexity for building one base decision tree is bounded by (n)
According our cascading decision trees algorithn[] after building one decision subtree, sam- ples that are classified True Positive are removed from the next round of decision sub- tree construction. In the worst case, every time, only one True Positive classified in the current decision tree. The time complexity for building the next cascading decision subtree is in (())-))kk) Therefore, the overall cascading decision trees training time T is bounded by: - k²k O (f (0 = (nn*k).
Testing Cascading Decision Trees. Our cascading decision trees testing process is described in Algorithm 2 In the procedure Test, we run all decision trees sequentially, and we report the decision path of that tree only as our explanation path.
Algorithm 2 Test Cascading Decision Trees Classifier
Input: cascadingTree :A list of cascading decision tree classfier
Input: 0 :Threshold
Output: Prediction Result: boolean variable, Postive or Negative.
Output: Explanation Paths: A conjunction of boolean statements explain the decisions.
procedure TESTT(eascadingITree ree 2: for f in cascading'l ree do
3:
if cl clf-predict (sample, 0) = Posétive then
4:
return (Postive, fl path(sample)) return (Negative)
EVALUATION
This section aims to evaluate the cascading decision trees algorithm by answering the following questions: (1) compared to the classic decision trees algorithm, what is the percentage explanation depth for positive classifications that has been shortened by using cascading decision trees? (2) what the prediction accuracy and the turn-around efficiency of cascading decision trees algorithm? (3) how well does cascading decision trees algorithm perform in real-world edge application such as continuous integration (CI) build status prediction? All experiments were conducted on a MacBook Pro with 2.5 GHz Intel i7 processor with 16GB of RAM.

---

Under review as a conference paper at ICLR 2021
5.1 EMPIRICAL EVALUATION
To empirically evaluate the explainability and accuracy of the cascading decision trees algorithm, we collect three datasets from UCI machine learning repositoried as our benchmark set. The UCI ma- chine learning datasets are standard benchmarks for comparing the performance of tree-based classi- fication methods. We select these three binary classification datasets out of the UCI datasets Zhao & Sudha Ram (2004). We select only the binary classification tasks, as our method provides expla- nations for positive classifications. While our method could be applied to multiclass classification, the user must pick class to focus on creating succinet explanations, which is not clear from the UCI datasets. Additionally, we select only the datasets with exclusively numeric features, as the underlying library, sccikit-lear of our implementation is limited in this respect.
Each of the three UCI datasets reflect tasks clearly benefit from more succinct explanations for positive predictions. They are:
1. Classification of breast cancer. "Positive" samples mean the tumor turns out to be malig- nant, while "Negative" samples are benign.
2. Detection free electrons in the ionosphere. "Positive" samples show the detecting signals fail to detect the free electrons; the signals just pass through the ionosphere. "Negative" samples show some evidence of the stucture in the ionosphere.
3. Discrimination of objects. This dataset includes bouncing sonar signals off a mine (metal cylinder) at various angles and under various conditions. "Positive" samples indicate the object is indeed rock not mine, while "Negative" samples indicate the object is mine.
We compare the performance of the proposed cascading decision trees algorithm to the performance of the classic decision trees algorithm with various bounds on the depth of the learned tree. We quantify algorithm performance using five-fold cross validation, and randomly shuffle the datasets. The maximum depth of the cascading decision trees algorithm uniformly set to three in all tests. The threshold in cascading decision trees algorithm is set to a fixed number 0.8.
Explainability. The shorter explanation, the more comprehensible that explanation is to users Quinlan (1987); [Huysmans et al.] (20TT); Pazzani] (2000). The ability to clearly explain the output of machine learning models is critical to their acceptance and use in practice, an idea sum- marize by Huysmans et al. (2011) "Larger representations result in a decrease in user's 's answer accuracy and decrease in user's confidence to the model."
Table 2: Average Explanation Depth of Postive Classifications from Cascading Decision Trees and Classical Decision Trees.
Dataset
Classical Decision Trees
Cascading Decision Trees
Improvement
Breast cancer
2.688
1,991
25.1%
Jonosphere
2.694
1.418
47.4%
Sonar
3.813
1.943
49.0%
Table 2 shows the comparison of the average explanation depth of model generated by cascading decision trees and classic decision trees. Our cascading decision trees algorithm shortens the ex- plainable paths to users by 40.8% on average among three datasets. The average representation size of our cascading decision trees model is 1.78 among three datasets. We specifically focus on the explanations for positive classifications. This means on average, only 1.78 features are necessary for the classification of a positive sample in cascading decision trees. However, for classical decision trees, 3.06 features are necessary for the classification of positive sample. This succinetness of the explanation of positive predictions enhances qualitative understanding to users, which could be used to diagnose the medical causals and back up the scientific hypothesis.
Accuracy. Table 3 shows the breakdown empirical evaluation of cascading decision trees. In two out of three datasets, our cascading decision tree surprisingly outperforms the base classic decision trees in prediction accuracy.
'htt:///rcchiee. ics res.uci.cdee cddu/m///ndex..ppp
'The decision trees module in scikit-learn is also used as the implementation for the classic decision trees algorithm our evaluation.
7

---

Under review as a conference paper at ICLR 2021
Table 3: Breakdown Evaluation of Cascading Decision Trees on Three Classic UCI datasets.
Datase:
Cascadine
Explanation Depth
Aecunacy
Runtine (s)
TP
TN
FP
FN
Precision
Recall
F- Scone
On
1.991
95.514
1,899
56.8
698
18
5A6
95.42%
96.57%
90.54%
Breast concer
2,58
39.4
MQ.477
Off (nove depth =
2
91.408
0.067
54.8
69.4
222
7.6
91.584
82.00%
K7.596
0n
1418
88.75%
1.108
20/4
89,28%
90,555
84.37%
loasophere
2,644
85.92%
0.000
20.0
41.0
81.77%
80.16%
Off (nore Jlish =
14K1
64.2%%
0.01
158
44.0
1.6
9.6
12.454
60.57%
73,076
1943
122
78,636
55.92%
62,46%
Sonur
1311
16.299
0003
17.4
138
6.0
1444
76.99%
Off (max..eeth
2654
06.71%
0.09
11.0
16.0
32
11.2
79.75%
504426
00.32
To lower the explanation path of the decision trees model, one common technique is to the maximum depth to a classic decision trees classifier. However, compared with the cascading decision trees, setting the maximum depth three incurs a decrease in average prediction accuracy by around 4.0%. Even with this max depth and lower accuracy, in all three datasets, the average explanation path is still longer than cascading decision trees algorithm.
In conclusion, compared with the classical decision trees model both with and without a fixed depth, our cascading decision trees algorithm delivers better model comprehensibility via significantly shorter explanation depth while maintaining high prediction accuracy.
Low False-positive Rate. In addition better model comprehensibility, the cascading decision trees model has another key advantage, which is the low false-positive rate in prediction. In medical and scientific domains, explanations behind positive classification results are often more useful than explanations behind the negatives. For example, in the medical domain if the prediction result is positive, the doctor needs to justify the accurate reasons behind the diagnosis of the disease and then report them to patients. A high possi-oosiivee rate not only greatly reduces physicians' confidence in adopting the prediction result but also leads to unnecessary and invasive follow-up tests on pa- tients HNR 2020). Therefore, it is crucial to have a competitive accuracy prediction model with very low false- lelst--ooiiive rate. As shown in Table the cascading decision trees algorithm has the lowest false positive (FP) rate for all three datasets compared to the classical decision trees algorithm.
Turn-around Efficiency. Although this paper does not focus on building fast classifier, the turn- around efficiency of our cascading decision trees algorithm turns out to be great in practice. The training process finishes in seconds in all three real-world UCI datasets. Taking the ionosphere dataset example, our cascading decision trees learning process terminates in 1.1 seconds with accuracy of 88.7%. This is comparable to accuracy of 87.0% the state-of-thh-aar optimal decision trees algorithm BioOCT when depth of the tree three (cf. Verwer & Zhang (019)). However, BioOCT takes around ten minutes to train.
apply the cascading decision trees for predicting the build status in the continuous integration (CI) environment Gousios et al. (2014). Notifying that the attempt build the project might fail, could save software engineers countless hours. We ran a study (link omitted for anonymity) where we learn how to classify po- tential build failures. The evaluation results demonstrate that cascading decision trees provides a shorter explanation, with competitive prediction accuracy of 90.55%. Moreover, the ratio of the average number of false positives reports to the average number of correct classifications only 1.8% Our study shows that the use of cascading decision trees provides developers with a more succinet but comprehensible set of rules that are responsible for positive classifications.
Real-world Application. The second part of evaluation
CONCLUSIONS
Learning decision trees on modern datasets generates large trees, which in turn produce decision paths of excessive depth, obscuring the explanation of classifications. This paper intends to maxi- mize model comprehensibility while maintaining prediction accuracy in binary classification. The cascading decision trees algorithm has been proposed to provide more succinet explanations in bi- nary decision trees. We evaluated our algorithm in real-world medical, scientific and program anal- ysis datasets, where the explainability of the positive test result is of the utmost importance. Our cascading decision trees algorithm shortens the explanation depth by over 40.8% for positive classi- fications compared to the classic decision trees algorithm.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
CDC:
https: www. cdc. http://www....//////asss.ssos/ hiv- ttssting/pssstiveee heieeee-ii---e Sev-results... pwt.ultss.tmmm..mmm October 2020.
Understanding Positive
Result.
Understanding medical tests: sensitivity, specificity, and positive predictive value. Article is avail-
able at http::/wwww.ealthewwseeeeweeee
with shortened URL at:
5tlvwf October 2020.
National
Cancer
institute Dictionary of Cancer Terms.
https://www.
cancer cancer. htwp::/.wgo/ppbblcaaiioooooo htw.://aaaiinn/iitiioaaaaaaaaaoe /iwtiiiaiiiiiesseeeeeeeemes www.ec/innareessaneeettteee cancer-terms deff
positivv--est--esuule
October 2020.
Gaäl Aglin, Siegfried Nijssen, and Pierre Schaus. Learning optimal decision trees using caching branch-and-boun search. The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New
York, NY, USA, February 7-12, 2020, pp. 3146-3153, AAAI Press, 2020. URL https://
baai.org/ojs//noeee
M. Gethsiyal Augasta and Kathirvalavakumar. Reverse engineering the neural networks for rule extraction in classification problems. Neural Processing Letters, 35(2):131 1500100 2012.
Leo Breiman. Bagging predictors. Machine Learning, 24(2):123-144 1996.
Leo Breiman, Jerome Friedman, Richard A Olshen, and Charles J Stone. Classification and regression trees. Monterey, CA, 1984.
Carla E. Brodley and Paul Utgoff. Multivariate decision trees. Machine Learning, 19(1):45-77, 1995. ISSN 1076-9757.
Rich Caruana, Hooshang Kangarloo, JD Dionisio, Usha Sinha, and David Johnson. Case-based explanation of non-case-basse based learning methods. In Proceedings of the AMIA Symposium, pp- 212. American Medical Informatics Association, 1999.
F. K. Doilovi, M. Bri, and N. Hlupi. Explainable artificial intelligence: A survey. In 2018 41st International Convention on Information and Communication Technology, Electronics and Mi- croelectronics (MIPRO), pp. 0210-0215, 2018.
Esposito, D. Malerba, Semeraro, and Kay. A comparative analysis of methods for pruning decision trees. IEEE Transactions Pattern Analysis and Machine Intelligence, 19(5):476 491, 1997.
Alex A. Freitas. Comprehensible classification models: A position paper. SIGKDD Explor. Newsl, 15(1):110, March 2014. ISSN 1931-0145. doi: 10. 10.1145/25044332559447.
URL https:
//doi.org/// /10 0145/2594477 2594475
Joo Gama and Pavel Brazdil. Cascade generalization. Machine Learning, 41(3):315-344 2000.
Georgios Gousios, Martin Pinzger, and Arie van Deursen. An exploratory study of the pull-based software development model. ICSE 2014. Association for Computing Machinery, 2014. ISBN 9781450327565.
Jan Havrda, Frantiek Charvt, Jan Havrda, and Frantisek Charvt, Quantification method of classifi- cation processes: Concept structural a-entropy. Kybernetika, 1967.
Johan Huysmans, Karel Dejaeger, Christophe Mues, Jan Vanthienen, and Bart Baesens. An em- pirical evaluation the comprehensibility of decision table, tree and rule based predictive models. Decision Support Systems, 51(1):141 154, 2011. ISSN 0167-9236. doi: https://
dbt.oog/10.1001,,,ss0000....... URL http://wwwwwcciieiiieeeee... http://wwww..eee...coooooooceeee ctt.sc/eeccc/ce/////coommo r

---

Under review as a conference paper at ICLR 2021
Laurent Hyafil and Ronald L. Rivest. Constructing optimal binary decision trees is np-compeete.
Information Processing Letters, 5(1):15 - 17. 1976. ISSN 0020-0190. doi: https://oii.on org/ 10.10166002000119076999999999999 articlle/p1/002200 907690009999999
URL http://wwt
Maximilian Junker, Ralf Huuck, Ansgar Fehnker, and Alexander Knapp. Smt-based false posi- tive elimination in static program analysis. In International Conference on Formal Engineering Methods, pp. 316-331. Springer. 2012.
Guang-He Lee and Tommi S. Jaakkola. Oblique decision trees from derivatives of relu networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababu, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL Bke8UR4FPB
net forum?id-
Sreerama K. Murthy, Simon Kasif, and Steven Salzberg. A system for induction of oblique decision trees. J. Artif. Int. Res,, 2(1):132, August 1994, ISSN 1076-9757.
M. J. Pazzani. Knowledge discovery from data? IEEE Intelligent Systems and their Applications, 15(2):10-12, 2000.
J.R. Quinlan. Simplifying decision trees. International Journal of Man-Machine Studies, 27(3):221 - 234, 1987. ISSN 0020-7373. doi: https:/6ciooo///0006655502227223 80053-6. URL http: wwtp://wwwww..oo www. htt.://weeeeeeeeeccc///////eeeea
SS0207333878005388
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. why should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135-1144 2016.
Mark Santolucito, Jialu Zhang, Ennan Zhai, and Ruzica Piskac. Statically verifying continuous integration configurations, 2018.
Robert E. Schapire. The strength of weak learnability. Mach. Learn,, 5(2):197-277, July 1990. ISSN 0885-6125. doi: 10.1023/A:10226488800 102244800770)
URI httpt:t/////....... http://///ooooo///.//.// org/10. 1023/A:
C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27 (3):379-4233 1948.
Anneleen Van Assche and Hendrik Blockeel. Seeing the forest through the trees: Learning a compre- hensible model from an ensemble. In Joost N. Kok, Jacek Koronacki, Raomon Lopez de Mantaras, Stan Matwin, Dunja Mladenič, and Andrzej Skowron (eds.), Machine Learning: ECML 2007, pp- 418 429, Berlin, Heidelberg. 2007. Springer Berlin Heidelberg. ISBN 978 378-3-540-74958-5.
Sicco Verwer and Yingqian Zhang. Learning optimal classification trees using a binary linear pro- gram formulation. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-Fira Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposiun on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA. January 27 February 2019. pp. 1625 1632, AAAI Press, 2019. doi: 10. doi http://ooo.ooogooo/////oo / 160 aaai v331 01. 3301 1800016660 62.4
aaai.v33i01.2 333001133111110 1624. URL
Xi Wang, Nickolai Zeldovich, M. Frans Kaashoek, and Armando Solar-Lezama. Towards optimization safe systems: Analyzing the impact of undefined behavior. In Proceedings of the Twenty-Fout Fourth ACM Symposium Operating Systems Principles, SOSP '13, pp. 260275, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450323888. 10. 10.1145/2517349.25555
doi: URL htw.::ttsss..mmmm /ttttps://di..ooo org. 1tt.:/1..11111// 1145/251 732112227792
H. Zhao and Sudha Ram. Constrained cascade generalization of decision trees. IEEE Transactions on Knowledge and Data Engineering, 16(6):727-739, 2004.
10

---

Under review as a conference paper at ICLR 2021
A APPENDIX
Real-world Application. Encouraged by the prior results from our empirical study, we conduct our second part of our evaluation by using our cascading decision trees algorithm in novel real-world application, continuous integration (CI) build status prediction.
In CI environment, developers upload their code one commit, and CI starts to build and tests users' code when they finish their uploading. Feedback from the positive CI build status enables developers quickly locate and troubleshoot errors in the code, expediting the software development cycle. However, one major drawback of CI is that a CI build attempt can be extremely time consuming, and can even take longer than day Santolucito al. (2018). discouraging the usage of CI itself. Previous work (Santolucito et al. (2018) used the historical data stored in the CI environment to predict the CI build status and report the root causes behind the failures to users.
We choose this dataset because it is an ideal testbed for our cascading decision trees algorithm, bi- nary classification task on all numerical features. As opposed to other common source of program- ming error such as buffer overflow, divide by zero and so on Wang et al. (2013), CI build failure is mainly caused by library version inconsistency. Therefore, all features extracted in this dataset are numerical, and result, is amenable to analysis by our algorithm. Moreover, in program analysis domain, a very low false-positive rate is crucial for user acceptance of the tool Junker et al. (2012).
Table 4: Breakdown Evaluation of Cascading Decision Trees on CI Build Status Prediction.
Caseading
Explanation Depth
Accuracy
Runtime (6)
TF
IN
FF
EN
Precision
Recall 58.20%
F- Score
ON
2
90.55%
249.43
135
66.50%
OFF
2311
90.30%
277.95
135
1427
66.18%
38.70%
62.2%%
Table 4 shows the breakdown evaluation of using cascading decision trees on CI build status pre- diction. The strategy we employ in the evaluation is the following; for a repository with total historical commits, we build our model with n//2 commits, and use that model to evaluate commit (n/2) 1. We then rebuild the model with training set of (n/2) + commits and used that incremental model to predict the status of the next coming commit. Using this approach, we find that cascading decision tree classifier can predict build status with an overall accuracy of 90.55% which is almost the same the accuracy of 90.50% if using only classic decision tree classifier. However, in addition to competitive prediction accuracy, cascading decision tree shortens the ex- planation depth for failed builds by 5.6%. This could help developers identify error locations more quickly and shorten the software development cycle.
In addition, our evaluation results show that the ratio of the average number of false positive reports to the average number of correct classifications is only 1.8% (FP/TP+TN). In conclusion, the use of cascading decision trees provides developers with more succinct but comprehensible set of rules that are responsible for positive classifications. This allows developers to more accurately and confidently troubleshoot the CI build failure.


Reviews:
[{"review_id": "kivlhk3kuY", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors presented in this submission a nice novel idea of building a tree ensemble in a cascading style so that any positive predictions are decided and explained by the first tree predicting them positively. The reviewer finds this idea very interesting and clearly elaborated in this paper. However, more theoretical and empirical justification is crucially necessary in order to make the claims in the submission convincing. The issues listed here are some questions that the reviewer believes should have been discussed or answered in the paper.\n\nMajor issues:\n \nDespite the fact that the focus of cascading decision trees (CDTs) is a short explanatory path, my major concern here is that it is very hard to justify them as a proper statistical model. \n\n1.\nPractically,  there are very simple adversarial cases that the cascading decision trees will fail to build. Consider this example that X ~ Unif([0,1]^2) and Y|X == 1 if X \\in [1/3, 2/3]^2 otherwise 0. If we apply the algorithm in the paper, using depth=2 trees and a mixed node threshold theta = 0.5 (which I believe are a reasonable choice), the positive-focused CDTs will almost fail to construct the first tree with a decently large sample, let alone the cascading subsequence. On the other hand, since depth=2 trees can cover all rectangles (0,0) - (a,b) \\in R^2,  the counterpart random forests or GBDTs are universal approximators. \n\nBy also checking the negative predictions there might be ways to mitigate this issue. However relevant discussions are lacking in this paper in its current shape. \n\nFrom a more abstract perspective regarding the CDTs depth: in a d-dim sample space, to separate out a d-dim cube, we are likely in the need of 2d splits. There might be fewer splits needed when the cube is touching the boundary of the support or there are other nodes made before as in an ensemble. But in general we should not make such assumptions, and it would be better if we could have more discussions in the paper. \n\n2\nClassic classification trees are asymptotically bayesian classifiers, whereas we can imagine asymptotically CDTs assign the positive label to a region only when the true positive rate theta* within the region is larger than the constant threshold theta, which means CDTs are intrinsically inaccurate - more specifically, low recall as mentioned by the authors. This situation is further worsened as CDTs will take positive examples off from the sample. The fact that CDTs are theoretically incapable of finding all positive examples is harming their credibility of giving short explanations to positive predictions. A bandage here might be to use adaptive thresholds, but no discussions are currently present in the submission.\n\nMinor issues:\n\n1. Classic CARTs are very sensitive towards outliers. The \"split one example out each time\" scenario being analyzed in the paper is likely to cause overfitting, chasing the outliers, and instability. It should be avoided. \n2. CARTs default greedy building algorithm uses entropy or Gini index which are indifferent towards both positive and negative examples. Since the focus in the paper is on positive predictions, it is worth discussing how the algorithm should be changed accordingly.\n3. It would be better if there were instructions in the paper regarding choosing the mixed node threshold theta, the tree depth, and hopefully the ensemble size. \n4. Since CDTs are still a tree ensemble, their capacity is expected to be larger than a single decision tree which can even be a bit deeper. The results pertaining to the accuracy, precision and recall in the empirical study session are therefore slightly unfair comparison - it would be better to benchmark against decision tree ensembles or rule-based models [1]. \n\n[1] Wang, Fulton, and Cynthia Rudin. \"Falling rule lists.\" Artificial Intelligence and Statistics. 2015.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "O98YplCR3ne", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "*Summary*\nThis paper introduces the Cascading Decision Tree, a novel variant of decision trees with permits to extract short explanations for a class of interest. The idea is to realize a cascade of small decision trees: at a certain level, the tree is built using all points except the positive ones correctly classified by trees in previous levels. The method has been tested using three standard datasets and a novel application.\n\n*Positive points*\n-> The motivation of this paper is definitely interesting. Actually, interpretability represents one of the key features of decision trees: deeper trees, which may be needed for solving complex classification tasks, may loose this property.\n-> The proposed approach is simple but reasonable.\n-> The paper is well written and clear.\n\n\n\n*Negative points/questions*\n\n-> The main problem of the proposed method is the empirical evaluation:\ni) authors used only three ML datasets of moderate size\nii) the impact of different parameters of the proposed methods is not analysed. For example, which is the impact of the threshold? (Authors only used 0.8 in all experiments). Further, all trees in the cascading architecture have max depth of 3. What about using longer/shorter trees?\niii) Comparisons of results in tables are not supported by a statistical test. Is the accuracy of 93.51% (first row table 3) different than 93.16% (second row)? Without a statistical test it is impossible to derive significant conclusions. A possible strategy: shown results are computed using 5 fold cross validation, thus meaning that reported numbers represent the average of 5 repetitions; by repeating the whole procedure 10 times (with different random subdivisions of training and testing), author would have a more robust estimation of the reported numbers (average of 50 tests). Moreover, with such scheme they can also assess the statistical significance of differences by using a (paired) t-test.\niv) the explanation depths of classic trees are in average very short, can authors comment this? Moreover,  which is the maximum length of the classic decision trees? Authors simply reported that they used “various bounds on the depth of the learned tree”.\nv) conclusions derived from tables are not completely supported by the tables. For example, in the paragraph “Low False-positive Rate” authors say that “As shown in Table 3, the cascading decision trees algorithm has the lowest false positive (FP) rate for all three datasets compared to the classical decision trees algorithm.”. By looking at table 3 this is not evident: it seems to me that with Ionosphere and Sonar the lowest FP is obtained with the variant without cascading (“Off (max_depth =3)”). Am I correct?\nvi) I wonder if the comparison with BioOCT is fair (in terms of classification accuracy), since the maximum depth of this last method has been fixed to three.\nvii) Comparisons only involve standard trees: what about comparing also to other methods used to reduce the depth of decision trees? This would enlarge the scope of the experiments and the value of the proposed approach.   \n\n\n-> I think that the proposed approach can be better inserted into the state of the art. Actually, the combination of different classifiers in cascade is not new in the literature of ensemble classifiers, with many methods introduced. Authors provide comments only on boosting (in Section 3),  but many other methods have been presented. Just to provide few pointers to old works:\n\nE. Alpaydin and C. Kaynak. Cascading classifiers.KYBERNETIKA, 34(4):369–374, 1998\nL. Bruzzone and R. Cossu. A multiple-cascade-classifier system for a robust and par-tially unsupervised updating of land-cover maps. IEEE Transactions on Geoscienceand Remote Sensing, 40(9):1984–1996, 2002\nLudmila I. Kuncheva: Combining Pattern Classifiers - Methods and Algorithms , Wiley 2004\n\nI agree with authors that the goal of their approach may be different (extracting shorter explanations rather than increasing classification performances), but a discussion of different cascading strategies may better contextualize and justify the proposed approach. \n\nIn the same spirit I would suggest the authors to discuss techniques for obtaining compact decision trees (pruning etc).\n\n\n-> If we focus on classification accuracies, decision trees do not represent state-of-the-art classifiers, with performances which are very often far away from competitors like SVMs or Neural Networks. This somehow limits the application of these techniques (if not used inside Random Forests).\n\n\n-> Authors provide methods and definitions (e.g. “valid explanation”) for a setting in which we have binary features. Why? If I correctly understand, the definitions can be easily provided also for numerical features (with the usual split based on a threshold), providing a more general framework. Moreover, the experiments are done with datasets having numerical non binary features.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "O8AqMxqxZcm", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This work proposes to use cascade decision tree models to come up with shorter explanations for the predictions made by the decision trees.\n\nThe proposed technique focuses on explaining one class in a binary classification task, i.e., positive samples. The idea is to build a decision tree with predefined depth to classify positive samples, remove those classified positive, as well as negative samples in leaf nodes that are dominated by negative samples, from the dataset, and then repeat this process until the sequence of tree models is built.\n\nExplainability of ML models is an important topic, especially for medical scenarios. In addition, shortening the decision tree paths to improve explainability is a promising direction. The writing of the work is also clear and easy to follow.\n\nHaving said that, I have the following concerns about this work:\n\nW1. The application scenario is narrow. And it is not clear why the explanation path is not the concatenation of all the paths of the cascading trees.\n\nD1. The proposed approach only applies to binary classification task. It is not clear how this can extend to multi-class and regression models.\n\nD2. Also, even for binary classification, it only explains one class. It is counterintuitive that you need to build different models to explain the classification of the two classes from the same dataset.\n\nD3. Since the process of building a subtree is independent of the previous subtrees built, i.e., the features and splits of the tree being built does not consider the features and splits in previous subtrees, it seems to me that the subtree is pre-conditioned by the previous subtrees. It is not clear why it is correct to only use the subtree that the prediction ends for explanation instead of all the subtrees that are used before the prediction ends. \n\t\t\nW2. The complexity of this decision tree can be high, leading to high inference time. And the model can be overfit to positive samples.\n\nD4. Because the cascading model tries to construct leaves with most pure positive samples, the total depth and the number of trees in the model can be quite high. This will especially impact the overhead in the inference.\n\nD5. Also, given this tree is built for optimizing the classification of one class with very high accuracy, the model can be overfit to that class, and the prediction accuracy of the other class is not guaranteed.\n\nW3. The evaluation needs to be enhanced.\n\nD6. The average path length of classic decision trees is already small, i.e., less than 4. The evaluation needs to perform on more complex datasets.\n\nD7. In medical scenarios, we would expect the negative data samples are much more than positive data samples. It is already easy to overfit for the positive samples in this scenario, and as mentioned in D5, the technique itself also tends to overfit. Overfitting may not be a good idea for this skewed dataset.\n\nD8. It is unclear if the proposed technique gives better explanation without doing a user study. As mentioned in W1 and D3, it is not entirely clear why the explanation does not need to concatenate all the paths in the subtrees before the prediction ends. This is especially a concern since the classic decision tree only has a single tree. It will be great to conduct some user study to understand why the proposed technique impacts the Explainability.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FJ4VuvkCcfj", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\n# Summary\n\nThis paper introduces a new type of classification model called the \"cascading decision tree.\" The cascading decision tree is a rule-based classifier designed to have an overlapping hierarchical structure between its nodes to produce succinct explanations. The paper introduces these models, presents an induction algorithm to learn them from data, and includes an empirical evaluation on three UCI datasets as well as a propietary dataset. The submission includes code.\n\n# Pros\n\n1. The paper introduces a new kind of classification model. This model form is a contribution in and of itself (i.e., regardless of the algorithm used to fit cascading decision trees from data). \n\n2. The paper highlights an innovative approach to the design of machine learning models – i.e., training models that are constrained to have particular \"explainability\" properties.\n\n# Cons\n\n3. The cascading trees produced by the algorithm in this work have little to no formal guarantees regarding their optimality or generalization produces. It is unclear if this is the best way to learn cascading decision trees.\n\n4. The paper does not provide a pruning routine. The authors suggest that the algorithm can be paired with any generic pruning method. However, the empirical results do not showcase how the trees perform after pruning. \n\n5. The experimental section is lacking in multiple ways. Ideally, this section should include comparisons on more than three datasets, and consider other baseline models such as \"rule lists\" (i.e., a special kind of decision tree) and sparse linear models (i.e., a type of model that does not require explanations). Finally, I would recommend the authors to include a plot that shows the distribution of explanation depths for all the examples in a dataset. This would allow readers to have a far better understanding of how each method affects the explanation depth (as compared to a comparison of the means).\n\n6. The paper does not make a strong case to motivate why \"shorter explanations are better.\" This is unfortunate given that succinct explanations are the primary motivation for using cascading decision trees. At a minimum, the paper should include a clear demonstration the advantages of using succinct explanations in a modern application. Ideally, this would include: (i) comparisons of the explanations produced for the same point by competing methods; (ii) a study of how the properties of explanations change based on other relevant phenomena (e.g., explanation depth for seen/unseen points).\n\n# Rating\n\nOverall, I was convinced that \"cascading decision trees\" were a valuable model class. I was also convinced that this work was valuable in that it highlights a novel approach for supervised learning (i.e., training models with explicit constraints on explainability such as in https://arxiv.org/abs/1703.03717)\n\nMy current rating (3) is based on the fact that the submission fails to analyze, validate, or motivate cascading decision trees sufficiently. Ideally, the paper should include a thorough analysis of the tree induction algorithm (as discussed in 3 and 4) as is standard in other work on decision trees. It should include more robust evidence that the proposed method produces succinct explanations (as discussed in 5), as well as a convincing demonstration of the utility of succinct explanations in modern applications (as discussed in 6).\n\n# Questions\n\nQ1. How does one measure the \"quality of a cascading decision tree\"? Is it only in terms of \"explanation depth?\"\n\nQ2. Did you use a pruning routine in your experiments?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces the idea of cascading decision trees.  The reviewers agree that this is a potentially novel and valuable idea, but they also agree that the paper fall short in execution.  The paper would be substantially strengthened with more theoretical analysis, more discussion of why cascading decision trees are useful, and most importantly substantially more empirical evaluation, especially with more data sets and more baselines for comparison.
Decision: Reject