LFD Book Forum Question 9
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

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

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

Quote:
 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.
#5
07-09-2013, 02:35 AM
 rbarve Junior Member Join Date: Jun 2013 Posts: 1
Re: Question 9

Is the answer in the Solution key for Question 9, Homework 3 correct?
#6
07-09-2013, 04:26 AM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Question 9

Quote:
 Originally Posted by rbarve 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
#7
03-23-2016, 07:06 AM
 khohi Member Join Date: Dec 2015 Posts: 10
Re: Question 9

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

 Thread Tools Display Modes Linear Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 09:51 AM.

 Contact Us - LFD Book - Top

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