18
$\begingroup$

I just read this article: Understanding Deep Learning (Still) Requires Rethinking Generalization

In section 6.1 I stumbled upon the following sentence

Specifically, in the overparameterized regime where the model capacity greatly exceeds the training set size, fitting all the training examples (i.e., interpolating the training set), including noisy ones, is not necessarily at odds with generalization.

I do not fully understand the term "interpolating" in the context of fitting training data. Why do we speak of "interpolation" in this context? What does the term exactly mean here? Is there any other term that can be used instead?

In my understanding interpolation means the prediction within the training domain for some novel input that was not part of the training set.

$\endgroup$
1

4 Answers 4

24
$\begingroup$

Your question already got two nice answers, but I feel that some more context is needed.

First, we are talking here about overparametrized models and the double descent phenomenon. By overparametrized models we mean such that have way more parameters than datapoints. For example, Neal (2019), and Neal et al (2018) trained a network with hundreds of thousands of parameters for a sample of 100 MNIST images. The discussed models are so large, that they would be unreasonable for any practical applications. Because they are so large, they are able to fully memorize the training data. Before the double descent phenomenon attracted more attention in the machine learning community, memorizing the training data was assumed to lead to overfitting and poor generalization in general.

As already mentioned by @jcken, if a model has a huge number of parameters, it can easily fit a function to the data such that it "connects all the dots" and at prediction time just interpolates between the points. I'll repeat myself, but until recently we would assume that this would lead to overfitting and poor performance. With the insanely huge models, this doesn't have to be the case. The models would still interpolate, but the function would be so flexible that it won't hurt the test set performance.

To understand it better, consider the lottery ticket hypothesis. Loosely speaking, it says that if you randomly initialize and train a big machine learning model (deep network), this network would contain a smaller sub-network, the "lottery ticket", such that you could prune the big network while keeping the performance guarantees. The image below (taken from the linked post), illustrates such pruning. Having a huge number of parameters is like buying piles of lottery tickets, the more you have, the higher your chance of winning. In such a case, you can find a lottery ticket model that interpolates between the datapoints but also generalizes.

Animated illustration of an algorithm pruning a neural network to a smaller sub-network.

Another way to think about it is to consider a neural network as a kind of ensemble model. Every neural network has a pre-ultimate layer (image below, adapted from this), that you can think of as a collection of intermediate representations of your problem. The outputs of this layer are then aggregated (usually using a dense layer) for making the final prediction. This is like ensembling many smaller models. Again, if the smaller models memorized the data, even if each would overfit, by aggregating them, the effects would hopefully cancel out.

Fully connected neural network diagram. The last hidden layer is circled in red.

All the machine learning algorithms kind of interpolate between the datapoints, but if you more parameters than data, you would literally memorize the data and interpolate between them.

$\endgroup$
4
  • $\begingroup$ Thanks for that useful answer! But how is it possible that a model interpolates / memorizes the training data, but at the same time is so flexible that it won't hurt the test set performance? I don't find this to be very intuitive. Could you help me with that? $\endgroup$
    – Gilfoyle
    Jun 24, 2021 at 10:22
  • 4
    $\begingroup$ @Samuel obviously, you need test data to come from the same distribution to achieve this. In such a case, this is just learning by example. One can argue that humans do a similar thing, if I tell you to imagine a dog of a size between a chihuahua and husky, your brain would probably be able to generate an impression of some dog of this size, resembling the dogs you already saw in your lifetime, it'll be a kind of interpolation, if not just recall of an actual dog you memorized. $\endgroup$
    – Tim
    Jun 24, 2021 at 10:29
  • 1
    $\begingroup$ Woah, what a great way to explain it. Thanks! $\endgroup$
    – Gilfoyle
    Jun 24, 2021 at 11:22
  • 2
    $\begingroup$ @Samuel There is very interesting research on the phenomenon of "benign overfitting". In this paper Bartlett et al. prove for a linear model with lots of dimensions, that it can obtain near optimal test error (with guarantees) even when noise is injected into the labels. The idea is that because one has so many parameters, it is possible to "hide" the noise / variability into the fitted parameters, so that many of them will handle uninformative directions in feature space. The drawback is that this makes the models very sensitive to adversarial attacks! $\endgroup$
    – Miguel
    Jun 24, 2021 at 16:45
