Split-Time Feature Subsampling in Random Forests

Bagging gives each tree a different resample, and that is not enough to make the trees differ much. The reason is visible in the split search: if one feature is strongly associated with the target, the greedy scan at the root will pick it in almost every resample, and the second level will pick whatever complements it in almost every resample, and so on. Two trees trained on overlapping samples of the same data with the same algorithm and the same candidate set tend to reconstruct the same structure. The average of near-identical trees has the variance of one tree.

A random forest changes one part of the procedure: at each node, the split search considers only a random subset of the features. Everything else is bagging. This single change decorrelates the members enough to make the averaging worthwhile, and the size of that subset becomes the central hyperparameter.

The dominant-feature problem

Consider a dataset where one feature carries most of the signal. Under plain bagging the root split of essentially every tree uses that feature, with a threshold that varies only slightly across resamples. The first two or three levels are therefore shared, and the trees agree on the prediction for a large fraction of the input space. Their correlation $\rho$ is close to one, so the ensemble variance $\rho\sigma^2 + (1-\rho)\sigma^2/B$ stays near $\sigma^2$ no matter how many members are added.

The fix has to break the agreement at the point where it is created, which is the split choice. If the strong feature is not in the candidate set for a given node, that tree is forced to explain the node with a different variable. It may do so worse, so the individual tree is weaker, but the error it makes is now different from the error its siblings make. Averaging differences reduces variance; averaging the same error does not.

This is the random subspace idea applied locally. Ho’s random subspace method drew a random subset of features once per tree, before fitting. Breiman’s forest draws a fresh subset at every node, which decorrelates more aggressively because a tree can still use the strong feature at the nodes where it happens to be drawn.

Sampling columns at each split, not at each tree

The mechanics are small. At a node with $n$ samples, the algorithm draws $m$ of the $p$ features uniformly without replacement, runs the usual sorted scan on each of the $m$, and takes the best split found. The remaining $p-m$ features are not examined at that node, though they remain available at every descendant.

def best_split_restricted(X, y, cols, rng, m, impurity):
    chosen = rng.sample(cols, m)       # m of p columns, without replacement
    best = None
    for j in chosen:
        order = sorted(range(len(y)), key=lambda i: X[i][j])
        cand = scan_threshold(order, X, y, j, impurity)
        if best is None or cand.decrease > best.decrease:
            best = cand
    return best

Three consequences follow directly from the loop.

The search is cheaper. The per-node cost of evaluating splits is proportional to the number of candidates scanned, so drawing $m$ of $p$ features reduces the dominant term by a factor of about $p/m$. With $p = 500$ and $m = 22$, the split search is roughly twenty times cheaper per node, which is why forests with heavy subsampling can be trained on wide problems where a single unpruned tree would be impractical.

The randomness is per node, not per tree. Two trees that happen to receive the same resample still diverge, because their root nodes draw different candidate sets with high probability. The number of distinct subsets is $\binom{p}{m}$, which is large even for modest $p$.

The sample size per feature is unchanged. Subsampling selects features, not rows. Every candidate feature is scanned over all $n$ samples at the node, so the threshold estimate is as precise as it would be without subsampling. This is the reason forests do not suffer the small-sample instability that comes from subsampling rows at the split level.

Strength and correlation as the two levers

Breiman’s analysis makes the trade explicit. Define the margin of a forest on a sample as the difference between the fraction of trees voting for the correct class and the fraction voting for the strongest incorrect class. Let $s$ be the expected margin, the forest’s strength, and let $\bar\rho$ be the mean correlation between the trees’ predictions. The generalization error is then bounded above by

$$ \text{PE}^* \le \frac{\bar\rho,(1-s^2)}{s^2} $$

The bound is loose and is not an estimate of accuracy, but it has the right shape. Error falls when strength rises and when correlation falls, and the two move in opposite directions as $m$ changes. Increasing $m$ makes each tree stronger, because the split search has more to choose from, and more correlated, because every tree sees the same strong features. Decreasing $m$ does the reverse. The default values, roughly the square root of $p$ for classification and a third of $p$ for regression, sit where the product is empirically favourable rather than at either extreme.

The trade also explains a fact that is easy to misread. A forest’s training error decreases with $m$, because individual trees fit better, while its generalization error has a minimum somewhere in the middle. Watching training error would recommend $m = p$, which is plain bagging.

What the extremes actually do

At $m = p$ the procedure is bagging, and the correlation term dominates. On datasets with several comparably strong features, the difference from a forest is modest; on datasets with one dominant feature, it is large.

At $m = 1$ every split is a comparison of randomly chosen single features. The trees become very different from one another and very weak, since no split can combine information. The forest then needs many more members, and on problems where interactions carry the signal the bias introduced by single-feature splits may not be recoverable at any ensemble size. Small $m$ is useful mainly when $p$ is very large and most features are irrelevant, where the cost saving matters and the strong features are still reachable across the ensemble.

Two boundary conditions deserve attention. When $p$ is small, say below five, subsampling removes little correlation and the forest reduces to bagging with extra randomness; the gain over a single tree comes from the averaging alone. When many features are pure noise, a large $m$ means most split candidates at a node are noise, and the greedy scan will pick up spurious thresholds. Small $m$ is a defence there, but it is a weaker defence than removing the noise features.

A different lever acts on the threshold rather than the feature set. Extremely randomized trees choose a random cut point within the observed range of a candidate feature instead of the optimal one, which adds variance to the split location and further decorrelates the members. That variant trades a little more bias for a cheaper search, since no sort is needed, and is the right choice when training cost dominates.

Importance scores inherit the correlation

The standard importance measure accumulates, over all nodes where a feature was used, the weighted impurity decrease. Two biases are built in. Features with many distinct values offer more candidate thresholds and therefore more chances to produce a spurious gain, so they score higher than they deserve; this is severe for high-cardinality categorical variables encoded as integers. And when several features are correlated, the impurity decrease is split arbitrarily among them, so each looks weak even though the group is strong.

Permutation importance avoids the first bias by measuring the drop in accuracy when a column’s values are shuffled, which uses the fitted model rather than the split history. It does not avoid the second: permuting one of two identical columns leaves the model able to recover the information from the other, so both score near zero. Grouping correlated columns before permuting is the usual remedy, and it requires knowing the correlation structure, which is exactly what the importance score was supposed to reveal.

Neither measure says anything about the direction or shape of a feature’s effect. A high score means the forest uses the feature, not that the relationship is monotone, and marginal-effect plots computed from a forest can be badly misleading when features interact. The constraints discussed in monotonic and interaction constraints exist precisely because the fitted function may violate a relationship that the domain requires.

The other persistent cost is inference. A forest of $B$ trees with depth $d$ costs $B \cdot d$ comparisons per prediction, and no amount of training-side cleverness changes that. Every comparison is a threshold test on one feature, which means the fitted function is a sum of step functions and inherits their inability to produce a value outside the range seen in training; the consequences of that shape are taken up in why tree ensembles cannot extrapolate.