Home / MLT / Week 11

Week 11 · Bagging, boosting and AdaBoost

Official syllabus line: Ensemble methods - Bagging and Boosting (Adaboost)

About 80 minEnd Term material (see exam radar)BSCS2007 · Arun Rajkumar

Before you start: MLT week 7 (decision trees), MLT week 6 (bias and variance).

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine asking one friend for advice; they might be wrong. But if you ask many friends, and they all give slightly different opinions, you often get a better answer. This is like combining many simple ideas to make one really strong one. We call this an ensemble.
There are two main ways to build this committee. Imagine many students studying different notes, then voting. This is called Bagging, and it helps fix 'jumpy' mistakes. Or, imagine tutors teaching one after another, each focusing on what the last one got wrong. This is Boosting, which makes 'weak' lessons strong.
With Boosting, we focus on tough problems. Imagine five balloons, all equally weighted. If our first attempt pops just one balloon, that tricky balloon instantly becomes much heavier. So, the next attempt will try extra hard to avoid that specific balloon, learning from the mistake.
Remember, for exams, know how Bagging fixes 'jumpy' problems by reducing variance, and how Boosting strengthens 'weak' lessons by reducing bias. Also, roughly 37 percent of data is 'out-of-bag' in Bagging. Keep practicing these ideas, and you'll do great!

The one-minute story

Think of it like this

One expert may be wrong. A committee is harder to fool. An ensemble combines many simple models into one strong one. There are two classic ways to build the committee:

Bagging: many students, each studying a different random pile of the notes. Each student gives a vote, and we go with the majority. Because each saw slightly different notes, their mistakes point in different directions and cancel out. This calms jumpy models (variance), like deep decision trees.

Boosting: a relay of tutors. Tutor 1 teaches a quick lesson and finds which questions the class got wrong. Tutor 2 concentrates specifically on those hard questions. Tutor 3 does the same for what is still wrong, and so on. The final answer is a weighted vote where better tutors speak louder. This lifts weak models (bias) into a strong one. AdaBoost is the famous example.

By the end of this week you can:

explain why averaging reduces variance;
describe bootstrap sampling, bagging, out-of-bag error and random forests;
run AdaBoost by hand: weights, error $\varepsilon$ , $\alpha$ , reweighting;
compare bagging and boosting.

Words you need

Ensemble - a group of models whose predictions are combined.
Weak learner - a model only slightly better than guessing (a one-question decision tree, a "stump").
Bootstrap sample - a sample of size $n$ drawn with replacement from $n$ examples.
Out-of-bag (OOB) - the examples a given bootstrap sample missed.
Random forest - bagged decision trees with extra randomness in the features each split may use.
Boosting - training models in sequence, each focusing on the previous ones' mistakes.

Idea 1: Why averaging helps

Suppose $n$ models each make a prediction with variance $\sigma^2$ , and their errors are independent. The average has variance

\operatorname{Var}\Big(\frac1n\sum\hat f_i\Big)=\frac{\sigma^2}{n}

Ten independent models with variance $4$ give an average with variance $0.4$ . If the errors are correlated with correlation $\rho$ , the variance is $\rho\sigma^2+\frac{1-\rho}n\sigma^2$ : averaging helps less when the models are alike. So the art is to make models that are good but different.

Idea 2: Bagging and random forests

The idea

Bagging (Bootstrap aggregating):

Build $B$ bootstrap samples (each: $n$ draws with replacement from the training set).
Train one model (typically a deep, unpruned decision tree) on each.
Predict by majority vote (classification) or average (regression).

It reduces variance and leaves the bias about the same. It works best with high-variance, low-bias models (deep trees) and does little for stable ones.

Out-of-bag error. The chance a particular example is not picked in a bootstrap sample is $\big(1-\frac1n\big)^n\to e^{-1}\approx0.368$ . So each model never sees about 36.8% of the data. Test each model on the examples it missed and average: a free, honest validation estimate with no separate hold-out set.

Random forest = bagged trees plus one trick: at every split, the tree may only consider a random subset of the features (about $\sqrt d$ for classification). That forces the trees to differ ( $\rho$ smaller), so the average is better. Forests are strong, need little tuning and give a feature importance measure.

Solved example: 1. Out-of-bag fraction

Question. A training set has $n=1000$ examples. About how many are out-of-bag for one bootstrap sample?

Solution. $\big(1-\frac1{1000}\big)^{1000}\approx e^{-1}=0.368$ , so about 368 examples are left out (and about 632 distinct ones are used).

