Random forests, visually

> fit <- randomForest(churned ~ ., data = train)
> fit
        Type of random forest: classification
                     Number of trees: 500
No. of variables tried at each split: 4

        OOB estimate of  error rate: 12.1%

That’s from a churn model I’ve been playing with on an anonymized copy of some of our own data, 17 features, a few thousand accounts. A single decision tree on the same data got 100% on the training set and 81% on the held-out test set, which is the classic sign of a model that memorized its homework. The forest above, with every setting left at its default, got 88% on the same test set. I hadn’t tuned anything. I’d typed one line.

I’ve been doing a lot of this kind of thing in R for the data science certificate, and random forests are the model where I was most uncomfortable with how well it worked compared to how little I understood it. Why would 500 bad trees beat one bad tree? So I sat down and worked through it, and it turns out the answer is a nice bit of probability that you can draw.

Trees are high variance

A decision tree splits the data again and again, each time picking the feature and threshold that best separates the classes, until the leaves are pure or tiny. That makes it extremely flexible, and it makes it unstable. Change a handful of rows in the training set and the first split can change, and everything below it changes with it. In the language of the bias-variance tradeoff, a deep tree has low bias (it can fit nearly anything) and very high variance (what it fits depends a lot on exactly which data it saw).

High variance is the kind of error averaging is good at. If you could train a hundred trees on a hundred independent training sets and average their predictions, the noise in each would partly cancel. You don’t have a hundred training sets, of course. You have one.

The bootstrap

So you fake it. Take your n rows and draw n rows from them with replacement. Some rows get picked twice or three times, some don’t get picked at all, and the result is a new training set the same size as the original that’s a bit different from it. That’s a bootstrap sample. Draw 500 of them and you’ve got 500 slightly different training sets, all from the same data.

How different? The chance that a particular row isn’t picked in one draw is 1 − 1/n, so the chance it’s missed in all n draws is (1 − 1/n)ⁿ. As n grows that goes to 1/e, about 0.368. So each bootstrap sample contains about 63% of your distinct rows and leaves out the other 37%. This is one of my favorite limits from undergrad, and I was pleased to meet it again somewhere useful.

Train one tree on each bootstrap sample and let them vote (or average, for regression), and you have bagging, short for bootstrap aggregating, which Leo Breiman published in 1996.

Why averaging works, and where it stops working

The math that made it click for me is short. If you average B independent predictions that each have variance σ², the average has variance σ²/B. More trees, less noise, all the way down to zero.

But the trees aren’t independent. They were all trained on resamples of the same data, so they tend to make the same mistakes. If each pair of trees has correlation ρ, the variance of their average is

ρσ² + (1 − ρ)σ²/B

The second term shrinks as you add trees. The first one doesn’t. No matter how many trees you add, you never get below ρσ². With ρ = 0.5 and 100 trees, you’re at 0.5 + 0.005 = 0.505σ², and the next 400 trees buy you almost nothing. With ρ = 0.1 and 100 trees you’re at 0.1 + 0.009 = 0.109σ², nearly five times lower:

(The ρ values here are made up for illustration. The real correlation depends on the data, and you never compute it directly.)

So once you have enough trees, the only way to keep improving is to make the trees less alike.

The random part

That’s what Breiman’s random forests (2001) add on top of bagging. At every split, each tree is only allowed to consider a random subset of the features, a fresh subset each time. In R’s randomForest the default for classification is √p features per split, rounded down, which is where the “variables tried at each split: 4” in my output above comes from (17 features, √17 ≈ 4.1). For regression the default is p/3.

This sounds like it should make each tree worse, and it does. But think about what happens with plain bagging when one feature is a much stronger predictor than the rest. In my churn data that’s days since last login. Every single bagged tree picks it for the first split, so every tree has the same top half, and they’re all highly correlated. Hide that feature from a split most of the time and the other features get a chance to shape the tree. The trees get individually a bit weaker and collectively much more different, and per the formula above, that’s a trade worth making.

The thing I like about this is how unintuitive it is. Deliberately making each component worse to make the whole better is not how I’d design anything in software. I’d normally be suspicious of a technique whose explanation needs the word “decorrelate”, but the math is right there.

The free test set

Remember the 37% of rows each tree didn’t see? Breiman noticed that you can use those. For each row, collect predictions only from the trees that didn’t train on it (about a third of the forest), and see whether they get it right. Do that for every row and you get the out-of-bag error, which is that 12.1% in the output at the top. It’s an honest estimate of test error that you get for free, without holding out any data and without cross-validation. In my case it was close to the 12% error on the separate test set, which is what you’d hope.

You can also use the out-of-bag rows to ask which features matter. Shuffle one feature’s values among the OOB rows, breaking its relationship with the outcome, and see how much the accuracy drops. A big drop means the forest was relying on it. importance(fit) and varImpPlot(fit) give you this, and on my data it confirmed what everyone at work already believed about logins, plus a surprise about support tickets that I’m still thinking about.

What it’s bad at

A few things I’ve run into, or read about and then run into.

It can’t extrapolate. A regression forest predicts averages of training values, so it will never predict a number outside the range it saw. If your target trends upward over time, a forest trained on last year will cap out at last year’s highest value.

It’s a black box, mostly. Variable importance tells you which features matter, not how. When someone at work asks “why did it flag this customer?”, a logistic regression gives me a coefficient to point at. The forest gives me 500 trees.

It’s big. 500 deep trees on a few thousand rows was a 30 MB object in R, which is fine on a laptop and a bit silly to ship inside a web service.

And it’s not always the best. On structured data like this it’s very good with zero tuning, which is why it’s my first model now on anything tabular. A well-tuned gradient boosted model often beats it, but “well-tuned” is doing a lot of work there, and the forest got me 88% with one line, before lunch.