Bagging

Set the slider in the box above to one member. That is one fully grown tree on the trees page’s tangled crowd, twenty-five people whose middle was built to be nearly noise. It scores 0.920 on the people it trained on, and the regions show how it got there, rectangles fitted around the particular people it happened to receive. Nothing about bagging yet. This is the baseline.

Now change the crowd slightly and grow the tree again. The widget below relabels one person, or grows a tree on each of five random four-fifths of the crowd.

…

One label moved the root question from height to weight, and once the root changes everything under it is decided in different halves. Five samples of the same crowd put their root cuts in five different places. The underlying problem did not change at all. The sample changed a little, and the tree changed a lot.

That sensitivity has a name. A learner whose fitted model swings from one plausible training sample to the next has high variance, in the sense the statistics primer gave the word. The prediction problem is fixed. The sample is one draw from it. A high-variance learner reads too much of the draw into the model, and reads something different from the next draw. Everything on this page is a way of reducing that swing without changing the learner.

There is one crowd of twenty-five. To make one bootstrap sample, draw one person from it, put them back, draw again, and keep going until twenty-five draws have been made. The phrase that matters is with replacement. A person drawn once stays in the pool and can be drawn again.

…

The machine replays the actual draws the first member of the committee made. Draw all twenty-five and the sample has twenty-five rows, some people in it twice or three times, and seven people not in it at all.

Untick the replacement box in the machine and draw again. Without replacement a drawn card stays out, so twenty-five draws reproduce the crowd exactly, every person once. With replacement the same twenty-five draws produce a varied training set of the same size. Replacement is the whole difference, and it is what lets one dataset generate many meaningfully different samples.

What the bootstrap does not do is invent anyone. The crowd is the best available stand-in for the population it came from, and drawing from it with replacement is drawing repeatedly from that stand-in. No new people and no new information, only a rearrangement of how much influence the people already there have.

A bootstrap sample of size n contains n draws and generally fewer than n distinct people. The ones drawn twice or three times influence the tree grown on the sample that many times over, and the ones never drawn influence it not at all. The gallery in section 7 sizes each person by how many times a member drew them, which is the sample as the tree saw it.

For each member, draw a bootstrap sample, grow one ordinary deep tree on it, and keep the tree. Repeat for the next member with a fresh sample. The tree-growing algorithm is the trees page’s, unchanged. All of the diversity comes from the samples.

…

Slide through the members. Their root questions differ, in feature and in threshold, their depths run from three to seven, and their maps carve the tangled middle differently. Twenty of the twenty-five root on height and five on weight, and seven of the twenty-five ask the very same first question, height below 147.5. Bootstrap variation makes different trees learn different questions and regions, and section 27 is about how different they manage to be.

To classify one person, ask every tree and count.

ŷ = mode(ŷ₁, ŷ₂, …, ŷ_B)

B is the number of members. A bagged classifier predicts by aggregating its members’ decisions, and voting is one way to aggregate. Averaging the members’ class probabilities and taking the largest is another, and it is the one used here, which matters for ties.

ŷ_bagged = (1/B) Σ_β ŷ_β

When the members predict numbers the aggregate is their mean. Classification votes or averages probabilities, regression averages predictions, and both are the same act of pooling B answers into one.

At one member the ensemble is that member, one tree on one sample, and no averaging has happened. Add members and every cell of the plane gains a vote.

…

The left map changes a great deal in the first few members, 24 cells flipping between three and four, and settles as more arrive, with long runs of zero changed cells past twenty. The training score reaches 1.000 by eight members and stays near it. The out-of-bag score, which Part 7 explains, lands around 0.64, because the tangled middle is nearly noise and a committee cannot learn what is not there.

Two cells can both be called adult with fifty-one percent of the members on one and ninety-eight percent on the other. The right map draws that difference, pale where the vote was close and dark where it was nearly unanimous. Move the probe into the tangled middle and the winner is a coin toss with the paint to match. Move it to the corners and the committee is unanimous.

The winning class and the strength of agreement are two outputs, and the second is not a calibrated probability. A vote share of 0.98 means twenty-four or twenty-five trees agreed, and whether people in that cell are adults ninety-eight percent of the time is a separate question, answered only by data the committee never saw.

Choose one person from a crowd of n. Sampling with replacement gives them the same chance of selection on every draw.

