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

- VCdim
- 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.