Problem 2.13

RicLouRiv · #1 07-10-2017, 09:58 AM

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, $d \leq \log_2 M$ .

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 $\min d_i$ . Assume to the contrary that you could shatter

points in the intersection; hence, you can find

points that are shattered by $h \in \bigcap H_i$ . 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, $0 \leq d \leq \min d_i$ .

For Part C, it seems obvious that your lower bound is always the maximum VC dimension from the individual sets: $\max d_i \leq d$ -- simply because the hypotheses that shatter $\max d_i$ 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