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

Regarding your first question, this is domain/task specific, and not always the case. My guess of why it happens in your situation (You did not specify your domain, so ill assume it's sometimes outside $(-1,1)$) is that higher order polynomials increase much faster than lower order ones so it may fall under the trap where the coefficients have to be large to handle it. (e.g. if $x=2.0$ then $ 2^5*x^2 = x^7 \rightarrow 32*x^2 = x^7$)

Now to answer why more points will cause less overfitting is sheerly because you have more equations. Your loss is generally some form of average distance accross points and predictions. Given $N$ points I can always find an $N-1$ order polynomial that fits it exactly. Instead of a formal proof I will provide a form in which you can easily generate this polynomial from $N$ $(x_i, y_i)$ pairs
$$ f(x) = \sum_{i=1}^{N}y_i\prod_{j=1\atop j \ != i}^N\frac{(x-x_j)}{(x_i-x_j)}$$

As you can see, for each $x_i$ it will zero out all terms in the sum except one where the product become 1 making $f(x_i) = y_i$ by construction. So adding more points will prevent whatever optimization process you are learning to directly solve each point exactly, but instead try to find an algorithm that best generalizes to each of the points.

Answer 2

Size of the co-efficients will probably increase only upto a certain degree of polynomial. This is due to the fact you are using $sin(2\pi x)$, if you used $sin(4\pi x)$ then the size of co-efficients will increase upto more degrees of polynomial. This can be seen when $sin(x)$ is represented as series:

$$ sin(x) = \frac{x}{1!} - \frac{x^3}{3!} + \frac{x^5}{5!}....$$

In your case $x \rightarrow 2\pi x$ so in order to approximate it the higher order terms must have very high co-efficients which the denominator factorial terms cannot cancel out (only upto a certain point though) and hence for small orders like $N=10$ (assume we have even terms in the series, since we are not dealing with mathematical definiteness, so even terms will cancel out or get cancelled out in some way), $10! = 3628800$ whereas $(2\pi) ^{10} = 95410558$ around 26 times greater. So you see till certain point the co-efficient values must increase for $sin(2\pi x)$. I think this answers both of your questions.

Coming to your second question, in general loosely we can say, the ML algorithm you are using performs Polynomial Regression which means fitting a curve by adjusting parameters, in a way such that the distance between the points generated by your model, for a given input, is as close as possible to the real data.

So the question is why does increasing data points gives better generalisation? What most people do not mention is now that you have a better generalisation of the function itself, by which I mean, if I give you 2 points (least number required as per Nyquist Sampling theorem to define a $sin$ wave of certain frequency) from a $sin$ curve, unless you know beforehand you cannot tell whether it was generated from a $sin$, but if I give you 100 points within the same time period (of a sine wave) you can easily guess the data must be generated from $sin$. Similarly, an ML algorithm cannot guess where the data is generated from when the number of data-points is less and tries to fit a model according to its best guess (minimum loss), but if you give a larger number of points it'll make better guess hence better generalisation.

Think like this, you want to make a circle with rubber band around pins. Can you make it with 4-5 pins? You need at-least certain number of pins to make it look a circle. The rubber band here is your model.