A decision tree predicts by asking a sequence of yes-or-no questions about the features, each question comparing one feature with a threshold. It is the standard example of a model that is nonlinear, easy to read and cheap to evaluate, and it is the building block of ensemble methods. The trees here are the CART type: binary, axis-aligned, grown greedily. This unit complements the stochastic-gradient and linear-classifier units, where the fitted function came from continuous optimization. A tree is instead built by a combinatorial search, and its main risk is not a poor optimizer but over-fitting, which is controlled by pruning.
Trees, impurity and the split rule
Definition 31.1.1
(Axis-aligned binary tree and its predictions)
A tree partitions the feature space into regions, one for each leaf. An internal node tests a rule for a feature index and a threshold : observations satisfying it go to the left child and the others to the right. A leaf with training observations predicts the majority class of for classification, with a fixed tie rule, and the mean for regression.
Definition 31.1.2
(Node impurity and the gain of a split)
For a node with training points and class proportions , the Gini impurity is and the entropy is with . A split sends points left and right, both nonempty, and its gain is
For two classes with proportion of class one, . The tree-growing procedure picks, at each node, the feature and threshold of largest gain, considering only thresholds between distinct consecutive sorted feature values, and recurses until a stopping rule applies, for instance a pure node or a minimum node size.
Concept lensCombinatorial
Gini impurity as a disagreement probability
Draw two points from the node independently, with replacement. They have the same class with probability , so is the probability that they disagree. For class counts among points, ordered pairs contain agreeing pairs and disagreeing ones, so .
Theorem 31.1.3
(A split never increases impurity)
The impurity function is concave on the probability simplex. Consequently, for every split, , with equality if and only if the left and right class proportions are equal to the parent's.
Proof
(Concavity of the Gini impurity)
The function is convex, being a sum of squares of linear functions, so is concave. The parent proportion vector is the convex combination of the child vectors. Jensen's inequality gives , which is . The square is strictly convex, so equality holds exactly when , and then both equal .
The case of equality matters: a split can have gain zero while a deeper split would help.
Counterexample mode
Stopping at zero gain misses the exclusive-or pattern
Consider the claim that if no split at the root has positive gain, further splitting cannot help. Take the four points with labels . The root has class proportions , so . The split sends the labels left and right; both children have , so . The split gives the same value. A rule that stops when no gain is positive therefore returns a single leaf, with training error . Yet splitting first on and then each child on gives four pure leaves and training error . Zero gain at one level says only that no single question helps immediately. The repair is to stop on other criteria, such as a pure node or a minimum node size, and to let pruning control the size of the tree.
Regression trees
For a numerical response, the impurity of a node is its sum of squared errors about the node mean, .
Theorem 31.1.4
(The mean is optimal, and the split gain has a closed form)
For any real , , so the leaf value minimizing squared error is the mean. If a split divides into nonempty parts and , with sizes and , then
Proof
(Variance decomposition of a split)
Writing and noting gives the first identity. Apply it to with and to with and add: . Since , we have and . The last two terms add to .
Proof X-ray
Why both parts are re-centered at the parent mean
The one non-obvious move is to apply the one-set identity to and to with the same center , instead of comparing with directly. The identity holds for every , and its cross term vanishes because deviations from a set's own mean sum to zero. The common center turns into plus two between-group terms, so the gain is exactly the between-group sum of squares. The relation is the only place where the parent mean is used as a weighted average; it makes both deviations multiples of the same difference and produces the factor . Nonemptiness of and is needed to define their means; if one part were empty the gain would be , consistent with . Nothing in the proof uses that the split is axis-aligned or how it was chosen, so it holds for every division of into two parts.
The factor shows that, for a given difference of means, a balanced split earns more gain than one that peels off a single point.
Cost-complexity pruning
A fully grown tree can fit the training data exactly and generalize poorly. Cost-complexity pruning penalizes the number of leaves. For a tree with leaf set and training error (misclassification fraction, or mean squared error), and a penalty per leaf, define
For an internal node , write for the error if the subtree below were collapsed into a single leaf, and for its number of leaves.
Theorem 31.1.5
(The threshold at which a collapse pays off)
For a subtree with , collapsing it into one leaf strictly lowers if and only if , where
The proof is one line: collapsing changes by , which is negative exactly when . Weakest-link pruning repeatedly collapses the node with the smallest , recomputing after each collapse, and produces a nested sequence of trees. The value of , equivalently the tree in the sequence, is then chosen on held-out data or by cross-validation, not on the training error.
Worked examples
Worked example 31.1.6
(Gini splits on a one-dimensional sample)
Take with labels . The parent has three ones, so . The candidate thresholds are . The threshold gives a pure left child of four zeros and a right child with and . The gain is . The threshold gives a left child with one one among six, , and a pure right child, so . The other thresholds are lower: for . So the root splits at .
Misclassification count cannot separate the two best candidates: both leave exactly one error. The Gini gain prefers the split at , because its pure child is larger (four points rather than two), which leaves less weighted impurity. The right child , on , has and splits best at into and , with gain ; the thresholds and each give only .
Worked example 31.1.7
(A regression split and a pruning sequence)
Take and . The overall mean is and . Splitting between and gives parts and with means and and each. The gain is , and the identity gives . The other cut points give gains .
For pruning, let a tree with training points have two subtrees below the root: with leaves and errors where collapsing to a leaf gives errors, and with leaves and errors where collapsing gives . If the root collapsed alone gives errors, then , and . The smallest is , so is collapsed first. Now the tree has leaves and error , so , and the root is the next weakest link. Collapsing the root leaves a single leaf, so the sequence is: the full tree, the tree with collapsed, and the single leaf.
Worked example 31.1.8
(A tied split, a zero-gain threshold and a pure node)
Take with labels . The root has and . The threshold gives a pure left child and a right child with , so . By symmetry the threshold also gives . The threshold gives children and with each, so : both children have the parent's class proportions, which is the equality case of the theorem. The two best thresholds tie, so a fixed tie rule is needed; taking the smaller threshold, the root splits at .
For the right child with labels and , the threshold gives and with gain , while the threshold gives and , both pure, with gain . The tree therefore splits at , and its three leaves predict for , for and for , with training error . Each leaf is pure, so there, and any split of a pure node has and : the node stays a leaf.
Common mistakes and subtle points
Common mistake
(Greedy gain, training error and the tree sequence are easily misread)
A tree that attains zero training error is not necessarily good. Gain is greedy: a split with zero gain may still be needed, and the best first split need not be part of the best tree. Selecting by minimizing training error always returns the full tree, since is smallest for the largest tree; the choice must use independent data. Splitting thresholds must lie between distinct feature values, otherwise a split can separate equal inputs. Finally, trees are unstable: a small change in the data can change the root split and hence the whole tree.
Common mistake
(Child impurities must be weighted by child size)
Averaging the two child impurities without weights overrates a split that peels off a few points. Let the parent have five points of each of two classes, and send one point of the first class left and the remaining right. The left child has and the right child has . The unweighted average is , which would suggest a gain of about . The correct weighted gain is .
Exercises
Quick check
(A node has class counts . Find its Gini impurity.)
Square each class proportion and subtract the sum from one.
Solution · Answer
The proportions are , so .
Quick check
(A node has points of each of two classes. A split sends left and right. Compute the gain. Then compute the gain at the root of the exclusive-or sample, split on one feature.)
Weight each child impurity by its share of the points.
Solution · Answer
The parent has . Each child has or , so , and the weighted child impurity is . The gain is . For the exclusive-or sample with four points, two of each class, the parent has , and splitting on either feature gives two children each containing one point of each class, with , so the gain is .
Quick check
(Let at sorted . Find the SSE of the parent, the gain of each of the three splits, and the best split. Check one gain by the closed form.)
Compute each part's SSE about its own mean.
Solution · Answer
The mean is and the parent SSE is . Splitting after the first point gives and , with SSE and , so the gain is . After the second point, and each have SSE , gain . After the third, has SSE and has , gain . The best split is after the second point, with gain . Closed form: .
Quick check
(A node has and its subtree has leaves with . Find , and say whether the node is collapsed at and at .)
Compare with .
Solution · Answer
. At the subtree is kept; at it is collapsed.