The power of choices in decision tree learning
Authors: Guy Blanc
Jane Lange
Chirag Pabbaraju
Li-Yang Tan
Venue: Submitted to ICLR 2023 (2023)
Keywords: Decision Trees
Decision Tree Learning
Top-k
ID3
Greedy Algorithms

Abstract: We propose a simple and natural generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4.5, and CART.   These classic algorithms, which have been central to machine learning for decades, are greedy in nature: they grow a decision tree by iteratively splitting on the "best" attribute.  We augment these algorithms with an additional greediness parameter $k$ and our resulting algorithm, Top-$k$, considers the $k$ best attributes as possible splits instead of just the single best attribute.

We demonstrate, theoretically and empirically, the power of this  simple generalization.  We first prove a sharp greediness hierarchy theorem showing that for every $k\in \mathbb{N}$, Top-$(k+1)$  can be much more powerful than Top-$k$: there are data distributions for which the former achieves accuracy $1-\epsilon$, whereas the latter only achieves accuracy $\frac{1}{2}+\epsilon$.  We then show, through extensive experiments, that Top-$k$ compares favorably with the two main approaches to decision tree learning: classic greedy algorithms and more recent "optimal decision tree" algorithms.  On one hand, Top-$k$ consistently enjoys significant accuracy gains over the greedy algorithms across a wide range of benchmarks, at the cost of only a mild training slowdown.  On the other hand, Top-$k$ is markedly more scalable than optimal decision tree algorithms, and is able to handle dataset and feature set sizes that remain beyond the reach of these algorithms.  

Taken together, our results highlight the  potential practical impact of the power of choices in decision tree learning.

Under review as a conference paper at ICLR 2023
THE POWER OF CHOICES IN DECISION TREE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We propose a simple and natural generalization of standard and empirically suc- cessful decision tree learning algorithms such as ID3, C4.5, and CART. These classic algorithms, which have been central to machine learning for decades, are greedy in nature: they grow decision tree by iteratively splitting on the "best" attribute. We augment these algorithms with an additional greediness parameter k and our resulting algorithm, Top-k; considers the best attributes as possible splits instead of just the single best attribute.
We demonstrate, theoretically and empirically, the power of this simple gener- alization. We first prove a sharp greediness hierarchy theorem showing that for every k IN, Top-(k 1) can be much more powerful than Top-k: there are data distributions for which the former achieves accuracy 1 é, whereas the latter only achieves accuracy + We then show, through extensive experiments, that Top-k compares favorably with the two main approaches to decision tree learning: classic greedy algorithms and more recent "optimal decision tree" algorithms. On one hand, Top-k consistently enjoys significant accuracy gains over the greedy algorithms across wide range of benchmarks, at the cost of only mild training slowdown. On the other hand, Top-k is markedly more scalable than optimal deci- sion tree algorithms, and able to handle dataset and feature set sizes that remain beyond the reach of these algorithms.
Taken together, results highlight the potential practical impact of the power of choices in decision tree learning.
INTRODUCTION
Decision trees are a fundamental workhorse in machine learning. Their logical and hierarchical structure makes them easy to understand and their predictions easy to explain. Decision trees are therefore the most canonical example of an interpretable model: in his influential survey (Breiman) 2001b), Breiman writes "On interpretabilityy trees rate A+"; much more recently. the sur- vey Rudin et al. (2022) lists decision tree optimization as the very first of 10 grand challenges for the field of interpretable machine learning. Decision trees are also at the heart of modern ensemble methods such as random forests (Breiman) 2001a) and XGBoost (Chen & Guestrin 2016), which
achieve state-of-the-art accuracy for wide range of tasks.
Greedy algorithms such as ID3 (Quinlan 1986). C4.5 (Quinlan 1993). and CART (Breiman et al., 1984) have long been the standard approach decision tree learning. These algorithms build decision tree from labeled data in a top-down manner, growing the tree by iteratively splitting on the "best" attribute as measured with respect certain potential function (e.g. information gain). Owing to their simplicity, these algorithms are highly efficient and scale gracefully to handle mas- sive datasets and feature set sizes, and they continue be widely employed in practice and enjoy significant empirical success. For the same reasons, these algorithms are also part of the standard curriculum in introductory machine learning and data science courses.
The trees produced by these greedy algorithms are often reasonably accurate, but can nevertheless be suboptimal. There has therefore been a separate line of work, which we overview in incSccoon 2, on algorithms that optimize for accuracy, and in fact, seek to produce optimally accurate decision trees. These algorithms employ a variety of optimization techniques (including dynamic programming, integer programming, and SAT solvers) and completely different from the simple greedy algo- rithms discussed above. Since the problem of finding an optimal decision tree has long been known to be NP-hard (Hyafil & Rivest 1976), any algorithm must suffer from the inherent combinatorial

---

Under review as a conference paper at ICLR 2023
explosion when the instance size becomes sufficiently large (unless P-NP). Therefore, while this line of work has made great strides in improving the scalability of algorithms for optimal decision trees, dataset and feature set sizes in the high hundreds understandably remain out of reach.
This state of affairs raises a natural question:
Can we design decision tree learning algorithms that improve significantly on the accuracy of classic greedy algorithms and yet inherit their simplicity and scalabil- ity?
In this work, we propose new approach and make the case that it provides strong affirmative answer to the question above. We further show that it opens up several new avenues for exploration in both the theory and practice of decision tree learning.
1.1 OUR CONTRIBUTIONS
1.1.1 TOP-k: A SIMPLE AND EFFECTIVE GENERALIZATION OF CLASSIC GRBEDY DECISION TREE ALGORITTMS
We introduce easily interpretable greediness parameter to the class of all greedy decision tree algorithms, a broad class that encompasses ID3, C4.5, and CART. This parameter, k, represents the number of features that the algorithm considers candidate splits at each step. Setting k recovers the fully greedy classical approaches, and increasing ls allows the practitioner to produce more accurate trees at the cost of only a mild training slowdown. The focus of our work is on the regime where k is small constant a primary objective of our work work-although we mention here that by setting to be the dimension d, our algorithm produces an optimal tree. Our overall framework can thus be viewed as interpolating between greedy algorithms at one extreme and "optimal decision tree" algorithms at the other, pre- cisely the two main and previously disparate approaches to decision tree learning discussed above.
the efficiency and scalability of greedy algorithms is
We will now describe our framework. A feature scoring function H takes as input a dataset over binary features and specific feature [d], and returns a number quantifying the "desirability" of this fcature as the root of the tree. The greedy algorithm corresponding to H. selects as the root of the tree it builds the feature that has the largest score under H; our generalization will instead consider the 1 features with the & highest scores.
Definition 1 (Feature scoring function). A feature scoring function H. takes as input a labeled dataset S over a d-dimensional feature space, a feature E [d], and returns a score vs E [0, 1).
See Section 3.T for a discussion of the feature scoring functions that correspond to standard greedy algorithms ID3, C4.5, and CART. Pseudocode for Top-k is provided in |Figure I We note that from the perspective of interpretability, the trained model looks the same regardless of what is. During training, the algorithm considers more splits, but only one split is eventually used at each node.
1.1.2 THEORETICAL RESULTS ON THE POWER OF TOP-k
The search space of Top-(k (k + 1) is larger than that of Top-k; and therefore its training accuracy is certainly least as high. The first question we consider is: Is the test accuracy of Top-(k + 1) only marginally better than that of Top-k, or are there examples of data distributions for which even a sin- gle additional choice provably leads to huge gains in test accuracy? Our first main theoretical result is a sharp greediness hierarchy theorem, showing that this parameter can have dramatic impacts on accuracy, thereby illustrating its power:
Theorem (Greediness hierarchy theorem). For every E > 0, k, h E IN, there is a data distribution on which Top-(k- 1) achieves at least 1- accuracy with depth budget of h, but Top-k achieves at most 3 + e accuracy with a depth budget of h.
Theorem is special case of a more general result that we show: for all l < K. there are data distributions on which Top-K achieves maximal accuracy gains over Top-k, even Top-k allowed a larger depth budget:
Theorem 2 (Generalization of Theorem 1p. For every e 0, k. K, h E IN where k < K, there is a data distribution on which Top- K achieves at least 1 - accuracy with a depth budget of h, but Top-k achieves at most 1 + accuracy even with depth budget of h + (K- k 1).
2

---

Under review as a conference paper at ICLR 2023
Top-k(H,, Sh))
Given: A feature scoring function H. labeled sample set S over d dimensions, and depth budget
Output: Decision tree of depth that approximately fits S.
1. If = O, or every point S has the same label, return the constant function with the best accuracy w.r.t. S.
2. Otherwise, let I S [d] be the set of k coordinates maximizing H(S, i).
3. For each E I, let T; be the tree with
Root = I
Left subtree Top-k (H, Sn;=0, h Right subtree = Top-k (H, Sp,=1, 1),
where Sz,=b is the subset of points in S where 2; b.
4. Return the T, with maximal accuracy with respect S among all choices of I.
Figure 1: The Top-k algorithm. be instantiated with any feature scoring function H. and when k == 1, recovers standard greedy algorithms such as ID3, C4.5, and CART.
The proof of [Teorrmm 2] is simple and cleanly highlights the theoretical power of choices. One downside, though, is that it is based on data distributions that are admittedly somewhat unnatural: the labeling function has embedded within a function that the XOR of certain features, and real- world datasets are unlikely to exhibit such adversarial structure. To address this, we further prove that the power of choices evident even for monotone data distributions.
Theorem (Greediness hierarchy theorem for monotone data distributions). For every E > 0, depth budget h, K between (2(h) and Ō(h²) and k S K h. there is a monotone data distribution on which Top-K achieves least accuracy with a depth budget of h, but Top-k achieves at most accuracy with depth budget of h.
Many real-world data distributions are monotone in nature, and relatedly, they are common as- sumption and the subject of intensive study in learning theory. Most relevant to this paper, recent theoretical work has identified monotone data distributions as a broad and natural class for which classical greedy decision tree algorithms (i.e. Top-1) provably succeed (Blane al. 2020b a). The- orem 3) shows that even within this class, increasing the greediness parameter can lead to dramatic gains accuracy. Compared to Theorem 2] the proof Theorem i more technical and involves the use of concepts from the Fourier analysis of boolean functions [O'Donnell] 2014).
We note that a weaker version of Theorem is implicit in prior work: 2020b Theorem 7b) and (Blanc et al. 2021b Theorem 2) yields the special case of Theorem where K = Ol:2) and K l much smaller.
Combining (Blanc et al.)
Theorem 3 is significant strengthening as allows for h: > and
1.1.3 EXPERIMENTAL RESULTS ON THE POWER OF TOP-k
We provide extensive empirical validation of the effectiveness of Top-k when trained on real- world datasets, and provide an in-depth comparison with both standard greedy algorithms as well as optimal decision tree algorithms.
We first compare the performance Top-k for = 1,2,3, 4 FFgure 2). and find that increasing k does indeed provide significant increase in test accuracy in number of cases, Top-4 already achieves accuracy that is comparable to the test accuracy attained by MurTree (Demirović et al.) 2022). state-of-the-an optimal decision tree algorithm. We further show, in miFigures 3 Jandd [4] that Top-k inherits the efficiency of popular greedy algorithms, and furthermore scales much better than the optimal decision tree algorithms MurTree and GOSDT (Lin et al. 2020).
3

