Polynomial and step regression (basis functions)
Linear regression can only draw straight lines. The trick here: invent new input columns (like x², or "is x between 2 and 5?") so the same straight-line machinery draws curves and steps.
Question type: regression.
Week: 2.
Book: ISLP 3.3.2 (non-linear terms), 7.1, 7.2, 7.3.
Techniques on this page: polynomial features, step functions, the general basis-function recipe, choosing how flexible to be.
The problem it solves
Real relationships are often curved. Car fuel efficiency drops fast as horsepower rises, then levels off. A straight line can’t follow that, so it’s wrong in a systematic way (high bias, from the big picture).
We’d like curves, but we don’t want to throw away everything we learned about linear regression. The clever bit: the word “linear” in linear regression refers to the coefficients \(\beta\), not to \(X\). As long as each \(\beta\) just multiplies a column, you can put anything you like in the columns, including \(x^2\), and least squares still works unchanged.
Words you’ll hear
| Word | Plain meaning |
|---|---|
| polynomial | a sum of powers: \(x\), \(x^2\), \(x^3\), … |
| degree | the highest power used. Degree 2 = a curve with one bend, degree 3 = up to two bends |
| feature engineering | making new input columns out of old ones |
| step function, piecewise constant | a flat value in each range, jumping between ranges, like a staircase |
| cut points, knots, \(c_k\) | where the ranges start and end |
| basis functions, \(b_k(x)\) | the general name for “whatever new columns you decided to make” |
| global vs local | global: changing data in one place changes the curve everywhere; local: only nearby |
Technique 1: polynomial features
Problem it solves: a smooth curve.
Add powers of \(X\) as extra columns:
\[Y = \beta_0 + \beta_1X + \beta_2X^2 + \beta_3X^3 + \epsilon\]
Then fit exactly as in linear regression, with the design matrix having columns \(1, x, x^2, x^3\).
Design matrix. Data \(x = (1, 2, 3)\), degree 2. Each row is \((1, x, x^2)\):
\[\mathbf X = \begin{pmatrix}1 & 1 & 1\\ 1 & 2 & 4\\ 1 & 3 & 9\end{pmatrix}\]
For a cubic, the row for \(x = 2\) would be \((1, 2, 4, 8)\).
Is it still linear? Ask: is every \(\beta\) just multiplying a column you can compute in advance?
- \(Y = \beta_0 + \beta_1\log X + \beta_2\sqrt X\): yes, the columns are \(\log x\) and \(\sqrt x\).
- \(Y = \beta_0 + e^{\beta_1 X}\): no, \(\beta_1\) is stuck inside the exponential.
Why not degree 20? High degrees wiggle wildly, especially near the edges of the data, and fit the luck. People rarely go above 3 or 4. Polynomials are also global: a few odd points at one end change the whole curve.
Non-linear example from the slides: in \(Y = \beta_0 + \beta_1X^2\), increasing \(X\) by \(\Delta\) changes \(Y\) by \(2\beta_1X\Delta + \beta_1\Delta^2\), which depends on where \(X\) already is. That’s what “not linear in \(X\)” means.
Technique 2: step functions (piecewise constant regression)
Problem it solves: polynomials are global. Sometimes you want each range of \(X\) to have its own level, unaffected by far-away data (e.g. wage by age group).
Choose cut points \(c_1 < c_2 < \dots < c_K\) and make one yes/no column per range:
\[C_0(X) = \mathbb 1(X < c_1),\quad C_1(X) = \mathbb 1(c_1 \le X < c_2),\ \dots,\ C_K(X) = \mathbb 1(c_K \le X)\]
For any \(x\), exactly one of these is 1. Fit \(Y = \sum_k \beta_k C_k(X)\) with least squares, and each \(\hat\beta_k\) turns out to be the average \(y\) in that range.
\(x = (1, 2, 3, 6, 7, 8)\), \(y = (3, 5, 4, 10, 12, 11)\), one cut at \(c = 5\).
- Range \(x < 5\): average \((3 + 5 + 4)/3 = 4\).
- Range \(x \ge 5\): average \((10 + 12 + 11)/3 = 11\).
The fit is a staircase: 4, then jumps to 11 at \(x = 5\).
With cuts at 2 and 5, the columns for \(x = 3.7\) are \((0, 1, 0)\) and for \(x = 5\) are \((0, 0, 1)\).
These are just dummy variables made from a number instead of a category. Downside: the jumps can be unnatural, and you must pick the cut points.
Technique 3: basis functions (the general recipe)
Problem it solves: gives one name to all of the above, so you can invent your own.
\[Y = \beta_0 + \beta_1b_1(X) + \beta_2b_2(X) + \dots + \beta_Kb_K(X) + \epsilon\]
You pick the functions \(b_k\) before fitting. Compute them for every training row, put them in the columns, run least squares. Examples:
| Basis | \(b_k(x)\) |
|---|---|
| polynomial | \(x^k\) |
| step | \(\mathbb 1(c_k \le x < c_{k+1})\) |
| Fourier (waves) | \(\cos\big((2k+1)\pi x/2\big)\) |
| piecewise polynomial (regression splines, only mentioned) | \(x^r\) inside one range, 0 outside |
Technique 4: deciding how flexible to be
Problem it solves: every extra column makes the model bendier. Too few and you miss the shape (bias); too many and you chase the luck (variance).
More columns also means more coefficients to estimate from the same data. When the number of columns gets close to the number of rows, estimates become unstable. This is exactly the situation ridge regression was invented for.
How to choose the degree or the number of cuts: try several, and pick the one with the lowest error on a validation set (data held back from fitting). Never pick by training error; the bendiest option always wins there.
What to read in the book
| Section | Read? | Why |
|---|---|---|
3.3.2 “Non-linear relationships” (the Auto horsepower example) |
Read | The slides’ motivation |
| 7.1 Polynomial regression | Read | Skip the bits about standard errors and confidence bands |
| 7.2 Step functions | Read | This is the “piecewise constant” part of the slides, even though 7.2 isn’t in the slide header |
| 7.3 Basis functions | Read | One page |
| 7.4 to 7.7 (splines, smoothing splines, local regression, GAMs) | Skip | Only mentioned in one line on the slides |
Practice prompt
I'm studying CS5100 Data Analysis (textbook ISLP, sections 3.3.2, 7.1-7.3). I want practice questions on POLYNOMIAL REGRESSION, STEP FUNCTIONS and BASIS FUNCTIONS:
- writing design-matrix rows for polynomial models of different degrees
- deciding whether a given model is "linear in the coefficients" and can be fitted with least squares
- computing step-function (piecewise constant) fits by hand: indicator columns for given cut points, and the fitted value = mean of y in each bin
- explaining why "linear" refers to the betas, not to x
- the trade-off of higher degree / more cut points: flexibility, bias vs variance, overfitting, behaviour at the edges
- choosing degree or number of cuts with a validation set
- interpreting how a change in x changes y when x^2 is in the model
Please:
1. Use plain, everyday language and explain any technical term in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with small numbers I can do by hand.
3. Wait for my answer, then mark it and show the full working step by step.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.