Feature engineering & overfitting

How to make a straight-line model fit a curve without changing the model at all — and the exact price you pay for overdoing it.

1. The premise: simple models, complex data

Note what it does not say: "use a more complex model." It says keep the simple model and change the data. That is the whole chapter.

The simple model, from chapter 8, for a one-dimensional input $x \in \R$:

$w$ is the slope, $b$ the intercept or bias; you fit it by minimising squared error, in closed form via the normal equations. Interpretable, easy to optimise, two parameters. Now watch it fail.

1.1 When linear regression works

On a dataset $\D = \{(x^{(i)}, y^{(i)})\}_{i=1}^{N}$ that follows a linear trend, a linear model fits beautifully.

1.2 When linear regression fails

Now take non-linear data: the five samples of Table 1 (§3), which the notes use too, so every number on this page lines up. Sorted, $x = 0, 2, 3, 6, 7$ with $y = 15, 5, 1, 5, 12$ — falls, bottoms out, rises. A parabola.

The line captures essentially nothing, and its slope is negative, so reading the coefficient as chapter 8 taught you — "$y$ decreases as $x$ increases" — gives the wrong conclusion about half the data.

2. The trick: linear in the parameters, not in the input

The data "strongly resembles a quadratic curve," as the notes put it. Suppose we could learn optimal parameters $[b, w_1, w_2]^\top$ for

But how? We only know how to fit lines. The answer is the most important sentence on this page:

2.1 Why "linear in the parameters" is the property that matters

Take that apart, because linear regression is an optimisation problem:

$\theta \in \R^M$ is the parameter vector, $z^{(i)} \in \R^M$ whatever numbers we put in row $i$, $N$ the number of samples, $M$ the entries per row, and $\theta^\top z^{(i)} = \sum_{j} \theta_j z^{(i)}_j$ the prediction.

What makes this solvable in closed form? Two facts, and only two:

1. The prediction $\theta^\top z^{(i)}$ is a linear function of $\theta$.
2. The loss is the square of (target − prediction), so the objective is a quadratic in $\theta$, hence convex, hence its gradient is linear in $\theta$, hence setting the gradient to zero gives a linear system you can solve.

Note what is absent: any requirement on $z^{(i)}$. Its entries are constants to the optimiser, computed before it ran. The algebra is identical whether $z^{(i)} = [1, x^{(i)}]^\top$, $[1, x^{(i)}, (x^{(i)})^2]^\top$, or $[1, \sin(x^{(i)}), e^{x^{(i)}}, \log(1 + (x^{(i)})^2)]^\top$.

3. Building $\D'$ by hand

Given the non-linear dataset $\D$, we construct (or engineer) new features to create a dataset $\D'$ that can express the more complex distribution. Concretely: add one column, $x^2$.

Table 1 — Original dataset $\D$ (left) and feature-engineered dataset $\D'$ (right). The new column is just $6^2=36$, $7^2=49$, $3^2=9$, $2^2=4$, $0^2=0$. No model and no optimiser was touched; we typed a column of numbers.

Train a linear regression model on $\D'$: two features ($z_1 = x$, $z_2 = x^2$) plus a bias, three parameters, and the hypothesis is exactly the quadratic we wanted:

The normal equations on these five rows give

3.1 The warning: the same transformation at prediction time

The transformation is part of the model now. The model's inputs are samples of the original $\D$, so to predict on a new $x \in \R$ you must first engineer $x^2$, and only then feed $[1, x, x^2]$ in.

4. Another perspective: you are fitting a plane, not a curve

$\D$ had one feature; the model was trained on the two of $\D'$. Two inputs plus one output still fits in a drawing, in three dimensions — and with two features the model is not fitting a line. It is fitting a plane.

5. Generalising: polynomial feature transforms

To model a quadratic we engineered $x^2$. For a cubic,

engineer $x^3$ as well; for a quartic, $x^4$ too. In general, for a degree-$M$ polynomial on a one-feature $\D$, add the columns below, plus a column of ones for the bias $b$ — from here on the bias is just the weight on a feature that is always 1.

Table 2 — Original dataset $\D$ (the $y, x$ columns) and feature-engineered dataset $\D'$ (all of it).

Two counts to remember. A degree-$M$ transform on a one-dimensional input costs $M+1$ parameters; on $K$ features, taking all monomials up to degree $M$ costs $\binom{K+M}{M}$, which explodes — degree 3 on 100 features is 176,851 columns.

6. Abstract feature transforms: $\phi$ and $\Phi$

Raising to a power is only a special case: any function you desire will do.

• Periodic: $\sin(x)$, paired with $\cos(x)$ so a phase shift is a linear combination. For cycles — hour of day, day of year.
• Radial: the distance $\lVert x\rVert_2 = \sqrt{x_1^2 + \dots + x_K^2}$. This alone lets a linear model carve out a circle in the original space, since "$\lVert x\rVert_2 \le r$" is linear in the new coordinate.
• Logs: $\log(1+x)$ compresses heavy tails (income, view counts) so a handful of giants stop dominating the squared loss.
• Interactions: $x_1x_2$. Without it the effect of $x_1$ must be the same whatever $x_2$ is; with it the model can say "fertiliser helps, but only if there is water."
• Indicators / one-hot: for colour ∈ {red, green, blue}, three binary columns $\1[\text{red}], \1[\text{green}], \1[\text{blue}]$ — how a model that only does arithmetic handles a variable with none.
• Buckets: $\1[x < 0],\ \1[0 \le x < 5],\ \1[x \ge 5]$ turns a continuous feature into a step function fitted at whatever heights the model likes.

