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