LFD Book Forum  

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

Reply
 
Thread Tools Display Modes
  #1  
Old 01-23-2013, 04:18 AM
tathagata tathagata is offline
Junior Member
 
Join Date: Jan 2013
Posts: 9
Question 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?
Reply With Quote
  #2  
Old 01-23-2013, 10:27 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q4 and Q5

Quote:
Originally Posted by tathagata View Post
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 k>N, we have {N \choose k}=0.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #3  
Old 01-24-2013, 05:08 AM
tathagata tathagata is offline
Junior Member
 
Join Date: Jan 2013
Posts: 9
Default Re: Q4 and Q5

Quote:
Originally Posted by yaser View Post
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?
Reply With Quote
  #4  
Old 01-24-2013, 11:30 AM
geekoftheweek geekoftheweek is offline
Member
 
Join Date: Jun 2012
Posts: 26
Default Re: Q4 and Q5

Quote:
Originally Posted by yaser View Post
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.
Reply With Quote
  #5  
Old 01-24-2013, 01:11 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q4 and Q5

Quote:
Originally Posted by tathagata View Post
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 2^N. 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
Reply With Quote
  #6  
Old 01-24-2013, 01:13 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q4 and Q5

Quote:
Originally Posted by geekoftheweek View Post
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
Reply With Quote
  #7  
Old 01-24-2013, 01:29 PM
Anne Paulson Anne Paulson is offline
Senior Member
 
Join Date: Jan 2013
Location: Silicon Valley
Posts: 52
Default 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.
Reply With Quote
  #8  
Old 01-24-2013, 01:59 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q4 and Q5

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

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

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

Tags
break points, growth functions

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 04:23 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.