Random Forests

Here is where the bagging page left the tangled crowd. The resamples gave the trees different people to learn from, the fitted trees became more varied than one tree refitted on nudged data, and the vote steadied the map. But 20 of the 25 trees still opened with a question about height, and across every pair of members the two agreed on 72.4 percent of the people neither had seen. The committee is more varied than one tree and still largely of one mind.

The reason is not mysterious. At the root of any of these trees two candidates compete, the best question height can ask and the best question weight can ask, and the tree takes whichever earns the larger impurity reduction on the rows it was given. Change the rows and both gains change. Whether the winner changes depends on how far apart they were.

…

Eight resamples, eight different boards, and height takes the root on five of them, usually at the same threshold of 147.5 centimetres. On the full committee it is 20 of 25. The samples vary the rows, and a feature that is consistently the strongest keeps winning anyway, so resampling alone cannot stop most trees from asking the same first question.

Before changing anything it is worth separating three ideas that the word similar runs together, because the forest is judged on the third and the census only shows the first.

These are related and not the same. Two trees can open on different features and still draw nearly the same map, because the second question repairs what the first one missed. Two trees can open on the same feature at different thresholds and diverge from there. On the bagged committee the three numbers are 20 of 25 roots on height, an agreement of 0.724, and an error correlation of 0.463, each measured over every pair of members on the people both members had left out.

At one node an ordinary tree lays out every feature it has, generates the candidate thresholds for each, scores every candidate by the impurity it would remove, and takes the best of the whole board. On the tangled crowd the root board has two rows.

The ordinary tree sees both rows and picks height, and it would pick height at this node every time, because the board does not change when nothing about the rows changes.

The forest adds one step before the search. Draw a random subset of the features, hide the rest, and search only the subset. The tree still chooses the best available split by exactly the same scoring; what changed is which splits were available to choose from.

…

With one feature offered per split, half the draws offer weight alone, and at those nodes the tree settles for the weaker question with the stronger one sitting hidden on the board. The draws made inside a grown tree are not recorded anywhere, so the draws above replay the rule from a seeded generator rather than recount a particular tree. What they show is the rule itself.

The subset is redrawn at every split, not chosen once for the tree. The root gets a draw, then the left child gets its own, then the right child, and so on down every branch that is still eligible to split. A tree denied height at the root can be offered it one level down and take it there, and a tree that opened on height can be denied it at the very next node.

Write p for the number of features and m for how many each split is offered. The setting goes by max_features in most implementations and mtry in the original one.

On the tangled crowd p is 2, so the only forest possible is m = 1, and each feature is offered at any given split with probability one half. The committee at the top of the page is that forest, the bagging page’s scrubber with the lottery switched on, refitted at every size from one member to twenty-five.

The cleanest way to see what the lottery does is to take the bootstrap out of the picture. Hold one resample fixed, grow several trees on exactly those rows, and vary only the seed of the feature lottery. Whatever differs between the trees was caused by the permissions and by nothing else.

…

The shared sample holds 18 distinct people and omits 7. A tree offered both features roots on height. Under lottery seed 1 the forest tree also roots on height, at 147.5, and finishes at depth 4 with 7 leaves; under seeds 2, 3 and 4 it roots on weight less than 41.5 and grows deeper. The first two trees agree on 88 percent of the crowd, 22 of the 25 people, from identical training rows.

Now the whole comparison, with everything held fixed that can be. Same crowd, same seed, so the same 25 bootstrap samples in the same order, same tree settings. Bagging offers every split both features; the forest offers one.

…

Read the two columns against each other. The roots spread from 20 and 5 to 8 and 17, which is structural diversity and the easy part. The prediction agreement barely moves, 0.724 against 0.731, and the error correlation goes the wrong way, 0.463 against 0.517. The members got weaker, from a mean out-of-bag strength of 0.641 to 0.572, and the committee’s own out-of-bag score fell from 0.64 to 0.52. On this crowd, under this seed, the lottery rearranged the trees without making their mistakes less shared, and paid for it in strength.

