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 (http://book.caltech.edu/bookforum/showthread.php?t=4233)

vsuthichai 04-22-2013 11: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-23-2013 12:30 AM

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 09: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 2^k 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 02: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 2^k 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 k points, none of them is in the convex hull of the rest. That implies that the k 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 k points are divided up by such a triangle hypothesis, if you think of the k 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 02:35 AM

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

yaser 07-09-2013 04: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 07:06 AM

Re: Question 9
 
thanks for this question
القسط الهندي


All times are GMT -7. The time now is 05:17 AM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, 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.