Thread: Break points?
View Single Post
  #3  
Old 07-29-2012, 06:00 AM
tzs29970 tzs29970 is offline
Invited Guest
 
Join Date: Apr 2012
Posts: 52
Default Re: Break points?

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 <= 4. Since we already know it is > 3, we conclude it is 4.
Reply With Quote