Learning Accurate and Interpretable Decision Trees (Extended Abstract)

1 Introduction

Decision trees are ubiquitous, with applications in operations research, management science, data mining, and machine learning. They are easy to use and understand models that explicitly include the decision rules used in making predictions. Each decision rule is a simple comparsion of a real-valued attribute to a threshold or a categorical attribute against a candidate set of values. Given their remarkable simplicity, decision trees are widely preferred in applications where it is important to justify algorithmic decisions with intuitive explanations [Rudin, 2018]. However, decades of research on decision trees has resulted in a large suite of candidate approaches for building decision trees [Breiman et al., 1984; Mingers, 1987; Quinlan, 1993; Quinlan, 1996; Kearns and Mansour, 1996; Mansour, 1997; Maimon and Rokach, 2014]. This raises an important question: how should one select the best approach to build a decision tree for the relevant problem domain?

∗ Full version appears in the proceedings of UAI 2024 [Balcan and Sharma, 2024], winner of Outstanding Student Paper Award.

Several empirical studies have been performed comparing various ways to build decision trees [Mingers, 1989b; Esposito et al., 1997]. Current wisdom from the literature dictates that for any problem at hand, one needs a domain expert to try out, compare and tune various methods to build the best decision trees for any given problem domain. For instance, the popular Python library Scikit-learn [Pedregosa et al., 2011] implements both Gini impurity and entropy as candidate 'splitting criteria' (a crucial component in building the decision trees top-down by deciding which node to split into child nodes), and yet theory suggests another promising candidate [Kearns and Mansour, 1996] that achieves smaller error bounds under the Weak Hypothesis Assumption 1 . It is therefore desirable to determine which approach works better for the data coming from a given domain. With sufficient data, can we automate this tedious manual process?

In this work we approach this crucial question, and propose ways to build more effective decision trees automatically. Our results show provable learning theoretic guarantees and select methods over larger search spaces than what human experts would typically explore. For example, instead of comparing a small finite number of splitting criteria, we examine learnability over continuously infinite parameterized families that yield more effective decision tree learning algorithms.

We consider the problem where the learner has access to multiple related datasets D1, . . . ,DN coming from the same problem domain (given by a fixed but unknown distribution D), and the goal is to design a decision tree learning algorithm that works well over the distribution D using as few datasets (N, the sample complexity) as possible. This algorithm design problem is typically formulated as the selection of a hyperparameter from an infinite family. Typically finding the best hyperparameters even on a single problem sample is tedious and computationally intensive, so we would like to bound the number of samples over which we should optimize them, while learning parameters that generalize well over the distribution generating the problem samples. We take steps towards systematically unifying, automating and formalizing the process of designing decision tree learning algorithms, in a way that is adaptive to the data domain.

1 an a priori assumption on the target function. Roughly speaking, it means that the decision tree node functions are already slightly correlated with the target function.

1.1 Our Contributions

We formulate the problem of designing a decision tree learning algorithm as a hyperparameter selection problem over multiple problem instances coming from the same domain. Under this formulation, we study the sample complexity, i.e. the number of problem instances needed to learn a provably good algorithm (hyperparameter) under the statistical learning setting (meaning problem instances are drawn from a fixed but unknown distribution) from several different design perspectives important in the construction of decision trees. A key technical challenge is the non-linearity of boundaries of the piecewise structured dual loss function.

• We introduce a novel family of node splitting criterion called (α, β)-Tsallis entropy criterion, which contains two tunable parameters, and includes several popular node splitting criteria from the literature including the entropybased ID3/C4.5 [Quinlan, 1986; Quinlan, 1993] and Gini impurity based CART [Breiman et al., 1984]. We bound the sample complexity of provably tuning these hyperparameters in top-down learning algorithms. We perform experiments to show the practical significance and effectiveness of tuning these hyperparameters on real world datasets.
• We further study tuning of parameters in Bayesian decision tree learning algorithms used in generating the prior distribution. We also study a parameterized family for node splitting for regression trees and bound the sample complexity of tuning the parameter.
• We next consider the problem of learning the pruning algorithm used in constructing the decision tree. We show how to tune parameters in popular algorithms including the complexity parameter ˜α in the Minimal Cost-Complexity Pruning algorithm, and again obtain sample complexity bounds. We also study the sample complexity of tuning pessimistic error pruning methods, which are computationally faster.
• We consider the problem of optimizing the explainabilityaccuracy trade-off in the design of decision tree learning algorithms. Here we consider tuning splitting and pruning parameters simultaneously when growing a decision tree to size t and pruning it down to size t′ ≤ t, while minimizing an objective that incorporates explainability as well as accuracy. Our work is the first to study explainability from a data-driven design perspective.

