Harnessing the power of choices in decision tree learning
Authors: Guy Blanc
Jane Lange
Chirag Pabbaraju
Colin Sullivan
Li-Yang Tan
Mo Tiwari
Venue: NeurIPS 2023 poster (2023)
Keywords: Decision Trees
Decision Tree Learning
Top-$k$
ID3
Greedy Algorithms
TL;DR: We propose a simple generalization of greedy decision tree learning algorithms which parameterizes the greediness in these algorithms by a parameter $k$, and validate the effectiveness of having this parameter, both theoretically and empirically.

Abstract: We propose a simple generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4.5, and CART.   These 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.  Our 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 greediness hierarchy theorem showing that for every $k\in \mathbb{N}$, Top-$(k+1)$  can be dramatically 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$ outperforms 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 greedy algorithms across a wide range of benchmarks.  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 far beyond the reach of these algorithms. The code to reproduce our results is available at https://github.com/SullivanC19/pydl8.5-topk.

Harnessing the Power of Choices in Decision Tree Learning
Guy Blane"
Jane Lange" MIT ji slange@mit.edu
Chirag Pabbaraju"
Stanford gbl Ablanc@stanford.ce edu
Stanford
cpabarra@stanford.edd
Colin Sullivan"
Li- LinYang Tan* Stanford lytan@stanford.edi
Mo Tiwari"
Stanford colins colins2@sstanfodd.c edu
Stanford
motiwari@stanford edu
Abstract
We propose simple generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4.5, and CART. These 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. Our 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 generalization. We first prove greediness hierarchy theorem showing that for every k E IN, Top-(k + 1) can be dramatically more powerful than Top-k: there are data distributions for which the former achieves accuracy - E, whereas the latter only achieves accuracy + E. We then show, through extensive experiments, that Top-k outperforms 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 greedy algorithms across wide range benchmarks. 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 far beyond the reach of these algorithms. The code to reproduce our results is available at: https: //tpttttttt///////////////e cow www.eoulliaaaaaaaeeeeeeeewweewle httm///llvaann9/p//iiiea /pyp//........m/// wwt.yd1......... 5-topk.
1 Introduction
Decision trees are a fundamental workhorse machine learning. Their logical and hierarchical structure makes them easy understand and their predictions easy to explain. Decision trees therefore the most canonical example an interpretable model: in his influential survey [Bre01b], Breiman writes "On interpretability, trees rate an A+"; much more recently, the survey [RCC+22] lists decision tree optimization as the very first of 10 grand challenges for the field of interpretable machine learning. Decision trees also central modern ensemble methods such as random forests [Bre01a] and XGBoost [CG16], which achieve state-of-the-art accuracy for a wide range of tasks.
Greedy algorithms such as ID3 [Qui86], C4.5 [Qui93], and CART [BFSO84] have long been the standard approach to decision tree learning. These algorithms build decision tree from labeled data top-down manner, growing the tree by iteratively splitting on the "best" attribute as measured with respect to certain heuristic function (e.g., information gain). Owing their simplicity, these
Authors ordered alphabetically.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

algorithms are highly efficient and scale gracefully to handle massive datasets and feature set sizes, and they continue to 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 review in Section 2, on algorithms that optimize for accuracy and seek to produce optimally accurate decision trees. These algorithms employ a variety of optimization techniques (including dynamic programming integer programming, and SAT solvers) and are completely different from the simple greedy algorithms discussed above. Since the problem of finding an optimal decision tree has long been known to be NP-hard [HR76), any algorithm must suffer from the inherent combinatorial 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 and thousands remain out of reach.
This state of affairs raises natural question:
Can design decision tree learning algorithms that improve significantly the accuracy of classic greedy algorithms and yet inherit their simplicity and scalability?
In this work, we propose a new approach and make a case that provides a strong affirmative answer to the question above. Our work also 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 greedy decision tree algorithms
We introduce an 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 as candidate splits at each step. Setting k = 1 recovers the fully greedy classical approaches, and increasing i 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- preserving the efficiency and scalability of greedy algorithms is a primary objective of our work-although we mention here that by setting l to be the dimension d, our algorithm produces an optimal tree. Our overall framework can thus be viewed interpolating between greedy algorithms at one extreme and "optimal decision tree" algorithms at the other, precisely the two main and previously disparate approaches to decision tree learning discussed above.
We will now describe our framework. A feature scoring function H takes as input a dataset over binary features and specific feature i E [d], and returns value quantifying the "desirability" of this feature as the root of the tree. The greedy algorithm corresponding to H selects as the root of the tree the feature that has the largest score under H;; our generalization will instead consider the A features with the highest scores.
Definition 1 (Feature scoring function). A feature scoring function H takes as input a labeled dataset over a d-dimensional feature space, a feature i E [d], and returns a score V E 1].
See Section 3.1 for a discussion of the feature scoring functions that correspond to standard greedy algorithms ID3, C4.5, and CART. Pseudocode for k is provided in Figure 1. We note that from the perspective of interpretability, the trained model looks the same regardless 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 at 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 single additional choice provably leads to huge gains in test accuracy? Our first main theoretical result a sharp greediness hierarchy theorem, showing that this parameter can have dramatic impacts on accuracy, thereby illustrating its power:
2

---

