LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 4 (http://book.caltech.edu/bookforum/forumdisplay.php?f=133)
-   -   Perceptron VC dimension (http://book.caltech.edu/bookforum/showthread.php?t=4240)

Elroch 04-24-2013 03:21 AM

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.

yaser 04-24-2013 02:39 PM

Re: Perceptron VC dimension
 
Nice argument! (and thank you for the compliment)

Quote:

Originally Posted by Elroch (Post 10579)
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.

Just to elaborate, the coefficients are not all zeros so because of the constant 1 coordinate, there has to be at least one positive and one negative coefficient, hence the rest of the argument even if all other coefficients are zeros.

yongxien 07-23-2015 12:09 AM

Re: Perceptron VC dimension
 
Isn't d+1 greater than the dimension too? Such that the proof works on d+1? why then is it not d_vc <= d?

yaser 07-23-2015 01:11 AM

Re: Perceptron VC dimension
 
Quote:

Originally Posted by yongxien (Post 11989)
Isn't d+1 greater than the dimension too? Such that the proof works on d+1? why then is it not d_vc <= d?

d+1 is greater than or equal to the VC dimension. Together with the other fact that d+1 is also less than or equal to that dimension gets you the equality.


All times are GMT -7. The time now is 04:15 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.