From One Decision Tree to a Random Forest

Here is the entire training problem in miniature. Each dot is one labelled observation, blue or red, and each position contains two measured features. We want a rule that predicts the colour of a new point. A decision tree will not draw a diagonal or fit a smooth curve. At one node it chooses one feature, one threshold, and one yes-or-no question. That question cuts the current region with an axis-aligned line. But which question should it ask first? The usual classification answer is the split that reduces impurity most. Impurity is not model error. It measures how mixed the labels are inside a node. For Gini impurity, subtract the squared class proportions from one. At the root we have eight blue and eight red, so both proportions are one half. The root impurity is zero point five, its largest possible value for two classes. The fitting code now considers thresholds between observed values. Let us compare two representative candidates. A vertical cut at x one equals four leaves both children evenly mixed. Its weighted child impurity is still zero point five. Subtract that from the root impurity and the gain is zero. The cut changed the addresses of the points, but learned nothing about their labels. Now try x two less than four. Below the line are six blue and two red. Above it are two blue and six red. Each child has Gini impurity three eighths, and their weighted average is also three eighths. The reduction is zero point five minus zero point three seven five, which is zero point one two five. That is larger than the vertical candidate's zero, so this horizontal question wins. The first branch of the tree and the first pair of rectangles are the same decision written in two languages. The root asks x two less than four. The left child receives the lower rectangle, and the right child receives the upper one. Notice what has not happened. We have not classified everything correctly, and neither child is pure. We have only made the labels less mixed. Training a tree means repeating this exact competition inside each child. That is the basic fitting loop behind the library call. Enumerate legal feature thresholds, score their weighted impurity, choose the best gain, partition the observations, and repeat on the resulting nodes.

Continue from the root split. The tree on the left and feature space on the right will grow together. A new internal node must always correspond to a new axis-aligned cut inside exactly one existing rectangle. Start in the lower rectangle. It contains six blue observations and two red ones. The best available gain first separates the far-right red point with x one less than six point one. The right child is pure, but the large left child is not. Within that child, a horizontal cut at x two equals two point five creates a pure blue strip below and a mixed strip above. That upper strip is mixed because of one red observation at two point two, two point eight. Another vertical threshold isolates it. The training algorithm is rewarded, because two new leaves become perfectly pure. Now do the same work above the root. Most points there are red, but two blue exceptions force the recursion to continue. The first upper split separates the far-right pair from the rest. The far-right pair still disagrees. A horizontal cut isolates the blue point at the top from the red point below. Again, training impurity falls to zero in both resulting leaves. The left upper region has its own blue exception. A split at x one equals two point eight narrows the search, and another horizontal split at x two equals five point one separates one red point. One final threshold at x one equals one point five isolates the remaining upper blue point. Every terminal region now contains only one class. Consequently every leaf has Gini impurity zero. On the training set, this looks perfect. Every observation is classified correctly. But look at the geometry required to achieve it: thin strips, short corridors, and thresholds whose only purpose is to rescue one exceptional dot. A new point can cross one of those arbitrary thresholds after an imperceptible change in a feature. Its predicted class then jumps, even though the training labels gave us almost no evidence that such a jump should exist. This is the characteristic strength and weakness of an unconstrained decision tree. It has low bias because it can represent complicated interactions. It also has high variance because a few observations can rearrange entire branches and rectangles. Pure leaves are therefore a training condition, not evidence of a useful model. The next question is whether every branch earns its complexity on data that did not choose the branch.

