View Single Post
#3
07-23-2015, 01:20 AM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478
Re: Help in understanding proof for VC-dimension of perceptron.

Quote:
 Originally Posted by yongxien 1. Is the matrix invertible because of the way we construct it , such that it is lower triangular. If it is the case, I don't see why it does not work for d+2 or any other k > dimension of the perceptron.
The number of columns is restricted to (length of the input vector) so the matrix would not be square if we had rows.

Quote:
 2. Why the second part of the proof d + 1 >= d_vc not work for the case when k = d + 1 but only d +2?
Because if you have only vectors, they can be linearly independent. The inevitable linear dependence of any vectors is what makes that part of the proof work.

Quote:
 3. I don't understand the statement why more points than dimension means we must have x_j = \sigma a_i x_i? (btw, d+1 is also more points than dimension)
This is a consequence of the basic linear algebra result mentioned in the response to point 2. As for the other remark, the length of the ector is , so (because of the zeroth coordinate) would not be more points than dimensions.
__________________
Where everyone thinks alike, no one thinks very much