AdaboostTutorial.pptVIP

Adaboost Derek Hoiem March 31, 2004 Outline Background Adaboost Algorithm Theory/Interpretations Practical Issues Face detection experiments What’s So Good About Adaboost Improves classification accuracy Can be used with many different classifiers Commonly used in many areas Simple to implement Not prone to overfitting A Brief History Bootstrapping Bagging Boosting (Schapire 1989) Adaboost (Schapire 1995) Bootstrap Estimation Repeatedly draw n samples from D For each set of samples, estimate a statistic The bootstrap estimate is the mean of the individual estimates Used to estimate a statistic (parameter) and its variance Bagging - Aggregate Bootstrapping For i = 1 .. M Draw n*n samples from D with replacement Learn classifier Ci Final classifier is a vote of C1 .. CM Increases classifier stability/reduces variance Boosting (Schapire 1989) Randomly select n1 n samples from D without replacement to obtain D1 Train weak learner C1 Select n2 n samples from D with half of the samples misclassified by C1 to obtain D2 Train weak learner C2 Select all samples from D that C1 and C2 disagree on Train weak learner C3 Final classifier is vote of weak learners Adaboost - Adaptive Boosting Instead of sampling, re-weight Previous weak learner has only 50% accuracy over new distribution Can be used to learn weak classifiers Final classification based on weighted vote of weak classifiers Adaboost Terms Learner = Hypothesis = Classifier Weak Learner: 50% error over any distribution Strong Classifier: thresholded linear combination of weak learner outputs Discrete Adaboost (DiscreteAB)(Friedman’s wording) Discrete Adaboost (DiscreteAB)(Freund and Schapire’s wording) Adaboost with Confidence Weighted Predictions (RealAB) Comparison Bound on Training Error (Schapire) Finding a weak hypothesis Train classifier (as usual) on weighted training data Some weak learners can minimize Z by gradient descent Sometimes we can ignore alpha (when the weak lea