Due Nov 3rd in class.
1. Consider a classifier in which assigns value to a point if and only if it is inside a certain axis-aligned rectangle. Such a classifier is precisely defined as
Consider the class of all axis-aligned rectangles in the plane
- Consider the algorithm that returns the smallest (in areas) axis-aligned rectangle enclosing all positive examples in the training set. Show that this algorithm -PAC learns .
- Let be the class of axis-aligned rectangles in . Prove that VCdim.
2. Let be a set of classifiers with VC-dimension . Let be the set of classifiers obtained by taking a weighted majority vote of classifiers from . Prove that the VC-dimension of is at most .
3. Let be hypothesis classes over domain set . Let . Prove that
- For , VCdim
For simplicity, you can assume that .
4. Show that any decision list on Boolean variables is equivalent to a halfspace. For a decision list of length , give a bound on the margin of the halfspace, and thereby bound the number of mistakes made by Perceptron and by Winnow in the worst case.
5. Give an algorithm to PAC-learn the parity of a set of linear threshold functions in ; the time and sample complexity of the algorithm should be polynomial for any fixed .
6. Let be a labeled sample of points in with
Show that the Perceptron algorithm makes updates before finding a separating hyperplane, regardless of the order in which it receives the points.