1
$\begingroup$

enter image description here

Here, the data $x$ are randomly generated, and $t$ are generated by running $x$ through a function $\sin(2\pi x)$, then Gaussian noise is added.

Bishop's text then tries to fit those data using a polynomial of 9th degree, i.e., $y(x,w) = w_o + w_1 x + \ldots + w_Mx^M$ (Shown in figure)

Then they showed that this results in large mean squared error for test data.

And the reason being that the weights associated with each of the parameters is extremely large, something like $w_i = O(1000000)$

But is this a fluke?

Why does the polynomial's weight need to be so large?

A polynomial of 9th order needs to have 8 bumps.

That's all it needs. So Bishop's curve could simply look like the black curve which I drawn.

enter image description here

No more huge weights, problem solved.

Can someone comment on why must the weights associated with the polynomial be so large when I fit a high order polynomial, instead of having smaller weight like the curve I drew?

Is this simply a simulation error in Bishop's text, or does solving the optimization problem actually give you weight that large (which I do not believe)?

Added: Exact weights as shown in textbook

enter image description here

Experiment: Poly-fitting in R using same data

enter image description here

$\endgroup$
  • 3
    $\begingroup$ There's no "optimization problem" involved: you can interpolate 10 points with a 9th order polynomial exactly by computing the Lagrange polynomial. We would need the actual points from the book to compute these coefficients. The "eyeballing" in the answer below won't work; the point of the overfitting example is that it is extremely sensitive to the values so we need them exactly. $\endgroup$ – Chris Haug Jan 23 '19 at 1:40
  • $\begingroup$ These are the points: x = 0.6020 0.2630 0.6541 0.6892 0.7482 0.4505 0.0838 0.2290 0.9133 0.1524 t = -0.3095 1.0339 -0.3928 -1.5162 -1.0592 -0.0566 1.3751 1.2389 -0.1043 0.5003 $\endgroup$ – The man of your dream Jan 23 '19 at 1:42
  • 2
    $\begingroup$ That doesn't look right; did you generate data in a similar manner as the book, or are these literally the numbers that are quoted in the book? The point of the example is that overfit models have high variance, so you will get very different weights depending on your exact data, even generated by the same process. $\endgroup$ – Chris Haug Jan 23 '19 at 1:49
  • $\begingroup$ Same manner: N = 10 x = rand(N,1) t = sin(2*pi*x) + normrnd(0, 0.3,[N,1]) $\endgroup$ – The man of your dream Jan 23 '19 at 1:51
5
$\begingroup$

Providing it as answer, since it is too long for a comment.

If you want to reproduce the results, you need to use the actual data. As noticed in the comments, if there was no seed for random generator provided, then other random sample obtained using the same procedure wouldn't be equivalent to using original data, especially since the sample is so small. You should use the original data and the same procedure.

Fortunately, this can be easily done. There are many tools both offline and online, that let you to extract (manually, or automatically) from the plots. Since the sample is small, doing this manually takes less then minute. Here is the extract:

  0, 0.3431578947368421
  0.11133603238866399, 0.8273684210526313
  0.222672064777328, 1.0084210526315789
  0.3340080971659919, 0.9705263157894736
  0.4443319838056681, 0.12842105263157877
  0.5556680161943321, 0.16210526315789453
  0.6680161943319839, -0.8526315789473684
  0.7783400809716601, -0.4526315789473685
  0.888663967611336, -0.5705263157894738
  1, 0.25473684210526315

If you used the code in Mark White's answer, but accounting for the fact that R uses orthogonal polynomials, while Bishop used raw polynomials, as noticed in the comment by @civilstat, then you'll get results that look very much alike as in Bishop's book.

ggplot(mapping = aes(x = x, y = y)) +
  geom_point() +
  geom_smooth(method = "lm", se = FALSE, formula = y ~ poly(x, 9, raw = TRUE)) +
  coord_cartesian(ylim = c(-1, 1))

enter image description here

What is worth emphasizing, is that Bishop use this example to show that it is possible to find a model that fits the data, while overfitting, he does not claim that this solution is optimal in any sense. The point is simply, that the fact that your model fits the training data does not prove that it is a good model. The example is not exaggerated in the sense, that if you used optimization algorithm to find the best fitting for ninth-degree raw polynomial, then this is what the algorithm finds as optimal solution given the constraints. Your hand-drawn line is not a polynomial, unless you can find parameters that fit polynomial that has perfect fit that looks like this, can you?

$\endgroup$
  • $\begingroup$ Hi thanks for the answer. Do you have the coefficients associated with your polynomial? $\endgroup$ – The man of your dream Jan 23 '19 at 14:57
  • $\begingroup$ @Themanofyourdream yes, I can estimate them, but their values are meaningless in here, so why would it matter? $\endgroup$ – Tim Jan 23 '19 at 15:05
  • $\begingroup$ How can you be sure it is the same polynomial if you don't have the weights. I mean they do look similar, but still.. $\endgroup$ – The man of your dream Jan 23 '19 at 17:53
  • $\begingroup$ @Themanofyourdream I didn't say it's the same, but that it looks very similar. Why is this a concern for you? The example does not claim show optimal or best solution, it shows some solution. $\endgroup$ – Tim Jan 23 '19 at 17:59
2
$\begingroup$

I eyeballed and approximated the data in R:

