Suppose I have a perceptron with one-hidden layer, with the input - one real number $x \in \mathbb{R}$, and the activation function of the output layers - threshold functions: $$ \theta(x) = \begin{cases} 0, x \leq 0 \\ 1, x > 0 \end{cases} $$ The hidden layer may contain $k$ units and I would like to calculate the VC dimension of this feed-forward neural network. The VC dimension is defined as a cardinality of the maximal set, that can be shattered by properly adjusting the weights of the neural network.

enter image description here

The threshold functions have a VC dimension of $n+1$, where $n$ is a number of input neurons, because by a plane $n-1$ plane one may split $n$ points in any way. So when considering the results in the first layer, we have a VC dimension of $2$ for each gate, and the total number of points, that can be separated by the activation is $2 k$. Then we have a vector $\in \mathbb{R}^k$ to be processed to output, and the output unit has a dimension $k + 1$.

Do I understand correctly, that the resulting VC dimension of this simple neural network is : $$ 2 k + k + 1 = 3k + 1 $$


1 Answer 1


I do not believe this is correct. The entire network will represent a piecewise-constant function with at most $k+1$ pieces, and has VC dimension $k+1$.

Each hidden neuron is a step function, and together there are at most $k$ jump points among them. Taking a linear combination of those, we still cannot create any new jump points, so at the output neuron before activation, we have a piecewise-constant function with at most $k$ jump points, and arbitrary constant values on the $k+1$ intervals between them. After the activation, it's just piecewise constant with values 0 and 1 on at most $k+1$ intervals.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.