We highlight the first couple of contributions above in this extended abstract. For further details on the other contributions, see the full version [Balcan and Sharma, 2024].

1.2 RelatedWork

Building and pruning decision trees. Typically, decision trees are built in two stages. First the tree is grown in a top-down fashion by successively 'splitting' existing nodes according to some splitting criterion. Numerous different methods to select which node to split and how to split have been proposed in the literature [Breiman et al., 1984; Quinlan, 1993; Kearns and Mansour, 1996]. The second stage involves pruning the tree to avoid overfitting the training set, and again a variety of approaches are known [Breiman et al., 1984; Mingers, 1987; Quinlan, 1987; Mansour, 1997]. Furthermore, empirical works suggest that the appropriate method to use depends on the data domain at hand [Mingers, 1989a; Mingers, 1989b]. The task of selecting the best method or tuning the hyperparameters for a method is left to domain expert. Recent work has developed techniques for computing the optimal decision trees by using branch-and-bound and dynamic programming based techniques [Hu et al., 2019; Lin et al., 2020; Demirovi´c et al., 2022]. The key idea is to reduce the search space by tracking bounds on the objective value. However, these approaches are computationally more expensive than the classical greedy methods.

Data-driven algorithm designis a recently introduced framework [Gupta and Roughgarden, 2016] for designing algorithms using machine learning in order to optimize performance over problems coming from a common problem domain (see [Balcan, 2020] for a survey). The basic premise is to design algorithms for typical inputs instead of worst-case inputs by examining repeated problem instances. In machine learning, this can be used to provably tune hyperparameters (Balcan et al. [2018a; 2018b; 2023b; 2023a; 2024b], Blum et al. [2021], Bartlett et al. [2022], Sharma et al. [2023; 2024; 2025]) as opposed to employing heuristics like grid search or random search [Bergstra and Bengio, 2012] for which formal global-optimality guarantees are typically not known. General techniques have been developed in previous works [Balcan et al., 2024a] for providing the sample complexity of tuning a linear combination of variable selection policies in branch-and-bound, and special cases of "path-wise" node selection policies have been studied [Balcan et al., 2021]. In contrast, our work provides new technical insights for node selection policies relevant for decision tree learning which do not satisfy the previously studied path-wise properties and involve a more challenging non-linear interpolation. Prior work obtains a general result for tree search without any path-wise assumptions, but still require a linear interpolation of selection policies.

2 Data-driven Top-down Learning

Let [k] denote the set of integers {1, 2, . . . , k}. A (supervised) classification problem is given by a labeled dataset D = (X, y) over some input domain X ∈ X n and y ∈ Y n = [c]n where c denotes the number of distinct classes or categories. Let D be a distribution over classification problems of size n. We will consider parameterized families of decision tree learning algorithms, parameterized by some parameter ρ ∈ P ⊆ Rd and access to datasets D1, . . . , DN ∼ DN . We do not assume that individual data points (Xi, yi) are i.i.d. in

Algorithm 1 Top-down decision tree learner (F, gρ, t)

Input: Dataset D = (X, y)

Parameters: Node function class F, splitting criterion gρ ∈

GP, tree size t

Output: Decision tree T

• 1: Initialize T to a leaf node labeled by most frequent label y in D.
• 2: while T has at most t internal nodes do
• 3: l∗ , f ∗ ← argminl∈leaves(T ),f∈FGρ(Tl→f )
• 4: T ← Tl∗→f ∗
• 5: return T

any dataset Dj .

We consider a finite node function class F consisting of boolean functions X → {0, 1} which are used to label internal nodes in the decision tree, i.e. govern given any data point x ∈ X whether the left or right branch should be taken when classifying x using the decision tree. Any given data point x ∈ X corresponds to a unique leaf node determined by the node function evaluations at x along some unique root-to-leaf path. Each leaf node of the decision tree is labeled by a class in [c]. Given a dataset (X, y) this leaf label is typically set as the most common label for data points x ∈ X which are mapped to the leaf node.

