Common Errors in Tree Risk Arguments

Why Tree-Risk Arguments Need Care

A tree can look convincing on the observations used to build it: its splits may sharply reduce empirical impurity, and its terminal nodes may appear homogeneous. Neither fact alone establishes that the tree will perform well on new observations. The difficulty is that tree construction often uses the same data both to choose a partition and to evaluate its fit. Some leaves may also contain no observations, and a large collection of candidate partitions gives the selection procedure many chances to find an apparently favorable split by chance.

A reliable risk argument distinguishes the fitted tree’s training performance from its risk on a fresh observation, states how the partition was chosen, and accounts for the range of partitions searched. The following notation makes these distinctions explicit.

Definition: Let \(Z=(X,Y)\) be a random observation with distribution \(P\), and let \(Z_1,\ldots,Z_n\) be independent observations from \(P\). For a predictor \(f\) and loss function \(L\), its population risk is \(R(f)=E[L(Y,f(X))]\), when the expectation exists. Its empirical risk is \(R_n(f)=n^{-1}\sum_{i=1}^n L(Y_i,f(X_i))\). If a fitting procedure uses the sample \(D=(Z_1,\ldots,Z_n)\) to produce \(f_D\), then \(f_D\) is random before observing \(D\). After conditioning on the observed data, its population risk \(R(f_D)\) is the risk of that particular fitted predictor on a fresh draw from \(P\).

For a tree, a predictor is constant or otherwise specified within each terminal region of a partition. A partition selected using \(D\) makes \(f_D\) data-dependent, even if the rule used to fit leaf predictions is simple. A risk calculation that treats the selected partition as if it had been fixed in advance needs an additional justification.

Worked Example: A Selected Predictor Has Zero Training Error but Positive Risk

Worked Example: Selection Among Two Trees

Let \(Y\sim\operatorname{Bernoulli}(1/2)\), and consider two constant classification trees, \(f_0(x)=0\) and \(f_1(x)=1\), under zero-one loss \(L(y,a)=\mathbf{1}\{y\ne a\}\). Take \(n=1\), and choose whichever tree classifies the one observed label correctly.

For either fixed tree, the population risk is \(R(f_0)=P(Y=1)=1/2\) and \(R(f_1)=P(Y=0)=1/2\).

If the observed label is \(Y_1=0\), the procedure selects \(f_0\); if \(Y_1=1\), it selects \(f_1\). In both cases, the selected tree has empirical risk \(R_1(f_D)=\mathbf{1}\{Y_1\ne f_D(X_1)\}=0\).

But the selected tree is still a constant predictor, and a new independent label is 0 or 1 with equal probability. Thus, for either possible observed data set, \(R(f_D)=1/2\). The training risk is zero while the population risk is one-half. The issue is not a mistake in calculating either risk: choosing a tree after seeing the label makes its training performance optimistic.

This example also identifies a common faulty step: “The fitted tree has low empirical risk, so its population risk must be low.” That conclusion does not follow just from the empirical calculation. A comparison with a fixed, prespecified tree and a comparison with a tree chosen after searching candidate trees are different claims. Sample splitting can separate construction from evaluation; alternatively, a bound can control deviations uniformly over the candidate class. In either case, the selection mechanism must be addressed.

Empty Leaves Are Not Harmless by Definition

For a region \(A\) in a tree partition, its sample count is \(N_A=\sum_{i=1}^n\mathbf{1}\{X_i\in A\}\). If \(N_A=0\), an empirical leaf mean or empirical class proportion calculated from observations in \(A\) is undefined: its denominator is zero. A tree implementation may assign a default value, inherit a parent prediction, or use some other convention. Whatever the convention, the data in that empty leaf do not determine its prediction.

The absence of a training observation in a region also does not imply that the region has zero probability under the population distribution. A future observation can fall there, in which case the chosen leaf prediction contributes to population risk.

Worked Example: An Empty Leaf Can Hide Population Error

Suppose \(X\in\{0,1\}\), with \(P(X=1)=0.2\) and \(P(X=0)=0.8\), and the true label is always \(Y=0\). Consider a tree split that makes \(\{X=0\}\) and \(\{X=1\}\) separate leaves. In a sample of size \(n=3\), the event that all observations have \(X_i=0\) has probability \(P(X_1=X_2=X_3=0)=(0.8)^3=0.512\).

