Why can neural networks generalize at all?

Question

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?

Answer 1

You've asked a question which is basically one of the most important open questions about neural networks. The answer is a huge mystery - any response to this question which immediately opens with a purported explanation is basically ridiculous. We don't know.

As you pointed out, the issue is that the training set simply does not contain enough information to uniquely specify the target function. On an infinite input domain like $\mathbb R^n$, no finite number of samples is enough to uniquely determine a single function, even approximately. Even accounting for bounds and discretization of the input, and even for the symmetries our architectures impose on the output function, our training sets are microscopic compared to the sizes of our input domains. The problem that neural networks successfully solve every day should be impossible.

You can think about this in a low dimensional input space to get some intuition. Doing supervised binary classification on the unit square (that is, your input is a pair of numbers) is equivalent to trying to determine a monochrome image by seeing a random sample of some of its pixels. In terms of the size of the training set relative to the size of the input domain, what neural networks do on say an image classification task like MNIST is comparable to, say, guessing a 1000x1000 monochrome image almost perfectly by observing 20 random pixels, and even 20 is probably generous. The task is impossible - unless you know something about what the target image is. If you know that the image (the target function) is restricted to some set $H$ of functions, then you might be able to determine it approximately from a finite sample. Neural networks must in some sense be doing this implicitly, with some set of "nice" functions $H$ which, it seems, happens to contain (approximations to) a lot of the functions we actually want them to learn, like the "is a cat" function on the space of all images.

The study of such sets of "nice" functions, and in particular how small they need to be before learning is possible, is the subject of statistical learning theory. But I'm not aware of any plausible answers for what $H$ could be for neural networks.

Answer 2

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.

Answer 3

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.

Answer 4

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.