Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9VC DimensionMidterm RecapPAC Bounds●Suppose a consistent learner has hypothesis space H.●Then for any h in H with 0 training error, ●m is # training examples,●|H| measures the 'flexibility' of the classifier.●Problem: Assumes discrete HPerrortrueh≤m−1[ln∣H∣−ln ] VC Dimension●VC(H) also measures the 'flexibility' of H.●m is # training examples●є is desired true error ●δ is probability of achieving desired true errorP ≥m−14 log22/8VC H log213/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 in {0,1}n to those examples.●'instance' is the X part of a training or testing exampleExample I●Instances: ●Hypothesis space: ●parameterized by {a,b}●classify x as 1 iff a<x<b∈ℝ1- + -Example II●Instances :●Hypothesis space: ●parameterized by {a,b}●classify (x,y) as 1 iff ax+by>0∈ℝ2-+Example III●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).∈ℝ2+--Example IV●Instances: ●Hypothesis space: ●Decision Trees on n variables∈{0,1}10Midterm: 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
View Full Document