Why Repeated Split Choices Matter
A tree can be sensitive to small changes in its training data. In a bagged ensemble, bootstrap samples encourage some variation among the trees, but a predictor that repeatedly offers the strongest split can still dominate their structure. If it is available at every node, many trees may divide the data in much the same way. Averaging similar trees usually provides less variance reduction than averaging trees whose predictions differ in their errors.
Feature subsampling adds another source of variation: at a node, the tree considers only a randomly chosen subset of predictors as split candidates. The best split is then chosen from that subset. This does not force the tree to use a weak predictor. Rather, it sometimes makes the strongest predictor unavailable, allowing another predictor to determine the split. Repeating this process across trees can reduce structural similarity and, when the resulting prediction errors differ, reduce inter-tree prediction correlation.
Candidate Availability and Split Choices
Suppose there are \(p\) predictors and a node draws \(m\) distinct candidates uniformly at random, with \(1 \leq m \leq p\). For any particular predictor, its probability of appearing in the candidate set is \(m/p\): there are \(m\) available positions for that predictor among the \(p\) equally likely positions. If two trees draw their candidate sets independently at the same node, the probability that a specified predictor appears in both sets is \((m/p)^2\).
This is a statement about availability, not selection. A predictor can be a candidate and still lose to a better split in that node's candidate set. Conversely, a predictor excluded from the set cannot be selected there, no matter how strong its split would have been if considered. The distinction is central: feature subsampling changes the competition among split options, not the split-scoring rule itself.
Worked Example: A Dominant Predictor Is Not Always Available
A hypothetical claim-severity tree has four predictors, \(D,A,B,C\). At a given node, each tree samples \(m=2\) candidates uniformly without replacement. Assume \(D\) gives the best split whenever it is available; if it is absent, \(A\) gives the best split. Two trees draw their candidate sets independently. Find the probability that both choose the same root predictor, and compare it with the case where all four predictors are always candidates.
Method. Enumerate the equally likely size-two candidate sets. There are \(\binom{4}{2}=6\). Predictor \(D\) appears in \(\binom{3}{1}=3\) of them, so \(P(D\text{ available})=3/6=1/2\). If \(D\) is available, it is selected; if it is absent, \(A\) is selected by assumption. Thus a tree selects \(D\) with probability \(1/2\) and \(A\) with probability \(1/2\).
Because the two candidate-set draws are independent, the probability both trees select \(D\) is \((1/2)^2=1/4\). The probability both select \(A\) is also \(1/4\). Therefore, the probability of the same root predictor is \(1/4+1/4=1/2\).
If all four predictors are candidates at every tree's root, both trees select \(D\), so their root predictor agrees with probability \(1\). In this stipulated example, feature subsampling lowers root-choice agreement from \(1\) to \(1/2\). Check: the two agreement events are disjoint and exhaust the ways the selected root predictors can match, and their probabilities sum to \(1/2\).
Common mistake avoided: \(m/p=1/2\) is the probability that \(D\) is available, not the probability that two trees choose the same predictor. Agreement requires considering the selection probabilities for every possible winner.
From Tree Correlation to Ensemble Variance
The benefit of decorrelation is easiest to see for a numerical prediction averaged over \(B\) trees. Let \(T_b\) be the prediction from tree \(b\) at a fixed prediction case. Assume that each \(T_b\) has variance \(\sigma_T^2\), and that every pair of distinct trees has the same correlation \(\rho\). These equal-variance, equal-correlation assumptions are a simplifying model; real forests need not satisfy them exactly. The ensemble prediction is \(\bar{T}=B^{-1}\sum_{b=1}^B T_b\).
The first term inside the brackets, \(\rho\), remains even as \(B\) grows. The second term, \((1-\rho)/B\), shrinks as more trees are averaged. Thus, if individual-tree variance is held fixed, lower positive inter-tree correlation reduces the variance that remains in the large-ensemble limit. This explains why decorrelation can help when simply increasing the number of trees has diminishing returns.
Worked Example: Comparing Two Correlation Levels
At a hypothetical policy valuation case, suppose each tree prediction has variance \(16\) (in squared prediction units), and an ensemble averages \(B=25\) trees. Under one candidate-sampling scheme, assume the pairwise tree correlation is \(0.60\); under another, assume it is \(0.20\). Compare the ensemble variances, holding the individual-tree variance fixed.
Method. Use \(\operatorname{Var}(\bar{T})=\sigma_T^2[\rho+(1-\rho)/B]\), which requires equal individual variances and a common pairwise correlation.
For \(\rho=0.60\), the bracket is \(0.60+(1-0.60)/25=0.60+0.40/25=0.60+0.016=0.616\). The ensemble variance is \(16(0.616)=9.856\).
For \(\rho=0.20\), the bracket is \(0.20+(1-0.20)/25=0.20+0.80/25=0.20+0.032=0.232\). The ensemble variance is \(16(0.232)=3.712\).
The variance difference is \(9.856-3.712=6.144\) squared prediction units. The lower-correlation case has lower ensemble variance under the stated assumptions. Check: as \(B\) grows without bound, the formula approaches \(16\rho\), which is \(9.6\) in the first case and \(3.2\) in the second; both are below their respective finite-\(B\) values.
Common mistake avoided: adding trees does not eliminate the correlation component. For example, with \(\rho=0.60\), the limiting variance is \(16(0.60)=9.6\), not zero.
Why Less Similar Structure Is Not the Same as Less Correlated Prediction
Different root variables are evidence of structural variation, not a direct measurement of prediction correlation. Two predictors can encode nearly the same information or induce the same grouping of cases. Trees that split on different names can therefore make almost identical predictions. On the other hand, changing a split can substantially alter which observations reach each terminal node, creating different prediction errors.
Worked Example: Different Predictors, Identical Predictions
A hypothetical tree has two binary predictors, \(D\) and \(A\), that divide three valuation cases in exactly the same way: cases 1 and 2 have value 0 for both predictors, and case 3 has value 1 for both. Suppose a split on either predictor produces terminal predictions of \(10\) for the first two cases and \(30\) for the third. One tree selects \(D\), and another selects \(A\). Compare their prediction vectors and explain what this does—and does not—show about decorrelation.
The prediction vector from the tree using \(D\) is \((10,10,30)\). The tree using \(A\) also predicts \((10,10,30)\). Their case-by-case prediction differences are therefore \((0,0,0)\). The split-variable names differ, but the predictions coincide exactly on these cases.
This example shows why root-variable disagreement alone cannot establish that prediction correlation has fallen. In a repeated-sampling analysis, identical prediction behavior would provide no prediction diversity for these cases. However, this three-case calculation does not define a correlation coefficient: correlation requires a specified collection of varying predictions or repeated fits, and it is undefined if one of the compared prediction variables has zero variance. Check: the two vectors match entry by entry, so no difference in their predicted values can be attributed to the different predictor names.
Common mistake avoided: treating every change in split variable as proof of lower tree correlation. Correlation concerns predictions, not merely tree diagrams.
What Feature Subsampling Changes—and What It Does Not
Random candidate sets can reduce the chance that the same strong predictor is available to every tree at a split. Where another candidate offers a useful alternative, the selected split may change and send observations down different branches. Across many nodes, these changes can make trees less alike and may reduce their prediction correlation. The mechanism is probabilistic: candidate-set randomization creates opportunities for different choices; it does not promise that those choices will be useful or that ensemble error will fall.
A small candidate set can also exclude predictors that would have produced strong splits. Individual trees may then have less accurate predictions or more variability. The variance formula isolates the effect of correlation only when individual-tree variance is held fixed. In practice, feature subsampling can affect both quantities, so a reduction in correlation alone is not enough to conclude that total prediction error has improved.
The following distinctions are useful when interpreting the mechanism:
- Candidate overlap: whether two trees are offered the same predictors at a node.
- Split agreement: whether they select the same predictor or partition.
- Prediction correlation: whether their numerical predictions tend to vary together.
- Ensemble performance: the resulting prediction quality, which also depends on individual-tree accuracy and the target loss measure.
These are related but not interchangeable. For example, independent candidate sets may still overlap substantially, and even distinct sets can lead to the same selected split. Distinct splits can likewise lead to almost identical predictions when predictors are redundant. Feature subsampling is therefore best understood as a way to weaken one cause of tree similarity—repeated access to the same dominant predictors—rather than as a guarantee of independent trees.
Check Your Understanding
Work through each question using the stated assumptions. Answers are given at the end of each item.
- A tree has \(p=10\) predictors and samples \(m=3\) candidates at a node. What is the probability that a specified predictor is available to one tree, and what is the probability it is available to both of two trees with independent candidate sets? (Answer: \(0.3000\) and \(0.0900\), respectively.)
- There are five predictors, and each of two trees independently selects one predictor uniformly at random as its root split. What is the probability that the trees select the same predictor? (Answer: \(0.2000\).)
- Suppose \(B=20\), each tree prediction has variance \(25\), and all distinct pairs have correlation \(0.40\). Calculate the variance of the averaged prediction. (Answer: \(25[0.40+0.60/20]=10.75\).)
- For the assumptions in question 3, what is the limiting variance as the number of trees grows without bound, and how much larger is the finite-ensemble variance? (Answer: limiting variance \(10\); the variance at \(B=20\) is \(0.75\) units larger.)
- Two trees use different predictors at a split, but those predictors divide every prediction case into the same groups and give the same terminal predictions. What conclusion is justified about their predictions, and what conclusion is not justified from split names alone? (Answer: their predictions coincide on those cases; different split names alone do not establish lower prediction correlation.)