LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 3

Reply
 
Thread Tools Display Modes
  #1  
Old 04-22-2013, 11:35 PM
vsuthichai vsuthichai is offline
Junior Member
 
Join Date: Jan 2013
Posts: 3
Default 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
Reply With Quote
  #2  
Old 04-23-2013, 12:30 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Question 9

Quote:
Originally Posted by vsuthichai View Post
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.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #3  
Old 04-24-2013, 09:40 AM
jlaurentum jlaurentum is offline
Member
 
Join Date: Apr 2013
Location: Venezuela
Posts: 41
Default 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.
Reply With Quote
  #4  
Old 04-24-2013, 02:28 PM
Elroch Elroch is offline
Invited Guest
 
Join Date: Mar 2013
Posts: 143
Default Re: Question 9

Quote:
Originally Posted by jlaurentum View Post
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.
Reply With Quote
  #5  
Old 07-09-2013, 02:35 AM
rbarve rbarve is offline
Junior Member
 
Join Date: Jun 2013
Posts: 1
Default Re: Question 9

Is the answer in the Solution key for Question 9, Homework 3 correct?
Reply With Quote
  #6  
Old 07-09-2013, 04:26 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Question 9

Quote:
Originally Posted by rbarve View Post
Is the answer in the Solution key for Question 9, Homework 3 correct?
Yes, it is.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #7  
Old 03-23-2016, 07:06 AM
khohi khohi is offline
Member
 
Join Date: Dec 2015
Posts: 10
Default Re: Question 9

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

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -7. The time now is 08:50 PM.


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.