LFD Book Forum  

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

Reply
 
Thread Tools Display Modes
  #1  
Old 04-24-2013, 02:07 PM
OlivierB OlivierB is offline
Member
 
Join Date: Apr 2013
Location: Paris
Posts: 16
Default 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 K-1 factor.
Can anybody more advanced on the subject propose an indication, a clue, a line of reasoning ? (NOT the answer)

Thx
Reply With Quote
  #2  
Old 04-24-2013, 06:20 PM
Michael Reach Michael Reach is offline
Senior Member
 
Join Date: Apr 2013
Location: Baltimore, Maryland, USA
Posts: 71
Default Re: Q10 higher bound

One helpful step is to check the problems in the book.
Reply With Quote
  #3  
Old 04-24-2013, 07:03 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q10 higher bound

Quote:
Originally Posted by OlivierB View Post
Can anybody more advanced on the subject propose an indication, a clue, a line of reasoning?
Let me just comment that this problem is probably the hardest in the entire course. A discussion from the participants is most welcome.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #4  
Old 04-27-2013, 03:35 PM
alasdairj alasdairj is offline
Member
 
Join Date: Mar 2013
Posts: 12
Default 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??
Reply With Quote
  #5  
Old 04-28-2013, 12:12 PM
marek marek is offline
Member
 
Join Date: Apr 2013
Posts: 31
Default Re: Q10 higher bound

Quote:
Originally Posted by alasdairj View Post
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??
I am struggling with this question as well. Based on this discussion, I can intuit what the right answer should be, but I am struggling with the justification.

I figure if I can simply come up with an H1 and H2 such that d(H1 U H2) = d(H1) + d(H2) + 1, I would be done. I can come up 1 short of that (much like your example, even consider 1d positive and negative rays). But I cannot think of an example that would hit the higher bound.

That being said, I decided to just play around with the growth function. We know that m_H(N) \leq \sum_{i=0}^{d} {N \choose i}. If all the terms in that expansion are present, we get 2^N and hence can shatter. The binomial expansion is symmetric, so if I had two growth functions that were "disjoint" one could get the terms from the bottom and the other could get terms from the top and these could together give the full expansion.

More formally:\sum_{i=0}^{d_1} {N \choose i} + \sum_{i=0}^{d_2} {N \choose i} = \sum_{i=0}^{d_1} {N \choose i} + \sum_{i=N-d_2}^{N} {N \choose i}. This gives the full expansion if the second sum starts off one term after the first sum ends, specifically N-d_2 \leq d_1 + 1 \Leftrightarrow N \leq d_1 + d_2 + 1.

This simple analysis gives me my desired d_1 + d_2 + 1. But clearly something is missing. How can growth functions be "disjoint"? Any example I come up with, there is a significant overlap in dichotomies. I feel like I'm definitely on the right track here, but I also feel like something is clearly missing. Maybe B(N,k) is a better starting point than the growth function?

Hopefully someone can pick up the ball and carry it over the finish line...
Reply With Quote
  #6  
Old 04-28-2013, 03:20 PM
OlivierB OlivierB is offline
Member
 
Join Date: Apr 2013
Location: Paris
Posts: 16
Default 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
m_{H}(N)\le B(N, d+1)=\sum_{i=0}^d \left(\begin{array}{c}N\\ i\end{array}\right)

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 H_{1} and H_{2} with VC dimensions respectively d_{1} and d_{2}.

We can construct two disjoint H'_{1} and H'_{2} putting the intersection of both with one of them only.
H'_{1}=H_{1}
H'_{2}=H_{2}-\bigcap(H_{1}, H_{2})

The VC dimension of H'_{1} is d_{1}
The VC dimension of H'_{2} is d'_{2}\le d_{2}

Let H be the union of these hypothesis sets:
H=\bigcup(H_{1}, H_{2})=\bigcup(H'_{1}, H'_{2})
Let N=d_{1}+d_{2}+1

Now in order to try and determine the VC dimension of H, let us compute a higher bound of m_{H}(N):

m_{H}(N)=m_{H'_1}(N)+m_{H'_2}(N)\le\sum_{i=0}^{d_1}\left(\begin{array}{c}N\\ i\end{array}\right)+\sum_{i=0}^{d'_2}\left(\begin{array}{c}N\\ i\end{array}\right)\le\sum_{i=0}^{d_1}\left(\begin{array}{c}N\\ i\end{array}\right)+\sum_{i=0}^{d_2}\left(\begin{array}{c}N\\ i\end{array}\right)

which we can simplify:

\sum_{i=0}^{d_1}\left(\begin{array}{c}N\\ i\end{array}\right)+\sum_{i=0}^{d_2}\left(\begin{array}{c}N\\ i\end{array}\right)=\sum_{i=0}^{d_1}\left(\begin{array}{c}N\\ i\end{array}\right)+\sum_{i=N-d_2}^{N}\left(\begin{array}{c}N\\ i\end{array}\right)=\sum_{i=0}^{d_1}\left(\begin{array}{c}N\\ i\end{array}\right)+\sum_{i=d_1+1}^{N}\left(\begin{array}{c}N\\ i\end{array}\right)

=2^N

For m_{H}(N)=2^N 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 H_{1} and H_{2} must be exactly B(N, d_1+1) and B(N, d_2+1)
2/ Removing the intersection of H_{1} and H_{2} from H_{2} does not decrease the VC dimension of H_{2}. 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 H is at least d_1+d_2+1.

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'.
Reply With Quote
  #7  
Old 04-28-2013, 06:08 PM
marek marek is offline
Member
 
Join Date: Apr 2013
Posts: 31
Default 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.
Reply With Quote
  #8  
Old 04-28-2013, 09:56 PM
MindExodus MindExodus is offline
Junior Member
 
Join Date: Apr 2013
Posts: 3
Default 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 d_1 = 0 , d_2 = 0 , d_{1+2} = 1 = d_1 + d_2 + 1


Quote:
Originally Posted by OlivierB View Post
@marek, Thanks for your contribution.
Let me try and rephrase, not adding much.

.......

For m_{H}(N)=2^N 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 H_{1} and H_{2} must be exactly B(N, d_1+1) and B(N, d_2+1)
2/ Removing the intersection of H_{1} and H_{2} from H_{2} does not decrease the VC dimension of H_{2}. 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 H is at least d_1+d_2+1.

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'.
Reply With Quote
  #9  
Old 04-28-2013, 10:59 PM
marek marek is offline
Member
 
Join Date: Apr 2013
Posts: 31
Default Re: Q10 higher bound

Quote:
Originally Posted by MindExodus View Post
As for requirement 1, I come up with the case that
H1 := mapping all points to +1
H2 := mapping all points to -1
thus d_1 = 0 , d_2 = 0 , d_{1+2} = 1 = d_1 + d_2 + 1
Fantastic! I can sleep well tonight =)
Reply With Quote
  #10  
Old 04-29-2013, 01:24 AM
jforbes jforbes is offline
Member
 
Join Date: Apr 2013
Posts: 12
Default Re: Q10 higher bound

Quote:
Originally Posted by MindExodus View Post
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 d_1 = 0 , d_2 = 0 , d_{1+2} = 1 = d_1 + d_2 + 1
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
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 06:47 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.