---

Under review as a conference paper at ICLR 2023
Taken a whole, our experiments demonstrate that Top-k provides a useful middle ground be- tween greedy and optimal decision tree algorithms: It is significantly more accurate than greedy algorithms, but still fast enough to be practical reasonably large data sets, See (Section 5| for an in-depth discussion of our experiments. Finally, we emphasis the benefits afforded by the simplic- ity of Top-k. Standard greedy algorithms (i.e. 1op-1) are widely employed and easily accessible. Introducing the parameter & requires modifying only a tiny amount of source code and gives the practitioner a new lever control. Our experiments and theoretical results demonstrate the utility of this simple lever.
2 RELATED WORK
Provable guarantees and limitations of greedy decision tree algorithms. long and fruitful line of work seeks to develop rigorous understanding of the performances of greedy decision tree learning algorithms such as ID3, C4.5, and CART, and to place their empirical success on firm theoretical footing (Kearns & Mansour 1996 Kearns 1996 Dietterich et al. 1996: Brutzkus
ct al. 2019; 2020 Blanc et al.] 2020b aj 2021a). These works identify feature and distributional assumptions under which these algorithms provably succeed; they also highlight the limitations of these algorithms by pointing out settings on which they provably fail. Our work complements this line of work by showing, theoretically and empirically, how these algorithms can be further improved with a simple new parameter while preserving their efficiency and scalability.
The work Blanc al. (0211)) Recent work of Blanc et al. also highlights the power of choices in decision tree learning. However, they operate within a stylized theoretical setting. First, they consider a specific scoring function that is based on a notion of influence of features, and crucially, computing these scores requires query access to the target function (rather than from random labeled samples as is the case in practice). Furthermore, their results only hold with respect to the uniform distribution. These are strong assumptions that limit the practical relevance of their results. In contrast, a primary focus of this work is to be closely aligned with practice, and in particular, our framework captures and generalizes the standard greedy algorithms used in practice.
Optimal decision trees.
Motivated in part by the surge of interest in interpretable machine learn- ing and the highly interpretable nature of decision trees, there have been numerous works on learning optimal decision trees (Bertsimas & Dunn
2017 Verwer & Zhang 2017 2019 9 Aghaei et al. 2019
Zhu et al. |020 Verhaeghe et al., |0200 Narodytska et al. 2018 Avellaneda 2020 Janota & Mor-
gado 2020; Nijssen & Fromont 2007 2010 Hu et al. 2019: Lin et al. 2020; Demirović et al.
2022 As mentioned in the introduction, this is NP-complete problem (Hyafil & Rivest 1976)
indeed, it is harhard to find even an approximately optimal decision tree (Sieling 2008 Adler &
Heeringa 2008 Alekhnovich et al., 2009). Due to the fundamental intractability of this problem,
even highly optimized versions of algorithms are unlikely to match the scalability of standard greedy algorithms. That said, these works implement a variety of optimizations that allow them build optimal decision trees for many real world data sets when the data set and feature sizes are in the hundreds and the desired depth small (== or less).
Finally, another related line of work is that of soft decision trees Trso et al. 2012 Tanno et al.
2019. These works use gradient-based methods learn soft splits at each internal node. We believe that one key advantage of our work over these soft trees is in interpretability. With Top-k, since the splits are hard (and not soft), to understand the classification of a test point, it sufficient to look at only one root-to-leaf path, as opposed to a weighted combination across many.
3 THE TOP-k ALGORITHM
3.1 BACKGROUND AND CONTEXT: IMPURITY-BASER ALGORITHMS
Greedy decision tree learning algorithms like ID33, C4.5 and CART are all instantiations of Top-k: in Figure with k = and an appropriate choice of the feature-scoring function H. Those three algorithms all used impurity-bsse heuristics their feature-scoring function:
Definition 2 (Impurity-base based heuristic), An impurity function G |0, 1] + [0.1] is a function that
is concave, symmetric about 0.5, and satisfies (())= G(1) = 0 and ((0.5) 1. A feature-scoring
4

---

Under review as a conference paper at ICLR 2023
function H is an impurity- impurity-based based heuristic, there is some impurity function G for which:
H(S, g
E (19
2. 0.y-
Pr x = 0] 2.305
E 2 2.y0
y x;
= =0)
Pr la: = 11.9 w.yrr
E
2; ===]]
where in each of the above, (x. y) are a uniformly random point from within S.
Common examples for the impurity function include the binary entropy function, G(p)
(p) (1 p) logg(1 p) (used by ID3 and C4.5), the Gini index G(p) 4p(1 P) (used
by CART), and the g(p) = 2 2vp(1 - p) (proposed and analyzed in Kearns Mansour 1999)). ). We
refer to the reader to Kearns & Mansour (1999) for theoretical comparison, and Dietterich et al. (996) for an experimental comparison, of these impurity- -based heuristics.
Our experiments focus Gini index being the impurity measure, but theoretical results apply to Top-k instantiated with any impurity-bars -aurity-based heuristic.
3.2 BASIC THEORETICAL PROPERTIES OF THE TOP-k ALGORITIIM
Running time. The key behavioral aspect in which Top-k differs from greedy algorithms is that it is less greedy when trying to determine which coordinate to query. This naturally increases the running time of Top-k, but that increase is fairly mild. Concretely, say that Top-k is run on a dataset S with n points. We can then easily derive the following bound on the running time of Top-k. where H(S, i) is assumed to take (n) time to evaluate (as does for all impurity-basee heuristics). Claim 3.1. The running time of To, S. h) is O((k)) nd).
Proof. Let Th be the number of recursive calls made by Top-k S, h). Then, we have the simple recurrence relation Th 2-TT--1. where To = 1. Solving this recurrence gives Th = (2k)*. Each recursive call takes (nd) time, where the bottleneck is scoring each the d features.
We note that any decision tree algorithm, including blazingly fast greedy algorithms such ID3, C4.5, and CART, has runtime that scales exponentially with the depth, h. The size of depth-h can be 2h, and this of course a lower bound on the runtime such a tree. In particular, contrasting the rumning time of Top-k with greedy algorithms (for which 1), Top-k incurs an additional k cost in running time. As mentioned earlier, in practice, we are primarily concerned with fitting small decision trees (e.g., h 5) to the data, as this allows for explainable predictions. this regard, the additional ksh cost is inexpensive, as confirmed by our experiments.
the algorithm needs output
The search space of Top-k: We state and prove a simple claim that Top-k returns the best tree within its search space.
Definition 3 (Search space of Top-k). Given a sample S and integers h, k, we use Tk. to refer to all trees in the search space of Top-k. Specifically, if = O, this contains all trees with height of zero (the constant and constant trees). For h 2 1, and I C [d] being the k coordinates with maximal score, this contains all trees with root of xs, left subtree in Tk. - and right subtree in Tu S,, for some E I.
Lemma 3.2 (Top-k chooses the most accurate tree in its search space). For any sample S and integers h, k, let T be the output of Top-k with depth budget of l on S. Then,
Pr (T)) = =b vi).
Pr (Tx)==))) S
=
max T'ETkE
We refer the reader to Appendix A for the proof of this lemma.
Parallelizability. We observe Top-k k is largely amenable to parallelization. Observe that each of the 24 recursive calls in Step 3 of the pseudocode can be assigned to separate processor. This means that given (2k)a processors, a carefully engineered implementation of Top-k can enjoy a parallel running time of ((hdd), which is also the parallel running time of standard greedy algorithms.
5

---

Under review as a conference paper at ICLR 2023
4 THEORETICAL BOUNDS ON THE POWER OF CHOICES
We refer the reader to the Appendix B for most of the setup and notation. For now, we briefly mention a small amount of notation relevant to this section: We use bold font (e.g. x) denote random variables. We also use bold font to indicate stochastic functions which output a random variable. For example.
with probability S
f(x)= x with probability
is the stochastic function that returns either the identity or its negation, each with equal probability. To define the data distributions Theorems 2 [nd we will give a distribution over the domain, X and the stochastic function that provides the label given an element of the domain.
4.1 PROOF OF THEOREM
For each depth budget h and search branching factor K, we will define a hard distribution Dr.K that is learnable to high accuracy by Top-K with depth of h, but not by Top-k with depth of h' for any h' < h + K k. This distribution will be over {0, 1] x {0, 1). where d h + K 1. The marginal distribution over {0, 1]d is uniform, and the distribution over (0, 1) conditioned
setting of the d features given by the stochastic function f (xr). All of the results of this section
Theorems 2 and 3) hold when the feature scoring function is any impurity- based heuristic.
Description of (x)), Partition x into two sets of variables, a+4) of size h and (2) of size K - Let fr.K (x) be the randomized function defined as follows:
(x) = Par (zr(1)
with probability 1
(2) x
chosen uniformly at random from x:
with probability E.
The definition of Para (x(1)) can be found in Appendix B
The proofTheoren 2jis divided into two components. First, we prove that when the data distribution is Dr,K. Top-K succeeds in building a high accuracy tree with a depth budget of h. Then, we show that Top-k fails and builds a tree with low accuracy, even given a depth budget of h + (K k 1).
Lemma 4.1 (Top-K succeeds). The accuracy of Top-K with depth of h Dr, is at least c.
Lemma 4.2 (Top-k fails). The accuracy of Top-k with a depth of h on Dr. K is at most (1/2 + e) for any h' + K.
Proofs of both these lemmas are deferred to Appendix B
4.2 PROOF OF THEOREM
In this section, we overview the proof Theorem 3 restated for convenience. Some of the proofs are deferred to Apppendix B.2
Theorem 4 (Greediness hierarchy theorem for monotone distributions). For every budget h. between (i(h log h) and O(h h1) and < K h, there is a monotone data distribution on which Top-K achieves at least 1 accuracy with depth budget of h, but Top-k: achieves at most 0.5 + E accuracy with depth budget of h.
O, depth
Before proving Theorem 4 we'll formalize monotonicity. For simplicity, we'll assume the domain is the Boolean cube, 1. and use the partial ordering < x' iff x; < x/ for each i E [d]: however, the below definition easily extends to the domain being any partially ordered set.
Definition 4 (Monotone). A stochastic function, f : 10, + 13, is monotone if. for any x, x' E 13d where x N z', E[f(x)] < E[f(x')]. A data distribution, D over 10. {0. 1} said to be monotone if the corresponding stochastic function, f (x) returning (y x z) where (æ. v) D, is monotone.
To construct the data distribution of Theorem& 4, we will combine monotone functions, Majority and Tribes, commonly used in the analysis of Boolean functions due to their extremal properties. See

---

Under review as a conference paper at ICLR 2023
Appendix B.2 for their definitions and useful properties. Let d h + 1, and the distribution over the domain be uniform over {0, 1]d. Given some I E {0, 1]d, we'll use xx41) to refer to the first h coordinates of z and 2²(2) the other K - coordinates. This data distribution is labeled by the stochastic function f given below.
(Tribess(x" far)= = MMajx-1 (x(21)
with probability 1 with probability
Clearly f is monotone as it is the mixture of two monotone functions. Throughout this subsection, we'll use D to refer to the data distribution over {0, 1) x {0, 1] where to sample (x, y) ~ DD we first draw æ ~ {0, 1]dd uniformly and then y from f(x). The proof of Theorem is a direct consequence of the following
Lemmas, both of which we prove in An/ppeidi B.2
Lemma 4.3 (Top-K succeeds). On the data distribution Dr,K, Top-K with a depth budget of h achieves at least - E accuracy.
Lemma 4.4 (Top-k fails). On the data distribution Da,K, Top-k with a depth budget of achieves at most + E accuracy.
EXPERIMENTS
Setup for experiments. At all places, unless otherwise specified, the Top-1 tree that we compare to is that given by scikit-lears (Pedregosa et al. 2011), standard library for machine learning algorithms. We run experiments on variety datasets from the UCI Machine Learning Reposi- tory (Dua & Graff, 2017) (numerical well categorical features) having a size in the thousands and having x 50- 300 features (after binarization). There were s 100 data sets meeting these criteria, and we took random subset of 20 such datasets. We binarize all the datasets for cate- gorical datasets, we convert every categorical feature that can take on (say) & values into binary features. For numerical datasets, we sort and compute thresholds for each numerical attribute for an appropriate number of thresholds, so that the total number of binary features is 2 100. A detailed description of the datasets is given in Appendix
We build decision trees corresponding to both gini and entropy as the impurity measure H. and report numbers for whichever of the two performed better on the test set (the trends are the same even if we fix the impurity measure). A simple implementation of the Top-k algorithm and other technical details for the experiments will be made publicly available.
5.1 KEY EXPERIMENTAL FINDINGS
Small increments of is yield significant accuracy gains. Since the search space of Top-k is superset of that of Top-1 for any A: > 1, the training accuracy of Top-k is guaranteed to be larger. The primary objective in this experiment is show that Top-k can outperform Top-1 in terms of test accuracy as well. Figure 2 shows the results for Top-1 versus Top-k for k = 2, 3, 4: each plot different dataset, where on the x-axis, we plot the depth of the learned decision tree, and on the y-axis, we plot the test accuracy. We also plot the test accuracy of an optimal decision tree (MurTree) in each plot as an additional point of reference We can clearly observe that the test accuracy increases as & increases-in some cases, the gain is > 5%-and for several datasets, the accuracy of Top-4 close to that of MurTree.
Top-k inherits the efficiency and scalability of greedy algorithms. Since Top-k invests more computation towards fitting better tree on the training set, its training time is naturally longer than 1op-1. However, our experiments show that the slowdown is fairly mild, especially compared the optimal decision tree algorithm MurTree. As stated in Claim 3.1 the running time of Top-k run to depth budget of h on dataset of size having d binary attributes is O(2k)* nd). Thus, if we were to plot the running time of Top-k in log-scale as function of the depth h, we would expect to see linear behaviour with slope log(2k). Concretely, Top-1 should differ from Top-k only in its
'This number should be agnostic to what algorithm is computing the optimal tree, and hence we only compute it for MurTree, since it scales up much better than GOSDT (furthermore, the GOSDT tree is not exactly optimal unless the regularization coefficient is set 0).

---

Under review as a conference paper at ICLR 2023
nursery
occupancy-esimmation
mi-prove
artiffcial-chaarctes
0.755
0,990
Test fecurecy
Tee Securccy
0.33
0.080
0.46
6.955
0.66
Desth spambase
Deptt
Depth
Depith
aviis
dry try-bean
telescope
1.0
4.85
0.41
Test A00UU00
0.75
Sall Aocusesyy
0.08
Selt Accurascy
2.00
2.2
0.60
3.00
2.00
Death cornect-4
Desth lester-recoghiton
Depth miniboone
Dopth
sersorless--riiee sirbsrlleedddiveddgggnosss
0.5
Teet Accurcyy
5.74
Accuracy
Teni Accurscyy
0.58-
Test
6.8
0.2
Desth
Desth
Depth
Depth
Top-1
Mur
Figure 2:
Test accuracy comparison between Top-1, Top-k and MurTree. We can see that Top- k ++1 generally obtains higher accuracy than Top-k for k: = 1, 2, 3, and in some cases, Top-4's accuracy is even comparable to MurTree's. As the dataset size increases, the missing points for MurTree indicate segmentation fault (possibly due to excessive memory requirements) before the tree-building process was completed.
slope, but the behaviour for both should be linear. Figure 4 behavior. Also, we can very well see that MurTree could not build a decision tree of depth 5 and beyond on the larger datasets, indicating that optimal decision trees do not scale up well (more on this ahead).
in Appendix D confirms this expected
Finally, note that we plot two lines for Top-1: Top-1 (sklearn), which is given by sci toikittless rn (and has much better training time) and also Top-1 (basic), where we simply substitute implementation of Top-k (which has comparatively slower training time; in fact, sklearn is se 20x faster). This is simply to highlight the fact that our implementation of Top-k can be made much more efficient by subjecting it to all the optimizations present in scikits melkkitleaand learn's implementation of ID3. We also verified that the accuracies (training and test) for Top-1 (sklearn) and Top-1 (basic) match, they are building the same trees.
in our
Top-k scales much better than optimal decision tree algorithms. Despite having an optimality certificate, optimal decision tree algorithms suffer lot in running time compared to ID3. Here, empirically demonstrate that in comparison, Top-k suffers a significantly more benign blow-up in training time. The experiment is identical to that in Figures 14, 15 in the GOSDT paper (Lin al.) 2020). where two notions of scalability are considered. In the first experiment, we fix the number of samples, and gradually increase the number of features to train the decision tree. In the second experiment, we include all the features, but gradually increase the number of samples to train on. The dataset under consideration is the FICO (FICO al. 2018) dataset, which has a total of 1000 samples having 1407 binary features. On the x-axis, we plot the number of features/samples, and on the y-axis, we plot the training time (in seconds) taken by optimal tree algorithms (MurTree, GOSDT) and Top-k. We do this for depth = 4, 5. 6 (for GOSDT, the regularization coefficient À is set to 2 depth, Figure 3 has the results we can observe that the training time for both MurTree and GOSDT blows up in a much more drastic manner as compared to Top-k, in both the experiments. In particular, for depth = 5. both MurTree and GOSDT couldn't finish building a tree on 300 features within the time limit of 10 minutes, while Top-4 completed execution even with all the 1407 features. Similarly, in the latter experiment, GOSDT/MurTree couldn't 't build a depth-5 tree on 150 samples within the time limit, while Top-4 comfortably finished execution even 1000 samples. This
8

---

Under review as a conference paper at ICLR 2023
600
600
600
Top-1
Top-1
Tap-1
Top-2
Top 2
Top-2
400
Top-4
Top-3
400-
Top 4
Top-3
400-
Tap-
Top-
300
G05DT
300-
GOSDT
GOSDT Mareee
Mur
Murfise
200
200-
200
100
L03
0
250
650
0
200
1400
1200 1400
Number Teatures
Number of Feurures
Number of Festures
(a) Depth = 4
(b) Depth = 5
(c) Depth = 6
600
600
000
Top-1
To-11
Trp-1
Top 2
To 2
Top 2
400
Tep-4
Tep-3
400
kpp-
1op-3
40D-
Top-4
Tep-3
GDSDT
COSDT
Time
GOSDT
Nu/Toe
Marile
NurThc
200
200
20D-
0
230
403
1000
0
202
400
6.00
850
1003
200
800
800
1.00
Number of Samples
Number of Samples
Number of Samples
(d) Depth 4
(c) Depth 5
(f) Depth =
Figure 3: Training time comparison between Top-k k and optimal tree algorithms. As the nummber of fcatures/samples increases, both GOSDT and MurTree scale poorly compared to Top-k, and beyond threshold, do not complete execution within the time limit.
nicely illustrates the scalability issues with optimal tree algorithms. Combined with the accuracy gains seen in the previous experiment, Top-k can thus be seen as achieving a nice bargain in the tradeoff between training time and accuracy
6 CONCLUSION
We have shown how popular and empirically successful greedy decision tree learning algorithms can be improved with the power of choices: our generalization, Top-k, considers the best features as candidate splits instead of just the single best one. As our theoretical and empirical results demon- strate, this simple generalization is extremely powerful, enabling significant accuracy gains while preserving the efficiency and scalability of standard greedy algorithms. Indeed, we find it surprising that such a simple generalization has not been considered before.
There is much more to be explored and understood, both theoretically and empirically; list here few concrete directions that we find particularly exciting and promising. First, we suspect that power of choices affords more advantages over greedy algorithms than just accuracy gains. For example, an avenue for future work to show that the trees grown by Top-k are more noise tolerant. Second, there principled approaches the automatic selection of the greediness parameter k?? Can the optimal choice be inferred from a few examples or learned over time? This opens up the possibility of new connections to machine-learner advice and algorithms with predictions (Mitzenmacher & Vassilvitskii 2020). an area that has seen surge of interest in recent years. Finally, as mentioned in the introduction, standard greedy decision tree algorithms are at the very heart of modern tree-based ensemble methods such as XGBoost and random forests. A natural next step is to combine these algorithms with Top-k and further extend the power of choices to these settings.
We also ran an experiment comparing accuracy with Soft Decision Trees Irsoy et al. 2012 We found that their code took significantly longer to train (often 1-2 orders of magnitude) than both Top-3 and Top-4 trained to the same depth. For accuracy. it seems that each method has data sets where it performs better; however, when Soft Decision Trees has more accuracy, it is typically by very small amount. In contrast, in the other cases, Top-k often has drastic accuracy gain.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Micah Adler and Brent Heeringa. Approximating optimal binary decision trees. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pp. 1-9, Springer, 2008.
Sina Aghaei, Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for non-discriminative decision-makin In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1418-1426, 2019.
Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, and Toniann Pitassi. The complexity of properly learning simple concept classes. Journal of Computer & System Sciences, 74(1):16-34, 2009.
Florent Avellaneda. Efficient inference of optimal decision trees. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 34, pp. 3195-3202, 2020.
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039- 1082, 2017.
Guy Blanc, Jane Lange, and Li- Yang Tan. Provable guarantees for decision tree induction: the ag- nostic setting. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020a.
Guy Blanc, Jane Lange, and Li- Yang Tan. Top-down induction of decision trees: rigorous guarantees and inherent limitations. In Proceedings of the I Ith Innovations Theoretical Computer Science Conference (ITCS), volume 151, pp. 1 1-44, 2020b.
Guy Blanc, Jane Lange, Mingda Qiao, and Li- Yang Tan. Decision tree heuristics fail, even in the smoothed setting. In Mary Wootters and Laura Sanità (eds.), Proceedings of the 25th Interna- fional Conference on Randomization and Computation (RANDOM), volume 207, pp. 45:1-45:16, 2021a.
Guy Blanc, Jane Lange, Mingda Qiao, and Li- Yang Tan. Properly learning decision trees al- most polynomial time. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2021b.
Ieo Breiman. Random forests. Machine learning, 45(1):5-32, 2001a
Leo Breiman. Statistical Modeling: The Two Cultures (with comments and a rejoinder by the author). Statistical Science, 16(3):199 231, 2001b. doi: 10. 00.2114//10099213726. URL httpst ptt.s/ssooo0022221 1tte://o..11//sss//saaaa
Leo Breiman, Jerome Friedman, Charles Stone, and Richard Olshen. Classification and regression Irees. Wadsworth International Group, 1984.
Alon Brutzkus, Amit Daniely, and Eran Malach. On the Optimality of Trees Generated by ID3. ArXiv, abs/1907. abs/1907.05444, 2019.
Alon Brutzkus, Amit Daniely, and Eran Malach. ID3 learns juntas for smoothed product distribu- tions. In Proceedings of the 33rd Annual Conference Learning Theory (COLT), pp. 902-915, 2020.
Tianqi Chen and Carlos Guestrin. Xghoost: scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 785-794, 2016.
Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Peter J Stuckey. Murtree: Optimal decision trees dynamic programming and search. Journal of Machine Learning Research, 23(26):1-47) 2022.
Tom Dietterich, Michael Kearns, and Yishay Mansour. Applying the weak learning framework to understand and improve C4.5. In Proceedings of the 13th International Conference on Machine Learning (ICMI), pp. 104, 1996.
10

---

Under review as a conference paper at ICLR 2023
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL UtLpttp::/arccive ics. uci. ucci.edumm.
FICO, Google, Imperial College London, MIT, University of Oxford, UC Irvine, and UC Berke- ley. Explainable Machine Learning Challenge. https: wttp//itmmmnncccc/oo/ee/....mm.t fico. com/s/ hht.ccchhheeeeearannnacaaaalleee
2018.
Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. Advances in Neural Information Processing Systems, 32, 2019.
Laurent Hyafil and Ronald L. Rivest. Constructing optimal binary decision trees is npmcompee Information Processing Letters, 5(1):15-17. 1976. ISSN 0020-0190. doi: https://oii.on org/
10.1016/00220-019907)))0)0000000
URL https: //t:://wwww.. sci encedi rect. article/pii 90766000000000000000000090000000
com.ct.ccommee www.coocccooo.oooo sc ence/
Ozan Insoy, Olcay Taner Yıldız, and Ethem Alpaydm. Soft decision trees. In Proceedings of the 21 international conference on pattern recognition (ICPR2012), pp. 1819-1822. IEEE, 2012.
Mikoláš Janota and António Morgado. SAT based encodings for optimal decision trees with explicit paths. In International Conference on Theory and Applications of Satisfiability Testing, pp. 501- 518. Springer, 2020.
Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on boolean functions. In Pro- ceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS), pp. 68-80, 1988.
Michael Kearns. Boosting theory towards practice: recent developments in decision tree induction and the weak learning framework (invited talk). In Proceedings of the 13th National Conference on Artificial intelligence (AAAI). pp. 1337-1339, 1996.
Michael Kearns and Yishay Mansour. On the boosting ability of top-down decision tree learning algorithms. In Proceedingy of the 28th Annual Symposium on the Theory of Computing (STOC), pp. 459-468, 1996.
Michael Kearns and Yishay Mansour. On the boosting ability of top-down decision tree learning algorithms. Journal of Computer and System Sciences, 58(1): 1999.
Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pp. 6150-6160. PMLR, 2020.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. arXiv preprint arXiv:2006.001133 2020.
Nina Narodytska, Alexey Ignatiev, Filipe Pereira, and Joao Marques-Silva. Learning optimal deci- sion trees with sat. In Ijcai, pp. 1362-1368, 2018.
Siegfried Nijssen and Elisa Fromont. Mining optimal decision trees from itemset lattices. In Pro- ceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 530-539, 2007.
Siegfried Nijssen and Elisa Fromont. Optimal constraint-based decision tree induction from itemset lattices. Data Mining and Knowledge Discovery, 21(1):9-51, 2010.
Ryan O' O'Donelll Analysis of Boolean Functions. Cambridge University Press, 2014.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Ross Quinlan. Induction of decision trees. Machine learning, 1(1):81-106, 1986.
Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993. ISBN 1558602402.

