Simple Model Selection Cross Validation Regularization Neural Networks Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University February 13th 2007 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 2 1 Test set error as a function of model complexity 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 9 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 2005 2007 Carlos Guestrin 10 5 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 2005 2007 Carlos Guestrin 11 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 In homework you ll prove that LOO is unbiased estimate of errortrue m 1 Great news Use LOO error for model selection 2005 2007 Carlos Guestrin 12 6 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 2005 2007 Carlos Guestrin 13 Using LOO error for model selection 2005 2007 Carlos Guestrin 14 7 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 2005 2007 Carlos Guestrin 15 Solution 2 to complexity of computing LOO More typical Use k fold cross validation Randomly divide training data into k equal parts For each i D1 Dk 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 2005 2007 Carlos Guestrin 16 8 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 2005 2007 Carlos Guestrin 17 Regularization in linear regression Overfitting usually leads to very large parameter choices e g 2 2 3 1 X 0 30 X2 1 1 4 700 910 7 X 8 585 638 4 X2 Regularized least squares a k a ridge regression for 0 2005 2007 Carlos Guestrin 18 9 Other regularization examples Logistic regression regularization Maximize data likelihood minus penalty for large parameters Biases towards small parameter values Na ve Bayes regularization Prior over likelihood of features Biases away
View Full Document
Unlocking...