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

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?

-

1
– Artem Kaznatcheev Feb 8 '12 at 23:51

## 1 Answer

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.

-

1
– Artem Kaznatcheev Feb 8 '12 at 23:41
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 3, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9500749707221985, "perplexity_flag": "middle"}