Why Randomize the Predictors as Well as the Data?
Bagging builds trees from bootstrap samples of the training data and combines their predictions. But if the same predictor is consistently the strongest split, many bagged trees may make similar choices near their roots. Their structures and predictions can then remain alike, even though their bootstrap samples differ.
A random forest adds another source of randomness: at each split, it makes only a randomly selected subset of the predictors eligible to compete. A strong predictor can be unavailable at a particular split, allowing another eligible predictor to be selected instead. The resulting trees can differ in structure as well as in the bootstrap observations used to fit them.
Suppose the training data contain \(n\) observations and \(p\) predictors. A typical forest draws a bootstrap sample of size \(n\) for each tree. At a node in that tree, it selects a subset of the predictors and chooses the best split among the eligible predictors, according to the tree’s splitting criterion. The subset is selected again at other nodes, so a predictor may be eligible at one node and unavailable at another.
The trees may use the same stopping or growth rules as other tree ensembles. Random predictor selection does not change the definition of a valid split; it changes which predictors can be considered for that split. If the globally best predictor is excluded, the algorithm chooses the best available alternative, not an unavailable predictor.
How a Restricted Candidate Set Changes a Split
For classification, a split can be assessed by the reduction in node impurity. For example, the Gini impurity of a node with class proportions \(p_1,\ldots,p_K\) is \(1-\sum_{k=1}^{K}p_k^2\). The split’s impurity decrease is the parent impurity minus the weighted average impurity of its child nodes. A forest compares eligible splits using the criterion specified for the tree; it does not compare an eligible split against a split that was excluded from consideration.
Worked Example: Choosing Among Available Classification Splits
At a node in a hypothetical two-class tree, there are 16 observations: 8 in class 1 and 8 in class 2. Four predictors, A, B, C, and D, offer the splits shown below. For each split, the two child nodes’ class counts are given. A random predictor subset makes only B, C, and D eligible. Which split is chosen?
Method. Calculate the parent Gini impurity, then calculate the weighted child impurity and impurity decrease for each predictor. Finally, choose the largest decrease among the eligible predictors.
The parent class proportions are \(8/16\) and \(8/16\), so its Gini impurity is \(1-(8/16)^2-(8/16)^2=1-1/4-1/4=1/2=0.5\).
For A, the child counts are \((7,1)\) and \((1,7)\). Each child has Gini impurity \(1-(7/8)^2-(1/8)^2=1-49/64-1/64=14/64=0.21875\). The children each contain 8 observations, so their weighted average impurity is \((8/16)(0.21875)+(8/16)(0.21875)=0.21875\). A’s impurity decrease is \(0.5-0.21875=0.28125\).
For B, the child counts are \((6,2)\) and \((2,6)\). Each child has impurity \(1-(6/8)^2-(2/8)^2=1-36/64-4/64=24/64=0.375\). The weighted average is \(0.375\), giving a decrease of \(0.5-0.375=0.125\).
For C, the child counts are \((5,3)\) and \((3,5)\). Each child has impurity \(1-25/64-9/64=30/64=0.46875\). The weighted average is \(0.46875\), giving a decrease of \(0.5-0.46875=0.03125\).
For D, the children each have counts \((4,4)\). Each child’s impurity is \(1-16/64-16/64=0.5\). The weighted average is \(0.5\), giving a decrease of \(0.5-0.5=0\).
Among the eligible predictors B, C, and D, the largest decrease is B’s \(0.125\). The forest therefore chooses B’s split. A would have given the largest decrease overall, \(0.28125\), but A is not eligible at this node.
Check. The chosen decrease is positive and smaller than the parent impurity of \(0.5\), as expected for these child impurities. The common mistake is to select A because it has the best decrease overall. The correction is to compare only the available predictors.
Extra Randomness and Tree Diversity
Bootstrap sampling changes which observations a tree sees, while predictor subsampling changes which split options it can use. These are distinct sources of variation. Even for similar bootstrap samples, two trees can choose different splits if their candidate subsets differ. Those choices can lead to different downstream nodes, terminal regions, and predictions.
The effect is not that every tree must be different, or that every randomized split must be weaker. Two trees can draw the same useful candidates and make the same choices. Conversely, a tree may be forced to use a less effective predictor at a particular node because its strongest option was unavailable. The forest’s behavior reflects both effects across many trees.
Worked Example: Comparing Predictions From Different Tree Choices
For a hypothetical regression problem, three bootstrap-fitted trees are evaluated at the same predictor profile. In a bagged fit, all predictors are eligible at every split; the three trees’ terminal-node response means for this profile are 96, 100, and 104. In a random forest, predictor subsets change some split choices; the corresponding terminal-node response means are 80, 100, and 90. Calculate each ensemble’s average prediction and explain what the comparison shows.
Method. For each ensemble, add the three tree predictions and divide by 3.
The bagged prediction is \((96+100+104)/3=300/3=100\). The random forest prediction is \((80+100+90)/3=270/3=90\).
In this hypothetical comparison, predictor subsampling has changed some tree paths and their terminal-node means, so the ensemble prediction differs by \(90-100=-10\). This illustrates a change in the fitted forest, not proof that the forest is more or less accurate. To assess accuracy, predictions must be compared with suitable outcomes not used to fit the relevant trees.
Check. The sum of the random-forest tree predictions is \(270\), and \(270/3=90\). A common mistake is to assume that randomization must move the prediction toward the correct value. Without knowing the true response, neither ensemble can be declared more accurate from these predictions alone.
A Simple Probability Calculation for Predictor Availability
A small probability calculation makes the extra randomization concrete. Suppose a node has \(p\) predictors and its candidate set contains exactly \(q\) distinct predictors, selected uniformly from all subsets of that size. For a particular predictor, the probability of appearing in the set is \(q/p\): there are \(\binom{p}{q}\) possible sets and \(\binom{p-1}{q-1}\) of them contain that predictor.
The last equality follows by expanding the combinations: \(\binom{p-1}{q-1}/\binom{p}{q} = [(p-1)!/((q-1)!(p-q)!)]/[p!/(q!(p-q)!)] = q/p\). This calculation describes availability, not the probability that the predictor is ultimately selected. It may be available but lose to another candidate under the split criterion.
Worked Example: How Often Is a Predictor Available?
A hypothetical forest has five predictors. At each of four specified nodes, two predictors are selected uniformly from the five, and the selections at the four nodes are independent. Calculate the probability that predictor Z is available at least once and the expected number of these nodes at which Z is available.
Method. First find Z’s availability probability at one node. Then use independence to calculate the probability it is absent from all four nodes. Finally, use indicator variables to calculate the expected number of appearances.
At one node, the probability Z is available is \(q/p=2/5=0.4\). Therefore, the probability it is absent at one node is \(1-0.4=0.6=3/5\).
By independence, the probability Z is absent at all four nodes is \((3/5)^4=81/625=0.1296\). Thus, the probability it is available at least once is \(1-81/625=544/625=0.8704\).
For the expected number of appearances, define an indicator equal to 1 if Z is available at a node and 0 otherwise. Each indicator has expectation \(2/5\). The expectation of their sum is the sum of their expectations, so it is \(4(2/5)=8/5=1.6\) nodes.
Check. The probability of at least one appearance, \(0.8704\), lies between 0 and 1, and the expected count, \(1.6\), lies between 0 and 4 nodes. Independence was needed for the probability of absence at all four nodes; it was not needed to add the four expectations.
What Diversity Does—and Does Not—Guarantee
Random predictor subsets can make trees less alike by giving them opportunities to choose different splits. Since the ensemble combines multiple trees, reducing similarity can be useful: it may reduce the extent to which the trees make the same errors. But a random forest is not guaranteed to outperform bagging in every sample or at every predictor profile. Restricting the candidates can exclude a valuable split, and the resulting change may help or hurt prediction.
The relevant idea is a balance between the quality of individual trees and how much their errors move together. Extra randomness can alter that balance; it does not establish the outcome in advance. This is why a forest’s predictive performance must be assessed rather than inferred merely from the fact that it uses randomized subsets. The treatment here is aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.
Common Mistakes
- Confusing the two sources of randomness. Bootstrap sampling changes the observations in a tree’s training sample; predictor subsampling changes the predictors eligible at a split.
- Choosing an unavailable predictor. At each node, compare split choices only within the candidate set for that node.
- Treating availability as selection. A predictor’s chance of appearing in a candidate set is not its chance of winning the split competition.
- Assuming more diversity means better accuracy. Different structures can make errors less alike, but a restricted candidate set can also force a weaker split. Accuracy requires an appropriate evaluation.
- Assuming every tree must differ. Random candidate sets can coincide, and different sets can still lead to the same selected split.
Check Your Understanding
Work each problem through before checking its final answer.
- A node has six predictors, and a uniformly selected candidate set contains two. What is the probability that predictor F is available at this node? Explain why this is not necessarily the probability that F is selected. (Answer: \(2/6=1/3\) that F is available; its selection probability also depends on the competing splits.)
- At a regression node, the parent sum of squared errors is 72. Candidate gains are A: 24, B: 17, C: 9, and D: 4. The random candidate set is \(\{B,D\}\). Which predictor is selected, and what is the resulting child sum of squared errors? (Answer: B is selected; \(72-17=55\).)
- At each of three independent nodes, a forest selects two of five predictors uniformly. What is the probability that a specified predictor is available at least once? (Answer: \(1-(3/5)^3=98/125=0.7840\).)
- Four regression trees in a hypothetical forest predict 12, 16, 18, and 22 for one profile. Calculate the forest’s average prediction. If random predictor subsets caused some trees to take different paths, what does this average establish about accuracy? (Answer: \((12+16+18+22)/4=17\); the average prediction is 17, but accuracy cannot be determined without an appropriate observed outcome.)
- Two forests use the same number of bootstrap-fitted trees. One uses all predictors at each split, while the other uses random predictor subsets. The second forest has more varied root predictors in this training run. State one mechanism that could explain the difference and one conclusion that cannot be drawn from it alone. (Answer: Different candidate subsets can make different predictors eligible and therefore change the selected root splits; greater root diversity alone does not establish that prediction error is lower.)