Boosting Linked from class website Schapire 01 Boosting Simple Model Selection Cross Validation Regularization Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University February 8th 2006 2006 Carlos Guestrin 1 Announcements Recitations stay on Thursdays 5 6 30pm in Wean 5409 This week Decision Trees and Boosting Homework due Tomorrow by 10 30am class time to Monica Hopes Wean Hall 4616 2006 Carlos Guestrin 2 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 2006 Carlos Guestrin 3 Voting 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 2006 Carlos Guestrin 4 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 2006 Carlos Guestrin 5 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 2006 Carlos Guestrin 6 2006 Carlos Guestrin 7 2006 Carlos Guestrin 8 What t to choose for hypothesis ht Schapire 1989 Training error of final classifier is bounded by Where 2006 Carlos Guestrin 9 What t to choose for hypothesis ht Schapire 1989 Training error of final classifier is bounded by Where 2006 Carlos Guestrin 10 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 2006 Carlos Guestrin 11 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 2006 Carlos Guestrin 12 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 2006 Carlos Guestrin 13 Boosting results Digit recognition Schapire 1989 Boosting often Robust to overfitting Test set error decreases even after training error is zero 2006 Carlos Guestrin 14 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 2006 Carlos Guestrin 15 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 come back to this later in the semester T number of boosting rounds d VC dimension of weak learner measures complexity of classifier m number of training examples 2006 Carlos Guestrin 16 Boosting Experimental Results Freund Schapire 1996 Comparison of C4 5 Boosting C4 5 Boosting decision stumps depth 1 trees 27 benchmark datasets 2006 Carlos Guestrin 17 2006 Carlos Guestrin 18 Boosting and Logistic Regression Logistic regression assumes And tries to maximize data likelihood Equivalent to minimizing log loss 2006 Carlos Guestrin 19 Boosting and Logistic Regression Logistic regression equivalent to minimizing log loss Boosting minimizes similar loss function Both smooth approximations of 0 1 loss 2006 Carlos Guestrin 20 Logistic regression and Boosting Logistic regression Minimize loss fn Boosting Minimize loss fn Define Define where xj predefined where h xi defined dynamically to fit data Weights j learned incrementally 2006 Carlos Guestrin 21 What you need to know about Boosting Combine weak classifiers to obtain very strong classifier Weak classifier slightly better than random on training data Resulting very strong classifier can eventually provide zero training error AdaBoost algorithm Boosting v Logistic Regression 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 2006 Carlos Guestrin 22 OK now we ll learn to pick those darned parameters Selecting features or basis functions Linear regression Na ve Bayes Logistic regression Selecting parameter value Prior strength Na ve Bayes linear and logistic regression Regularization strength Na ve Bayes linear and logistic regression Decision trees MaxpChance depth number of leaves Boosting Number of rounds More generally these are called Model Selection Problems Today Describe basic idea Introduce very important concept for tuning learning approaches Cross Validation 2006 Carlos Guestrin 23 Test set error as a function of model complexity 2006 Carlos Guestrin 24 Simple greedy model selection algorithm Pick a dictionary of features e g polynomials for linear regression Greedy heuristic Start from empty or simple set of features F0 Run learning algorithm for current set of features Ft Obtain ht Select next best feature Xi e g Xj that results in lowest training error learner when learning with Ft Xj Ft 1 Ft Xi Recurse 2006 Carlos Guestrin 25 Greedy model selection Applicable in many settings Linear regression Selecting basis functions Na ve Bayes Selecting independent features P Xi Y Logistic regression Selecting features basis functions Decision trees Selecting leaves to expand Only a heuristic But sometimes you can prove
View Full Document
Unlocking...