Average Sensitivity of Decision Tree Learning
Authors: Satoshi Hara
Yuichi Yoshida
Venue: ICLR 2023 poster (2023)
Keywords: decision tree
average sensitivity
trustworthy machine learning

Abstract: A decision tree is a fundamental model used in data mining and machine learning. In practice, the training data used to construct a decision tree may change over time or contain noise, and a drastic change in the learned tree structure owing to such data perturbation is unfavorable. For example, in data mining, a change in the tree implies a change in the extracted knowledge, which raises the question of whether the extracted knowledge is truly reliable or is only a noisy artifact. To alleviate this issue, we design decision tree learning algorithms that are stable against insignificant perturbations in the training data. Specifically, we adopt the notion of average sensitivity as a stability measure, and design an algorithm with low average sensitivity that outputs a decision tree whose accuracy is close to the optimal decision tree. The experimental results on real-world datasets demonstrate that the proposed algorithm enables users to select suitable decision trees considering the trade-off between average sensitivity and accuracy.

Published as a conference paper at ICLR 2023
AVERAGE SENSITIVITY OF DECISION TREE LEARNING
Satoshi Hara
Yuichi Yoshida
Osaka University
National Institute of Informatics
aatohara@ar. u... acac. ip
yyoshidaenii.ac:
ABSTRACT
A decision tree is a fundamental model used in data mining and machine learning. In practice, the training data used to construct decision tree may change over time or contain noise, and drastic change in the learned tree structure owing to such data perturbation is unfavorable. For example, in data mining, change in the tree implies a change in the extracted knowledge, which raises the question of whether the extracted knowledge is truly reliable or is only a noisy artifact. To alleviate this issue, we design decision tree learning algorithms that are stable against insignificant perturbations in the training data. Specifically, we adopt the notion of average sensitivity as stability measure, and design an algorithm with low average sensitivity that outputs a decision tree whose accuracy is close to the optimal decision tree. The experimental results on real-world datasets demon- strate that the proposed algorithm enables users to select suitable decision trees considering the trade-off between average sensitivity and accuracy.
INTRODUCTION
A decision tree is fundamental model in applications such extracting knowledge in data min-
ing and predicting outcomes in machine learning. Learned decision trees enable the extraction of
hidden structures in the data in an interpretable manner using the if-then format. In data mining.
the extracted structures are of fundamental interest (Rokach & Maimon 2007| Gorunescul 2011))
Decision trees also play an essential role in decision making (Zeng al. Rudin [019 Arrieta et al. 2020) because unlike complex models, such as deep neural networks, the decisions made by decision trees are explainable. With the increase of the utility of machine learning models in real-
world problems, decision trees and their variants are widely used particularly for applications such as high-stake decision making, where explainability is crucial and transparency higher than post-hoc
explanations (e.g., (Angelino et al. 2018 Rudin 2019: Arrieta et al. 2020 are required.
Current studies on decision trees and their families mainly focus on developing learning algorithms to improve two aspects of learned trees: accuracy and interpretability. Here, we demonstrate that there is a third essential aspect that is missing in current studies: the stability of the learning algo- rithm against insignificant perturbations extract knowledge from data and help users make decisions that can be explained. If the learning algorithm is unstable, the structure of the learned trees can vary significantly even for insignificant changes in the training data. In data mining, this implies that the extracted knowledge can be unsta- ble, which raises the question of whether the extracted knowledge is truly reliable or only noisy artifact induced by the unstable learning algorithm. In model- based decision making, this implies that the decision process can change drastically whenever few additional data are obtained and the tree is retrained on the new training data. Such noisy decision makers are unacceptable for sev- eral reasons. For example, stakeholders may lose their trust in such decision makers, or it may be extremely costly to frequently and drastically update the entire decision making system.
the training data. Decision trees typically used to
Figure | shows an illustrative example of sensitive/stable decision tree learning algorithms. this example, the standard greedy tree learning algorithm induces different trees before and after one data point (large red triangle) is removed (Figure aa). Thus, can be observed that the greedy algorithm is sensitive the removal of data points. The objective of this study is to design tree learning algorithm that can induce (almost) same trees against the removal of a few data points (Figure

---

Published as a conference paper at ICLR 2023
Data Points
Before Removing
After Removing
Before Removing
After Removing
Class
Class
Predictions
by Tree
Class
x1
X1
X1
X1
Class 2
(a) Standard greedy tree learning algorithm
(b) Proposed stable tree learning algorithm
Figure 1: Decision boundaries the learned decision trees. (a) The standard greedy tree learning algorithm is sensitive to the removal of even single data point (large red triangle) from the training data. (b) The proposed learning algorithm produces more stable trees.
In this study, we design decision tree learning algorithm that is stable against insignificant pertur- bations in the training data. Specifically, we consider the change in (the distribution of) the learned tree upon deletion of random data point from the training data, using the notion of average sen- sitivity (Varma & Yoshida, 202T). Subsequently, we design a (randomized) decision tree learning algorithm with low average sensitivity while preserving the accuracy of the learned decision tree up to tolerance parameter.
A randomized algorithm may output completely different decision trees on the original training data and on the training data obtained by deleting a random data point even if the output distributions are close. To alleviate this issue, we design (randomized) decision tree learning algorithm with low expected average sensitivity over random bits used in the algorithm, which implies that the output decision tree on the original training data and that on the training data obtained by deleting random data point are close with high probability over the choice of the random bits used.
Through real-world data experiments, demonstrate that our learning algorithm exhibits lower average sensitivity compared to the standard greedy decision tree learning algorithm, while main- taining the decrease in accuracy within the prescribed tolerance parameter.
RELATED WORK
Decision Tree Learning Algorithms Generally, learning optimal decision tree is NP- hard (Laurent & Rivest T976), and hence we can obtain optimal trees only for small problems (Bert-
simas & Dunn] 2017 Angelino al.) 2018 Günlük al.] 2021). To avoid this issue, recursive greedy splitting is widely used for learning (non-optimal) decision trees (Rivest, 1987 Loh 2011 Quinlan 2014). and Bayesian approaches are used learn a family of decision trees, such as rule lists and rule sets (Wang et al. 2017; Yang et al. 2017). These studies are concerned with learning trees with less computation or better interpretability. This study orthogonal to them in that our interest is developing stable decision tree learning algorithms, which was not considered before. We stress that the focus of the current study to learn stand-alone decision tree and not to learn a collection of decision trees for ensemble models (e.g., (Ho 1995] Breiman] 2001] Friedman [200T] Chen & Guestrin 2016)). For the latter, we want decision trees that make different predictions, and hence somewhat sensitive algorithms are favorable rather than stable ones.
Average Sensitivity Varma & Yoshida (202T) introduced the notion of average sensitivity and de- signed algorithms with low average sensitivity for various graph problems including the minimum spanning tree, minimum cut, and minimum vertex cover problems. Average sensitivity of algorithms discussed also for various problems including the maximum matching problem (Yoshida & Zhou 2021), ) problems that can be solved by dynamic programming (Kumabe Yoshidal 2022a b). spec- tral clustering (Peng& & Yoshida 2020), and Euclidean k-clustering Yoshida & Ito 2022).
Adversarial Robustness Insignificant human caiman-imperceptiblle perturbations to the input can mis- lead trained models, and such perturbations are called adversarial attacks. It is known that adversar- ial attacks are harmful to decision trees (Chen et al., 2019a] b) Kantchelian et al., 2016). To alleviate this issue, several recent studies have considered the problems of robustness verification (Chen et al. 20196. Tömbblom & Nadjm-TTehe Tchrani 2019: Wang et al.) 2020) and adversarial defense (Chen et al,
2019a
Andriushchenko & Hein 2019: Calzavara al. 2020 Chen et al. 2021 Adversarial at-
2

---

Published as a conference paper at ICLR 2023
tacks focus the change in the predicted label against perturbing single input data point the inference time, whereas average sensitivity focuses on the change in the learned decision tree against perturbing the entire training data at the learning time.
Stability Bousquet and Elisseeff introduced the notion of the stability of learning algorithm and discussed its relation to generalization ability (Bousquet & Elisseeff [2002). Unlike average sensitivity, this notion only concerns the stability of the loss value against data perturbation. Hence, it cannot be used to stabilize the structure of learned decision tree.
Differential Privacy Differential privacy [worrk 2006) measures the stability of the output against perturbation the input. Decision trees have been intensively studied from the perspective of differential privacy (see (Fletcher & Islam 2019) and references therein). The average sensitivity of an algorithm can be bounded by the differential privacy parameter times the maximum size of the output (Varma& & Yoshida [202T) In the decision tree learning setting, the bound we obtain in this manner roughly O(s 2²), where B specifies the depth of the output decision tree. By contrast, our bound (Theorem 4.1 1 is O(B2 /n), where is the number of points in the training data. Our bound is much smaller because we usually set 2 < n to avoid overlitting.
PRELIMINARIES
3.1 DECISION TREE
Let X and Y be input and output spaces, respectively. We call Boolean function w X + {0, decision rule. Then, a decision tree is a function Φ X' - y represented by a rooted proper binary tree, that is. it has special node called the root and each node has either zero two children, such that each internal node L is associated with a decision rule wt : X' - {0, 1 and each leaf is associated with a label ye E Y. Then given an input x E X, the decision tree & predicts label y according to PREDICT(O, æ) shown in Algorithm !
Let [ ((x1, (1).)))... .I..... (In, yn)) be a training data. The total score of a decision tree ò X y with respect to L is defined to be s( C) ;= Σx= [[((x;) = wi]. where 1[X] is the indicator of the event X. Note that s(Ø L)/n the accuracy of Φ on L.
ii=1
For nonnegative integer B. let TB be the set of decision trees of depth B. Then, let opt == max s( L) be the maximum total score of decision tree of depth B. Also for decision rule w: X' -> [0. }} and nonnegative integer B, let Tw, be the set of decision trees of depth B with the root node having the decision rule w. Then we define opt (()) = max s(6 L). We clearly have ( max,, opt (C))
For decision tree Φ, we denote by |o| the number of nodes (including the leaves) ó. For two decision trees & and ø', we define the distance do d') between them as the output of DIs- TANCH(Ó, σ') shown in Algorithm 2 Intuitively, the procedure DISTANCE(Ó, (') computes the maximal subtree common to é and Ø and then outputs the total number of remaining nodes after subtracting the common subtree from and Φ'. is clear that (:.(::)) satisfies triangle inequality.
We note that, even if two decision trees 0. : X' + y are equal as function, they may have a large distance in dpr if they have different tree structures. For interpretability, however, we believe this is the advantage of using dpT because it is not easy to verify the equivalence of and ø when they have different tree structures and dDT correctly reflect this situation.
3.2 AVERAGE SENSITIVITY
For a training data L. ((11,,1), -...) (Wis Mn)) and 1 (x4-11 11-1), (2441, (141), (F Mx)) be the training data obtained from L by dropping the ith data point.
5 n, let (()
Let A be a deterministic algorithm that, given a training data, outputs a decision tree. Then, the average sensitivity of A Lis
dor(A(()) d(
3

---

Published as a conference paper at ICLR 2023
Algorithm 1:
Procedure PREDICT(O, z)
Let t be the root node of Φ; if t is a leaf then return yr: else
Let dr, RR be the decision trees rooted at the left and right children of t, respectively; if (xr) 0 then return PREDICT(OL,
else return 2)):
Algorithm 2:
Procedure DISTANCE(Ó, d')
Let t and t' be the root nodes of & and ø', respectively; both and t' are leaves then return 0 if Yt Ye and 2 otherwise.
else if either t or t' is leaf then return @6) 10'1; else we + w/ then return @ lo'|: else
Let ΦL, ØR be the decision trees rooted at the left and right children of t, respectively; Let Ø6, R be the decision trees rooted at the left and right children of t', respectively; return DISTANCE d'z)) + DISTANCE(Ón, R'R)-
10
Now, generalize this definition for randomized algorithms. First for two distributions D and D' over decision trees, we define their earth mover's distance as (EM D') minp - (irr(2,6)) where P is over distributions of pairs of decision trees such that the marginal distributions the first and second coordinates equal to D and D', respectively. Let A be a randomized algorithm that, given a training data, outputs decision tree. Then, we define the average sensitivity of A L as
((M(A(()
where regard A(-) distribution decision trees.
is natural to consider a variant of average sensitivity such that we delete & data points instead of single data point because in practice many data points can be dropped. As discussed in Varma & Yoshida (2021). this variant can be bounded by l: times the average sensitivity above, and hence we focus bounding the latter.
4 DECISION TREE CONSTRUCTION
In this section, we provide a decision tree learning algorithm with high total score and low average sensitivity. Specifically, we show the following:
Theorem 4.1. There exists an (possibly inefficient) randomized algorithm that, given a training data of size n,, depth bound B, and parameter > O, returns a decision tree à of depth at most B such that Eg(s( [s,, L)] 2 (1 - B and for the set of decision rules S, its average sensitivity is
B2" log
We note that we usually choose B < n to avoid overfitting and = ((1BB) to achieve constant approximation, and hence the average sensitivity bound is essentially O(1nn). We note that the algorithm of Theorem makes use of the optimal total score, which is not efficiently computable in general. We discuss practical implementations of the algorithm in Section 6
The algorithm of Theorem 4. is based on a procedure called STABLEDR, which selects a decision rule in stable way (Algorithm This is simple application of the exponential mechanism (Mc-
4

---

Published as a conference paper at ICLR 2023
Algorithm 3:
Procedure STABLEDR(C, e)
Select w E S with probability & (x op where A c-optg(C)
2 [
return w.
Procedure STABLEDT'CC. c,)
ic I or d = B then return an optimal label for L;
STABLEDR B, e);
Partition L into L2 U R according to wt
ØL < STABLEDT' (Lz, c, 1) and Φn t STABLEDT (CR, B, c,c+1))
Let o., be the decision tree such that the root node has rule w and the left and right children of are dr. and ΦR. respectively; return dh.-
10
11 Procedure STABLEDT(C. B,e)
12
return STABLEDT' (C, e)
Sherry & Talwar 2007 to BBt,,B(C) (w E Q). Then, the proposed algorithm, STABLEDT (Algo- nlhm 5). works follows. At each node, compute decision rule using STABLEDR, split the training data according to w, and recursively construct decision trees for each of the split data until the depth becomes B.
the size of the training data becomes most
To understand why the randomized procedure STABLEDR produces stability, consider the following scenario: Suppose that we have candidate rules w/ and w2 with optimal scores un ,, (L) 90 and wp ()) 89, respectively. The greedy algorithm selects wa because it has the larger score. Suppose that the scores have changed upon the removal a subset S C and now we have opt n \ S) 85 and opt ( 8) 86. Then, the greedy algorithm selects w2 because has now the larger score, and hence never obtain the same tree for L and L S. By contrast, the probability that STABLEDR selects w1 (resp., w2) is nearly half for both L. and L \ S because wi (resp., w2) is nearly optimal rule. Hence, the distributions of the trees given by Algorithm are close between L an
5 EXPECTED DETERMINISTIC AVERAGE SENSITIVITY
Recall that the average sensitivity for randomized algorithms bounds the earth mover's distance between distributions of A(L) and A(C('). This does not immediately imply that, given decision tree for C. we can compute a similar decision tree for (()) with a similar total score because the mapping from decision trees for those for ( that achieves the earth mover's distance is not always available. To address this issue, we consider bounding the expectation of deterministic average sensitivity between output decision trees over random bits:
a
dor (A)(A, n Σ
E
where Aş is the deterministic algorithm obtained from randomized algorithm A by fixing the ran- dom bits used in A to E 1)" Then, using the same random bits π,, we can obtain similar decision trees for L and ((+), Note that the average sensitivity ( is bounded from above by the ex- pected deterministic average sensitivity (2) because the pair of random variables (Ax(C), A (C()))
induces joint distribution over pairs of decision trees.
By slightly modifying STABLEDT and the proof of Theorem 4.1 we obtain the following:
Theorem 5.1. There exists (possibly inefficient) randomized algorithm that, given training data C of size n, a depth bound B, and parameter c > 0, returns a decision tree & of depth at most B such that Esls(0, L)] 2 (1 e) opl.ppp (C), and for the set of decision rules n its expected average sensitivity over random bity is O B22 log [5]]
5

---

Published as a conference paper at ICLR 2023
Table Datasets
training data size
sampled data size
test data size
of features
# of classes
tree
Dataset
depth
breast cancer
546
436
137
10
5
diabetes
614
491
154
cod-rna
59535
1000
271617
10
covtype
400000
1000
181000
large
higgs
10500000
1000
500000
28
2
3
ijenn
49900
1000
91701
22
2
1
sensorless
48509
1000
10000
48
11
9
wehspam
300000
1000
50000
254
7
PRACTICAL IMPLEMENTATIONS
require the value of opt (C)),, which NP-hard compute (Laurent & Rivest 1976). Although several algorithms based on integer pro- gramming were proposed (Bertsimas & Dunn 2017: Günlük et al.) (021). they are not fast enough handle large data. To address this issue, we suggest replacing opt... (L) with opt.. (C) because the latter can be computed quite efficiently. Note that this strategy is the same as the standard greedy
The algorithm STABLEDR and the algorithm of Theorem 5.1
recursive splitting used for training (non-optimal) decision trees (Rivest) 1987; Loh [011 Quinlan 2014). We use this version in our experiments in Section 7 The same analysis goes through and we obtain the following.
Theorem 6.1. There exists a randomized algorithm that, given a training data L of size n, a depth bound B, and parameter
returns decision tree of depth most B such that E[s(Ø, L)] Z (1 - c)opt, (C), and for the set of decision rules Q its expected average sensitivity over random [loon]]]1
bits is B32 [91 en The time complexity is Ld=o 2 T(n/2 [52], where T(m) the
running time required compute opt (C') for w E Q with | m.
We note that, although the approximation guarantee of Theorem 6. is weaker than those of Theo- rems 4.1 and [5.I, practically used decision tree learning algorithms also lack approximation guar- antees. In Section 7 empirically confirm that the accuracy of the algorithm of Theorem 6.1 is not much worse than those baseline algorithms. We also note that, in many cases, computing opt (L') takes linear time, and sometimes we can compute opt (C') for many w's at once.
EXPERIMENTS
We demonstrate that the proposed algorithm can output stable decision trees.
7.1 SETUPS
Datasets We used datasets shown in Table We split the datasets into small ones (breast cancer and diabetes) and large ones (cod-rna, covtype, higgs, ijenn, sensorless, and webspam). We use small datasets to demonstrate the stability of the proposed algorithm, and large datasets to study trade-offs between average sensitivity and accuracy. the experiments, we used subsamples of these datasets. For training, we randomly sampled 80% of the data points and 1000 data points for small and large datasets, respectively. In the experiments. evaluated the accuracy of the learned decision trees using the entire test data.
Tree Learning Algorithms In the experiment, we used the practical implementation described in Section 6 for training the decision trees. As we have shown Theorem 66.1] this practical imple- mentation can output stable decision trees without solving NP-hard problems. We also adopted the following greedy tree learning algorithm as the baseline for comparison. each node, the greedy
'These datasets obtained from hotps: // h//gtttii thub. com/ ted MNIST-based datasets because decision are typically not used for images.
We omit-

---

Published as a conference paper at ICLR 2023
algorithm selects the decision rule with the highest score, i..., arg max o (C). When multiple decision rules exist in arg EE o,t (C), we select one of them uniformly at random. We set the tree depth shown in Table I so that the greedy algorithm exhibits the highest accuracy in vols-vaaliotion.
We implemented both the greedy and proposed algorithms in Python 3 using the JIT compiler of Numba. We used the equidistant points feature 2j as the decision rules, where 3j.min = j.1 and j.max = =, are the minimum and the maximum of øj in the dataset and we set Q 500. That is, we set Ω {u 1(ug S F3gali..
within the interval I 2 ) for each
Procedure We generated 10 sampled training data from the original training data. For each of the sampled training data, we trained decision trees using the greedy algorithm and proposed algorithms over different values of e. Because the tree learning algorithms are randomized, we trained trees for ten different random bits T1,"2, ....... 100- Through this procedure, we obtained 100 trees for each tree learning algorithm (over ten sampled training data and ten different random bits). We report the average of the average sensitivity and the training and test accuracy over these 100 trees. To estimate the average sensitivity, we trained additional trees using the sampled training data, with m data points removed at random. Formally, let A(C) be the tree trained using the algorithm A on L. Then, we consider another tree A(C \ S) trained on the set L S S with SS] m.. We selected the sets S S2,.... Sn at random, and estimated the (normalized) expected deterministic average sensitivity over random bits as R
> dor(A,, (4),,,, where मe is the f-th random bits,
dn and dg = B is the maximum distance between the trees with depth B, which normalizes the sensitivity within [o, 1]. We interpret this normalized sensitivity as the fraction of different nodes between the two trees. We set R- 100, and varied the number m of removed data points from to 30% of the sampled training data.
7.2 RESULT 1: DEPENDENCY ON C
First, we evaluated the dependency of the proposed algorithm on the choice of for small datasets. In the experiment, we evaluated the algorithm over nine different e values from 10-2 to 109 on a logarithmic scale and over the number of removed data points m = L, 1%, and 10% of the sampled training data. Figure 2 shows the average sensitivity, training accuracy, and test accuracy. It is evident from Figures (a) and (d) that the average sensitivity decreases as e increases as suggested by Theorem 6. Empirically, we observed that the average sensitivity is kept almost constant until 0.1 and it began to decrease for larger e values. Figures (b) and (e) show that the training accuracy decreases for larger than 0.1. These results suggest that the stability of the trees is obtained at the cost of the decrease in training accuracy. This observation is consistent with Theorem 66.] as well. Based on these results,
empirically confirm the correctness of Theorem 6.1 the trained decision trees become stable, particularly for larger e, whereas the accuracy decrease. We also note that Figures ( and (f) suggest that this may not always be the case for test accuracy, which is outside the scope of our theorem.
7.3 RESULT 2: EXAMPLES OF TREES
Figure shows examples of the trees trained on the breast cancer dataset using the greedy and the proposed algorithms with = 0.3 and m 10% of the sampled training data. In the experiment, we trained 100 trees on the set S, for r 1...., 100 estimate the expected average sensitivity over random bits. Within these 100 trees, some had identical structures, while others did not. In
the figure, we show the original tree trained using all the sampled training data, and the three most
frequently identical structures within the 100 trees. In this example, the original tree and the most frequent trees were identical.
There are two important implications in Figure 3 Firstly, the second frequent trees of the greedy algorithm changed drastically from the original tree, whereas in the proposed algorithm, the changes appeared only in small substructures. These smaller changes in the proposed algorithm induced smaller distance dpr (A(C), A(C \ S,,)), resulting in smaller expected deterministic average sensi- tivity for > 0.1, as shown in Figure
Secondly, the most frequent trees dominated 10/100 and 72/100 of the cases for the greedy and pro- posed algorithms, respectively. Therefore, the tree can change frequently upon data point removal
7

---

Published as a conference paper at ICLR 2023
Average Senoiivitty
Accuracy
The number m of removed data points Proposed
0370
Awerage
0.977
0.65
0.976
10
0364
0.62
8.73
0960
0972
1%
10%
(a) Sensitivity
(b) Training accuracy
(c) Test accuracy
Average Sensitivity
10a
Training Accuracy
Greedy
9.74
0.74
Average
Averape
9.72
772
20
0.60
10%
0.66
(d) Sensitivity
(c) Training accuracy
(1) Test accuracy
Figure 2: Average sensitivity and accuracy of the trained trees over different on small datasets,
breast cancer (a)-() and diabetes (d)-c). The blue and red lines denote the results for the proposed and greedy tree learning algorithms, respectively.
Original Tree
1st Frequent: 10/100
2nd Frequent: 6/100
3rd Frequent: 6/100
Ky
X s
1 29
Ne.1 $1
Xa
Xy
Xx
52
Xy 59
At 5
D
DB
DB
0
(a) (Greedy) The original tree (leftmost) the first three frequent trees (the others).
Original Tree
1st Frequent: 72/100
2nd Frequent: 12/100
3rd Frequent: 2/100
x:
K,33
X: 59
12 59
Xt
Xx
Xis2
y- dy-
-0
ory
(b) (Proposed) The original tree (leftmost) and the first three frequent trees (the others).
The three most frequent trees on the breast cancer dataset for (a) the greedy and (b) proposed learning algorithms over 100 random data point removals with 0.3 and m 10%. "T" and "F" on the edges denote the splitting whether the rule in the parent node is True and False, respectively. In both methods, the most frequent trees are identical the original trained using all the sampled training data. The red nodes denote differences from the original tree.
Figure 3:
in the greedy algorithm, whereas the change is less frequent in the proposed algorithm, where more than 70% of the trees are identical. These results indicate that the proposed algorithm can induce trees with small distances and less frequent structural changes. This property is favorable in prac- tical situations because in data mining applications, the extracted knowledge is guaranteed to not change drastically, and in machine learning applications, decision-making process.
continue using almost the same
7.4 RESULT 3: SENSITIVITY-ACCURAAN TRADE-OFF
The results in Figure suggest that the average sensitivity and accuracy in trade-off relation through e. Using a large e, we obtain stable trees with slight decrease in accuracy, where using a small e, we obtain accurate trees; however they tend have high sensitivities.
8

---

Published as a conference paper at ICLR 2023
Taining Accurac)
Traiing Accuracy
0.76-
Training Acturacy
The number m of removed data points Proposed
Average
0.92
Average
0.72
Average
0.
0.00
8:70
0.52
0.89
0.60
A.8
0.00
0.58
m 1%
0.0
0.2
05
0.8
02
0.4
3.6
0.8
1.0
5.0
0.2
044
0.6
0.5
Average Sensitivity
Average Sensibivity
Average Sensitivity
m 3%
10%
(a) cod-rna
(b) covtype
(c) higgs
M 30%
Traning Accuracy
0.00225
CA
Training Accuracy
Training Accuracy
Greedy
0.90703
0.92
egerage
0.5 0.50675-
0.99225
0.00/5D
Average
0.94
0.92
Awerage
0.50-
A
O
m
0.9600-
V
m = 3%
0.84
m 10% D
0.0 0.1
0.2 03 0.4 05
0.0
0.2
0.4
0.6
0.8
0.0
088 Average Sensitivity
02
04
0.6
100
30%
Average Sensitivity
Average Sensitivity
(d) ijenn
(e) sensorless
webspam
Figure 4: Trade-off curves between average sensitivity and training accuracy when is changed. We varied the number of training data points be removed from one to 30% of the sampled training data. White markers denote the results of the greedy tree learning.
We computed this trade-off for large datasets by varying from 10-5 to 10 on a logarithmic scale. Figure shows the trade-off curves between the average sensitivity and training accuracy. In the figures, we observe that the average sensitivity and accuracy are in trade-off relation for most of the datasets. The trees become stable as e increases, while incurring an accuracy decrease in the bottom left of the figures. We note that our theory only guarantees that the decrease in training accuracy is limited. However, the test accuracy results in Figure i Appendix also confirm that the drop in test accuracy is limited. Thus, it is not necessary sacrifice considerable amount of the test accuracy to obtain stable decision trees in practice.
The result cod-rna is an exception that did not exhibit clear trade-off curves. In this dataset, the trees become less stable and less accurate simultaneously for small as shown in the bottom right of the figures. In particular, the greedy trees tend be less accurate than stable ones. One possible reason of this phenomenon is overfitting. In Table | the tree depth is set to ten for this dataset. In such deep trees, the number of training data points that reach a deep node tends to be small. Then, the greedy selection of the best decision rule based on small number of data points can be unstable, some arbitrary rules may be selected by chance, and overfitting occurs. Therefore, the greedily selected rule is not optimal if we consider deeper trees, i.e., opt..p((4 can be smaller than some opt B even if opt... (4) opt .,),,(()) (C). On the contrary, the proposed algorithm randomizes the choice of the decision rule using an exponential mechanism. We conjecture that this randomization can help prevent suboptimal rules and overfitting, and increase the chance of gaining more accurate trees.
Finally, we emphasize that the results confirm that we gained the freedom to choose decision trees on these trade-off curves using the proposed algorithm. This will open up a new paradigm for prac- titioners who have suffered from the high sensitivity of existing learning algorithms. Practitioners can now tune e and obtain stable trees upon their demand.
8 CONCLUSION
We proposed decision tree learning algorithms with theoretical guarantees on its average sensitivity and accuracy. We experimentally confirmed that the proposed algorithms performed well on real- world datasets. An obvious open problem is to show some hardness on the trade-off between average sensitivity and accuracy. In practice, it is important that the predictions made by the learned model do not change significantly with slight changes in the training data. Hence, it is also natural to measure the distance between models by the number of mismatches of their predictions and study average sensitivity in terms of this distance even for "non- explaxxplai learning models such as random decision forests Ho (995); Breiman (001) and deep neural networks.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
In the experiments, we only used publicly available data so that all the results to be reproducible.
The code is available
ACKNOWLEDGEMENT
SH is supported by JST, PRESTO Grant Number JPMJPR20CS. YY is supported by JST, PRESTO Grant Number JPMJPR192B.
REFERENCES
Maksym Andriushchenko and Matthias Hein. Provably robust boosted decision stumps and trees against adversarial attacks. NeurIPS. 32:13017-13028, 2019.
Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists for categorical data. Journal of Machine Learning Research, 18:1-78, 2018.
Alejandro Barredo Arrieta, Natalia Diaz-Rodríguez, Javier Del Ser, Adrien Bennetot, Siham Tabik, Alberto Barbado, Salvador García, Sergio Gil-López, Daniel Molina, Richard Benjamins, et al. Explainable artificial intelligence (XAI): concepts, taxonomies, opportunities and challenges to- ward responsible ai. Information Fusion, 58:82-115. 2020.
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039- 1082, 2017.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
Leo Breiman. Random forests. Machine Learning, 45(1):5-32, 2001.
Stefano Calzavara, Claudio Lucchese, Gabriele Tolomei, Seyum Assefa Abebe, and Salvatore Or- lando. Treant: training evasion-aware decision trees. Data Mining and Knowledge Discovery, 34 15:1 2020.
Hongge Chen, Huan Zhang. Duane Boning, and Cho-Jui Hsieh. Robust decision trees against ad- versarial examples. In ICML, pp. 1122-1131, 2019a.
Hongge Chen, Huan Zhang, Si Si, Yang Li, Duane Boning, and Cho-Jui Hsieh. Robustness verifi- cation of tree-based models. NeurIPS, 32:12317-12325 2019b.
Tianqi Chen and Carlos Guestrin. Xgboost: scalable tree boosting system. In KDD, pp. 785-794, 2016.
Yizheng Chen, Shiqi Wang, Weifan Jiang, Asaf Cidon, and Suman Jana. Cost-aware robust tree ensembles for security applications. In USENIX Security, pp. 2291-2308, 2021.
Cynthia Dwork. Differential privacy. In ICALP, pp. 1-12, 2006.
Sam Fletcher and Md Zahidul Islam. Decision tree classification with differential privacy: A survey. ACM Computing Surveys (CSUR), 52(4):1-33, 2019.
Jerome H. Friedman. Greedy function approximation: A gradient boosting machine. Annals of statistics, 1189111892 2001.
Florin Gorunescu. Data mining: concepts, models and techniques, volume 12. Springer Science & Business Media, 2011.
Oktay Günlük, Jayant Kalagnanam, Minhan Li. Matt Menickelly, and Katya Scheinberg. Optimal decision trees for categorical data via integer programming. Journal of Global Optimization, pp- 1-28, 2021.
10

---

Published as a conference paper at ICLR 2023
Tin Kam Ho. Random decision forests. In ICDAR, pp. 278-282, 1995.
Alex Kantchelian, J Doug Tygar, and Anthony Joseph. Evasion and hardening of tree ensemble classifiers. In JCML, pp. 2387-2396, 2016.
Soh Kumabe and Yuichi Yoshida. Average sensitivity of dynamic programming. In SODA, Pp- 1925-1961 2022a.
Soh Kumabe and Yuichi Yoshida. Average sensitivity of the knapsack problem. In ESA, volume 244, pp. 75:1-75:14, 2022b.
Hyafil Laurent and Ronald L Rivest. Constructing optimal binary decision trees is np-complete. Information Processing Letters, 5(1):15-17, 1976.
Wei-Yin Loh. Classification and regression trees. Wiley Intendisciplinary Reviews: Data Mining and Knowledge Discovery, 1(1):14-25 23, 2011.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. FOCS, pp. 94- 103, 2007.
Pan Peng and Yuichi Yoshida. Average sensitivity of spectral clustering. In KDD, pp. 1132-1140, 2020.
J Ross Quinlan. C4. 5: progrums for machine learning. Elsevier, 2014.
Ronald L Rivest. Learning decision lists. Machine learning. 2(3):229-2)) 246, 1987.
Lior Rokach and Oded 7. Maimon. Data mining with decision trees: theory and applications, volume 69, World scientific, 2007.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and interpretable models instead. Nature Machine Intelligence, 1(5):206-215, 2019.
John Törnblom and Simin Nadjm-Tehrane An absstrcction-reiiemeeet approach to formal verifica- tion of tree ensembles. In SAFECOMP, pp. 301-313, 2019.
Nithin Varma and Yuichi Yoshida. Average sensitivity of graph algorithms. In SODA, pp. 684-703, 2021.
Tong Wang, Cynthia Rudin, Finale Desei-Velez, Yimin Liu, Erica Klampfl, and Perry MacNeille. A bayesian framework for learning rule sets for interpretable classification. The Journal of Machine Learning Research, 1811)23357-233, 2017.
Yihan Wang, Huan Zhang. Hongge Chen, Duane Boning, and Cho-Jui Hsich. On Ip-morm robustness of ensemble decision stumps and trees. In ICML, pp. 10104-10114 14, 2020.
Hongyu Yang, Cynthia Rudin, and Margo Seltzer. Scalable bayesian rule lists. In ICML, pp. 3921- 3930, 2017.
Yuichi Yoshida and Shinji Ito. Average sensitivity of euclidean k-clustering, In NeurIPS, 2022. to appear.
Yuichi Yoshida and Samson Zhou. Sensitivity analysis of the maximum matching problem. In ITCS, pp. 58:1-58:20 2021.
Jiaming Zeng. Berk Ustun, and Cynthia Rudin. Interpretable classification models for recidivism prediction. Journal of the Royal Statistical Society: Series A (Statistics in Society), 180(3):689- 722, 2017.
11

---

Published as a conference paper at ICLR 2023
A ANALYSIS OF STABLEDR
In this section, we show the following performance guarantee for STABLEDR.
Theorem A.1. For training data L, depth bound B, and a parameter O, let
STABLEDR B)e). Then, we have Ew [optw..[C]] 2 (1 - ()) Moreover, we have
Ei=1 drv (w,, (l) =0 (10s101)
[St] ) where w(t) A(C B, c). and dry (ws, wll)) denotes the total
variation distance between (the distributions of) w and w()
The first inequality claims that we can achieve nearly optimal total score using the output decision rule w. The second inequality claims that the distribution of does not change significantly when data point is removed from the training data. Theorem A. is obtained by combining Lemmas A.2 and A.4
A.1 APPROXIMATION GUARANTEE
First, we show that the selected decision rule does much deteriorate the total score of optimal decision tree.
Lemma A.2. Let = STABLEDR(C, (c, B,e). Then, we have
Elopl,,n 2 (1 -eoop (L).
Proof. For any have
Prfopt..B(A) I opt - cl exp(A opt,. (C)) Even opt
E Evestoop
expxxp(> (C) c))
Even exp(A optp.
|0 exp(A ( (C) - c))
I [ exp(-Ac).
exp(A opt (C))
Therefore, have
Elopt,, (C)]
2 Pr|opt n (C) S opt - -0
Pr/opt > opt - c) (opt c)
2 (1 [0 exp(eppppoo -c))) (cp - c)
2 opt (C) - [ exp)-Ac)
By setting c = log //2// and the choice of X, the claim holds.
A.2 AVERAGE SENSITIVITY
Next, analyze the average sensitivity of STABLEDR. For notational simplicity, write opt. and opt
(i) to denote oCC,, and opt,, respectively. The following lemma is useful for analysis.
Lemma A.3. For any decision rule w E Ω we have
Σ (pt opt!!)) S opt...
Similarly, we have
(C) - opt s (c).
12

---

Published as a conference paper at ICLR 2023
Proof. We first consider the first statement. Let & be the optimal decision that attains opt Note that & has depth B and the root node of o has the decision rule w. Then, we have
Σ (opt_ -ppt
(s(0, sl0, (1,
[6(())) v]
$ L) opt
The second statement follows by similar argument.
L
Lemma A.4. Ler
w STABLEDR B,C),
w (6) S
Then, we have
log [S2]
drv (w, (0)) =0 Σ 1=1
Proof. Notice that
n
Σ wl))
Σ
max 0. Pr(w = v8] -Pr(w()) = v
i=1 EER
Let (0) be A used in STABLEDR(C (8), B, E). Then we have
max 0, Pr(w = w) -r = 4i}
exp(A opt.p)
exp(A() (p)
=max 0, Σ E'r exp(1 optnr)
Eveen exp(A(() (1) opt
exp(A opt.)) - exp(A (f)
Ewee exp(A opt.y)
exp(A opt
exp(A(1) opt 2!
+ max
0
(3)
Te exp(A opt.))
Even exp(A() opt
where the equality is from the design of the algorithm and the inequality is from the following inequality
max - a} (b æ) + max(0, a}
which holds for any < b.
Let A and Bi denote the first and second terms, respectively, of (3. The following two claims bound the sums of the first and the second terms over and vh.
Claim A.S.
A X (C)
VEn
Claim A.6.
72
Σ Bid S 0() (C))
WEE
Before proving these claims, we first complete the proof the lemma assuming them. Combin- ing (3) and the two claims above, we have
(Log!
log [ (11)
Σ drv(w, < <0 opt +
e
13

---

Published as a conference paper at ICLR 2023
Theorem A.1
follows by combining Lemmas A.2 and A.4
Proof of Claim A.5
We have
exp(A opt.) - exp(A- opt!") )
= Pr(w = 2b] (1-111111 exp(A (1-exp(A opt (0)
E Ewen exp(A opt.y)
exp(1 opt
Pr[w 16] (1 exp (-X (opt - opr!
S Pr(w = (opt. - opt
where the inequality from c= S x for any x E R. Therefore, we have
A
Am
PEN
exp(1 opt..) exp(A )pr
E Een exp(A opt
Pr(w (optt opt
eE
Pr[w = opt
(by Lemma A.3)
#EN
< X opt
as desired.
Proof of Claim A.6
We first note that
B
exp(A (pt (i)
exp(A()) opt
max
0
Wen exp() opt,)
Σ Even exp(1(t) opt
exp(A opt!"))
exp(A opt!") (0)
< max
0,
Even exp() optp)
Even exp(1 opt
exp(A (pt
Σ Pee exp() opt.r) (1 exp (-opt (1 - )(o1))
max
0,
0, Pr|w = wlppt (A - 2 (0))
max
opt (C) Pr(w dillA (0)
Also, we have
log [9]
log [8]]
(1)
opt a
opt, g (C())
Log 53
opt
Ing (C)
log [52]
log 13
log
A
max
opt (2))
opt a (C0)
opt y
log [
log [92 opt.5 (C)
1=
optg((
log [2]
log [2]]
optn 263
1 opt
X
max
log [92]
i=1
(2)
log [
log [2]]
opt x
o (C())
A
+ A
log [62]
14

---

Published as a conference paper at ICLR 2023
S "
log [S2]
log [
opt woppppc.
+ 2A
(by opt p 1)
log [S2]
opt
-()),
(by Lemma A.3
Combining the two incqualities above, we obtain
BL
opt Pr(w 16]1 | = 0 (A optt
i=1 PEN
1=1 PER
B ANALYSIS OF STABLEDT
In this section, we analyze STABLEDT and prove Theorem 4.1
Proof of the first claim of Theorem 4.1 Let Lu be the input training data (so that we can use C to denote other sets).
We prove the following by backward induction on depth.
E|s(STABLEDT (C, c, d), C) 2 (1- - opt
Then, the statement holds by setting O.
The claim clearly holds when d = B because we output the optimal label.
Suppose that the claim holds for depth more than STABLEDT' (L, B, e, d), and let ø denote the output decision tree, let be the decision rule used in root node of ạb, and let Lÿ and C% denote the two training datas obtained from L by splitting according to Note that these
Consider particular call
random variables. Then, we have
E|s -] = Σ Pr|w wi [|sABBTAL (C), B,c,d+1),447
PEn
E|s(STABLEDT (C B, 1),
2 Σ Pr(w (1-11))
B-d-1 B-d-1 opt opt B
#E0
+ (1 c) B-d-1 n (Cx)
2 (1 6) B-d-1
Pr(w w9| (0((ooph.... opt.y.B-
2 (1 E) B-d
Pr[w = 01 - e)opt B-a
vED
21 c) opt (C))
where the first inequality is based the induction hypothesis and the second last inequality is based on Theorem A.I
Proof of the second claim of Theorem For notational simplicity, we drop the arguments and when calling STABLEDT' (L, B, d), because they are fixed in this proof. Additionally, we write STABLEDT instead of STABLEDT'.
Let Co ((I1,,1),... (In, Vn)) be the input training data (so that we can use L to denote other sets). For a subset L of Lo and E (1,2....,n), let g()) = L ((r),:))}
For 0 < < B, let La,.,..., Ca,z be the sets on which STABLEDT is called depth (if the number of sets on which STABLEDT' is called at depth is less than 24, we append empty sets). We order them so that STABLEDT and STABLEDT (Ca+ + 1) (if STABLEDT' (Ca.)) d) does not make recursive calls, we set f L441,2 0).
calls STABLEDT (Ca41.2511, d 1)
15

---

Published as a conference paper at ICLR 2023
For fixed {LB.)t, f have
dEM (STABLEEDD B), STAALD (4 B))
a
2d
ΣΣ [((, Wi) E Lnol = Σ ((x,,))) E EL = [4]
because the output changes only when (2t, 36) E L and the output change is bounded by one.
Let S d < B. Let waj and waj the w values used in STABLEDT d) and STA- BLEDT dg. d), respectively. Note that they are random variables. For a rule w, Let L and 2d+1,25 be the two sets obtained by partitioning Ca, according to w. Then for fixed {Ld.j by- we have
dEM dEM (STABLEDT STABLEDT d))
24
(rv(waj.4a)) 28-d
E dEM (STABLED) (C (411,22- 1), STABLEDT' (0)
(C (1411,5-111 1))
da.
E (STABLED) (C2ti d 1), (C dd 1))
2d
log |
< 2
n 2d+1
E dEM (STABLEDT' (c d 1), STABLEDT' (C 1)) Was
(by Lemma A.1
< C. BB log [
2d+1
E dEM (STABLEDT (C d 1), STABLEDT' (1 d 1)),
Wa
where C {Cas}}
0 is some universal constant.
By backward induction, obtain for any d and fixed
2d
(STABLEE (Laj, STABLEDT (c d))
log Ω
< C. 2 (B- d)
+n
for every 5 B. By setting d 0, we obtain the claim.
C MISSING PROOFS OF SECTION
In this section, we prove Theorem 5.1 We discuss modifications to STABLEDR and STABLEDT in Sections C.1 and C respectively.
16

---

Published as a conference paper at ICLR 2023
Algorithm 4:
Procedure SELDEEISTABLEDRC....oot log [[]] ( while true do
Sample w E Ω uniformly at random using Sample 7 [0, 1] uniformly random using म.
Pw be the probability of choosing w given in STABLEDR;
Pw > T then return W:
Procedure SEEDEDSTABLEDI (C, (,c,d,j,m)
if [I
= B then return an optimal label for
10
11
w/ < SEEDEDSTABLEDDRCC B, T)) Partition L into L U LR according to w;;
13
TL + [T1: (T.... ..) and R f (Tyy TT.
ØL SEEDEDSTABLEDI (,,,
1, mz)
15
ØR < SEEDEDSTABLEDT' (CR, B, d 1,2j 1R)
Let t.e be the decision tree such that the root node has rule and the left and right children of are Φ and on. respectively;
17
return dw.
Procedure SEEDEDSTABLEDTICC B,
19
return SEEDEDSTABLEDD (C,
C.I DECISION RULE SELECTION
In STABLEDR, we sampled a rule w E Q by the exponential mechanism McSherry & Talwar 2007 To bound the expected deterministic average sensitivity over random bits, perform the fo following rejection sampling. We first sample a rule E Ω and threshold т E [o, 1] uniformly at random by using и. If the threshold is than the probability Pw that sample w in the exponential mechanism, then we output W. Otherwise, we repeat the same process again. The details are given as SEEDEDSTABLEDE
Algorithm
The following lemma shows that the distributions of STABLEDR and DIRANDOMIZDSTAELEDD are the same and the derandomized average sensitivity of the latter can be bounded from above by the average sensitivity of the former.
Lemma C.1. Ler
STABLEDR'S B,c), (1) STABLEDR' (CO), B,e),
Wx DERANDOMIZEDSSAALLEERR (C, B,E,T),
((() DERANDOMIIEDSTABBEDDR (C,,,,
Then, the distribution of w and that of wa over n are the same. Moreover for any i E (1,2...., have
Pr(we # w(ll < 2d (dT
Proof. The first claim is clear from the design of DERANDOMIZEDSTABLEERR
Now we see the second claim. Let = Even exp(A opt,, (C)) and let Z = E EvER exp(X-
(C)),, opt,.n(C())) For w E Q, we let Pw: = exp(A opt (C))/Z. For w E Q we let p.
exp(A o ( (c(O)))))) and for EΩ Ω. we let (() = 0. Then, we have
Pr(w # w
Σ wen
Primin(py, (4) < max (0)
17

---

Published as a conference paper at ICLR 2023
Σ Pv - pp 2drv (w)
By the analysis of STABLEDR and Lemma C.I
we obtain the following:
Theorem C.2. Let Wx SEEDEDSTABLEDR(C.BB))
We have En lopt [(G]] N
(1
(f).
Moreover for w
SEEDEDSTABLEDR(CCC) B,C, have
Ex E dDT(Wa, wF)) 0 log 2
C.2 DECISION TREE CONSTRUCTION
We now explain the modification to STABLEDT. Let Ld. La.24 be the sets on which our al- gorithm called depth defined in the proof in Section Then, we want to make sure that the same random bits are used when processing particular La., no matter whether the input training data is C or ((a) (1 S i n.. To this end, at each node in the decision tree, split the random bits π (TI, ....... into JT = (TL, T3....) and म = (T22, m4, .), and then pass Tr and π on to the nodes for 2d+1,2 and Ed+1,2j+1, respectively. See Algorithm for details.
We replace Theorem A. with Theorem C.2 in the proof of Theorem 4.1 and we obtain Theorem 5.1
D ADDITIONAL RESULTS
D.1 DETAILED RESULTS IN SECTION 7.2
In Section 722 reported the trends of average sensitivity and accuracies over small datasets, breast cancer and diabetes. Here, we show the detailed results (i) with error bars, and (ii) with a relaxed version of the tree distance. For (i), in addition the average results, also show their variations. More specifically, we report the 25 and 75 percentiles of the results over 10 random realizations of the sampled training data. For (ii), we adopt relaxed version of the tree distance in Algorithm 5 In the original tree distance in Algorithm 2 we regarded that two trees are (completely) different when their top rules are different (Line 6). In the relaxed version Algorithm we regard that two trees are completely different only when the features used in the top rules are different. With this relaxation, we regard two subtrees with similar top rules such as w u + [[u S 1.0) and w/ u 1 [u < 1.01] as identical.
Algorithm 5:
Procedure DISTANCE' (cb Φ')
Let i. and E' be the root nodes of é and ø', respectively; Let ure be the feature used in w; if both and t' are leaves then L return
yt = ye and 2 otherwise.
else if either t or t' is leaf then return |d'|: else if wi. feature # wr. featue then return (Ø) + |0'|: else
Let d1.,, ØR be the decision trees rooted at the left and right children of I, respectively; Let Φ',, d be the decision trees rooted at the left and right children of L', respectively; return DISTANCE' DISTANCE'(éL
10
DISTANCE' (ORAACEE'OOR.AC. ('z).
Figures 6nd show the detailed results breast cancer and diabetes, respectively. In the figures, we show the and 75 percentiles using colored shades. The figures named Sensitivity and Sen- sitivity' the average sensitivity computed using the original distance and the relaxed distance, respectively.
The figures confirm that the decrease of the average sensitivity for > 0.1 will be sufficiently sig- nificant, in particular for the number of data removal m 1% and 10%. The figures on Sensitivity and Sensitivity also confirm that the average sensitivity measured by using the original tree distance
18

---

Published as a conference paper at ICLR 2023
and the relaxed tree distance are almost identical, implying the choice of the tree distance will only have negligible impacts to the results.
Average Sensitviiy
Average Sensitivity
Average Sensitivity
The number m of removed data points Proposed
10
1019
10
10
10a
15ct
10
16
10
10
10%
(a) Sensitivity (m 1)
(b) Sensitivity (m 1%)
(c) Sensitivity (m 10%)
Average Sensitiitty
107
Average Sensitivity
Avertge Sensitivitt
Greedy
20-1
2011
371 1%
371 10%
107H
10ml
10
10
10t4
10c
10-3
15mh
(d) Sensitivity' (m 1)
(e) Sensitivity' (m 1%)
(I) Sensitivity (m 10%)
Acturacy
Taaning Accuracy
1 Accurecy
0.00/52
300762
e.aove2
0.00/80
0 000760
0.00ee
0.00758
Average
3.00555
Average
0.00788
2.05754
15a4
10
15P
10"H
10"4
10c4
13
gg) Training accuracy (m (h) Training accuracy (m (i) Training accuracy (m
I)
1%)
10%)
Accuracy
0.00766
Test Test Accuracy
3.00765-
Tes Arcuracy
0.07666
Average
Average
Average
0.00758
8.0375
0.0758
(i) Test accuracy (m 1) (k) Test accuracy (m 1%) ()) Test accuracy (m 10%)
Figure 5: Detailed results on average sensitivity and accuracy the trained trees over different e on breast cancer. The figures named Sensitivity and Sensitivity' are the average sensitivity computed using the original distance and the relaxed distance, respectively.
D.2 TEST ACCURACY
For the experiments in Section 7 Figure 7 shows the trade-off curves between average sensitivity and test accuracy when is changed.
19

---

Published as a conference paper at ICLR 2023
Average Senalivity
Average Sensitivity
Averaige Sersitivity
The number m of removed data points Proposed
10-4
10-2
1%
10%
(a) Sensitivity (m 1)
(b) Sensitivity (m = 1%)
(c) Sensitivity (m = 10%)
Average Sensitivity
Average Sensitivity
Average Sensttvvng
Greedy
10
10%
(d) Sensitivity" (w1 1)
(e) Sensitivity" (m 1%)
(f) Sensitivity' (m 10%)
Training Accuraty
Tra raiiing Accuracy
Training Accuracy
Average
0.092
Average
Average
0.092
0.090
0.090-
0.00n
0.08
0.086
0.086
0.086
0.004
0.84
10T4
10
10a
10
10m4
109
10tt
E
Training accuracy (m (h) Training accuracy (m
(i) Training accuracy (m
1)
1%)
10%)
Accue 62
0.092
Average
Average
0.000
2.080
0.08s-
0.085
0.005
0.084
10
(i) Test accuracy (m 1) (k) Test accuracy (m = 1%) (I) Test accuracy (m = 10%)
Figure 6: Detailed results average sensitivity and accuracy of the trained trees over different on diabetes. The figures named Sensitivity and Sensitivity' are the average sensitivity computed using the original distance and the relaxed distance, respectively.
Test Test. Accuracy acx
486
0.88
0.67
Text Accuras age
0.52
The number of removed data points Proposed
Average
Average
Average
0.50
0.59
0.84
0.83
0.3
m
0.0
0.2
04
0.8
3.0
02
0.4
3.6
6.8
1.0
5.0
0.2
04
0.6
o's
m 1%
Average Sensitivity
Average Sensitvityy
Average Sensitivity
3%
10%
(a) cod-mo
(b) covtype
(c) higgs
X 30%
Greedy
Best Accuracy
Test Accurapy
0.86
Avera ge
89928-
Average
0.84
Average
O
m
A m
1%
89226
0.02
V m = 3%
0.50
D
10%
0.0 0.1
0'3 6/4
0.0
0.2
6.4
6.6
an
0.3
04
na
10
30%
Average Sensitiitty
Average Sensitivity
Average Sensidivity
(d) ijenn
(e) sensorless
webspam
Figure 7: Trade-off curves between average sensitivity and test accuracy when is changed. We varied the number training data points to be removed from one to 30% the sampled training data. White markers denote the results for the greedy tree learning.
20


Reviews:
[{"review_id": "y96rXvVDEE", "reviewer": "Reviewer_hkCt", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper presents an analysis of the sensitivity of a learned decision tree when perturbing the learning set. Authors define perturbation and design a training algorithm which is stable with respect to such perturbation, providing a theoretical quantification of it.", "summary_of_the_review": "Interesting paper with a nice idea. Experiments not completely convincing, some doubts on the significance.\n\nUPDATE AFTER REBUTTAL. I carefully read the responses, the clarifications, and the additional material, and I thank the authors for the significant efforts made in clarifying my doubts. After all, I still maintain my opinion on the paper: this represents an interesting work, with few limitations on experiments and significance (even if I acknowledge the efforts made by the authors in improving these aspects in the rebuttal)", "strength_and_weaknesses": "Positive points\n- The topic is definitely interesting\n- The idea, according to my knowledge, is novel and well explained\n- The structure of the manuscript is clear\n- Experiments and findings are interesting\n\nNegative points\n1. I’m not completely convinced about the significance of the proposed ideas. More in detail, I understand that it is interesting to evaluate the sensitivity of tree learning for small changes in the training data, but maybe this is of limited help. Actually Random Forests (or in general ensemble tree methods) start from this diversity and exploit this behavior to enrich single trees, why do we need to correct this? Why do we would prefer to have less sensitive decision trees? Or, in a provocative perspective, why should we work with single trees? I think this is an issue that deserves a discussion. \nA second comment: the theorem is focused on error on the training set, which is not as interesting as the error on the testing set (the generalization error). Other analyses focus on the generalization error.\n\n\n2. I have some concerns on the experiments.\n- The choice of the datasets is not well motivated. Moreover, it is not clear why authors used different sets of problems for different parts of the experimental evaluation: in section 7.2 they used breast cancer and diabetes, in section 7.3 breast, and is section 7.4 all the large datasets. \n- From table 1 it seems that trees for 3 of the 8 datasets have a very low depth, with two having depth 1 (which, according to me, can not be considered as a tree anymore). Why not using a standard depth, such as log(n)? Comparing results from so differently deep trees may lead to biases in the presented results: did authors consider the tree depth in the analysis?\n- Authors repeated the whole procedure 10 times, meaning that the variability across different repetitions can be very high (considering that strong subsampling has been done to create a training set, especially for large datasets). Results only display averaged accuracies, what about standard deviations? Are differences in the plot statistically significant? Without a statistical analysis strong conclusions can not be derived.\n\n3. A minor concern: authors defined “perturbation” as the removal of a single (or more than one) element from the training set. This is not the only possibility, authors should discuss relation with other definitions, like adding noise, or resampling like in bootstrap, just to cite a few.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UNd0Vjk8yv", "reviewer": "Reviewer_s724", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "[Varma et al 2021] recently proposed the notion of average sensitivity to measure the stability of solutions produced by graph algorithms. The authors of the paper under review propose to use the AS as a measure of the stability of algorithms learning decision trees w.r.t. random permutations of the training examples. The authors further propose an algorithm whose average sensitivity can be decreased at the cost of decreasing the prediction accuracy. The method is empirically evaluated and compared against standard greedy algorithm.", "summary_of_the_review": "The paper introduces the notion of average sensitivity as a measure of the stability of decision tree algorithms and proposes a simple randomized strategy to reduce it. Experiments show benefits of the proposed randomized method over standard greedy algorithm on small sample sizes. The paper would benefit from adding an intuitive explanation of the key idea, i.e. increasing stability of the learning algorithm via introducing randomness. \n", "strength_and_weaknesses": "Strengths:\n\nThe notion of stability of the learning algorithm is both practically relevant and theoretically interesting. There are not many existing papers on the topic. This paper provides a way how to study the issue of stability of decision trees formally. \n\nThe authors prove approximation guarantees for the proposed algorithm and the algorithm's ability to decrease the AS.  \n\nThe method is relatively simple modification of the standard greedy algorithm.\n\nWeaknesses:\n\nAlthough AS is exactly defined, it is not clear how relevant this measure is in practical applications. E.g. it would be more appealing to know a probability with which the learned tree is exactly the same after perturbing the data, or a probability that AS will below a specified threshold. On the other hand currently there are not much other alternatives.\n\nThe proven bounds show that AS of the proposed algorithm decreases with increasing number of examples. However, the bounds do not show why the proposed method should outperform the standard greedy algorithm. On the other hand, experimental results suggest that on small data the proposed method is indeed beneficial if compared to the greedy one.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PAgYI9lfXM", "reviewer": "Reviewer_tBhR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The paper describes a mean to lower the high sensibility of decision trees using randomization of algorithm construction. Some theorems are given and experiments are done showing that in general, trees obtained by the randomization process are less sensitive. ", "summary_of_the_review": "The paper requires one to know quite well the particular approaches used in the paper (derived by Yoshida and colleagues, for the most part of it), that seems to be well-known in combinatorial optimisation, maybe a bit less in machine learning. As I had to make an emergency review, I could just skim over those and my familiarity with them is too poor to make a strong judgment about the used techniques.\n\nAll in all, the approach looks interesting, but it would require a bit of clarifications for non-expert readers to better follow the paper. In its current form, intuition is sometimes hard to grasp, but the methodology is described with sufficient details to be reproducible. There are some aspects in the experiments that I could not interpret given my understanding, however.  ", "strength_and_weaknesses": "+: an interesting problem treated in an original way, that I did not know of\n\n-: some unclarity regarding experiments and methodology that I give here, that authors could maybe clarify:\n\n* If I understand Algorithm 3 well, each potential cut or optimal split of the tree is now a probabilistic decision (the cut is made or not). I honestly do not understand how this result in more stability of the tree? In particular, one would expect randomized cuts to put more diversity in built trees? What is the general value of the probability of accepting a cut (it is hard to grasp intuitively at first sight without being familiar with the approach). For example, in Figure 3.b, how does randomization help to have more systematic obtention of the original tree in the second line? \n \n* It would be good to have some idea of the variance values over some of the graphs. For example, in Figure 2.c, one would expect the high variations to be due to variance and not general trends, especially as those looks very small and edgy?\n\n* In figure 4, it seems that the evolution of all the curves in terms of training accuracy is the same for all the settings (for each curve, the sequence of ordinate values are exactly the same. Given the fact that this are randomized splits over different data sets, how is this possible? \n\n-: some unclarity about the reasonableness of the made assumptions, the considered distance and the obtained results:\n\n* I would disagree to some extent that a distance based on the maximal common sub-tree is a natural distance between learned decision trees. In particular, it seems the distance will consider that a split made in the same variable but on a possibly slightly different value will lead to different trees, which is highly questionable interpretability-wise, as two trees with all the same variables but different yet close cut-points would roughly be the same for an expert, yet would be maximally different in this paper. Hence, I would like authors to clarify how much they think this distance is natural, and how much is it a convenient way to get theoretical results? \n \n* Maybe some intuition about the theorems would be good. For example, from the text alone, it appears that theorems 4.1. and 5.1. are exactly the same (at least I could not detect any textual/formal difference). Similarly, it is not clear at all whether Theorem 6.1. is in general useful, as the optimal stump making only one cut may actually have a very bad accuracy (especially at startup)? \n\n* From a non-expert view, it is very difficult to know whether the obtained theoretical results are easy derivation from previous results in the same vein, or are genuinely difficult to obtain. In connection with the above remark, it is also quite difficult to see how strongly connected those theoretical results are to the actual practical implementation/methodology, and helps in predicting the behaviours of those? Maybe a bit more intuition would be needed to fully appreciate this.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4GeaOjBFIC6", "reviewer": "Reviewer_sr4W", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The authors propose a method to stabilize decision tree learning by randomizing the decision rule for selecting the split. The authors prove several theorems that quantify the accuracy / stability tradeoff, and perform experiments on several datasets of varying sizes to demonstrate the tradeoff in practice.", "summary_of_the_review": "A simple modification to standard tree-building procedures provides some nice guarantees about model stability with respect to ablation of small amounts of training data.  The paper is well-written and technically sound.  The main contribution seems to be the theoretical analysis that precisely quantifies the accuracy and sensitivity bounds. The experimental results do show a tradeoff occurs in practice, somewhat in contradiction to the abstract.\n", "strength_and_weaknesses": "Strengths\nClear, well-written, principled approach to an important problem. The theoretical results clearly and cleanly demonstrate the performance tradeoffs. The analysis provides stronger bounds than those available from standard DP technique.\n\nWeaknesses\nThe claim in the abstract - “The experimental results on real-world datasets demonstrate that the proposed algorithm achieves a low average sensitivity with an insignificant decrease in accuracy” - seems not justified. If I understand figure 4 correctly, there is in fact a significant decrease in accuracy for low sensitivity approaches, on many of the datasets.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster