LFD Book Forum  

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

Reply
 
Thread Tools Display Modes
  #1  
Old 04-23-2013, 06:07 AM
jlaurentum jlaurentum is offline
Member
 
Join Date: Apr 2013
Location: Venezuela
Posts: 41
Default d-dimensional Perceptrons and break points (related to Q4 of homework)

Hello:

In slide 9 of lecture 5 (minute 33:03), the Professor gives an example of 3 colinear points for which there can be no possible hypothesis. Still, "it doesn't bother us because we want the maximum bound of possible dichotomies", so k=3 is not considered as a breakpoint. My question is:

In a d-dimensional perceptron, it appears we would not consider a set of points lying in a (d-1)-dimensional hyperplane as candidates for giving an "impossible" dichotomy. Why? Is it because the probability of picking such a set of points from the input space that all lie in a (d-1) dimensional space is zero? (As in the case of picking 3 collinear points in a plane).
Reply With Quote
  #2  
Old 04-23-2013, 07:13 AM
IsidroHidalgo IsidroHidalgo is offline
Member
 
Join Date: Apr 2013
Location: Toledo (Spain)
Posts: 28
Default Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

No, the probability isn't cero. The question is that we are interested in the maximum of points our hypothesis can shatter. So you must take a set of points that maximizes the probability of shatter the most...
Reply With Quote
  #3  
Old 04-23-2013, 08:48 AM
Elroch Elroch is offline
Invited Guest
 
Join Date: Mar 2013
Posts: 143
Default Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

Quote:
Originally Posted by jlaurentum View Post
Hello:

In slide 9 of lecture 5 (minute 33:03), the Professor gives an example of 3 colinear points for which there can be no possible hypothesis. Still, "it doesn't bother us because we want the maximum bound of possible dichotomies", so k=3 is not considered as a breakpoint. My question is:

In a d-dimensional perceptron, it appears we would not consider a set of points lying in a (d-1)-dimensional hyperplane as candidates for giving an "impossible" dichotomy. Why? Is it because the probability of picking such a set of points from the input space that all lie in a (d-1) dimensional space is zero? (As in the case of picking 3 collinear points in a plane).
It's worth observing that the set H_n of d-dimensional perceptrons, restricted to a (d-k)-dimensional subspace, is simply H_{n-k}, the set of (d-k)-dimensional perceptrons on that subspace. hence, the capabilities of H_n restricted to the subspace is the same as that of H_{n-k}.

It turns out that the power of the hypothesis set comprising perceptrons increases as the dimension of their domain increases. The three points are a good example. If co-linear, they cannot be shattered, regardless of what dimension space they are in. If not co-linear, they can always be shattered: this requires the domain to be at least 2-dimensional.
Reply With Quote
  #4  
Old 04-23-2013, 08:55 AM
jlaurentum jlaurentum is offline
Member
 
Join Date: Apr 2013
Location: Venezuela
Posts: 41
Default Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

Ok. This 3 point set: +1 -1 +1 cannot be shattered if the 3 points are collinear, no matter what dimension the perceptron is. Why isnt three the break point for a 2-d perceptron (or a 3-d perceptron, for that matter)? What is the reason that we must consider point sets that are in the same dimension as the input space?
Reply With Quote
  #5  
Old 04-23-2013, 08:57 AM
Elroch Elroch is offline
Invited Guest
 
Join Date: Mar 2013
Posts: 143
Default Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

That's simply a matter of the definition!

The break point is the (minimum) value of n such that no set of n points can be shattered. To put it another way, it is the (minimum) value of n such that every set of n points fails to be shattered. Finding one set of n points that fails to be shattered is consistent with the existence of a break point, but you need to demonstrate all other sets of n points have the same property.
Reply With Quote
  #6  
Old 04-23-2013, 10:05 AM
jlaurentum jlaurentum is offline
Member
 
Join Date: Apr 2013
Location: Venezuela
Posts: 41
Default Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

Now I'm confused. The break point for 2-d perceptrons is 4. In lecture 5, one example of a 4-point set is given that is not shatterable. However, there are other 4-point sets that are (shatterable). Likewise for positive rays, positive intervals, where the break point is 2 and 3 respectively.
Reply With Quote
  #7  
Old 04-23-2013, 10:53 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

Quote:
Originally Posted by jlaurentum View Post
The break point for 2-d perceptrons is 4. In lecture 5, one example of a 4-point set is given that is not shatterable. However, there are other 4-point sets that are (shatterable).
Hi,

It is actually not possible to shatter any set of 4 points using the 2-dimensional perceptron. Perhaps we can discuss the set of points you have in mind and look for which dichotomies would be impossible there.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #8  
Old 04-23-2013, 01:13 PM
kafar kafar is offline
Junior Member
 
Join Date: Apr 2013
Posts: 6
Default Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

Quote:
Originally Posted by yaser View Post
Hi,

It is actually not possible to shatter any set of 4 points using the 2-dimensional perceptron. Perhaps we can discuss the set of points you have in mind and look for which dichotomies would be impossible there.
Hi Prof,

there are several questions related to finding the break point of a given hypothesis restriction.

So I'm wondering: is there a procedural method that we can follow to find the break points?

It is fine using imagination and permutation in one,two or even three dimensional space. But as the dimension increases (often with increasing break point), it seems to be harder and harder to go through each permutation of classification and determine if a given set of points can be shattered.

Or did i miss something in the lecture?
Reply With Quote
  #9  
Old 04-23-2013, 01:49 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

Quote:
Originally Posted by kafar View Post
is there a procedural method that we can follow to find the break points?
There is no systematic way that applies to all cases, but it is usually not too difficult to get some upper bound of when the growth function breaks. Fortunately, only an upper bound is needed to carry through the theory, as you will see in Lecture 7.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #10  
Old 04-23-2013, 03:03 PM
jlaurentum jlaurentum is offline
Member
 
Join Date: Apr 2013
Location: Venezuela
Posts: 41
Default Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

Thanks for intervening Professor.

The 4-point set I have in mind is the set of 4 corners of a square. The concept of "shattering" I am working under corresponds to being able to propose a hypothesis that conforms to the classification given for each of the points in the dataset. So in the case of a 2-d perceptron, It is easy to "shatter" (if my def. of shattering is correct) the 4 corners in a square if 2 of the corners in one side of the square are red and the other 2 corners are blue - just pass a line in the middle of the square such that the two red points are on one side of the line and the other 2 are on the opposite side. Got your colors inverted? No problem, just multiply the w vector by -1.

Now if the red points are on opposite corners (and the blue as well), then we couldn't shatter them because no matter what boundary line we choose, we always get either both sides with the same color or two colors on each side. That's how I understand that the break point for the 2-d perceptron is 4- because there exists a 4-point set that is not shatterable.

Obviously there is a mistake in my concepts somewhere because if you choose a 3 point set in which all points are collinear and you set the middle point to blue and the outer points to red, this is not shatterable by a 2-d perceptron, or a 3-d perceptron or any higher dimensional perceptron.

I hope I made clear what my doubts are and where is my confusion.
Reply With Quote
Reply

Tags
break points, perceptron

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 01:08 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.