Decision trees have been central to machine learning since its early days. They give a simple way to represent a dataset in a hierarchical and logical manner, and they are perhaps the most canonical example of an intepretable model. They are also quick to evaluate, with evaluation time scaling with the depth of the tree, a quantity that is typically exponentially smaller than the overall number of nodes. Classic decision tree learning algorithms such as ID3 (Quinlan, 1986), C4.5 (Quinlan, 1993), and CART (Breiman et al., 1984), as well as tree-based ensemble methods such as random forests (Breiman, 2001) and XGBoost (Chen & Guestrin, 2016), are therefore standard techniques in the modern machine learning toolkit.
Impurity-based algorithms are a broad class that captures ID3, C4.5, CART, and indeed essentially all decision tree Proceedings of the 39 th International Conference on Machine Learning, Baltimore, Maryland, USA, PMLR 162, 2022. Copyright 2022 by the author(s). algorithms used in practice. These algorithms build a binary decision tree for a labeled dataset S in a greedy top-down fashion. Each algorithm A G is defined by an impurity function G : [0, 1] → [0, 1] and a class H of allowable splitting functions. The root of the tree built by A G corresponds to the split of S into S 0 and S 1 by a function h ∈ H that maximizes the purity gain with respect to G. The left and right subtrees are built by recursing on S 0 and S 1 respectively. We elaborate on this framework in the body of the paper, mentioning for now that the standard algorithms ID3, CART, and C4.5 can all be cast within this framework: ID3 and C4.5 use the binary entropy function G(p) = H 2 (p) and the associated purity gain is commonly called information gain, whereas CART uses the Gini impurity function G(p) = 4p(1 -p).
Prior work on provable performance guarantees. Motivated by the empirical success of impurity-based decision tree algorithms, a fruitful and ongoing line of work has focused on establishing provable guarantees on their performance in a variety of models and settings (Kearns & Mansour, 1996;Kearns, 1996;Dietterich et al., 1996;Fiat & Pechyony, 2004;Lee, 2009;Blanc et al., 2020b;a;Brutzkus et al., 2019;2020;Blanc et al., 2021a).
However, these existing results either only hold in the noiseless setting or require strong and stylized assumptions that limit their practical relevance. For example, the recent work of Blanc et al. (2020a) provides guarantees under the assumptions that examples are distributed according to a product distribution, that noise only affects the labels and not the features (i.e. agnostic noise (Haussler, 1992;Kearns et al., 1994)), and that the corrupted labels are monotone in the features.
Using the framework of boosting, we prove that all impuritybased decision tree algorithms are highly noise tolerant in a fully general setting: our results apply to arbitrary distributions over features and labels, and we consider the strongest noise model, allowing for adversarial corruptions of both features and labels (i.e. the nasty noise model of Bshouty et al. (2002), also known as strong contamination). Equivalently, we give the first formal guarantees on the robustness of impurity-based decision tree algorithms to distributional shifts; we elaborate on this perspective in the body of the paper. We further provide near-matching upper and lower bounds on the allowable noise rate, showing that our analysis is essentially optimal.
Lastly, specializing this result to the setting of product distributions over features, we show that these algorithms enjoy provable guarantees in the noisy setting that are unmatched by existing algorithms in the sizeable theoretical literature on decision tree learning. Most of these algorithms were developed after the invention of ID3, C4.5, and CART in the 1980s, and are more complicated and much less used in practice.
In more detail, our first result is the following: Theorem 1.1 (Impurity-based algorithms are noise-tolerant boosting algorithms; see Theorem 3.1 for formal version). For all impurity functions G and distributions D over features and labels, w.h.p. over the draw of a sample S from D, if A G is trained on an η-nasty-noise corruption S of S where η ≤ O(εγ), as long as the internal nodes of the tree are γ-advantage hypotheses, growing the tree to size exp(O(1/γ 2 ε 2 )) achieves error ≤ ε.
In one of the first papers to study impurity-based decision tree algorithms from a theoretical perspective, Kearns & Mansour (1996) showed that they can be viewed as boosting algorithms. Theorem 1.1 generalizes these results of Kearns & Mansour (1996) to the setting of adversarial noise and shows that these algorithms are in fact highly noise-tolerant boosting algorithms.
Optimality of Theorem 1.1. Next, we show that the quantitative parameters of Theorem 1.1 are essentially optimal. First, even in the noiseless setting it can be seen that there are target functions for which the tree needs to be grown to size exp(Ω(1/γ 2 )) to achieve high accuracy; this was already observed in Kearns & Mansour (1996);Freund (1995). Second, we prove that the guarantees of Theorem 1.1 cannot hold for noise rates η ≥ Ω(εγ), even under strong feature and distributional assumptions: Theorem 1.2 (Near-matching lower bound on noise rate; see Theorem 4.1 for formal version). Let the feature space be X = {±1} d and η ≥ Ω(εγ). There is a distribution D whose marginal over X is uniform, such that for all impurity functions G, w.h.p. over the draw of a sample S from D, there is an η-nasty-noise corruption S of S such that if A G is trained on S, even if all the internal nodes of the tree are γ-advantage hypotheses, the tree has to be grown to size 2 Ω(d) in order to achieve error ≤ ε.
A weaker lower bound of η ≥ Ω( √ γ) for constant ε follows from the work of Dachman-Soled et al. (2015). Theorem 1.2 improves this to the near-optimal η ≥ Ω(εγ). A key ingredient in our proof is the celebrated Kahn-Kalai-Linial theorem (Kahn et al., 1988) from discrete Fourier analysis. We contrast the dimension-independent bound, exp(O(1/γ 2 ε 2 )), on the size of tree in Theorem 1.1 with the 2 Ω(d) lower bound in Theorem 1.2.
Improving on the theoretical state of the art. Specializing Theorem 1.1 to the setting of product distributions over binary features, we further show the following: Theorem 1.3 (Learning monotone decision trees in the presence of nasty noise; see Theorem 5.4 for formal version).
For any product distribution over {±1} d , impurity-based decision tree algorithms learn size-s monotone decision trees in the presence of nasty noise in poly(d)
This problem of learning decision trees in the setting of product distributions has been intensively studied in learning theory (Hancock, 1993;Bshouty, 1993;Kushilevitz & Mansour, 1993;Blum et al., 1994;Jackson & Servedio, 2006;O'Donnell & Servedio, 2007;Gopalan et al., 2008;Lee, 2009;Kalai et al., 2009;Hazan et al., 2018;Chen & Moitra, 2019;Brutzkus et al., 2020;Blanc et al., 2020b;2021b). Many real-world learning scenarios are naturally monotone in nature, and relatedly, monotonicity is a commonly studied assumption in learning theory.
Prior to our work, the only algorithms provably resilient to nasty noise run in time d O(log s) (Linial et al., 1993;Kalai et al., 2008a;Blanc et al., 2021c), which is only poly(d) for constant s. These algorithms do not resemble the impurity-based algorithms used in practice. Theorem 1.3 therefore gives the first poly(d)-time algorithm for any s = ω d (1); our running time remains poly(d) for s as large as 2 O( √ log d) . For the weaker model of agnostic noise, recent work of (Blanc et al., 2020a) gives a poly(d)•s O(log s) time algorithm.
We discuss other related work in Appendix A.
Notation. We use boldface (e.g. x ∼ D) to denote random variables. We consider the binary classification setting where we have a distribution D X over an arbitrary domain X and a (randomised) classification function D Y =1|X : X → [0, 1]. Together, these define a distribution D over X × {0, 1}. The goal of a learning algorithm is to use i.i.d. samples (x, y) ∼ D to construct a hypothesis T : X → {0, 1} that achieves low error on D, where error is defined as:
(1)
We also define µ(D) := Pr D [y = 1], the bias of D towards the 1-label, and ε(D) := min{µ(D), 1 -µ(D)} to be the error of predicting the majority label on D.
Decision tree hypotheses. We consider binary decision trees T : X → {0, 1} whose internal nodes v are labeled by functions h v : X → {0, 1} from a class H of allowable splitting functions. The most standard class of splitting functions is the set of thresholds of a single feature, h(x) = 1[x i ≥ θ], though our guarantees apply to any arbitrary class H. Each instance x ∈ X follows a unique root-to-leaf path in T : at any internal node v, it follows either the left or right branch depending on the result of h v (x), until a leaf is reached. The set of leaves ∈ leaves(T ) therefore form a partition of X . We write w D ( ) to denote the probability that x ∼ D X reaches and we write D to denote D conditioned on x reaching . We write ∼ (T, D) to denote the draw of a random leaf where each leaf ∈ leaves(T ) is given weight w D ( ).
The prediction at a leaf is then taken to be the majority label of points that reach that leaf, i.e. 1[µ(D ) ≥foot_0 2 ]. The error of T on D is therefore given by the sum of the error at each leaf incurred by predicting the majority label, weighted by the probability of reaching that leaf:
We will need the notion of feature influences in the context of binary features:
X be a production distribution over {±1} d . For i ∈ [d], the influence of feature i on f , denoted as Inf i (f ) is given by the quantity 2 Pr x∼D X ,b∼D (i)
, where x i=b rerandomises the i-th bit of x with a random sample from D (i) X .
Essentially almost all decision tree learning algorithms used in practice, including the classic and popular ID3, C4.5, and CART, learn decision trees greedily in a top-down manner, using an impurity function as a measure of progress. (introduced and analyzed in (Kearns & Mansour, 1996)).
For this paper, we will focus on G(p) = 4p(1 -p) for simplicity, but our results hold generally for all impurity functions that have a second derivative bounded away from 0 (see Remark C.1 in appendix).
Impurity-based decision tree learning algorithms are parameterized by an impurity function G and a class H of allowable splitting functions. For a tree T , leaf , and label function h ∈ H, we denote T ,h to be the extension of T that replaces the leaf with an internal node that splits on h. At every step, the algorithm loops through all possible leaves and labelling functions h ∈ H, 1 looking for a potential split that will result in the largest reduction G(T ) -G(T ,h ) of the impurity function, and hence also (hopefully) the error of the new tree.
Definition 2.3 (Purity gain). Let h be a splitting function, be a leaf of T , and D be D conditioned on x reaching . Let 0 be the leaf of T ,h corresponding to h(x) = 0, 1 be the leaf corresponding to h(x) = 1, and D 0 and D 1 be their respective conditional distributions.
We define the local drop in G at this leaf, after splitting with h, as:
Kearns & Mansour (1996) were the first to analyze impuritybased decision tree learning algorithms from the perspective of boosting. Their simple but key insight was that the splitting functions at the internal nodes of the tree can be viewed as weak hypotheses, and the decision tree construction as a process of creating a strong learner by combining these weak hypotheses. We recall that standard weak learning assumption from the literature on boosting:
Definition 2.4 (Standard distribution-independent weak learning assumption). Let f : X → {0, 1} be a target function and H be a class of hypotheses from X to {0, 1}. For γ > 0, we say that H satisfies the distributionindependent γ-weak learning assumption w.r.t.
Definition 2.4 can be hard to satisfy because of the requirement that there exists a γ-advantage hypothesis for every distribution D X over X . Our analysis will only rely on a milder distribution-specific weak learning assumption that TOPDOWNDT H,G,D (t):
Given: Size bound t.
Output: Decision tree of size t approximating D, with internal nodes chosen from H.
1. Initialize T to be the empty tree.
2. While size(T ) < t:
(a) Let ( , h ) be set to arg max
4. Return T .
Figure 1: The decision tree boosting algorithm for hypothesis class H and impurity function G over distribution D.
For simplicity, we assume that ∆ D (h), w D ( ), and µ(D ) can be computed exactly. In practice, these quantities can be replaced with empirical estimates from a random sample of D (see Appendix D for details).
is significantly easier to satisfy. Looking ahead, the mildness of our weak learning assumption will be crucial for our proof of Theorem 1.3. We first need the notion of an induced distribution:
Definition 2.5 (Induced distributions). Let D be a distribution over X × {0, 1} and H be a class of hypotheses from X to {0, 1}. We say that D is a distribution induced by conditioning D on H if D can be expressed as
Remark 2.6. Note that all the conditional distributions, D , at the leaves of a decision tree are induced distributions of D conditioned on H. Moreover, if D is such that D X is a product distribution and if H is the class of hypotheses that threshold on a single feature (i.e. h(x) = 1[x i ≥ θ]), then D X remains a product distribution for every distribution D that is induced by conditioning D on H.
Definition 2.7 (Our distribution-specific weak learning assumption). Let D be a distribution over X × {0, 1} and H be a class of hypotheses from X to {0, 1}. For γ > 0, we say H satisfies the γ-weak learning assumption w.r.t D if, for any distribution D that is induced by conditioning D on H, there exists an h ∈ H that satisfies:
We call such an h a γ-advantage hypothesis with respect to D .
Remark 2.8. Our weak learning assumption in Definition 2.7 is a weaker assumption than the standard Definition 2.4. This is because Equation ( 2) is equivalent to having Pr (x,y)∼D bal [h(x) = y] ≤ 1/2 -γ, where D bal is the balanced version of D , so that the points in X are reweighted to make the probability of a positive or negative label equally likely. Since Definition 2.4 has to hold for all distributions over X , it also has to hold in particular for the marginal distribution of D bal over X . Therefore, Definition 2.4 implies Definition 2.7.
Adversarial noise can take on many strengths and forms, depending on both what kind of corruptions are allowed and when these corruptions can be made. We focus on the strongest model of noise called nasty noise (Bshouty et al., 2002). In this setting, we wish to learn a binary classifier on a distribution D over X × {0, 1}. However, instead of receiving a set of samples S ∼ D n , an adversary is allowed to replace any η-fraction of points in S with arbitrary points to get a corrupted sample S. The algorithm then receives the corrupted sample S.
This noise model captures many other weaker forms of noise. For example, if the adversary can only change the labels of the η corrupted fraction, we recover agnostic noise.
Similarly, if the adversary has to obliviously commit to a corruption strategy before seeing the sample S, this is equivalent to choosing a distribution D that is η-close to D in Total Variation (TV) distance, and drawing S from that. This is often called the distributional shift setting.
We can now state the formal version of Theorem 1.1, which states that impurity-based decision tree learning algorithms are boosting algorithms that are resilient to nasty noise.
We draw on a recent result by Blanc et al. (2022), which shows that learning in the presence of η-nasty-noise corruption is equivalent to learning in the presence of η distribution shift with respect to Total Variation distance (dist TV ), as long as the learner only interacts with its samples by computing expectations. For details on the formal relationship between Theorems 1.1 and 3.1, as well as the runtime analysis of TOPDOWNDT see Appendix D.
We now prove a few lemmas that will be useful for our proof of Theorem 3.1. We begin by quantifying how much the impurity function decreases when we split at this particular leaf with a splitting function h : X → {0, 1}. The following lemma lower bounds this decrease, ∆ D (h), in terms of the covariance between h(x) and y. We state the lemma generally for an arbitrary distribution E since we will be applying it to the distributions, D , at each leaf.
Lemma 3.2 (Local drop in G in terms of covariance). Let E be any distribution over X × {0, 1} and h : X → {0, 1} be a splitting function. Then:
Proof. This result follows almost directly from Kearns & Mansour (1996). See Appendix G for details.
Our weak learning assumption (Definition 2.7) provides lower bounds on the covariance between h(x) and y on the uncorrupted distribution D . We want to relate this this to the covariance on an adversarially corrupted distribution D that is η -close to D .
We will need the following useful facts relating the variance and covariance of bounded functions on two distributions that are close in TV distance. We consider an arbitrary domain V and, without loss of generality, functions from V to [0, 1]. We defer the proofs to Appendix B.
Lemma 3.3 (Moments and TV-distance). Let E, E be two distributions over a domain V with dist TV (E, E) ≤ η and let f, g : V → [0, 1] be functions. Then
(5)
We now use Lemma 3.3 with our weak learning assumption to prove the existence of an h at that has high covariance on the adversarially corrupted distribution at a given leaf:
Lemma 3.4 (Covariance on the corrupted distribution). Let D be a distribution over X × {0, 1} and H be a class of splitting functions from X to {0, 1} that satisfies the γ-weak learning assumption w.r.t D. For a decision tree T and leaf of T , let D be any distribution with dist TV (D , D ) ≤ η . Then there is an h ∈ H s.t.
We can now prove the theorem:
, by our assumption that η ≤ O(εγ).
γ + ε, we prove the existence of a leaf * ∈ T and splitting function h * ∈ H such that splitting * according to h * results in a substantial reduction in G D (T ). In more detail, we consider the expected reduction in G D (T ) if a random leaf ∼ (T, D) is split with the respective h from Lemma 3.4:
where we use the notation (x) + := max{0, x}.
All together, we have
(by assumption)
Rewriting the expectation, we get
If there are currently s leaves in T , there must exist a leaf such that
Since TOPDOWNDT greedily splits the leaf that results in the largest drop in G D (T ), it follows that the drop in G at timestep s is at least least 4γ 2 ε 2 /s. Therefore, after t steps, the total drop is at least:
Since the range of G D is [0, 1], we conclude that after t = exp(O(1/γ 2 ε 2 )) steps, we must be done i.e.
Theorem 3.1 says that TOPDOWNDT can grow a tree with error ≤ ε only when η ≤ O(εγ), where η is the amount of corruption and γ is the weak learning advantage. Here, we show that this bound is tight: If we allow η = Õ(εγ), then we can design distributions D on which TOPDOWNDT fails to achieve error ≤ ε.
We remark that for technical convenience, in both this section and Section 5, we switch to functions outputting {±1} rather than {0, 1}. The two formulations are equivalent.
Theorem 4.1 (Formal version of Theorem 1.2). For any ε, γ > 0 where γ 1/γ ≤ ε, d ∈ N, and η ≥ Ω(γε log(1/ε)).
There is a distribution D whose marginal over X := {±1} d is uniform, an η-nasty noise corruption D of D, and a hypothesis class, H, satisfying the γ-weak learning assumption w.r.t D, such that for all impurity function G, TOPDOWNDT H,G, D (t) fails to build an ε-error tree for D unless t ≥ 2 d-O(log(1/γ)/γ) .
Proof sketch. We will design a function f : {±1} d → {±1} that only depends on its first k features (meaning f (x) = g(x [1:k] ) for some function g : {±1} k → {±1}) for k d and set D to the distribution of (x, f (x)) where x is uniform from {±1} d . This function will be carefully designed so that there is an η-corruption D of D in which every hypothesis h ∈ H has a local drop in G of 0. As a result, TOPDOWNDT cannot identify the "important" k hypotheses and is likely to pick one of the d -k useless (because they are independent of the label) hypothesis. That continues until all d -k useless hypotheses have been used, which requires the tree to have depth d -k corresponding to a size of 2 d-k .
To formalize the above proof sketch, we will need to prove that the D we design satisfies the weak-learning hypothesis. To do so, we use the celebrated Kahn-Kalai-Linial inequality from the analysis of Boolean functions.
Fact 4.2 (KKL inequality, (Kahn et al., 1988)). For any function f : {±1} k → {±1} and D X the uniform distribution over {±1} k , there is a coordinate i ∈ [k] for which
The KKL inequality will allow us to prove that a broad class of distributions satisfy the weak-learning assumption.
Definition 4.3 (Monotone functions). We say that a Boolean function f : {±1} n → {±1} is monotone if for any x, y ∈ {±1} n where x i ≤ y i for all i ∈ [n], f (x) ≤ f (y).
Combining Fact 4.2 with Lemma 5.1 immediately gives the following.
Corollary 4.4. For any monotone function g :
We apply the above corollary to prove a class of distributions satisfying the weak-learning assumption. Before doing so, we'll need the notion of a restriction:
Restrictions. Given some domain X := {±1} d , a restriction of that domain is a defined by value for each coordinate,
where we define to be equal to both +1 and -1. The coordinates i where ρ i ∈ {±1} are said to be specified, and we define |ρ| to be the number of coordinates specified. The number of inputs consistent with a restriction ρ is 2 d-|ρ| , and there is a natural projection proj ρ from {±1} d-|ρ| to the subset of X consistent with ρ that uses the input to proj ρ for the unspecified coordinates and fills in the specified coordinates according to ρ. Proof. Let D be any induced distribution of D by H. Our goal is to show that Equation ( 2) is satisfied, or equivalently, that there is some i ∈
As H is the set of coordinate projections and D X is uniform over {±1} d , every induced distribution D X corresponds to the uniform distribution over all elements of X consistent with some restriction ρ. Given that restriction ρ, we can define the function
As f is a monotone function of the first k coordinates of its input, f ρ is a monotone function of the first (up to k) coordinates of its input. Hence, there is some k ≤ k and monotone
Then,
This means that H satisfies our weak learning assumption w.r.t. D.
To design the distribution D of Theorem 4.1, we'll use the following proposition.
Proposition 4.6. For any ε ∈ (0, 1/3] and d ≥ log 2 (1/ε), for some integer k ≤ d, there is a monotone function f : {±1} k → {±1} where, for x ∼ {±1} k chosen uniformly,
The proof of Proposition 4.6 is given in Appendix E.
Finally, we prove the main result of this section.
Proof of Theorem 4.1. Let
Note as we assume that γ 1/γ ≤ ε, we have that ≥ log 2 (1/ε). Therefore, by Proposition 4.6, we know for some k ≤ , there exists a monotone g : {±1} k → {±1} where for x ∼ {±1} k chosen uniformly,
and, where η is chosen as the unique solution of (1-η)v -η = 0 where v is as defined in Equation ( 9). Note that this solution satisfies
As D is a mixture with (1 -η) fraction coming from D, it is an η-nasty noise corruption of D. Furthermore, as the contribution of E is chosen to exactly cancel out the correlations of D, for all i ∈ [d],
This means that for any impurity function G, all hypotheses have a local drop in G of 0. Furthermore, all projections except for the first k are fully independent of one another and of the label. Therefore, if all internal nodes in the tree consists of projections for the last d -k coordinates, then all hypotheses at every leaf will still have impurity gain.
As a result, TOPDOWNDT will choose an arbitrary ( , h ) at each iteration. Unless t ≥ 2 d-k , these arbitrary decisions can lead to the complete tree of depth log(t) being built, where all internal nodes have a hypothesis for one of the d -k projection functions that are independent of y.
In that case, by Equation ( 8) for every leaf ,
Therefore, regardless of how TOPDOWNDT labels the leaves, the resulting tree will have error ≥ 2ε.
In this section we consider distributions D for which the marginal D X is an arbitrary product distribution D X = D
(1)
X over {±1} d (i.e. each bit is independent) and the deterministic target function D Y |X is monotone and representable by a size-s decision tree.
The following is a useful fact about the influence of features on monotone functions. See Appendix F for a proof. Lemma 5.1 (Influence = covariance for monotone functions).
X be an arbitrary product distribution over {±1} d . For a monotone function f :
The key technical ingredient in our proof of Theorem 1.3 is a theorem of O'Donnell, Saks, Schramm, and Servedio from discrete Fourier analysis (O'Donnell et al., 2005): Theorem 5.2 (OSSS inequality). Let f : {±1} d → {±1} be function that is representable by a size-s decision tree and D X be a product distribution over {±1} d . Then
where Inf i (f ) and Var[f ] are with respect to D X .
For the class of distributions described at the beginning of this section, Lemma 5.1 and Theorem 5.2 together imply that the weak learning assumption of Theorem 3.1 can be satisfied by the set H = {proj i : i ∈ [d]} of projection functions:
Lemma 5.3 (Projection functions satisfy weak learning assumption). Let D be a distribution for which the marginal D X is a product distribution over X = {±1} d and the target function f := D Y |X is monotone and can represented as a size-s decision tree. The set H = {proj i : i ∈ [d]} of projection functions satisfies the γ-weak learning assumption w.r.t. D with γ = 1/ log s.
Proof. We first note that there is an h ∈ H that is a γadvantage hypothesis with respect to D:
where we have used Lemma 5.1 for the equality and Theorem 5.2 for the inequality. Since H is the set of projection functions, every distribution D that is induced by conditioning
Similarly, since f is monotone and representable by a size-s decision tree, the same remains true for any restriction of f by the projection functions in H. Therefore, we can again apply Lemma 5.1 and Theorem 5.2 to infer the existence of a γ-advantage hypothesis h ∈ H with respect to D . runs in poly(d) • s O((log s)/ε 2 ) time and constructs a size-t decision tree hypothesis T satisfying error D [T ] ≤ ε.
We have given the first noise tolerance guarantees for the class of impurity-based decision tree learning algorithms that hold in a fully general setting. Theorem 3.1 shows that they are noise-tolerant boosting algorithms that combine γ-advantage weak hypotheses into a strong hypothesis with error ≤ ε, even in the presence nasty noise of rate as high as η ≤ O(εγ). Theorem 4.1 provides a near-matching lower bound ruling out, in a strong sense, any such guarantee for noise rates η ≥ Ω(εγ). Finally, instantiating Theorem 3.1 in the setting of product distributions over binary features-a setting that is particularly well studied in the theoretical literature-we show that these classic and widely-used algorithms achieve guarantees that are better than those known for any existing theoretical algorithms. Taken as a whole, our work helps place the popularity and empirical success of impurity-based decision tree learning algorithms on firm theoretical footing.
There are several immediate avenues for future research.
First, a natural next step is to establish similar formal noise tolerance guarantees for tree-based ensemble methods such as random forests and XGBoost. Second, the focus of our work has been on understanding properties of impuritybased decision tree learning algorithms exactly as they are, to provide theoretical justification for their practical effectiveness. It would nevertheless be interesting to consider possible modifications of these algorithms that are even more resilient to adversarial noise-for example, are there such modifications that evade our lower bounds?
Boosting by branching programs. Kearns and Mansour (Kearns & Mansour, 1996) (see also (Kearns, 1996;Dietterich et al., 1996)) were the first to propose the perspective of viewing impurity-based decision tree algorithms as boosting algorithms. Their analysis assumes the noiseless setting. Subsequently, departing from (Kearns & Mansour, 1996)'s motivation of analyzing practical decision tree algorithms, Mansour and McAllester (Mansour & McAllester, 2002) initiated a line of work on boosting by branching programs, a variant of decision trees where the underlying graph is a DAG rather than a tree. While (Mansour & McAllester, 2002) assumes the noiseless setting, the followup works (Kalai, 2004;Long & Servedio, 2005;Kalai & Servedio, 2005;Long & Servedio, 2009) handle various types of random (i.e. non-adversarial) label noise, and the work of (Kalai et al., 2008b) handles agnostic noise.
Our work differs from this line of work in two ways: first and foremost, our results apply to impurity-based decision tree algorithms such as ID3, CART, and C4.5-the overarching goal of our work is to analyze and establish noise tolerance properties of these algorithms that are widely used in practice-whereas branching programs are much less commonly used. Second, we handle the strongest noise model of nasty noise, whereas these results only allow for corruptions of labels and not features.
Theoretical work on decision tree learning. Decision trees are one of the most intensively studied concept classes in learning theory. The literature on this problem is rich and vast, spanning over three decades, and it continues to grow. However, in most of these works, the algorithms analyzed not resemble practical impurity-based decision tree algorithms. Indeed, most of them are improper algorithms, in the sense that their hypotheses are not themselves decision trees. Quoting Kearns and Mansour (Kearns & Mansour, 1996), "In summary, it seems fair to say that despite their other successes, the models of computational learning theory have not yet provided significant insight into the apparent empirical success of programs like C4.5 and CART."
Lemma B.1 (Expectation and TV-distance). Let E, E be two distributions over a domain V with dist TV (E, E) ≤ η and let
Proof. The result follows immediately from the following definition of total variation distance:
Lemma B.2 (Variance and TV-distance). Let E, E be two distributions over a domain V with dist TV (E, E) ≤ η and let
Proof. We can write
If dist TV (E, E) ≤ η, then it is easy to see that dist TV (E 2 , E 2 ) ≤ 2η, where E 2 indicates the product distribution of two independent draws from E, Moreover, since (f (x) -f (x )) 2 ≤ 1, we can apply Lemma B.1 to Equation ( 12) with E 2 and . Let E, E be two distributions over a domain V with dist TV (E, E) ≤ η and let f, g : V → [0, 1] be two functions. Then
Proof. We can write
, where E 2 indicates the product distribution of two independent draws from E, Moreover, since f, g : V → {0, 1}, we have
, so we can apply Lemma B.1 to Equation ( 13) with
Lemma B.4. For any finite set L, (possibly infinite) set X, and distributions D, D each over the product domain L × X,
where D is marginal distribution of for (x, ) ∼ D and D x| is the conditional distribution of x when ( , x) ∼ D conditioned upon = .
Intuitively, we will define a distribution D that "mixes" D and D: To sample ( , x) ∼ D , we first draw ∼ D and then x ∼ D x| . We'll be able to show that the l.h.s. of Equation ( 14) is equal to dist TV (D, D ). Proof of Lemma B.4. We compute,
We analyze each term of the above two terms separately. For the first,
Remark C.1 (Other impurity functions). Lemma 3.2 is the only part of the proof of Theorem 3.1 that depends on the particular impurity function G. That Lemma goes through for any impurity function that, for any constant κ, satisfies G (x) ≤ -κ for all x ∈ (0, 1), though the 16 in Equation ( 3) is replaced with 2κ. This is because (using the fact that The above holds with equality when G (x) = 4x(1 -x) for κ = 8. Therefore, the local drop in G will always be at least κ 8 as large as it is for G . The remainder of the proof of Theorem 3.1 goes through unmodified except for slight changes to the constants hidden by O(•).
In the pseudocode provided in Figure 1, we assume that we can exactly compute the drop in impurity and therefore can exactly compute expectations of the form µ(D ) = E x,y∼D [y]. If instead, those expectations are estimated using random samples (as in the statements of Theorems 1.1 and 1.3 in the introduction), the algorithm only can estimate them to within some tolerance ±τ . It is straightforward to carry out the proofs of Theorems 3.1 and 5.4 accounting for this ±τ error as long as τ ≤ O( γ 2 ε 2 t ). As the TOPDOWNDT only needs to compute at most O(t 2 |H|) expectations, standard concentration inequalities can be used to show that a sample of size Õ(1/τ 2 • t 2 • |H|) is sufficient to compute all expectations to accuracy τ with high probability. However, the situation with noise is slightly more nuanced, as the adversary gets to see the sample S ∼ D n before deciding on η-nasty-noise corruption Ŝ. This means the adversary can choose how to modify empirical estimates after seeing the sample S. Luckily, Theorem 5 of (Blanc et al., 2022) handles exactly this case. It says that as long as the sample has size Õ(1/τ 2 • t 2 • |H|), with high probability, all empirical estimates computed on the corrupted sample Ŝ will be within ±τ of the true expectations of some D that is η-close to D. Therefore, by proving that TOPDOWNDT succeeds on every D that is η-close to D, as we do in Theorem 3.1, we ensure that our algorithm succeeds even if an adversary gets to modify η-fraction of a sample after seeing it.
Runtime analysis. Before proving that TOPDOWNDT build low error trees, we will briefly prove that it is efficient. Let ζ be the time it takes to compute µ(D ) and Pr D [h(x) = 1] for some leaf of the tree. Typically, this will be proportional to the size of the data set. Then, as the number of leaves in each iteration will be at most t, the time required for an iteration of TOPDOWNDT is at most O(ζt • |H|). The algorithm runs for t iterations, so the total runtime is O(ζt 2 • |H|).
In the context of practical decision tree algorithms, the class of splitting functions H is usually finite and small. Standard implementations of these popular algorithms, such as in scikitlearn, do a brute force search over hypotheses.