Machine Learning
Topic 7 · ML foundations · ⏱ about 4 h

Linear Regression

The simplest predictive model — and the foundation for many others.

Show:
In this topic
Beginner

The model

Linear regression is the simplest predictive model, and it is worth understanding thoroughly because so many other methods build on it. It predicts a number by giving each feature a weight, multiplying, and adding the results, plus a constant:

ŷ = wx + bresidual y − ŷ
Least squares chooses the line that makes the sum of squared residuals (red) as small as possible.
y^=w1x1+w2x2+⋯+wdxd+b=w⊤x+b. \hat y = w_1x_1 + w_2x_2 + \dots + w_dx_d + b = w^\top x + b.

Each weight has a direct interpretation. The weight wjw_j says how much the prediction changes when feature xjx_j increases by one unit while all the other features stay the same. For a house-price model, a weight of 0.5 on "floor area in square metres" would mean that each extra square metre adds about $500 to the predicted price, other things being equal. The constant bb is called the intercept or bias; it is the prediction when every feature equals zero, and it lets the line sit at the right height.

To decide which weights are best, we need a way to measure how wrong a set of weights is. For each training example, the residual yi−y^iy_i - \hat y_i is the difference between the true value and the prediction. We square each residual and average them, giving the mean squared error:

MSE=1n∑i=1n(yi−y^i)2. \text{MSE} = \frac{1}{n}\sum_{i=1}^{n}(y_i - \hat y_i)^2.

Squaring does two useful things. It makes every error count as positive, so that over-predictions and under-predictions can't cancel each other out. And it penalises large errors much more heavily than small ones: an error of 10 counts 100 times as much as an error of 1. As the likelihood topic shows, this choice is also exactly what maximum likelihood recommends when the noise in the data is Gaussian. "Fitting" linear regression means finding the weights that make this MSE as small as possible.

Interactive: this part runs in your browser.

Breakdown. The MSE formula taken apart: tap each coloured part to see where it appears in the calculation.
Beginner

Watch it: Linear regression: finding the best straight line

A short narrated animation. Press ▶ Play, or step through it with ⏮ ⏭. Tick 🔊 narrate to hear each step.

Interactive: this part runs in your browser.

Try it

Try it: fit a line by hand

Move the sliders to make the red residual lines as short as possible, watching the MSE. Then press Snap to best fit to see the exact least-squares answer.

Interactive: this part runs in your browser.

Beginner

Solving it

There are two main ways to find the weights that minimise the squared error, and both are used in practice.

The first is an exact formula called the normal equation. If we stack the training examples into a data matrix XX (with a column of 1s for the intercept) and the targets into a vector yy, the best weights are

w^=(X⊤X)−1X⊤y. \hat w = (X^\top X)^{-1}X^\top y.

This gives the exact answer in one calculation, with no iteration and no learning rate to tune. Its drawbacks appear at scale: inverting the d×dd\times d matrix X⊤XX^\top X takes time roughly proportional to d3d^3, which becomes slow with many features, and the matrix cannot be inverted at all if some features are exact combinations of others. The next section derives this formula step by step.

The second is gradient descent, which starts from some initial weights and repeatedly takes small steps downhill on the squared-error surface. It needs many steps, but each one is cheap, and it scales to enormous datasets because it can work on small batches of data at a time. It is also the method that generalises to models without a neat formula, such as neural networks, which is why it has a topic of its own.

Linear regression relies on a few assumptions, and knowing them helps you recognise when it is the wrong tool. It assumes the relationship between features and target is roughly linear; that the errors for different examples are independent of each other; that the errors have about the same spread everywhere (called homoscedasticity); and that the features are not too strongly correlated with one another (otherwise the individual weights become unstable). Plotting the residuals against the predictions is a quick way to check: a healthy model shows a shapeless cloud, while a curve or a funnel shape signals that an assumption is violated.

The usual summary of fit is R2R^2, the coefficient of determination:

R2=1−∑i(yi−y^i)2∑i(yi−yˉ)2. R^2 = 1 - \frac{\sum_i(y_i - \hat y_i)^2}{\sum_i(y_i - \bar y)^2}.

The denominator measures how much the targets vary around their average, and the numerator measures how much error remains after using the model. So R2R^2 is the fraction of the variation that the model explains. A value of 1 means perfect predictions, and a value of 0 means the model is no better than always predicting the average.

Finally, "linear" refers to the weights, not to the features. If you add new features such as x2x^2 and x3x^3, the model y^=w1x+w2x2+w3x3+b\hat y = w_1x + w_2x^2 + w_3x^3 + b can fit curves, but it is still a weighted sum, so all of the methods above still apply unchanged. This is called polynomial regression, and it reappears in the bias–variance topic.

Interactive: this part runs in your browser.

Interactive. Least squares made literal: move the line and watch the total area of the squares.
Intermediate · Maths

Deriving the normal equation

📐 Maths you'll need: m-matrices · m-gradients
💡 The idea in plain words

We want the weights that make the total squared error smallest. The error is a bowl-shaped function of the weights, and at the bottom of a bowl the slope is zero in every direction. Setting the gradient to zero gives a system of linear equations, and solving it gives the best weights directly, with no iteration needed.

🔤 Symbols in this section
X∈Rn×dX\in\mathbb R^{n\times d}design matrix: n examples (rows), d features (columns)
y∈Rny\in\mathbb R^nvector of targets
wwweight vector
∥v∥2\lVert v\rVert^2squared length = sum of squares
X⊤X^\toptranspose of X
(⋅)−1(\cdot)^{-1}matrix inverse
HHthe "hat" matrix that maps y to predictions

Here we derive the normal equation carefully, using the matrix calculus from the gradients topic, and then look at what it means geometrically.

space spanned by the columns of X (all possible predictions Xw)yŷ = Xŵresidual y − ŷ⟂ every column of X
Geometrically, least squares projects y onto the space of possible predictions; the residual is perpendicular to it (the "normal" equation).

We collect the training data into a design matrix X∈Rn×dX\in\mathbb R^{n\times d}, with one row per example and one column per feature (including a column of 1s so that the intercept is just another weight), and the targets into a vector y∈Rny\in\mathbb R^n. The predictions for all examples are XwXw, and the total squared error is the squared length of the residual vector:

L(w)=∥y−Xw∥2=(y−Xw)⊤(y−Xw). L(w) = \lVert y - Xw \rVert^2 = (y - Xw)^\top (y - Xw).

Multiplying out the brackets, and using the facts that (Xw)⊤=w⊤X⊤(Xw)^\top = w^\top X^\top and that a single number equals its own transpose, gives three terms:

L(w)=y⊤y−2w⊤X⊤y+w⊤X⊤Xw. L(w) = y^\top y - 2w^\top X^\top y + w^\top X^\top X w.

Now we take the gradient with respect to ww, one term at a time. The first term y⊤yy^\top y does not depend on ww, so its gradient is zero. The second is linear in ww, and by the rule ∇w(a⊤w)=a\nabla_w(a^\top w) = a it contributes −2X⊤y-2X^\top y. The third is a quadratic form with the symmetric matrix X⊤XX^\top X, and by the rule ∇w(w⊤Aw)=2Aw\nabla_w(w^\top Aw) = 2Aw it contributes 2X⊤Xw2X^\top Xw. So

∇wL=−2X⊤y+2X⊤Xw=−2X⊤(y−Xw). \nabla_w L = -2X^\top y + 2X^\top X w = -2X^\top (y - Xw).

At the minimum, the gradient must be zero. Setting it equal to zero and dividing by −2 gives the normal equation, X⊤X w=X⊤yX^\top X\, w = X^\top y. If X⊤XX^\top X can be inverted (which is true whenever no feature is an exact combination of the others), multiplying both sides by its inverse gives the solution:

w^=(X⊤X)−1X⊤y \boxed{\hat w = (X^\top X)^{-1} X^\top y}

How do we know this stationary point is a minimum and not a maximum? The Hessian of LL is 2X⊤X2X^\top X, and as shown in the eigenvectors topic, X⊤XX^\top X is always positive semi-definite. The loss is therefore a bowl (it is convex), so any point where the gradient is zero is a global minimum.

The normal equation also has a lovely geometric meaning. The predictions y^=Xw^\hat y = X\hat w can be written as y^=Hy\hat y = Hy, where H=X(X⊤X)−1X⊤H = X(X^\top X)^{-1}X^\top is called the hat matrix (because it puts the hat on yy). The vector y^\hat y is the orthogonal projection of yy onto the space spanned by the columns of XX: out of all the vectors the model could possibly produce, it is the one closest to the true targets. Rewriting the normal equation as X⊤(y−y^)=0X^\top(y - \hat y) = 0 says that the residual vector is perpendicular, or "normal", to every feature column. That is where the name comes from, and it makes sense: if the residual still had some component along a feature, we could reduce the error further by adjusting that feature's weight.

Key takeaway. Setting the gradient −2Xᵀ(y − Xw) to zero gives XᵀXw = Xᵀy, so ŵ = (XᵀX)⁻¹Xᵀy; geometrically, predictions are the projection of y onto the space of the features.
Advanced

Statistical properties, R² and numerical stability

📐 Maths you'll need: m-prob · m-eigen
💡 The idea in plain words

If you collected a different sample of data, you'd get slightly different weights. This section asks: on average, are the weights right (unbiased)? And how much do they wobble from sample to sample (variance)? The wobble is large when features are strongly correlated, because the data can't tell which feature deserves the credit.

🔤 Symbols in this section
w∗w^*the true weights
ε\varepsilonrandom noise
σ2\sigma^2noise variance
Cov⁡(w^)\operatorname{Cov}(\hat w)covariance matrix of the estimated weights
VIFj\text{VIF}_jvariance inflation factor for feature j
Radj2R^2_{\text{adj}}adjusted R²
Q, RQ,\ RQR decomposition (orthogonal × triangular)

If you collected a fresh sample of data and refitted the model, you would get slightly different weights. This section asks how good the least-squares weights are as estimates: are they right on average, and how much do they vary?

To answer this, assume the data really come from a linear model, y=Xw∗+εy = Xw^* + \varepsilon, where w∗w^* are the true weights and ε\varepsilon is random noise with mean zero, variance σ2\sigma^2, and no correlation between examples. Substituting this into the normal equation gives

w^=(X⊤X)−1X⊤(Xw∗+ε)=w∗+(X⊤X)−1X⊤ε. \hat w = (X^\top X)^{-1}X^\top(Xw^* + \varepsilon) = w^* + (X^\top X)^{-1}X^\top \varepsilon.

The estimate equals the true weights plus a term caused by the noise. Since the noise averages to zero, so does that term, and therefore E[w^]=w∗\mathbb E[\hat w] = w^*: least squares is unbiased. The variability of the estimate comes entirely from the noise term, and working out its covariance gives

Cov⁡(w^)=σ2(X⊤X)−1. \operatorname{Cov}(\hat w) = \sigma^2 (X^\top X)^{-1}.

The Gauss–Markov theorem adds that, among all estimators that are linear in yy and unbiased, least squares has the smallest variance. It is often summarised by saying that least squares is the BLUE, the best linear unbiased estimator.

The covariance formula reveals an important practical danger. When two features are strongly correlated, such as house size in square metres and number of rooms, X⊤XX^\top X is close to being non-invertible: its smallest eigenvalue is tiny, so its inverse has a huge entry, and the variance of the weights becomes enormous. Intuitively, the data can't tell which of the two correlated features deserves the credit, so their weights swing wildly from sample to sample even though the predictions stay sensible. This problem is called multicollinearity. It is measured for each feature by the variance inflation factor, VIFj=1/(1−Rj2)\text{VIF}_j = 1/(1 - R_j^2), where Rj2R_j^2 is how well feature jj can be predicted from the other features. Ridge regression fixes it by adding λI\lambda I to X⊤XX^\top X.