We denote by Tl→f the tree obtained by splitting the leaf node l, which corresponds to replacing it by an internal node labeled by f and creating two child leaf nodes. We consider a parameterized class of splitting criterion GP over some parameter space P consisting of functions gρ : [0, 1]c → R≥0 for ρ ∈ P. The splitting criterion governs which leaf to be split next and which node function f ∈ F to be used when building the decision tree using a top-down learning algorithm which builds a decision tree by successively splitting nodes using gρ until the size equals input tree size t. More precisely, suppose w(l) (the weight of leaf l) denotes the number of data points in X that map to leaf l, and suppose pi(l) denotes the fraction of data points labeled by y = i ∈ [c] among those points that map to leaf l. The splitting function over tree T is given by

and we build the decision tree by successively splitting the leaf nodes using node function f which cause the maximum decrease in the splitting function. For example, the information gain criterion may be expressed using gρ({pi(l)}ci=1 ) = - ∑ci=1 pi log pi.

Algorithm 1 summarizes this well-known general paradigm. We denote the tree obtained by the top-down decision tree learner on dataset D as TF,ρ,t(D). We study the 0-1 loss of the resulting decision tree classifier. If T(x) ∈ [c] denotes the prediction of tree T on x ∈ X , we define the loss on dataset D(X, y) as L(T,D) := 1n ∑ni=1 I[T(Xi) ̸= yi], where I[·] denotes the 0-1 valued indicator function.

2.1 Learning to Split Nodes

In this section, we study the sample complexity of learning the splitting criteria. Given a discrete probability distribution P = {pi} with ∑ci=1 pi = 1, we define (α, β)-Tsallis entropy as

where C is a normalizing constant (does not affect Algorithm 1), α ∈ R+, β ∈ Z+. β = 1 corresponds to standard Tsallis entropy [Tsallis, 1988]. For example, α = 2, β = 1 corresponds to Gini impurity, α = 1 2 , β = 2 corresponds to the Kearns and Mansour [1996] criterion (using which error ϵ can be achieved with trees of size poly(1/ϵ)) and limα→1 g TSALLIS α,1 (P) yields the (Shannon) entropy criterion.

We consider α ∈ R+ and β ∈ [B] for some positive integer B, and observe that several previously studied splitting criteria can be readily obtained by setting appropriate values of parameters α, β. We consider the problem of tuning the parameters α, β simultaneously, given access to multiple problem instances (datasets) drawn from some distribution D. The goal is to find parameters ˆα, ˆ β based on the training samples, so that on a random D ∼ D, the expected loss ED∼DL(TF,(ˆα,ˆ β),t ,D) is minimized. We will bound the sample complexity of the ERM Empirical Risk Minimization (ERM) principle, which given N problem samples D1, . . . ,DN computes parameters ˆα, ˆ β such that

We obtain the following guarantee on the sample complexity of learning a near-optimal splitting criterion. The overall argument involves an induction on the size t of the tree (which has appeared in several prior works including Megiddo [1978] and Balcan et el. [2018a; 2021]), coupled with a counting argument for upper bounding the number of parameter sub-intervals corresponding to different behaviors of Algorithm 1 given a parameter interval corresponding to a fixed partial tree corresponding to an intermediate stage of the algorithm.

Theorem 1. Suppose α > 0 and β ∈ [B]. For any ϵ, δ > 0 and any distribution D over problem instances with n examples, O( 1 ϵ2 (t(log |F|+log t+c log(B+c))+log 1δ )) samples drawn from D are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the parameters ˆα, ˆ β learned by ERM over the sample have expected loss that is at most ϵ larger than the expected loss of the best parameters α∗ , β∗ = argminα>0,β≥1ED∼DL(TF,(ˆα, ˆ β),t ,D) over D. Here t is the size of the decision tree, F is the node function class used to label the nodes of the decision tree and c is the number of label classes.

2.2 Experiments

We examine the significance of the novel splitting techniques and the importance of designing data-driven decision tree learning algorithms via hyperparameter tuning for various benchmark datasets from the UCI repository.

We first study the effect of choice of (α, β) parameters in the Tsallis entropy based splitting criterion. For each dataset, we perform 5-fold cross validation for a large grid of parameters depicted in Figure 1 and measure the accuracy on held out test set consisting of 20% of the datapoints (i.e. training datasets are just random subsets of the 80% of the dataset used for learning the parameters). We implement a slight variant of Algorithm 1 which grows the tree to maximum depth of 5 (as opposed to a fixed size t). We do not use any pruning here. There is a remarkable difference in the optimal parameter settings for different datasets. Moreover, carefully chosen values of (α, β) significantly outperform standard heuristics like Gini impurity or entropy based splitting, or even specialized heuristics like [Kearns and Mansour, 1996] for which worst-case error guarantees (assuming weak learning) are known. This further underlines the significance of data-driven algorithm design for decision tree learning.

