11. A Crowd of Unstable Trees

Averaging many trees into a random forest

Last time, one decision tree on MNIST reached only about eighty-seven or eighty-eight percent on our validation images. It also changed shape when we dropped a random five percent of the rows. Here is the fix for both problems. Grow many trees, each on a slightly different version of the data, and average what they say. That is a random forest. In scikit-learn it is called RandomForestClassifier, and on raw MNIST pixels it lands close to ninety-seven percent. That puts it level with nearest neighbors, and well above logistic regression's ninety-two. Back in chapter two we met Leo Breiman's 2001 random forests as part of the tree family's history. Today we open one up and see why it works.

Start with how each tree gets its own data. The method is called bagging, short for bootstrap aggregating. A bootstrap sample is a draw with replacement. Say you have ten rows, numbered one to ten, and you draw ten times. After each draw the row goes back in the pot. Say your draws come out as 3, 7, 7, 1, 9, 3, 10, 2, 7 and 5. Row seven shows up three times. Row three shows up twice. Rows four, six and eight never show up at all. Each tree in the forest trains on a sample like this one, so each tree sees a different mix of rows.

How many rows does a sample miss? On any single draw, a given row is missed with chance one minus one over n, where n is the number of rows. With ten rows that is nine tenths. A row has to be missed on every one of the n draws, so you multiply that chance by itself n times. For ten rows, nine tenths to the tenth power is about 0.35. As n grows, the number settles near 0.37. So each bootstrap sample holds about sixty-three percent of the distinct rows, and about thirty-seven percent are left out. Those left-out rows are called that tree's out-of-bag rows. That tree never trained on them, which makes them useful for checking it later.

Now, why does averaging help? Here is a piece of standard algebra worked on numbers. Suppose each tree's prediction wobbles with a variance we call sigma squared. Variance is how much a prediction would shift if you retrained on fresh data. Suppose any two trees are correlated by an amount rho, a number from zero to one that says how much they tend to make the same mistakes. Average M such trees. The variance left over is rho times sigma squared, plus one minus rho, times sigma squared, divided by M.

Put numbers in. Let sigma squared be one and M be a hundred trees. If the trees were fully independent, rho would be zero and the variance would drop to one over a hundred, which is 0.01. That is a hundredfold calmer. Now let rho be one half. The first part is half of one, so 0.5. The second part is half of one divided by a hundred, so 0.005. The total is about 0.505. Going from one tree to a hundred only cut the wobble in half. You can see why from the formula. The second part shrinks as you add trees. The first part, rho times sigma squared, does not shrink at all. More trees cannot remove the mistakes the trees share.

Bootstrap sampling alone leaves the trees quite alike. On MNIST, every tree will probably ask about the same few strong center pixels near its root, because those give the biggest impurity drop. So random forests add a second source of difference. At each split, the tree may only look at a random subset of the features. The scikit-learn default is the square root of the feature count. The square root of 784 is exactly 28, so each split chooses among 28 random pixels instead of all 784. Sometimes the best pixel is not in the subset, and the tree has to use the second- or fifth-best one. Each tree gets a bit worse. That is a small rise in bias. But the trees now disagree more, so rho falls, and the part of the variance that averaging could not touch shrinks with it.

Breiman made this tradeoff precise. In plain words, his bound says the forest's error grows as the trees become more correlated and falls as each tree becomes stronger. He also showed that the forest's error settles down as you add trees. So adding more trees does not make a forest overfit. It mostly costs time and memory. If you turn the feature subset all the way up, so that every split sees every pixel, you get plain bagged trees with no feature randomness. In scikit-learn that setting is max_features equals 1.0.

Now build one. You already have the split from earlier lessons. Fit on the first fifty thousand training images, validate on the next ten thousand, and leave the last ten thousand test images sealed. You do not need to scale the pixels. A tree only asks whether a pixel is above a threshold, so scaling changes nothing for a forest, just as it changed nothing for a single tree. Import RandomForestClassifier from sklearn dot ensemble. Create it with n_jobs equals minus one and random_state equals zero. Call fit on the fitting images and labels, then call score on the validation images and labels.

Each setting you just accepted has a default worth knowing. The number of trees is n_estimators, and it defaults to a hundred. Before version 0.22 it was ten, so older tutorials may show weaker results. The feature subset is max_features, and it defaults to the string "sqrt". Before version 1.1 the default was called "auto", so you will see that word in old code. bootstrap is True, which gives the resampling we worked through. min_samples_leaf is one and max_depth is None, so every tree grows fully, splitting until each leaf is pure, and many leaves hold only one or two images. oob_score is False unless you turn it on, and it only works when bootstrap is True. n_jobs equals minus one uses all your cores. The default of None uses only one. The speedup is often less than your core count, so eight cores will not make it eight times faster. random_state fixes both the bootstrap draws and the feature draws, so a rerun with the same seed and the same library version gives the same forest.

Fully grown trees bring a cost. A hundred trees, each with thousands of leaves, take real memory. If the model is too large to keep or save comfortably, raise min_samples_leaf or set max_depth. Either one shrinks every tree.

What should you expect? For scale, one published benchmark trained a random forest on raw MNIST pixels and averaged 97.20 percent test accuracy over five trials. It did not state the tree count. Training and evaluation together took about 591 seconds, a little under ten minutes, on a Xeon E-2288G server with 128 gigabytes of memory. Your number is a validation score on a different split and different hardware, so it will not match exactly. Expect it in the same neighborhood, near nearest neighbors' ninety-seven and clearly above logistic regression's ninety-two and a single tree's high eighties.

The forest and nearest neighbors reach similar accuracy in very different ways. Nearest neighbors has to compare each new image with all fifty thousand stored ones before it can answer. A forest asks each tree a short run of yes-or-no pixel questions and adds up the answers. So the forest predicts far faster. The exact gap depends on your machine, so measure it yourself. Wrap predict in a timer for both models and write down the two numbers.

The out-of-bag rows give you an extra check for free. Set oob_score equals True when you create the forest. After fitting, read oob_score_. Here is what it measures. Each training image is scored only by the trees that left it out of their bootstrap sample, and the score is the accuracy of those votes across all fifty thousand fitting images. It works like a built-in validation set.

Two cautions follow from how it works. Each image is judged by only about a third of the trees, the ones that missed it, so its vote comes from a smaller forest than the real one. You should expect the out-of-bag score to come in slightly below what the full forest would get. And if you try many settings and keep whichever gives the best out-of-bag score, that score turns optimistic, for the same reason a validation score does once you tune on it. That is why the test set stays sealed. A third detail matters if you run small forests. With only a handful of trees, some images were in every tree's sample and are never out-of-bag. Their rows in oob_decision_function_ come out as NaN, meaning not a number, and those images get no out-of-bag prediction. Check the out-of-bag score against your ten thousand validation images. If the two agree closely, you have some evidence the out-of-bag estimate is trustworthy for this setup.

Next, look at what the forest uses. The fitted forest has feature_importances_, one number per pixel. Reshape it to 28 by 28 and draw it as an image, the same way we did for the single tree. It will be smoother, because a hundred trees spread credit across many more pixels. You should still see the center bright and the border near zero. Be careful with this measure. It is computed on the training data, from how much each pixel lowered impurity while the trees grew. That means it can reward a feature the trees leaned on while overfitting. It also favors features with many distinct values.

The alternative is permutation importance. Import permutation_importance from sklearn dot inspection and pass it the fitted forest plus your validation images and labels. For each pixel, it shuffles that column and measures how far validation accuracy drops. A pixel the model truly relies on causes a big drop. On 784 pixels this takes a while, so start with a few thousand validation images and n_repeats of three or so. The two maps usually look broadly alike, but where they differ, trust the one computed on held-out data. Permutation importance has its own limit, which matters a lot for images. Neighboring pixels are strongly correlated. Shuffle one, and the model can lean on its neighbor, so the accuracy barely drops, and both pixels look less important than the stroke they share. Also, permutation importance only says anything about a model that works. On a weak model it describes what the weak model happens to use.

Probabilities change too. A single deep tree's predict_proba was just the class counts in one leaf, so it gave almost all zeros and ones. A forest's predict_proba averages each tree's leaf fractions. It does not count hard votes, which is a detail where scikit-learn differs from Breiman's original description. The result is a much smoother set of scores. A seven can now come back as 0.83. That helps with ROC curves, but smooth is not the same as calibrated. Whether a score of 0.8 means right eight times in ten is still something you check, not something you assume.

If you want even more randomness, scikit-learn also offers ExtraTreesClassifier, short for extremely randomized trees. Instead of searching for the best threshold on each candidate pixel, it draws a random threshold for each and picks the best among those. It also defaults to bootstrap equals False, so every tree sees all the rows. The trees differ more, variance falls further, and bias rises a little. It is worth one run beside the forest.

Here is the exercise. Use the validation split only. Sweep n_estimators at ten, fifty, a hundred and three hundred, against max_features at "sqrt" and at 0.5, which lets each split see half the pixels. That makes eight forests. Turn oob_score on for every run and keep random_state fixed. Before each run, write down a guess for validation accuracy. For each run, record the out-of-bag score, validation accuracy, fit time and prediction time.

Three checks tell you whether the results make sense. Accuracy should climb from ten trees to a hundred and then flatten, not fall, because adding trees does not overfit. The out-of-bag score should sit within about half a point of validation once you have fifty or more trees. At ten trees, look for NaN in the out-of-bag decision function. The 0.5 setting should fit far slower, since each split searches hundreds of pixels instead of 28. Whether it is more accurate is the guess you are testing. The earlier exercises, the error analysis, the AUC ranking, the nearest-neighbor runs and the tree sweep, are still open. This sweep can sit beside the tree sweep in the same notebook, so the two can be compared directly.

A forest builds its trees side by side, each blind to the others, and lets averaging cancel their mistakes. Gradient boosting comes next and does the opposite. It adds trees one after another, and each new tree is fitted to the errors the earlier ones left behind.