The fully grown tree has zero training impurity, but it pays for that fit with nine leaves and several thresholds supported by a single unusual observation. Pruning asks whether those extra leaves earn their keep. Cost-complexity pruning gives the trade a precise form. R of T measures the fitted tree's error or impurity. The second term charges alpha for every terminal leaf. At alpha zero, extra leaves are free, so the pure tree wins. As alpha increases, a weak pair of leaves can cost more than the small reduction in training error that created it. Prune the weakest lower twigs first. Their narrow thresholds disappear from feature space at the same moment their branches disappear from the tree. The replacement leaf predicts the local majority class. Now prune the corresponding upper twigs. Again, the replacement is not pure on the training set. It deliberately accepts a few mistakes in exchange for a much larger and more stable prediction region. The remaining four-leaf tree still captures the broad interaction. The horizontal root separates low from high x two. Within each half, one x one threshold handles the main exception near the far-right edge. This smaller tree has higher training error by construction. The relevant question is whether it has lower error on observations that did not participate in choosing all those thresholds. A pruning path supplies a nested sequence of subtrees. Here the unpruned tree has nine leaves and no training mistakes, but its validation error is the worst entry in the table. A small penalty removes three leaves. Training error rises, validation error falls. A larger penalty leaves four terminal regions, and the validation error reaches its minimum. Push alpha farther and the tree collapses to two leaves. That model is now too simple for the data, so validation error rises again. Pruning is not a ritual of making trees small. It is model selection along a structured complexity path. Select alpha using cross-validation, a held-out set, or a nested procedure when tuning itself must be evaluated. Never choose the pruning strength by returning to the same training impurity that rewarded every twig. Libraries also offer pre-pruning controls such as maximum depth, minimum samples per leaf, minimum impurity decrease, and maximum leaf count. Those prevent growth. Cost-complexity pruning fits first and removes branches afterward. Either route trades some bias for less variance. A single pruned tree is often much easier to explain and more stable than the pure tree. The forest will take a different route: keep many unstable trees, then make their instability cancel.

A forest does not begin by cloning one fitted tree. It creates many related training problems. For each tree, draw n observations from the original n with replacement. With replacement means an observation can appear more than once. In the first sample, indices one and five are repeated, while three and six are absent. The sample still contains n rows. A second bootstrap draw repeats different observations and omits different ones. A third does it again. Each tree therefore sees a perturbed empirical distribution, even though all draws came from the same dataset. Fitting deep trees to these samples is ordinary bootstrap aggregation, or bagging. It creates diversity because a marginal observation may be duplicated in one sample and unavailable in another. A random forest adds a second source of variation. At every node, it offers the split search only a random subset of the available features. Here is one tree in an eight-feature problem. The formula records a fresh feature subset at node j. At the root, features two, five, and eight are offered, and feature two supplies the best available impurity reduction. The left child gets a fresh draw, features one, four, and eight. The right child gets another draw, features three, five, and seven. Feature availability is local to a node. This restriction can force a tree to ignore the dominant predictor at a particular node. That sounds inefficient for one tree. Its purpose is to prevent every tree from making the same early decisions. Bootstrap sampling perturbs the observations. Feature sampling perturbs the available questions. Together they produce trees whose errors are less synchronized. These are three trees trained from the same original problem. Each diagram shows the axis-aligned boundaries produced by one bootstrap sample and one sequence of random feature offers. The first tree chooses a horizontal root and then several local vertical cuts. Its boundary is coherent within each rectangle, but jagged as a whole. The second tree begins vertically because its sample and offered features differ. It partitions the same feature plane into a visibly different collection of rectangles. The third tree returns to a horizontal root, but its thresholds and deeper branches are different again. None of these trees is intended to be the final boundary. For classification, each tree supplies class probabilities from its reached leaf, commonly the class proportions among that leaf's training samples. The forest averages those probabilities and then chooses a class. For regression, the same architecture averages numeric predictions. Bootstrap samples and random feature subsets still serve the same purpose: build individually flexible models whose mistakes are not identical.

