Simple Model Selection Cross Validation Regularization Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University October 7th 2009 Carlos Guestrin 2005 2009 1 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 Regularization strength Decision trees Boosting Na ve Bayes linear and logistic regression Na ve Bayes linear and logistic regression MaxpChance depth number of leaves 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 Carlos Guestrin 2005 2009 2 1 Test set error as a function of model complexity Carlos Guestrin 2005 2009 3 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 Carlos Guestrin 2005 2009 4 2 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 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 there Carlos Guestrin 2005 2009 5 Simple greedy model selection algorithm Greedy heuristic 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 When do you stop When training error is low enough Carlos Guestrin 2005 2009 6 3 Simple greedy model selection algorithm Greedy heuristic 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 When do you stop When training error is low enough When test set error is low enough Carlos Guestrin 2005 2009 7 Validation set Thus far Given a dataset randomly split it into two parts 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 Test data x1 xNtest 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 evaluation Carlos Guestrin 2005 2009 8 4 Simple greedy model selection algorithm Greedy heuristic 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 When do you stop When training error is low enough When test set error is low enough When validation set error is low enough Carlos Guestrin 2005 2009 9 Validating 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 10 5 Simple greedy model selection algorithm Greedy heuristic 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 When 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 Carlos Guestrin 2005 2009 11 LOO Leave one out cross validation Consider a validation set with 1 example Learn classifier hD i with D i dataset Estimate true error as D training data D i training data with i th data point moved to validation set 0 if hD i classifies i th data point correctly 1 if hD i is 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 Carlos Guestrin 2005 2009 12 6 LOO cross validation is almost unbiased estimate of true error When computing LOOCV error we only use m 1 data points LOO is almost unbiased 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 Let errortrue m 1 be 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 Carlos Guestrin 2005 2009 13 Simple greedy model selection algorithm Greedy heuristic 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 When 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 errorLOO IS LOW Carlos Guestrin 2005 2009 14 7 Using LOO error for model selection Carlos Guestrin 2005 2009 15 Computational 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 Carlos Guestrin 2005 2009 16 8 Solution 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 Di using data point not in Di Estimate error of hD Di on validation set Di k fold cross validation error is average over data splits k fold cross validation properties Much faster to compute than LOO More pessimistically biased using much less data only m k 1 k Usually k 10 Carlos Guestrin 2005 2009 17 Announcements Midterm Wean 7500 on Thursday Oct 29 5 7pm Office hours Please be mindful of your TAs and limit interruptions to office hours Carlos Guestrin 2005 2009 18 9 Regularization Revisited Model selection 1 Greedy Pick subset of features that have yield low LOO error Model selection 2 Regularization Include all possible features Penalize complicated hypothesis Carlos Guestrin 2005 2009 19 Regularization in linear regression Overfitting usually leads to very large
View Full Document
Unlocking...