this question might seem a bit odd. I was doing some self-studies into information theory and decided to do some more formal investigations into deep learning. Please bear with me as I try to explain. I took a large "training" subset of MNIST as my guinea pig.

1) Converted every image in MNIST into "black-and-white" (pixels values only 0 or 1)

2) Summed over all data images to build a histogram over the pixels - I counted the number of times each pixel gets a 1 value in the dataset

3) Normalized histogram to get an estimate of the "true" probability distribution

4) From this, I got the following probability distribution (shown as a heatmap with matplotlib):

[Probability distribution for an MNIST training set[1]

5) Now I calculated the entropy and got: $191$ bits

6) According to David MacKay in his Information Theory book, we could interpret a neural network as a noisy channel and consider each neuron as having a 2 bit capacity. Although he does state to use this idea with care. Chapter 40 of his book http://www.inference.org.uk/itila/book.html)

7) So, as a rough estimate (and with care) we could say we would need a neural network of 95 neurons in order to be able to encode the labeling of this MNIST training set (190/2) 8) Now we can get to my question:

Even if this is a very "back-of-the-envelope" calculation, shouldn't a neural network capable of learning the labelling be at least in the ballpark of 95 neurons? Why do we need, for instance, a neural network with 21840 parameters to get 99% accuracy? (considering the one in PyTorch's example for MNIST: https://github.com/pytorch/examples/blob/master/mnist/main.py)


1 Answer 1


The current thinking is that it is easier to fit an overparameterized neural network, since the local extrema are different ways of expressing the same thing, whereas in a minimal neural network you have to worry about getting to the global extremum:

The subtle reason behind this is that smaller networks are harder to train with local methods such as Gradient Descent: It’s clear that their loss functions have relatively few local minima, but it turns out that many of these minima are easier to converge to, and that they are bad (i.e. with high loss). Conversely, bigger neural networks contain significantly more local minima, but these minima turn out to be much better in terms of their actual loss. Since Neural Networks are non-convex, it is hard to study these properties mathematically, but some attempts to understand these objective functions have been made, e.g. in a recent paper The Loss Surfaces of Multilayer Networks. In practice, what you find is that if you train a small network the final loss can display a good amount of variance - in some cases you get lucky and converge to a good place but in some cases you get trapped in one of the bad minima. On the other hand, if you train a large network you’ll start to find many different solutions, but the variance in the final achieved loss will be much smaller. In other words, all solutions are about equally as good, and rely less on the luck of random initialization.

CS231n Convolutional Neural Networks for Visual Recognition

  • $\begingroup$ Thank you for your answer, Emre. Do you know of any study relating the entropy of datasets to the required network to achieve a given accuracy? I am imagining here a plot, where X is entropy of a dataset and Y is the size in bits of the minimum network found so far that achieves 99% accuracy on it. $\endgroup$ Apr 5, 2018 at 9:40
  • 1
    $\begingroup$ Not exactly, but Tishby's information bottleneck method and follow-ups such as On the Information Bottleneck Theory of Deep Learning get pretty close and are rather interesting. There are also numerous papers on neural network compression, but the ones I can think of are empirical rather than theoretical like the aforementioned. $\endgroup$
    – Emre
    Apr 5, 2018 at 16:20

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.