Model and feature selection10601Machine LearningModel selection issues• We have seen some of this before …• Selecting features (or basis functions)– Linear regression– Logistic regression– SVMs• Selecting parameter value– Prior strength • Naïve Bayes, linear and logistic regression– Regularization strength• Naïve Bayes, linear and logistic regression– Decision trees• depth, number of leaves– Boosting• Number of rounds• More generally, these are called Model Selection Problems2Training and test set error as a function of model complexitySimple 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 error learner whenlearning with Ft {Xj}– Ft+1 Ft {Xi*}– Recurse4Greedy 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 it5Simple greedy model selection algorithm• Greedy heuristic:– …– Select next best feature Xi*• e.g., Xjthat results in lowest training error learnerwhen 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? 6Validation 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 evaluation7Simple greedy model selection algorithm• Greedy heuristic:– …– Select next best feature Xi*• e.g., Xjthat results in lowest training error learnerwhen 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?8Sometimes, but there is an even better option …Validating a learner, not a hypothesis (intuition only, not proof)• With a validation set, get to estimate error of 1 hypothesis on 1 dataset- e.g. Should I use a polynomial of degree 3 or 4• Need to estimate error of learner over multiple datasets to select parameters9][},{ tyxhEExpected error over all datasets(LOO) Leave-one-out cross validation• Consider a validation set with 1 example:– D – training data– D\i – training data with ith data point moved to validation set• Learn classifier hD\iwith D\i dataset• Estimate true error as:– 0 if hD\iclassifies ith 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: 10LOO 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!!!11Simple greedy model selection algorithm• Greedy heuristic:– …– Select next best feature Xi*• e.g., Xjthat results in lowest training error learnerwhen 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!!!12LOO cross validation errorComputational 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 forever!14Solution: 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 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)/k15Regularization• Model selection 1 (using CV): Greedy– Pick subset of features that have yield low LOO error• Model selection 2: Regularization– Include all possible features!– Penalize “complicated” hypothesis16Regularization in linear regression• Overfitting usually leads to very large parameter choices, e.g.:• Regularized least-squares (a.k.a. ridge regression):-2.2 + 3.1 X – 0.30 X2-1.1 + 4,700,910.7 X – 8,585,638.4 X2+ …17iijjjTwwyxw22)w(minarg*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 from zero probability outcomes• Decision tree regularization– Many possibilities, e.g., Chi-Square test– Biases towards smaller trees• Sparsity: find good solution with few basis functions, e.g.:– Simple greedy model selection from earlier in the lecture– L1 regularization, e.g.:18For example, the Beta distribution we discussediijjjTwwyxw ||)w(minarg*2How do we pick magic parameter ?Cross Validation!!!19Regularization and Bayesian learning• For example, if we assume a zero mean, Gaussian prior for win a logistic regression classification we would end up with an L2 regularization- Why?- Board …- What is ?• Similar
View Full Document
Unlocking...