#1




Problem 2.13
I'm having some trouble with Problem 2.13  especially Part C. Let me walk through the other parts first...
For Part A, if the VC dimension of a hypothesis set is , then you need at least hypotheses to run the points through in order to get them to shatter. So, . For Part B, at worst, your hypothesis set contains no, or perhaps 1, hypothesis. In this event, you have . I claim you can't have a VC dimension of more than . Assume to the contrary that you could shatter points in the intersection; hence, you can find points that are shattered by . But since these hypotheses belong to every individual , it means that you can shatter these points in the that has the minimum dimension  a contradiction. So, . For Part C, it seems obvious that your lower bound is always the maximum VC dimension from the individual sets:  simply because the hypotheses that shatter points in the corresponding set will carry through to the union. The upper bound is harder. I can think of simple cases (i.e., 2 hypothesis spaces, each with 2 hypotheses in it) where . While looking ahead a little at Problem 2.14, I'm trying to see if I can find a case where . I can't find one, so I'm just hoping that is a break point. I want to argue as follows: present me with points that are shattered, and it must be the case that either or shattered or points, which is a contradiction. So, given the points, if you restrict to the subset of the union that contains all hypotheses in , by assumption it can't shatter more than points, so some dichotomy is missing...but then I get stuck. Any hints? 
#2




Re: Problem 2.13

Thread Tools  
Display Modes  