On this event the \(X=1\) leaf is empty. Suppose its stored class prediction is 1, while the \(X=0\) leaf predicts 0. The empirical classification error is \(0/3=0\), because every observed feature value is 0 and is classified correctly.

For a fresh observation, the prediction is wrong exactly when \(X=1\). Therefore the population risk is \(R(f_D)=P(X=1)=0.2\), despite the zero training error. If the empty leaf instead inherited prediction 0, this particular tree would have population risk 0. The data in the empty leaf justify neither convention; the risk depends on how the leaf is handled and on the probability mass of its region.

A further mistake is to silently apply a formula for a leaf estimate in every leaf. For example, the empirical mean \(\sum_{i:X_i\in A}Y_i/N_A\) is defined only when \(N_A>0\). A valid argument must either ensure nonempty leaves, specify what happens when a leaf is empty, or treat the event of an empty leaf explicitly. A positive population probability \(P(X\in A)>0\) does not ensure that the realized sample count is positive.

Training Impurity Decrease Is Not a Population Improvement

Impurity decrease is a description of the observed sample unless a separate argument connects it to the distribution of future observations. A split can make training leaves purer by separating a chance arrangement of labels. The next example uses a fixed split, so the issue does not depend on having searched over many possible split locations.

Worked Example: A Split Improves Training Error but Not Risk

Let \(X\) and \(Y\) be independent Bernoulli random variables with success probability \(1/2\). Use the fixed split on \(X\), making one leaf for \(X=0\) and one for \(X=1\). Consider a sample of size 2 in which the two feature values differ and the two labels differ. This event has probability \(P(X_1\ne X_2)P(Y_1\ne Y_2)=(1/2)(1/2)=1/4\), because the feature and label samples are independent.

On this event, each child leaf contains one observation and hence is pure in the sample. The split tree predicts the observed label in each leaf, so its empirical zero-one risk is 0. At the root, the two observed labels are tied. If the tie is resolved by predicting 0, the root tree misclassifies one of the two observations and has empirical risk \(1/2\). The empirical error decreases by \(1/2\); the root Gini impurity is \(1/2\), whereas each child’s empirical Gini impurity is 0.

In the population, \(Y\) is independent of \(X\). For either possible value of \(X\), either class prediction has error probability \(1/2\). Consequently, the split tree’s population risk is \(1/2\), as is the population risk of the root predictor that always predicts 0. The observed impurity decrease is real as a sample calculation, but it does not establish a population improvement.

It would also be incorrect to infer that every empirical impurity decrease is spurious. A decrease can reflect a genuine signal. The correction is narrower: state the empirical comparison as an empirical comparison, and use an appropriate risk argument before claiming a population benefit. In particular, the fact that a split was fixed in this example avoids one selection issue but does not make a small sample’s impurity decrease conclusive.

Partition Complexity Must Appear Somewhere

If a procedure searches many candidate trees, it can select a favorable empirical fit even when none has especially low population risk. The following finite-class result shows precisely how the number of candidates enters a basic risk guarantee. It is not a tree-specific approximation theorem; it is a transparent bound for a finite collection of predictors.

Theorem: Let \(\mathcal{F}\) be a fixed, nonempty finite collection of \(M\) predictors. Suppose \(Z_1,\ldots,Z_n\) are independent and identically distributed, and for every \(f\in\mathcal{F}\), the loss \(L(Y,f(X))\) lies in \([0,1]\) almost surely. Let \(\hat f\) minimize \(R_n(f)\) over \(\mathcal{F}\), and let \(f^\star\) minimize \(R(f)\) over \(\mathcal{F}\). For any \(0<\delta<1\), with probability at least \(1-\delta\), \(R(\hat f)\le R(f^\star)+2\sqrt{\log(2M/\delta)/(2n)}\).

The assumptions matter. The collection must be fixed independently of the sample for this finite-class argument, the losses must be bounded as stated, and an empirical minimizer must be selected from the collection. In a tree application, \(M\) can represent a finite set of candidate fitted predictors, including the partitions and leaf predictions under consideration. A count of possible partitions alone is not automatically a count of predictors if the leaf fitting procedure adds further choices.

Control each fixed predictor.
For fixed \(f\), the losses on the independent observations are independent, identically distributed variables in \([0,1]\), with mean \(R(f)\). Hoeffding’s inequality gives \(P(|R_n(f)-R(f)|>\varepsilon)\le 2\exp(-2n\varepsilon^2)\).

