LFD Book Forum Q4 and Q5

#1
01-23-2013, 04:18 AM
 tathagata Junior Member Join Date: Jan 2013 Posts: 9
Q4 and Q5

Regarding Q4, which asks us to determine the break point of a 3D Perceptron, just a clarification: I am thinking that the 2D case will also be a pathological case in 3D, as it is just a special case for the 3D plane, but if there exists any setting of 4 points in 3D that can be shattered by the 3D Perceptron then break point is greater than four, since we take the maximum? (like the 2D case with collinear points for N = 3)

Regarding Q5, as I understand it, any monotonically increasing function <= 2^N for all N, can be a possible growth function, is that correct or are there more restrictions?
Also we have a N choose 2 term in one of the options that is not defined for N = 1, but that can be logically regarded as zero, right?
#2
01-23-2013, 10:27 AM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Q4 and Q5

Quote:
 Originally Posted by tathagata Regarding Q4, which asks us to determine the break point of a 3D Perceptron, just a clarification: I am thinking that the 2D case will also be a pathological case in 3D, as it is just a special case for the 3D plane, but if there exists any setting of 4 points in 3D that can be shattered by the 3D Perceptron then break point is greater than four, since we take the maximum? (like the 2D case with collinear points for N = 3)
You are right.

Quote:
 Regarding Q5, as I understand it, any monotonically increasing function <= 2^N for all N, can be a possible growth function, is that correct or are there more restrictions?
There are more restrictions that were discovered in Lecture 6.

Quote:
 Also we have a N choose 2 term in one of the options that is not defined for N = 1, but that can be logically regarded as zero, right?
Correct. For , we have .
__________________
Where everyone thinks alike, no one thinks very much
#3
01-24-2013, 05:08 AM
 tathagata Junior Member Join Date: Jan 2013 Posts: 9
Re: Q4 and Q5

Quote:
 Originally Posted by yaser There are more restrictions that were discovered in Lecture 6.
But doesn't lecture 6 discuss a more strict bound only if we have a break point? Whereas Q5 asks for any possible growth function, so being less than 2^N is sufficient I would have thought. What am i missing?
#4
01-24-2013, 11:30 AM
 geekoftheweek Member Join Date: Jun 2012 Posts: 26
Re: Q4 and Q5

Quote:
 Originally Posted by yaser You are right.
I don't follow. In 2D, all four points must be coplanar so no line can shatter the points. In 3D the two x's and two o's can be separated along the third axis and this can easily be shattered by a plane. You need k > 4 as a breakpoint. Am I missing something? Perhaps I did not understand the OP's question.
#5
01-24-2013, 01:11 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Q4 and Q5

Quote:
 Originally Posted by tathagata But doesn't lecture 6 discuss a more strict bound only if we have a break point? Whereas Q5 asks for any possible growth function, so being less than 2^N is sufficient I would have thought. What am i missing?
We either have a break point, or else we don't. In the latter case, the growth function is identically . In the former case, the growth function is constrained such that many formulas cannot possibly be valid growth functions.
__________________
Where everyone thinks alike, no one thinks very much
#6
01-24-2013, 01:13 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Q4 and Q5

Quote:
 Originally Posted by geekoftheweek I don't follow. In 2D, all four points must be coplanar so no line can shatter the points. In 3D the two x's and two o's can be separated along the third axis and this can easily be shattered by a plane. You need k > 4 as a breakpoint. Am I missing something? Perhaps I did not understand the OP's question.
You are not missing anything. You have just articulated why a break point in 2D may not be a break point in 3D.
__________________
Where everyone thinks alike, no one thinks very much
#7
01-24-2013, 01:29 PM
 Anne Paulson Senior Member Join Date: Jan 2013 Location: Silicon Valley Posts: 52
Re: Q4 and Q5

The terminology can be a bit confusing, because a break point exists if there is no pathological case that can be shattered. If you can shatter, you don't break.
#8
01-24-2013, 01:59 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Q4 and Q5

Quote:
 Originally Posted by Anne Paulson If you can shatter, you don't break.
__________________
Where everyone thinks alike, no one thinks very much
#9
01-24-2013, 02:38 PM
 tathagata Junior Member Join Date: Jan 2013 Posts: 9
Re: Q4 and Q5

Quote:
 Originally Posted by yaser We either have a break point, or else we don't. In the latter case, the growth function is identically . In the former case, the growth function is constrained such that many formulas cannot possibly be valid growth functions.
Ah.. I got it thanks!
#10
04-17-2013, 06:25 PM
 Elroch Invited Guest Join Date: Mar 2013 Posts: 143
Re: Q4 and Q5

One tip I would give for studying is this: if you are shattered, take a break.

 Tags break points, growth functions

 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 08:18 AM.