The census is the most visible readout and the easiest to over-read. It shows how often each feature was chosen at the root, whether one feature dominated the first question, and whether the restriction forced alternative openings. It does not show whether the trees make different predictions, whether their errors are less correlated, or whether the committee is more accurate. The dashboard above is the case in point, since the census changed a great deal and the agreement hardly changed at all.

When a different root does matter, it matters because of what follows it. The first split decides which people reach each child, and every later node searches only the rows it was sent, so a different first question changes every board below it. The two trees here are the seed 1 and seed 2 trees from section 6, grown on the whole crowd with one feature per split, stepped in lockstep.

…

Tree A opens on height and finishes at 8 splits and 9 leaves. Tree B opens on weight and needs 9 splits and 10 leaves to reach a worse fit. The strongly coloured cells are where the two partitions disagree at each step, and they appear from the first split and never fully close.

Strength needs a working definition rather than a mood. A tree is stronger when it predicts better on people it did not fit, and every member has such people ready made, the ones its own resample omitted. The member strengths on the dashboard are each tree’s accuracy on its own out-of-bag rows.

Restriction may weaken a tree for three reasons. Its strongest feature may be unavailable at a node, it may take a weaker split there, and it may need more questions to recover a pattern one question would have captured. It is not guaranteed to weaken a tree, since an alternative feature can sometimes generalise better than the one the training rows preferred, which is why the number is measured. Here it fell by 0.07.

Take any two members and the people both of them left out. Each person lands in one of four cells, both trees right, only the first right, only the second right, both wrong. Agreement is the share in the two cells where the trees said the same thing, and error correlation is the ordinary correlation between the two columns of right-or-wrong indicators, which is high when the both-wrong cell is fuller than the two trees’ separate error rates would predict.

The dashboard averages both over every pair that has a defined value. On this crowd the forest’s error correlation is 0.517 against bagging’s 0.463, so the lottery did not buy the thing it was meant to buy.

So the forest is a bet, made with open eyes. It accepts a possible loss of individual strength in exchange for a possible drop in correlation, and the committee improves only if the second is worth more than the first.

On two features the sweep over m has two points, and they are the two columns of the dashboard. Everything the trade involves is in one table.

Section 19 runs the same sweep on data with six features, where m has room to move and the answer changes with the data.

With height and weight only, m = 1 is the harshest restriction the rule can impose. Every node loses half of everything it has, and the two halves are not equal. At the root of the whole crowd the best height question earns 0.188 and the best weight question 0.103, so a node offered weight alone cannot compare it with anything and takes a question worth just over half as much.

Section 5’s lottery counts how often the strongest feature was denied, and at m = 1 it was withheld in 8 of the 12 draws shown, about what a coin should manage.

The census and the scores are both worth reading for what they support and no further.

The forest’s roots are more evenly spread across the two features, and that much is directly supported. The particular 8 to 17 split is random variation under this run, not a finding that weight became the better predictor, since height was denied at half the roots by the coin rather than by the data. And under this dataset, this configuration, 25 trees and this random draw, the forest scored worse.

The restriction appears to have cost more strength than it recovered through lower correlation, and section 13 showed the correlation did not fall at all. What this one result does not establish is that bagging is generally better on two-feature problems, and 25 trees is few enough that a different seed could tell a different story.

So run the seeds.

…

Across eight seeds the forest beats bagging on one, seed 1, where bagging happened to draw a poor set of samples, and the mean difference is 0.06 in bagging’s favour. The census, meanwhile, is steady in a way the one run could not show. Bagging opens on height in 16 to 23 of 25 trees at every seed, and the forest in 7 to 9, which is the coin doing what a coin does. The one run was a fair sample of the procedure after all, and it took eight runs to know that.

