Does Adaboost ensemble use bootstrapping?

Question

I am reading about boosting methods in the book Elements of statistical learning. In page 339 they describe the Ada boost algorithm as

I understand the general idea behind it: Give more weight to missclassification errors so that the next model predicts those better. However, I do not understand how the weights affect the classifiers. In this image, it only states

• Fit classifier $G_m(x)$ to the training data using weights $w_i$

How are the weights used? My guess is that, similarly to bagging, adaboost performs bootstrapping on the dataset, and observations are drawn based on the weights, so observations with larger weights are more likely to appear in the next iteration. But I have been unable to find any reference that verify if this is actually what the algorithm does or if I am completely missunderstanding something.

Answer 1

It depends, actually. There are two possible behaviors, described in section 3 of "Experiments with a New Boosting Algorithm" by Freund and Schapire:

We first mention briefly a small implementation issue: Many learning algorithms can be modified to handle examples that are weighted by a distribution such as the one created by the boosting algorithm. When this is possible, the booster's distribution $D_t$ is supplied directly to the weak learning algorithm, a method we call boosting by reweighting. However, some learning algorithms require an unweighted set of examples. For such a weak learning algorithm, we instead choose a set of examples from $S$ independently at random according to the distribution $D_t$ with replacement. The number of examples to be chosen on each round is a matter of discretion; in our experiments, we chose $m$ examples on each round, where $m$ is the size of the original training set $S$. We refer to this method as boosting by resampling.

(For example, the sklearn implementation only allows for boosting by reweighting; the docs say "support for sample weighting is required" for the base classifier.)

Answer 2

You understanding is completely correct.

• Starting at step 1, you initialise uniform weights $w_i = 1 / N$.

• Beginning at step 2, in say iteration $m = 1$, you sample a bootstrap dataset $\mathcal{B}_1$, which consists of $N$ data points. This bootstrap dataset $\mathcal{B}_1$ is the result of sampling each point $(x_i, y_i)$ in the original training dataset $\mathcal{D}$ with probability $w_i$.

Then you use this bootstrap dataset $\mathcal{B}_1$ so that the specification in ESL that you

"fit the classifier $G_1(x)$ to the training data using weights $w_i$"

is exactly equivalent to

"fit the classifier $G_1(x)$ using the bootstrap data set $\mathcal{B}_1$"

You then proceed to carry out steps 2(b), 2(c), 2(d), which concludes with updating the weights $w_i$, then with these updated weights you return to begin iteration $m = 2$, which involves sampling a new bootstrap dataset $\mathcal{B}_2$ and repeat...

---

I am somewhat confused by why it is that you are unable to find appropriate references on the behaviour of Adaboost. There are notes on its behaviour in ESL pp338-339, but I can see why they might be unclear, they make no reference to the idea of using bootstrapped datasets, which clarifies things. My suggestion is that when in doubt, consult primary sources e.g. the original papers of Schapire and Freund. In the case that it might be mathematically heavy-going (sometimes primary literature can be), consult a secondary ML text like Murphy's MLPP or Bishop's PRML; or university lecture materials on the topic.

N.B. There is a 2nd possible behaviour to Adaboost that I was not aware of, which @Ben Reininger has supplied primary source info on.

On this basis, my response needs to be appropriately qualified to refer to the description of Adaboost as given in ESL.