13
$\begingroup$

In layman's terms, an interpolator will literally 'join the dots'.

Here's a simple graphical summary of what interpolation can do and why it can be awful. I'd like to stress that interpolation does play a useful role in statistics/ml but should be used carefully. The black dots are training data and the red crossed are a similar dataset drawn form the same data generating process - they can be though of as a test set. Image of a linear fit to data (left) and a high order polynomial interpolator (right)

We can see the in the left hand plot fits okay to both the training and test data. On the left I just used linear regression to fit a line to the data (just $2$ parameters). The curve in the right hand plot perfectly predicts the training set but looks nothing like the test set. I'd used an $11^{th}$ order polynomial (plus intercept) to fit the interpolator. Additionally, on the test set, the linear fit gives $MSE = 23.8$, the interpolator gives $MSE = 10350842349$ -- not good!

$\endgroup$
3
  • $\begingroup$ Can you give an intuition what "joining the dots" in image space looks like? Is it possible to transfer the right plot to images or other abstract representations of data? $\endgroup$
    – Gilfoyle
    Jun 24, 2021 at 8:48
  • 1
    $\begingroup$ A computer just stores an image as rgb value for each pixel (usually each rgb value is from $\{0, 1, 2, \ldots, 255 \}$). So your model will just predict rgb values for each pixel - 'joining the dots' in this case will just be interpolating these values. Likewise, any other data representation will be converted to a number for a model to deal with it $\endgroup$
    – jcken
    Jun 24, 2021 at 8:52
  • $\begingroup$ It's not really the fact that it's "joining the dots" which is the problem in these examples though - it's the way it's doing it. If you linearly interpolated between the black dots the model would be poor but it would somewhat fit the test data. The terminology "interpolating the training data" is a bit loose, I guess what it really means is overfitting the training data in a way that doesn't generalise to the test data? Or at least the inductive bias of the model is such that the interpolation between training data instances doesn't match the structure of the data? $\endgroup$ Jun 26, 2021 at 1:43
7
$\begingroup$

Apart from literal meaning of interpolation, this is related to something called deep learning models totally memorize the training data. Hence, both interpolating and memorisation in this paper/context means zero training loss but still not overfitting on the test set. Hence the curious phenomena, that normally we would call an overfitting (overtraining actually), which is not resolved yet.

$\endgroup$
2
  • 2
    $\begingroup$ I don't understand this part of your answer "but still not overfitting on the test set". Can we ever overfit the test data? Can you please elaborate on that a bit more? $\endgroup$
    – Gilfoyle
    Jun 24, 2021 at 8:43
  • $\begingroup$ It meant to imply, deep learning models do not give predictions of overfitted model even though it "memorise/interpolate" the training set, as phenomenon suggests. $\endgroup$ Jun 24, 2021 at 8:53
3
$\begingroup$

I would add, the quote actually contains the definition, "fitting all the training examples... including noisy ones". So the training loss is zero. The comment "including noisy ones" implies the the data is generated by a process say

$y= f(x) + \epsilon$

Where $\epsilon$ represents noise. By fitting the model such that $y=f(x)$ for every training example even when $\epsilon$ is non-zero you are interpolating.

$\endgroup$
3
  • $\begingroup$ The explanation is a little confusing since it says “fitting to every example even if noise is non-zero”, in statistics we generally assume non-zero noise for all samples, as they are thought as random variables. Also, no algorithm distinguishes between noisy and non-noisy examples. $\endgroup$
    – Tim
    Jun 26, 2021 at 5:00
  • $\begingroup$ Actually this goes into deep learning models being a regularisers by construction. $\endgroup$ Jun 26, 2021 at 12:25
  • $\begingroup$ @Tim interpolation algorithms (generally) assume no noise though, i.e. if you use a spline interpolator you're fitting a curve $y=f(x)$ which is different to the assumption in statistics that "we generally assume non-zero noise for all samples". $\endgroup$ Jun 27, 2021 at 5:26

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.