LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 3 (http://book.caltech.edu/bookforum/forumdisplay.php?f=132)
-   -   Question 9 with triangles (http://book.caltech.edu/bookforum/showthread.php?t=4220)

Michael Reach 04-18-2013 01:41 PM

Question 9 with triangles
 
I am having a hard time finding a good way to visualize this. Maybe someone can make suggestions.

One thing I decided early on: A "best" set of N points (with a maximal number of dichotomies) has to be convex. If it is concave, make the point on the inside -1 and three points surrounding it +1 and it won't work.

Once the set is convex (maybe you can put them on a circle WLOG or some such), I _think_ I can guess the number that will force no breaking, but I don't have a clear argument.

yaser 04-18-2013 01:54 PM

Re: *ANSWER* Question 9 with triangles
 
Quote:

Originally Posted by Michael Reach (Post 10474)
I am having a hard time finding a good way to visualize this. Maybe someone can make suggestions.

One thing I decided early on: A "best" set of N points (with a maximal number of dichotomies) has to be convex. If it is concave, make the point on the inside -1 and three points surrounding it +1 and it won't work.

Once the set is convex (maybe you can put them on a circle WLOG or some such), I _think_ I can guess the number that will force no breaking, but I don't have a clear argument.

Take a look at this thread:

http://book.caltech.edu/bookforum/showthread.php?t=2606

and we can discuss this further.

Michael Reach 04-18-2013 02:59 PM

Re: *ANSWER* Question 9 with triangles
 
Well, I see that an N-gon (won't say which) is easy to shatter, and the (N+2)-gon is easy to see that it can't be shattered. So I know which of the answers to choose, but I'm still not clear on the (N+1)-gon in between.

yaser 04-18-2013 03:28 PM

Re: Question 9 with triangles
 
I took out the *ANSWER* warning since the discussion seems safe so far.

Michael Reach 04-18-2013 03:48 PM

Re: Question 9 with triangles
 
Ah, well, I guess an (N+1)-gon works too - brute force check on all triangles. Not very elegant, but it works.

Michael Reach 04-19-2013 07:02 AM

Re: Question 9 with triangles
 
I was having about the same troubles figuring out the perceptron problem, but I think looking in the book (*ANSWER*) helps a lot.


All times are GMT -7. The time now is 09:20 PM.

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.