LFD Book Forum Break points?
 User Name Remember Me? Password
 Register FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
04-24-2012, 04:49 AM
 costas Junior Member Join Date: Apr 2012 Posts: 1
Break points?

How can I find the smallest break point for a given problem?
#2
07-26-2012, 05:53 AM
 dvs79 Member Join Date: Jul 2012 Location: Moscow, Russia Posts: 24
Re: Break points?

Quote:
 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.
#3
07-29-2012, 07:00 AM
 tzs29970 Invited Guest Join Date: Apr 2012 Posts: 52
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 . Since we already know it is , we conclude it is 4.
#4
07-29-2012, 10:38 AM
 samirbajaj Member Join Date: Jul 2012 Location: Silicon Valley Posts: 48
Re: Break points?

Quote:
 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
#5
07-29-2012, 05:37 PM
 tzs29970 Invited Guest Join Date: Apr 2012 Posts: 52
Re: Break points?

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.
#6
04-19-2013, 04:02 PM
 ckimbrough Junior Member Join Date: Apr 2013 Posts: 4
Re: Break points?

Thank you, for example helped me a great deal.

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 12:17 AM.

 Contact Us - LFD Book - Top

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.