Random Forest in machine learning

Module 01 · Machine Learning · 55 concepts

In depth / 15 lines

Random Forest, in more detail

A random forest is many trees that vote.

Each tree sees a random sample of the rows, drawn with replacement.

Each split also considers only a random subset of the features.

That double randomness is the whole trick.

Without it every tree would look alike and voting would gain nothing.

On their own the trees are mediocre and unstable.

Averaged together, their random errors largely cancel out.

It is remarkably hard to make it perform badly.

The defaults usually work, which is rare and very useful.

More trees never makes it worse, only slower.

It copes with messy tabular data with little preparation.

It tells you which features mattered, though that ranking can mislead.

Features that move together share the credit and can both look unimportant.

You lose the readable flowchart, since nobody reads five hundred trees.

It is the sensible first thing to try on tabular data, before anything fancier.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath Random Forest

The variance a single tree cannot lose

Averaging $B$ independent estimators each with variance $\sigma^2$ divides the variance by $B$ , and that is the whole idea a forest is built on.

\mathrm{Var}\left( \frac{1}{B} \sum_{b=1}^{B} T_b \right) = \rho \sigma^2 + \frac{1 - \rho}{B} \sigma^2

$B$ : the number of trees.
$\sigma^2$ : the variance of one tree.
$\rho$ : the correlation between two trees in the forest.

The second term vanishes as you add trees. The first does not, and it is $\rho$ that sets the floor.

So a forest is not built by growing more trees. It is built by making the trees disagree.

The two sources of disagreement

P(\text{a given sample is left out}) = \left(1 - \frac{1}{n}\right)^{n} \xrightarrow[n \to \infty]{} e^{-1} \approx 0.368

Bagging gives each tree a bootstrap sample drawn with replacement, so each tree sees about 63 percent of the data and misses the rest.

m = \lfloor \sqrt{d} \rfloor

Feature subsampling is the stronger one: at every split each tree may only consider $m$ features out of $d$ , chosen at random.

Without it one dominant feature is picked first by every tree and $\rho$ stays high, which is exactly what bagging alone fails to fix.

One forest, in order

Draw a bootstrap sample of size $n$ from the training set.
Grow a tree on it, choosing $m$ random features at each split.
Grow that tree deep, with no pruning.
Repeat for all $B$ trees.
Predict by majority vote across trees, or by averaging for regression.

The error estimate that costs nothing

Each sample was left out of about a third of the trees, so those trees can predict it as though it were unseen.

\mathrm{OOB} = \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\big[ \hat{y}_i^{\,\mathrm{oob}} \neq y_i \big]

The out-of-bag error is a validation score obtained from the training run itself, close to what k-fold cross-validation would report, at no extra cost.

Why individual trees are left unpruned

A single deep tree overfits because its variance is high, and variance is the one thing averaging removes.

Pruning would lower each tree's variance and raise its bias, and bias is what averaging cannot touch.

So the forest takes low-bias, high-variance trees on purpose and spends the averaging on the half of the problem it can solve.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

Why does each split in a random forest see only a random subset of features?

Machine Learning

55 concepts in this module, then a graded test with every answer explained.

Study this module →