Homework 3

I've put up some relevant lecture notes on this topic.

1. Figure out the VC dimension of the following concept classes, by showing n points that can be shattered and giving a handwavy explanation of why no set of n+1 points can be shattered. In all these examples, the input space is two-dimensional.

   1. Unions of two half-planes (ie the OR of two perceptrons).

   2. A second-degree polynomian threshold, ie accept points (x₁,x₂) for which p(x₁,x₂)>0, where p(x1,x2) is a quadratic polynomial.

   3. Let C₁ and C₂ both be concept classes whose elements have one-dimensional inputs, with VC(C₁)=n₁ and VC(C₂)=n₂. Let C be the ``cross product'' of C₁ and C₂, ie for each concept c₁ in C₁ and c₂ in C₂ there is a concept c in C, and c accepts an input (x₁,x₂) when c₁ accepts x₁ and c₂ accepts x₂.

      Example: if C₁ and C₂ are both the concept class of one-dimensional intervals (ie accept an input x if a<x<b for constants a and b), then C would be the concept class of axis-aligned rectangles.

2. Determine how many traning samples are needed if you have a multilayer perceptron with 200 weights and want a PAC guarantee of less than a 2% chance of more than a 3% generalization error rate.

3. Determine how few weights you need if you have 50,000 examples in your training set and you want to make a PAC guarantee that your multilayer perceptron will have less then a 5% chance of more than a 1% generalization error rate.