LFD Book Forum *ANSWER* Q9 (fairly long, not complete)
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
07-13-2018, 02:16 PM
 skbaek90 Junior Member Join Date: Jul 2018 Posts: 1
*ANSWER* Q9 (fairly long, not complete)

First, my understanding of the problem's background.

Dr. Yaser has mentioned in previous threads that there are no systematic way of doing this problem, but that placing the points on the perimeter of a circle is a good start.

From what I understand, this ensures that if you can't shatter k points on the perimeter of a circle with a triangle, then you can't shatter the k points with a triangle no matter how you place them and thus k is the break point.

Now, my reasoning about why 7 is correct. To shatter 7 points, you either shatter the 7 points into

Case 1: 0 & 7
Case 2: 1 & 6
Case 3: 2 & 5
Case 4: 3 & 4
... and so forth, where, let's say, the number on the left represents the number of +1's and the right the number of -1's.

You are basically separating the 7 points by connecting 3 points on the circle (thereby forming a triangle). Case 1 ~ 4 is easily handled because for Case 3, for example, you just pick 2 points as vertices of the triangle and pick somewhere on the circle that is NOT a point, thus including the 2 points and excluding the rest, the 5 points.

Case 5 ~ 8 is where I am stuck, but I feel like it still has to do with the fact that Case 5: 4 & 3, where we can shatter using a triangle (3 vertices) and that number 3 is included in Case 5.

Also, if you think about why 9 is not the correct answer, when you try to shatter 9, it breaks down into the following cases:

Case 1) 0 & 9
Case 2) 1 & 8
Case 3) 2 & 7
Case 4) 3 & 6
Case 5) 4 & 5
and so on..

If you look at case 5, you have to define the region for 4 points, or 5 points using only a triangle (which only has 3 vertices). Therefore, it's not possible to shatter 9 points.

This is my understanding of the answer, although not complete. Please correct me if I'm wrong.
#2
01-24-2020, 10:56 AM
 AlexS Junior Member Join Date: Sep 2018 Posts: 7
Re: *ANSWER* Q9 (fairly long, not complete)

Quote:
 Originally Posted by skbaek90 First, my understanding of the problem's background. Dr. Yaser has mentioned in previous threads that there are no systematic way of doing this problem, but that placing the points on the perimeter of a circle is a good start. From what I understand, this ensures that if you can't shatter k points on the perimeter of a circle with a triangle, then you can't shatter the k points with a triangle no matter how you place them and thus k is the break point. Now, my reasoning about why 7 is correct. To shatter 7 points, you either shatter the 7 points into Case 1: 0 & 7 Case 2: 1 & 6 Case 3: 2 & 5 Case 4: 3 & 4 ... and so forth, where, let's say, the number on the left represents the number of +1's and the right the number of -1's. You are basically separating the 7 points by connecting 3 points on the circle (thereby forming a triangle). Case 1 ~ 4 is easily handled because for Case 3, for example, you just pick 2 points as vertices of the triangle and pick somewhere on the circle that is ASO a point, thus including the 2 points and excluding the rest, the 5 points. Case 5 ~ 8 is where I am stuck, but I feel like it still has to do with the fact that Case 5: 4 & 3, where we can shatter using a triangle (3 vertices) and that number 3 is included in Case 5. Also, if you think about why 9 is not the correct answer, when you try to shatter 9, it breaks down into the following cases: Case 1) 0 & 9 Case 2) 1 & 8 Case 3) 2 & 7 Case 4) 3 & 6 Case 5) 4 & 5 and so on.. If you look at case 5, you have to define the region for 4 points, or 5 points using only a triangle (which only has 3 vertices). Therefore, it's not possible to shatter 9 points. This is my understanding of the answer, although not complete. Please correct me if I'm wrong.
very nice case do you have more?

 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 07:04 PM.

 Contact Us - LFD Book - Top

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2020, 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.