LFD Book Forum

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 \{x_1, x_2, x_3\}
H1:
\{x_1 = 1, x_2 = 1, x_3 = 1\}
\{x_1 = 1, x_2 = 1, x_3 = -1\}
\{x_1 = 1, x_2 = -1, x_3 = 1\}
\{x_1 = -1, x_2 = 1, x_3 = 1\}

H2:
\{x_1 = -1, x_2 = -1, x_3 = -1\}
\{x_1 = -1, x_2 = -1, x_3 = 1\}
\{x_1 = -1, x_2 = 1, x_3 = -1\}
\{x_1 = 1, x_2 = -1, x_3 = -1\}

thus:
d_{H1} = 1 , d_{H2} = 1
and \{H_1 \cup H_2\} can shatter all 3 point


d_{H_1 \cup H_2} = 3:)

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 H_1, H_2 with VC dimension d_1, d_2

H1: hypothesis over \{x_1, x_2, ... , x_{d1+d2-1}\}
mapping these point to cases that at most d_1 points to +1 and other points to -1

H2: hypothesis over \{x_1, x_2, ... , x_{d1+d2-1}\}
mapping these point to cases that at most d_2 points to -1 and other points to +1
so there is at least d_1 + 1 +1 and other points to -1


easy to prove that H_1 \cap H_2 = \{\}
since card(H_1) + card(H_2) = 2^{d_1+d_2+1}
so \{H_1 \cup H_2\} can shatter all d_1 + d_2 + 1 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 \{x_1, x_2, x_3\}
H1:
\{x_1 = 1, x_2 = 1, x_3 = 1\}
\{x_1 = 1, x_2 = 1, x_3 = -1\}
\{x_1 = 1, x_2 = -1, x_3 = 1\}
\{x_1 = -1, x_2 = 1, x_3 = 1\}

H2:
\{x_1 = -1, x_2 = -1, x_3 = -1\}
\{x_1 = -1, x_2 = -1, x_3 = 1\}
\{x_1 = -1, x_2 = 1, x_3 = -1\}
\{x_1 = 1, x_2 = -1, x_3 = -1\}

thus:
d_{H1} = 1 , d_{H2} = 1
and \{H_1 \cup H_2\} can shatter all 3 point


d_{H_1 \cup H_2} = 3:)


Elroch 04-29-2013 06:04 PM

Re: Q10 higher bound
 
Simpler?

H_1=\{\}, H_2=\{a\}

:)

jforbes 04-29-2013 08:19 PM

Re: Q10 higher bound
 
Quote:

Originally Posted by MindExodus (Post 10640)
thus:
d_{H1} = 1 , d_{H2} = 1
and \{H_1 \cup H_2\} can shatter all 3 point


d_{H_1 \cup H_2} = 3:)

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 d_{VC}(H_1) > 1, 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 A and B, and hypothesis sets \mathcal H_A \subset 2^A and \mathcal H_B \subset 2^B (where 2^S is the set of subsets of S), then you can can form a new hypothesis set \mathcal H_{ A X B} \subset 2^{A \cup B} with one hypothesis for each pair of hypotheses in \mathcal H_A and \mathcal H_B (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 d_{VC}(H_1) > 1, 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 \mathcal H_1 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 \mathcal H_1 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)
m_{H}(N)=m_{H'_1}(N)+m_{H'_2}(N)

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:51 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.