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 regressionSelecting 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 roundsMore generally, these are called Model Selection ProblemsToday: 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