#1




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




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




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




Re: Quick clarification on the growth function
Quote:
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




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




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




Re: Quick clarification on the growth function
Quote:
Quote:

#8




Re: Quick clarification on the growth function
Quote:
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




Re: Quick clarification on the growth function
Quote:
But the idea is correct. 
#10




Re: Quick clarification on the growth function
Quote:

Thread Tools  
Display Modes  