P(selected on one draw) = 1/n
P(omitted on one draw) = 1 − 1/n

Because the draws are independent, multiply the omission probability once for each draw to find the chance of never selecting that person.

P(left out) = (1 − 1/n)ⁿ

n = 25:   (24/25)²⁵ ≈ 0.360
n → ∞:    (1 − 1/n)ⁿ → 1/e ≈ 0.368

The curve settles onto 1/e almost at once, so about 36.8 percent is the figure whatever the crowd’s size, and about 63.2 percent of the crowd appears at least once in a typical sample. It is an expected proportion, and no single sample is obliged to hit it.

expected omitted  = n (1 − 1/n)ⁿ = 25 × 0.360 ≈ 9.0
expected distinct = 25 − 9.0 ≈ 16.0

A bootstrap sample of twenty-five typically holds around sixteen distinct people and omits around nine. Across the twenty-five members of the committee the actual omitted counts run from 7 to 12, and the histogram in section 7 shows them scattered around the expected 9. A person who appears twice still counts once as distinct.

Start with numbers rather than trees. Suppose B members each estimate one quantity, each with variance σ² and with errors independent of each other.

m̄ = (1/B) Σ_β m_β
Var(m̄) = σ² / B

Four independent members cut the variance to a quarter, a hundred to a hundredth, and the spread of the average falls as one over the square root of B. Each new estimate scatters as widely as the first. Their average does not, because positive and negative errors partly cancel, and that cancelling is all that averaging does.

A vote is a number in disguise. For one class, write each tree’s vote as one if the tree predicted that class and zero if not.

v̄ = (1/B) Σ_β v_β   =   the share of trees voting for the class

The mean vote is the share, and the committee picks the class with the largest share. Majority voting is averaging zero-and-one indicators and selecting the largest average, so section 15 applies to it, with one large caveat, which is the next section.

Bagged trees are not independent. They come from one dataset, their samples overlap by about two thirds, the same strong feature dominates most of their roots, and so they tend to learn similar boundaries and make similar mistakes. With a common variance σ² and a common pairwise correlation ρ the variance of the average is

Var(ensemble mean) = ρσ² + (1 − ρ)σ² / B

Two terms. The second is the reducible part, and it goes to zero as B grows. The first is the shared part, and B never touches it. Adding members averages away the variation the members do not share, and cannot average away a mistake they all make together.

At ρ near zero the curve falls like σ²/B and keeps falling. At ρ of 0.6 it drops to the floor within a dozen members and then goes flat, with sixty percent of a single member’s variance left however many are added. That floor is the reason bagging plateaus, and lowering it is the whole idea of the random forest.

Every person was left out of about a third of the samples, so for every person there stands a group of members that never trained on them. The grid below is who saw whom.

…

Click a row. The filled cells are the trees that drew that person, and the empty cells, lit green, are the trees that did not. Only the green trees may judge that person out of bag, because to every other tree they are a training example.

For person i, find the trees that omitted i, ask each for a prediction, aggregate only those, and compare with i’s known label.

OOB prediction for i = aggregate over trees β with i ∉ sample β

The panel beside the grid gives both verdicts. The whole committee’s vote includes trees that trained on the person and so tends to get them right, since a deep tree remembers its own sample. The judges’ vote is what the committee would say about a stranger. On this crowd the two verdicts differ for eight of the twenty-five people, every one of them in the tangled middle.

OOB accuracy = correct OOB predictions / people with at least one judge

Repeat for everyone who has a judge and divide. Different people are judged by different subsets of trees, which is unlike a held-out set where one model is judged by every held-out row, and the score is an estimate assembled from twenty-five partial ones. On the full committee it reads 0.64 against a training score of 0.96, and the gap is the truth about this crowd rather than a fault in the method.

With one member, only the people that member omitted have a judge, seven of the twenty-five here, and the score is seven verdicts. Coverage reaches all twenty-five at seven members. Even then, a person’s judges number between three and thirteen on this committee, so an out-of-bag verdict can rest on three votes.

Out-of-bag evaluation reuses the training data efficiently, and it obeys the same rules as every other evaluation. It stops being untouched evidence when hyperparameters are chosen by it repeatedly, since it is then part of the selection and no longer a judge of it. It leaks when features were selected or preprocessing was fitted on the whole crowd, because the judges then know something about the person from a step upstream of the bootstrap.

