Quick clarification on the growth function

[kartikeya_t@yahoo.com]

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.

[Suhas Patil]

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.

[yaser]

Indeed, the position of the points is fixed. Arbitrary, but fixed.

[geekoftheweek]

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.

[melipone]

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?

[ezreal]

@ 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?

[geekoftheweek]

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.

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.

[kartikeya_t@yahoo.com]

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.

[Suhas Patil]

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.