VC Dimension Midterm Recap PAC Bounds Suppose a consistent learner has hypothesis space H Then for any h in H with 0 training error P error true h m ln H ln 1 m is training examples H measures the flexibility of the classifier Problem Assumes discrete H VC Dimension VC H also measures the flexibility of H 1 P m 4 log2 2 8VC H log 2 13 m is training examples is desired true error is probability of achieving desired true error Computing VC Dimension Size of largest set set of instances that can be shattered by a classifier A classifier can shatter a set of n instances if the classifier can assign every possible labeling n in 0 1 to those examples instance is the X part of a training or testing example Example I 1 Instances Hypothesis space parameterized by a b classify x as 1 iff a x b Example II 2 Instances Hypothesis space parameterized by a b classify x y as 1 iff ax by 0 Example III 2 Instances Hypothesis space parameterized by a b s classify x as 1 iff x is inside the the square of side s centered at a b Example IV 10 Instances 0 1 Hypothesis space Decision Trees on n variables Midterm Tough Questions 1 1 1 2 Does NB achieve 0 train test error 1 1 4 5 Are two Bayes nets equivalent 2 1 6 EM Algorithm on a Bayes net 2 2 Constructing a Bayes net 4 Linear regression 5 1 2 Naive Bayes with cond indep violation 6 Extra Credit Violated Bayes net assumption
View Full Document
Unlocking...