# Calculation of VC dimension of simple neural network

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. 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

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.