Question 9

[vsuthichai]

I'm having trouble understanding the problem. Picking an arbitrary triangle and N points, it seems simple to pick N points such that every point can be moved inside and outside the triangle effectively making h(x) equal to 1 or -1 at will. This obviously doesn't seem to be the correct line of thinking or else I would think the answer is just 2^N because all dichotomies are realized.

Do the chosen points within N need to consist of the three endpoints of the triangle? If that's the case, how does choice 'a' where N = 1 make up a triangle since it's only a singular point?

Any clarity is appreciated

[yaser]

Originally Posted by vsuthichai

it seems simple to pick N points such that every point can be moved inside and outside the triangle effectively making h(x) equal to 1 or -1 at will. This obviously doesn't seem to be the correct line of thinking or else I would think the answer is just 2^N because all dichotomies are realized.

Indeed, this is not allowed since the points have to be fixed in position; arbitrary but fixed. The game is to generate as many dichotomies as you can on a fixed set of (carefully chosen for this purpose) points.

[jlaurentum]

I failed question 9 because my concept of "shattering" was erroneous. A data set of size 1 can be shattered by the triangle hypothesis set. I have not worked on justifying the right answer for this question yet, but I suppose the way to go about it would be to take the sucessive values (k=1,3,5 and so on) and see if you can choose a set of points of size k so that all dichotomies are possible. For me though, it gets a little tricky to verify that for ANY given set of k points, not all dichotomies are possible.

[Elroch]

Originally Posted by jlaurentum

I failed question 9 because my concept of "shattering" was erroneous. A data set of size 1 can be shattered by the triangle hypothesis set. I have not worked on justifying the right answer for this question yet, but I suppose the way to go about it would be to take the sucessive values (k=1,3,5 and so on) and see if you can choose a set of points of size k so that all dichotomies are possible. For me though, it gets a little tricky to verify that for ANY given set of k points, not all dichotomies are possible.

Well, since a triangle is a convex set, if triangles can shatter the points, none of them is in the convex hull of the rest. That implies that the points are the vertices of a convex polygon. If you consider the intersection of a triangle with such a convex polygon, its border consists partly of a subset of the border of the convex polygon and partly of parts of the sides of the triangle.

This puts a strong constraint on the way that the points are divided up by such a triangle hypothesis, if you think of the points as being connected to the ones to the left and the right in the polygon. This is enough to get the exact value of the minimum break point.

I have to admit it took me quite a while to tie this argument together.

[rbarve]

Is the answer in the Solution key for Question 9, Homework 3 correct?

[yaser]

Originally Posted by rbarve

Is the answer in the Solution key for Question 9, Homework 3 correct?

Yes, it is.