LFD Book Forum  

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

Reply
 
Thread Tools Display Modes
  #1  
Old 01-25-2013, 11:10 AM
kartikeya_t@yahoo.com kartikeya_t@yahoo.com is offline
Member
 
Join Date: Jul 2012
Posts: 17
Default Quick clarification on the growth function

Hello all,
I have a small question about the growth function. I believe I understand the answer, but just want a confirmation.
When we are given a budget of a number of points N, we can place them anywhere in the input space to maximize the number of dichotomies on them. But during the process of finding the dichotomies, can the locations of those N points be changed? In other words, given a set of N points, will they have to be fixed in location while the number of dichotomies is counted on them? Is it true that the locations can be changed only once the counting process starts afresh, which would happen if the number of dichotomies turns out to be less than 2^N in the present configuration?
Thanks for your time.
Reply With Quote
  #2  
Old 01-25-2013, 11:47 AM
Suhas Patil Suhas Patil is offline
Senior Member
 
Join Date: Dec 2012
Posts: 57
Default Re: Quick clarification on the growth function

Not sure if 'location' of the point can be changed to determine the growth function. For example, in case of N=4 with 2D perceptron, growth function is 14 because the perceptron cannot separate diagonally opposite points of the same class. If we change the position of the points in this case we would get growth function as 16. It seems like one can get at least one arrangement of all N points that can be shattered for any N by placing the points at appropriate position. I guess I am missing something.
Reply With Quote
  #3  
Old 01-25-2013, 12:25 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Quick clarification on the growth function

Indeed, the position of the points is fixed. Arbitrary, but fixed.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #4  
Old 01-25-2013, 12:44 PM
geekoftheweek geekoftheweek is offline
Member
 
Join Date: Jun 2012
Posts: 26
Default Re: Quick clarification on the growth function

Quote:
Originally Posted by Suhas Patil View Post
If we change the position of the points in this case we would get growth function as 16. It seems like one can get at least one arrangement of all N points that can be shattered for any N by placing the points at appropriate position.
I don't think this is correct. I believe that is what it means to have a break point: no matter what configuration (i.e. set of point locations) you pick you will not be able to satisfy the hypothesis and therefore hypothesis set can not shatter the N points.

Take N=4 for the 2D perceptron. This can be separated:
o o
x x

But this can not:
o x
x o

So, now we move the points. Separable:
x o
x
o

Not separable:
x o
o
x

Still there is binary distribution that can not be separated. So, *no* N=4 configuration can be shattered for 2D perceptron.

Each attempt to satisfy a hypothesis proceeds with first fixing the locations of the points, then permuting the possible values across all the set points (e.g. xxxx, oxxx, xoxx, etc), and finally determining if the hypothesis is violated. If the hypothesis can be violated for all orientations of the N points then there is a breakpoint. That's at least how I'm thinking about it. I could be completely wrong. I apologize if I misunderstood you and this was totally obvious.
Reply With Quote
  #5  
Old 01-25-2013, 01:19 PM
melipone melipone is offline
Senior Member
 
Join Date: Jan 2013
Posts: 72
Default Re: Quick clarification on the growth function

Yes, this is confusing to me as well, especially Figure 2.1

In my own words, what I understood is that if no configuration of N points can be shattered (meaning finding a hypothesis for all possible dichotomies), then N is a breakpoint.

So, in Figure 2.1(b) a configuration of 3 points can be shattered but Figure 2.1(c) gives one example of a configuration of 4 points that cannot be shattered. The catch is that this is just one example. It should not be possible to shatter 4 points in any configuration.

Do you agree?
Reply With Quote
  #6  
Old 01-25-2013, 01:30 PM
ezreal ezreal is offline
Member
 
Join Date: Jan 2013
Posts: 15
Default Re: Quick clarification on the growth function

@ melipone
"It should not be possible to shatter 4 points in any configuration. "

Yes, this is true. If you read the description, it states that "at most 14 out of the possible 16 dichotomies on ANY 4 points can be generated."

The book does not go out of its way to back up that statement, but if you try to visualize it yourself you will realize that (just restating the definition here) for any configuration of 4 points, it is not possible to draw a line (perceptron) to create every possible dichotomy.

Is this what you meant?

