A single decision tree is twitchy: change a few training points and it can grow a very different shape. A random forest tames that by training a whole crowd of trees and letting them vote. The trick is making the trees *disagree in their mistakes* — because if many independent-ish trees each err in different places, the majority vote washes the errors out.
Two sources of randomness
1Bagging (bootstrap aggregating) — each tree trains on its own bootstrap sample: a random draw of the data, the same size as the original, taken *with replacement*. So some points repeat and (on average) about a third are left out of any given tree.
2Random feature subsets — at each split, a tree may only consider a random subset of the features, not all of them. A common default is √d features for classification (d total).
Why both kinds of randomness
Bagging alone leaves the trees too similar — if one feature is strongly predictive, every tree splits on it first and they all look alike. Restricting the features per split decorrelates the trees, so their errors stop lining up and the vote gets the full benefit of averaging.
Making a prediction
For a new point, every tree predicts independently. For classification, the forest returns the majority vote — the class chosen by the most trees. For regression, it returns the average of the trees' numeric predictions. Suppose 100 trees classify an email and 78 say *spam*, 22 say *not spam*: the forest says spam, and the 78/100 also reads naturally as a confidence.
Free validation: out-of-bag error
Each point was left out of roughly a third of the trees. Predict it using only those trees, and you get an honest accuracy estimate — the out-of-bag (OOB) error — without ever holding out a separate validation set.
OperationTimeSpace
Train · T trees, each a decision tree; trees are independent so training parallelizesO(T · n·d·log n)O(T · n)
Predict · run all T trees, then tally the voteO(T · depth)O(1)
Check yourself
Why does a random forest restrict each split to a random subset of features instead of using bagging alone?
