Random Forest: Wisdom of an Unruly Crowd of Trees

One tree, too much memory

A decision tree learns by recursively splitting the feature space: at each node it picks the feature and threshold that most reduces impurity in the two resulting groups, usually measured with Gini impurity or entropy. Grown deep enough, a tree can carve out a boundary so specific that every training example ends up in its own leaf — perfect training accuracy, and a model that has essentially memorized the dataset. That is the classic decision-tree failure mode: low bias, very high variance. Change the training set slightly and a deep tree's structure can look completely different, which means its predictions on new data swing wildly depending on which examples happened to be in the training sample.

Bagging: averaging away the noise

Leo Breiman's 1996 idea of bootstrap aggregating, or bagging, is deceptively simple: draw N rows with replacement from the training set (a bootstrap sample), train one full, unpruned tree on it, and repeat this hundreds of times. Because each tree sees a slightly different slice of the data, its individual errors are somewhat independent of the other trees' errors. Averaging predictions from many high-variance but low-bias models cancels out a large share of that variance while barely touching the bias, which is exactly the trade a single tree cannot make on its own. Breiman formalized this further in his 2001 paper "Random Forests," adding the second ingredient that gives the method its name.

Random feature selection: breaking the trees apart

Bagging alone has a weakness: if one feature is a genuinely strong predictor, nearly every bootstrap tree will pick it near the root, so the trees end up structurally similar and their errors stay correlated — averaging correlated models removes far less variance than averaging independent ones. A random forest fixes this by restricting, at every single split, the candidate features to a random subset — commonly the square root of the total feature count for classification, or a third of it for regression. This forces different trees down different paths even when trained on similar data, decorrelating the ensemble and letting the averaging step do much more work.

// growing a random forest of T trees over p features
for t in 1..T:
    sample_t = bootstrap_sample(training_data)     // N rows, drawn with replacement
    tree_t   = grow_tree(sample_t):
        at each node:
            candidates = random_subset_of_features(size = sqrt(p))
            split      = best_split(candidates)     // minimize Gini impurity
            recurse until max_depth or min_leaf_size
    forest.add(tree_t)

predict(x):
    votes = [tree.predict(x) for tree in forest]
    return majority_vote(votes)                     // average(votes) for regression

Out-of-bag error: a validation set built in

Sampling N rows with replacement from N rows leaves out, on average, about 1/e ≈ 36.8% of the original rows for any given bootstrap sample — those rows simply never got picked. Because each tree never saw its own "out-of-bag" rows during training, predicting them with only the subset of trees that excluded them gives an honest, unbiased estimate of test error, without setting aside a separate validation split or running cross-validation. This OOB error is one of random forests' most practical conveniences: it comes essentially for free from the training process itself.

What the forest can tell you about your features

Because every split records which feature it used and how much it reduced impurity, a forest can rank features by mean decrease in impurity — summing each feature's impurity reduction across every split in every tree. A more robust alternative is permutation importance: shuffle one feature's values across the out-of-bag rows and measure how much OOB accuracy drops. A feature the forest actually relies on will hurt accuracy badly when scrambled; a feature it ignores will barely move the needle. Neither method requires refitting the model from scratch.

Tuning the knobs

The number of trees mostly trades compute time for a smoother, more stable OOB error curve — unlike boosting methods, adding more trees to a random forest does not increase overfitting, it just averages over more independent noise. The variance of each individual tree, and therefore how much work the averaging step has to do, is controlled separately through max depth and minimum samples per leaf: shallower trees with larger leaves are individually less accurate but more stable, which can shift the ensemble's sweet spot depending on how noisy the data is.

Frequently asked questions

Try it live

Everything above runs in your browser — open Random Forest Classifier and watch bootstrap sampling, random feature selection and OOB error unfold as the forest grows. Nothing is installed, nothing is uploaded, the whole model lives in one tab.