Why can neural networks generalize at all?

Neural networks are incredibly good at learning functions. We know by the universal approximation theorem that, theoretically, they can take the form of almost any function - and in practice, they seem particularly apt at learning the right parameters. However, something we often have to combat when training neural networks is overtfitting - reproducing the training data and not generalizing to a validation set. The solution to overfitting is usually to simply add more data, with the rationalization that at a certain point the neural network pretty much has no choice but to learn the correct function.

But this never made much sense to me. There is no reason, in terms of loss, that a neural network should prefer a function that generalizes well (i.e. the function you are looking for) over a function that does incredibly well on the training data and fails miserably everywhere else. In fact, there is usually a loss advantage to overfitting. Equally, there is an infinite number of functions that fit the training data and have no success on anything but.

So why is it that neural networks almost always (especially for simpler data) stumble upon the function we want, as opposed to one of the infinite other options? Why is it that neural networks are good at generalizing, when there is no incentive for them to?

• AFAIK, universal function approximation theorems show that, in theory, neural networks are capable of approximating continuous functions, which are, of course, not all functions. Neural networks seem to generalize in certain cases because the data they have been trained with is similar to the data they are tested on. Adversarial examples show that neural networks can catastrophically fail and don't really understand what they are supposed to do. – nbro Jan 1 at 0:00
• @nbro Although it has been shown that adversarial examples are signs that the neural network is learning robust and semantically rich features. Equally, while training and test data might be similar to us, who understand generalized features, the data usually isn't similar in terms of distance between tensors $n$-dimensional space, which is the way the computer "sees" it, or else you could solve every problem by k-means. The fact that a neural network can understand and cluster by those non-trivial, rich features leads back to my original question. – Nico A Jan 1 at 0:07
• I've not read that paper and I won't read it now. Given that we use neural networks to solve our problems, we expect them to be consistent with our knowledge, that is, if it's a cat according to us, it should also be a cat according to the neural network. You can fool neural networks even by changing only some pixels. (IMHO, neural networks don't understand anything, but this is a philosophical digression). – nbro Jan 1 at 0:18
• Don't we use a validation set to check when we are over fitting vs when we are actually generalizing? – DuttaA Jan 1 at 4:01

A neural network is composed of continuous functions. Neural networks are regularized by adding an l2 penalty on the weights to the loss function. This means the neural network will try to make the weights as small as possible. The weights are also initiallized with a N(0, 1) distribution so the initial weights will also tend to be small. All of this means that neural networks will compute a continuous function that is as smooth as possible while still fitting the data. By smooth I mean that similar inputs will tend to have similar outputs when run through the neural network. More formally, $$||x-y||$$ small implies $$||f(x)-f(y)||$$ small where f represents the output from the neural network. This mean that if a neural network sees an novel input $$x$$ that is close to an input from the training data $$y$$, then $$f(x)$$ will tend to be close to $$f(y)$$. So the end result is that the neural network will classify $$x$$ based on what the labels for the nearby training examples were. So the neural network is actually a little like k-nearest neighbors in that way.

Another way for neural networks to generalize is using invariance. For example, convolutional neural networks are approximately translation invariant. So this means that if it sees and image where the object in question has been translated then it will still recognize the object.

But it's not giving us the exact function we want. The loss function is a combination of classification accuracy and making the weights small so that you can fit the data with a function that is as smooth as possible. This tends to generalize well for the reasons I said before but it's just an approximation. You can solve the problem more exactly using minimal assumptions with a Gaussian process but Guassian processes are too slow to handle large amounts of data.

There is normally more to generalisation than just increasing training data. It helps to make the task noisy, through various means. One common and popular method is to use dropout, which encourages the network to utilise every node, and avoids dependencies on small clusters of nodes.

So how does making the task more noisy help with generalisation? Well it's easy to explain with a conceptual example, but I don't think that's what you're looking for, rather a more mathematical approach.

The best way to think of it is with a simple example of a polynomial data set, in only 2 dimensions. If you consider this, and the way the network slowly approaches optimums through back propagation, the concept that the classification boundary gradually approaches the optimum, which in all cases is an over-fit function, isn't too far fetched.

Now considering this, this would suggest that in order to properly train a network, we would need some way of determining when the network isn't super close to the optimum (as it will have over-fit by then) but also isn't so far from it that it's worse than randomly picking. This is were methods to improve generalisation come in, we want to hit that sweet spot.

If the learning rate is too high, we will overshoot that sweet spot and miss out entirely (the range can sometimes be very small), if it's too low, we may get stuck in tiny local minimums and never escape, or it could take years to reach it.

Using the example of dropout from before, this increases noise, and makes training harder on the network. Due to more difficult training, the network approaches the optimal function at a slower rate, and makes it easier to cut training when the network has generalised well.

Conveniently, this extends to n-dimensional problems as well. Now, as far as I know, there is no robust mathematical proof of why this works for n-dimensional problems. The reason for this, explains why neural networks even exist: We don't know how to mathematically classify these issues to the degree a NN does ourselves. Because of this, there will always be gaps in our knowledge. We will never be able to quantitatively say what a neural network is doing, without making them obsolete. So until we can figure it out for ourselves, we'll have to just perform testing against unseen data to see if the network has indeed generalised.

• It's misleading to say "dropout, which forces the network to utilise every node". You should reformulate your description of dropout, IMHO. – nbro Jan 1 at 1:35
• @nbro You're right, I changed forces to encourages – Recessive Jan 1 at 2:13
• What I meant is that, even without dropout, all units are involved. Moreover, dropout is usually only applied during training, although you can also apply it during testing (MC dropout). I would describe dropout as a way of training randomly chosen subsets of the network at every iteration, so that, in a way, you're training multiple smaller NNs to detect slightly different things. – nbro Jan 1 at 2:45
• @nbro I don't think that's the popular interpretation of dropout. – DuttaA Jan 1 at 5:46
• @DuttaA In dropout, at every iteration, you randomly select units and you drop them, so that you train only the ones you haven't dropped. I am familiar with dropout and MC dropout. In this case, my knowledge was mainly acquired while reading research papers. But I am curious, what's the popular interpretation you're talking about? – nbro Jan 1 at 11:55

A fairly recent paper posits an answer to this:
Reconciling modern machine learning practice and the bias-variance trade-off. Mikhail Belkin, Daniel Hsu, Siyuan Ma, Soumik Mandal
https://arxiv.org/abs/1812.11118
https://www.pnas.org/content/116/32/15849

I'm probably not qualified to summarize, but it sounds like their conjectured mechanism is: by having far more parameters than are needed even to perfectly interpolate the training data, the space of possible resulting functions expands to include "simpler" functions (simpler here obviously not meaning fewer parameters, but instead something like "less wiggly") that generalize better even while perfectly interpolating the training set.

That seems completely orthogonal to the more traditional ML approach of reducing capacity via dropout, regularization, etc.