Idea 3: Boosting and AdaBoost

AdaBoost (Adaptive Boosting) keeps a weight on every training example, and re-weights after every round so that the next learner concentrates on the examples the ensemble currently gets wrong. Labels are $\pm1$ and each weak learner $h_t$ outputs $\pm1$ .

The idea

AdaBoost

Start with equal weights $w_i=\frac1n$ .
For rounds $t=1,\dots,T$ :
- train a weak learner $h_t$ using the weights $w_i$ ;
- compute its weighted error $\varepsilon_t=\sum_{i:\,h_t(\mathbf x_i)\ne y_i}w_i$ (must be $<0.5$ );
- its say in the final vote: $\alpha_t=\dfrac12\ln\dfrac{1-\varepsilon_t}{\varepsilon_t}$ ;
- update: $w_i\leftarrow w_i\,e^{-\alpha_ty_ih_t(\mathbf x_i)}$ (wrong examples get heavier, right ones lighter), then normalise so the weights sum to 1.
Final classifier: $H(\mathbf x)=\operatorname{sign}\!\Big(\sum_{t=1}^T\alpha_th_t(\mathbf x)\Big)$ .

Intuition for $\alpha_t$ : $\varepsilon_t$ close to 0 means a great learner, $\alpha_t$ is large; $\varepsilon_t=0.5$ means a useless coin flip, $\alpha_t=0$ ; $\varepsilon_t>0.5$ would give a negative weight (flip its vote).

Solved example: 2. One AdaBoost round

Question. Five examples start with weights $0.2$ each. The first stump gets exactly one wrong. Compute $\varepsilon_1$ , $\alpha_1$ and the new weights.

Solution.

$\varepsilon_1=0.2$ (the weight of the one mistake).
$\alpha_1=\frac12\ln\frac{0.8}{0.2}=\frac12\ln4=\mathbf{0.693}$ .
Wrong example: $0.2\cdot e^{0.693}=0.2\cdot2=0.4$ . Each of the four right ones: $0.2\cdot e^{-0.693}=0.2\cdot0.5=0.1$ . Sum $=0.4+4(0.1)=0.8$ .
Normalise (divide by $0.8$ ): wrong example $=\mathbf{0.5}$ ; each right one $=\mathbf{0.125}$ .

The single mistake now holds half of all the weight. The next stump will be heavily penalised unless it gets that example right, which is exactly the "focus on the hard question" idea.

Solved example: 3. Combining weak learners

Question. Three stumps with $\alpha=(0.9,\,0.4,\,0.3)$ vote $+1,\,-1,\,-1$ on a new point. What does the final classifier say?

Solution. Score $=0.9(+1)+0.4(-1)+0.3(-1)=0.2>0$ , so the prediction is $+1$ . Two stumps said $-1$ , but the first is trusted more than the other two together.

Facts about AdaBoost:

Only needs weak learners with $\varepsilon_t<0.5$ ; the training error drops exponentially with the number of rounds (bounded by $\prod_t2\sqrt{\varepsilon_t(1-\varepsilon_t)}$ ).
It reduces bias: many simple stumps combine into a complex boundary.
It is sensitive to noise and outliers: mislabelled points keep getting heavier and can drag the ensemble along, so it can overfit noisy data.
It minimises an exponential loss; gradient boosting generalises the idea to any differentiable loss.

Idea 4: Bagging versus boosting

	Bagging / random forest	Boosting (AdaBoost)
Builds models	in parallel, independently	in sequence, each depends on the last
Data seen by each model	bootstrap sample, equal weights	re-weighted data
Combines by	simple vote / average	weighted vote ( $\alpha_t$ )
Reduces mainly	variance	bias
Base learner	deep, low-bias trees	shallow, weak learners (stumps)
Noise sensitivity	robust	sensitive

Your turn

Your turn: 1. Variance of an average

Ten independent models each have prediction variance $9$ . What is the variance of their average?

Need a hint?

$\sigma^2/n$ .

Show the full solution

$9/10=\mathbf{0.9}$ .

Your turn: 2. AdaBoost arithmetic

A weak learner has weighted error $\varepsilon=0.25$ . Find $\alpha$ , and the multipliers applied to correct and wrong examples.

Need a hint?

$\alpha=\frac12\ln\frac{1-\varepsilon}\varepsilon$ .

Show the full solution

$\alpha=\frac12\ln3=0.549$ . Wrong: $e^{0.549}=\sqrt3=1.732$ . Right: $e^{-0.549}=\frac1{\sqrt3}=0.577$ .

