Confused about the notion of overfitting and noisy target function

Question

So I am reading a textbook called "Learning from Data" by Abu Mostafa et al.

I am confused about the following concepts:

1. According to the authors, most real-world target functions $f$ are not deterministic, such as $f(x) = \sin(x)$, but are noisy. In other words, a noisy target function can be expressed as the summation between a deterministic target function and noise. You can hear the authors say this here. The authors further emphasized that a noisy target function is represented by the probability distribution $P(y|x)$, which is what we are trying to learn.

2. According to the authors, overfitting is when the model achieves a small training error while having a large test error. The reason is because we are fitting onto the noise. This is undesirable because we are getting a large test error. See here.

Wait a moment...

1. Most of the real-world target functions are noisy.
2. We are trying to learn target functions (in the real world).
3. Overfitting causes the model to fit onto the noise.

But isn't this exactly what we want? We are training a model to fit a noisy target function. Can someone please clarify or resolve this for me?

Some further context directly taken from the Learning from Data textbook:

(P. 31) Noisy Targets: In many practical applications, the data we learn from are not generated by a deterministic target function. Instead, they are generated in a noisy way such that the output is not uniquely determined by the input. For instance, in the credit-card example, two customers may have identical salaries, outstanding loans, etc., but end up with different credit behavior. Therefore, the credit 'function' is not really a deterministic function, but a noisy one.

This situation can be readily modeled within the same framework that we have. Instead of $y = f(x)$, we can take the output $y$ to be a random variable that is affected by, rather than determined by, the input $x$. Formally, we have a target distribution $P(y|x)$ instead of a target function $y = f(x)$. A data point $(x, y)$ is now generated by the joint distribution $P(x, y) = P(x)P(y| x)$.

One can think of a noisy target as a deterministic target plus added noise. If $y$ is real-valued for example, one can take the expected value of $y$ given $x$ to be the deterministic $f(x)$, and consider $y - f(x)$ as pure noise that is added to $f$.

The author emphasized multiple times elsewhere that we need to learn $P(y|x)$, which is the noisy target. Since the noisy target is deterministic target plus noise, therefore learning the noisy target, logically, means learning the noise as well.

The authors then went on saying:

Why does a higher target complexity lead to more overfitting when comparing the same two models? The intuition is that for a given learning model, there is a best approximation to the target function. The part of the target function 'outside' this best fit acts like noise in the data. We can call this deterministic noise to differentiate it from the random stochastic noise. Just as stochastic noise cannot be modeled, the deterministic noise is that part of the target function which cannot be modeled. The learning algorithm should not attempt to fit the noise; however, it cannot distinguish noise from signal. On a finite data set, the algorithm inadvertently uses some of the degrees of freedom to fit the noise, which can result in overfitting and a spurious final hypothesis.

Answer 1

As they mention in the video, the classic mathematical definition of a function you typically hear about in algebra or calculus is that a function has a given domain (inputs) and range (outputs), wherein the inputs can only have one unique output. One commonly taught way to test this is the "vertical line test", where you draw a vertical line through a plot of $(x,y)$ values and see if you hit a line twice. An example below:

A sin curve is an example of this function if we have that exact function. A normal sin curve spans the range of $[-1,1]$. This passes the vertical line test.

The real world is rarely so convenient. Suppose we are trying to find the actual function, $\sin(x)$, but we have all this noise:

We have to find the real function via approximation. However, if we simply "chase the noise" by overfitting, we can get something like this, which fits a line to the data really well, but is not really approximating the underlying function. This is the essence of overfitting.

By trying not to chase the noise, we can get a better approximation of the true function by not trying to fit every point on the graph. Here I have fit a spline with 10 degrees of freedom (red) and the actual $\sin(x)$ function (blue). Even here we are not doing an amazing job, but were are doing better than before (the last spline used 200 degrees of freedom by comparison).

By doing this we have let the data speak for us rather than the other way around. So to answer your questions:

Most of the real-world target functions are noisy.

This is true, as shown by nearly any linear regression that is performed in the real world. In fact, this is the essence of the typical simple linear regression formula:

$$ y = \beta_0 + \beta_1 \cdot x + \epsilon $$

where our $\epsilon$ here, the error, is the "leftover" information we failed to capture. Having nearly zero error is often suspect and warrants concern, for reasons outlined earlier.

We are trying to learn target functions (in the real world).

We are trying to learn target functions, but rarely will you ever get an exact function unless it is already known.

