Random Forest

A random forest trains many decision trees, each on a slightly different version of the data, and averages their votes. Individual trees are noisy, but their errors largely cancel out.

The idea

Ask one person to guess the number of sweets in a jar and they may be way off. Ask a hundred people and average the guesses, and you are usually close. That only works if people make different mistakes.

A forest forces its trees to disagree in two ways. Each tree may see a random resample of the data, and at each split it is only allowed to consider one randomly chosen feature (xx or yy). Diverse trees, averaged, give a steadier answer than any one of them.

How it learns

  1. For each tree, draw a bootstrap sample: nn points picked with replacement.
  2. Grow a decision tree on that sample using Gini impurity.
  3. At every split, pick xx or yy at random and find the best cut on that feature only.
  4. Repeat for the chosen number of trees.
  5. To predict, average the class probabilities from all trees.

Reading the picture

The background blends the votes of every tree. Strong colour means the trees agree; pale bands show where they split their votes. The boundary is still built from axis-aligned pieces, but it is far smoother than a single tree's.

With Bootstrap samples on, about a third of the points are left out of each tree. Out-of-bag accuracy scores each point using only the trees that never saw it, which gives a fair test score for free.

Try this

  1. On Moons, set Number of trees to 1. You see one jagged tree. Slide it up to 60 and watch the boundary smooth out.
  2. Compare Training accuracy with Out-of-bag accuracy. Training is near perfect; out-of-bag tells you what to actually expect.
  3. Turn off Bootstrap samples. Trees now differ only in their random feature choices, so they agree more and the shading becomes harder-edged.
  4. Try Spiral with Max depth 12. Forests can follow complex shapes that would make a single tree overfit badly.

The maths

Bootstrap

Dt=n draws with replacement from DD_t = n \text{ draws with replacement from } D

Left out

P(point∉Dt)=(1−1n)n≈1e≈37%P(\text{point} \notin D_t) = \left(1 - \frac{1}{n}\right)^n \approx \frac{1}{e} \approx 37\%

Prediction

P(k∣x)=1T∑tPt(k∣x)P(k \mid x) = \frac{1}{T}\sum_t P_t(k \mid x)

Out-of-bag

score xi with only the trees where xi∉Dt\text{score } x_i \text{ with only the trees where } x_i \notin D_t

Strengths and weaknesses

Good at

  • Accurate out of the box with little tuning.
  • Hard to overfit by adding more trees.
  • Out-of-bag accuracy gives built-in validation.

Struggles with

  • Loses the readability of a single tree.
  • Many trees cost memory and prediction time.
  • Boundaries remain axis-aligned underneath.