Today we defined version space, growth function, and VC-dimension of a concept class.
We stated and proved Sauer's lemma, which tells us how the growth function grows (sorry for the redundance).
We also stated two theorems essentially saying that the sample size needed for PAC learning a class is both upper and lower bounded by the VC-dimension, up to constants, when we fix the epsilon and delta parameters.
Exercise 8:
- find the VC-dimension of hyperrectangles in R^d
- find the VC-dimension of unions of at most k rectangles in R^2
- find the VC-dimension of linear halfspaces in R^2
- find the VC-dimension of the class of sinusoid concepts S_{a,b,c} on R. Concept S_{a,b,c} is the set of points such that a*sin(b*x)+c > 0.
No comments:
Post a Comment