11BoostingMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityOctober 5th, 2009©Carlos Guestrin 2005-20092Fighting 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-200923Voting (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-20094Boosting 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[Schapire, 1989]©Carlos Guestrin 2005-200935Learning 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-20096weakweak©Carlos Guestrin 2005-200947©Carlos Guestrin 2005-20098Training error of final classifier is bounded by:Where What αtto choose for hypothesis ht?[Schapire, 1989]©Carlos Guestrin 2005-200959Training error of final classifier is bounded by:Where What αtto choose for hypothesis ht?[Schapire, 1989]©Carlos Guestrin 2005-200910Training error of final classifier is bounded by:Where If we minimize ∏∏∏∏tZt, we minimize our training errorWe can tighten this bound greedily, by choosing αtand hton each iteration to minimize Zt.What αtto choose for hypothesis ht?[Schapire, 1989]©Carlos Guestrin 2005-2009611What αtto choose for hypothesis ht?We can minimize this bound by choosing αton each iteration to minimize Zt.For boolean target function, this is accomplished by [Freund & Schapire ’97]: You’ll prove this in your homework! ☺[Schapire, 1989]©Carlos Guestrin 2005-200912Strong, 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-2009713Boosting results – Digit recognition Boosting often Robust to overfitting Test set error decreases even after training error is zero[Schapire, 1989]©Carlos Guestrin 2005-200914Boosting generalization error bound T – number of boosting rounds d – VC dimension of weak learner, measures complexity of classifier m – number of training examples[Freund & Schapire, 1996]©Carlos Guestrin 2005-2009815Boosting generalization error bound T – number of boosting rounds d – VC dimension of weak learner, measures complexity of classifier m – number of training examples[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©Carlos Guestrin 2005-200916Boosting: Experimental ResultsComparison of C4.5, Boosting C4.5, Boosting decision stumps (depth 1 trees), 27 benchmark datasets[Freund & Schapire, 1996]errorerrorerror©Carlos Guestrin 2005-2009917©Carlos Guestrin 2005-200918Boosting and Logistic RegressionLogistic regression assumes:And tries to maximize data likelihood:Equivalent to minimizing log loss©Carlos Guestrin 2005-20091019Boosting and Logistic RegressionLogistic regression equivalent to minimizing log lossBoosting minimizes similar loss function!!Both smooth approximations of 0/1 loss!©Carlos Guestrin 2005-200920Logistic regression and BoostingLogistic regression: Minimize loss fn Define where xjpredefinedBoosting: Minimize loss fn Define where ht(xi) defined dynamically to fit data(not a linear classifier) Weights αjlearned incrementally©Carlos Guestrin 2005-20091121What 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©Carlos Guestrin
View Full Document
Unlocking...