View Single Post
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)

Originally Posted by jlaurentum View Post

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