Random forests: how many decision trees vote on a single prediction
A random forest is an ensemble of decision trees. Each tree is trained on a bootstrap sample and uses random feature subsets. For classification, the forest takes a majority vote across all trees; for regression, it averages their outputs.
The voting mechanism
In a random forest, each decision tree in the ensemble produces its own prediction for a given input. The forest then combines these predictions: for classification, it takes the class that receives the most votes, and for regression, it averages the tree outputs, as described in IBM's random forest overview.
The voting process relies on the diversity of the trees. If all trees were identical, the vote would simply repeat the same error. The random forest deliberately introduces randomness so that different trees make different mistakes, and the majority can correct individual errors.
The number of trees is a key hyperparameter. More trees generally improve accuracy up to a point, but the gain diminishes and the computational cost increases. The forest can be run with many trees without overfitting, according to the Berkeley random forests description.
How each tree is built
Each tree in a random forest is trained on a bootstrap sample: a random sample of the training data drawn with replacement, meaning some data points appear multiple times and others are left out. This is the bagging method, as explained in IBM's bagging article.
At each node of a tree, only a random subset of the input features is considered for the best split. This feature randomness, also called feature bagging, reduces the correlation between trees. The Berkeley page notes that the number of features considered, denoted m, is held constant during forest growth.
Trees are grown to their full depth without pruning. This high-variance approach is intentional: each tree may overfit, but the ensemble averages out the individual overfitting, leading to a lower overall error.
The wisdom of the crowd
The idea behind voting in random forests is similar to the wisdom of the crowd. A famous example is the 1906 ox weight guessing competition, where the average of many individual guesses was closer to the true weight than most individual guesses, as noted in Google's decision forests introduction.
Mathematically, this is supported by Condorcet's Jury Theorem from 1785, which states that if each voter is more than 50 percent correct, adding more voters increases the probability that the majority is correct. The MLU Explain random forest page uses this theorem to show that a forest of trees with 60 percent accuracy can reach 75 percent accuracy with enough trees.
The theorem has a caveat: the trees must be different. If every tree makes the same prediction, the vote does not improve. The random forest achieves this difference through bagging and feature selection.
Out-of-bag error and evaluation
Because each tree is trained on a bootstrap sample, about one-third of the training data is left out for that tree. This out-of-bag (OOB) data can be used to estimate the test error without a separate validation set, as described in Cornell's lecture on bagging.
The OOB error is computed by running each training point through the trees that did not see it during training and comparing the aggregated prediction to the true label. This provides an unbiased estimate of the generalization error.
The OOB error can also be used to tune the number of features considered at each split. The Berkeley page states that the forest error rate depends on the correlation between trees and the strength of individual trees, and that the OOB error helps find a good value for m.
| Aspect | Bagging | Random forest |
|---|---|---|
| Training data | Bootstrap samples with replacement | Bootstrap samples with replacement |
| Feature selection | All features considered at each split | Random subset of features at each split |
| Tree correlation | Higher | Lower due to feature randomness |
| Prediction for classification | Majority vote | Majority vote |
| Prediction for regression | Average | Average |
| Typical use | Reduce variance of high-variance models | Improve accuracy and reduce overfitting |
Frequently asked questions
How many trees are needed in a random forest?
There is no fixed number. More trees generally improve accuracy up to a point, but the gain diminishes. The Berkeley page notes that random forests do not overfit, so one can run as many trees as desired, limited only by computational resources.
What is the difference between bagging and random forest?
Bagging uses bootstrap samples but considers all features at each split. Random forest adds feature randomness, selecting a random subset of features at each split, which reduces correlation between trees. IBM's bagging article states that random forest is an extension of bagging.
How does the majority vote work in classification?
Each tree in the forest predicts a class for a given input. The class that receives the most votes across all trees becomes the final prediction. This is called hard voting or majority voting, as described in IBM's ensemble learning article.
What is out-of-bag error?
Out-of-bag error is an estimate of the test error computed from the training data that each tree did not see. For each training point, the trees that did not include it in their bootstrap sample are used to make a prediction, and the error is averaged. This is explained in the Cornell lecture.
Why do random forests need diverse trees?
Diverse trees make different errors, so the majority vote can correct individual mistakes. If trees are identical, the vote does not improve. The MLU Explain page emphasizes that the forest performs better when trees are different, which is achieved through bagging and feature selection.