LFD Book Forum Quick clarification on the growth function
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
01-25-2013, 11:10 AM
 kartikeya_t@yahoo.com Member Join Date: Jul 2012 Posts: 17
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.
#2
01-25-2013, 11:47 AM
 Suhas Patil Senior Member Join Date: Dec 2012 Posts: 57
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.
#3
01-25-2013, 12:25 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
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
#4
01-25-2013, 12:44 PM
 geekoftheweek Member Join Date: Jun 2012 Posts: 26
Re: Quick clarification on the growth function

Quote:
 Originally Posted by Suhas Patil 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.
#5
01-25-2013, 01:19 PM
 melipone Senior Member Join Date: Jan 2013 Posts: 72
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?
#6
01-25-2013, 01:30 PM
 ezreal Member Join Date: Jan 2013 Posts: 15
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?
#7
01-25-2013, 01:34 PM
 geekoftheweek Member Join Date: Jun 2012 Posts: 26
Re: Quick clarification on the growth function

Quote:
 Originally Posted by melipone 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 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.
#8
01-25-2013, 02:55 PM
 kartikeya_t@yahoo.com Member Join Date: Jul 2012 Posts: 17
Re: Quick clarification on the growth function

Quote:
 Originally Posted by geekoftheweek 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.
#9
01-25-2013, 03:05 PM
 ezreal Member Join Date: Jan 2013 Posts: 15
Re: Quick clarification on the growth function

Quote:
 Originally Posted by kartikeya_t@yahoo.com 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.
#10
01-25-2013, 10:36 PM
 Suhas Patil Senior Member Join Date: Dec 2012 Posts: 57
Re: Quick clarification on the growth function

Quote:
 Originally Posted by geekoftheweek 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.

 Thread Tools Display Modes Linear Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 07:58 PM.

 Contact Us - LFD Book - Top

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2020, 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.