Home / MLT / Week 5

Week 5 · Regression: least squares and its Bayesian view

Official syllabus line: Supervised Learning - Regression - Least Squares; Bayesian view

About 80 minQuiz 2 material (see exam radar)BSCS2007 · Arun Rajkumar

Before you start: MLF week 3 (least squares), MLF week 7 (gradient descent), MLT week 4 (MLE and the Bayesian view).

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine you're trying to guess the price of a house. You look at its size, how many rooms it has, and compare it to other houses you know. This is like 'supervised learning' where you learn from examples with correct answers. We want to find a simple rule, like a line, to make good guesses.
We find this 'best line' by making the total 'mistake' as small as possible. Imagine the line is like a target, and each data point is an arrow. We measure how far each arrow misses the target. We then square these misses and add them up. The line that gives the smallest total squared miss is our best guess!
Let's try! If we have points like (zero, one), (one, two), and (two, two), our best line might be 'y equals seven-sixths plus one-half x'. To predict for a new input, say 'x equals three', we just plug it into our line's rule. The line helps us make educated guesses for new data!
Remember, we use a 'line' to predict numbers, finding it by making total squared errors smallest. This is linked to 'Gaussian noise' for exams! Always test your line on new, unseen data to see how well it truly performs, not just on the data it learned from. Keep practicing, you've got this!

The one-minute story

Think of it like this

