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.

Answer 2

Venturing a contrasting view: VC dimension as cited by AK is a good/solid theoretical measurement of ANN complexity but would be unlikely to be applied to any real constructed ANN except as an estimate, and researchers/papers in large applied ANNs do not currently estimate VC dimension.

In a sense, how to measure complexity of an ANN is an open question that researchers are currently attempting to answer ("work in progress") and won't be solved until there is some more general theory of "feature detection" which seems to be slowly emerging at the moment e.g., in deep learning research. such a theory is likely a long time in the making if it is even possible & ever is obtained. Roughly, in this view, a "more complex" ANN recognizes "more complex" features across different dimensions (spatial, temporal, different sensory modalities such as auditory, kinesthetic (robotics), etc).

It is worthwhile & fairly objective however in the meantime to just consider a "black box" or "operational" style estimate based on intelligent functionality exhibited by the ANN. in other words, what can the ANN accomplish, and how does this compare to our only other benchmark of intelligence, namely biological?

You tend to rule this out in the question, but there is already a commonly used informal "sliding scale" of biological intelligence, e.g., with say small organisms at one end, moving through insects and mammals, etc., and humans at the other end. In animal science there are fairly conclusive questions & study to, e.g., "which is smarter, a dog, a pig, or a cat" with fairly nuanced/definitive answers (also with understanding that "context matters" & there are some various aspects of incomparability).

This approach basically dates to the Turing test and the Turing test is still a very valid scientific measurement of intelligence, still applied, e.g., in the Loebner contest, & seems to have roots also in behavioralist psychology principles. it involves the basic aspects of a scientific test such as a control & blind sampling etcetera.

Moreover, there are aspects of intelligence that are unique to humans such as speech recognition, image recognition, language translation, etc., and these lead to good benchmarks of ANNs that are targeted at human-like functionality as far as how well the ANN compares to human performance. it can even lead to measurements of supra-human performance in various cases.

This does not lead to a single quantifiable/numerical estimate of intelligence but in psychology, that premise is starting to be quite seriously questioned anyway, e.g., theory of multiple intelligences & perhaps even refuted somewhat at this point.