Return to the labelled plane. One deep tree supplies one jagged boundary. It reacts strongly to the particular observations and random choices that shaped its branches. For each query point x, tree b supplies a class probability. The forest averages those probabilities. Its displayed boundary is where the winning averaged class changes. Add trees until B equals ten. Each individual boundary is still made of rectangular steps, but their idiosyncratic notches occur at different places. Majority support removes many notches that only one tree wanted. Now average one hundred trees. The aggregate is still a staircase if we inspect it finely enough, because every contributor is a tree. At this scale, however, it follows the broad class structure rather than every isolated observation. Calling this boundary smoother does not mean that a forest fits a smooth analytic function. It means the averaged prediction varies more stably across nearby points and fewer decisions depend on one tree's narrow rectangular accident. Why should averaging unstable models work? Imagine each tree prediction as a useful signal plus a zero-mean fitting error. Averaging keeps the shared signal. Errors that point in different directions can cancel. If the tree errors were independent and each had variance sigma squared, the mean of B trees would have variance sigma squared over B. Double the number of trees and this variance contribution halves. Real tree errors are not independent. They use the same original dataset, and strong predictors can make them discover similar branches. Let rho represent their average pairwise error correlation. Here is the extreme problem. Five trees all make an error of plus one on the same case. Their average error is still plus one. Repetition did not remove a shared mistake. On the right, errors differ across trees. Positive and negative errors offset, and their average is zero in this small illustration. Diversity is useful when it concerns errors, not merely visual differences between diagrams. With equal variance and average correlation rho, the ensemble variance is sigma squared times rho plus one minus rho over B. The second part shrinks as trees are added. The correlated part does not. Take the number of trees toward infinity. The variance approaches rho sigma squared, not zero. If rho is close to one, a huge forest behaves like repeated copies of one unstable tree. This is why decorrelation is essential. Bootstrap samples alter which observations drive the branches. Random feature subsets prevent one dominant predictor from forcing the same root and early splits in every tree. There is a trade-off. Offering fewer features can weaken each individual tree by denying it useful predictors. But if that loss is modest and the correlation falls substantially, the average can generalize better. Adding trees mainly reduces Monte Carlo noise in the fitted ensemble. It does not repair severe bias, leakage, bad labels, a shifted deployment population, or a feature set that contains no useful signal. The forest's advantage is therefore specific. Deep trees provide flexible, high-variance base predictions. Resampling and feature randomness make their errors less alike. Averaging then removes the part of the variance that is not shared.

Here is a practical sequence that preserves the logic we have developed. Start with the prediction problem, not the estimator. Fix the target, evaluation unit, split strategy, and metric before fitting. A random row split is wrong whenever rows from the same customer, patient, device, location, or future time can leak information across folds. Group and temporal structure belong in the validation design. Fit a small decision tree before the forest. Its splits expose coding mistakes, target proxies, implausible thresholds, and feature interactions that a large ensemble can conceal behind a good aggregate score. Then tune tree structure against validation performance. Maximum depth limits path length. Minimum samples per leaf demands evidence in each terminal region. Cost-complexity alpha removes weak fitted branches. For a forest, raise the number of estimators until the validation metric and predictions stabilize. More trees usually increase compute rather than overfitting in the familiar single-tree sense, but returns become negligible. Finally inspect more than one aggregate score. Check important subgroups, threshold-sensitive decisions, probability calibration, drift, and the cost of the errors the model actually makes. Maximum depth and maximum leaf nodes limit global tree size. They are coarse controls on how many successive rectangles the tree may create. Minimum samples per leaf directly attacks tiny regions. Minimum impurity decrease requires a split to earn enough local gain before it is allowed. Cost-complexity alpha names the post-pruning penalty we used earlier. Its numerical scale depends on the data, weights, impurity, and implementation, so tune it through the supplied pruning path rather than by folklore. Bootstrap turns observation resampling on or off. Max features controls the random candidate subset at each split. Lowering max features usually reduces correlation, but can also weaken individual trees. The number of estimators is the ensemble size B. Parallel-job settings change wall-clock cost, not the fitted statistical objective. Do not confuse faster execution with stronger regularization. Classification probabilities deserve separate validation. A forest averages leaf class proportions, which can rank cases very effectively while remaining overconfident or underconfident as probabilities. Out-of-bag predictions use, for each training row, only trees whose bootstrap samples omitted that row. They provide a convenient internal diagnostic, but they do not override grouped, temporal, or external validation requirements. Impurity-based feature importance summarizes how fitted splits used a feature. It can favour variables with many available thresholds and divide credit awkwardly among correlated predictors. It is not a causal effect. Permutation importance asks how predictive performance changes after one feature is disrupted. It is often closer to the operational question, but correlated features can substitute for one another and hide each other's importance. Class weights alter the fitting objective. They do not decide which deployment metric matters. A random seed makes the stochastic fit reproducible; it does not make sampling uncertainty disappear. The whole lecture can be compressed into three ingredients. Trees must be strong enough to capture useful structure. Their errors must be sufficiently decorrelated. Averaging then reduces the unshared variance. One tree turns impurity reduction into an interpretable hierarchy of rectangles. Pruning makes that hierarchy less fragile. A random forest keeps many flexible trees, makes their mistakes less alike, and averages what remains.