Polynomials, steps and flexibility
Bend a straight line by inventing new columns: $X^2$, $X^3$, or "is $X$ in this range?". The model stays linear in its parameters, so least squares still works, and the number of columns becomes your flexibility knob.
This is the heart of 2024 Q1: a polynomial model written as \(f(X) = \lambda \cdot \phi(X)\) with \(\lambda \in \mathbb R^d\), the point that it is “non-linear in \(X\) but linear in \(\lambda\)”, and a discussion of how the dimension \(d\) (the degrees of freedom) controls flexibility and overfitting.
Book: what to read for this stage
ISLP 7.1 polynomial regression, 7.2 step functions and 7.3 basis functions: read (they are short). 7.4 to 7.7 (splines, smoothing splines, local regression, GAMs): skip, the slides only mention regression splines in one line. 3.3.2’s “non-linear relationships” paragraph (horsepower squared) is the same idea.
1. Polynomial regression
Replace \(X\) by the new columns \(X, X^2, \dots, X^d\):
\[Y = \beta_0 + \beta_1X + \beta_2X^2 + \dots + \beta_dX^d + \epsilon.\]
The fitted curve is non-linear in \(X\), but the model is linear in the parameters \(\beta\): each \(\beta_j\) just multiplies a known column. So you build the design matrix with the powers precomputed and use the same least-squares formula, \(\hat\beta = (\mathbf X^T\mathbf X)^{-1}\mathbf X^T\mathbf y\).
Design-matrix rows for degree 2 and \(x = 1, 2, 3\): \((1, 1, 1)\), \((1, 2, 4)\), \((1, 3, 9)\). With two inputs you can include \(X_1, X_2, X_1X_2, X_1^2, X_2^2\).
Degree is rarely above 3 or 4. High degrees are wildly flexible and swing about near the edges of the data, and polynomials are global: moving data in one region changes the curve everywhere.
Which of these models can be fitted by ordinary least squares?
Only the first is linear in the parameters: \(\log X\) and \(\sqrt X\) are just new columns. In the others a parameter sits inside a non-linear function.
2. Step functions
Polynomials impose one global shape. Step functions cut the range of \(X\) at points \(c_1 < c_2 < \dots < c_K\) and fit a constant in each bin. The new columns are indicators:
\[C_0(X) = \mathbb 1(X < c_1),\quad C_k(X) = \mathbb 1(c_k \le X < c_{k+1}),\quad C_K(X) = \mathbb 1(X \ge c_K).\]
Exactly one is 1 for any \(X\). Fitting \(Y = \sum_k\beta_kC_k(X) + \epsilon\) by least squares gives \(\hat\beta_k\) = the mean of \(y\) in bin \(k\).
Worked example. \(x = (1, 2, 3, 6, 7, 8)\), \(y = (3, 5, 4, 10, 12, 11)\), one cut at \(c = 5\). Bin \(X < 5\) has mean \((3 + 5 + 4)/3 = 4\); bin \(X \ge 5\) has mean \(11\). The fit is a step from 4 to 11 at \(x = 5\). With cuts at 2 and 5, the indicator row for \(x = 3.7\) is \((0, 1, 0)\) and for \(x = 5\) it is \((0, 0, 1)\).
Step regression with one cut at \(c = 4\) on \(x = (1, 2, 3, 5, 6)\), \(y = (2, 4, 3, 7, 9)\). What does the fit predict at \(x = 5.5\)?
\(x = 5.5\) is in the bin \(X \ge 4\), whose points have \(y = 7, 9\), mean 8.
3. Basis functions: the general recipe
Polynomials and steps are special cases of
\[Y = \beta_0 + \sum_{k=1}^{K}\beta_k\,b_k(X) + \epsilon,\]
where the basis functions \(b_k\) are fixed and chosen before fitting: powers \(x^k\), indicators, Fourier terms \(\cos\big((2k + 1)\pi x/2\big)\), or pieces of polynomials between knots (regression splines). Compute every \(b_k(x_i)\), put them in \(\mathbf X\), run least squares. In the exam’s notation: \(f(X) = \lambda \cdot \phi(X)\) with the feature vector \(\phi(X) = (1, b_1(X), \dots, b_K(X))\) and \(\lambda \in \mathbb R^{K + 1}\).
(Week 4’s neural networks do the same thing, except that they learn their basis functions from the data instead of having you choose them.)
4. Degrees of freedom and flexibility (2024 Q1)
The number of parameters \(d\) (the length of \(\lambda\), the model’s degrees of freedom) is the flexibility knob:
- Larger \(d\) (higher degree, more knots or bins): a more flexible curve. Training RSS can only go down. Lower bias, higher variance.
- \(d\) close to \(n\): each parameter is estimated from very few points, so \(\hat\lambda\) varies wildly between samples (recall \(\mathrm{var}(\hat\beta) = \sigma^2(\mathbf X^T\mathbf X)^{-1}\)). At \(d = n\) the curve passes through every point: training RSS 0, terrible test error.
- \(d > n\): no unique solution at all.
- Too small \(d\): underfitting (a line through a curve).
Choose \(d\) by validation error (U-shaped in \(d\)), or keep \(d\) large and shrink the parameters with a penalty (stage 8’s ridge, where a large penalty makes the model less flexible). Notice the clash of letters: in 2024 the parameters were called \(\lambda\); in ridge regression \(\lambda\) is the penalty. Read each question’s definitions.
Worked example: a full-marks discussion. “Discuss the relationship between the degrees of freedom, the dimension \(d\) of \(\lambda\) and the model’s flexibility.”
“The degrees of freedom are the number of free parameters, here \(d\), the dimension of \(\lambda\). Increasing \(d\) (for example raising the polynomial degree) adds basis functions, so the model can represent more complicated curves: it becomes more flexible, its bias falls and its training RSS decreases. But each extra parameter must be estimated from the same \(N\) points, so the variance of \(\hat\lambda\) grows; when \(d\) approaches \(N\) the model can interpolate the training data, fitting the noise (overfitting), and the test error rises. For \(d > N\) the least-squares solution is not unique. So \(d\) should be chosen on a validation set, or the parameters should be regularised.”
You raise a polynomial’s degree from 2 to 8 with 30 data points. Tick everything that is true.
The degree-2 model is nested in the degree-8 one, so least squares can’t do worse on the training data. The test error may go either way (U-shape). It stays linear in the parameters.
Stage test
(5 marks, exam format 3; 2024 Q1.) A polynomial regression model is written \(f(X) = \lambda \cdot \phi(X)\) with \(\lambda \in \mathbb R^d\). Explain why it is “non-linear in \(X\) but linear in \(\lambda\)”, and discuss how \(d\) relates to the model’s flexibility and to overfitting.
The feature map \(\phi(X) = (1, X, X^2, \dots, X^{d - 1})\) is a fixed, non-linear function of the input, so \(f(X) = \lambda\cdot\phi(X)\) draws a curve in \(X\). But \(f\) is a weighted sum of these known features with weights \(\lambda\), so it is linear in the parameters: the RSS is still a quadratic bowl in \(\lambda\) and least squares applies with the rows \(\phi(X_n)\) in the design matrix. The dimension \(d\) is the number of free parameters (the degrees of freedom). Increasing \(d\) makes the model more flexible: it can follow more complicated shapes, so the bias and the training RSS go down. At the same time the variance increases, because more parameters are estimated from the same \(N\) points; as \(d\) approaches \(N\) the curve can pass through every training point and fits the noise, so the test error goes up (overfitting), and for \(d > N\) there is no unique solution. \(d\) should therefore be chosen by validation error, or the parameters shrunk with a penalty.
What is the design-matrix row for \(x = 2\) in a cubic polynomial model?
Intercept column, then \(x, x^2, x^3\).
Step regression with cuts at 2 and 5 on \(x = (1, 1.5, 3, 4, 6, 7)\), \(y = (2, 4, 9, 11, 20, 22)\). What does the fit predict at \(x = 3.5\)?
\(x = 3.5\) is in the bin \([2, 5)\), which holds \(y = 9, 11\): mean 10. So the prediction is 10. (If you answered 11 you took a single point instead of the bin mean.)
A residual plot for a linear fit shows a clear U-shape. What should you try?
A U-shape means the straight line systematically misses a curve.
Why are polynomials called “global” and step functions “local”?
That’s the motivation for steps and splines in ISLP 7.2.