View Single Post
Old 01-25-2013, 12:44 PM
geekoftheweek geekoftheweek is offline
Join Date: Jun 2012
Posts: 26
Default Re: Quick clarification on the growth function

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

Not separable:
x o

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