Good resources to learn VC dimension
Machine f can shatter a set of points x1 , x2 .. Xr if and only if… For every possible training set of the form (x1 ,y1 ) , (x2 ,y2 ) ,… (xr ,yr ) …There exists some value of a that gets zero training error.
Given machine f, the VC-dimension h is The maximum number of points that can be arranged so that f shatter them
For 2-d inputs, what’s VC-dim of f(x,w,b) = sign(w.x+b)? Well, can we find four points that f can shatter? Can always draw six lines between pairs of four points. Two of those lines will cross. If we put points linked by the crossing lines in the same class they can’t be linearly separated So a line can shatter 3 points but not 4 So VC-dim of Line Machine is 3