Lecture 28 · Regression

Linear Regression: Error, Overfitting and Structure

To learn a prediction rule we need a way to score candidates: the squared error. But if every possible function is allowed, you can get zero error just by memorising the training data, which is useless on new data. The fix is to search only structured functions. The simplest choice, linear functions, gives linear regression.

Source: this lecture on YouTube (≈18 min). Previous: L27 · Next: L29.

1 · The goal

Training data: $x_1,\dots,x_n\in\mathbb R^d$ with real labels $y_1,\dots,y_n$. We want a function $h:\mathbb R^d\to\mathbb R$ that predicts the label of new points well. There are endless such functions, so we need to be able to say how good a given $h$ is on our data.

2 · Scoring a function: the squared error

$$\text{error}(h)=\sum_{i=1}^{n}\big(h(x_i)-y_i\big)^2$$

For each point, compare the prediction $h(x_i)$ with the true $y_i$, square the difference, and add up.
Why square it? The error must never be negative. If we used the plain difference $h(x_i)-y_i$, a function that always predicts $-\infty$ would "win". Other non-negative errors are possible; squared error is the natural starting point, and later lectures justify it.
The smallest possible value is 0, a sum of squares, reached only when $h(x_i)=y_i$ for every training point.

3 · The trap: zero error by memorising

If any function is allowed, getting 0 error is trivial: just make $h$ return $y_i$ whenever it sees $x_i$. That's a lookup table. It's perfect on the training data and tells you nothing reliable about new points.

This is overfitting: matching the training data, noise included, at the cost of doing well on new (test) data. We never care about training error for its own sake. A rainfall predictor that's perfect on the last three years but wrong from tomorrow onwards is useless.

–

training error (avg squared)

–

test error on new points

training pointsnew test points

4 · The fix: restrict the search to structured functions

The squared error isn't the culprit. The problem is searching all functions. Assume the true input–output relationship has some structure and search only functions with that structure. The simplest is linear:

$$\mathcal H_{\text{linear}}=\big\{\,h_w(x)=w^{\top}x\;:\;w\in\mathbb R^d\,\big\}$$

(A shifted version, $w^\top x+b$, works the same way. The lecture drops $b$ to keep things simple.) The weights $w$ say how much each feature matters, and the prediction is a weighted combination of the features.

Linear regression: $$\min_{w\in\mathbb R^d}\;\sum_{i=1}^{n}\big(w^{\top}x_i-y_i\big)^2$$

5 · What zero error means now

This error can still reach 0, but now that's not overfitting. It would mean $w^\top x_i=y_i$ exactly for every point: the labels follow the assumed linear structure with no noise at all. Overfitting happens when the search space is much bigger than the true structure, so the fit starts chasing the noise. Here, the "noise" is whatever the linear structure can't explain. A probabilistic view of noise comes in a later lecture.

Key takeaways

Score a predictor with the squared error $\sum_i(h(x_i)-y_i)^2$.
Allowing all functions leads to memorising: zero training error, bad on new data. That's overfitting.
Restrict the search to structured functions. The linear class $w^\top x$ gives linear regression.
Zero error with a linear model means noise-free data, not overfitting.