---

Under review as a conference paper at ICLR 2023
Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong. In- terpretable machine learning: Fundamental principles and 10 grand challenges. Statistics Surveys, 16:1-85, 2022.
Detlef Sieling. Minimization of decision trees is hard to approximate. Journal of Computer and System Sciences, 74(3):394-403, 2008. ISSN 0022-0000. doi: https//dbo.org//1..1166/// 2007.06.014. URL https: sciencedirect. ccmm//ccienn///ttttcl/////1 S002200007000815 Computational Complexity 2003.
Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In International Conference on Muchine Learning, pp. 6166-6175. PMLR, 2019.
Hélene Verhaeghe, Siegfried Nijssen, Gilles Pesant, Claude-Guy Quimper, and Pierre Schaus. Learning optimal decision trees using constraint programming. Constraints, 25(3):226-250, 2020.
Sicco Verwer and Yingqian Zhang. Learning decision trees with flexible constraints and objectives using integer optimization. In International Conference on Al and OR Techniques Constraint Programming for Combinatorial Optimization Problems, pp. 903103. Springer, 2017.
Sicco Verwer and Yingqian Zhang. Learning optimal classification trees using binary linear pro- gram formulation. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 1625-1632 2019.
Haoran Zhu, Pavankumar Murali, Dzung Phan, Lam Nguyen, and Jayant Kalagnanam. A scalable MIP-based method for learning optimal multivariate decision trees. Advances in Neural Informa- tion Processing Systems, 33:1771-1781, 2020.
12

