Boosting Rong Jin Inefficiency with Bagging Bagging Inefficiency with boostrap sampling D Every example has equal chance to be sampled No distinction between easy examples and difficult examples Boostrap Sampling D1 D2 Dk Inefficiency with model combination weight for each classifier No distinction between accurate classifiers and inaccurate classifiers h1 h2 A constant i Pr c hi x hk Improve the Efficiency of Bagging Better sampling strategy Focus on the examples that are difficult to classify correctly Better combination strategy Accurate model should be assigned with more weights Intuition Education in China X1 Y1 X2 Y2 X3 Y3 Mistakes X4 Y4 X1 X3 Y1 Y3 Mistakes X1 Y1 Classifier 3 No training mistakes Training Example s Classifier 2 May overfitting to training data Classifier1 AdaBoost Algorithm AdaBoost Example t ln2 D0 h1 D1 h2 D2 x1 y1 x 2 y 2 x3 y 3 x4 y4 x5 y5 1 5 1 5 1 5 1 5 1 5 x1 y1 x 2 y 2 x3 y 3 x4 y4 x5 y5 2 7 1 7 1 7 2 7 1 7 x1 y1 x3 y3 x5 y 5 Training Update Weights Sample h1 x1 y1 x3 y3 Training x1 y1 x 2 y 2 x 3 y 3 x4 y 4 x5 y5 Update Weights 2 9 1 9 1 9 4 9 1 9 Sample Sample h2 How To Choose t in AdaBoost Consider how to construct the best distribution D t 1 i given Dt i and ht 1 Dt 1 i should be significantly differen from D t i 2 Dt 1 i should create a situation that classifier h t performs poorly Dt 1 arg max KL D Dt D 0 1 m arg max D i ln D 0 1 m i D i Dt i s t i D i 1 i ht i yi D i 1 2 1 1 rt a t ln 2 1 rt rt i ht i yi D i Optimization View for Choosing t ht x x 1 1 a basis weak classifier HT x a linear combination of basic classifiers H T x a1h1 x a 2 h2 x a T hT x H T 1 x a T hT x Goal minimize training error err 1 N N I i 1 H T xi yi Approximate the training error with a exponential function 1 err N N i 1 exp H T xi yi AdaBoost A Greedy Approach to Optimize the Exponential Function Exponential cost function 1 N N i 1 exp HT xi yi Use the inductive form HT x HT 1 x ThT x 1 1 iN 1 exp H T xi yi iN 1 exp H T 1 xi yi exp T hT xi yi N N 1 iN 1 exp H T 1 xi yi exp T I hT xi yi N 1 iN 1 exp H T 1 xi yi exp T I hT xi yi N err AdaBoost A Greedy Approach to Optimize the Exponential Function Exponential cost function 1 N N i 1 exp HT xi yi Use the inductive form HT x HT 1 x ThT x Data points that hT x 1 1 correctly err iN 1 exp H T xi yi iN 1 exp Hpredict T 1 xi y i exp T hT xi y i N N Data points that hT x 1 iN 1 exp H T 1 xi yi exp T I hT xipredict yi incorrectly N 1 iN 1 exp H T 1 xi yi exp T I hT xi yi N Minimize the exponential function 1 rt D x exp t ht xi yi 1 t ln and Dt 1 xi t i 2 1 rt Zt AdaBoost is a greedy approach overfitting Empirical studies show that AdaBoost is robust in general AdaBoost tends to overfit with noisy data Empirical Study of AdaBoost AdaBoosting decision trees Generate 50 decision trees through the AdaBoost procedure Linearly combine decision trees using the weights computed by the AdaBoost Algorithm In general AdaBoost Bagging C4 5 AdaBoost usually needs less number of classifiers than Bagging Bia Variance Tradeoff for AdaBoost AdaBoost can reduce both model variance and model bias variance bias single decision tree Bagging decision tree AdaBoosting decision trees