LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 3 (http://book.caltech.edu/bookforum/forumdisplay.php?f=132)
-   -   *ANSWER* Q9 (fairly long, not complete) (http://book.caltech.edu/bookforum/showthread.php?t=4841)

skbaek90 07-13-2018 02:16 PM

*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. :clueless:

All times are GMT -7. The time now is 07:29 AM.

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