How does resampling in AdaBoost (exactly) work?

Overall, I like to think that I understand how AdaBoost works, i.e., fitting a weak learner, calculating the error, calculating the confidence / amount of say of the learner, updating the sample weights. However, I'm not 100% sure about the last step of resampling for the next iteration -- I'm aware that the alternative is to directly consider the updated weights if learner uses the weighting information during training (which not all learner support).

Let's assume I have a dataset X = [x1,x2,x3,x4,x5] so my initial "sample" is simply D_0 = X with all sample weights initialized with 1/5. Now let's assume that my first learner misclassifies x1 and x2. This means that the sample weights for x1 and x2 increase (all others decrease). Now I can sample D_1 from D_0 using the new sample weight, resulting in, say, D_1 = [x2, x1, x1, x5, x2]. I also re-initialize all the sample weights in D_1 with 1/5, right?

As far as I understand, now I do the same steps -- fitting a weak learner, calculating the error, calculating the confidence / amount of say of the learner, updating the sample weights -- for D_1.

But now my questions is: How do I sample D_2?

• Sampling from D_1 is straightforward but would mean that D_2 could never include sample x4 from the original dataset. That feels kind of odd to me.

• Sampling from D_0 would give all samples a chance to be picked, but than it's not clear to me how to use the weights. Firstly, D_2 gives me no weight for x4 and some samples (here: x1 and x2) are duplicated in D_2.

Or maybe I'm missing something more fundamental. Unfortunately, all examples/tutorials/illustrations/etc. I've found only go from D_0 to D_1 using sampling but then stop and it's simply not clear to me how to get from D_1 to D_2 and so on.

• Is resampling necessary to AdaBoost? I could not understand what is our expectation of D_m for next iteration. Commented Mar 2, 2022 at 12:22
• I'm aware that the alternative is to directly consider the updated weights if learner uses the weighting information during training (which not all learner support). That's how you do it. You keep updating the weights in the same way, but instead of using the weights to calculate a weighted GI metric, you draw from the original dataset where each sample is chosen with probability proportional to the weights. Commented Mar 8, 2022 at 19:48