Supervised learning means learning with a teacher: every example comes with the right answer. This week the answer is a number (a house price, a temperature, tomorrow's sales). That is regression.

You have met the idea before: draw the best straight line through a cloud of dots. We now look at it three ways:

as geometry (a shadow, from MLF week 3),
as calculus (make the total squared mistake as small as possible),
as probability (assume the data is the line plus random noise, and find the most likely line).

All three give the same line. The probability view is new, and it opens a door: once you can say what kind of noise you expect, you can also say what kind of line you believe in beforehand, which is the Bayesian view and leads straight to next week's ridge regression.

By the end of this week you can:

write linear regression with a design matrix and solve the normal equations;
explain least squares as projection, as gradient descent, and as MLE under Gaussian noise;
use basis functions (polynomial regression) to fit curves with a linear model;
measure quality with MSE and validate with a held-out set or leave-one-out cross-validation.

Words you need

Regression - predicting a real number.
Feature vector $\mathbf x_i$ and target $y_i$ - the inputs and the right answer for example $i$ .
Weights $\mathbf w$ - the numbers the model learns. Prediction: $\hat y=\mathbf w^T\mathbf x$ .
Design matrix $X$ - one row per example here ( $n\times d$ ), so $X\mathbf w$ is the vector of all predictions.
Residual - $y_i-\hat y_i$ , the mistake on one example.
Training / validation error - error on the data used for fitting / on held-back data.
Basis function - a fixed transformation of the input (like $x^2$ ) that we feed to a linear model.

Idea 1: Linear regression

Model: $\hat y=\mathbf w^T\mathbf x$ (add a constant 1 to $\mathbf x$ to get an intercept). For all $n$ examples at once, with the design matrix $X$ whose rows are the $\mathbf x_i^T$ :

\hat{\mathbf y}=X\mathbf w

Loss. The sum of squared errors:

\mathcal L(\mathbf w)=\sum_{i=1}^n(y_i-\mathbf w^T\mathbf x_i)^2=\|\mathbf y-X\mathbf w\|^2

Solving it (calculus). The gradient is $-2X^T(\mathbf y-X\mathbf w)$ . Setting it to zero:

\boxed{X^TX\,\mathbf w=X^T\mathbf y}\qquad\Longrightarrow\qquad\mathbf w^*=(X^TX)^{-1}X^T\mathbf y

These are the normal equations. Geometrically: $X\mathbf w^*$ is the projection of $\mathbf y$ onto the column space of $X$ , and the residual $\mathbf y-X\mathbf w^*$ is perpendicular to every column of $X$ (MLF week 3). By iteration: you can also reach $\mathbf w^*$ by gradient descent, $\mathbf w\leftarrow\mathbf w+2\eta X^T(\mathbf y-X\mathbf w)$ (MLF week 7). With millions of examples that is how it is done.

If the columns of $X$ are linearly dependent, $X^TX$ is not invertible and the best $\mathbf w$ is not unique. That is exactly the situation ridge regression fixes next week.

Solved example: 1. Predicting with a fitted line

Question. The data are $(x,y)=(0,1),\,(1,2),\,(2,2)$ . We found in MLF week 3 that the best line is $\hat y=\frac76+\frac12x$ . Predict $y$ at $x=3$ and compute the training MSE.

Solution. $\hat y(3)=\frac76+\frac32=\frac{16}6=\frac83\approx2.67$ . Fitted values at $0,1,2$ : $1.17,\,1.67,\,2.17$ . Residuals: $-0.17,\,0.33,\,-0.17$ . Sum of squares $=\frac16\approx0.167$ , so MSE $=\frac{1/6}{3}\approx0.056$ .

Idea 2: The probabilistic view

Suppose the world works like this:

y_i=\mathbf w^T\mathbf x_i+\varepsilon_i,\qquad\varepsilon_i\sim\mathcal N(0,\sigma^2)\ \text{independently}

i.e. a true line plus bell-shaped noise. Then $y_i\mid\mathbf x_i\sim\mathcal N(\mathbf w^T\mathbf x_i,\sigma^2)$ , and the log-likelihood of the data is

\ell(\mathbf w)=-\frac1{2\sigma^2}\sum_i(y_i-\mathbf w^T\mathbf x_i)^2+\text{constant}

Maximising $\ell$ means minimising the sum of squared errors. So:

The idea

Least squares $=$ maximum likelihood estimation under Gaussian noise.

This is why squared error is the "natural" loss for regression: it is what you get when the noise is bell-shaped.

The Bayesian view (a preview of ridge)

Now put a prior on the weights too: $\mathbf w\sim\mathcal N(\mathbf 0,\tau^2I)$ , "I expect the weights to be small". Then (week 4's recipe: posterior $\propto$ likelihood $\times$ prior) the MAP estimate minimises

\sum_i(y_i-\mathbf w^T\mathbf x_i)^2+\lambda\|\mathbf w\|^2,\qquad\lambda=\frac{\sigma^2}{\tau^2}

That is ridge regression, which we study next week. Least squares is the special case with an infinitely wide (uninformative) prior.

Idea 3: Curves from lines, using basis functions

"Linear" means linear in the weights, not in $x$ . To fit a curve, replace $x$ with features such as $\phi(x)=(1,\,x,\,x^2,\,\dots,\,x^p)$ . The model $\hat y=w_0+w_1x+\dots+w_px^p$ is still linear in $\mathbf w$ , so all the machinery above applies with the new design matrix.

Underfitting: $p$ too small, the curve is too stiff to follow the pattern (high bias).
Overfitting: $p$ too large, the curve wiggles through every noisy dot and fails on new data (high variance). With $p=n-1$ the polynomial passes through all $n$ points exactly and training error is $0$ , yet predictions can be wild.

Think of it like this

Fitting a curve through every dot is like a student who memorises the answers to last year's paper, including its printing mistakes. The score on that paper is perfect; on the new paper it is a disaster. We want the student who understood the pattern.

Idea 4: Checking quality honestly

MSE $=\frac1n\sum(y_i-\hat y_i)^2$ . $R^2$ $=1-\frac{\sum(y_i-\hat y_i)^2}{\sum(y_i-\bar y)^2}$ : the fraction of the variation explained (1 is perfect, 0 is as good as predicting the mean).

Training error always shrinks as the model gets more flexible. So judge on data the model has not seen:

Hold-out / validation set: keep a slice aside.
Leave-one-out cross-validation (LOOCV): for each example $i$ , train on the other $n-1$ , predict example $i$ , record the squared error; average over all $n$ . Accurate but costly (it needs $n$ fits).
$k$ -fold CV: split into $k$ parts, each used once as validation.

Solved example: 2. LOOCV by hand

Question. A very simple model predicts the mean of the training targets. The targets are $y=1,\,2,\,6$ . Compute the LOOCV error.

Solution. Leave out each in turn:

left out	train on	prediction (mean)	squared error
1	2, 6	4	$(1-4)^2=9$
2	1, 6	3.5	$(2-3.5)^2=2.25$
6	1, 2	1.5	$(6-1.5)^2=20.25$

LOOCV error $=\frac{9+2.25+20.25}3=\frac{31.5}{3}=\mathbf{10.5}$ .

Idea 5: Kernel regression, briefly

Just as in kernel PCA, a linear regression only needs dot products between inputs, so we can swap them for a kernel $k(\mathbf x,\mathbf x')$ and fit curvy functions without ever building the features. The prediction takes the form $\hat y(\mathbf x)=\sum_i\alpha_ik(\mathbf x_i,\mathbf x)$ , a weighted sum of "similarity to training point $i$ ".

Your turn

Your turn: 1. Normal equations

Fit a no-intercept line $y=wx$ to $(1,2),\,(2,3),\,(3,5)$ .

Need a hint?

$X$ is the column $(1,2,3)^T$ .

Show the full solution

$X^TX=1+4+9=14$ , $X^T\mathbf y=2+6+15=23$ . $w=\frac{23}{14}\approx1.643$ .

Your turn: 2. Predict and measure

Using $w=\frac{23}{14}$ from the previous problem, give the three fitted values and the sum of squared errors.

Need a hint?

$\hat y_i=wx_i$ .

Show the full solution

$1.643,\,3.286,\,4.929$ . Errors: $0.357,\,-0.286,\,0.071$ . Squares: $0.1276,\,0.0816,\,0.0051$ . Sum $\approx0.214$ . (Check the normal equation: $\sum x_ie_i=0.357-0.571+0.214=0$ ✓.)

Your turn: 3. LOOCV

Targets $2,\,4,\,9$ and the "predict the mean of the others" model. Find the LOOCV error.

Need a hint?

Leave each out; use the mean of the other two.

Show the full solution

Predictions $6.5,\,5.5,\,3$ . Errors $^2$ : $20.25,\,2.25,\,36$ . Mean $=\frac{58.5}3=\mathbf{19.5}$ .

Your turn: 4. Which is true?

(a) Training error never increases when you add polynomial features. (b) A degree-9 polynomial through 10 noisy points has zero training error. (c) Least squares is MLE under uniform noise. (d) The residual vector is perpendicular to the columns of $X$ .

Need a hint?

Think about flexibility and the normal equations.

Show the full solution

(a) True (the old model is a special case). (b) True, 10 points determine a degree-9 polynomial. (c) False, Gaussian noise. (d) True.

Your turn: 5. Noise assumption

Under which noise assumption does minimising $\sum|y_i-\hat y_i|$ (absolute error) become MLE?

Need a hint?

The Gaussian gave squared error.

Show the full solution

Laplace noise ( $p(\varepsilon)\propto e^{-|\varepsilon|/b}$ ): its log-likelihood is $-\frac1b\sum|\varepsilon_i|$ . So absolute error corresponds to Laplace noise (and gives a median-like fit).

Exam radar

In MLT Quiz 2 (which covers weeks 5 to 8) the summaries mention linear regression in 10 papers, kernel regression in 8, ridge in 7, gradient descent in 6, update rule in 6, LOOCV in 4, model evaluation in 6, projection in linear regression and linear regression and MSE in a few. In the End Term, linear regression appears in 19 papers and ridge regression in 20.

Typical: "which of the following is the solution of the normal equation?", MSE for a small data set, gradient-descent update for regression, "LOOCV error for this tiny data set", and "least squares equals MLE under what noise?".

Watch out - real exam trap

Normal equations: $X^TX\mathbf w=X^T\mathbf y$ (not $XX^T$ ). The shape of $X$ matters ( $n\times d$ rows are examples).
Training error is not a good measure of quality; validation error is.
Squared-error corresponds to Gaussian noise.
A lower training MSE does not mean a better model if it overfits.
Don't forget the intercept column of ones.

Quick quiz

The least-squares weights w satisfy...

X w = 0
X transpose X w = X transpose y
w = y
X transpose w = X y

The normal equations come from setting the gradient of the squared error to zero.

Least squares is the maximum likelihood estimate when the noise is...

uniform
Gaussian
exponential
Poisson

Gaussian noise gives a log-likelihood proportional to the negative sum of squared errors.

A polynomial of degree n-1 fitted to n distinct points has training error...

always large
zero
equal to the variance
negative

It can pass exactly through all n points, so the training error is zero (and it usually overfits).

Select all TRUE statements. (select all that apply)

The residual is perpendicular to the columns of X at the optimum.
Polynomial regression is still linear in the weights.
LOOCV needs only one fit.
The best w is always unique.

LOOCV needs n fits, and w is not unique if the columns of X are dependent.

Recap

Remember this

Loss $\|\mathbf y-X\mathbf w\|^2$ ; normal equations $X^TX\mathbf w=X^T\mathbf y$ ; geometric meaning: projection.
Gaussian noise $\Rightarrow$ MLE $=$ least squares; Gaussian prior on $\mathbf w$ $\Rightarrow$ MAP $=$ ridge.
Basis functions give curves; too flexible $\Rightarrow$ overfit. Judge with validation / LOOCV / $k$ -fold.
Kernel regression replaces dot products by kernels.

Formulas to keep

$\hat{\mathbf y}=X\mathbf w$ ; $\mathcal L=\|\mathbf y-X\mathbf w\|^2$ ; $\nabla\mathcal L=-2X^T(\mathbf y-X\mathbf w)$
$\mathbf w^*=(X^TX)^{-1}X^T\mathbf y$ ; gradient step $\mathbf w\leftarrow\mathbf w+2\eta X^T(\mathbf y-X\mathbf w)$
MSE $=\frac1n\sum(y_i-\hat y_i)^2$ ; $R^2=1-\frac{SS_{res}}{SS_{tot}}$
LOOCV $=\frac1n\sum_i(y_i-\hat y^{(-i)}_i)^2$

Connected weeks (learn them together)

MLF week 3 - Vectors, matrices and the best-fit line: Least-squares regression is the same problem as MLF week 3's best-fit line.
MLF week 12 - Estimating parameters, and EM: MLE and MAP give the probabilistic view of least squares and ridge.
MLP week 3 - Linear regression and gradient descent in sklearn: Linear regression: the theory, then the code.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 50 real questions on this week All Quiz 2 papers