Question 9 with triangles

[Michael Reach]

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]

Originally Posted by Michael Reach

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]

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]

I took out the *ANSWER* warning since the discussion seems safe so far.

[Michael Reach]

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

[Michael Reach]

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