Neural Nets Many possible refs e g Mitchell Chapter 4 Simple Model Selection Cross Validation Regularization Neural Networks Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University February 13th 2006 2006 Carlos Guestrin 1 Announcements Recitations stay on Thursdays 5 6 30pm in Wean 5409 This week Cross Validation and Neural Nets Homework 2 Due next Monday Feb 20th Updated version online with more hints Start early 2006 Carlos Guestrin 2 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 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 Validation 2006 Carlos Guestrin 3 Test set error as a function of model complexity 2006 Carlos Guestrin 4 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 2006 Carlos Guestrin 5 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 2006 Carlos Guestrin 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 2006 Carlos Guestrin 7 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 2006 Carlos Guestrin 8 Validation 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 evaluation 2006 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 2006 Carlos Guestrin 10 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 2006 Carlos Guestrin 11 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 i with D i dataset Estimate true error as 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 2006 Carlos Guestrin 12 LOO 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 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 2006 Carlos Guestrin 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 2006 Carlos Guestrin 14 Using LOO error for model selection 2006 Carlos Guestrin 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 2006 Carlos Guestrin 16 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 2006 Carlos Guestrin 17 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 2006 Carlos Guestrin 18 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 2006 Carlos Guestrin 19 Other regularization examples Logistic regression regularization
View Full Document
Unlocking...