Re: Q10 higher bound
Here is another example for the upper bound:
* H1 takes any 1 point and sets it to + or , with the other pointsif anygetting the opposite sign * H2 sets all to + or all to  H1 can only shatter 1 point, and H2 can only shatter 1 point Their union however can shatter 3 points 
Re: Q10 higher bound
And this method can be generalizes!!
for with VC dimension H1: hypothesis over mapping these point to cases that at most points to +1 and other points to 1 H2: hypothesis over mapping these point to cases that at most points to 1 and other points to +1 so there is at least +1 and other points to 1 easy to prove that since so can shatter all point:D By proper extension with same idea, it can reach higher bound in k points cases 
Re: Q10 higher bound

Re: Q10 higher bound
MindExodus  very nice; I'm thoroughly convinced.
Quote:
H1 contains + and +, but not  or ++ Whereas if you give it three points, it contains +, +, +, ++, ++, and ++. Just looking at the first two points, now H1 contains all 4 combinations. How can this be if its VC dimension is only 1? I think it must be the case that , but I'd be unsurprised if I were missing something. 
Re: Q10 higher bound
A useful little construction is this.
If you have two underlying disjoint sets of points and , and hypothesis sets and (where is the set of subsets of ), then you can can form a new hypothesis set with one hypothesis for each pair of hypotheses in and (in the obvious way). There is a simple relationship between the VCdimensions of these three hypothesis sets, which can be used in examples. 
Re: Q10 higher bound
Quote:

Re: Q10 higher bound
Good work on this problem by several of you guys!

Re: Q10 higher bound
Quote:
I'm still curious about what went wrong if H1 does in fact include +, +, ... Is this sort of hypothesis set disallowed for some reason? 
Re: Q10 higher bound

All times are GMT 7. The time now is 06:46 AM. 
Powered by vBulletin® Version 3.8.3
Copyright ©2000  2022, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. AbuMostafa, Malik MagdonIsmail, and HsuanTien Lin, and participants in the Learning From Data MOOC by Yaser S. AbuMostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.