Computational Learning Theory 10 701 15 781 Recitation March 25 2010 Ni Lao What s Computational Learning Theory Laws about whether we can perform learning successfully or not Instead of relying purely on empirical knowledge our skills in probability can help Often in the form of the following question With a family of models H of certain complexity how many training samples R is needed in order to learn a model h with reasonable training time and sufficient accuracy on future data Major components Model complexity Num of parameters Size of hypothesis space VC dimension Sample complexity Error rate Time complexity What We Have Learnt in Class For categorical inputs PAC Learning Probably Approximately Correct Learning All inputs and outputs are binary easy to measure H Data is noiseless easy to analyze For continuous inputs VC dimension a hypothesis family H can shatter a set of points x1 x2 xr iff for every possible label y1 y2 yr 2r of them there exists some hypothesis h in H that can gets zero training error VC H is the maximum number of points that can be shattered by H Example PAC Learning of Boolean Functions Chose number of samples R such that with probability less than we ll select a bad hypothesis which makes mistakes more than fraction of the time l rma o N ctive n u j Dis DNF Form R b H g 2 o l a 2001 Andrew W Moore Example VCd of Circle Hypothesis H f x b sign x x b VC H N 1 N 2 2001 Andrew W Moore Example VCd of Circle Hypothesis H f x a b sign ax x b VC H N 2 N 3 n Ofte No VC H er t e m a Par 2001 Andrew W Moore Homework 4 VCd of Gaussian Bayes Models Practice your VCd finding skills in two class classification problems Homework 4 Linear Regression Model express the average risk R n for linear regression 0 as a function of features p and samples n Result from hw3 slightly revised Summary of Model Selection Methods VC dimension Structural Risk Minimization Very conservative AIC Akaike Information Criterion Asymptotically the same as Leave one out CV BIC Bayesian Information Criterion Asymptotically the same as a carefully chosen k fold CV CV Cross validation The ultimate weapon used by most people who apply ML techniques The End Thanks
View Full Document
Unlocking...