@ kartikeya_t
If you can shatter a set of points of size k in configuration A and must change the configuration to B in order to shatter a set of size k+1, then you might as well start out with the configuration B because if you can shatter a set of points of size k+1, you will be able to shatter a set of size k.

Does that help a little?
Reply With Quote
  #7  
Old 01-25-2013, 01:34 PM
geekoftheweek geekoftheweek is offline
Member
 
Join Date: Jun 2012
Posts: 26
Default Re: Quick clarification on the growth function

Quote:
Originally Posted by melipone View Post
In my own words, what I understood is that if no configuration of N points can be shattered (meaning finding a hypothesis for all possible dichotomies), then N is a breakpoint.
I agree with with this. I don't *think* I said something different above.

Quote:
Originally Posted by melipone View Post
So, in Figure 2.1(b) a configuration of 3 points can be shattered but Figure 2.1(c) gives one example of a configuration of 4 points that cannot be shattered. The catch is that this is just one example. It should not be possible to shatter 4 points in any configuration.
I think we were just meant to infer the rest. The points are placed arbitrarily in that example but if you erected a coordinate system and systematically attempted every configuration of four points they would suffer the same issue: there is a binary configuration that is not separable.
Reply With Quote
  #8  
Old 01-25-2013, 02:55 PM
kartikeya_t@yahoo.com kartikeya_t@yahoo.com is offline
Member
 
Join Date: Jul 2012
Posts: 17
Default Re: Quick clarification on the growth function

Quote:
Originally Posted by geekoftheweek View Post
I agree with with this. I don't *think* I said something different above.

I think we were just meant to infer the rest. The points are placed arbitrarily in that example but if you erected a coordinate system and systematically attempted every configuration of four points they would suffer the same issue: there is a binary configuration that is not separable.
So, if I am understanding everybody's input clearly, the following steps must be followed:
1. A budget of N points is given.
2. We set up the positions of these points in the input space arbitrarily.
3. We apply all the hypotheses from the hypothesis set to generate all possible dichotomies, noting only the unique ones. While doing this, we do not change the positions of these points.
4. If all possible dichotomies are obtained, we have proven that the hypothesis set can shatter N points.
5. If all possible dichotomies are not obtained, we reposition the N points in an educated way, and repeat the experiment. Again, once the positions are set, we don't change them till we have listed all possible unique dichotomies for those positions.
6. Doing this repeatedly can give a sense of whether there is any set of positions of the N points that can be shattered. If not, N is a break point.
Reply With Quote
  #9  
Old 01-25-2013, 03:05 PM
ezreal ezreal is offline
Member
 
Join Date: Jan 2013
Posts: 15
Default Re: Quick clarification on the growth function

Quote:
Originally Posted by kartikeya_t@yahoo.com View Post
So, if I am understanding everybody's input clearly, the following steps must be followed:
1. A budget of N points is given.
2. We set up the positions of these points in the input space arbitrarily.
3. We apply all the hypotheses from the hypothesis set to generate all possible dichotomies, noting only the unique ones. While doing this, we do not change the positions of these points.
4. If all possible dichotomies are obtained, we have proven that the hypothesis set can shatter N points.
5. If all possible dichotomies are not obtained, we reposition the N points in an educated way, and repeat the experiment. Again, once the positions are set, we don't change them till we have listed all possible unique dichotomies for those positions.
6. Doing this repeatedly can give a sense of whether there is any set of positions of the N points that can be shattered. If not, N is a break point.
Well, hopefully you'll come up with a clever arrangement from the outset and you won't have to reposition the points many times.
But the idea is correct.
Reply With Quote
  #10  
Old 01-25-2013, 10:36 PM
Suhas Patil Suhas Patil is offline
Senior Member
 
Join Date: Dec 2012
Posts: 57
Default Re: Quick clarification on the growth function

Quote:
Originally Posted by geekoftheweek View Post
I agree with with this. I don't *think* I said something different above.

I think we were just meant to infer the rest. The points are placed arbitrarily in that example but if you erected a coordinate system and systematically attempted every configuration of four points they would suffer the same issue: there is a binary configuration that is not separable.
I agree with you...thanks for clearing the confusion. With N=4 for a linear perceptron, however we try, it's not possible to get 2^N combinations that can be separated. After trying it out by plotting points on the paper with different combinations (with fixed position) it was much easier to visualize.
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 12: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.