Overfitting causes the model to fit onto the noise.

As demonstrated above, we can wildly overestimate where our function is by chasing noise. If we fit this to a regression, our predictions will be terrible, as the regression will be overly confident in where the data should be and thus anything that ranges outside of the "guesses" will misfire by a lot.

Edit

For clarification since OP asked further questions, this particular comment from @num_39 sums it up:

There is no contradiction. We are trying to learn a target function that is a) deterministic + b) noise. There is nothing to be learned from noise. The noise in one sample is unrelated to the noise in the next sample. Anything we fit to noise in a particular sample will not tell us anything about the target function.

You are trying to accomplish two goals...you try to fit data to a noisy function (and approximate it through things like residual standard error, etc.) but also try not to fit the regression so precisely that it doesn't generalize. What the book is getting at is you need some kind of "sweet spot" between finding what the signal is without letting the noise do all the talking.

Lets say we fit a line very close to the points in one sample using R with a similar function as before.

#### Library and Seed ####
library(splines)
set.seed(123)

#### Sample 1 ####
x <- runif(1000,-10,10)
y <- sin(x) + rnorm(n=1000,sd=.5)
plot(x,y)
sp <- smooth.spline(x,y,df=200)
lines(sp,col="red")

We then find a new sample which more closely resembles a sin wave. We fit our previously crafted regression to see if it predicts this second dataset's distribution.

#### Sample 2 ####
x2 <- runif(1000,-10,10)
y2 <- sin(x2) + rnorm(n=1000,sd=.1) 
plot(x2,y2)
lines(sp,col="red")

We find now that our data points are far above and below where we predicted they should be. It also still doesn't show the general trend well, as its quite erratic compared to the actual function that generated this data. So in short, our original model did a poor job because it also needs to generalize to other samples, where here it did not because its overfit.

Answer 2

(This terminology is confusing.)

What you want to do in the scenario you be described is to learn $\sin(x)$. This wouldn’t be so hard if every point were on the curve $y=\sin(x)$, but you have noise that corrupts this perfect sinusoidal signal. In other words, you have $y=\sin(x)+\epsilon$, where $\epsilon$ is some kind of noise.

I think the authors mean that $y=f(x,\epsilon)=\sin(x)+\epsilon$ is the noisy function, but it’s absolutely the $\sin(x)$ that you are trying to learn while the noise tries to trick you into believing it to be part of the “true” sine signal. Consider overfitting to be when you badly fall for the noise’s deception.

Answer 3

The key point is that the noise is random and therefore not the same in the training and the test data.

For the underlying function the basic assumption of modelling is that if you plug in the same x value you get back the same value f(x) every time both in the training data and in the test data. For real world data this is a bit to simplistic. When you plug in the same value x multiple times you get back f(x) plus some small noise term and the noise term is different every time you do it. If you learn the noise your model would try to predict the noise terms you had in the training data. But these noise terms are different from what you have in the test data so this wouldn't be useful.

Answer 4

To answer both your question and the comment:

I am not interested in knowing why we don't want to overfit, or why we don't want to learn noise, but rather, why do the authors say that we want to learn a noisy target (deterministic 𝑓 + non-deterministic noise), but then says that the overfitting problem occurs because we are fitting onto the noise? Are we learning the noise or not?

I'm afraid no-one, except maybe the authors, can give an answer to "why do the authors say". But, regarding "Are we learning the noise or not", I can offer my interpretation.

From the part of the video you linked, I recon he wants to say that we want to learn the probability distribution $P(y | {\bf x})$. Now, the probability distribution can be described by its CDF (or, alternatively, PDF) and the parameters. For example, the well-known one-dimensional normal distribution is given by its PDF: $$ f(y) = \frac{1}{\sigma \sqrt{2\pi}}\exp\left({-\frac{(y-\mu)^2}{2\sigma^2}}\right) $$ Here, $\mu$ and $\sigma$ are the parameters of the distribution. If they are constant, the whole distribution is constant, too, in the sense that it doesn't depend on ${\bf x}$. But, we can make them functions of $\bf x$, for example $\mu({\bf x}) = {\bf \beta x} + \beta_0$. This is what we do in linear regression. So $P(y | {\bf x})$ describes how $y$-values are distributed depending on ${\bf x}$---in case of linear regression they follow a normal distribution centred around $\mu({\bf x})$. This is the noisy target function we want to learn. It consists of a deterministic part, $\mu({\bf x})$, and the noise, which follows the normal distribution around zero.

