1©2005-2007 Carlos Guestrin1Simple Model SelectionCross ValidationRegularizationNeural NetworksMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityFebruary 13th, 2007©2005-2007 Carlos Guestrin2OK… now we’ll learn to pick thosedarned 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©2005-2007 Carlos Guestrin3Test set error as a function ofmodel complexity©2005-2007 Carlos Guestrin4Simple greedy model selection algorithm Pick a dictionary of features e.g., polynomials for linear regression Greedy heuristic: Start from empty (or simple) set offeatures F0 = ∅ Run learning algorithm for current setof features Ft Obtain ht Select next best feature Xi e.g., Xj that results in lowest training errorlearner when learning with Ft [ {Xj} Ft+1 Ã Ft [ {Xi} Recurse3©2005-2007 Carlos Guestrin5Greedy 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 thatinclude Naïve Bayes There are many more elaborate methods out there©2005-2007 Carlos Guestrin6Simple greedy model selection algorithm Greedy heuristic: … Select next best feature Xi e.g., Xj that results in lowest training errorlearner when learning with Ft [ {Xj} Ft+1 Ã Ft [ {Xi} RecurseWhen do you stop??? When training error is low enough?4©2005-2007 Carlos Guestrin7Simple greedy model selection algorithm Greedy heuristic: … Select next best feature Xi e.g., Xj that 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?©2005-2007 Carlos Guestrin8Validation 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., modelselection Save test data for very final evaluation5©2005-2007 Carlos Guestrin9Simple greedy model selection algorithm Greedy heuristic: … Select next best feature Xi e.g., Xj that 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?©2005-2007 Carlos Guestrin10Simple greedy model selection algorithm Greedy heuristic: … Select next best feature Xi e.g., Xj that 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!”6©2005-2007 Carlos Guestrin11(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:©2005-2007 Carlos Guestrin12LOO 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!!!7©2005-2007 Carlos Guestrin13Simple greedy model selection algorithm Greedy heuristic: … Select next best feature Xi e.g., Xj that 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 errorLOO IS LOW!!!©2005-2007 Carlos Guestrin14Using LOO error for model selection8©2005-2007 Carlos Guestrin15Computational cost of LOO Suppose you have 100,000 data points You implemented a great version of your learningalgorithm Learns in only 1 second Computing LOO will take about 1 day!!! If you have to do for each choice of basis functions, it willtake fooooooreeeve’!!! Solution 1: Preferred, but not usually possible Find a cool trick to compute LOO (e.g., see homework)©2005-2007 Carlos Guestrin16Solution 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
View Full Document
Unlocking...