In practice σ2\sigma^2 is unknown, but it can be estimated from the residuals: σ^2=1n−d∥y−Xw^∥2\hat\sigma^2 = \frac{1}{n-d}\lVert y - X\hat w\rVert^2. We divide by n−dn - d rather than nn because fitting dd weights uses up dd "degrees of freedom" and makes the residuals slightly smaller than the true noise. Plugging this estimate into the covariance formula gives a standard error for each weight, which statistics packages use to produce confidence intervals and to test whether a weight is significantly different from zero.

A word on comparing models with R2R^2: adding any feature, even pure noise, can never make the training R2R^2 go down, so it always favours bigger models. The adjusted R2R^2 corrects for this by penalising the number of features dd:

Radj2=1−(1−R2)n−1n−d−1. R^2_{\text{adj}} = 1 - (1 - R^2)\frac{n - 1}{n - d - 1}.

Finally, a numerical point. Although the formula contains (X⊤X)−1(X^\top X)^{-1}, good software never computes that inverse explicitly. Forming X⊤XX^\top X squares the condition number of the problem, which can magnify rounding errors badly. Instead, libraries use a QR decomposition of XX or the singular value decomposition, which solve the same least-squares problem accurately and also cope with columns that are exact combinations of others. NumPy's np.linalg.lstsq does this for you.

Key takeaway. OLS is unbiased with Cov(ŵ) = σ²(XᵀX)⁻¹: correlated features make the weights unstable, and you should solve least squares with QR/SVD rather than an explicit inverse.
Code

Code: three ways to fit linear regression

The same model fitted by the normal equation, by gradient descent, and by scikit-learn. All three agree.

Python · NumPy from scratch
import numpy as np

rng = np.random.default_rng(0)
n, d = 200, 3
X = rng.normal(size=(n, d))
true_w, true_b = np.array([2.0, -1.0, 0.5]), 4.0
y = X @ true_w + true_b + rng.normal(scale=0.5, size=n)

Xb = np.c_[np.ones(n), X]                      # add intercept column

# 1) Normal equation, solved stably (QR/SVD under the hood)
w_ls, *_ = np.linalg.lstsq(Xb, y, rcond=None)
print("lstsq:      ", w_ls.round(3))

# 2) Batch gradient descent on MSE = (1/n)||y - Xw||^2
w = np.zeros(d + 1)
lr = 0.1
for epoch in range(500):
    grad = -2 / n * Xb.T @ (y - Xb @ w)        # derived above
    w -= lr * grad
print("grad descent:", w.round(3))

# Goodness of fit
y_hat = Xb @ w_ls
r2 = 1 - np.sum((y - y_hat) ** 2) / np.sum((y - y.mean()) ** 2)
print("R^2 =", round(r2, 4))
Open in playground ↗
Python · scikit-learn
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_squared_error, r2_score

reg = LinearRegression().fit(X, y)              # intercept handled for you
print("intercept:", reg.intercept_.round(3), "coef:", reg.coef_.round(3))
print("MSE:", round(mean_squared_error(y, reg.predict(X)), 4),
      " R^2:", round(r2_score(y, reg.predict(X)), 4))
# Polynomial regression = PolynomialFeatures + LinearRegression in a pipeline
Open in playground ↗
Before it runs, the code block above runs first (silently), because this one continues it.
Check yourself

Quiz

1. What does MSE stand for and do?

2. R² = 0 means the model is…

3. Polynomial regression (x, x², x³) is…

4. The normal equation says the residual vector is…

5. Under the standard assumptions, Cov(ŵ) equals…

Go deeper

📚 Further reading

Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.

Ready