Q10 higher bound
I think I have found the tighter lower bound.
But I cannot determine the tighter higher bound, among the two candidates. From the tighter lower bound that I have found and the information in the question, it seems possible to determine the tighter higher bound. But I would like to either properly admit or dismiss the K1 factor. Can anybody more advanced on the subject propose an indication, a clue, a line of reasoning ? (NOT the answer) Thx 
Re: Q10 higher bound
One helpful step is to check the problems in the book. :)

Re: Q10 higher bound
Quote:

Re: Q10 higher bound
In 2d, a positive "2d ray" in the x direction can shatter 1 point, and a positive "2d ray" in the y direction can shatter 1 point, whereas their union can shatter 2 points...
So at least I can feel comfortable that the union of hypothesis sets *can* achieve a VC dimension which is the sum of the VC dimensions of its parts, but can it exceed it?? 
Re: Q10 higher bound
@marek, Thanks for your contribution.
Let me try and rephrase, not adding much. For a hypothesis set H with VD dimension d, we have The second equality is the result of 2 inequalities in opposite direction. In class, we saw '≤' and '≥' is the subject of problem 2.4 in the book. Let 2 hypothesis sets and with VC dimensions respectively and . We can construct two disjoint and putting the intersection of both with one of them only. The VC dimension of is The VC dimension of is Let H be the union of these hypothesis sets: Let Now in order to try and determine the VC dimension of H, let us compute a higher bound of : which we can simplify: For to be true i.e. for H to shatter N, all inequalities must be equalities. In other words, we must have: 1/ The growth functions of and must be exactly and 2/ Removing the intersection of and from does not decrease the VC dimension of . If the intersection is empty then this condition holds. If these 2 requirements are not contradictory (which seems plausible but I cannot prove  neither can I visualize with an example), then the VC dimension of is at least . Now unless there is a mistake in the reasoning, the question is: Can these requirements be met ? Ideally via an example, because beyond the abstract equations, I would really like to 'visualize' a case where these inequalities are 'saturated'. 
Re: Q10 higher bound
I am still confused on how to piece everything together. I like your much cleaner version, but I do have one comment. Having disjoint hypothesis sets does not necessarily mean that the set of dichotomies they create will also be disjoint.
For example, let H1 and H2 be the positive and negative 1d rays, respectively. These two hypothesis sets are disjoint. However, given any data set they can both create the dichotomies of all +1 or all 1. They won't have much overlap beyond that (and maybe THAT is the point), but they won't be entirely disjoint as far as our inequalities are concerned. 
Re: Q10 higher bound
Your requirement 2 can be simply rendered from Q9 that the VC dimension of intersection of hypothesis could not exceed any one of them(hope I got Q9 right)
As for requirement 1, I come up with the case that H1 := mapping all points to +1 H2 := mapping all points to 1 thus Quote:

Re: Q10 higher bound

Re: Q10 higher bound
Quote:
I'm still on the fence for this question  my first attempts at constructing an example similar to this where each hypothesis set had a VC dimension of 1 failed to shatter 3 points, but I'm not 100% sure yet that I can't get it to work. 
Re: Q10 higher bound
sry about didn't notice that requirement
but the key to this problem is the same: let me just put another example: just think of H1 and H2 on H1: H2: thus: , and can shatter all 3 point :) Quote:

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

Re: Q10 higher bound
Quote:

Re: Q10 higher bound
Quote:
for N=1, H={+,} and shatters this 1 point for N=2, H={+,+} and does not shatter these two points. for N=3, H={++, ++, ++, +, +, +} and does shatter two points. What is the VC dimension of this hypothesis set? From the N=2 case, I might conclude that it's 1 (it fails to shatter two points), but from the N=3 case I might conclude it's 2 (it shatters 2 of the points within this set of points). Where am I going wrong? 
Re: Q10 higher bound
Since the homework set was now due, I was wondering if the course staff could weigh in on this question. Did our discussion adequately cover this question or were there any nuances that we missed?

Re: Q10 higher bound
Quote:

Re: Q10 higher bound
Quote:

Re: Q10 higher bound
There is a proviso to my glib claim above that absolutely any subset can be a hypothesis. While this is true when the underlying set is finite or countable, when it is uncountably infinite I believe it only makes sense to have hypotheses which are measurable sets, according to the probability distribution associated with samples.
[Almost anything that makes any sense is likely to satisfy this, but it is not difficult to construct pathological examples even when the sample space is as simple as the unit interval with the uniform distribution]. 
Re: Q10 higher bound
Quote:
Quote:

Re: Q10 higher bound
Quote:

Re: Q10 higher bound

All times are GMT 7. The time now is 08:33 AM. 
Powered by vBulletin® Version 3.8.3
Copyright ©2000  2020, 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.