Your turn: 3. Normalise

Four examples have weights $0.25$ each. The learner gets one wrong with $\varepsilon=0.25$ , so the multipliers are $\sqrt3$ and $1/\sqrt3$ . Give the new normalised weights.

Need a hint?

Multiply, add, divide.

Show the full solution

Wrong: $0.25\sqrt3=0.433$ . Right: $0.25/\sqrt3=0.144$ each (three of them: $0.433$ ). Total $=0.866$ . Normalised: wrong $=0.5$ , each right $=0.1667$ . (Again the one mistake gets exactly half the weight.)

Your turn: 4. Bagging facts

In a bootstrap sample of $n$ points, what fraction are expected to be out-of-bag for large $n$ ? How many distinct points are in the sample, as a fraction?

Need a hint?

$e^{-1}$ .

Show the full solution

OOB about $36.8\%$ ; distinct points about $63.2\%$ .

Your turn: 5. True or false

(a) Bagging trains its models one after another. (b) AdaBoost gives larger weights to misclassified examples. (c) A random forest considers all features at every split. (d) A learner with error 0.5 gets a zero vote in AdaBoost.

Need a hint?

Re-read the tables.

Show the full solution

(a) False, in parallel. (b) True. (c) False, a random subset. (d) True, $\alpha=\frac12\ln1=0$ .

Exam radar

In the MLT End Term, summaries mention AdaBoost in 22 of 49 papers, Bagging in 14, Random Forest in 12.

Typical: compute $\alpha_t$ or the new weights for a given $\varepsilon$ , "which statements about bagging/boosting are true?", "bagging reduces variance, boosting reduces bias", fractions of out-of-bag samples, and "what does the final AdaBoost classifier look like?" ( $\operatorname{sign}\sum\alpha_th_t$ ).

Watch out - real exam trap

$\alpha_t=\frac12\ln\frac{1-\varepsilon_t}{\varepsilon_t}$ (the half and the order of $1-\varepsilon$ over $\varepsilon$ ).
After updating, normalise the weights.
Bagging $\to$ variance; boosting $\to$ bias.
Bootstrap = with replacement.
Boosting is sequential and cannot be parallelised across rounds; bagging can.

Quick quiz

In AdaBoost, a learner with weighted error 0.2 gets the vote weight alpha equal to...

ln 4
half of ln 4
0.2
4

alpha = 0.5 ln((1 - 0.2)/0.2) = 0.5 ln 4 = 0.693.

Bagging mainly reduces...

bias
variance
the number of features
training time

Averaging many models trained on bootstrap samples reduces variance.

For large n, the fraction of examples missing from one bootstrap sample is about...

10 percent
50 percent
36.8 percent
63.2 percent

(1 - 1/n)^n tends to e^-1 = 0.368.

Select all TRUE statements. (select all that apply)

Boosting trains models sequentially.
AdaBoost can be hurt by noisy labels.
Random forests use all features at every split.
Bagging gives higher weights to misclassified points.

Random forests restrict each split to a random subset of features; the re-weighting of misclassified points is boosting.

Recap

Remember this

Averaging independent models cuts variance by $1/n$ ; use different-but-good models.
Bagging: bootstrap samples, deep trees, vote/average; ~36.8% OOB (free validation). Random forest = bagging + random feature subset per split.
AdaBoost: weights $\to$ weak learner $\to\varepsilon_t\to\alpha_t=\frac12\ln\frac{1-\varepsilon_t}{\varepsilon_t}\to$ reweight $w_i e^{-\alpha_ty_ih_t}$ $\to$ normalise; final $\operatorname{sign}\sum\alpha_th_t$ .
Bagging reduces variance; boosting reduces bias (but is noise-sensitive).

Formulas to keep

Average of $n$ independent: $\sigma^2/n$ ; correlated: $\rho\sigma^2+\frac{1-\rho}n\sigma^2$
OOB probability $(1-\frac1n)^n\to e^{-1}\approx0.368$
AdaBoost: $\varepsilon_t=\sum_{\text{wrong}}w_i$ ; $\alpha_t=\frac12\ln\frac{1-\varepsilon_t}{\varepsilon_t}$ ; $w_i\leftarrow w_ie^{-\alpha_ty_ih_t(\mathbf x_i)}$ ; $H=\operatorname{sign}\sum\alpha_th_t$

Connected weeks (learn them together)

MLP week 10 - Random forests, boosting and tuning: Boosting and random forests: the theory, then the code.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 16 real questions on this week All End Term papers