Top- h):
Given: A feature scoring function H, a labeled sample set S over d dimensions, and depth budget h.
Output: Decision tree of depth h that approximately fits S.
1. If O, if every point in S has the same label, return the constant function with the best accuracy w.r.t. S.
2. Otherwise, let S [d] be the set coordinates maximizing H(S, i).
3. For each E I, let T, be the tree with
Root 3;; Left subtree = Top-k(H,, So;=0, 1) Right subtree Top-k(H, S2,=1, h 1), where Sag=b is the subset of points in S where vi = b.
4. Return the T3 with maximal accuracy with respect to S among all choices of E Z.
Figure I: The Top-k algorithm. It can be instantiated with any feature scoring function H. and when
1, recovers standard greedy algorithms such as ID3, C4.5, and CART.
Theorem (Greediness hierarchy theorem). For every > 0, k, h E N. there is a data distribution D and sample size n for which, with high probability over random sample S ~~ D", Top-(k + 1) achieves at least 1 4-6 E accuracy with a depth budget of h, but Top-k achieves at most 2 + accuracy with depth budget of h.
All of our theoretical results, Theorems 1 to 3, hold whenever the scoring function is impurity- based heuristic. This broad class includes the most popular scoring functions (see Section 3.1 for more details). Theorem is special case of a more general result that we show: for all k K, there are data distributions on which Top-K achieves maximal accuracy gains over Top-k, even if Top-k is allowed a larger depth budget:
Theorem 2 (Generalization Theorem 1). For every E > O, k. K, h E IN where k < K, there data distribution D and sample size for which, with high probability over random sample S ~ D Top-K achieves at least - E accuracy with a depth budget of h, but Top-k achieves at most E accuracy even with depth budget of h (K - 1).
The proof of Theorem is simple and 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 it 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 is evident even for monotone data distributions. We defer the definition of monotone data distributions to Section 4.2.
Theorem 3 (Greediness hierarchy theorem for monotone data distributions). For every > 0, depth budget h, K between (2(h) and Ö(h2) and k < K h, there is monotone data distribution D and sample size n. fofor which, with high probability over a random sample S ~ DD Top- K achieves at least E accuracy with depth budget of b, but Top-k achieves most 1 + accuracy with depth budget of h.
Many real-world data distributions are monotone in nature, and relatedly, they are a common assumption 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 [BLT20b, BLT20a]. Theorem 3 shows that even within this class, increasing the greediness parameter can lead to dramatic gains in accuracy. Compared to Theorem 2, the proof of Theorem is more technical and involves the use of concepts from the Fourier analysis of boolean functions [O'D14].

---

We note that weaker version of Theorem 3 is implicit in prior work: combining [BLT20b, Theorem 7b] and [BI.QT21b, Theorem 2] yields the special case of Theorem 3 where K = (hh² and = 1. Theorem is a significant strengthening as allows for k and much smaller K K.
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 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 of Top-k for k: 1, 4, 8, 12, (Figure 2), and find that increasing k does indeed provide a significant increase in test accuracy- in some cases, Top-8 already achieves accuracy comparable the test accuracy attained by DL8.5 [ANS20], an optimal decision tree algorithm. We further show, in Figures 3 and 6, that Top-k inherits the efficiency of popular greedy algorithms and scales much better than the state-of-the-ar optimal decision tree algorithms MurTree and GOSDT 20].
Taken as a whole, our experiments demonstrate that Top-k provides useful middle ground between greedy and optimal decision tree algorithms: it is significantly more accurate than greedy algorithms, but still fast enough be practical on reasonably large datasets. See Section 5 for an in-depth discussion of our experiments. Finally, we emphasize the benefits afforded by the simplicity of Top-k. Standard greedy algorithms (i.e. Top-1) are widely employed and easily accessible. Introducing the parameter k requires modifying only a tiny amount of source code and gives the practitioner a new lever to 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. A long and fruitful line of work seeks to develop a 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 [KM96, Kea96, DKM96, BDM19, BDM20, BLT20b, BLT20a, BLQT21a]. 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 in 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 of [BLQT21b). Recent work of Blanc, Lange, Qiao, and Tan also highlights the power of choices in decision tree learning. However, they operate within 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, 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 learning and the highly interpretable nature of decision trees, there have been numerous works on learning optimal decision trees [BD17, VZ17, V719, AAV19, 7MP+20 20, VNP+20, NIPMS18, Ave20, JM20, NF07, HRS 19, + DLH As mentioned the introduction, this is an NP-complete problem [HR76]-indeed, it is NP-hard to find even an approximately optimal decision tree [Sic08, AH08, ABF+ 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 to build optimal decision trees for many real world datasets when the dataset and feature sizes are in the hundreds and the desired depth is small (< 5).
Finally, another related line of work is that of soft decision trees [IYA12, TAA+ 19]. These works use gradient-based methods to 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), understand the classification of test point, it is sufficient look at only one root-to-leaf path, as opposed to a weighted combination across many.
The Top-k algorithm
3.1 Background and context:
Impurity-based algorithms
Greedy decision tree learning algorithms like ID3, C4.5 and CART are all instantiations of Top-k in Figure with k 1 and an appropriate choice of the feature- function H. Those three algorithms all used impurity-bsedd heuristics as their feature-scoring function:
Definition (Impurity -based heuristic). An impurity function
[0. - [0. is a function that is
concave, symmetric about 0.5, and satisfies (()) = ((1) = 0 and (00.5) 1. A feature-scoring
function H an impurity-bant -based heuristic, if there is some impurity function g for which:
i) -
E 14i - Pr [x,
= 0]
E
21 = =0]
Pr at = 1] ay.--
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 ((p) -plog2 - (1 -p) l0 - p) (used by ID3 and C4.5), the Gini index G(p) 4p(1 p) (used by CART), and the function G(p) = p - p) (proposed and analyzed in [KM99]). We re- fer the reader to [KM99] for theoretical comparison, and [DKM96] for experimental comparison, of these impurity-based heuristics.
Our experiments focus binary entropy being the impurity measure, but our theoretical results apply Top-k instantiated with any impurity-basee based heuristic.
3.2 Basic theoretical properties of the Top-k algorithm
Running time. The key behavioral aspect in which Top-k differs from greedy algorithms that 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. More concretely, suppose Top-k is run dataset S with n points. We can then easily derive the following bound on the running time of Top-k, where H(S,0 i) is assumed to take (n) time to evaluate (as it does for all impurity-bast heuristics). Claim 3.1. The rumning time of TH, S, h) is O((kk)* nd).
Proof. Let Ti be the number recursive calls made by TH, Then, we have the simple recurrence relation Ty 2 where To = Solving this recurrence gives T₁ (2k)*. Each recursive call takes ((n) time, where the bottleneck is scoring each the d features.
We note that any decision tree algorithm, including fast greedy algorithms such ID3, C4.5, and CART, has runtime that scales exponentially with the depth /t. The size of depth-/a tree can be 2 and this is of course lower bound the runtime the algorithm needs output such tree. In contrast with greedy algorithms (for which & = 1). Top-k incurs an additional h² cost in running time, As mentioned earlier, practice, we are primarily concerned with fitting small decision trees (e.g., h = 5) to the data, as this allows for explainable predictions. In this setting, the additional h cost (for small constant kc) is inexpensive, as confirmed by our experiments.
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 sample S and integers h, k, we use Tk.h.s to refer to all trees the search space of Top-k. Specifically, if = 0, this contains all trees with height of zero (the constant O and constant 1 (rees). For h 2 1, and I C [d] being the k coordinates with maximal score, this contains all trees with root of Vs, left subtree Tr Tk.b-1.8... 1,8..- and right subtree in Tk T1, for some E I.
5

---

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 ouiput of Top-k with a depth budget of h on S. Then
( Pr (T
Pr m.
[())= =y] =
max T TT.A.
We refer the reader to Appendix A for the proof of this lemma.
4 Theoretical bounds on the power of choices
We refer the reader to the Appendix B for most the setup and notation. For now, we briefly mention small amount of notation relevant to this section: variables. We also use bold font to indicate stochastic functions which output a random variable. For example.
bold font (e.g. denote random
with probability 1
f(x) = x
with probability 1
is the stochastic function that returns either the identity its negation with equal probability. To define the data distributions of Theorems 2 and 3, we will give a distribution over the domain, and the stochastic function that provides the label given an element of the domain.
Intuition for proof of greediness hierarchy theorem To construct distribution which Top-k fits poorly and Top- (k + 1) fits well, we will partition features into two groups: one group consisting of features with medium correlation to the labels and another group consisting of features with high correlation when taken all together but low correlation otherwise. Since the correlation of features in the former group is larger than that of the latter group unless all features from the latter group are considered, both algorithms will prioritize features from the former group. However, if the groups are sized correctly, then Top-(k + 1) will consider splitting on all features from the latter group, whereas Top-k will not. As a result, Top-(ke + 1) will output a decision tree with higher accuracy.
4.1 Proof of Theorem 2
For each depth budget h and search branching factor K, we will define hard distribution D,.K that is learnable to high accuracy by Top-K with a depth of h. but not by Top-k with depth of h' for any W < h K k. This distribution will be over {0, 13 {0, 1}. where d = K 1. The marginal distribution over {0, 1]dd is uniform, and the distribution over {0, 1} conditioned setting of the d features is given by the stochastic function x All of the results of this section (Theorems 2 and 3) hold when the feature scoring function is any impurity-based heuristic.
Description of (z). Partition x into two sets of variables, (1) of size h and (2) of size K 1. Let f f (x) be the randomized function defined follows:
(n,x(z) = Par, (x)
with probability 1 1-6
J (2))
with probability E;
where Unif(ax(22) denotes the uniform distribution on (2)), Parz(x is the parity function, whose formal definition can be found in Appendix B.
The proof of Theorem 2 is divided into two parts. First, we prove that when the data distribution is DR.K. Top-K K succeeds in building high accuracy tree with depth budget of h. Then, we show that Top-k fails and builds a tree with low accuracy, even given a depth budget of + (K - 1).
Lemma 4.1 (Top-K succeeds). The accuracy of Top-K K with depth of h on Dr.K is at least 1
Lemma 4.2 (Top-k fails). The accuracy of Top-k with depth of hi on Dr.K is at most (1/2 + 8) for any h' < h + K- k.
Proofs of both these lemmas are deferred Appendix B. Theorem then follows directly from these two lemmas.

---

4.2 Proof of Theorem 3
In this section, we overview the proof Theorem 3. Some of the proofs are deferred to Appendix B.2.
Before proving Theorem 3, we formalize the concept of monotonicity. For simplicity, we assume the domain is the Boolean cube, {0, 13,, and use the partial ordering x I x' iff x; S xr for each i [d]; however, the below definition easily extends to the domain being any partially ordered set.
Definition 4 (Monotone). A stochastic function, f {0, + (0, 1}, is monotone if. for any x E {0, 1] where x 1 x', E[f(x) I [xf(x')). A data distribution, 'D over {0, 1] x {0, 1] said to be monotone if the corresponding stochastic function, f f(x) returning (y z) where (ac y) ~ D, is monotone.
To construct the data distribution of Theorem 3, will combine monotone functions, Majority and Tribes, commonly used in the analysis of Boolean functions due to their extremal properties. See Appendix B.2 for their definitions and useful properties. Let h K 1, and the distribution over the domain be uniform over {0, 1jdd Given some {0, 13d, use 2( to refer the first h coordinates of x and (2) the other K coordinates. This data distribution is labeled by the stochastic function f given below.
f(x) = (Tribes (I:(1)
with probability 1 6 (2()) with probability
Clearly f is monotone as it is the mixture of two monotone functions. Throughout this subsection, we'll use K to refer to the data distribution over {0, 1]dd x {0, where to sample (æ: y) ~ D, we first draw x {0. 1)dd uniformly and then y from f fax). The proof of Theorem is a direct consequence of the following two Lemmas, both of which we prove in Appendix B.2.
Lemma 4.3 (Top-K succeeds). On the data distribution Dr.k. Top-K with a depth budget of achieves least - accuracy.
Lemma 4.4 (Top-k fails). On the data distribution Dr.K, Top-k with a depth budget of h achieves at most + accuracy.
5 Experiments
Setup for experiments. At all places, the Top-1 tree that we compare to that given by scikit-learn [PVG+11], which according to their documentation", is an optimized version of CART. We run experiments on variety of datasets from the UCI Machine Learning Repos- itory [DG17] (numerical well categorical features) having size in the thousands and having 50 300 features after binarization. There were 100 datasets meeting these criteria, and we took random subset of 20 such datasets. We binarize all the datasets for categorical datasets, convert every categorical feature that can take on (say) values into binary features. For numerical datasets, sort and compute thresholds for each numerical attribute, so that the total number of binary features 100. detailed description of the datasets is given in Appendix C.
We build decision trees corresponding to binary entropy as the impurity measure H. In order to leverage existing engineering optimizations from state-of-the-art optimal decision tree imple- mentations, we implement the Top-k algorithm given in Figure via simple modifications to the PyDL8.5 [ANS20, ANS21] codebase Details about this are provided Appendix D. Our imple- mentation of the Top-k algorithm and other technical details for the experiments available at https://gt thub. com hte//Sullin SoullivnnC99/ pppp/////.11///1 t-top..
5.1 Key experimental findings
Small increments of ls yield significant accuracy gains. Since the search space of Top-k is be larger.
superset of that of Top-1 for any l > 1, the training accuracy of Top-k: is guaranteed The primary objective in this experiment is to show that Top-k can outperform Top-1 in terms of test accuracy as well. Figure shows the results for Top-1 versus Top-k for l: 2,3, 4, 8, 12, 16, d. Each
7

---

A42
1.01
1487
0224
6:0
1.00
0.70
013
Lon
100n
1005
Figure 2: Test accuracy comparison between Top-k for various values of k. We can see that Top- (k + 1) generally obtains higher accuracy than Top-k, and in some cases (c.g., nursery). Top-8/ 8/p-8/11 16's accuracy is even comparable to the optimal tree (Top-d). Missing points the plots correspond to settings that did not terminate within a sufficiently large time limit. All plots are averaged over 10 random train-test splits (except avila and ml- prove that have pre-specified splits) with confidence intervals plotted for 2 standard deviations.
plot a different dataset, where on the x-axis, we plot the depth of the learned decision tree, and on the y-axis, plot the test accuracy. Note that k: = d corresponds to the DL8.5 optimal decision tree. We can clearly observe that the test accuracy increases as k increases- in some cases, the gain 5% (absolute). Furthermore, for (smaller) datasets like nursery. for which we were able to run k == d, the accuracy of Top-8/ 16 is already very close to that of the optimal tree.
Lastly, since Top-k invests training time is naturally longer than Top-1. However, Figure in Appendix E, which plots the training time, shows that the slowdown is mild.
computation towards fitting a better
the training set, its
Top-k scales much better than optimal decision tree algorithms. Optimal decision tree algo- rithms suffer from poor runtime scaling. We empirically demonstrate that, in comparison. Top-k has a significantly better scaling in training time. Our experiments are identical to those in Figures 14 and 15 in the GOSDT paper [LZH+20], 20], where two notions of scalability are considered. 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 training samples. The dataset we use is the FICO [FGI 18] dataset, which has total of 1000 samples with 1407 binary features. We plot the training time (in seconds) versus number of features/samples for optimal decision tree algorithms (MurTree,, GOSDT) and Top-k in Figure 3. We do this for depth 4, 5,6 (for GOSDT, the regularization coefficient À set to 2- depth)). We observe that the training time for both MurTree and GOSDT increases dramatically compared to Top-k; in both experiments.
the first
particular, for depth = 5, both MurTree and GOSDT were unable to build a tree on 300 features within the time limit of 10 minutes, while Top-16 completed execution even with all 1407 features. Similarly, in the latter experiment, GOSDT/MurTree were unable to build a depth-5 tree on 150 samples within the time limit, while Top- 16 comfortably finished execution even on 1000 samples. These experiments demonstrates the scalability issues with optimal tree algorithms. Coupled with the accuracy gains seen in the previous experiment, Top-k thus be seen achieving a more favorable tradeoff between training time and accuracy.
We note, however, that various optimization have been proposed to allow optimal decision tree algorithms to scale to larger datasets. For example, more recent version of GOSDT' has integrated guessing strategy using reference ensembles which guides the binning of continuous features, tree

---

600
600
900
1pp1
Top-1
Top
509
Top-2
Tap-2
400
Top
Top
400
Top
Top
400
Top
Top-
lop-16
Top
Top-15 GOEDT
GOSET
200
MurPoc
200
Murfise
200
Marees
0
250
400
650 B0n 1200 1400 Number of Resoures
0
200
400
1200
1400
250
400
800
1000
1250 1400
Number of Features
Number of Features
(a) Depth 4
(b) Depth 5
(c) Depth
600
Top
500
Top
500
500
400
Top-8
Tep-é
400
To-8
400-
Top-
Top-4
300
Top
Top 16
Top 15
GCSDT
CO5DT
G05DT
200
MurThe
200
Marthe
200-
Nur Tree
100
200
400
600
500
1000
200
400
6:0
850
1000
200
4.00
600
500
1000
Namber Semples
Number Samppe
Number Semples
(d) Depth
(e) Depth
Depth
Figure 3: Training time comparison between Top-k and optimal tree algorithms. As the number of features/samples increases, both GOSDT and MurTree scale poorly compared to Top-k, and beyond a threshold, do not complete execution within the time limit.
Uc
0.82
0.8
Pe ACCurcy
0.76
0.6-
0.70
Figure 4: Test accuracy plateaus for large k. All rums averaged over 10 random train-test splits with maximum depth fixed 3.
size, and search [MZA+]. Many of these optimizations are generally applicable across optimal tree algorithms and could be combined with Top-k for further improvement in performance.
Increasing h beyond a point does not improve test accuracy. In our experiments above, we ran Top-k only till & 16: Figure 4, we show that increasing very large values, which increases runtime, often does not improve test accuracy, and in some cases, may even hurt due to overfitting. For 3 datasets car, hayes-roth and tic-tac-toe we plot train and test error as a function of Naturally, the train accuracy monotonically increases with & in each plot. However, for both car and hayes-roth, we can observe that the test accuracy first increases and then platcaus. Interestingly, for tic-tac-toe, the test accuracy first increases and then decreases demonstrate that selecting too large of k, as optimal decision tree algorithms do, waste of computational resources and can even hurt test accuracy via overfitting.
increase k. These experiments
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 A best features as candidate splits instead of just the single best one. As our theoretical and empirical results demonstrate, this simple generalization is powerful and enables significant accuracy gains while preserving the efficiency and scalability of standard greedy algorithms. Indeed, we find it surprising that such simple generalization has not been considered before.
There much more to explored and understood, both theoretically and empirically; we list here a few concrete directions that we find particularly exciting and promising. First, suspect that power

---

of choices affords more advantages over greedy algorithms than just accuracy gains. For example, an avenue for future work is to show that the trees grown by Top-k are more robust to noise. Second, 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 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 k and further extend the power of choices to these settings.
there principled approaches
machine-learned advice and algorithms with predictions [MV20], an area
Acknowledgements
We thank the NeurlPS reviewers and AC for their detailed and helpful feedback.
Guy and Li- Yang are supported by NSF awards 1942123, 221 1237, 2224246 and Google Research Scholar award. Jane supported by NSF Graduate Research Fellowship under Grant No. 2141064, NSF Awards CCF-2006664, DMS- DMS-2022448, and Microsoft. Mo is supported by Stanford Interdisci- plinary Graduate Fellowship and a Stanford Data Science Scholarship. Chirag is supported by Moses Charikar and Greg Valiant's Simons Investigator Awards.
References
[AAV19] Sina Aghaci. Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for non-discriminative decision-making In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1418-1426, 2019.
[A Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, and Toniann Pitassi. The complexity of properly learning simple concept classes. Journal of Computer & System Sciences, 16-34, 2009.
[AH08] Micah Adler and Brent Heeringa. Approximating optimal binary decision trees. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Tech- niques, pages 1-9. Springer, 2008.
[ANS20] Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. Learning optimal decision trees using caching branch-and bound search. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages
2020.
[ANS21] Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. Pyd18. 5: a library for learning optimal decision trees. Proceedings of the Twenty-Ninth International Conference on International Joint Conferences Artificial Intelligence, pages 5222-5224, 2021.
[Ave20] Florent Avellaneda. Efficient inference of optimal decision trees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3195-3202, 2020.
[D17]] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning. 106(7):009--1082, 2017.
[BDM19] Alon Brutzkus, Amit Daniely, and Eran Malach. On the Optimality of Trees Generated by ID3. ArXiv,
05444, 2019.
[BDM20] Alon Brutzkus, Amit Danicly, and Eran Malach. ID3 learns juntas for smoothed product distributions. In Proceedings of the 33rd Annual Conference on Learning Theory (COLT), pages 902-915, 2020.
[BFSO84] Leo Breiman, Jerome Friedman, Charles Stone, and Richard Olshen. Classification and regression trees. Wadsworth International Group, 1984.
[BLQT21a] Guy Blanc, Jane Lange, Mingda Qiao, and Li- Yang Tan. Decision tree heuristics can fail, even in the smoothed setting. In Mary Wootters and Laura Sanità, editors, Proceedings of the 25th International Conference on Randomization and Computation (RANDOM), volume 207, pages 155:166,, 2021.
10

---

[BIQQT1b] Guy Blanc, Jane Lange, Mingda Qiao, and Li- Li-Yang Tan. Properly learning decision trees in almost polynomial time. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2021.
[BLT20a] Guy Blanc, Jane Lange, and Li- Li-Yang Tan. Provable guarantees for decision tree induction: the agnostic setting. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
[BLT20b] Guy Blanc, Jane Lange, and Li- Yang Tan. Top-down induction of decision trees: rigorous guarantees and inherent limitations. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151, pages 1-44, 2020.
[Bre01a] Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
[Bre01b] Leo Breiman. Statistical Modeling: The Two Cultures (with comments and rejoinder by the author). Statistical Science, 16(3):199 - 231,,,200 2001.
[CG16] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Pro- ceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), pages 785-794, 2016.
[DG17] Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
[DKM96] 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 (ICML), pages 96-104, 1996.
[DLH+22] Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christo- pher Leckie, Kotagiri Ramamohanarao, and Peter Stuckey. Murtree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research, 23(26):1-47, 2022.
[FGI+18] FICO, Google, Imperial College London, MIT, University of Oxford, UC Irvine, and UC Berkeley. Explainable Machine Learning Challenge. https: // communi ty fico. com/s/C //explainabbeeeeeeeeeaeaaaaaabee maw.eee-aaa--eeane-eeeee machine-learningee.....------ cha.gggchaaleee... 2018.
[HR76] Laurent Hyafil and Ronald I.. Rivest. Constructing optimal binary decision trees is np-complete. Information Processing Letters, 5(1):15-17, 1976.
[HRS19] Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. Advances in Neural Information Processing Systems, 32, 2019.
[[YA12] Ozan Irsoy, Olcay Taner Yildız, and Ethem Alpaydın. Soft decision trees. In Proceedings of the 21st international conference pattern recognition (ICPR2012), pages 1819- 1822. IEEE, 2012.
[JM20] Mikoláš Janota and António Morgado. baT-b encodings for optimal decision trees with explicit paths. In International Conference on Theory and Applications of Satisfiability Testing, pages 501-518. Springer, 2020.
[Kaа96] 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), pages 1337-1339, 1996.
[Kaа98] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6))983-1066 1998.
[KL888] Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables boolean functions. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS), pages 68 80, 1988.

---

[KM96] Michael Kearns and Yishay Mansour. On the boosting ability of top-down decision tree learning algorithms. In Proceedings of the 28th Annual Symposium on the Theory of Computing (STOC), pages 459-468, 1996.
[KM99] Michael Kearns and Yishay Mansour. On the boosting ability of top-down decision tree learning algorithms. Journal of Computer and System Sciences, 58(1):109-128, 1999.
[0] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In International Conference Machine Learning, pages 6150-6160. PMLR, 2020.
[MV20] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. arXiv preprint UrXiv:2006.09123, 2020.
[MZA+] Hayden McTavish, Chudi Zhong, Reto Achermann, Ilias Karimalis, Jacques Chen, Cynthia Rudin, and Margo Seltzer. Fast sparse decision tree optimization via reference ensembles. Proceedings of the AAAI Conference Artificial Intelligence, 36(9).
[NF07] Siegfried Nijssen and Elisa Fromont. Mining optimal decision trees from itemset lattices. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 530-539, 2007.
[NF10] Siegfried Nijssen and Elisa Fromont. Optimal constraint-based decision tree induction from itemset lattices. Data Mining and Knowledge Discovery, 21(1):9-51, 2010.
[NIPMS18] Nina Narodytska, Alexey Ignatiev, Filipe Pereira, and Joao Marques-Silva. Learning optimal decision trees with sat. In Ijeai, pages 1362-1368, 2018.
[O'D14] Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.
[PV F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blon- del, P. Prettenhofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournaeeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 022825-28300 2011.
[Qui86] Ross Quinlan. Induction of decision trees. Machine learning, 1(1):81-106, 1986.
[Qui93] Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993.
[RCC*22] Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong. Interpretable machine learning: Fundamental principles and 10 grand challenges. Statistics Surveys, 16:1-85, 2022.
[Sie08] Detlef Sieling. Minimization of decision trees hard to approximate. Journal of Computer and System Sciences, 74(3):394 403, 2008. Computational Complexity 2003.
[TAA+19] Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In International Conference on Machine Learning, pages 1166-6175. PMLR, 2019.
[VNP+20] Hélene Verhaeghe, Siegfried Nijssen, Gilles Pesant, Claude-Guy Quimper, and Pierre Schaus. Leamning optimal decision trees using constraint programming. Constraints, 25(3):226-250, 2020.
[VZ17] Sicco Verwer and Yingqian Zhang. Learning decision trees with flexible constraints and objectives using integer optimization. In International Conference Al and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 94-103. Springer, 2017.
12

---

[VZ19] Sicco Verwer and Yinggian Zhang. Learning optimal classification trees using binary linear program formulation. Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 1625-1632, 2019.
[7MP+20] 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 Information Processing Systems, 13:177111781, 2020.
13


Reviews:
[{"review_id": "GeKgaYwxhc", "reviewer": "Reviewer_mdbV", "summary": "The paper studies an extension of greedy decision tree algorithms. The main idea is, instead of simply greedily selecting the best feature, to consider several features. This can also be seen as a restriction of optimal decision tree algorithms, so in some sense the studied approach lies somewhere in between greedy and exhaustive algorithm. The point is that greedy approach are fast, optimal algorithms are slow, so something in between may be desirable.\n\nThe authors provide theoretical results and some experiments to illustrate a few points. \n\nEven though the idea of selecting a subset of the features is emphasized in the paper, I find this questionable, e.g., I find that a minor and rather natural point. In my view the main contribution are the theoretical results - these are novel to the best of my knowledge and provide a nice way to formalize relatively intuitive ideas. I think the paper would benefit from focusing on this theoretical aspect since this is a unique point.\n\nWhile I am enthusiastic about the theoretical results, I feel that there are many (small) issues with the paper that need to be addressed before publication. In particular, the relationship with related work needs to be expanded and discussed in more depth, the experiments go in the right direction but the claims are not convincingly backed up by data, and there are several (minor) technical issues.\n", "questions": "I believe the paper does have potential but there are many issues as outlined in the Weakness section. Since there are many issues, I do not have specific questions at this point. I hope my review will help the authors in revising the work, I would be happy to see it refined and published later on. In case I misunderstood something the authors are welcome to point out flaws in my reasoning.\n", "limitations": "This is somewhat discussed in the paper. ", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The theoretical results sound relevant. Recent recent tree works concerning \"practical\" algorithms do not provide virtually any theoretical results, and in this work this is studied formally. The authors also point of the artificialness of the theoretical results, and then propose a more \"realistic\" mathematical setting. All of these points are welcome contributions, and highlight (potential) for good technical depth.\n", "weaknesses": "Conceptual \n\nThe related work is treated very briefly: the related work section is half a page. The text gives a bird's eye overview of the field, which is good, but even this text does not relate to the work done in the paper. I would like to see some more discussion on how related algorithms work and have the authors draw the connection to this approach. This places the work in the right context which is important when publishing a paper. This absence of direct relation to related work is also reflected in the paper later on.\n\nSince the paper covers theory and the authors consider a parameter k, it would be natural to relate this work to the paramaterized complexity of decision trees paper [Parameterized Complexity of Small Decision Tree Learning, AAAI 2021]. This would provide more rigorous analysis.\n\nThe text presents the results as surprising, as going from k to k+1 may make a large difference even though it is only an increase of one. This is a nice observation, and should be mentioned, but the text needs to be toned down. Since the number of decision trees grows exponentially with the number of features, it is clear that going from k to k+1 leads to an exponential increase in number of trees. So it makes sense that this has an impact on accuracy. Note that this does not diminish the value of the contribution, it merely puts it in the right perspective.\n\nThe authors state that considering \"top-k\" compared to \"top-1\" introduces a \"mild\" increase in complexity. However the algorithm increases _exponentially_ with the k parameter, which is also shown in this paper (Claim 3.1). It could be that in practice, if the k is small, the impact is not large in terms of absolute nubmer of seconds, but in theory this is still a large complexity increase. Setting k = number of features leads to the exhaustive algorithm, which is exponential.\n\nI find the idea of top-k interesting and relevant but the idea is rather small. The value of the paper in my view is in the theory part and (possibly improved) experiments. This could be reflected more in the text. Note that the top-k approach has already been implemented in MurTree but I am not sure if there have been thorough evaluations.\n\nDefinition 3 and Lemma 3.2: these follow directly from the algorithm (Figure 1), so it is odd to pack the results as a lemma that has proof in Appendix, makes it sounds more complicated that it is. A simpler proof, if needed to be included, is to show by induction on the recursively formulation in Figure 1.\n\nParallelization is mentioned as an \"easy\" task. First, this is the case with virtually every decision tree algorithm. Second, the situation is only easy on the surface level: it is not trivial to parallelize techniques used by optimal decision tree algorithms (bounding, caching) that give significant runtime improvements, so a trivial parallelization can leads to degradation of performance.\n\nExperiments\n\nThe experiments mention that 100 datasets are available, but the authors select a random subset of 20. But why only 20, why not all? Why not take available datasets that have been directly used in previous works? This seems odd given the ability of the datasets, and the runtimes are still managable.\n\nThe conclusions are made on cherry picked datasets, i.e., only a few datasets even though many datasets are available. The scalability experiments shows that top-k scales much better: this is obvious based on the complexity, but it is still interesting to see. However the dataset seems to be extreme: while other considered datasets have 50-300 features, this dataset has 1400 features. While it is a good idea to use an extreme example to emphasize the scalability problem, this needs to be done all datasets and not just on one.\n\nThe comparison with MurTree and GOSDT is also not entirely proper, since the algorithms solve slightly different problem. MurTree is the most similar, GOSDT is slightly different because of the alpha parameter and no explicit depth. This would need to be discussed, and/or setting the same alpha parameter for MurTree so that the comparisons are more aligned (although in this case this paper does not support the alpha parameter, the authors could also include this parameter).\n\nThe conclusion that after some k value there are no gains in accuracy: this is intuitive and nevertheless interesting, but the conclusion is made on three datasets. It is needed to do more thorough experiments on all datasets to make this claim.\n\nThe authors discuss that top-k can sometimes even lead to better test accuracy. This is problematic for two reasons. First, the method of comparison (dl8.5 in this case) does not optimise in any way for test accuracy, so the comparison is odd. Second, the authors compare against full decision trees, which are prone to overfitting. Since the algorithm is incentivised to use all nodes, it will use all nodes and capture noise in the training data, so it is expected that it will not generalize well. The fix here is to do tuning with not only the depth, but the number of nodes the algorithm is allowed to use, or alternatively use the alpha parameter.\n\nMinor\n\nFigure 5 seems important but it is placed in the Appendix.\n\nPlease provide the intuition behind the proofs. This would add more depth to the paper.\n\nSince monotone is an important concept, please introduce monotonicity for completeness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer mdbV for their helpful feedback. We provide a point-by-point response to Reviewer mdbV’s comments below.\n\nConceptual\n\nW1: We have synthesized a body of additional related work and would be happy to provide it in an additional “Official Comment” if requested. We have currently omitted it from our Rebuttal to respect the length limit.\n\nW2: We will cite this paper. While their work considers a bound on feature domain size, Top-k considers all possible features, but only branches on the first k in each recursive step based on a greedy heuristic.\n\nW3: We will make the text more muted.\n\nW4: We agree with this point. We meant to describe a small absolute increase in runtime and will make this more clear. \n\nW5: We would like to clarify a potentially critical misunderstanding: our proposed algorithm, Top-k, does not select a fixed or predetermined subset of features. Instead, Top-k considers all possible features at each step but only explores the top k of them, as determined by greedy heuristics. Top-k is not doing feature subset selection and, rather, is more similar to a beam search.\n\nMurTree has not implemented the Top-k approach and only considers maximum depth, sparsity, and maximum number of internal nodes. In a comparison to Random Forest done in the MurTree paper, MurTree is run on several randomly generated subsets of the feature domain. In Top-k, all features are considered and k refers to the number of features that are chosen to expand in each step, as ranked by a greedy heuristic. To our knowledge, Top-k has not yet been incorporated into any ODT algorithms.\n\nW6: We will move the proof to the main paper.\n\nW7: Reviewer mdbV is correct about parallelization; we will correct this.\n\nExperiments\n\nW8: The subset on which we ran experiments were a true random sample, not cherry-picked (as described on Lines 269-270). The only dataset that was chosen for illustrative purposes was the dataset with 1400 features. Running on the random subset took over 8 days. Unfortunately, running all 100 datasets would be prohibitively expensive. This is because DL8.5, MurTree, and GOST required large memory allocations and took over 10 minutes to train on most datasets.\n\nW9: Apart from the dataset with 1400 features, which was chosen for direct comparison with the GOSDT paper, all other datasets were a true random sample of the available datasets. This is described on Lines 269-270 of the original submission.\n\nW10: In our experiments, we used the default hyperparameters for the baseline algorithms. Top-k and MurTree share the same depth constraint. For GOSDT, we set the regularization coefficient to 2^{-depth}, as described on Line 302 of our submission. This choice of regularization coefficient sets the same hard depth constraint implicitly. Even in this setting, GOSDT exhibits significantly worse runtime compared to Top-k.\n\nW11: In an additional experiment presented as Figure 1 in the “global” comment to all reviewers, we run this experiment with a 10 second time limit per run, letting Top-k return the best tree discovered within the time limit. We observe that the same trend holds in many other datasets: that increasing k beyond a point does not result in additional gains in accuracy. \n\nIn Figure 2 of our additional experiments, we also run a similar experiment as done for Figure 4. We find that the pattern observed by Figure 4 of our original submission still holds: that increasing k provides marginal or no benefit beyond a certain point and can even lead to overfitting at higher depths.\n\nW12: We agree with Reviewer mdbV’s observation that the baseline ODT algorithms overfit and do not generalize well at higher depths.\n\nWe also note that the restriction on depth implicitly constrains the number of nodes in a tree. Even when ODT algorithms are not able to expand fully due to this depth constraint, we observe that they still overfit. \n\nWe ran an additional experiment to provide further empirical evidence of this observation. In this experiment we replicated Figure 2 from the original paper but expanded to higher depths and values of k by imposing a time limit of $10$ seconds and having Top-k return the best tree discovered within the time limit. The results of this experiment are displayed in Figure 1 of our additional experiments, provided in a “global” comment to all reviewers. We observe that increasing k provides marginal benefits at low to mid depths, and at higher depths, higher values of k experience severe dips in performance. This is due to overfitting and an inability to fully explore the search space. \n\nFor lower k values, Top-k is able to expand to much higher depths and still perform well, whereas ODT overfits. Indeed, this is a weakness of ODT algorithms and a strength of our proposed Top-k approach.\n\nWe also note that Optimal Decision Trees often cannot be trained at very high depths because their training time and memory requirements are too large.\n\nMinor\n\nW13: We will move Figure 5 to the main paper.\n\nW14: The intuition behind Theorems 2 and 3 is that we can design data sets in which the features are in two disjoint groups, “truly important” and “seemingly important” where:\nThe “seemingly important” features are rated more important by the feature scoring function than the “truly important” features,\nAny decision tree built from only “seemingly important” features will have low accuracy.\nIt is possible to build a decision tree using only the “truly important” features that achieves high accuracy.\n\nTo prove our result, we set the number of “seemingly important” features so that Top-k will only select “seemingly important” features, but Top-$(k+1)$ can see past the “seemingly important” features to select the “truly important” features. This construction is possible because impurity heuristics only measure first order correlations; whereas the truly important features have higher order correlations.\n\nW15: We define monotonicity on Line 246 of our original submission."}, {"review_id": "zyrXLNvp6f", "reviewer": "Reviewer_UM1K", "summary": "The paper presents a novel generalization of classic greedy decision tree algorithms called Top-k, which considers recursively the top k attributes for possible splits rather than the single best attribute. It enhances traditional decision tree learning algorithms such as ID3, C4.5, and CART, and is expected to be a significant improvement on these established methodologies. The authors provide both theoretical and empirical proof supporting the effectiveness of this modification.\n\nTheoretically, the authors establish the greediness hierarchy theorem that demonstrates there exist data distributions for which one can expect significant improvements in accuracy as k increases. Empirically, they test Top-k against standard greedy algorithms and optimal decision tree algorithms using real-world datasets. The experimental results reveal that for the same tree depths, Top-k significantly outperforms the classic greedy methods while also being much more scalable than optimal decision tree algorithms.", "questions": "- In gradient-boosting tree ensembles, the depth of each tree is usually small. Can Top-k improve the predictive performance of GBDTs?", "limitations": "The limitations have been discussed in the Conclusion section. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper makes a novel contribution to the field of decision tree learning by introducing the Top-k generalization of classic greedy algorithms. The concept is simple and intuitive, yet it has a profound effect on the performance of the algorithm.\n\n- The authors have provided a detailed theoretical basis for their work. The introduction of the greediness hierarchy theorem gives clear theoretical evidence of the potential benefits of considering more attributes for splits. This robust theoretical grounding is a key strength of this paper.\n\n- A comprehensive experimental evaluation is carried out to back the theoretical findings. The authors evaluate the Top-k approach using UCI datasets, comparing the results with both classic greedy algorithms and optimal decision tree algorithms. The performance of Top-k is compelling, exhibiting significant improvements over classic methods and demonstrating comparable scalability.\n", "weaknesses": "- While Top-k demonstrates stronger performance than classic greedy algorithms for the same tree depths, an additional, more fair setup would be comparing the test accuracy achieved in comparable training time.\n- The runtime scales exponentially with the depth h.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer UM1K for their insightful comments and helpful feedback.\n\nReviewer UM1K Comment 1: While Top-k demonstrates stronger performance than classic greedy algorithms for the same tree depths, an additional, more fair setup would be comparing the test accuracy achieved in comparable training time.\n\nResponse to Reviewer UM1K Comment 1: We would like to clarify the motivation for our proposed algorithm. Optimal Decision Trees (ODTs) are popular because they can be generated in “reasonable time” for shallow depths and offer better accuracy than greedy approaches, not because they achieve better balance between speed and accuracy. Our proposed algorithm, Top-$k$, expands the range of datasets and depths that can be considered in “reasonable time” while still improving upon the accuracy of greedy approaches. As such, our experiments set a “reasonable” bound on the runtime (10 minutes) and take accuracy measurements under this restriction, because accuracy is our key metric (not training time).\n\n\nReviewer UM1K Comment 2: The runtime scales exponentially with the depth h.\n\nResponse to Reviewer UM1K Comment 2: We also note that the runtime scales exponentially with the depth $h$ for all optimal decision tree algorithms (where $k = d$), and for CART and other greedy algorithms (where $k = 1$), where there are exponentially many internal nodes. In future work, we hope to improve upon $(2k)^h$ naive bound as $k$ increases using the techniques from the ODT literature.\n\nReviewer UM1K Comment 3: In gradient-boosting tree ensembles, the depth of each tree is usually small. Can Top-k improve the predictive performance of GBDTs?\n\nResponse to Reviewer UM1K Comment 3: This is an exciting direction for future work. Research into optimal decision tree ensembles is relatively unexplored. The original MurTree paper compares MurTree ensembles to Random Forests; however, further systematic study is necessary. We note that in our proposed algorithm, Top-$k$, the $k=1$ case corresponds to greedy algorithms and therefore subsumes greedy gradient-boosting ensemble methods (with the appropriate training objective). We suspect our method could be applied with $k > 1$ to improve upon existing greedy gradient boosting ensemble methods, though we leave a thorough exploration of this to future work."}, {"review_id": "tQqo7yoHNj", "reviewer": "Reviewer_B1BN", "summary": "In the paper authors propose a new algorithm that allows balancing between two approaches to decision tree learning: fully greedy optimization, and exactly optimal decision tree construction.  Authors discuss the long standing line of research that focuses on either ends of this balance, and propose a novel algorithm Top-K that solves the issues of both sides:\n- Greedy algorithms are fast, but there are counterexamples that lead to arbitrarily bad accuracy\n- Optimal algorithms are inherently slow because of the NP-hardness of the problem.\n\nThe Top-K algorithm is backed up by several theorems that show that increasing K allows solving counterexamples that are unsolvable with high enough accuracy using smaller K. While some of the counterexamples involve artificial constructions, authors propose evaluation on real-world datasets that show practical applicability of the proposed method.", "questions": "- Since the paper provides one way to balance between fully-greedy and fully-optimal approaches, reader may be curious whether there other possible ways to achieve a balance between those two ends (This may be addressed in the future work, or perhaps authors already have an answer about why Top-K was implemented in a given way, and what could be other possible implementations?)\n- There is a line of research on optimizing the Optimal Decision tree algorithm: for example, using Dynamic Programming. While it does not solve the problem of slow running time of the Optimal Algorithm due to NP-hardness of the problem, it allows obtaining different running time bounds, that may be better than fully brute-force search for specific problem sizes and parameters. Would be nice to know whether such optimizations are applicable to the proposed Top-K algorithm (this may be a topic of future work, but perhaps authors already have answers to this question?)\n- We see from the experimental results that Top-K outperforms Top-1 on the test set; but in the current implementation Top-K uses binarization and is compared to Top-1 that also uses binarization of the features. Does this binarization significantly reduce the accuracy compared to using a non-binarized dataset? Specifically, what would happen if Top-1 would run on a non-binarized version (because standard Top-1 greedy solvers, such as the ones from scikit-learn do not require binarization of the dataset)? \n", "limitations": "Main concern about limitations is the applicability to problem settings other than binary classification with binary features (outlined in the above sections of the review)\n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Most importantly, this is a novel contribution to the field of Decision Trees learning. The proposed algorithm is easy to implement, theoretically sound, and solves major issues of the existing approaches.\n\nOn a side note, the paper is well-written, provides convincing motivational examples, a thorough literature review, strong theoretical foundation and a clear description of the algorithms.\n", "weaknesses": "No major weaknesses. There is one concern outlined below, and other questions (which may be addressed here or solved in the future work) are placed in the \"Questions\" section.\n- The paper focuses on a binary classification setting. And features are also binary in the theorems and definitions. This was confirmed in the experimental section, where categorical features have been converted to binary and numerical features had to be thresholded and converted to binary. This raises a question about applicability to non-binary data; and more importantly, to a regression setting (which is equally practically popular, as classification). Clearly stating this limitation or addressing possible ways to extend both theoretical and practical results will help in convincing the reader about usefulness of the proposed algorithm in real world settings and clarify how high is the impact of the paper on the Decision Trees learning field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer B1BN for their insightful comments and helpful feedback.\n\nReviewer B1BN Comment 1: The paper focuses on a binary classification setting. And features are also binary in the theorems and definitions. This was confirmed in the experimental section, where categorical features have been converted to binary and numerical features had to be thresholded and converted to binary. This raises a question about applicability to non-binary data; and more importantly, to a regression setting (which is equally practically popular, as classification). Clearly stating this limitation or addressing possible ways to extend both theoretical and practical results will help in convincing the reader about usefulness of the proposed algorithm in real world settings and clarify how high is the impact of the paper on the Decision Trees learning field.\n\n\nResponse to Reviewer B1BN Comment 1: We would like to clarify a few points regarding binarization of the datasets. First, we chose to consider binary datasets primarily for comparison with prior work, as many SOTA Optimal Decision Tree algorithms are restricted to binary datasets, and for theoretical analysis. \n\nHowever, this is not a restriction of our work as our proposed Top-$k$ algorithm can be easily generalized to non-binary data. For example, we may also consider the $k$ best feature splits by considering the top $k$ (feature, threshold) pairs or, instead, consider the top $k$ features and select the best threshold for each feature based on a heuristic – either approach would work in the non-binary data setting.\n\nLastly, we note that every dataset can be appropriately binarized by appropriately thresholding each feature, and an advantage of our proposed Top-$k$ algorithm is that it works better than existing approaches when this binarization process introduces many more features. \n\nThe modification for regression is also simple. In classification, at each leaf, we put the most frequent label among training points that reach that leaf. In regression, we would simply put the mean of the label among such training points (e.g., if the goal is to minimize $L_2$ loss).\n\nReviewer B1BN Comment 2: Since the paper provides one way to balance between fully-greedy and fully-optimal approaches, reader may be curious whether there other possible ways to achieve a balance between those two ends (This may be addressed in the future work, or perhaps authors already have an answer about why Top-K was implemented in a given way, and what could be other possible implementations?)\n\nResponse to Reviewer B1BN Comment 2: To the best of our knowledge, Top-$k$’s ability to interpolate between fully-greedy and fully-optimal approaches is novel. Indeed, this is a key strength of our work. \n\nWe note that a recent paper [1] extends DL8.5 to achieve better anytime behavior via iterated limited discrepancy search. This approach is much slower than Top-$k$, because the number of iterations to achieve optimality is very large, and there are no theoretical performance guarantees for intermediate steps of the algorithm, but this work may nonetheless be of interest to the reviewer. We will add [1] to our related work section.\n\n[1: ​​Time Constrained DL8.5 Using Limited Discrepancy Search, ECML PKDD 2022]\n\nReviewer B1BN Comment 3: There is a line of research on optimizing the Optimal Decision tree algorithm: for example, using Dynamic Programming. While it does not solve the problem of slow running time of the Optimal Algorithm due to NP-hardness of the problem, it allows obtaining different running time bounds, that may be better than fully brute-force search for specific problem sizes and parameters. Would be nice to know whether such optimizations are applicable to the proposed Top-K algorithm (this may be a topic of future work, but perhaps authors already have answers to this question?)\n\nResponse to Reviewer B1BN Comment 3: These optimizations are indeed applicable to our proposed Top-$k$ algorithm and we have already implemented them. Appendix Figure 5 of our original submission describes our algorithm with these optimizations. Our implementation is actually an extension of DL8.5, a state-of-the-art Optimal Decision Tree (ODT) algorithm, and incorporates many of its optimizations.\n\nReviewer B1BN Comment 4: We see from the experimental results that Top-K outperforms Top-1 on the test set; but in the current implementation Top-K uses binarization and is compared to Top-1 that also uses binarization of the features. Does this binarization significantly reduce the accuracy compared to using a non-binarized dataset? Specifically, what would happen if Top-1 would run on a non-binarized version (because standard Top-1 greedy solvers, such as the ones from scikit-learn do not require binarization of the dataset)?\n\nResponse to Reviewer B1BN Comment 4: We would like to emphasize that we used binarization primarily for comparison with prior SOTA Optimal Decision Tree algorithms, which require binary datasets. We anticipate that extending Top-$k$ to the non-binary case would be simple and the comparisons to CART demonstrate similar results (see our response to Comment 1)."}, {"review_id": "Iy3aPuy4VS", "reviewer": "Reviewer_8rCb", "summary": "The paper is about a new method for machine learning using decision trees. Namely, the authors propose an algorithm that can span the spectrum of the methods that are currently used: \n(i) traditional decision tree learning algorithms that choose features and splitting points based on a criterion that is optimized greedily (e.g., gini impurity), and \n(ii) optimal decision tree learning, which performs an exhaustive search for the best possible short decision tree (we should also have fairly few candidate features for splitting). \n\nIn particular, the authors allow a parameter k that controls the amount of splits that will be considered at every node. In other words, the authors consider the top k greedy choices at every node. This allows one to consider exponentially many trees, and thus choose the best tree among those considered. Note that when k=1, the algorithm reduces to the standard greedy algorithms such as C4.5 and CART, whereas when k=d (where d is the dimension of the instances), we obtain an algorithm that constructs an optimal decision tree.\n\nThe authors have some nice results to complement the proposed approach. For example, in Theorem 1 of the paper, it is shown that there are data distributions where a (k+1) branching factor would allow accuracy of 1-ε, while a branching factor of k can achieve accuracy at most 1/2 + ε. The authors also show (in Theorem 2) a generalization of the previously mentioned theorem. Eventually the authors show experimentally that the proposed algorithm behaves well in an experimental setting with the solutions provided between the two extremes of optimal decision tree learning and pure greedy methods that have been used for decades. In other words, through the experiments, the authors highlight the tradeoff one would be willing to explore by spending some extra time on constructing decision trees that can potentially allow the user to achieve better accuracy, while at the same time one would be able to create much deeper trees, much faster, compared to optimal decision trees.\n\nAfter the rebuttal: Upgraded the score from borderline accept to weak accept since I was satisfied with the responses that I received and largely with the responses that the authors gave to the comments and issues that were raised by the other reviewers.", "questions": "Q1. How many runs did you use for the results in Figure 2? Are the conclusions based on statistically significant observations?\n\nQ2. On a related note, in Figure 2, in the case of spambase (and some other cases), MurTree that calculates the optimal decision tree, provides a solution with worse accuracy compared to what the authors achieve with their method. Can the authors shed some light in this? Also, another observation has to do with the fact that on the same graph (spambase), at depth 8, top-2 outperforms top-3. Is there an explanation for this?", "limitations": "I think the paper is ok.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think this is a well-written paper that is also backed up with theoretical analysis and is also validated (to a large extent) in the experiments. It is an interesting algorithm that appears to be improving the accuracy of the learned decision trees in many practical datasets, while at the same time the increase in performance is probably tolerable. The paper also has a fairly nice summary of related work.", "weaknesses": "The paper is not based on any striking new idea. While the novelty is limited, it is nevertheless interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reviewer 8rCb Comment 1: The paper is not based on any striking new idea. While the novelty is limited, it is nevertheless interesting.\n\nResponse to Reviewer 8rCb Comment 1: We believe the simplicity of our ideas, combined with theoretical performance guarantees and the fact that these ideas work well empirically, are strengths of our work. Regarding novelty, prior work has focused only on either end of the spectrum: greedy tree construction or optimal tree construction. In our framework, greedy tree construction corresponds to $k=1$ and optimal tree construction corresponds to $k=d$. Our theoretical results show that there always exists a dataset for which increasing $k$ can be valuable. We believe that our work unifies the approaches at either end of the spectrum and provides useful theoretical results and examples that can guide the choice of $k$ to interpolate between fast, greedy tree construction and slow, optimal tree construction. We consider our theoretical contribution nontrivial and believe that it strongly motivates the Top-$K$ algorithm. As such, we believe both our theoretical motivation and proposed Top-$k$ algorithm are novel.\n\nReviewer 8rCb Comment 2: How many runs did you use for the results in Figure 2? Are the conclusions based on statistically significant observations?\n\nResponse to Reviewer 8rCb Comment 2: 10 runs were used for each of the plots in Figure 2 and +/- 2 standard error confidence intervals are shown; this is described in the caption for Figure 2. Conclusions are based on statistically significant observations; we generally see that Top-$(k+1)$ outperforms Top-$k$ because their confidence intervals are disjoint (with some exceptions). We note that, as described in the caption for Figure 2, missing points in the plots correspond to settings that did not terminate within a sufficiently large time limit (usually corresponding to the case where $k = d$, i.e., fully optimal decision trees).\n\nReviewer 8rCb Comment 3: On a related note, in Figure 2, in the case of spambase (and some other cases), MurTree that calculates the optimal decision tree, provides a solution with worse accuracy compared to what the authors achieve with their method. Can the authors shed some light in this?\n\nResponse to Reviewer 8rCb Comment 3: MurTree optimizes for train accuracy and, like other ODT algorithms, overfits at higher depths. This is in contrast with our Top-$k$ algorithm, which demonstrates less overfitting for lower values of $k$. Our restriction to the top $k$ features in each recursive step of tree construction can be seen as a form of regularization similar to how Random Forest considers a subset of features at each node split.\n\nReviewer 8rCb Comment 4: Also, another observation has to do with the fact that on the same graph (spambase), at depth 8, top-2 outperforms top-3. Is there an explanation for this?\n\nResponse to Reviewer 8rCb Comment 4: In this setting, Top-$3$ is also overfitting to the training data because there are many features to consider in this dataset. Top-$2$ demonstrates less overfitting and therefore generalizes better."}]

Author rebuttal:
Attached please find new experimental results which we refer to in our rebuttals to reviewers.

Meta-review: The paper extends decision tree construction from greedy to beam search, ie. allowing to optimize recursively over k splits at each node instead of 1. When k equals to 1, we have standard greedy trees and when k equals to the number of features, we have optimal decision trees. They show theoretically that there exist problems (kinds of XOR problems) for which increasing k by 1 is beneficial. They then perform experiments in which they compare their method to standard greedy trees and optimal decision tree algorithms on 20 problems.
		
One of the reviewers strongly suggests rejection, while all other reviewers clearly recommend acceptance. The main limitations of the work that were identified in the reviews and subsequent discussions are the following:
- The treatment of the related literature is not complete enough (reviewer mdbV spotted several missing references and errors in the treatment of related works).
- The paper overlooks a bit the computational complexity of the proposed method. The Top-k method is more efficient than existing optimal tree algorithms for small k but it scales exponentially with respect to tree depth and is probably not competitive with these methods when k is at its maximum value. The argument that it can be made trivially efficient by parallelisation is a bit naive, as this would require an exponential number of jobs and this would also benefit other methods. The reviewers and I suggest to remove or tone down the discussions about parallelisation.
- Experiments have limitations. There were discussions about the selection of only 20 datasets and the fairness of the comparison against optimal tree algorithms. The three positive reviewers are however convinced that the datasets were not cherry-picked and that the experiments provide enough evidence of the interest of the approach. I tend to agree although I believe that some important experiments are nevertheless missing. It would have been more informative to compare the performance of top-k against optimal tree algorithms on the training set instead of the test set (since this is what optimal tree algorithms are targeting, as highlighted by reviewer mdbV).  Additionally, the experiments do not clearly highlight the benefit of top-k against standard greedy trees. Indeed, the experimental setting is very far from the way one would use decision trees in practice (mostly the features would be not be discretised and the tree complexity would be tuned). It’s not obvious that top-k would still be performing well in a more realistic setting. Actually, given the way the results are presented in the paper, I found it difficult to really compare top-1 with top-k, in terms of test accuracy and computing times (it's not easy to link improvements in Figure 2 with computing times in Figure 6).
			
Despite these limitations, all reviewers however agree that the proposed method is novel, relevant, and that it deserves to be studied. They are also positive about the theoretical analyses in the paper. For these reasons, I recommend acceptance. However, I urge the authors to consider Reviewer mdbV's comments about the treatment of related works and also to try to address the other points mentioned in the reviews and this meta-review, in order to strengthen their contribution.
Decision: Accept (poster)