DOC PREVIEW
CMU CS 10701 - Simple Model Selection Cross Validation Regularization

This preview shows page 1-2-3-4-5 out of 14 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

11Simple Model SelectionCross ValidationRegularizationMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityOctober 7th, 2009©Carlos Guestrin 2005-2009OK… 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-Validation2©Carlos Guestrin 2005-20092Test set error as a function of model complexity3©Carlos Guestrin 2005-2009Simple 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., Xjthat results in lowest training errorlearner when learning with Ft∪ {Xj} Ft+1←Ft ∪ {Xi*} Recurse4©Carlos Guestrin 2005-20093Greedy 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 something cool about it e.g., [Krause & Guestrin ’05]: Near-optimal in some settings that include Naïve Bayes There are many more elaborate methods out there5©Carlos Guestrin 2005-2009Simple greedy model selection algorithm Greedy heuristic: … Select next best feature Xi* e.g., Xjthat results in lowest training errorlearner when learning with Ft∪ {Xj} Ft+1←Ft ∪ {Xi*} RecurseWhen do you stop??? When training error is low enough? 6©Carlos Guestrin 2005-20094Simple greedy model selection algorithm Greedy heuristic: … Select next best feature Xi* e.g., Xjthat results in lowest training errorlearner when learning with Ft∪ {Xj} Ft+1←Ft ∪ {Xi*} RecurseWhen do you stop??? When training error is low enough? When test set error is low enough? 7©Carlos Guestrin 2005-2009Validation set Thus far: Given a dataset, randomly split it into two parts:  Training data – {x1,…, xNtrain} Test data – {x1,…, xNtest} But Test data must always remain independent! Never ever ever ever learn on test data, including for model selection Given a dataset, randomly split it into three parts:  Training data – {x1,…, xNtrain} Validation data – {x1,…, xNvalid} Test data – {x1,…, xNtest} Use validation data for tuning learning algorithm, e.g., model selection Save test data for very final evaluation8©Carlos Guestrin 2005-20095Simple greedy model selection algorithm Greedy heuristic: … Select next best feature Xi* e.g., Xjthat results in lowest training errorlearner when learning with Ft∪ {Xj} Ft+1←Ft ∪ {Xi*} RecurseWhen do you stop??? When training error is low enough? When test set error is low enough? When validation set error is low enough? 9©Carlos Guestrin 2005-2009Validating a learner, not a hypothesis (disclaimer: intuition only, not proof) With a validation set, get to estimate error of 1 hypothesis on 1 dataset Need to estimate error of learner over multiple datasets to select parameter  Think variance ©Carlos Guestrin 2005-2009 106Simple greedy model selection algorithm Greedy heuristic: … Select next best feature Xi* e.g., Xjthat results in lowest training errorlearner when learning with Ft∪ {Xj} Ft+1←Ft ∪ {Xi*} RecurseWhen do you stop??? When training error is low enough? When test set error is low enough? When validation set error is low enough? Man!!! OK, should I just repeat until I get tired??? I am tired now… No, “There is a better way!”11©Carlos Guestrin 2005-2009(LOO) Leave-one-out cross validation Consider a validation set with 1 example: D – training data D\i – training data with i th data point moved to validation set Learn classifier hD\iwith D\i dataset Estimate true error as: 0 if hD\iclassifies i th data point correctly 1 if hD\iis wrong about i th data point Seems really bad estimator, but wait! LOO cross validation: Average over all data points i: For each data point you leave out, learn a new classifier hD\i Estimate error as: 12©Carlos Guestrin 2005-20097LOO cross validation is (almost) unbiased estimate of true error! When computing LOOCV error, we only use m-1 data points So it’s not estimate of true error of learning with m data points! Usually pessimistic, though – learning with less data typically gives worse answer LOO is almost unbiased! Let errortrue,m-1be true error of learner when you only get m-1 data points LOO is unbiased estimate of errortrue,m-1: Great news! Use LOO error for model selection!!!13©Carlos Guestrin 2005-2009Simple greedy model selection algorithm Greedy heuristic: … Select next best feature Xi* e.g., Xjthat results in lowest training errorlearner when learning with Ft∪ {Xj} Ft+1←Ft ∪ {Xi*} RecurseWhen do you stop??? When training error is low enough? When test set error is low enough? When validation set error is low enough? STOP WHEN errorLOOIS LOW!!!14©Carlos Guestrin 2005-20098Using LOO error for model selection15©Carlos Guestrin 2005-2009Computational cost of LOO Suppose you have 100,000 data points You implemented a great version of your learning algorithm Learns in only 1 second  Computing LOO will take about 1 day!!! If you have to do for each choice of basis functions, it will take fooooooreeeve’!!! Solution 1: Preferred, but not usually possible Find a cool trick to compute LOO (e.g., see homework)16©Carlos Guestrin 2005-20099Solution 2 to complexity of computing LOO: (More typical) Use k-fold cross validation Randomly divide training data into k equal parts D1,…,Dk For each i Learn classifier hD\Diusing data point not in Di  Estimate error of hD\Dion


View Full Document

CMU CS 10701 - Simple Model Selection Cross Validation Regularization

Documents in this Course
lecture

lecture

12 pages

lecture

lecture

17 pages

HMMs

HMMs

40 pages

lecture

lecture

15 pages

lecture

lecture

20 pages

Notes

Notes

10 pages

Notes

Notes

15 pages

Lecture

Lecture

22 pages

Lecture

Lecture

13 pages

Lecture

Lecture

24 pages

Lecture9

Lecture9

38 pages

lecture

lecture

26 pages

lecture

lecture

13 pages

Lecture

Lecture

5 pages

lecture

lecture

18 pages

lecture

lecture

22 pages

Boosting

Boosting

11 pages

lecture

lecture

16 pages

lecture

lecture

20 pages

Lecture

Lecture

20 pages

Lecture

Lecture

39 pages

Lecture

Lecture

14 pages

Lecture

Lecture

18 pages

Lecture

Lecture

13 pages

Exam

Exam

10 pages

Lecture

Lecture

27 pages

Lecture

Lecture

15 pages

Lecture

Lecture

24 pages

Lecture

Lecture

16 pages

Lecture

Lecture

23 pages

Lecture6

Lecture6

28 pages

Notes

Notes

34 pages

lecture

lecture

15 pages

Midterm

Midterm

11 pages

lecture

lecture

11 pages

lecture

lecture

23 pages

Boosting

Boosting

35 pages

Lecture

Lecture

49 pages

Lecture

Lecture

22 pages

Lecture

Lecture

16 pages

Lecture

Lecture

18 pages

Lecture

Lecture

35 pages

lecture

lecture

22 pages

lecture

lecture

24 pages

Midterm

Midterm

17 pages

exam

exam

15 pages

Lecture12

Lecture12

32 pages

lecture

lecture

19 pages

Lecture

Lecture

32 pages

boosting

boosting

11 pages

pca-mdps

pca-mdps

56 pages

bns

bns

45 pages

mdps

mdps

42 pages

svms

svms

10 pages

Notes

Notes

12 pages

lecture

lecture

42 pages

lecture

lecture

29 pages

lecture

lecture

15 pages

Lecture

Lecture

12 pages

Lecture

Lecture

24 pages

Lecture

Lecture

22 pages

Midterm

Midterm

5 pages

mdps-rl

mdps-rl

26 pages

Load more
Download Simple Model Selection Cross Validation Regularization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Simple Model Selection Cross Validation Regularization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Simple Model Selection Cross Validation Regularization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?