Boosting Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University October 5th 2009 Carlos Guestrin 2005 2009 1 Fighting the bias variance tradeoff Simple a k a weak learners are good e g na ve Bayes logistic regression decision stumps or shallow decision trees Low variance don t usually overfit Simple a k a weak learners are bad High bias can t solve hard learning problems Can we make weak learners always good No But often yes Carlos Guestrin 2005 2009 2 1 Voting Ensemble Methods Instead of learning a single weak classifier learn many weak classifiers that are good at different parts of the input space Output class Weighted vote of each classifier Classifiers that are most sure will vote with more conviction Classifiers will be most sure about a particular part of the space On average do better than single classifier But how do you force classifiers to learn about different parts of the input space weigh the votes of different classifiers Carlos Guestrin 2005 2009 Boosting Schapire 1989 Idea given a weak learner run it multiple times on reweighted training data then let learned classifiers vote On each iteration t weight each training example by how incorrectly it was classified Learn a hypothesis ht A strength for this hypothesis t Final classifier Practically useful Theoretically interesting 3 Carlos Guestrin 2005 2009 4 2 Learning from weighted data Sometimes not all data points are equal Some data points are more equal than others Consider a weighted dataset D i weight of i th training example xi yi Interpretations i th training example counts as D i examples If I were to resample data I would get more samples of heavier data points Now in all calculations whenever used i th training example counts as D i examples e g MLE for Na ve Bayes redefine Count Y y to be weighted count Carlos Guestrin 2005 2009 5 Carlos Guestrin 2005 2009 6 weak weak 3 Carlos Guestrin 2005 2009 7 What t to choose for hypothesis ht Schapire 1989 Training error of final classifier is bounded by Where Carlos Guestrin 2005 2009 8 4 What t to choose for hypothesis ht Schapire 1989 Training error of final classifier is bounded by Where Carlos Guestrin 2005 2009 9 What t to choose for hypothesis ht Schapire 1989 Training error of final classifier is bounded by Where If we minimize t Zt we minimize our training error We can tighten this bound greedily by choosing t and ht on each iteration to minimize Zt Carlos Guestrin 2005 2009 10 5 What t to choose for hypothesis ht Schapire 1989 We can minimize this bound by choosing t on each iteration to minimize Zt For boolean target function this is accomplished by Freund Schapire 97 You ll prove this in your homework Carlos Guestrin 2005 2009 11 Strong weak classifiers If each classifier is at least slightly better than random t 0 5 AdaBoost will achieve zero training error exponentially fast Is it hard to achieve better than random training error Carlos Guestrin 2005 2009 12 6 Boosting results Digit recognition Schapire 1989 Boosting often Robust to overfitting Test set error decreases even after training error is zero Carlos Guestrin 2005 2009 13 Boosting generalization error bound Freund Schapire 1996 T number of boosting rounds d VC dimension of weak learner measures complexity of classifier m number of training examples Carlos Guestrin 2005 2009 14 7 Boosting generalization error bound Freund Schapire 1996 Contradicts Boosting often Robust to overfitting Test set error decreases even after training error is zero Need better analysis tools we ll T number of boosting rounds d VC dimension of weak learner measures complexity of classifier m number of training examples Carlos Guestrin 2005 2009 15 Boosting Experimental Results Freund Schapire 1996 Comparison of C4 5 Boosting C4 5 Boosting decision stumps depth 1 trees 27 benchmark datasets error come back to this later in the semester error error Carlos Guestrin 2005 2009 16 8 Carlos Guestrin 2005 2009 17 Boosting and Logistic Regression Logistic regression assumes And tries to maximize data likelihood Equivalent to minimizing log loss Carlos Guestrin 2005 2009 18 9 Boosting and Logistic Regression Logistic regression equivalent to minimizing log loss Boosting minimizes similar loss function Both smooth approximations of 0 1 loss Carlos Guestrin 2005 2009 19 Logistic regression and Boosting Logistic regression Minimize loss fn Define Boosting Minimize loss fn Define where ht xi defined dynamically to fit data where xj predefined not a linear classifier Weights j learned incrementally Carlos Guestrin 2005 2009 20 10 What you need to know about Boosting Combine weak classifiers to obtain very strong classifier AdaBoost algorithm Boosting v Logistic Regression Weak classifier slightly better than random on training data Resulting very strong classifier can eventually provide zero training error Similar loss functions Single optimization LR v Incrementally improving classification B Most popular application of Boosting Boosted decision stumps Very simple to implement very effective classifier Carlos Guestrin 2005 2009 21 11
View Full Document
Unlocking...