10
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – nbro
    Jan 1, 2020 at 0:00
  • $\begingroup$ @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. $\endgroup$
    – Nico A
    Jan 1, 2020 at 0:07
  • 2
    $\begingroup$ 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). $\endgroup$
    – nbro
    Jan 1, 2020 at 0:18

5 Answers 5

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Maybe that's true in terms of a rigorous theorhetical basis but actually I see several 'intuitive' explanations including occam's razor, similarity, attractor states. The question is more which ones are right / contribute most. $\endgroup$ Jul 12 at 10:09
  • $\begingroup$ @BruceAdams Sorry, but that's garbage. Occam's Razor, for example, is completely subjective. What does "simplest" mean? It only pushes the question back one stage - why do neural nets find the same qualities "simple" that humans do? Same kind of problem with "similarity" - what's "similar"? You can always contrive to find something similar between any two objects. Why do neural nets like the same kinds of "similarities" people do? Even "intuitively", no one ought to find these kinds of explanations remotely satisfying. $\endgroup$
    – Jack M
    Jul 13 at 11:09
  • $\begingroup$ If you use the example from OP. A "wiggly" line is a more complex solution to a problem if you can draw a single line that goes close to or through all the target points. You can define that mathematically as having a lower error (distance measure from each point say) and less complexity (say a lower order polynominal is simpler) but not so easily in the context of SE post. $\endgroup$ Jul 15 at 0:16
  • $\begingroup$ "If you use the example from OP. A "wiggly" line is a more complex solution to a problem if you can draw a single line that goes close to or through all the target points." No, it isn't. What's complex about it? You as a human being intuitively like to call it more complex, it is not actually more complex. What is simple about some random number (polynomial degree) being smaller? I could just as easily say bigger is simpler, or define some new metric which is smaller for a curvy line than for a straight one. These are human factors, not mathematical or objective ones. $\endgroup$
    – Jack M
    Jul 15 at 12:53
  • $\begingroup$ It is mathematical or rather computational. You can define metrics for complexity. For example you could use the number of terms in an equation or the highest power in a polynomial. You have to fit your measures to the problem of course but it would be absurd to say that because there is no single universal definition of complexity it is not possible to create and use such measures. Many of these measures will share similar properties. An elephant is bigger than a cow if you measure its weight, its length or its volume. Each of those metrics is a useful measure of size. $\endgroup$ Jul 15 at 14:55
0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ It's misleading to say "dropout, which forces the network to utilise every node". You should reformulate your description of dropout, IMHO. $\endgroup$
    – nbro
    Jan 1, 2020 at 1:35
  • $\begingroup$ @nbro You're right, I changed forces to encourages $\endgroup$
    – Recessive
    Jan 1, 2020 at 2:13
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Jan 1, 2020 at 2:45
  • $\begingroup$ @nbro I don't think that's the popular interpretation of dropout. $\endgroup$
    – user9947
    Jan 1, 2020 at 5:46
  • $\begingroup$ @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? $\endgroup$
    – nbro
    Jan 1, 2020 at 11:55
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ In other words we have implementation of something like occam's razor in some models $\endgroup$ Jul 12 at 10:11
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Your question "Why can neural networks generalize at all" make no sense. Model does not simply either generalize or not in a black-or-white manner.

Perhaps what you mean is "Why does improving complexity of neural networks doesn't always cause the notorious bias-variance trade-off?"

To that my answer might be more controversial: Are we really sure that it doesn't?

The question is difficult to be verify in the sense that most of machine learning model (especially deep learning models) that perform really well currently arises from academia. So there is a mix of survival-of-the-fittest. While there might be bias-variance trade-off, it might be counteract with inductive biases employed by prior knowledge of the data scientist.

Then the remaining problem is how do we fairly and randomly adjust the variance of the model to significantly test the question? Unless we figure out how, I don't think we'll get an answer to your question any soon.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .