10
$\begingroup$

If I have some fixed non-recurrent (DAG) topology (fixed set of nodes and edges, but the learning algorithm can vary the weight on the edges) of sigmoid neurons with $n$ input neurons which can only take strings in $\{-1,1\}^n$ as input and lead to one output (that outputs a real value that we round up to 1 or down to -1 if it is a certain fixed threshold away from 0). Is there any fast way to compute (or approximate) the VC-dimension of this network?


Notes

I asked a slightly more precise algorithmic reformulation on CS.SE:

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

$\endgroup$
  • $\begingroup$ Just to clarify: do you have any hidden layers of neurons? Your question does not specify explicitly whether or not you have any hidden layers. $\endgroup$ – Andrew Apr 12 '12 at 16:35
  • $\begingroup$ @Andrew the method should work for either case. Since no hidden layers is a linear classifier, it is trivial to do; so I am more interested in the non-trivial case; assume we have 2+ hidden layers (although the method should also work for fewer, since it is easier). $\endgroup$ – Artem Kaznatcheev Apr 12 '12 at 18:01
6
$\begingroup$

I stumbled across your post while hunting for a general formula for calculating VC dimensions on neural nets, but apparently there isn't one. Apparently we only have a hodgepodge of disparate VC equations that only apply in certain narrow cases. Caution: I'm basing this on old research I barely understand, on the concept of VC Dimensions, which I'm only now learning about. Nevertheless, it may be worthwhile to skim this paper by Peter L. Bartlett and Wolfgang Maass1 on the calculability of VC dimensions. Note how they go to great lengths to derive VC formulas in 13 theorems, but how diverse and numerous the necessary conditions are for each. These prerequisites range from the number of operators in activation functions to the types of jumps allowed, the number of neurons and their positions, the bit depth of the input, etc.; there are so many of these scattered "gotchas" that they render the formulas useful only for certain narrow classes of problems. To make matters worse, they point out in Theorems 5 and 8 that sigmoidal activation functions are particularly difficult to calculate VC figures for. On pp. 6-7 they write:

"While the VC-dimension of networks with piecewise polynomial activation functions is well understood, most applications of neural networks use the logistic sigmoid function, or Gaussian radial basis function. Unfortunately, it is not possible to compute such functions using a finite number of the arithmetic operations listed in Theorem 5. However, Karpinski and Macintyre [Karpinski and Macintyre, 1997] extended Theorem 5 to allow the computation of exponentials. The proof uses the same ideas, but the bound on the number of solutions of a system of equations is substantially more difficult."

I also ran across this paper with the encouraging title of "Bounding VC-Dimension for Neural Networks: Progress and Prospects."2 A lot of the math is over my head and I didn't skim it long enough to overcome my lack of translation skills, but I suspect it doesn't offer any earth-shattering solutions, since it predates the second edition of the book Bartlett and Maass, who cite a later work by the same authors. Perhaps later research over the past 20 years has improved the calculability of VC dimensions for neural nets, but most of the references I've found seem to date from the mid-'90s; apparently there was a flurry of work on the subject back then that has since died down. If the capabilities haven't been extended by more recent scholarship far beyond what they were in the '90s, then I hope someone comes up with a more widely applicable solution soon so I can start calculating VC dimensions on my neural nets as well. Sorry I couldn't provide a more encouraging answer, for the time being at least.

1Bartlett, Peter L. and Maass, Wolfgang, 2003, "Vapnik-Chervonenkis Dimension of Neural Nets," pp. 1188-1192 in The Handbook of Brain Theory and Neural Networks, Arbib, Michael A. ed. MIT Press: Cambridge, Mass.

2Karpinski, Marek and Macintyre, Angus, 1995, "Bounding VC-Dimension for Neural Networks: Progress and Prospects," pp. 337–341 in Proceedings of the 2nd European Conference on Computational Learning Theory, Barcelona, Spain. Vitanyi, P. ed. Lecture Notes in Artificial Intelligence, No. 904. Springer: Berlin.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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