LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 2 - Training versus Testing (http://book.caltech.edu/bookforum/forumdisplay.php?f=109)
-   -   Problem 2.13 (http://book.caltech.edu/bookforum/showthread.php?t=4770)

RicLouRiv 07-10-2017 09:58 AM

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 d, then you need at least 2^d hypotheses to run the d 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 d = 0. I claim you can't have a VC dimension of more than \min d_i. Assume to the contrary that you could shatter d+1 points in the intersection; hence, you can find d+1 points that are shattered by h \in \bigcap H_i. But since these hypotheses belong to every individual H_i, it means that you can shatter these points in the H 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 d=d_1+d_2. While looking ahead a little at Problem 2.14, I'm trying to see if I can find a case where d=d_1+d_2+1. I can't find one, so I'm just hoping that d_1+d_2+1 is a break point. I want to argue as follows: present me with d_1+d_2+1 points that are shattered, and it must be the case that either H_1 or H_2 shattered d_1+1 or d_2+1 points, which is a contradiction. So, given the points, if you restrict to the subset of the union that contains all hypotheses in H_1, by assumption it can't shatter more than d_1 points, so some dichotomy is missing...but then I get stuck.

Any hints?

RicLouRiv 07-12-2017 02:29 AM

Re: Problem 2.13
 
The internet helped me out here. Using growth functions (duh), you can show that m_{H_1}(d_1+d_2+2) + m_{H_2}(d_1+d_2+2) < 2^{d_1+d_2+2}, and so d_1+d_2+2=(d_1+1)+(d_2+1) is a break point for the union.


All times are GMT -7. The time now is 11:01 AM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.