It misleads when the observations are dependent, ordered in time, or grouped, so that ordinary resampling breaks a structure the data has. And it is unstable when the committee is too small to cover everyone well.

Bagging is at its best when the base learner can express the pattern and estimates it unstably. A deep tree can draw any rectangle the tangled crowd needs, and draws different ones from different samples. The scrubber in section 11 shows the individual members disagreeing in the middle and the vote settling on the stable regions, which is variance being averaged away.

Now bag members that cannot express the pattern. The right committee below is twenty-five stumps, trees allowed one question each.

…

The stumps score 0.72 on the training crowd however many there are, because every one of them cuts the plane once and the crowd needs a second cut. They make the same structural mistake, and voting among members that all lack the same thing does not supply it. Aggregation reduces variance. It does not reduce bias, and it cannot recover structure that every member is too restricted to represent.

Nor does it repair the data. Labels that are wrong in the crowd are wrong in every resample. A feature that is missing is missing from every tree. A crowd sampled badly, a target that does not mean what it should, a leak between training and evaluation, or a shift between the crowd and the people the model will meet, all of these pass through the bootstrap untouched. Bagging reduces model variance and nothing else.

Read the changed-cells readout in section 11 as the members are added. Early members change the map by dozens of cells at a time. Past about twenty the count is mostly zero, with the odd flip of eleven cells when a tree breaks a near tie. The training score settled by eight members and the out-of-bag score by about the same. Every further member costs another tree to grow and to consult and buys stability more than accuracy. Additional trees eventually stabilise the ensemble more than they improve it.

The reason is section 17’s floor, and the gallery in section 7 shows where the floor comes from. Twenty of the twenty-five members root on height and five on weight, and seven ask exactly the same first question. The samples differ, and the strong feature still wins most of the time, so the trees start alike and their errors stay correlated. Bootstrap resampling creates diversity, and a strong predictor can keep the trees correlated regardless.

Bagging varies which people each tree sees. The random forest also varies which features each split is allowed to consider, so that height is sometimes off the table and a tree has to root on weight whether it wanted to or not. A strong feature cannot dominate every split when it is sometimes unavailable, the trees become less alike, ρ falls, and the floor in section 18 drops. That is not free. Restricting the features weakens each individual tree, and the trade is the forest page’s subject.

Nothing in the recipe mentions a tree. Draw B bootstrap samples, fit one model to each, aggregate their predictions. Any learner that can be fitted to a sample can be a member, and the aggregate is a vote or an average of probabilities for a classifier and a mean for a regressor, as section 10 said.

What the recipe needs from its learner is three things, and this page has already shown all three on the deep tree. It has to be sensitive to its training data, which is Part 1, where one relabelled person moved the root question from height to weight. It has to be able to reach low bias, which is Part 4, where the committee’s training score reaches 1.000 by eight members because every member can draw whatever rectangles its sample asks for. And it has to produce meaningfully different fits from different resamples, which is the gallery in section 7, where the twenty members that root on height do so at ten different thresholds between 144 and 158, and the five on weight at three. That is a description of a deep tree and of little else on this site.

A learner that is already stable, a straight line say, gives nearly the same fit on every resample, and a committee of nearly identical members gains nothing from the vote. Section 17’s formula says why. Members that agree have a correlation ρ near one, so the floor ρσ² is nearly the whole variance and the part that B removes is nearly nothing. Bagging is a general method whose canonical case is the one that made it worth inventing.

A complete implementation states its settings and its edge cases, and the ones that matter here are these.

P(both missed by one sample) = (1 − 2/30)³⁰ ≈ 0.126
P(some member of 25 misses the class) = 1 − (1 − 0.126)²⁵ ≈ 0.966

Two rows of the table are about what the committee refuses to pretend. A person no member omitted has no judge, and their out-of-bag entry is left empty and counted as uncovered rather than filled with a zero, because a zero is a number a later average would quietly include. On this committee nobody is uncovered, since coverage reached all twenty-five at seven members, but at five members five of the twenty-five still had no judge, and a score assembled then rests on the other twenty. And a crowd holding one class is refused before any sample is drawn, since twenty-five copies of a tree that can only answer one way have nothing to vote on.