Introduction
The -nearest-neighbor classifier predicts from labels near a query point, and naive Bayes predicts from a factorized probability model. A classification tree works differently. It recursively partitions the feature space into axis-aligned regions and predicts one label in each region. The partition is learned greedily: at each node the algorithm chooses the single split that most reduces an impurity measure computed on the training labels in that node.
This note treats binary labels and the Gini impurity. We define the criterion, prove an exact formula for the reduction it achieves, give a fully deterministic fitting rule, and compute a complete tree by hand. We then separate what this reduction proves from what it does not. It is a statement about training labels, not about test error.
Nodes and Gini impurity
Definition 5.6.1
(Node, label fraction and Gini impurity)
A node is a finite multiset of training pairs with elements. If of its labels equal , its label fraction is , and its Gini impurity is
The value is an empirical fraction. It describes this finite collection of labels and nothing more. The definition has a concrete probabilistic meaning. Draw two labels independently with replacement from the node's empirical label distribution, so that each draw equals with probability . They disagree when one is and the other is :
The words "with replacement" matter. For , sampling without replacement from a node of size would give , which generally differs from the with-replacement quantity.
Two common misreadings should be ruled out.
Common mistake
(Reading Gini impurity as the training error rate)
If a node predicts its majority label, it misclassifies a fraction of its training points, and this is not . For we have , and by symmetry for every . Equality holds only when . At , for example, while the error rate is .
Common mistake
(Reading a leaf fraction as a calibrated probability)
A leaf containing two training points, both labeled , has . That does not mean a new point landing in that leaf is labeled with probability . Calibration is a property of predictions on new data and must be checked on held-out data.
is symmetric, . It vanishes exactly on pure nodes () and is maximized at , where .
Splits and the gain identity
Definition 5.6.2
(Split and Gini gain)
A split partitions a parent node into two nonempty children and , with sizes . Write
The Gini gain of the split is the parent impurity minus the size-weighted child impurity:
Counting ones gives . Dividing by yields
Theorem 5.6.3
(Gini gain identity)
For any split of a node into nonempty children,
Consequently , and if and only if .
Proof
(Expansion and total variance)
By expansion. Write and . Since and ,
Hence
Expanding and using and ,
By conditional variance. Pick one training point uniformly from the parent. Let be its label and let record its child. Then is Bernoulli with mean , so . Likewise and . The law of total variance gives
Therefore . The variable equals with probability and with probability , and a two-point variable of this kind has variance .
The equality condition follows because whenever both children are nonempty.
Proof X-ray
What the gain identity rests on
Both arguments use exactly one link between parent and children: the counting identity , which says the parent fraction is the size-weighted average of the child fractions. Everything else is algebra on the single function .
The key move is that is a quadratic. Its linear part cancels in because is the weighted average, and only the quadratic part survives, as , a weighted variance of the two child fractions. Strict concavity of is what makes this gap positive as soon as .
Nonemptiness of both children enters twice: it makes and defined, and it gives , which is the whole content of the "only if" direction. The argument would not survive with the misclassification rate in place of : that function is concave but linear on each side of , so its gap is zero whenever and lie on the same side of . The first counterexample below shows this happening.
The identity says the gain is large when the children have very different fractions of ones and are not too unbalanced in size. It is computed entirely from the finite training sample. It is an empirical reduction in impurity.
Concept lensAlgorithmic
A Gini split is a least-squares split
Treat the labels as numbers and fit each child by its mean. The child's squared error is then , and likewise for . Hence the weighted child impurity equals times the total squared error of the two-mean fit, and the split with the largest Gini gain is exactly the split a regression tree with squared-error loss would choose on the labels. The leaf fraction is that least-squares fit.
A population analogue would replace empirical fractions by unknown conditional probabilities such as . One could also use population conditional entropy, which is a different criterion. The training gain only estimates such quantities, and the estimate becomes noisy as nodes shrink. So never guarantees lower test error.
A deterministic fitting rule
To make the algorithm reproducible, we fix every choice in advance. Features are numerical and indexed . Node depth counts splits from the root, so the root has depth .
- Candidate thresholds. At a node, for each feature , take the distinct values of among that node's training points in increasing order. The candidate thresholds are the midpoints of adjacent distinct values. A threshold sends to and to . Because lies strictly between two observed values, neither child is empty.
- Choice. Choose the candidate with the largest positive gain. Break ties first by smallest feature index, then by smallest threshold.
- Stopping. Make the node a leaf if it is pure, if no candidate has positive gain, or if its depth equals a depth limit fixed before fitting.
- Leaf prediction. Predict the majority label. If , predict .
Cost. Sorting each feature at a node of size costs . After sorting, a single left-to-right scan that maintains the cumulative count of ones in the left child evaluates every threshold of that feature in each, for total. Nodes at a fixed depth hold disjoint subsets of the data, so re-sorting at each node costs at most per level. Actual totals depend on node sizes and on implementation choices such as presorting. Categorical features need separate split rules and are not analyzed here.
Extrapolation. For a query outside the training range of a feature, the prediction is simply whatever the threshold rule assigns. It belongs to the leftmost or rightmost region along that feature. This is a consequence of the rule, not evidence that the label pattern continues beyond the data.
Worked example 5.6.4
(A tie between features changes predictions off the sample)
Take four points in : , , , . The root has and .
Along feature the labels in increasing order are . The thresholds give and gains , then , then by symmetry. Along feature the order is with labels , and the same three gains appear.
The maximum is attained by and by . The tie rule takes the smaller feature index, so the fitted tree is , , with two pure leaves and zero training error.
The rejected split forms the same training partition , giving the tree , , also with zero training error. At the query the chosen tree predicts and the rejected one predicts . The training labels cannot decide between them; the tie convention is part of the fitted model.
Worked example 5.6.5
(Repeated feature values leave an impure leaf)
Take with labels . The parent has and . There are two distinct values, so the only candidate is .
The left child holds both points at , with labels , so and . The right child is the single point at , so . Directly, ; by the identity, . The gain is positive, so the root splits.
The left child has a single distinct value of and hence no candidate threshold. It becomes a leaf with and predicts by the tie convention. The training error is . No threshold tree can do better here, because two points with the same feature value and different labels always fall in the same leaf. This is the boundary case of the purity result proved below, whose hypothesis of distinct values fails here.
A complete worked tree
Worked example 5.6.6
(Fitting a one-dimensional tree by hand)
Take with labels and no binding depth limit. The parent has and , so and .
Root. The candidate thresholds are . Each row below can be checked against the identity .
| left labels | weighted child | |||||
|---|---|---|---|---|---|---|
The maximum gain is attained at and at . The tie rule selects the smaller threshold, . The left child is pure with label and becomes a leaf.
Right child. The right child has points with labels . Here and . Its own candidate thresholds are .
- : the left child is , which is pure. The right child is with , weighted by to give . The gain is .
- : the left child is with , weighted by to give . The right child is pure. The gain is .
- : the left child is with and , weighted by to give . The right child is pure. The gain is .
The rule chooses . The right grandchild is pure with label . The left grandchild has labels . Its only threshold is , which yields two pure leaves with gain .
Fitted regions.
The deepest leaves sit at depth , so any depth limit reproduces this tree. Training error is zero.
Zero training error here is not a calibrated probability. Each of the regions around and rests on a single observation.
Counterexamples and limits
Counterexample mode
Gini decreases while classification error does not
Split a parent of size into two children of size . The left child has one label equal to , so . The right child has two, so . The parent has and . The children have and , with weighted average . The gain is .
Every node here predicts . The parent makes errors, and the children make errors. Training misclassification stays at . Gini impurity is a smooth surrogate that rewards moving the fractions and apart even when no prediction changes.
This counterexample is about the criterion. The next one is about the stopping rule, which halts as soon as no single split has positive gain.
Counterexample mode
Zero-gain stopping misses an interaction
Consider four equally weighted points: , , , . Splitting on either feature at gives children with , so the gain is . The fitting rule stops at the root. Under the tie convention the root predicts , which gives training error .
A depth- tree that splits on the first feature and then on the second in each child fits all four points exactly. The failure belongs to greedy positive-gain stopping. It does not show that trees cannot represent the pattern.
Training purity can also be achieved by memorizing idiosyncrasies of the sample. The next result makes this precise under an explicit model.
Theorem 5.6.7
(Memorization does not create signal)
Suppose the training data and a test pair satisfy the following: is a fair Bernoulli variable, and is independent of the whole tuple , where contains the predictor's internal randomness. Let be any predictor fitted from using . Then
Proof
(Conditioning argument)
Condition on , on , and on the predictor's internal randomness. The prediction is then a fixed label . Because is fair and independent of everything conditioned on, . Averaging over and the internal randomness preserves the value .
The fitting rule of this note can indeed memorize, as the next result shows.
Proposition 5.6.8
(Distinct values force pure leaves)
Suppose some feature takes pairwise distinct values on the training points and the depth limit satisfies . Then the deterministic fitting rule produces a tree whose leaves are all pure, so its training error is zero.
Proof
(Isolating the smallest value)
Let a node of size be impure, with ones, . The candidate on feature that isolates the point with the smallest value of has . If that point has label , then and . If it has label , then and . Either way , so this candidate has positive gain by the gain identity, and the node is split unless its depth equals .
Every split produces two nonempty children, so by induction a node at depth holds at most points. An impure node holds at least two points, so its depth is at most ; the depth limit never stops an impure node. The children of any split again carry distinct values of , so the argument repeats. Node sizes strictly decrease along every path, so fitting terminates, and every leaf is pure. A pure leaf predicts its own label, so no training point is misclassified.
If the training labels are also independent fair coins, the independent test error of this zero-error tree is still by the memorization result. The hypotheses are modeling assumptions. They are not claims about any particular collected dataset.
Validation discipline
Any preprocessing that learns from data must be fitted inside each training fold only. This includes imputation values and scaling parameters, and it includes the threshold search itself.
Strictly increasing transformations of a single feature do not change which training partitions a tree can form. Imputation, however, can change them. Choices of , minimum leaf sizes, or pruning level are model selection and require validation data. The final test set must stay untouched until all such choices are fixed. Split-based feature importances describe how the fitted tree used its training data. They carry no causal meaning.
Exercises
Exercise 5.6.9
(For the four XOR points above, compute the root gain of each single-feature split. Explain why the fitting rule stops, and exhibit a depth- tree with zero training error.)
Foundation
Solution(3)
- 1
Compute the split on feature
At , has labels and has labels . Thus and .
- 2
Apply the stopping rule
No candidate has positive gain, so the root becomes a leaf predicting .
Because: Feature is symmetric, so its only split also has gain .
- 3
Exhibit a zero-error tree
Split first on and then on in both children. The four leaves hold one point each and are pure. The positive-gain rule cannot see that a zero-gain first split enables perfect later splits.
Exercise 5.6.10
(A parent of size splits into children of size with and . Compute two ways and compare training errors.)
Foundation
Solution(3)
- 1
Compute directly
, , , so .
- 2
Compute by the identity
.
- 3
Compare training errors
All three nodes predict . The parent errs on points and the children on , so the error rate is before and after the split.
Exercise 5.6.11
(For at , give the counts for threshold and verify the gain. Then swap all labels and discuss what changes.)
Core
Solution(4)
- 1
Record the counts
The parent has and . The left child has and . The right child has and .
- 2
Verify the gain
, , , and .
- 3
Swap the labels
Key step
Every gain is unchanged, and so is the sequence of chosen splits. Leaf predictions in tied leaves are a different matter.
Because: and is unchanged when both fractions are replaced by their complements.
- 4
Examine a tied leaf
With , the node is a leaf with labels and predicts . After swapping, its labels are and it still predicts . In terms of the original labels, that prediction now corresponds to class . The fixed tie convention is therefore not symmetric under relabeling.
Exercise 5.6.12
(A dataset contains several rows per person, and a random row split places the same person in both training and validation. Explain the problem and give a correct protocol.)
Synthesis
Solution(3)
- 1
Diagnose the leakage
A deep tree can isolate person-specific feature combinations. Validation rows from the same person then land in leaves fitted on that person's own training rows. The validation score can reflect recall of familiar individuals rather than performance on new ones, and can be optimistically biased for the latter deployment target.
- 2
Split by group and fit inside folds
Key step
Use group-aware splitting, so that every row of a person falls in a single fold. Within each training fold, fit imputation, any scaling, and the threshold search. Then evaluate on the held-out groups. Select or the pruning level from these validation results, and only afterwards evaluate once on an untouched final test set of unseen people.
- 3
State what the protocol estimates
This protocol estimates performance on new people only to the extent that people can be treated as independent draws from a common population. That is an assumption about how the data were collected, not something the split proves.