linear-regression

A regression model that assumes the target $y$ is a linear function of (possibly transformed) input features plus noise: $y={\mathbf{w}}^{\top }\mathbf{\varphi }(\mathbf{x})+\epsilon$. The standard fit is ordinary least squares — minimise the sum of squared residuals — which has a closed-form solution via the normal equation.

The Model

Linear regression posits that the target $y$ depends linearly on a fixed set of basis functions of the input:

$\hat{y}(\mathbf{x},\mathbf{w})={\sum }_{j=0}^M{w}_j{\varphi }_j(\mathbf{x})={\mathbf{w}}^{\top }\mathbf{\varphi }(\mathbf{x})$

where:

• $\mathbf{\varphi }(\mathbf{x})=({\varphi }_0(\mathbf{x}),{\varphi }_1(\mathbf{x}),\dots ,{\varphi }_M(\mathbf{x}){)}^{\top }$ is a vector of basis functions, with ${\varphi }_0(\mathbf{x})=1$ as a dummy for the intercept.
• $\mathbf{w}=(w_0,w_1,\dots ,w_M{)}^{\top }$ is the weight vector to be learned.
• $\hat{y}$ is the predicted value; the actual observed $y$ is assumed to differ by some noise $\epsilon$.

The simplest case (${\varphi }_j(\mathbf{x})=x_j$) gives plain $\hat{y}=w_0+w_1{x}_1+\cdots +w_d{x}_d$ — a hyperplane in input space.

Why It’s Called “Linear”

The name refers to linearity in the parameters $\mathbf{w}$, not linearity in $\mathbf{x}$. The following are all linear regression models, even though they bend dramatically in input space:

$y=w_0+w_1{x}_1^2+w_2{x}_2^2+\cdots +w_D{x}_D^2$ $y=w_0+w_1{e}^{x_1}+w_2{e}^{x_2}$ $y=w_0+w_1\exp \left(-\frac{(x-{\mu }_1{)}^2}{2s^2}\right)+w_2\exp \left(-\frac{(x-{\mu }_2{)}^2}{2s^2}\right)$

What makes them “linear” is that $\partial \hat{y}/\partial w_j$ is a function of $\mathbf{x}$ alone — not of $\mathbf{w}$. The prediction is a linear combination of pre-computed basis values; the unknowns $\mathbf{w}$ enter linearly.

This matters because OLS only relies on linearity in $\mathbf{w}$ to give a closed-form solution. The same recipe handles polynomial regression, RBF regression, and arbitrary fixed-basis models.

Common Basis Functions

Basis	Form	When
Polynomial	${\varphi }_j(x)=x^j$	Smooth low-degree relationships
Gaussian / RBF	${\varphi }_j(x)=\exp (-\frac{(x-{\mu }_j{)}^2}{2s^2})$	Local bumps; bell-shaped responses
Sigmoidal	${\varphi }_j(x)=(1+e^{-(x-{\mu }_j)/s}{)}^{-1}$	Smooth saturation effects
tanh	${\varphi }_j(x)=\tanh ((x-{\mu }_j)/s)$	Symmetric saturation

For multi-input data, basis functions are typically applied per dimension or to selected combinations.

Fitting the Model

Two equivalent recipes for finding $\mathbf{w}$:

1. Ordinary Least Squares (OLS) — minimise the sum of squared residuals. Yields the normal equation: ${\mathbf{w}}_{\text{OLS}}=({\mathbf{\Phi }}^{\top }\mathbf{\Phi }{)}^{-1}{\mathbf{\Phi }}^{\top }\mathbf{y}$ where $\mathbf{\Phi }$ is the design matrix.

2. Maximum Likelihood Estimation under Gaussian noise — assume $y=\hat{y}(\mathbf{x},\mathbf{w})+\epsilon$ with $\epsilon \sim \mathcal{N}(0,{\sigma }^2)$. The MLE for $\mathbf{w}$ is identical to the OLS solution. See OLS § MLE equivalence.

The probabilistic view (recipe 2) supplies the missing justification for why we minimise squared error: it’s the optimal estimator under additive Gaussian noise.

Predictions and Evaluation

Once $\mathbf{w}$ is fit, predict $\hat{y}({\mathbf{x}}_{\text{new}})={\mathbf{w}}^{\top }\mathbf{\varphi }({\mathbf{x}}_{\text{new}})$.

