LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 4

Reply
 
Thread Tools Display Modes
  #11  
Old 04-29-2013, 04:06 AM
MindExodus MindExodus is offline
Junior Member
 
Join Date: Apr 2013
Posts: 3
Default 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 View Post
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.
Reply With Quote
  #12  
Old 04-29-2013, 08:50 AM
nkatz nkatz is offline
Junior Member
 
Join Date: Apr 2013
Posts: 4
Default 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
Reply With Quote
  #13  
Old 04-29-2013, 05:44 PM
MindExodus MindExodus is offline
Junior Member
 
Join Date: Apr 2013
Posts: 3
Default 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

By proper extension with same idea, it can reach higher bound in k points cases

Quote:
Originally Posted by MindExodus View Post
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
Reply With Quote
  #14  
Old 04-29-2013, 06:04 PM
Elroch Elroch is offline
Invited Guest
 
Join Date: Mar 2013
Posts: 143
Smile Re: Q10 higher bound

Simpler?

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

Reply With Quote
  #15  
Old 04-29-2013, 08:19 PM
jforbes jforbes is offline
Member
 
Join Date: Apr 2013
Posts: 12
Default Re: Q10 higher bound

Quote:
Originally Posted by MindExodus View Post
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.
Reply With Quote
  #16  
Old 04-30-2013, 04:13 AM
Elroch Elroch is offline
Invited Guest
 
Join Date: Mar 2013
Posts: 143
Default 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.
Reply With Quote
  #17  
Old 04-30-2013, 04:20 AM
Elroch Elroch is offline
Invited Guest
 
Join Date: Mar 2013
Posts: 143
Default Re: Q10 higher bound

Quote:
Originally Posted by jforbes View Post
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
Reply With Quote
  #18  
Old 04-30-2013, 07:14 AM
Michael Reach Michael Reach is offline
Senior Member
 
Join Date: Apr 2013
Location: Baltimore, Maryland, USA
Posts: 71
Default Re: Q10 higher bound

Good work on this problem by several of you guys!
Reply With Quote
  #19  
Old 04-30-2013, 01:05 PM
jforbes jforbes is offline
Member
 
Join Date: Apr 2013
Posts: 12
Default Re: Q10 higher bound

Quote:
Originally Posted by Elroch View Post
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?
Reply With Quote
  #20  
Old 04-30-2013, 02:10 PM
TTHotShot TTHotShot is offline
Junior Member
 
Join Date: Apr 2013
Posts: 3
Default Re: Q10 higher bound

Quote:
Originally Posted by OlivierB View Post
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.
Reply With Quote
Reply

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 04:42 PM.


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.