Overfitting happens when you mistake (part of) the noise for the deterministic part. This is usually the case when you assume the form of the deterministic part to be more complex than it really is. Returning to the linear regression example, you could assume the parameter $\mu$ to be some high-degree polynomial of $\bf x$, while, in reality, it is (or can be better approximated by!) a simple linear function. The polynomial can fit random oscillations ("noise") in the observed data better than a simple linear function because it has more degrees of freedom. But, as an approximation of the parameters of the true underlying probability distribution it is actually worse.

So, to return to your question:

Are we learning the noise or not?

I believe the author wanted to say that we want to learn the distribution function behind the noise and to avoid treating the noise in the observations as the result of the deterministic part of the target function.

---

A little side note by me: Taking the author's words literally, he seems to imply that in machine learning we try to learn the both the probability function and its parameters. In my experience, this never happens. The probability function is normally fixed in advance, based on our domain knowledge, and the only thing we try to learn are its parameters. But I doubt the author really wanted to say that. Expressing oneself precisely and clearly is high art. I apologise in advance if I wasn't precise or clear enough.

Answer 5

^{Edit: Watching the video further, I see that they meant something else. I leave my answer anyway as a useful answer for people that land on this question and have a different interpretation of the question. The use of the term 'noisy function' in the article relates to the observed and predicted values being variable. The function itself is not necessarily noisy and can still behave as a straight line. But it is multivalued and describes the output, observation/prediction, as a function rather than a single value (so it is a function that maps $x$ to a function $f(y)$)}

1. Most of the real-world target functions are noisy.
2. We are trying to learn target functions (in the real world).
3. Overfitting causes the model to fit onto the noise.

The real-world target function is not noisy or random. It is a fixed value.

For example the distribution of average gold and oil under the ground is a fixed value. If you dig in one single place and measure all the available resources, then you will find a certain specific total amount, and if you dig another time in the same place you wil again find the same total amount. It is not like rolling a dice that the amount of gold and oil is variable each time you dig in the same place.

However, the real-world target function is not a pretty and simple function. The amount of gold and oil in the ground varies from place to place and it is not like you can always use a straight line or polynomial to fit it's the distribution. In particular, the amount is probably having an origin in a random process. So it is a function that has in some way a random behaviour. For a linear function, if you find in x-positions 1,2,3,4 the values 11, 19, 33, 41, then for x-position 5 you might extrapolate the underlying function and expect a value that is something around 50. For the amount of gold or oil it may not be like that. Possibly if you find gold or oil in some place, it may have an effect on neighbouring points, but far away it has little effect.

The problem is the type of noise that is due to measurement errors. When we measure the amounts of gold and oil in the ground, by taking probes, then there will be either errors due to the measurements being inaccurate, or due to the sample being a bad representation of the average in the area. We could be sitting on top of a rich oil field, but happen to dig oreasure just in a place where there is little.

The problem of inference is to find an estimated value for a distribution property that resembles the true properties of the distribution (e.g. the average amount of oil/gold in some area). The true properties may behave like a noisy function, but that is different from the noise that troubles the inference (sampling and measurement).

---

A related concept to study might be a Gaussian process and more specifically 'latent Kriging' as explained here: Wikipedia article: nonlinear mixed effects model; Example: Prediction of oil production curve of shale oil wells at a new location with latent kriging

Answer 6

The use of the term 'noisy function' in the article relates to the fitting describing a deterministic (not neccesarily noisy) part plus the noise. The problem with overfitting is that we may confuse the noisy part for the deterministic part.

In a way the fitted function is a multivalued target function. The function itself is not necessarily noisy and can still behave as a deterministic straight line (as the example below shows). But, the function is multivalued and describes the output, observation/prediction as noisy data.

Below is an example with an image of a fit to 10 points:

• right: The points are fitted with a polynomial curve that goes through every point. This does not really look sensible (and in fact, it is also not how the data was created which was by using a linear curve plus noise)
• left: The points are not fitted with a single curve, but with a multivalued function, depicted by the shaded area. The line is the center of this area. The colour of the area relates to the hight of the function and represents a probability density (the probability density of the distribution of the points)

So in a way the function is random. Not it's parameters, but the output that it describes. What we often want to fit is the description of that function and that can still be a straight line (like in the example) and should not be fitted to go through all the points exactly.