Help in understanding proof for VC-dimension of perceptron.

yongxien · #1 07-23-2015, 12:20 AM

https://work.caltech.edu/library/072.pdf

I am referring to the slides given in the link above.

I have a few questions regarding this proof:
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.
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?
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)

yongxien · #2 07-23-2015, 01:01 AM

I don't understand the second part of the proof too. Why y_i = sign(w^T x_i) = sign(a_i).

yaser · #3 07-23-2015, 02:20 AM

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.

MaciekLeks · #4 05-05-2016, 07:55 AM

Context:
To show that $d_{vc}\leq d+1$ we need to prove we cannot shatter any set od

points. In this case we have

vectors of $\mathbf{x}_{i}$ , where $1\leq i\leq d+2$ , hence we have

vector than the total number of dimensions (our space is

-dimensional). According to the theory of vector spaces when we have more vectors than dimensions of the space then they are linearly dependent (one of the vectors is a linear combination of the others). Which means that for instance our extra point $\mathbf{x}_{d+2}$ , can be computed by the equation (in

-dimensional space): $\mathbf{x}_{d+2}=\sum_{i=1}^{d+1}a_{i}\mathbf{x}_{i}$ , (where not all $a_{i}$ coefficients are zeros).
We need to show that we can't get $\mathbf{y}=\begin{bmatrix}\pm1\\ \pm1\\ \pm1\\ \pm1\\ \pm1 \end{bmatrix}$ ( $2^{d+2}$ ) dichotomies, where $\mathbf{y}$ is of

size.

Problem:

And now let me define my problem I have with understanding the video proof. Why do we correlate $a_{i}$ coefficient with the $y_{i}=sign(a_{i})$ while they don't correlate? On what basis we can draw that $sign(a_{i})=sign(\mathbf{w}^{T}\mathbf{x}_{i})$ , and that's why $\mathbf{w}^{T}\mathbf{x}_{d+2}=\sum_{i=1}^{d+1}a_{i}\mathbf{w}^{T}\mathbf{x}_{i}>0$ , hence we can't generate $\mathbf{y}=\begin{bmatrix}\pm1\\ \pm1\\ ...\\ \pm1\\ -1 \end{bmatrix}$ ?

ntvy95 · #5 05-05-2016, 10:57 AM

Quote:

Originally Posted by MaciekLeks

Context:
To show that $d_{vc}\leq d+1$ we need to prove we cannot shatter any set od

points. In this case we have

vectors of $\mathbf{x}_{i}$ , where $1\leq i\leq d+2$ , hence we have

vector than the total number of dimensions (our space is

-dimensional). According to the theory of vector spaces when we have more vectors than dimensions of the space then they are linearly dependent (one of the vectors is a linear combination of the others). Which means that for instance our extra point $\mathbf{x}_{d+2}$ , can be computed by the equation (in

-dimensional space): $\mathbf{x}_{d+2}=\sum_{i=1}^{d+1}a_{i}\mathbf{x}_{i}$ , (where not all $a_{i}$ coefficients are zeros).
We need to show that we can't get $\mathbf{y}=\begin{bmatrix}\pm1\\\pm1\\\pm1\\\pm1\\\pm1\end{bmatrix}$ ( $2^{d+2}$ ) dichotomies, where $\mathbf{y}$ is of

size.

Problem:

And now let me define my problem I have with understanding the video proof. Why do we correlate $a_{i}$ coefficient with the $y_{i}=sign(a_{i})$ while they don't correlate? On what basis we can draw that $sign(a_{i})=sign(\mathbf{w}^{T}\mathbf{x}_{i})$ , and that's why $\mathbf{w}^{T}\mathbf{x}_{d+2}=\sum_{i=1}^{d+1}a_{i}\mathbf{w}^{T}\mathbf{x}_{i}>0$ , hence we can't generate $\mathbf{y}=\begin{bmatrix}\pm1\\\pm1\\...\\\pm1\\-1\end{bmatrix}$ ?

Here is my understanding:

For any data set of size d + 2, we must have linear dependence, and the question is: With such inevitable linear dependence, can we find at least a specific data set that can be implemented 2^N dichotomies? The video lecture shows that for any data set of size d + 2, there are some dichotomies (specific to the data set) that the perceptron cannot implement, hence there's no such a data set of size d + 2 can be shattered by the perceptron hypothesis set.

The proof tries to consider some dichotomies (specific to the data set) have two following properties:
- $x_{i}$ with non-zero $a_{i}$ get $y_{i} = sign(a_{i})$ .
- $x_{j}$ gets $y_{j} = -1$ .

Hope this helps.

MaciekLeks · #6 05-06-2016, 01:40 AM

Quote:

Originally Posted by ntvy95

Here is my understanding:

For any data set of size d + 2, we must have linear dependence, and the question is: With such inevitable linear dependence, can we find at least a specific data set that can be implemented 2^N dichotomies? The video lecture shows that for any data set of size d + 2, there are some dichotomies (specific to the data set) that the perceptron cannot implement, hence there's no such a data set of size d + 2 can be shattered by the perceptron hypothesis set.

I agree. I tried to write it in Context part of my post.

Quote:

Originally Posted by ntvy95

The proof tries to consider some dichotomies (specific to the data set) have two following properties:
- $x_{i}$ with non-zero $a_{i}$ get $y_{i} = sign(a_{i})$ .
- $x_{j}$ gets $y_{j} = -1$ .

Hope this helps.

Unfortunately it does not help. I understand the assumption, but I do not understand the source of confidence that we can correlate $a_{i}$ with perceptron outputs.

ntvy95 · #7 05-06-2016, 02:42 AM

Quote:

Originally Posted by MaciekLeks

Yes, I tried to write it in Context part of my post.

Unfortunately it does not help. I understand the assumption, but I do not understand the source of confidence that we can correlate $a_{i}$ with perceptron outputs.

I'm not sure if I understand your point right:

If the perceptron hypothesis set can shatter the data set then for the same $x_{i}$ , there exists

and

such that $sign(w'x_{i}) = 1$ and $sign(w''x_{i}) = -1$ . It means that if the data set is shatterable by the perceptron hypothesis set, for any $x_{i}$ in the data set, we can choose the case to be $y_{i} = 1$ or $y_{i} = -1$ and be sure that there exists at least one hypothesis from perceptron hypothesis set can implement the case we have chosen.

Instead of choosing $y_{i} = 1$ or $y_{i} = -1$ explicitly, the proof let the choice for the value of $y_{i}$ depends on the value of $a_{i}$ : $y_{i} = sign(a_{i})$ , because for whatever the real value of $a_{i}$ is, $sign(a_{i})$ only has value of 1 or -1, hence $y_{i} = 1$ or $y_{i} = -1$ . In my understanding, this dependence does not make the chosen dichotomy invalid.

Thread Tools
Show Printable Version Email this Page
Display Modes
Switch to Linear Mode Hybrid Mode Switch to Threaded Mode