View Single Post
Old 04-24-2013, 04:21 AM
Elroch Elroch is offline
Invited Guest
Join Date: Mar 2013
Posts: 143
Default Perceptron VC dimension

First I'd like to say that Professor Abu-Mostafa's lectures are unsurpassed in clarity and effectiveness in communicating understanding of the key elements of this fascinating subject. So it is unusual (actually, unique so far) for me to think I can see a way in which clarity of a point can be improved. Maybe I'm wrong: please judge!

The proof I am referring to is the second side of the proof of the VC dimension of a perceptron, where it is necessary to show that no set of (n+2) points can be shattered. Here's my slightly different version.

Consider a set X of (n+2) points in (n+1)-dimensional space, all of which have first co-ordinate 1. There is a non-trivial linear relation on these points:

\sum\limits_{x\in X}a_x x = 0

Rearrange so all the coefficients are positive (changing labels for convenience)

\sum\limits_{x\in X_A}a_x x =\sum\limits_{x\in X_B}b_x x

X_A and X_B must be non-empty subsets of X because the relation is non-trivial, and the first co-ordinate of all the points is 1.

If some perceptron is positive on X_A and negative on X_B then the value of the perceptron on \sum\limits_{x\in X_A}a_x x is positive and its value on \sum\limits_{x\in X_B}b_x x is negative.

But from the above these are the same point. Hence such a perceptron does not exist, so X cannot be shattered, completing the proof.
Reply With Quote