dat <- data.frame(
  x = seq(0, 1, length.out = 10), 
  y = c(.3, .8, 1, .95, .1, .15, -.8, -.5, -.6, .25)
)

I'm not sure what you mean by the weights being large; it seems like your notation means the coefficients. They aren't that large:

> as.matrix(lm(y ~ poly(x, 9), dat)$coef)
                   [,1]
(Intercept)  0.16500000
poly(x, 9)1 -1.26335592
poly(x, 9)2  0.15231795
poly(x, 9)3  1.33490536
poly(x, 9)4  0.03646293
poly(x, 9)5 -0.04117661
poly(x, 9)6  0.13039857
poly(x, 9)7  0.04127680
poly(x, 9)8  0.15800604
poly(x, 9)9  0.50725754

Part of the reason that the line looks so wild is that the y-axis is limited to about -1 and 1. We can plot a ninth-order polynomial with and without having a y-axis limit:

ggplot(dat, aes(x = x, y = y)) +
  geom_point() +
  geom_smooth(method = "lm", se = FALSE, formula = y ~ poly(x, 9))

enter image description here

ggplot(dat, aes(x = x, y = y)) +
  geom_point() +
  geom_smooth(method = "lm", se = FALSE, formula = y ~ poly(x, 9)) +
  coord_cartesian(ylim = c(-1, 1))

enter image description here


Apologies, I read too quickly and didn't see the $\sin(2\pi x)$ bit. The comment by Chris Haug is probably right. I can't reproduce it correctly:

x <- seq(0, 1, length.out = 10)
y <- sin(2 * pi * x)

as.matrix(lm(y ~ poly(x, 9))$coef)

                     [,1]
(Intercept) -9.645959e-17
poly(x, 9)1 -1.361193e+00
poly(x, 9)2 -4.462868e-16
poly(x, 9)3  1.606816e+00
poly(x, 9)4 -2.927905e-16
poly(x, 9)5 -2.552363e-01
poly(x, 9)6  1.293542e-16
poly(x, 9)7  1.222198e-02
poly(x, 9)8  2.953532e-16
poly(x, 9)9 -1.487057e-04

ggplot(mapping = aes(x = x, y = y)) +
  geom_point() +
  geom_smooth(method = "lm", se = FALSE, formula = y ~ poly(x, 9))

enter image description here

The random number code you wrote in the comment won't work, either, I'm afraid, as there's no random seed to make sure everything is the same from simulation to simulation.

$\endgroup$
  • $\begingroup$ I appended his weights in the question; weights are coefficients $\endgroup$ – The man of your dream Jan 23 '19 at 1:37
  • $\begingroup$ I used his exact technique to generate the points, try to fit this: x = 0.6020 0.2630 0.6541 0.6892 0.7482 0.4505 0.0838 0.2290 0.9133 0.1524; t = -0.3095 1.0339 -0.3928 -1.5162 -1.0592 -0.0566 1.3751 1.2389 -0.1043 0.5003 $\endgroup$ – The man of your dream Jan 23 '19 at 1:42
  • $\begingroup$ I updated this after reading the underlying process closer. $\endgroup$ – Mark White Jan 23 '19 at 1:53
  • $\begingroup$ You still have tiny weights though... $\endgroup$ – The man of your dream Jan 23 '19 at 1:59
  • $\begingroup$ Correct—I'm not sure how the book is getting those weights, or what those weights mean. $\endgroup$ – Mark White Jan 23 '19 at 2:00
1
$\begingroup$

A polynomial of 9th order needs to have 8 bumps.

That's all it needs. So Bishop's curve could simply look like the black curve which I drawn.

When we eyeball a curve, we tend to draw something more like a spline: a piecewise-polynomial solution to an optimization problem that penalizes jagged curves in favor of smoother curves.

Indeed, with the help of @mark-white's example data, we can ask R's smooth.spline() function to fit a cubic smoothing spline. By using as many degrees of freedom as there are data points, the spline will interpolate, and we get a curve very much like your hand-drawn black curve.

dat <- data.frame(
  x = seq(0, 1, length.out = 10), 
  y = c(.3, .8, 1, .95, .1, .15, -.8, -.5, -.6, .25)
)
plot(dat$x, dat$y)
ss = smooth.spline(dat$x, dat$y, df = nrow(dat))
lines(predict(ss, x = seq(0, 1, length = 100)))

SmoothingSpline

Can someone comment on why must the weights associated with the polynomial be so large when I fit a high order polynomial, instead of having smaller weight like the curve I drew?

Is this simply a simulation error in Bishop's text, or does solving the optimization problem actually give you weight that large (which I do not believe)?

As the other answers have shown, the extreme weights and jagged nature of Bishop's polynomial are correct for this dataset. What you've drawn isn't a bad fit to the data, but it also isn't a single polynomial. As I understand it, the smoothing spline is drawing separate cubic curves between each pair of data points, and ensuring that the overall curve looks smooth by matching up derivatives where the cubics meet. Since Bishop's single polynomial doesn't have this piecewise nature, it doesn't look as smooth as the spline or your sketch. Although the regularized spline estimate still overfits compared to the true sine curve, it isn't as bad as the polynomial.

In other words: Bishop's example isn't an exaggeration, and overfitting is a real problem, but we do have some ways to mitigate it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.