Control the whole finite class.
By the union bound, \(P(\max_{f\in\mathcal{F}}|R_n(f)-R(f)|>\varepsilon)\le 2M\exp(-2n\varepsilon^2)\). Choose \(\varepsilon=\sqrt{\log(2M/\delta)/(2n)}\). The right-hand side is \(\delta\), so with probability at least \(1-\delta\), every \(f\in\mathcal{F}\) has \(|R_n(f)-R(f)|\le\varepsilon\).

Compare the empirical minimizer with the population minimizer.
On that event, \(R(\hat f)\le R_n(\hat f)+\varepsilon\le R_n(f^\star)+\varepsilon\le R(f^\star)+2\varepsilon\). The middle inequality holds because \(\hat f\) minimizes empirical risk over the same collection. Substituting the chosen \(\varepsilon\) proves the bound.

The factor \(\log M\) is the cost of controlling all candidates at once; without a complexity term, the bound would claim the same guarantee no matter how many alternatives were searched. In a richer or infinite class, a finite-cardinality bound may not apply directly, and an appropriate complexity measure or other argument is needed. Merely naming a measure is not a proof that a particular adaptive tree procedure satisfies a risk guarantee.

Worked Example: How Candidate Count Changes the Bound

Worked Example: Comparing Two Search Sizes

Suppose the bounded-loss conditions of the theorem hold, \(n=100\), and \(\delta=0.05\). If the candidate class contains \(M=10\) predictors, the deviation term in the oracle bound is \(2\sqrt{\log(2M/\delta)/(2n)}=2\sqrt{\log(400)/200}\). Since \(\log(400)\approx5.9915\), this is \(2\sqrt{5.9915/200}=2\sqrt{0.0299575}\approx2(0.1731)=0.3462\).

If instead \(M=1000\), the term is \(2\sqrt{\log(40000)/200}\). Using \(\log(40000)\approx10.5966\), it equals \(2\sqrt{10.5966/200}=2\sqrt{0.052983}\approx2(0.2302)=0.4604\).

Thus, with these sample size and confidence choices, the stated guarantee’s excess-risk allowance is about 0.346 for 10 candidates and about 0.460 for 1000. These are bounds, not estimates of the actual excess risk. The calculation illustrates why a tree-risk argument that reports empirical performance but says nothing about the candidate class has left out a relevant part of the justification.

A Practical Audit for Tree-Risk Claims

When reading or writing a tree-risk argument, check what is random, what was selected, and what the claimed risk averages over. The population risk of a fitted tree is evaluated on a fresh draw, whereas the empirical risk uses the observations that may have determined the splits and leaf predictions. If those same observations drive both construction and evaluation, fixed-tree concentration applied after selection is not justified merely by conditioning on the selected tree.

A useful correction is to make the logic explicit: either evaluate on data independent of tree construction under the required conditions, or establish a simultaneous guarantee over a class that includes the possible selected trees. Then check leaf occupancy and the scope of the candidate class. For each leaf, ask whether its estimate exists when the count is zero and what prediction is used otherwise. For the search, ask what collection or complexity is actually controlled. Finally, keep empirical and population statements separate: a training impurity decrease is a sample fact, while a population improvement needs its own argument.

Selection: Was the partition fixed in advance, or chosen using the same data used to report performance?
Empty cells: Is every leaf estimate defined, including when its sample count is zero?
Risk target: Does the calculation concern training impurity, empirical prediction error, or risk on a fresh observation?
Complexity: What set of candidate partitions or predictors is covered by the guarantee?
Conclusion: Does the stated result support the population claim, or only describe the observed sample?

Key takeaway: Tree risk is not established by a low training impurity alone. A sound argument accounts for data-dependent selection, specifies how empty leaves are handled, distinguishes sample improvement from population improvement, and controls the complexity of the search.

Check Your Understanding

Use the distinctions and calculations in this tutorial to assess each claim.

Why can applying a fixed-tree risk argument after choosing a tree on the same data fail to justify the selected tree’s population risk?
A terminal region has sample count zero. Which part of an empirical leaf-mean formula is undefined, and why can the region still affect population risk?
In the worked split example, what was the empirical classification-error decrease, and what was the population-risk difference?
In the finite-class theorem, where does the factor \(M\) enter the proof, and what does it represent?
What additional information is needed before a training impurity decrease can support a claim of improved population performance?