LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 4 (http://book.caltech.edu/bookforum/forumdisplay.php?f=133)
-   -   Q10 higher bound (http://book.caltech.edu/bookforum/showthread.php?t=4241)

 MindExodus 04-29-2013 04:06 AM

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:
 Originally Posted by jforbes (Post 10636) Bad news: the problem requires that each hypothesis set has a finite positive VC dimension, so this particular example does not guarantee that the maximum is greater than the sum of the VC dimension for the case we're being asked about. 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.

 nkatz 04-29-2013 08:50 AM

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 points--if any--getting 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

 MindExodus 04-29-2013 05:44 PM

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

Quote:
 Originally Posted by MindExodus (Post 10640) 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 :)

 Elroch 04-29-2013 06:04 PM

Re: Q10 higher bound

Simpler?

:)

 jforbes 04-29-2013 08:19 PM

Re: Q10 higher bound

Quote:
 Originally Posted by MindExodus (Post 10640) thus: , and can shatter all 3 point :)
MindExodus - very nice; I'm thoroughly convinced.

Quote:
 Originally Posted by nkatz Here is another example for the upper bound: * H1 takes any 1 point and sets it to + or -, with the other points--if any--getting 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
nkatz, your example has me slightly puzzled. The only way H1 can fail to shatter 2 points is if there are exactly two points:
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.

 Elroch 04-30-2013 04:13 AM

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 VC-dimensions of these three hypothesis sets, which can be used in examples.

 Elroch 04-30-2013 04:20 AM

Re: Q10 higher bound

Quote:
 Originally Posted by jforbes (Post 10659) MindExodus - very nice; I'm thoroughly convinced. nkatz, your example has me slightly puzzled. The only way H1 can fail to shatter 2 points is if there are exactly two points: 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.
I presume he meant it was only one specific point that was being referred to, so is +-- and -++, nothing more

 Michael Reach 04-30-2013 07:14 AM

Re: Q10 higher bound

Good work on this problem by several of you guys!

 jforbes 04-30-2013 01:05 PM

Re: Q10 higher bound

Quote:
 Originally Posted by Elroch (Post 10669) I presume he meant it was only one specific point that was being referred to, so is +-- and -++, nothing more
Wouldn't it then be the case that the union of the hypothesis sets could only shatter two points?

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

 TTHotShot 04-30-2013 02:10 PM

Re: Q10 higher bound

Quote:
 Originally Posted by OlivierB (Post 10620)
Great work everyone - this question had me scratching my head until I found this post. The one thing I don't understand is the above statment. Am I missing something? It seems like it should be an inequality.

All times are GMT -7. The time now is 06:46 AM.