---

Under review as a conference paper at ICLR 2023
A PROOFS DEFERRED FROM SECTION 3
Proof of Lemma 3.2 By induction: When = 0, the only trees in the search space are the constant O and constant functions. Top-k returns which of these two trees the most accurate.
When h 2 1, let 7" be a tree with maximal accuracy within TA.ASS. As 7" is in the search space, its root must be one of the k coordinates with maximal score which form the candidate set I.
For each coordinate E I, the candidate tree T, satisfies
Pr (T((a) + y) Pr x~ l1 = w.y~S
Pr Pr (oo()) + y) Pr = Pr Tu( + y), E.y~s
a.yrs
where Ta and Ta the left and right subtrees of T; respectively. Each of Tin and Ta is output of Top-k with a depth budget of 1. We assume as the inductive hypothesis that each these minimizes error among all trees h1, and 1,5,-1 respectively; therefore the candidate T, minimizes error among all trees in Tk.h.s that have H; at the root. Since Top-k chooses the most accurate of the Ti's, it follows that the chosen tree minimizes error among all trees in TR.A.S.
B PROOFS DEFERRED FROM SECTION 4
Setup and notation: We use [t] for the indicator function, and [d] to refer the set (1....,d} dd.
For brevity, we'll make two simplifying assumptions about Top-k:
We will assume Top-k builds non-redundant trees, meaning on every root-to-leaf path, each coordinate is queried at most once. This is easy to enforce in the pseudocode: At each step, the algorithm can track a set Q of the coordinates already queried along this path, and pick the top-k coordinates according to the feature score function among [d]] \ Q. For brevity, we do not include that modification to the pseudocode in in/Figure !
2. We assume, roughly speaking, that Top-k has access to an infinite-sized sample. More pre- cisely, whenever Top-k needs to compute an expectation over its sample (to determine the set of & coordinates maximizing the scoring function, or to decide which constant function put leaf), replace the the empirical expectation with the population expectation. Using standard techniques, if the sample is large enough, these expectations will concen- trate and results still hold.
3. We assume that Top-k always build complete trees (i.e every root-to-leaf path has depth exactly h). This is without loss generality, as whenever Top-k stops early, does so because it has already achieved perfect accuracy that path.
Throughout this section, we will assume the feature scoring function is an impurity-basee based heuristic. As our data distribution is uniform on the input, we are able to use the following fact and simulta- neously prove results for all impurity-based based heuristic.
Fact B.1 (Proposition 7.7 of Blane et al. (2020b)). If the scoring function is any impurity-based heuristic, and the data distribution is uniform over inputs (æ is uniform when (x. y) D), then the score of a coordinate i is monotone increasing with its correlation with the label, E (x.y)~-D (x,y].
Fact B.1 means that, when analyzing Top-k on uniform data distributions, we are free to replace the "k coordinates with largest scores" with the "k coordinates with largest correlations."
B. PROOFS DEFERRED FROM SECTION 4.1
The stochastic function fa,K x used throughout Lemma 4.1 and Lemma 4.2 combines function that outputs random one features with the h-wise parity function.
Definition 5 (Parity). The parity function of i variables, indicated by Parę {0, 13 {0, 1}, returns
Pare(x)) ==
Σ sELE
mod 2.
13