Now give the rule room. Two simulated worlds share the same 120 people and the same six measurements, and differ only in where the signal that decides the label lives. In the sparse world one feature carries all of it and the other five are noise, so withholding that feature leaves a node with nothing worth asking. In the shared world all six features carry an equal part of it, so whichever features a node is offered, something useful is on the board.

…

The same restriction does two different things. In the sparse world the members lose strength fast as m falls, from 0.932 at m = 6 to 0.757 at m = 1, because a node offered only noise columns asks a useless question. Their errors become far less shared at the same time, the correlation falling from 0.694 to 0.141, and the two effects cancel almost exactly, so the committee’s score sits between 0.933 and 0.95 at every m and the restriction is close to free.

In the shared world no feature is much better than another, so restriction costs almost no strength, 0.68 to 0.69 at every m, while the correlation still falls, 0.205 to 0.117, and the committee gains, from 0.75 at m = 6 to 0.80 at m = 1 and 0.817 at m = 2.

Put the three measured cases side by side. On the tangled crowd the restriction cost 0.12. In the sparse world it cost nothing to speak of. In the shared world it gained 0.05 to 0.07. A fourth arrangement, three noisy copies of one feature beside three noise columns, was measured at 25 members and lost 0.06 at m = 1, which is the world the phrase redundant features usually brings to mind, and at a committee size section 18 has already shown to be unstable.

What decided each case was whether a node denied its best feature was offered something nearly as good.

Nor does a large feature count guarantee useful alternatives. Hundreds of mostly irrelevant columns make a small subset weak in the way the sparse world is weak, only more so. What the right m depends on is the number of features, how many of them carry signal, how much they overlap, the sample size, the tree settings and the task, which is a list to evaluate over rather than a rule to remember. Random forests benefit from useful alternative features, not from a long feature list as such.

At every location each tree predicts a class, the votes are counted, and the larger count is the answer. The winning share is a separate number, and the scrubber at the top of the page draws the two apart, the majority on the left and how firmly the members agree on the right. Two cells can be painted the same class with the forest nearly unanimous in one and split 13 to 12 in the other, and the left map cannot tell them apart.

The lottery changes individual trees, and through them the committee’s final regions. The map below is blank wherever bagging and the forest agree and coloured only where they do not, in the forest’s colour, with the probe reporting each committee’s vote as a count of members.

…

The bagging page’s formula is the right instrument for thinking about this trade, with its assumptions stated. Take B numeric predictions with a common variance σ², a common pairwise correlation ρ, and equal weights in the average. Then

Var(committee) = ρσ² + (1 − ρ)·σ²/B

Let B grow without bound and the second term vanishes, leaving ρσ². More trees shrink the part of the variance the members do not share and leave the part they do untouched, so a committee approaches a floor set by its correlation rather than approaching zero. Lowering ρ lowers the floor, which is the one lever the forest is pulling.

Restriction reaches into both symbols at once. A member denied its best question fits its resample worse and less stably, which raises σ². Members denied it at different moments stop opening the same way and can make less similar predictions, which lowers ρ. The committee benefits only if the combined result is lower, and at any finite B both terms are in play, so it is not enough to ask whether ρσ² fell.

Compare three hypothetical committees of twenty-five trees. Each calculation has a shared-error contribution that averaging cannot remove and a remaining contribution divided by the committee size.

bagging, σ² = 1.0 and ρ = 0.5:
  variance = 0.5 + 0.5 / 25 = 0.52

forest A, σ² = 1.2 and ρ = 0.25:
  variance = 0.3 + 0.9 / 25 = 0.336

forest B, σ² = 1.6 and ρ = 0.45:
  variance = 0.72 + 0.88 / 25 = 0.7552

Forest A’s reduced correlation more than pays for its noisier members. Forest B loses too much individual accuracy for its smaller reduction in correlation. Use the calculator to find where the trade changes sign.

