LFD Book Forum  

Go Back   LFD Book Forum > Book Feedback - Learning From Data > Chapter 2 - Training versus Testing

Thread Tools Display Modes
Old 07-10-2017, 08:58 AM
RicLouRiv RicLouRiv is offline
Junior Member
Join Date: Jun 2017
Posts: 7
Default 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?
Reply With Quote
Old 07-12-2017, 01:29 AM
RicLouRiv RicLouRiv is offline
Junior Member
Join Date: Jun 2017
Posts: 7
Default 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.
Reply With Quote

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

All times are GMT -7. The time now is 10:36 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2017, 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.