2.3 Bayesian Decision Tree Models

Several Bayesian approaches for building a decision tree have been proposed in the literature [Chipman et al., 1998; Chipman et al., 2002; Wu et al., 2007]. The key idea is to specify a prior which induces a posterior distribution and a stochastic search is performed using Metropolis-Hastings algorithms to explore the posterior and find an effective tree. We will summarize the overall approach below and consider the problem of tuning parameters in the prior, which control the accuracy and size of the tree. Unlike most of prior research on data-driven algorithm design which study deterministic algorithms, we will analyze the learnability of parameters in a randomized algorithm. One notable exception is the study of random initialization of centers in k-center clustering via parameterized Llyod's families [Balcan et al., 2018b].

σ, ϕ-Bayesian algorithm family. Let F = (f1, . . . , ft) denote the node functions at the nodes of the decision tree T. The prior p(F, T) is specified using the relationship

We start with a tree T consisting of a single root node. For any node τ in T , it is split with probability pSPLIT(τ) = σ(1+ dτ)-ϕ , and if split, the process is repeated for the left and right children. Here dτ denotes the depth of node τ , and σ, ϕ are hyperparameters. The size of generated tree is capped to some upper bound t. Intuitively, σ controls the size of the tree and ϕ controls its depth. At each node, the node function is selected uniformly at random from F. This specifies the prior p(T). The conjugate prior for the node functions F = (f1, . . . , ft) is given by the standard Dirichlet distribution of dimension c - 1 (recall c is the number of label classes) with parameter a = (a1, . . . , ac), ai > 0. Under this prior, the label predictions are given by

where nji = ∑k I(yjk = i) counts the number of datapoints with label i at node j, nj = ∑i nji and i = 1, . . . , c. a is usually set as the vector (1, . . . , 1) which corresponds to the uniform Dirichlet prior. Finally the stochastic search of the induced posterior is done using the Metropolis-Hastings (MH) algorithm for simulating a Markov chain [Chipman et al., 1998]. Starting from a single root node, the initial tree T 0 is grown according to the prior p(T ). Then to construct T i+1 from T i , a new tree T ∗ is constructed by splitting a random node using a random node function, pruning a random node, reassigning a node function or swapping the node functions of a parent and a child node. Then we set T i+1 = T ∗ with probability q(T i , T ∗ ) according to the posterior p(y | X, T), or keep T i+1 = T i otherwise. The algorithm outputs the tree T ω where ω is typically a fixed large number of iterations (say 10000) to ensure that the search space is explored sufficiently well.

Hyperparameter tuning. We consider the problem of tuning of prior hyperparameters σ, ϕ, to obtain the best expected performance of the algorithm. To this end, we define z = (z1, . . . , zt-1) ∈ [0, 1]t-1 as the randomness used in generating the tree T according to p(T). Let Tz,σ,ϕ denote the resulting initial tree. Let z′ denote the remaining randomness used in the selecting the random node function and the stochastic search, resulting in the final tree T(Tz,σ,ϕ, z′ , ω). Our goal is to learn the hyperparameters σ, ϕ which minimize the expected loss

where D denotes the distribution according to which the data D is sampled, and L denotes the expected fraction of incorrect predictions by the learned Bayesian decision tree. ERM over a sample D1, . . . ,Dn ∼ Dn finds the parameters ˆσ, ˆ ϕ which minimize the expected average loss 1n ∑ni=1 Ez,z′L(T(Tz,σ,ϕ, z′ , ω),Di) over the problem instances in the sample. It is not clear how to efficiently implement this procedure. However, we can bound its sample complexity and prove the following guarantee for learning a near-optimal prior for the Bayesian decision tree.

Theorem 2 (informal). Suppose σ, ϕ > 0. The sample complexity of tuning the parameters (with at most ϵ error and high probability at least 1 - δ) in the σ, ϕ-Bayesian algorithm family is O( 1 ϵ2 (log t + log 1δ )) given samples from an arbitrary distibution D (in the sense of Theorem 1).

Acknowledgments

We thank Avrim Blum, Misha Khodak, Hedyeh Beyhaghi, Siddharth Prasad and Keegan Harris for helpful comments. This material is based on work supported by the National Science Foundation under grants CCF1910321, IIS 1901403, SES 1919453, ECCS-2216899, and ECCS-2216970; and the Defense Advanced Research Projects Agency under cooperative agreement HR00112020003.