Treat m as a model setting like any other. Small m means more restriction, potentially more diversity and potentially weaker splits. Large m means a stronger choice at each node, potentially more similar trees, and at m = p it is bagging. The conventional defaults, the square root of p for classification and a third of p for regression, are starting points that a dataset is under no obligation to respect.

Since out-of-bag evaluation is taught elsewhere, the procedure is short. Fit forests at several candidate values of m, compare their out-of-bag scores, look at how much those scores move across seeds before trusting a small difference, and choose by the evaluation procedure the search page lays out. Section 19 is that sweep on two worlds, and section 18 is the seed check on one crowd.

The lottery defines the forest, and it is not the only setting that decides how the forest behaves. The number of trees, the maximum depth, the minimum rows to split and to leave, the size of the bootstrap sample and whether bootstrapping is on at all, any class weighting, the split criterion and the random seed all carry over from bagging and from the tree, and a forest inherits every one of their consequences. Some implementations allow the bootstrap to be switched off, leaving the feature lottery as the only source of randomness.

A fitted forest can be asked three different questions about a feature. Which features were used often, which produced large impurity reductions, and which most affect predictive performance. These can produce different rankings, and the feature-importance page measures where they part. The first measure adds up, over every split in every tree, the weighted impurity reduction the feature produced, and normalises the totals to shares.

The third question is answered by breaking a feature and watching what happens. Measure the baseline score, shuffle one feature’s column so it keeps its distribution and loses its relationship with the label, measure again, and read the drop as reliance on that feature. It should be computed on evaluation rows, and the out-of-bag rows serve when an implementation supports it.

One tree can sometimes be read as a flowchart, and the decision-tree page reads one. A forest of hundreds of trees holds thousands of branches, and a single person takes a different path through every tree, so the committee is not readable as one compact set of rules. The trees in section 8 are four readable flowcharts; the committee in section 9 is 25 of them voting, and the map is the only summary of it that fits on a page.

A forest does not repair data problems. Biased sampling, wrong labels, leakage, missing predictive information, a shift in the population between fitting and use, an inappropriate target, unequal costs of the two mistakes and poorly calibrated vote shares all pass straight through the vote, since every member learned from the same flawed rows.

Far from the data, the forest keeps answering. A regression forest assembles its answer from training targets in the leaves, so it cannot follow a trend past the range it saw the way a line can. A classification forest lets the outermost regions of every tree extend to infinity, so a query far outside the crowd inherits whichever leaf its ray ends in.

A complete implementation states its configuration in full. The number of trees, whether bootstrapping is on and how large a sample is, the number or fraction of features per split and how they are drawn, the base tree’s depth and minimum split and leaf sizes, the split criterion, whether the vote is hard or averages probabilities, how ties break, any class weighting, how the seed is shared among members, whether members fit in parallel, and whether out-of-bag evaluation is offered.

Several of those were measured on this crowd. A single-class target is refused with a named error, and so is a crowd of one person, since one row is one class. A max_features of zero is refused when the forest is constructed, before any data is seen, because a lottery that offers nothing cannot be run. Asking for three features of two is accepted and offers both, and what comes back under seed 7 is the bagged committee exactly, the same 20 and 5 roots, the same 0.96 on the training crowd and the same 0.64 out of bag, with every member answering as its bagged twin does. Nothing is drawn when every feature is already on the board, and the bootstrap samples come from the same seed, so there is nothing left to differ.

The seeding row is the one the bagging page recorded being got wrong. A committee that handed every member its own single seed made every tree draw the same features at every node, which is bagging wearing a forest’s name, and the census was what caught it, since twenty trees that all rooted on the same feature are not a lottery. Each member’s lottery is seeded from the committee’s seed and its own position, so two members never share a draw, and a refit under the same seed reproduces every draw. That is also why a forest refuses a base tree handed to it. The restriction is a setting on the tree, and a tree handed in already configured would carry its own seed into every member, which is the fault by another route.