LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 3 (http://book.caltech.edu/bookforum/forumdisplay.php?f=132)

 vsuthichai 04-22-2013 10:35 PM

Question 9

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 04-22-2013 11:30 PM

Re: Question 9

Quote:
 Originally Posted by vsuthichai (Post 10552) 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 04-24-2013 08:40 AM

Re: Question 9

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 04-24-2013 01:28 PM

Re: Question 9

Quote:
 Originally Posted by jlaurentum (Post 10582) 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 07-09-2013 01:35 AM

Re: Question 9

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

 yaser 07-09-2013 03:26 AM

Re: Question 9

Quote:
 Originally Posted by rbarve (Post 11185) Is the answer in the Solution key for Question 9, Homework 3 correct?
Yes, it is.

 khohi 03-23-2016 06:06 AM

Re: Question 9

thanks for this question
القسط الهندي

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