Random forest is an ensemble learning method used for classification, regression, and other tasks. It constructs a large number of decision trees during training and combines their outputs: for classification, it returns the class selected by most trees; for regression, it averages the predictions of individual trees. The method corrects for the tendency of deep decision trees to overfit their training set, reducing variance while keeping bias low.
The first random forest algorithm was developed in 1995 by Tin Kam Ho, based on the random subspace method, which implements the stochastic discrimination approach proposed by Eugene Kleinberg. Leo Breiman and Adele Cutler later extended the approach by combining bagging with random feature selection, and they registered "Random Forests" as a trademark in 2006; as of 2019 the trademark is owned by Minitab, Inc.
Background: Decision Trees and Their Limitations
Decision trees are a widely used method in Machine learning. They partition the feature space through a series of binary splits, making them scalable and easy to interpret. However, deep trees tend to learn highly irregular patterns, leading to low bias but very high variance. In practice, trees trained on a particular dataset can change drastically if a few training points are altered, and their predictions are often accurate only for the training data. They are seldom accurate on unseen data, as noted by Trevor Hastie and colleagues. Random forests address this by averaging many deep trees, each trained on different subsets of data, to significantly reduce variance.
The difficulty with tree methods is that growing too many trees on the same data yields correlated predictions. To de-correlate trees, random forests use bootstrapping and random feature selection, which make the individual trees diverse but strong.
History and Development
The general idea of random decision forests appears in 1993 work by Salzberg and Heath, who proposed using a randomized decision tree algorithm to generate multiple trees and combine them by majority voting. In 1995, Tin Kam Ho extended this idea, showing that forests of trees that split on oblique hyperplanes can gain accuracy as they grow without suffering from overtraining, provided the forests are randomly restricted to only a subset of feature dimensions. Ho's method, called the random subspace method, built trees by projecting the training data into randomly selected feature subspaces. This approach was a key step in the development of random forests.
Subsequent work by Amit and Geman independently introduced the idea of searching a random subset of available decisions at each split, though they applied it to a single tree. Independently, Thomas Dietterich introduced the idea of randomized node optimization, in which the attribute chosen at each node is selected by a random procedure rather than a deterministic optimality criterion. These ideas, combined with Leo Breiman's earlier work on bagging, led to the modern formulation of random forests. Breiman's influential 2001 paper, one of the most cited in machine learning, combined these targets and provided a theoretical bound on generalization error based on the strength and correlation of trees in the forest.
Breiman's paper also established practical tools: out-of-bag error for estimating generalization error without a separate validation set, and permutation-based variable importance, which measures how performance degrades when a feature's values are randomly shuffled. These remain core aspects of random forests today.
Bagging and Ensemble Learning
The base technique in random forest training is bootstrap aggregating, or Bagging. Given a training set with features X and responses Y, the algorithm samples B times with replacement from the training data, each time creating a new dataset of the same size. A decision tree, typically grown deep and unpruned, is fit to each bootstrap sample. After training, predictions for a new point are made by averaging the regression or taking the majority vote for classification. This meta-algorithm decreases broader variance without increasing bias because the average of many trees that are not correlated is more stable than any single tree.
Bootstrap sampling de-correlates trees by showing them different training sets. If all trees were trained on the same original data, they would be highly similar and prone to the same errors. Using the bootstrap, each tree captures random variations. The model gains variance reduction as B increases, but after a few hundred trees, the marginal improvement diminishes. In practice, B is often set to 500 or 1000 trees, though modern implementations automatically stop when the out-of-bag error stabilizes.
A critical aspect of random forests is that each tree is typically trained on a different set of data due to sampling with replacement: approximately two-thirds of observations appear at least once in each bootstrap sample, while the remaining third are out-of-bag. The out-of-bag predictions can be used to estimate generalization error, without needing a dedicated validation set but based on the aggregated prediction for each observation using trees for which that observation was not included in the training data.
Random Feature Selection
The key innovation in random forests is the random selection of features at each node split. Traditional decision trees optimized by choosing, at every node, the split among all features that best reduces impurity, for example, the Gini impurity for classification or the squared error in regression. In random forests, however, each split considers only a randomly chosen subset of features, often of size about the square root of the total number of features. This forces trees to be structured differently and reduces the correlation among them. Sometimes alternative splits are chosen because some global features might dominate all others, leading to many trees nearly identical trees. By randomly restricting the candidate features, the forest can explore permutations that otherwise might, achieving a more robust prediction.
This random subspace approach was introduced by Ho and later combined with Amit and Geman's node randomization. Breiman's final formulation used random subset selection at each node, but some variants use random selection only before fitting each tree. Modern implementations differ; many libraries support either 'random subspace' or an 'random split' strategy. Commonly the feature dimension d is used, with a subset of size sqrt(d) for classification or d/3 for regression.
Model Behavior and Overfitting Resistance
Random forests are known for their resistance to overfitting. Each tree is deep and may overfit, but the ensemble reduces variance. Unless deeper forests tend to perform better as more trees are added, as long as feature randomization restricts them. This is supported by the theoretical results in Breiman's paper, which shows a bound on generalization error that narrows with better tree strength and lower correlation. However, if the number of trees is too large, the model is not overfitted; the error is approachable as B increases, but it can still be susceptible to noise in the label. If features are not randomly selected, trees may be correlated and offset the advantage. With random feature selection, the forest tends to maintain accuracy even when the complexity of the classifier increases. This is in contrast to increasing depth of a single tree, which leads to overfitting.
For classification, the forest's output is the class with most votes. For regression, the prediction is the average of individual trees, and the standard deviation of tree predictions is a natural estimate of uncertainty.
Practical Uses and Extensions
Random forests are applied in many domains, including remote sensing, bioinformatics, finance, and computer vision. They are robust to irrelevant feature, can handle non-linearities, and produce comprehensibility, but are less interpretable than a single tree. Variable importance metrics allow researchers to identify which features are relevant. Random forests are also used in artificial intelligence, and are a fundamental algorithm in traditional operations a baseline for many modern machine learning tasks, along with deep learning and neural network.
Extensions include extra trees - even more random split thresholds - and using random forest for anomaly detection, ranking, and missing value imputation. They are also used as the building blocks of bagging and ensemble learning in Machine learning pipelines.
Comparison with Other Models
Random forests differ from deep learning-based models such as neural network in that they are interpretable, require less data, and are simpler. They can be trained on CPU while deep neural networks often require accelerators. But they can struggle with high dimensional data, but can balance between bias and error. They are less effective for unstructured data like images and text, where deep learning excels. The trade-off is notable: random forests remain a sturdy benchmark, yet lacking hierarchical representation learning.
At the frontier of modern artificial intelligence research, methods like large language model and Transformer (architecture) based architectures dominate language tasks, but random forests and other tree ensembles are still common in areas like tabular data and explainable AI.
See Also
- machine learning
- artificial intelligence
- decision tree not in available links within the system.
References
The original sources are cited within the article, but no external URLs are relevant.