AdaBoost: Re-weighting Data to Stack Weak Classifiers into a Strong One | NTU Hsuan-Tien Lin Machine Learning Techniques Lecture 8
This lecture re-reads bagging's bootstrap as putting a weight on every example, then deliberately tunes the weights so that the previous round's gₜ has a weighted error rate of exactly 1/2, which forces the next round to learn a different hypothesis. The recipe multiplies incorrect examples by ◆ₜ = √((1−εₜ)/εₜ), divides correct ones by it, and uses αₜ = ln ◆ₜ as the vote weight in a linear vote. That is AdaBoost. As long as the base algorithm is a little better than random guessing in every round, E_in drops to 0 within O(log N) rounds; with decision stumps, three hand-computed rounds on six examples are enough to see it.