BOOSTING
(ADABOOST ALGORITHM)
Eric Emer
Consider Horse-Racing Gambler
• Rules of Thumb for determining Win/Loss:
• Most favored odds
• Fastest recorded lap time
• Most wins recently, say, in the past 1 month
• Hard to determine how he combines analysis of feature
set into a single bet.
Consider MIT Admissions
• 2-class system (Admit/Deny)
• Both Quantitative Data and Qualitative Data
• We consider (Y/N) answers to be Quantitative (-1,+1)
• Region, for instance, is qualitative.
Rules of Thumb, Weak Classifiers
• Easy to come up with rules of thumb that correctly classify the training data at
better than chance.
• E.g. IF “GoodAtMath”==Y THEN predict “Admit”.
• Difficult to find a single, highly accurate prediction rule. This is where our Weak
Learning Algorithm, AdaBoost, helps us.
What is a Weak Learner?
• For any distribution, with high probability, given
polynomially many examples and polynomial time we can
