Relation between size of parameters and complexity of model with overfitting

Question

I'm reading the book Pattern Recognition and Machine Learning by Bishop, specifically the intro where he covers polynomial regression model. In short, let's say we generate $10$ data points using the function $\sin(2\pi x)$ and add some gaussian random noise to each observation. Now we pretend not knowing the generating function and try to fit a polynomial model to these points.

As we increase the degree of the polynomial, it goes from underfitting ($d=1,2$) to overfitting ($d=10$). One thing the author notes is that the higher the degree of the polynomial, the higher the values of the coefficients (parameters). This is my first doubt: why does the size of the coefficients increase with the polynomial degree? And why is the size of the parameters related to overfitting?

Secondly, he states that even for degree $10$, if we get sufficiently many data points (say $100$), then the high degree polynomial will no longer overfit the data and should have comparatively better generalization performance. Second doubt: Why is this so?

Answer 1

Part 1: Why does the size of the coefficients increase?

You do not specify what you mean exactly. At first reading I thought you meant the size of each coefficient itself increases, but on second reading I thought maybe the statement in the book is supposed to lead to regularisation, and hence the sum of absolute parameter values is noticed to increase.

Here is some code to show that the value of each coefficient does not necessarily increase, while the sum of absolute coefficients (obviously) does, as you have more of them in the model:

set.seed(1)
x <- seq(0, 2*pi, len=100)
y <- sin(2*pi*x) + rnorm(100, sd=0.1)
plot(x, y, type="l")

sample10 <- sample(100, 10)
xy10 <- cbind.data.frame(x, y)[sample10,]
plot(xy10)

coef(lm(y ~ poly(x,1), xy10)) # 0.0495 -0.8541
coef(lm(y ~ poly(x,2), xy10)) # 0.0495 -0.8541  0.55887 
coef(lm(y ~ poly(x,5), xy10)) # 0.0495 -0.8541  0.55887  0.97975 1.4309 -0.282

sum(abs(coef(lm(y ~ poly(x,1), xy10)))) # 0.9
sum(abs(coef(lm(y ~ poly(x,2), xy10)))) # 1.4
sum(abs(coef(lm(y ~ poly(x,5), xy10)))) # 4.1

As a result, I cannot really answer the second part of your first question: each parameter separately does not increase. But obviously, the more parameters you have, the larger their absolute sum. Hence, at whatever level you start overfitting, this sum will be larger than with lower-dimensional polynomials (a bit trivial, I guess).

Part 2: Why is it better to have a high-order polynomial to fit a sine-function when you have many data points?

My humble understanding is that any continuously differentiable function can be approximated, over a closed interval, by a polynomial (Stone–Weierstrass theorem). Adding more data, you will be able to identify the most suitable polynomial better. If your function is simple, let's say even linear, then the higher-order terms of the polynomial can still be better estimated to be 0; hence, the "generalisation performance" increases.

Several notes may be warranted:

• An example would help. I am not sure I interpreted your question correctly.
• The domain of the function in the example is [0, $2\pi$]. If you are thinking of many more periods, then you need many more data points before you "get it right".
• Of course there is substantially more scope for overfitting as the number of dimensions increases (falling prey to the curse of dimensionality). Hence, while in this toy example higher-order polynomials do just fine, imposing a constraint on the absolute value of the coefficients (shrinkage, e.g. using the L1 or L2 norm) is often indicated in the context of multiple regression (and equivalent machine-learning approaches).
• I used orthogonal polynomials (function poly in R); results will differ if you use non-orthogonal polynomials.