Grow many decision trees, each on a bootstrap resample of the data and splitting on a random subset of features, then take the majority vote. The randomness decorrelates the trees, so their independent errors cancel — the ensemble beats every single tree even when each tree is mediocre. It is bagging (parallel, variance-reducing), the opposite twin of AdaBoost’s boosting (sequential, bias-reducing).
THE TECHNIQUE three trees that each miss once, vote perfectly
Five samples, three features; each tree is a stump splitting on one feature. Each stump gets one sample wrong — but a different one, because they look at different features. Majority vote (2 of 3) overrules every lone mistake, so the forest is perfect where no single tree is. Watch each stump’s error, then the vote. live demo
HISTORY & CREDIT the name is 2001; the invention is 1995
“Breiman invented random forests in 2001” — he invented named and popularized them; the first algorithm is Tin Kam Ho (1995). cited
1993 · Heath, Kasif & Salzberg — randomized-tree committees combined by majority vote already exist. 1995 · Tin Kam Ho (Bell Labs) coins “random decision forests” and ships the first algorithm — the random subspace method (a random feature subset per tree). 1996 / 1997 · Breiman’s bagging (bootstrap resample + vote — a separate, earlier result, not itself a random forest); Amit & Geman add a random feature subset at each node. 2001 · Leo Breiman’s definitive (single-authored) paper synthesizes bagging + per-node random features on CART trees, adding out-of-bag error and permutation importance. Adele Cutler co-developed the method, the reference Fortran, and the “Random Forests” trademark (2006) — a genuine co-developer routinely erased by the single-name story.
A bagging / variance-reduction method — not boosting; careless writeups conflate the two. Ho 1995 / Breiman & Cutler 2001
RECOMMEND FOR I-13 stumps compare, the forest counts votes
Each tree is a threshold compare; the forest is a majority count over f64 arrays — and it strictly beats every member:
$ i13 run rf.i13 # 5 samples, 3 stumps (rule: value <= 5 -> A else B)
each stump: 4/5 = 80% (each misses a different row)
forest majority vote: A,A,A,B,B -> 5/5 = 100% (outvotes every lone miss)
Recommend:nothing new — a tree’s prediction is a threshold compare x ≤ t; per-class vote tallies are f64 arrays; the forest decision is argmax over the counts (verified each stump 4/5, the majority vote 5/5 — the ensemble strictly beats every member because their errors land on different rows). The stdlib seeded PRNG supplies the bootstrap rows and feature subset, so the whole forest is reproducible under a seed. Note: the real samples × features design matrix is a 2-D array (PS-004) — the same want AdaBoost (dart 118) hits; the two are the campaign’s bagging/boosting pair, and both meet the matrix wall the moment they leave one feature.