A sequence of questions becomes a classifier
A decision tree routes an observation through a sequence of feature tests. At an internal node, the test selects a child; at a leaf, the tree returns a class prediction. A numerical test such as splits the feature space into regions. Several levels can describe interactions that a single test cannot express.
Training a tree requires more than drawing those questions. We need a rule for choosing a leaf's prediction, a score for candidate splits, and a way to stop or simplify a tree. These choices solve different problems. A split can improve a training score while offering no improvement on new observations; a greedy rule can also miss a useful interaction.
We use a finite training sample with binary labels . Observations are indexed, so repeated feature vectors are allowed and can even have different labels. Features used in this note are fully observed, and numerical values are finite real numbers. Every considered split has nonempty training children. Missing-value handling is a separate modeling choice.
The best constant prediction at a leaf
Proposition 3.2.1
(Majority prediction minimizes leaf training error)
Let a nonempty leaf receive label-1 and label-0 training observations. A constant prediction of 1 makes mistakes and a constant prediction of 0 makes mistakes. Under zero–one loss the smallest possible number of mistakes is therefore , attained by predicting a majority class. Ties are resolved by a fixed rule, such as predicting 0 when the counts tie.
Proof
(Count the mistakes of each constant)
A constant prediction is wrong exactly on the observations of the other class. Predicting 1 errs on the label-0 observations, and predicting 0 errs on the label-1 observations. With binary labels these are the only two constant predictions, so the minimum is , and a majority class attains it.
This proves a local optimum for a fixed leaf region. It does not prove that the region is well chosen or that its training majority will be the population majority. The empirical fraction is a useful summary, but it is not automatically a calibrated probability for future data.
Entropy measures empirical label uncertainty
Definition 3.2.2
(Binary entropy and split information gain)
For a node with , put and define
with by continuous extension. A pure node has entropy 0; a balanced node has entropy 1 bit.
If a candidate test partitions the node into nonempty children indexed by , let be the child size and its label-1 fraction. Its information gain is
The weights are necessary. If one training observation is chosen uniformly from this node, it reaches child with that probability. The sum is the average remaining label entropy after learning the test outcome. Giving a tiny child the same weight as a large one would score a different quantity and can change which split wins.
Proposition 3.2.3
(Information gain is nonnegative)
In the notation of the definition, with every child nonempty,
Moreover exactly when every child has the same label fraction as the parent, for all .
Proof
(Concavity of binary entropy)
Every observation of the node lies in exactly one child, so the parent fraction is the weighted average . For ,
Since is continuous on , it is strictly concave there. The weights are positive and sum to 1, so Jensen's inequality gives , that is, . Equality holds exactly when all are equal, and a common value must equal their weighted average . Because child entropies are nonnegative, also .
Proof X-ray
Where the partition and strict concavity enter
The key move is to write as a weighted average of the child fractions. That identity holds because the children partition the node: counts of label 1 add, and the sizes add to . If an observation were sent to two children, or to none, the weights would no longer sum to 1 and the identity would fail.
Concavity gives only . Strictness together with positive weights, which come from nonempty children, turns equality into a statement about the data: the split has zero gain only when it leaves every child's label fraction unchanged.
This is a statement about the observed sample distribution. It does not claim that population labels depend on the feature, or that an estimated positive gain will persist on new data.
A small pure child can mislead an unweighted score
Worked example 3.2.4
(Compare two tests on the same eight observations)
At the root, consider two binary features :
| Observation | Label | ||
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 0 | 0 | 1 |
| 3 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 |
| 6 | 0 | 1 | 0 |
| 7 | 0 | 1 | 0 |
| 8 | 0 | 1 | 0 |
The root has four labels of each class, so its entropy is 1. Testing isolates one pure label-1 observation and leaves a child of size seven, with three ones and four zeros. Testing gives two size-four children, with class counts and .
| Test | Correct weighted child entropy | Information gain |
|---|---|---|
Information gain chooses . Its majority leaves make two mistakes in eight observations. The split makes three mistakes: its large child predicts 0, misclassifying the three remaining ones. A constant root leaf makes four mistakes under either tie prediction.
If instead we averaged the two child entropies without size weights, would appear to have entropy , below 's . That incorrect rule would prefer , giving one observation as much influence as the other seven together.
Entropy and training misclassification are distinct criteria. A smaller entropy need not always imply fewer majority-vote mistakes for arbitrary candidate partitions. The example reports both scores; it does not identify them as interchangeable objectives.
Numerical splits should respect repeated values
For a numerical feature, use the test for the left child and for the right. Sort the node's observations by that feature and group equal values. If the distinct values are , then only nontrivial training partitions are possible. Each threshold satisfying
gives the same training partition. Taking is one exact convention. A midpoint is another, but these choices can predict differently for an unseen value between and . Store the actual threshold and use the same inequality at prediction time.
Equal feature values cannot be separated by this test. Placing a boundary between two equal observations in sorted order would create a fictitious partition that no threshold can reproduce.
Maintain prefix counts of each label while scanning the distinct-value groups. Moving a whole group from right to left updates both child counts; compute the weighted entropy only when both sides are nonempty.
BEST_THRESHOLD(observations):
sort by this feature; keep all equal values in one group
left0, left1 = 0, 0
right0, right1 = total counts of labels 0 and 1
bestGain = -INFINITY
bestThreshold = NONE
for each value group except the final group:
move the group's label counts from right to left
gain = parentEntropy - sizeWeightedChildEntropy
if gain > bestGain:
bestGain = gain
bestThreshold = this group's feature value
return the best threshold, or NONE if there is only one distinct value
Proposition 3.2.5
(The threshold scan visits every admissible partition once)
Let a node contain observations, and let a numerical feature take distinct values . The partitions with both sides nonempty are exactly in number: for , the left side consists of the observations with values . The scan evaluates each of them once, so with exact scores it returns a partition of maximum gain, and among exact ties the one with the smallest threshold.
Proof
(Thresholds and value groups correspond)
If or , one side is empty. If with , the left side is exactly the first value groups, so distinct give distinct partitions. The scan moves the groups one at a time, so after the th move its counts describe partition , and the gain is computed from them. A maximum over all is a maximum over all partitions. Replacing the best value only on strict improvement keeps the first maximizer in increasing order, which has the smallest threshold. Moving groups touches each observation once, so the count updates cost after sorting.
Because thresholds are scanned in increasing order and only strict improvements replace the best, this version breaks equal-gain ties by the smaller threshold. Other fixed tie rules are possible. The tie statement concerns exact mathematical scores; a numerical implementation must specify its precision and tie policy. Sorting costs at this node, followed by an count scan. For features sorted separately, the simple bound is for one node. Training the whole tree repeats work at later nodes, so this is not automatically the cost of the entire training procedure. Prediction through a tree of depth uses at most constant-time tests.
Concept lensGeometric
A tree as boxes in feature space
Geometrically, a tree built from tests cuts feature space by hyperplanes parallel to the coordinate axes. Each leaf is a box, a product of intervals (some possibly unbounded), and the tree predicts one constant on each box. The scan over one feature is then a search over the distinct positions of a single cutting plane between occupied values. The XOR tree below has four leaves, one for each of the four cells cut out by the two features.
Worked example 3.2.6
(A threshold scan with a repeated value)
Take values with labels . The node has two ones and three zeros, so its entropy is . There are four distinct values, hence three admissible partitions. The two observations with value 3 stay together.
| Threshold | Left labels | Right labels | Weighted child entropy | Gain |
|---|---|---|---|---|
The scan stores , the largest gain. Separating the two observations with value 3 would pair the value 3 on both sides of one test; no threshold can do that, so that partition is not among the three. Only gains are computed, not four.
Worked example 3.2.7
(Conflicting labels at one feature value)
Take observations . The root has two ones and one zero, with entropy . The only admissible partition is against . The left child has labels and entropy 1, and the right child is pure, so the gain is .
The left child cannot be split further, because its two observations have the same feature value. Under the tie rule that predicts 0, its leaf misclassifies the observation with label 1, so the tree makes one mistake in three. No tree that uses only can do better: it gives the same prediction to the two observations with , and their labels differ, so at least one of them is wrong. The remaining error is a property of the data, not of the training procedure.
Zero greedy gain can hide an interaction
Counterexample mode
XOR needs two levels even though every first gain is zero
Take all four binary feature pairs and labels
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The root is balanced. Splitting on either feature gives two balanced children, so the first information gain is zero. A rule that stops whenever the best gain is not positive leaves a root classifier with training error .
Yet testing first and then in both children gives four pure leaves and zero error. The first split makes useful structure available to a later split without improving the immediate entropy score. Greedy one-step selection is not a global search over all small trees.
Allowing zero-gain splits can help this example but does not remove the need for stopping rules. Depth limits, minimum child sizes, a lack of admissible tests and pure labels are possible reasons to stop. If repeated feature vectors have conflicting labels, no deterministic sequence of tests using only those features can separate those observations.
Training improvement is not a generalization proof
Suppose a binary feature and the population label are independent fair bits. Training rows and future observations are independent draws from this joint distribution. For , a sample has positive probability of having in every row, with both feature values represented. Splitting on then gives pure training leaves and zero training error. On a fresh observation, however, the rule predicting is wrong with probability , since independence gives .
Thus even the maximum possible training gain, namely this parent's entropy, which need not be 1 bit, does not certify predictive accuracy. Separate training, validation and test roles: fit using training data, select complexity using validation data, and reserve an untouched test set for the final evaluation. A training impurity score is not a substitute for those separate observations.
One way to simplify an already grown tree is to compare candidate subtrees using a size penalty. Let
where is the training misclassification fraction and is the number of leaves. Consider collapsing a subtree with leaves into one majority leaf on the same observations reaching that subtree. Its collapsed error is for that region. Let its old training mistakes be and its collapsed mistakes be . With total training size , the change in the objective is
The errors are normalized by the whole training size , not just the subtree's sample count. The rest of the tree is unchanged and cancels in the comparison. Collapse when this difference is nonpositive, if that is the chosen pruning objective, using a tie rule that favors the smaller tree. This is a precise comparison between these two candidates, not a claim that any local pruning schedule finds the globally best tree or that a particular guarantees low test error. Validation can help choose the complexity setting.
Common mistake
(Dividing subtree errors by the subtree sample size)
Suppose and a subtree reaching 40 observations has leaves, and , with . The correct change is , so with a tie rule favoring the smaller tree the subtree is collapsed. Dividing the error difference by 40 instead gives and wrongly keeps it. Every term of is on the scale of the whole training sample.
The leaf constant and the impurity are replaced together, while the weighted-decrease structure stays.
A path to generalization
What changes for more classes or numerical responses?
The leaf constant and the impurity are replaced together, while the weighted-decrease structure stays.
With classes the entropy becomes and a leaf predicts a most frequent class. With a real response and squared error, the best constant at a leaf is the mean of its responses, the matching impurity is their variance, and the weighted decrease in variance after a split is again nonnegative, because total variance splits into a within-child part and a between-child part. The partition argument is unchanged; only the leaf rule and the impurity are replaced.
Solved exercises
Quick check
(1. Weight the child entropies by observations)
A balanced node has ten observations. A candidate split puts one label-1 observation alone in a pure child; the other child has four ones and five zeros. Give the information gain. What incorrect gain would an unweighted average of the two child entropies report?
Solution · Solution 1
The correct remaining entropy is , so gain is approximately . The unweighted average is , giving the incorrect gain . Both use parent entropy 1; the discrepancy comes entirely from giving the size-one child an unjustified half of the weight.
Quick check
(2. Reject a split that separates equal feature values)
The sorted numerical feature values are , with labels . Under tests , list all distinct nonempty training partitions and their gains. Why is the apparent pure split after the second sorted row not admissible?
Solution · Solution 2
Use thresholds and , representing intervals and respectively. Each gives one pure singleton and a three-observation child with label fraction or . Both gains equal . A threshold cannot place one value 2 on the left and the other value 2 on the right. The apparent gain-1 split between those rows is an ordering artifact, not a valid feature test.
Quick check
(3. Find the minimum depth for the XOR sample)
Allow only tests of the individual binary features. Prove that no tree of depth one classifies the four XOR rows perfectly, and exhibit a depth-two tree that does. What would a strictly positive-gain stopping rule do?
Solution · Solution 3
A depth-one tree has a root test and constant child predictions. It can test only or . In either case each child contains one label of each class, so every constant leaf makes one mistake: two mistakes in four rows. At depth two, test at the root and in each child; label the four leaves with . This is exact, so minimum depth is two. The positive-gain stopping rule never takes the first zero-gain split and instead stops at depth zero with error .
Quick check
(4. Compute a pruning comparison without changing its denominator)
There are training observations. A five-leaf subtree makes 12 mistakes; collapsing it to one majority leaf makes 20. Compare the two candidates for and . Other parts of the tree stay fixed.
Solution · Solution 4
The objective change on collapse is . At it is , so collapse lowers the objective. At it is , so keeping the subtree is better under this comparison. The calculation uses the same whole-sample denominator 100 in both cases. It selects between two penalized training candidates and does not itself establish their relative error on new data.