LFD Book Forum d-dimensional Perceptrons and break points (related to Q4 of homework)
 User Name Remember Me? Password
 Register FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
04-23-2013, 07:07 AM
 jlaurentum Member Join Date: Apr 2013 Location: Venezuela Posts: 41
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).
#2
04-23-2013, 08:13 AM
 IsidroHidalgo Member Join Date: Apr 2013 Location: Toledo (Spain) Posts: 28
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...
#3
04-23-2013, 09:48 AM
 Elroch Invited Guest Join Date: Mar 2013 Posts: 143
Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

Quote:
 Originally Posted by jlaurentum 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 of -dimensional perceptrons, restricted to a -dimensional subspace, is simply , the set of -dimensional perceptrons on that subspace. hence, the capabilities of restricted to the subspace is the same as that of .

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 -dimensional.
#4
04-23-2013, 09:55 AM
 jlaurentum Member Join Date: Apr 2013 Location: Venezuela Posts: 41
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?
#5
04-23-2013, 09:57 AM
 Elroch Invited Guest Join Date: Mar 2013 Posts: 143
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 such that no set of points can be shattered. To put it another way, it is the (minimum) value of such that every set of points fails to be shattered. Finding one set of points that fails to be shattered is consistent with the existence of a break point, but you need to demonstrate all other sets of points have the same property.
#6
04-23-2013, 11:05 AM
 jlaurentum Member Join Date: Apr 2013 Location: Venezuela Posts: 41
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.
#7
04-23-2013, 11:53 AM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478
Re: d-dimensional Perceptrons and break points (related to Q4 of homework)

Quote:
 Originally Posted by jlaurentum 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

 Tags break points, perceptron

 Thread Tools Display Modes Hybrid 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 04:43 AM.

 Contact Us - LFD Book - Top