Averaging Many Trees

Last timeOne Tree Is Unstable

Growing hundreds of trees on resampled data, with the questions at each split drawn from a random handful of inputs, and averaging them removes the instability without making the model any more wrong.

Many trees, deliberately different

The previous lesson ended with a fact: averaging models that disagree reduces

the part of the error that comes from sensitivity to the sample, and the more

they disagree the more it reduces.

Trees disagree readily, which is their defect and now their qualification. The

method in this lesson builds hundreds of them, makes sure they disagree, and

averages. It is called a forest, it takes about thirty lines, and on ordinary

table shaped data it is very hard to beat.

Two devices make the trees differ.

Giving each tree different data

The first device is to grow each tree on a resample. Draw n rows from the n

available, with replacement, so some rows appear twice or three times and

others not at all. Grow a tree on that. Draw again for the next tree.

How many rows does a resample miss? Each draw misses a particular row with

chance one minus one over n, and there are n draws.

FIG 1The chance a row is left out of a resample

: how many rows the data has, and how many are drawn
: the limit this approaches, which it is already close to by n of twenty

About thirty seven percent of the rows are missing from any given resample, whatever the size of the data. That is a large difference between one tree training set and the next, which is what makes the trees differ, and those missing rows are also the free score at the end of this lesson.

FIG 2How quickly the left out fraction settles

the exact fractionthe limit

The curve is already within a percentage point of the limit by twenty rows, so a third left out is a safe statement at any realistic size. The fraction does not depend on how many trees there are, only on how the resample is drawn.

Forcing the trees to differ more

Resampling alone is not enough, and the reason is specific.

Suppose one input is much stronger than the others. Every resample still

contains it, so every tree splits on it first, and the trees come out

similar near the top where the structure matters most. Similar trees have

correlated errors, correlated errors do not cancel, and the averaging buys

much less than it should.

So the second device hides inputs. At each split, consider only a random

handful of the inputs rather than all of them. The strong input is unavailable

at most splits, so other trees find other structure, and the committee ends

up genuinely varied.

The lesson stops here

6 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents