What is an effective metric of complexity for an Artificial Neural Network?

Question

After asking the question What is the most complex neural network... I realized I don't really have a good metric of "complexity" in a general sense. The simplest measure would likely be count of neurons or number of synapses, but that fails to take into account the structure of the network.

A couple measures of complexity are discussed in the paper Complexity of Predictive Neural Networks but they are very specific to a single task. One is the amount of work needed to learn a certain thing, and the other is how many neurons are needed to approximate a certain function.

Rough, animal based measures are often employees for the sake of grabbing headlines; such as the incorrect claims that The Blue Brain Project had emulated a neural network "as complex as" a cat's brain. C. elegans is a common and seemingly attainable level of complexity for an artificial neural network.

Animal based measures are relateable to the layman but seem questionable, especially when comparing a neural network to that of an animal who's neural network has not been completely mapped (as C. elegans has).

What is a meaningful measure by which artificial neural networks can be measured? How are such networks currently compared? Can any such metric appropriately measure complexity of such a system?

Answer 1

The standard complexity metric in theoretical computer science and machine learning, in particular in statistical learning theory, is the Vapnik–Chervonenkis (VC) dimension. It is of interest because it gives us a very good tool to measure the learning ability of a neural network (or any other statistical learner, in general).

A good introduction to the use of VC dimension for studying neural nets is:

Eduardo D. Sontag [1998] "VC dimension of neural networks" [pdf].

There, the author shows (for instance) that a network with one hidden layer, $n$ inputs, and $\tanh$ neurons has VC dimension of $n + 1$. He also explain some basic technique for how to upper-bound the VC dimension, and for how to use it for dynamic neural nets.