The only rule: apply the same transformation to every sample, at training time and at prediction time (§3.1).

6.1 The notation

Given a dataset $X \in \R^{N\times K}$ — $N$ samples, $K$ features each — define a feature transformation function

where $M$ is the number of features $\phi$ produces. The transformed dataset $\Phi$ is stacked row by row:

(often just renamed $X$)

Each $x^{(i)} \in \R^K$ is a column vector, so ${x^{(i)}}^\top$ is a row — row $i$ of the matrix (the long dashes mean "this row is that whole vector laid flat"). Applying $\phi$ turns a $K$-vector into an $M$-vector, so row $i$ of $\Phi$ has $M$ entries and $\Phi \in \R^{N \times M}$. $\phi$ itself you may define to be anything at all.

7. The normal equations carry over — and where they break

Nothing about the optimisation changed, so everything from chapter 8 transfers with $X$ replaced by $\Phi$:

and setting $\nabla_\theta J = 0$ gives, exactly as before,

7.1 What happens when $M > N$

Chapter 8's corner case — "what if $X^\top X$ isn't invertible?" — is the common case here. $\Phi^\top\Phi$ is $M \times M$ with rank $\operatorname{rank}(\Phi) \le \min(N, M)$:

• If $M > N$, then $\operatorname{rank}(\Phi^\top\Phi) \le N < M$, and an $M\times M$ matrix of rank less than $M$ is singular. The inverse does not exist and the boxed formula is meaningless as written.
• Geometrically: you have $M$ unknowns and only $N$ independent equations. The solution set is an affine subspace of dimension at least $M - N$ — infinitely many parameter vectors that all achieve exactly zero training error.
• Each one interpolates the training data perfectly and they disagree wildly everywhere else. Nothing in the least-squares objective prefers one over another.

$M = N$ is already trouble: with $N$ distinct $x$ values and a degree-$(N-1)$ polynomial the Vandermonde matrix is square and invertible, so the unique fit passes through every point and training error is zero — a disaster, as §8 shows. Just below that threshold $\Phi^\top\Phi$ is invertible but ill-conditioned, so $\theta$ comes out with enormous entries of alternating sign that nearly cancel: the violent wiggles you are about to see.

8. "Why not just have more and more features?"

If more features reach a larger family of functions, why not add as many as possible? Take genuinely linear data — degree 1 is the honest answer — and fit transforms of increasing degree $k$.

9. Interactive: watch overfitting happen

Ten training points (orange) from a smooth true function plus noise; forty held-out test points (grey) the model never sees. The slider sets the degree $M$, and the fit is recomputed from the normal equations on every move.

10. Overfitting, properly

The notes stop at "this is overfitting; more to come later." Here is the later part. extends the reading

10.1 The two error curves

10.2 Saying it with risk and empirical risk

The precise version is overfitting in the language of chapter 5. The true risk (expected loss) of a hypothesis $h$ is an expectation over the data-generating distribution $p(x, y)$:

That is what you care about, and you cannot compute it: you do not have $p$. So you compute the empirical risk on your $N$ samples instead:

and minimise that: empirical risk minimisation. The whole enterprise rests on $\hat R$ being a good stand-in for $R$.

Which is why a held-out test set works: those points did not choose $h$, so on them $\hat R$ is unbiased again.

10.3 Underfitting, the mirror failure

Figure 2 was underfitting: a model too rigid to express the truth, with high error on training and test data. Look at both numbers and the two failures are never confused.

10.4 Bias and variance, in words

10.5 The fixes the notes promise are coming

The notes promise "more to come on how to combat overfitting." Four fixes, all of them chapter 12:

• Held-out validation set — split train / validation / test; pick the degree by validation error, report on test. Costs data.
• $k$-fold cross-validation — $k$ fits, each validating on a different fold, averaged. Costs $k\times$ the compute, buys a much less noisy estimate.
• Regularisation — keep the features, charge for large weights: minimise $\lVert y - \Phi\theta\rVert^2 + \lambda\lVert\theta\rVert^2$, giving $\theta^* = (\Phi^\top\Phi + \lambda I)^{-1}\Phi^\top y$, which also fixes the invertibility problem of §7.1.
• More data — overfitting is a ratio of capacity to data, so doubling $N$ moves the interpolation threshold $M+1 = N$ right and the U-curve's minimum to a higher complexity.

11. The same story, in a different chapter

Overfitting happens to any model with enough capacity to memorise. A decision tree with no depth limit splits until every leaf is pure, and with distinct feature vectors it always can — in the limit, one leaf per sample. Training error zero; test error bad, because a leaf built from one sample knows only that sample's label. Line the two up:

12. Common mistakes, collected

13. Recap

Every statement is in the Essentials box at the top. Four things are worth repeating:

• The fix for complex data is applied to the data, not the model — and "linear" means linear in the parameters.
• The shipped model is the pair $(\phi, \theta)$. Lose $\phi$ and $\theta$ is meaningless numbers.
• The curve you plot is a flat plane's height read along the constraint curve the features obey. Off that curve there is no support at all.
• Training error is monotone in capacity, so it can only ever tell you to add more. Measure on data you did not fit on.