Break points?

[costas]

How can I find the smallest break point for a given problem?

[dvs79]

Originally Posted by costas

How can I find the smallest break point for a given problem?

Hi costas,

actually, the break point can be only one for each set of hypothesis (and it's the smallest by definition).

I found the break point for 3D perceptron just by imagining points in 3D space and trying to separate them by a plane in all possible ways.
But then decided to do it more "strictly" and used Octave in a following fashion:

1. generate N random points
2. create all possible 2^N dichotomies
3. for each dichotomy find ideally separating plane, using PLA, if possible.
4a. if for all dichotomies PLA "converged" - then your N points can be shattered and it's not a break point, program stop.
4b. if not for all - repeat experiment, generating new random set of N points (just in case your previous set happened to be "special" - 3 points in line, e.g.)

If after some number of experiments (I used 1000, but suppose it's too much, 10 will do) for N points your dichotomies are still not all converged, you can state, that N points can't be shattered, and if N-1 were "shatterable", then N is a break point.

[tzs29970]

You can do 3D perceptron by using reasoning similar to that you would use to find the break point for 2D perceptron. Here's that kind of reasoning for the 2D case.

First, it helps to make sure you are clear on what you are seeking. It's really easy to get confused here (I know...I confused myself several times). If the break point is k, it doesn't mean every collection of k-1 points can be shattered--only that there exists a collection of k-1 that can be shattered. It also means that no collection of k points can be shattered.

So, to show that the break point for 2D perceptron is 4, we need to do two things. (1) we need to show that there exists a collection of 3 points that can be shattered (which shows that the break point is greater than 3), and (2) we need to show that no collection of 4 points can be shattered (which shows that the break point is 4.

Showing that there exists a collection of 3 points that can be shattered is easy. Just consider any 3 points that are not in a line, so they form a triangle. If they are all the same color, separate them with any line that does not intersect the triangle. If one is one color and two are the other, separate them with a line parallel to the side of the triangle that contains the two points of the same color, and that passes through the midpoint of one of the other sides.

Now let's assume we have some set of 4 points, and that this set of 4 can be shattered. Pick any three of them. Call these A, B, and C. If these are all on one line, in that order, then color A and C blue, B red. That arrangement cannot be separated by a line. Thus A, B and C cannot be on a line. They must form a triangle.

Extend the sides of this triangle, and the plane will be partitioned into 7 regions. Here's a diagram:



Let's think about where the fourth point, D, can be. Take a look at the region labeled "1". If A and B are colored blue and C is colored red, what can we say about D point if it happens to be in region 1? Any line separating A, B and C cannot be parallel to the line AC, and so it must intersect AC. It has to intersect AC between A and C, in order to separate A and C. If D were blue, then the separator line would have to intersect CD between C and D, in order to separate C and D. But then it must intersect BC on the opposite side of C from B, and so would not separate C and B. So, if D is in region 1, we can color it blue and A, B, C, D cannot be separated.

Similar reasoning can be used to show that a red D in region 4 would be a configuration that is not separable.

We've now eliminated regions 1 and 4 as possible locations for D. Now color A, B, C blue, red, blue, respectively, and we can use the same argument to eliminate regions 4 and 6. Coloring A, B, C red, blue, blue lets us eliminate 2 and 5.

That leaves region 7 as the only possible place for point D. To eliminate that, color A, B, and C all blue, and color D red. A separator line must intersect the line CD between C and D, which means it passes through the triangle, and so must intersect at least one side between the vertices. It then separates those two vertices, and so would classify them as different colors. But they are all blue, and so D inside does not work.

Note that although I drew an approximately equilateral triangle, nothing depends on the shape of the triangle. Everything above works for triangles with uneven sides, and with obtuse angles.

We've shown that no D works, and so 4 points cannot be separated by a line no matter how they are placed in 2D, so the break point is . Since we already know it is , we conclude it is 4.

[samirbajaj]

Originally Posted by tzs29970

It's really easy to get confused here (I know...I confused myself several times). If the break point is k, it doesn't mean every collection of k-1 points can be shattered--only that there exists a collection of k-1 that can be shattered. It also means that no collection of k points can be shattered.

This is the part I keep getting confused about ... somehow I need to find a way to internalize this...

Thanks for the explanation.

-Samir

[tzs29970]

For a given hypothesis (say 2D perceptrons) and a given number of points N, there are three possibilities.

1. You can always separate the points, no matter how they are arranged or colored. In other words, you can ALWAYS shatter the points.
   
2. Some arrangements of the points can be separated, no matter how colored. Some arrangements can be colored in a way that makes them non-separable. In other words, there are arrangements that you can shatter and arrangements that you cannot.
   
3. No matter how the points are arranged, the is some coloring that cannot be separated. In other words, you can NEVER shatter the points.

2D perceptrons illustrate all of these cases.

With N=2, it is easy to see that no matter how you arrange the two points you can shatter them. If they are the same color, just pick any line that has the two points on the same side of the line. If they are opposite colors, pick any line that passes between the two points. So for N=2, you can ALWAYS shatter.

With N=3, whether or not you can shatter depends on the arrangement of the points. Put the three points in a line, and color the middle point red and the end points blue, and you cannot separate them, so 3 points in a line cannot be shattered.

Put the three points in a triangle, and then they can always be separated. If they are all the same color, pick a line that does not intersect the triangle. If one is red and two are blue, consider the two line segments that join the red to the blues, and draw a line through the bisectors of those segments. That line separates the points. Similar argument if there is one blue and two reds.

So, for N=3, whether you can shatter or not depends on the arrangement.

With N=4, no matter how you arrange the points, there is coloring that cannot be separated, so with N=4 you can NEVER shatter.

That means 4 is the break point for 2D perceptron.

Note also that for , you can always find an arrangement of points that can be shattered (because for you can shatter ever arrangement, an for N=3 there are arrangements you can shatter). So the growth function of is . That's because the growth function is the MAXIMUM number of dichotomies you can separate, so even though there are some arrangements at N=3 that cannot be shattered, we are only interested in the maximum, so the important thing for N=3 is that there are some that can be shattered.

[ckimbrough]

Thank you, for example helped me a great deal.