LFD Book Forum - View Single Post - Help in understanding proof for VC-dimension of perceptron.

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}$ ?