---

Under review as a conference paper at ICLR 2023
Fact B.2 (Computing any function with complete tree). Let f :0, 10 + {0,1} be any function that only depends on the first variables, meaning there is some 9 {0, 1} + {0,1) such that:
f(z) = g(F(L)))
for all E {0,1]a Let T be any non-redundant complete tree of depth-h in which every internal node is one of the first coordinates. Then, there way to label the leaves of T such that T exactly computes f.
Proof. Since T' is non-redundant, each coordinate is queried at most once each root-to-leaf path. T' is complete and depth-h, so each of the first coordinates must be queried exactly once on each root-to-leaf path. Therefore, each leaf of T corresponds to exactly one way to set the first k coordinates of x. If the leaf is labeled by the output of g given those first & coordinates, T will exactly compute
Proof of Lemma 4.7]
The function Para (x))) is (1-=e-approximmtion f, it suffices to show that the depth-h tree for (arn(x(!)) is within the search space of Top-K when run to a depth of h.
There are only K - variables not in 2!1),, so each set of K candidate variables must contain some variable in z ()) Since Top-K K is non non-redundant, this must be variable that hasn' 't yet been queried higher in the tree. Thus, every step Top-K will always try candidate variable that reduces the number of relevant x² -vrribble by 1. It follows that the complete nonadaptive tree of depth h, containing all the variables of 2(1), is within the search space, so by Fact B.2 there is tree in the search space that computes Par,, (arx(((()) (z) exactly. Then the accuracy of the output must be at least the total accuracy of this tree, which is e)).
Conditioned on any setting of < h variables, for any variable in xx3), ((f (x) 2 1/k. Similarly, for any variable x, in (1)), [=]()) = 0. By Fact B.1 at every node the variables of (2( that have not yet been queried all rank ahead of the variables of (z), Thus, if at most K l variables have already been queried, the remaining k most-correlated candidates will
Proof of Lemma 4.2)
all be from (2), so no variable in x0 will be considered. Thus, at least K k variables from (1)
will be placed.
Since the depth budget h is smaller than h + K - k and at least K - k variables from x(()) are placed in every path, no path can contain all of the variables of (1)), The value of Par, (2) is O with probability 1/2 and with probability 1/2 conditioned smaller than h. Therefore, the tree built by Top-k cannot achieve accuracy better than 1/2 on the parity portion of the function (and thus have accuracy better than (1/2 + E) overall),
the values of any of variables
B.2 PROOFS DEFERRED FROM SECTION 4.2
The data distribution showing the accuracy separation between Top-K and Top-k is formed by combining the following two functions.
Definition 6 (Majority). The majority function of variables, indicated by Maje {0, - 1), returns
Mai == 11 jat least half of x's coordinates are 1).
Definition (Tribes). For any input length let u be the largest integer such that (1 - 2--2-w/e/w = 1/2. For x E 13 let (1) be the first w coordinates, (2)), the second w, and so on. Tribes; defined as
Tribes(()) = (z(") A A... xx v. (x A... A x!!)
where t =
For our purposes, it sufficient to know a few simple properties about Tribes. These are all proven in (0 [O'Donnel]] 2014, $4.2).
14

---

Under review as a conference paper at ICLR 2023
Fact B.3 (Properties of Tribes).
1. Tribess is monotone.
2. Tribes; is nearly balanced:
Tribes; = o(1)
2
where the o(1) term goes to 0 as goes to oc.
3. All variables in Tribes; have small correlation: For each i E [e],
[c Tribess(x)] O ( log
E 20- (0.1)
Indeed, the famous KKL inequality implies that any function with the first and second property has a variable with correlation at least (log Ł/E) (Kahn et al. 1988). Our construction uses Tribes exactly because it has the minimum correlations among functions with the above properties (up to constants). In contrast, we use Maj because its correlations are as large as possible, which will "trick" Top-k into building bad tree.
With the above definitions in-hand, we are able to provide proofs of the two missing Lemmas.
Proof Lemma 4.3 This proof is very similar to that of Lemma 4.1 Once again, we observe the tree computing (x + Tribes,, (a.()) (z:"))) has at least 1 accuracy with respect to Dr, k- Lemma 3.2 it is sufficient to prove such tree is in the search space.
By Fact B.2 any non-redundant complete tree depth & that only queries the first coordinates of its input will compute the function (r + (aibes;(<())) whenever the leaves are appropriately labeled. Therefore, we only need to prove such a tree is in the search space TK,A,D. There are only K - 1 coordinates that are not one of the first corresponding to (²)), Therefore, within any non-redundant set of coordinates, least one must be a non-redundant coordinate from the first h. This implies one of the desired trees is in the search space.
Proof of Lemma 4.4 Let T' be the tree returned by Top-k. Consider any root-to-leaf path of T that does not query any of the first h coordinates (those within ()))). Recall that, with probability (1 =), the label is given by Tribes,, ("))), On this path, the label of I" does not depend on any of the coordinates within (11), Therefore,
Pr [T(x)) = y x follows this path] (m.g)>DD.K
(1 - =)) Pr [T(x) Tribes; (2:(1)) follows this path]
(a.g)~Do,
+ 8
Pr
(T(x) = Maj (2) x follows this path)
(m.g))>Dh.K
(2+o(1)
(oC1))+e-16 +
+ 2
+ o(1)
where the last line follows because Tribes, is nearly balanced Fact B.3). As the distribution over a uniform, each leaf is equally likely. Therefore, if only p-fraction of root-to-leaf paths of T query at least one of the first h coordinates, then,
[xx) = vl s (1-p) (+ + +(1)) + + (a. (a.y)>Da,
1
p
15
+
+ o(1)
2
2
Our goal is prove the returned by Top-k achieves most accuracy. Therefore, it is enough to prove that o(1). Indeed, will prove that p < O(K-2)
Here, we apply (Blanc et al., 20206] Lemma 7.4), which was used to show that Top-1 fails to build a high accuracy tree. They used different data distribution, but that particular Lemma still applies to
15

---

Under review as a conference paper at ICLR 2023
setting. They prove that random root-to-leaf path of T satisfies the following with probability at least - O(k' the length of this path is less than O(K/ log K), at any point along that path, all coordinates within x22) that have not already been queried have correlation at least 1000k'
That Lemma will be useful for proving Top-k fails with the following parameter choices.
1. By setting K log h), can ensure all root-to-leaf paths T have length at most (K/ log K) so (Blanc et al. 2020b Lemma 7.4) applies.
2. By setting K I O / h 1)) can ensure that all the coordinates within x (11) have correlation less than 100vE FFact B.3). This means that all non-redundant coordinates within (2) have more correlation than those within (1))
3. By setting k < K - h, we ensure at all nodes along every path, there are at least l co- ordinates within the last K - 1 coordinates (those corresponding to x!²)), that have not already been queried. With probability at least O(K-KK 2) over a random path, those all have more correlation than all coordinates within 2(1), so Top-k won't 't query any of the coordinates within (1)).
We conclude that, with probability at least - O over a random path in T, that path does not query any of the first h variables. As result, the accuracy of T is at most 1+z
2 o(1)
O
16

