# Efficiently computing or approximating the VC-dimension of a neural network

My goal is to solve the following problem, which I have described by its input and output:

Input:

A directed acyclic graph $G$ with $m$ nodes, $n$ sources, and $1$ sink ($m > n \geq 1$).

Output:

The VC-dimension (or an approximation of it) for the neural network with topology $G$.

More specifics:

• Each node in $G$ is a sigmoid neuron. The topology is fixed, but the weights on the edges can be varied by the learning algorithm.
• The learning algorithm is fixed (say backward-propagation).
• The $n$ source nodes are the input neurons and can only take strings from $\{-1,1\}^n$ as input.
• The sink node is the output unit. It outputs a real value from $[-1,1]$ that we round up to $1$ or down to $-1$ if it is more than a certain fixed threshold $\delta$ away from $0$.

The naive approach is simply to try to break more and more points, by attempting to train the network on them. However, this sort of simulation approach is not efficient.

### Question

Is there an efficient way (i.e. in $\mathsf{P}$ when changed to the decision-problem: is VC-dimension less than input parameter $k$?) to compute this function? If not, are there hardness results?

Is there a works-well-in-practice way to compute or approximate this function? If it is an approximation, are there any guarantees on its accuracy?

### Notes

I asked a similar question on stats.SE but it generated no interest.

• It might make the question more self-contained if you could make the transfer function more explicit. I.e specify the actual formulas for how the information propagates. – Suresh Apr 25 '12 at 15:48

If you are willing to constrain the problem further by letting the network be layered, then Tom Mitchell's "Machine Learning" gives an upper bound of ( $2ds \log(es)$) (section 7.4.4) where $s$ is the number of internal nodes (which must be higher than 2), $d$ is the VC dimension of the individual nodes, and $e$ is the base of the natural logarithm. If you're after a bound on the number of training examples then this information should be enough.