Common evaluation metrics:

Metric	Formula	Notes
MSE	$\frac{1}{N}\sum (y_i-{\hat{y}}_i{)}^2$	What OLS minimises (up to scale)
RMSE	$\sqrt{\text{MSE}}$	Same units as $y$; interpretable
MAE	$\tfrac{1}{N} \sum	y_i - \hat{y}_i
$R^2$	$1-\frac{\sum (y_i-{\hat{y}}_i{)}^2}{\sum (y_i-\bar{y}{)}^2}$	Fraction of variance explained; 1 = perfect

Choosing the Polynomial Degree

A higher-degree polynomial can fit any training set arbitrarily well (with $M=N$, you can interpolate every point exactly). But this overfits — the curve thrashes wildly between training points and fails on test data.

This is where regularisation and validation enter the picture (later weeks). The intuition: pick the degree that fits the data well without contorting itself into the noise.

Strengths and Limitations

Strengths:

• Closed-form solution via the normal equation. No iterations, no learning rate.
• Convex objective — unique global optimum.
• Interpretable coefficients — each $w_j$ is the (partial) effect of feature $j$ on the output.
• Probabilistic backing — MLE under Gaussian noise gives the same answer.
• Extends to non-linear shapes via basis expansion without leaving the linear-regression machinery.

Limitations:

• Sensitive to outliers — squared loss penalises large residuals quadratically; one extreme point can dominate the fit. Use MAE or robust regression if outliers are an issue.
• Numerical issues — $({\mathbf{\Phi }}^{\top }\mathbf{\Phi }{)}^{-1}$ becomes ill-conditioned when columns of $\mathbf{\Phi }$ are near-collinear, or when $M>N$. Then OLS fails outright; gradient descent or regularisation is needed.
• Overfitting with too many basis functions — high-degree polynomials or many RBFs without regularisation will memorise noise.
• Linear-in-parameters is still a constraint — if the true relationship is genuinely non-linear-in-parameters (e.g., $y=e^{w_{1}x}$), linear regression with any basis can only approximate, never recover it.

Connections

• ordinary-least-squares — the criterion and closed-form solution.
• design-matrix — the $N\times (M+1)$ matrix whose rows are basis-function evaluations of each training input.
• non-linear-transformation — the basis-expansion trick, shared with SVMs.
• gaussian-distribution — the noise model that justifies squared loss.
• maximum likelihood estimation — the principle that links OLS to a probabilistic model.
• gradient descent — alternative fitting method when ${\mathbf{\Phi }}^{\top }\mathbf{\Phi }$ is too large/singular.
• logistic-regression — the classification analogue: linear in parameters, but with sigmoid + Bernoulli noise instead of identity + Gaussian noise.

Active Recall

Why is the model $y=w_0+w_1{x}^2$ called "linear regression" even though it traces a parabola?

Linearity refers to the parameters $\mathbf{w}$, not the input $x$. We can write it as $y={\mathbf{w}}^{\top }\mathbf{\varphi }(x)$ with $\mathbf{\varphi }(x)=(1,x^2{)}^{\top }$. The derivative $\partial y/\partial w_j$ is a function of $x$ alone, not of $\mathbf{w}$ — that’s the linear-in-parameters property. OLS works because of this linearity, regardless of what $\mathbf{\varphi }$ does in input space.

A dataset has 14 examples and 3 features (plus intercept). What are the dimensions of $\mathbf{\Phi }$, $\mathbf{y}$, and $\mathbf{w}$ in the normal equation?

$\mathbf{\Phi }$ is $14\times 4$ (one row per example, one column per parameter including the intercept). $\mathbf{y}$ is $14\times 1$. $\mathbf{w}$ is $4\times 1$.

Given training data $(x,y)$: $(1,0.5),(0,0),(6,3),(4,2)$. Linear regression $y=w_0+w_{1}x$ fits perfectly. What are $w_0$ and $w_1$?

The relationship is $y=0.5x$, so $w_0=0$ and $w_1=0.5$. (Verify: $0.5\cdot 1=0.5$, $0.5\cdot 0=0$, $0.5\cdot 6=3$, $0.5\cdot 4=2$. ✓)