Why doesn't overfitting devastate neural networks for MNIST classification?

Question

I have a simple neural network(NN) for MNIST classification. It includes 2 hidden layers, each with 500 neurons. Hence the dimensions of the NN are: 784-500-500-10. ReLU is used in all neurons, softmax is used at the output, and cross-entropy is the loss function.

What puzzles me is why overfitting doesn't appear to devastate the NN?

Consider the number of parameters (weights) of the NN. It's approximately $$784\times500+500\times 500+500\times 10=647000.$$ However, in my experiment, I used only $6000$ examples (a tenth of the MNIST training set) to train the NN. (This is just to keep the run time short. The training & test error would both go down considerably if I used more training examples.) I repeated the experiment 10 times. Plain stochastic gradient descent is used (no RMS prop or momentum); no regularization/drop-out/early-stopping was used. The training error and test error reported were:

$$\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|} \hline \textrm{No.} & 1 & 2 & 3 &4 &5&6&7&8&9&10\\ \hline E_{train}(\%) & 7.8 & 10.3 & 9.1 & 11.0 & 8.7 & 9.2 & 9.3 & 8.3 &10.3& 8.6\\ \hline E_{test}(\%) & 11.7 & 13.9 & 13.2 & 14.1 &12.1 &13.2 &13.3 &11.9 &13.4&12.7\\ \hline \end{array}$$

Note that in all 10 experiments (each with independent random parameter initialization), the test error differed from the training error only by approx. 4%, even though I used 6K examples to training 647K parameters. The VC dimension of the neural network is on the order of $O(|E|log(|E|))$ at least, where $|E|$ is the number of edges (weights). So why wasn't the test error miserably higher (e.g. 30% or 50%) than the training error? I'd greatly appreciate it if someone can point out where I missed. Thanks a lot!

[ EDITS 2017/6/30]

To clarify the effects of early stopping, I did the 10 experiments again, each now with 20 epochs of training. The error rates are shown in the figure below:

$\qquad\qquad\qquad$

The gap between test and training error did increase as more epochs are used in the training. However, the tail of the test error stayed nearly flat after the training error is driven to zero. Moreover, I saw similar trends for other sizes of the training set. The average error rate at the end of 20 epochs of training is plotted against the size of the training set below:

$\qquad\qquad\qquad$

So overfitting does occur, but it doesn't appear to devastate the NN. Considering the number of parameters (647K) we need to the train and the number of training examples we have (<60K), the question remains: why doesn't overfitting easily render the NN useless? Moreover, is this true for the ReLU NN for all classification tasks with softmax output and cross-entropy objective function? Have someone seen a counter-example?

Answer 1

I have replicated your results using Keras, and got very similar numbers so I don't think you are doing anything wrong.

Out of interest, I ran for many more epochs to see what would happen. The accuracy of test and train results remained pretty stable. However, the loss values drifted further apart over time. After 10 epochs or so, I was getting 100% train accuracy, 94.3% test accuracy - with loss values around 0.01 and 0.22 respectively. After 20,000 epochs, the accuracies had barely changed, but I had training loss 0.000005 and test loss 0.36. The losses were also still diverging, albeit very slowly. In my opinion, the network is clearly over-fitting.

So the question could be re-phrased: Why, despite over-fitting, does a neural network trained to the MNIST data set still generalise apparently reasonably well in terms of accuracy?

It is worth comparing this 94.3% accuracy with what is possible using more naive approaches.

For instance, a simple linear softmax regression (essentially the same neural network without the hidden layers), gives a quick stable accuracy of 95.1% train, and 90.7% test. This shows that a lot of the data separates linearly - you can draw hyperplanes in the 784 dimensions and 90% of the digit images will sit inside the correct "box" with no further refinement required. From this, you might expect an overfit non-linear solution to get a worse result than 90%, but maybe no worse than 80% because intuitively forming an over-complex boundary around e.g. a "5" found inside the box for "3" will only incorrectly assign a small amount of this naive 3 manifold. But we're better than this 80% lower bound guesstimate from the linear model.

Another possible naive model is template matching, or nearest-neighbour. This is a reasonable analogy to what the over-fitting is doing - it creates a local area close to each training example where it will predict the same class. Problems with over-fitting occur in the space in-between where the values of activation will follow whatever the network "naturally" does. Note the worst case, and what you often see in explanatory diagrams, would be some highly curved almost-chaotic surface which travels through other classifications. But actually it may be more natural for the neural network to more smoothly interpolate between points - what it actually does depends on the nature of the higher order curves that the network combines into approximations, and how well those already fit to the data.

I borrowed the code for a KNN solution from this blog on MNIST with K Nearest Neighbours. Using k=1 - i.e. choosing the label of the nearest from the 6000 training examples just by matching pixel values, gives an accuracy of 91%. The 3% extra that the over-trained neural network achieves does not seem quite so impressive given the simplicity of pixel-match counting that KNN with k=1 is doing.

I tried a few variations of network architecture, different activation functions, different number and sizes of layers - none using regularisation. However, with 6000 training examples, I could not get any of them to overfit in a way where test accuracy dropped dramatically. Even reducing to just 600 training examples just made the plateau lower, at ~86% accuracy.

My basic conclusion is that MNIST examples have relatively smooth transitions between classes in feature space, and that neural networks can fit to these and interpolate between the classes in a "natural" manner given NN building blocks for function approximation - without adding high frequency components to the approximation that could cause issues in an overfit scenario.

It might be an interesting experiment to try with a "noisy MNIST" set where an amount of random noise or distortion is added to both training and test examples. Regularized models would be expected to perform OK on this dataset, but perhaps in that scenario the over-fitting would cause more obvious problems with accuracy.

---

This is from before the update with further tests by OP.

From your comments, you say that your test results are all taken after running a single epoch. You have essentially used early stopping, despite writing that you have not, because you have stopped the training at the earliest possible point given your training data.

I would suggest running for many more epochs if you want to see how the network is truly converging. Start with 10 epochs, consider going up to 100. One epoch is not many for this problem, especially on 6000 samples.

Although increasing number of iterations is not guaranteed to make your network overfit worse than it already has, you haven't really given it much of a chance, and your experimental results so far are not conclusive.

In fact I would half expect your test data results to improve following a 2nd, 3rd epoch, before starting to fall away from the training metrics as the epoch numbers increase. I would also expect your training error to approach 0% as the network approached convergence.

Answer 2

In general, people think about overfitting as a function of the model complexity. Which is great, because model complexity is one of the things that you can control. In reality, there are many other factors that are related to the overfitting problem: - number of training samples - number of iterations - the dimension of the input ( in your case , I believe this is the reason why you are not overfitting) - the difficulty of the problem:if you have simple problem, linearly separable, then you do not to worry much about overfitting.

There is a visual demo provided by google tensorflow that allows you to change all these parameters. http://playground.tensorflow.org You can change you input problem, the number of samples, the dimension of your input, the network, the number of iterations.

I like to think about overfitting as Overfitting = large models + unrelated features