---

Under review as a conference paper at ICLR 2023
C
DETAILS ABOUT DATASETS USED IN SECTION 5
Name
Type
Size (#train/#test)
#feats
#binary feats
#classes
connect-4
C
67557 (54045/13512)
42
126
3
nursery
C
12960 (10368/2592)
8
27
lettet-recoguition
C
19999 (15999/4000)
16
256
26
car
1728 (1382/346)
6
21
KI-VS- kp
3196 (2556/640)
36
73
2
hiv- hiv- -proteaeee
6590 (5272/1318)
8
160
mnolecular-boolog--iie
3190 (2552/638)
60
287
3
mushroom
8124 (6499/1625)
22
117
artifeeial-hhrratoor
N
10218 (8174/2044)
7
91
10
telescope
19020 (15216/3804)
10
100
2
spambase
4601 (3680/921)
57
57
2
dry-bean
13611 (10888/2723)
16
96
7
occupancc-esttmatiin
10129 (8103/2026)
16
86
4
mimboone
130064 (104051
50
100
2
dive-diagnosis
58509 (46807/1 1702)
48
96
11
ml -pove
6118 (4588/1530)
51
51
6
avila
20867 (0043//1037))
100
12
taiwanese-bandee bankruptcy
6819 (5455/1364)
95
95
2
credit-card
30000 (24000/6000)
23
88
electrical-grd--sttbee
10000 (8000/2000)
13
91
2
FICO
1000 (900/100)
23
1407
Table 1: Dataset characteristics. the Type column, C stands for Categorial and N stands Numerical.
Table provides complete details regarding all the datasets we used in our experiments. For datasets that don't it provide an explicit train/test split, we randomly compute 80:20 split. The column #feats has the number raw attributes in each dataset, while the column #binary feats has the number of features obtain after converting these raw attributes to binary-valued attributes. For categorical datasets, we encode a categorical attribute taking on / distinct values to / binary attributes. For numerical datasets, sort and compute thresholds for each numerical attribute. The number of thresholds so selected that the total number of binary attributes does not exceed 100.
17

---

Under review as a conference paper at ICLR 2023
D TRAINING TIME COMPARISON
nursery
occuaancyesslmatoon
ml.prove
7.5-
Titee (ogg scaloc
Time Dogp scolo)
3.0
2.5
Depth spambase
Depth
Depth dry bean
Depth
telescope
Time (1rg scalo)
Tine (Bogroccaaa
10
3.
20-
-25
4
Depth connect-4
Depth
Depth
Depth
letten-teconniiion
miniboone
senoorees--rrve--llgnnoo
10
12.0
10.3-
Time 1log scalc)
Time (oopoccaae)
(lopscala)
Time (oggecaaa)
60-
Depth
Depth
Depth
Depth
Top-1
Top-1
Top-4
MurThee
Figure 4: Training time comparison between Top-1, Top-k and MurTree We can see that the plots for Top-k are all straight lines with increasing slope, would be expected from Claim 3.1 The dashed vertical line for MurTree indicates a segmentation fault before completing execution of build- ing the decision tree.
18

---

Under review as a conference paper at ICLR 2023
E ACCURACY COMPARISON WITH TOP-1 FURTHER PLOTS
wawanese-bakkrusee
credit
electrical gradical-ggid..o lily
0.0250
2,900
0.0223
Accurec
6.90
0.5250
660
1p-1
Top-2
To--
Ttp-1
kpp2
Top
1op-2
Top2
1pp-3
0.230
Top-3
0.00
Ttp-1
6/000
1ap-4
Tsp-4
2075
64325-4
Dapth
Dopth
kr-ys-kp kp
hiv-l-pratease
moleculbrbboooogy..ooo spllic
mushraom
6.6
1op-1
1.000
B1--2
1p--3
0.99
0.86
1sp-1
3g-1
Top-
1o-22
0.6-
3.00
Figure 5: Test accuracy comparison between Top-1 and Top-k.
We provide plots from experiments further few datasets comparing the test accuracy of Top-k and Top-1 in Figure 5 the case of taiwanexe-bankruptey, credit-card and electrical-gricl stability, we observe that Top-1 is outperforming Top-k. However, believe that this is because the learning problem in this regime is extremely susceptible to overfitting. In particular, we can see that Top-1 itself consistently improving with increasing depth. Concretely, increasing depth beyond 3 is already causing Top-1 1 to overfit, and hence we would expect Top-k to suffer from overfitting even more. Furthermore, we can see that the gradation that the accuracy numbers are very close to one another. In the case of the remaining datasets (which all happen to categorical), while the numbers might not be monotonically getting better with increasing k, we can still observe that there is always some value of A: E {2, 3, 4) which is outperforming k = 1 (except for molecular-bion bililarrboooooysppiicc for which this is still the case till depth 6). This lends further support to proposition of incorporating A an additional hyperparameter to tune while training decision trees greedily.
the y-axis is very small, in
19


Reviews:
[{"review_id": "zJexAPFQqtG", "reviewer": "Reviewer_E3aU", "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": "The paper considers a simple algorithm for learning decision trees with high accuracy. The authors prove that there exists a distribution over instances for which the algorithm with larger depth parameter k+1 outputs a tree with higher accuracy than that produced by the algorithm with depth parameter k. Furthermore, the author provides experimental results showing the advantages of the proposed algorithm. ", "summary_of_the_review": "The paper proposes a simple but effective decision tree algorithm. Empirical results are promising, showing advantages over previous work. However, theoretical proofs are not accurate enough and I feel the technical contribution is not strong enough unless the theoretical parts are fixed.", "strength_and_weaknesses": "Strength\n- a simple but effective algorithm for learning more accurate trees than the standard greedy algorithms\n\nWeakness\n- The proofs do not seem accurate enough \n- implications of the theoretical results\n\nThe algorithm is an extension of the standard greedy decision tree algorithms such as ID3. The idea of using top-K features and finding an optimal tree is simple but effective. I agree with the statement that accurate small trees are important and the exponential time complexity is not high when the depth parameter is constant. Empirical results look promising as well.\n\nOn the other hand, I have serious concerns about the theoretical results of the paper. First, I think the proofs are not accurate enough since it lacks formal discussion, say, how to obtain information from the distribution. I raised some technical points below. \n\nSecond, the implications of the theorems are neither clear nor meaningful. Roughly, the main theorems say that there is a good situation where the algorithm with a large depth parameter is better than that with a smaller depth parameter. This does not imply the larger parameter is always better. Contrarily, when given a small sample, larger trees could overfit and smaller trees are better.  \n\n\n\nSome technical issues on theoretical proofs\nThe proofs are not accurate enough in the following reasons.\n- In the proofs, the scoring function is not specified. At least, there should be some properties that the function should satisfy in order to make the proofs correct. \n- The topK algorithm takes a sample of labeled instances. But, in the theorems and proofs, it somehow has access to the distribution directly(?). You need to formalize the process, e.g., using an oracle. What can the algorithm obtain from the distribution?\n- Sample complexity is not discussed. What is the sample complexity of the algorithm? This is related to the previous issue. In general, learning from a larger hypothesis class needs a larger sample, which is well-known in the statistical learning theory (e.g., PAC bound or VC-based generalization bounds). \n- The search space \\calT need a formal definition. The definition should be defined without using the algorithm.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "qHni22_iiA", "reviewer": "Reviewer_o6dK", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Learning decision trees from data is a simple and rich problem. The classic decision tree learning algorithms use a greedy strategy to select the best feature to evenly split the dataset. In this work, the authors look at k features and select an attribute that achieves maximal accuracy. This recovers the classic strategy for k=1.\n\nThey theoretically prove that for certain datasets their top-k algorithm achieves only $1/2+\\epsilon$ accuracy whereas top-(k+1) achieves $1-\\epsilon$ accuracy.\n\nThey also experimentally show that their algorithm betters both the classical top-1 algorithm and also more recent optimization algorithms which uses complicated and non-greedy strategies and hence are time-expensive.", "summary_of_the_review": "I prefer to accept the paper considering that they combine a classic algorithm with a classic strategy to give an algorithm for learning decision trees.", "strength_and_weaknesses": "strength: the proposed approach is natural and simple. Authors have shown both theoretical and empirical evidence that shows that their algorithm is better.\n\nweakness: the negative result would have been much stronger had they compared their top-(k+1) algorithm against any other algorithm, not just the top-k algorithm.", "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": "VvUWb76RLnO", "reviewer": "Reviewer_uFXj", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this paper, the authors proposed a new way of training decision trees, which extends the standard greedy tree fitting algorithms. The main idea is to consider Top-k features for each split, instead of just greedily using the top-1 feature. Theoretically, the authors present a sharp greediness hierarchy theorem that shows that even a Top-(k+1) tree can be much more power full than Top-k. Further, the empirical results also demonstrate the efficacy and efficiency of the proposed algorithm.", "summary_of_the_review": "This paper presents a simple and intuitive extension of existing tree-fitting algorithms. One major concern is the multiplicative exponential factor in the computational complexity - I'm not fully convinced this is a scalable solution. See details in the weaknesses.", "strength_and_weaknesses": "Strength:\n\n1. The proposed method is a simple and intuitive generalization of the standard tree-fitting algorithms, which naturally covers the optimal tree when $k$ equals the dimension $d$.\n\n2. The new training algorithm is largely amenable to parallelization, despite the exponential increase in computational complexity.\n\n3. The greediness hierarchy theorem demonstrates the power of choices in decision tree learning - even going from $k$ to $k+1$ brings significant improvement in performance.\n\n4. The empirical evaluation also demonstrates the efficacy and efficiency of the proposed algorithm for relatively small $k$.\n\nQuestions and weaknesses:\n\n1. One major concern is computational complexity. I'm not fully convinced by the discussion on page 5 about computational complexity. While the original complexity is $2^h$, the proposed algorithm has an additional multiplicative factor of $k^h$. Since this is a multiplicative factor, this is not negligible. The exponential factor is also empirically verified in Fig 4. This is prohibitive for a decent depth - for instance, for h = 10 and k = 3, training one tree in this way is equivalent to training 3^10 ~= 59,000 trees in a greedy way.\n\n2. What is the difference between Theorem 3 and Theorem 4?\n\n3. Scikit-learn is used as a baseline lib for all experiments. However, for tree-fitting algorithms, xgboost or lightgbm seem to be a more common choice and usually deliver better accuracy.\n\n4. In the first paragraph of Section 5, the sentence \"For numerical datasets,.... appropriate number of thresholds\" is duplicated.", "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": "B-pWRKRtij", "reviewer": "Reviewer_Nivx", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes a simple generalization of greedy algorithms for learning decision trees. At a given iteration, instead of growing the tree using the most promising (top-1) feature, the proposed algorithm uses the top-k features and builds a subtree for each of them.\nThe paper highlights that, even though the time complexity of the top-k algorithm is polynomial in $k$, the algorithm can be easily parallelized to obtain running times of the same order as top-1 algorithms' ones (unlike optimal tree methods).\n\nUnsurprisingly, an empirical analysis shows that using a $k \\in [2, 4]$ generally improves over the test accuracy of top-1 greedy algorithms (although it is more prone to overfitting) while having a time complexity (both in number of samples and of features) much smaller than optimal tree methods.\nThe paper further shows that there exist data distributions on which the test accuracy of the top-K algorithm is provably better than the test accuracy (Theorem 1) when using top-(K-1) for the same depth $h$ or (Theorem 2) when using top-k with $k < K$ and allowing for deeper trees (up to $h + K - k - 1$ depth) or (Theorem 3) when using top-k with $k \\leq K - h$ for same depth budget $h$.", "summary_of_the_review": "The paper's contributions are significant and potentially impactful. The theoretical and empirical analyses are sufficient to support the claims of the paper. \nSome work is needed to improve the presentation of the paper, in particular of the theoretical results. I would be happy to increase my score accordingly.", "strength_and_weaknesses": "## Strengths\n### Clarity. \nThe paper is generally well-written: the contributions are clearly stated, the empirical analysis is described with enough level of detail and intuitions are provided for the theoretical results.\n\n### Significance and impact. \nPartly due to its simplicity, the proposed generalization of standard greedy approaches is likely to be adopted in future works, both in the machine learning and the application-oriented communities.\n\n## Weaknesses\n### Mathematical rigour.\n1. The notation, definitions and theoretical results are split over different sections in the main paper and the appendix. It makes it harder to understand the proofs as the reader has to jump forward and backward just to be able to follow them. More precisely, the theorems are stated in Section 1.1.2, the proofs and definitions are partially reported in Section 4.1 and completed in the appendix. It would really help that at least in the appendix all the elements needed to understand the theorems and the proofs are reported together. \n\n2. Incorrect or unclear results: \n\n- Lemma 3.2. Shouldn't it be a max over the trees and not a min?\n\n- Fact B.2, hence the following results too, stands only for $h \\leq k$.\n\n- In proof of Lemma 4.2, the derivation of the two expectations should be reported.\n\n- In proof of Lemma 4.4, why is Pr[T(x) = Tribes(x)| x follows path] is upper bounded by Exp[Tribes(x)|?\n\n3. Missing notation: $x_i$ in Figure 1 (in particular its domain), $x, y, S$ in Definition 2. \n\n### Literature.\nThe paper never discusses the rich literature on learning optimal soft decision trees with gradient-based methods, e.g. [1], [2]. This literature is very relevant to the proposed work, as it shares the goal of learning decision trees with a scalability close to greedy algorithms and an accuracy close to optimal tree methods.\nHow does the proposed method compare to this literature?\n\n### Empirical analysis.\n1. In page 7, it is said that \"We build decision trees corresponding to both gini and entropy as the impurity measure H, and report numbers for whichever of the two performed better on the test set\". This is ambiguous and does not seem a rigorous way of comparing methods. Does this mean that within the same figure or subfigure the methods are optimized with different impurity scores? How much the choice of impurity score affect the performance gap?\n\n2. The comparison with the baselines is carried out in terms of accuracy and running times independently. To have a better idea of the trade-off between the two, it would be valuable to plot these two metrics together and highlight in which regimes (in terms of k and depth) it is possible to improve accuracy without incurring into prohibitive running times.\n\n3. Figure 4 is commented in the main paper but reported in the appendix. For the paper's main text to be self-contained, the figure and its description should be reported together.\n\n### (minor) Interpretability. \nThe theoretical results provide some intuition on how to choose $k$ and $h$, in particular so that learning a top-k tree would allow to reduce the depth of the tree without degrading accuracy. It is not clear however how this analysis relates to the interpretability of the decisions, which is one of the (if not the) principal reasons for learning decision tree-based models. My question is: does using $k > 1$ results in reducing the interpretability of the model, as the overall number of decision splits increases? It would be valuable to briefly discuss this point, showing how this affects the interpretability of the decision for a point and for a class.\n\n### (minor) Typos\n\n- Section 2: understanding the performances -> understanding of the performance\n\n- Section 4 $f_{h, k}$ definition: in the multicase,  $f_{h, k} = $ -> $f_{h, k}(x) = $\n\n- Page 7, footnote: seeing as -> as\n\n- Page 15, last two lines: which was used to that (missing word)\n\n[1] Ozan Irsoy, Olcay Taner Yildiz, Ethem Alpaydin: Soft decision trees. ICPR 2012\n\n[2] Ryutaro Tanno, Kai Arulkumaran, Daniel C. Alexander, Antonio Criminisi, Aditya V. Nori: Adaptive Neural Trees. ICML 2019", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject