Ensembles: bagging, random forests and boosting

The supervised algorithms so far come in two families. Generative models assume a form for \(P(\mathbf{x}, y)\) and estimate its parameters: naive Bayes and Gaussian naive Bayes, also called Gaussian discriminant analysis (Part 14). Discriminative models go straight for the decision: k-nearest neighbours and decision trees (Part 13), the perceptron and logistic regression (Part 15) and support vector machines (Part 16). Part 18 places many of these in one loss-plus-regularization framework.

This part is about meta-classifiers, also called ensemble classifiers. A meta-classifier sits on top of an existing learning algorithm. It runs that algorithm many times and combines the resulting classifiers into a single, better one.

Weak and strong learners L66 · 3:10

The course keeps the definition informal. A weak learner is a classification algorithm that does better than random on test data, perhaps only a little better. For binary labels, tossing a fair coin is the random baseline and has a 50% error rate. A weak learner might reach 55% or 60% accuracy.

The goal of an ensemble is to convert a weak learner into a strong learner. Why start from weak learners instead of building a good learner directly? The lecture gives two kinds of weak learner, and each leads to one of the two methods in this part:

• learners that are weak because they overfit, handled by bagging (L67);
• learners that are weak because they underfit, handled by boosting (L68).

Labels come from structure plus noise. The true relationship between input and output has some structure (linear, tree-shaped, a sine curve), and the observed labels carry random noise on top of it. A learner has to recover the structure from noisy data, and it can go wrong in two opposite directions.

• Overfitting: the learner treats noise as if it were structure. The lecture's example is a decision tree split again and again until every leaf is pure and the training error is 0 (Part 13 warned against this). The last splits only follow the noise.
• Underfitting: the learner treats structure as if it were noise. It is too conservative and misses part of the real relationship.

A regression example

Regression makes the picture easy to see, and the same ideas apply to classification. Let the true structure linking \(x\) to \(y\) be a sine curve, and let the data points scatter around it because of noise. We never see the true curve; as designers we only choose which family of models to search.

• A straight line underfits 8:19. The best line treats the rise and fall of the sine as noise, although they are real structure. Its training error is not zero. The classification version is a linear classifier used when the label really depends on a quadratic or cubic function of the input.
• A high-degree polynomial overfits 10:21. The lecture draws a degree-8 polynomial that passes through every training point, so its training error is 0. It treats the noise as structure.

Neither does well at a new test point 10:52. Both predictions miss the true value, for opposite reasons.

Complexity knobs from earlier parts L66 · 11:53

• k in k-NN. Small \(k\) gives a very complicated decision boundary. As \(k\) grows the boundary smooths out, and at \(k = n\) the classifier outputs one value over the whole space.
• Depth of a decision tree. At depth 1 the tree asks about a single feature–threshold pair, which is too simple for good test accuracy. Grown until it is as pure as possible, it fits the noise.

At either end of these knobs the result is a weak learner that does poorly on test data.

Start with the overfit model. Draw a fresh data set of the same size from the same distribution. The noise is random, so the labels come out a little different. Fit a degree-8 polynomial again: it still has zero training error, but it is a different polynomial, because it follows the new noise. Repeat this many times and look only at the prediction \(\hat y\) at one test point. It lands in very different places from one data set to the next.

The model is too sensitive to the data. This is high variance: a small change in the training data causes a large change in the predictions.

The underfit line behaves the other way 16:28. Redrawing the data moves the best line only slightly, so its predictions at the test point stay in a narrow range: low variance. They are still wrong, every time, because a line has missed the structure. This is high bias. Bias measures how well the assumed structure can represent the truth. A line is far from a sine curve, so its bias is high. A degree-8 polynomial can imitate a sine closely, so its bias is low, and it pays for that with high variance.

Every hyperparameter tuned by cross-validation so far (Part 11) can be read as a setting on this trade-off: \(k\) in k-NN, the depth of a decision tree, and the regularization weight \(\lambda\) in regularized logistic regression or in support vector machines. Each one chooses between searching a larger, more complex class of models and a smaller, simpler one. Ensembles take a different route: they handle the trade-off by combining many classifiers 19:31.

The first ensemble method is bagging, short for bootstrap aggregating (bootstrap aggregation). Its idea comes from maximum likelihood estimation (Part 8). Let \(x_1, \dots, x_n\) be independent samples from a Gaussian with unknown mean \(\mu\) and known variance 1. In the lecture's example \(\mu = 5.5\) and the samples are \(5,\ 7.3,\ 6.7,\ 8.2,\ \dots\), ending with \(9\).

Estimation lets us pick any function of the data as the estimator. Compare these:

The data are random, so every estimator is a random variable. An estimator \(\hat\theta\) of \(\theta\) is unbiased if \(\mathbb{E}[\hat\theta] = \theta\): on average it equals the truth 3:09. Every estimator above is unbiased. Each \(x_j\) is a sample from a Gaussian with mean \(\mu\), and expectation is linear:

So unbiasedness alone cannot tell them apart, yet \(\hat\mu_1\) is clearly worse. Draw a fresh sample \(x_1', \dots, x_n'\) and \(\hat\mu_1\) jumps to wherever \(x_1'\) happens to fall, while the average hardly moves. The size of this fluctuation is measured by variance.

Bagging applies the same idea to classifiers.

Suppose someone gives us \(M\) data sets \(D_1, \dots, D_M\), each holding \(n\) feature–label pairs drawn independently from the same distribution \(P\):

Run the weak learner on each one. Here the weak learner is a decision tree grown to full depth, so each tree overfits. This gives classifiers \(h_1, \dots, h_M\), each a map \(h_i : \mathbb{R}^d \to \{-1, +1\}\), where \(h_i(\mathbf{x}_{\text{test}})\) is the \(i\)-th tree's prediction. Each tree has low bias and high variance: change its data set a little and its predictions change a lot.

Reduce the variance by averaging, as with the estimator:

The average of \(\pm1\) votes lies between \(-1\) and \(+1\). It is positive when most of the \(h_i\) say \(+1\) and negative when most say \(-1\), so \(h^*\) is a majority vote (a tie counts as \(+1\) under this definition of sign).

The hope: the individual trees have low bias but high variance; the aggregate keeps the low bias and has much lower variance, and low bias with low variance is what gives low error 11:49. The catch is that nobody hands us \(M\) independent data sets. We have one.

The input is a single data set \(D = \{(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)\}\) with \(\mathbf{x}_i \in \mathbb{R}^d\) and \(y_i \in \{-1, +1\}\). The obvious way to get \(M\) data sets is to cut \(D\) into \(M\) disjoint pieces. The pieces are independent, but they are small: the more pieces, the fewer points each has, and a learner trained on a handful of points has too little information to learn from. We want many data sets without dividing the data, which sounds contradictory. The way out is to let points repeat.

Bootstrapping is sampling with replacement. Each data set it creates is called a bag (hence "bagging"). To build a bag from \(D = \{\mathbf{x}_1, \dots, \mathbf{x}_5\}\), reach into \(D\) with your eyes closed and pick a point uniformly at random, note it, put it back, mix, and pick again, until the bag holds as many points as \(D\), here 5. In the lecture the first bag came out as \(\mathbf{x}_3, \mathbf{x}_4, \mathbf{x}_5, \mathbf{x}_3, \mathbf{x}_5\) and a second as \(\mathbf{x}_1, \mathbf{x}_1, \mathbf{x}_5, \mathbf{x}_4, \mathbf{x}_1\). Since every draw is uniform, anything can happen: repeats, and points missing altogether.

1. Bagging (bootstrap aggregation)
2. Input: one data set \(D = \{(\mathbf{x}_i, y_i)\}_{i=1}^n\) and the number of bags \(M\).
3. Bootstrap. For \(j = 1, \dots, M\), build bag \(D_j\) by drawing \(n\) points from \(D\) uniformly at random with replacement.
4. Train. Run the weak learner on each bag to get \(h_j\). A full-depth decision tree is the usual choice, but any learner can be used.
5. Aggregate. Output \(h^*(\mathbf{x}) = \operatorname{sign}\big(\frac1M\sum_{j=1}^M h_j(\mathbf{x})\big)\).

The two steps give the method its name 17:17: bootstrapping turns one data set into \(M\), and aggregation turns \(M\) classifiers into one. The result is a bagging classifier.

How much repetition is there in a bag? Fix one point \(\mathbf{x}_j\). A single uniform draw picks it with probability \(1/n\), so it misses \(\mathbf{x}_j\) with probability \(1 - 1/n\). The bag is \(n\) independent draws, and \(\mathbf{x}_j\) is absent only if every one of them misses it:

So on average a bag contains about two-thirds of the distinct points (the lecture rounds this to "about 67%", which is the value at \(n = 5\); for large \(n\) it settles at 63.2%). Roughly 37% of the data is missing from any one bag, and the empty slots are filled by repeats.

Why does this help? An overfit tree fits the noise specific to its own bag, repeats included. But different bags repeat and omit different points, so different trees fit different noise. When their votes are averaged, the noise tends to cancel. Each tree is still a complex, low-bias classifier, so the combination keeps the low bias while its variance falls. In practice, plotting bias and variance as more trees are added shows the variance coming down and the bias staying roughly flat.

Standard result, not in the lecture: if \(M\) predictors each have variance \(\sigma^2\) and every pair has correlation \(\rho\), their average has variance \(\rho\sigma^2 + (1-\rho)\sigma^2/M\). More bags shrink only the second term; only lowering \(\rho\) shrinks the first. This is why decorrelation matters.

A very popular way to get less correlated learners is the random forest, one of the most widely used classification techniques in practice. It has two ingredients.

1. Bag decision trees, and overfit each one. Build bags \(D_1, \dots, D_M\) and grow a tree on each until it is as pure as possible (zero training error), with no cross-validation of the depth. These trees have low bias.
2. Feature bagging. While growing each tree, consider only a random subset of the features at every node.

Recall how a tree picks a split (Part 13). At each node it tries every feature and threshold and keeps the question "\(f_j < \theta\)?" that gives the largest drop in impurity, measured by information gain, the Gini index or any other impurity measure. So every tree, whatever its bag, considers all the features at every node.

Feature bagging changes that search. Say there are \(d = 1000\) features (height, weight, and so on). To choose the split at the root, sample a few features, in the lecture's illustration \(f_1, f_5, f_{23}, f_{40}\), pretend the data has only these, and find the best feature–threshold split among them; suppose it is on \(f_5\). At the next node, sample again, say \(f_1, f_{10}, f_{40}, f_{20}\), and find the best split among those. Doing this at every split means different trees use different sets of features, so they become more decorrelated, and averaging them reduces variance more. This is also what is observed in practice.

• How many features per split. A common rule of thumb is about \(\sqrt d\) features at each split for classification, for which there is some theoretical reasoning. For regression the lecture recalls a suggestion of around \(d/3\) or \(d/5\), that is, of the order of \(d\). These are rules of thumb; with enough computation time, try other values and keep the one that works best.
• Variants. For regression, replace the classification trees by regression trees. One can randomize further, for example by also sampling the candidate thresholds at each split 27:22. Standard practice is still overfit trees plus feature bagging.

A major practical advantage of bagging: the weak learners are not needed until the aggregation step, and none of them depends on another. On a CPU with many cores they can all be trained at the same time, without waiting for one tree to finish before starting the next. This is one reason bagging is popular in practice.

Bagging is two choices made with a reason:

1. Bootstrapping creates the bags by uniform sampling with replacement.
2. Aggregation takes a plain average, because averaging reduces variance.

Is there a more principled way to sample than uniformly, and a more principled way to aggregate than a plain average 30:15? The answer to both is yes. An algorithm that keeps the same two steps but does each in the best possible way, in a sense made precise by its analysis, is the boosting algorithm.

Boosting is a general technique. The lecture studies one specific boosting algorithm, AdaBoost, introduced by Freund and Schapire in the 1990s. Their work on boosting, a contribution to theoretical machine learning, earned them the Gödel Prize.

Boosting also turns a weak learner into a strong one, and does it in a theoretically sound, principled way. Its weak learners can just as well be underfit. This is part of what makes boosting powerful, because underfit classifiers are easy and cheap to get 1:05. Stop a decision tree after one question, "\(f_j < \theta\)?". In the plane this cuts the feature space once, with a vertical or horizontal line, and calls one side positive and the other negative. In higher dimensions it is even more simplistic.

Such a one-level tree is a decision stump; sometimes two levels (two questions) are used. Stumps are the usual weak learners in boosting. A tree in practice might be 10 to 15 levels deep, so cutting it at one or two levels costs a lot of accuracy: a stump has high bias and low variance.

Now treat the weak learner as a black box: give it a data set and it returns, say, a stump. A single stump cannot reach 100% training accuracy. Can we control what we feed the black box so that the resulting classifiers, combined, reach zero training error? A combination that does is what the lecture calls a strong learner here. Boosting says this is possible and gives an algorithm for it.

AdaBoost (adaptive boosting) replaces both of bagging's steps by more principled ones. In place of uniformly drawn bags it keeps a weight on every training point, a probability distribution \(D_t\) over the points that changes every round. In place of a plain average it takes a weighted vote.

1. AdaBoost
2. Input: \(S = \{(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)\}\), \(\mathbf{x}_i \in \mathbb{R}^d\), \(y_i \in \{-1, +1\}\), and a number of rounds \(T\).
3. Initialize \(D_1(i) = 1/n\) for every point \(i\).
4. For \(t = 1, \dots, T\):
   • Give \(S\) and \(D_t\) to the weak learner; it returns \(h_t : \mathbb{R}^d \to \{-1, +1\}\).
   • Compute the weighted error \(\varepsilon_t = \sum_{i:\, h_t(\mathbf{x}_i) \ne y_i} D_t(i)\) and \(\alpha_t = \ln\sqrt{(1-\varepsilon_t)/\varepsilon_t}\).
   • Reweight: \(\tilde D_{t+1}(i) = D_t(i)\,e^{\alpha_t}\) if \(h_t(\mathbf{x}_i) \ne y_i\), and \(\tilde D_{t+1}(i) = D_t(i)\,e^{-\alpha_t}\) if \(h_t(\mathbf{x}_i) = y_i\).
   • Normalize: \(D_{t+1}(i) = \tilde D_{t+1}(i) \big/ \sum_{j} \tilde D_{t+1}(j)\).
5. Output \(h^*(\mathbf{x}) = \operatorname{sign}\Big(\sum_{t=1}^T \alpha_t\, h_t(\mathbf{x})\Big)\).

The lecture writes the uniform starting weights as \(D_0\); they are called \(D_1\) here so that round \(t\) always trains on \(D_t\). Where \(\alpha_t\) comes from is the next section.

Feeding weights to the weak learner L68 · 7:38

If the weak learner can take weighted points, pass it \(S\) together with \(D_t\). The plain versions of algorithms such as decision trees do not handle weights. Then create a bag from \(S\) according to \(D_t\): draw \(n\) points with replacement, where each draw picks point \(i\) with probability \(D_t(i)\). A point with \(D_t(i) = 0.7\) has a 70% chance of being the one picked at each draw. Train the weak learner on that bag to get \(h_t\). With the uniform \(D_1\) this is exactly bagging's bootstrap; later rounds tilt the sampling.

Whose weights should go up? L68 · 9:50

Suppose there are 1000 points and the first stump classifies 600 correctly and 400 incorrectly. The next stump is also only better than random, and we want it to be a different, useful classifier. So raise the weights of the 400 misclassified points and lower the rest. Heavier points are drawn more often into the next bag, so the next stump tries to find features that classify them correctly. In this way each round is pushed to do well where the previous one failed.

The update is multiplicative: a mistake's weight is multiplied by \(e^{\alpha_t}\) and a correct point's by \(e^{-\alpha_t}\) 13:01. After this the weights no longer add up to 1, so divide each by their sum to get a distribution again, which we need in order to sample from it 13:33.

The lecture's example L68 · 14:03

Three points start at \(1/3\) each. Suppose that at some round their weights are \(D_t = (0.3,\ 0.5,\ 0.2)\), and the stump \(h_t\) misclassifies \(\mathbf{x}_1\) and classifies \(\mathbf{x}_2\) and \(\mathbf{x}_3\) correctly. Then

\(Z_t\) is just the normalizer that makes the three weights add up to 1. The numbers are worked out in the next section, once \(\alpha_t\) is known.

The final classifier

After \(T\) rounds there are \(T\) weak learners \(h_1, \dots, h_T\), each trained on a different distribution over the data. They are combined as in bagging, with one change: a weighted vote, \(h^*(\mathbf{x}) = \operatorname{sign}\big(\sum_t \alpha_t h_t(\mathbf{x})\big)\). The vote weights are exactly the \(\alpha_t\) that were used to bump the point weights.

The analysis of boosting says the right weights are

\(\varepsilon_t\) is the error of \(h_t\) measured with the weights it was trained on: take the points it gets wrong and add up their weights under \(D_t\). Heavy points count for more. The logarithm appears because \(\alpha_t\) is used in an exponent: the multiplier on a mistake is \(e^{\alpha_t} = \sqrt{(1-\varepsilon_t)/\varepsilon_t}\).

A learner with low weighted error gives its mistakes a large bump and gets a large say in the final vote. A learner with error close to \(\tfrac12\), barely better than random, changes the weights very little and gets almost no vote 18:53. A weak learner beats random, so \(\varepsilon_t < \tfrac12\) and \(\alpha_t > 0\). The lecture says that deriving this choice is beyond the scope of the course.

The example, with numbers

In the three-point example only \(\mathbf{x}_1\) is misclassified, so \(\varepsilon_t = 0.3\) and \(\alpha_t = \tfrac12\ln(0.7/0.3) \approx 0.424\), giving multipliers \(e^{\alpha_t} \approx 1.53\) and \(e^{-\alpha_t} \approx 0.65\). The lecture keeps \(\alpha_t\) symbolic; plugging in:

The mistake ends up holding exactly half the weight. This is a general property of this \(\alpha_t\) (a standard fact, not stated in the lecture): on the new weights \(D_{t+1}\), the stump \(h_t\) has weighted error exactly \(\tfrac12\), no better than random, so the next round cannot simply pick \(h_t\) again.

The lecture states a guarantee and points to standard boosting texts for the proof. With \(\alpha_t\) set as above, the training error of \(h^*\) on the original data set \(S\) drops fast as rounds are added, even though each weak learner on its own makes many training mistakes. Once the number of rounds \(T\) exceeds a certain quantity, the training error is exactly zero 20:33. That quantity depends on two things:

• The number of data points \(n\). More data needs more rounds, as you would expect, but the dependence is only logarithmic in \(n\).
• How good the weak learner is, through a parameter \(\gamma\). The weak learner is assumed to be better than random by some margin: its accuracy is \(\tfrac12 + \gamma\) 22:14. At 60% accuracy \(\gamma = 0.1\); at 70%, \(\gamma = 0.2\); at 90%, \(\gamma = 0.4\). A very weak learner with 51% accuracy has \(\gamma = 0.01\) and needs many rounds; one with 75% has \(\gamma = 0.25\) and needs far fewer. The stronger the weak learner, the fewer the rounds.

The striking part is that AdaBoost never needs to know \(\gamma\), that is, how weak its weak learner is. Earlier versions of boosting needed \(\gamma\) as part of the algorithm 23:55. AdaBoost adapts: keep adding weak learners and the training error must eventually reach zero. The lecture calls this the power of boosting.

The real goal is doing well on test data. So plot both errors against the number of rounds \(T\), stopping the algorithm after each round and measuring its error on a held-out test set. Theory says the training error falls to zero at some round \(T^*\) and stays at zero. The test error also falls.

What happens after \(T^*\)? A reasonable guess is overfitting. Every training point is already classified correctly, so further weak learners might start fitting the noise, and the test error would turn upward. Surprisingly, on many data sets the test error keeps decreasing after the training error reaches zero. It does not reach zero, since the training data carries only so much information about the underlying distribution. This is typical behaviour with exceptions: one can construct data sets on which boosting does start to overfit.

The practical advice 27:35: do not stop boosting the moment the training error becomes zero. Continue for a while, watch the error on a validation set, and choose the number of rounds based on whether the validation error keeps going down or starts to reverse.

There is an explanation under certain conditions, beyond the scope of the course. After the training error is zero, the newly added weak learners keep increasing the margin of the combined classifier, and a larger margin means a better ability to do well on test data, the same idea that motivated SVMs in Part 16.

AdaBoost is an off-the-shelf classifier that works extremely well and can boost even a poor classifier's accuracy a long way. Its downside is that it cannot run in parallel. To build the next weak learner you need to know where the previous one made its mistakes, so each round waits for the round before it. Bagging's bags are uniform, independent of one another, and can all be processed at once. Boosting therefore takes somewhat longer to train, but it typically performs better than bagging in practice.

Boosting helps most when the base learner really is weak. Start from a good learner and boosting typically gives no improvement in accuracy. Theory would allow an SVM as the weak learner, but in practice one boosts a quick and dirty learner such as a decision stump. Comparative studies find boosted stumps and SVMs typically perform comparably: on some data sets one is better, on others the other 30:51.

Neither bagging nor boosting needs much tuning, so both can be run quickly. That is why they are called off-the-shelf classifiers.

This ends the course's discussion of ensemble (meta) classifiers. The next lecture 31:58 unifies the classifiers seen so far under one theme, loss plus regularization, which also explains why binary classification has a whole host of algorithms while regression had essentially one (Part 18).

Weak learner

A classifier that does better than random (50% for binary labels) on test data, perhaps only slightly, e.g. 55–60%.

Strong learner

What an ensemble aims for; in L68, a combination that reaches zero training error.

Ensemble (meta) classifier

Runs a base learning algorithm many times and combines the resulting classifiers into one.

Overfitting

Treating noise as structure: zero or tiny training error, poor test error, predictions sensitive to the data.

Underfitting

Treating structure as noise: a model too simple for the true relationship.

Bias

How far the assumed structure is from the truth; high for underfit models such as a line for a sine.

Variance

How much the predictions change when the training data is redrawn; high for overfit models.

Bootstrap sample (bag)

\(n\) uniform draws with replacement from the data; it holds about 63% of the distinct points.

Bagging

Bootstrap aggregation: train one learner per bag, predict with \(\operatorname{sign}\big(\frac1M\sum_i h_i(\mathbf{x})\big)\). Reduces variance.

Random forest

Bagged full-depth decision trees with feature bagging: each split considers only a random subset of about \(\sqrt d\) features.

Decision stump

A decision tree with one (sometimes two) questions: cheap, high bias, low variance. The usual weak learner for boosting.

AdaBoost

Adaptive boosting: reweight the points after each round, raising the weights of mistakes, and output \(\operatorname{sign}\big(\sum_t \alpha_t h_t(\mathbf{x})\big)\).

Weighted error \(\varepsilon_t\)

Total weight under \(D_t\) of the points that \(h_t\) misclassifies.

Vote weight \(\alpha_t\)

\(\tfrac12\ln\frac{1-\varepsilon_t}{\varepsilon_t}\): the factor in the weight update \(e^{\pm\alpha_t}\) and the weight of \(h_t\) in the final vote.