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 02: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 02: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:

and we can discuss this further.

 Michael Reach 04-18-2013 03: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 04: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 04: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 08: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 04:55 PM.