16
$\begingroup$

I have come across some basic ways to measure the complexity of neural networks:

Are there other alternatives?

It is preferred:

  • If the complexity metric could be used to measure neural networks from different paradigms (to measure backprop, dynamics neural nets, cascade correlation, etc) on the same scale. For instance, VC-dimension can be used for different types on networks (or even things other than neural networks) while number of neurons is only useful between very specific models where the activation function, signals (basic sums vs. spikes), and other properties of the network are the same.
  • If it has nice correspondences to standard measures of complexity of functions learnable by the network
  • If it is easily to compute the metric on specific networks (this last one is not a must, though.)

Notes

This question is based on a more general question on CogSci.SE.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Shouldn't the complexity be also dependent on the learning algorithm? VC dimension is usually applied to methods with convex loss functions. If you have a non-convex loss, you could get in the situation where you model would be able to separate some points but you learning algorithm will never find this solution. Therefor I feel it should be quite hard to have bounds using the structure of the network. I agree with @tdc that generalization error is the way to go. Vapnik's paper on statistical learning theory might be a good place to start learning about that. $\endgroup$
    – Andreas Mueller
    Commented Feb 14, 2012 at 8:40

2 Answers 2

Reset to default
8
$\begingroup$

You might want to have a look at the paper "(Not) Bounding the True Error by John Langford & Rich Caruana (NIPS, 2001)

The abstract states:

We present a new approach to bounding the true error rate of a continuous valued classifier based upon PAC-Bayes bounds. The method first constructs a distribution over classifiers by determining how sensitive each parameter in the model is to noise. The true error rate of the stochastic classifier found with the sensitivity analysis can then be tightly bounded using a PAC-Bayes bound. In this paper we demonstrate the method on artificial neural networks with results of a 2 3 order of magnitude improvement vs. the best deterministic neural net bounds.

They show that you can apply PAC-Bayes style bounds to stochastic neural networks. However the analysis only applies to 2-layer feed-forward neural networks with a sigmoidal transfer function. In this case the complexity term only depends on the number of nodes and the variance of the weights. They show that for this setting the bound effectively predicts when over-training will occur. Unfortunately it doesn't really hit any of your "preferred" properties though!

Improve this answer
$\endgroup$
4
  • $\begingroup$ +1 that looks cool -- thank you, I will take a look. But I agree that it doesn't fit any of the preferred properties and at first hand doesn't seem to be really measuring the complexity of the network as much as its performance... but I guess those are inseparable. $\endgroup$
    – Artem Kaznatcheev
    Commented Feb 9, 2012 at 14:44
  • $\begingroup$ What it's looking at is Generalisation Error. The bounds that are created usually have a term that is based on the training error, and a penalty term based on the complexity of the model. All you're interested in is the complexity term, but it will be an ingredient in nearly every bound. This video explains it better than I can! $\endgroup$
    – tdc
    Commented Feb 9, 2012 at 14:48
  • $\begingroup$ think this direction is not correct. error is much different than network complexity. although existing theory may blur the two. a simple example is overfitting where the error is low but the complexity is high. also, error may behave in counterintuitive ways wrt complexity. such as bias. it seems like a small network might underestimate error. etcetera $\endgroup$
    – vzn
    Commented Feb 11, 2012 at 22:36
  • $\begingroup$ @vzn but generalisation error is the error on future data - i.e. if you have low training error and high complexity, your error bound will be loose. $\endgroup$
    – tdc
    Commented Feb 12, 2012 at 14:44
3
$\begingroup$

In addition, you might also have interest in the fat-shattering dimension work done by Professor Peter Bartlett. Here is an introduction to the analysis of the neural network complexity, in a 1998 IEEE paper: The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network (Bartlett 1998) [http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=661502]

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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