# 4. Linear regression Linear regression predicts a continuous target from a linear score. This module follows one thread from end to end: pose the model, fit it to noisy data by least squares, justify that objective by maximum likelihood, regularize it by maximum a posteriori (ridge, then its selecting cousin the lasso), then widen the model with basis functions and multiple outputs, where the same two closed forms return unchanged. ## 4.1 The linear model The hypothesis is linear in the augmented input $x \in \mathbb{R}^{n+1}$ with $x_0 = 1$, the convention of the [Introduction](/en/Machine%20Learning/01%20Introduction): $$\boxed{ h_w(x) = w^T x = w_0 + w_1 x_1 + \dots + w_n x_n }$$ $w_0$ is the bias (the intercept) and the remaining coordinates are the weights, and folding the bias into the dot product is exactly what the $x_0 = 1$ convention buys. Geometrically, the prediction is a line for $n = 1$, a plane for $n = 2$, and a hyperplane beyond.  *With one feature the model draws a line through the data, with two a plane, and beyond that a hyperplane that can no longer be drawn.* ## 4.2 The problem to solve Given the training set $\{(x^{(i)}, y^{(i)})\}_{i=1}^{m}$, ideally we would have $h_w(x^{(i)}) = y^{(i)}$ at every point. Real targets are noisy (measurement error, unmodelled factors), so no line passes through them all, and the goal becomes to make the smallest total error. Least squares takes the squared residual as the error and sums it over the training set: $$\boxed{ w^{*} = \arg\min_w \; \sum_{i=1}^{m}\left(w^T x^{(i)} - y^{(i)}\right)^2 }$$  *Left: if the targets were noise-free, the model could pass through every point. Right: real targets scatter around the trend, so each point leaves a residual between $y^{(i)}$ and the prediction $h_w(x^{(i)})$, and the fit minimizes their sum of squares (grey segments).* *Remark:* why the square rather than, say, the absolute value? Because this choice is provably optimal when the noise is Gaussian, a classic interview question that the next section unpacks. ## 4.3 Maximum likelihood: least squares justified Give the data a generative story, using the estimation principle of [Probabilistic formulation](/en/Machine%20Learning/03%20Probabilistic%20formulation): each target is the linear prediction plus independent Gaussian noise, $$\boxed{ y^{(i)} = w^T x^{(i)} + \varepsilon^{(i)}, \quad \varepsilon^{(i)} \sim \mathcal{N}(0, \sigma^2) }$$ so $p(y^{(i)} \mid x^{(i)}; w) = \mathcal{N}(w^T x^{(i)}, \sigma^2)$. Maximum likelihood picks the parameters under which the observed targets are the most probable, and it delivers two results. First, maximizing the likelihood is exactly minimizing the sum of squared errors: $$\boxed{ w_{\mathrm{MLE}} = \arg\max_w \; p(y \mid X; w) = \arg\min_w \; \sum_{i=1}^{m}\left(y^{(i)} - w^T x^{(i)}\right)^2 }$$ Second, the minimizer has a closed form, the normal equation, with $X$ the design matrix whose rows are the $x^{(i)T}$: $$\boxed{ w_{\mathrm{MLE}} = (X^T X)^{-1}X^T y }$$ one matrix solve away from the data. *Remark:* the first box is the most important fact of the module. Least squares is not a convenient convention, it is the maximum-likelihood estimate under Gaussian noise. <details class="proof"> <summary>Proof: maximizing the likelihood is minimizing the squared error</summary> The examples are i.i.d., so the likelihood of the whole training set factorizes into a product of Gaussian densities: $$p(y \mid X; w) = \prod_{i=1}^{m} p(y^{(i)} \mid x^{(i)}; w) = \prod_{i=1}^{m} \frac{1}{\sqrt{2\pi\sigma^2}}\, \exp\!\left(-\frac{\left(y^{(i)} - w^T x^{(i)}\right)^2}{2\sigma^2}\right)$$ The logarithm is increasing, so it preserves the argmax and turns the product into a sum, the log-likelihood, which separates into a constant and the sum of squares: $$\ell(w) = \sum_{i=1}^{m} \log \mathcal{N}\!\left(y^{(i)} \mid w^T x^{(i)}, \sigma^2\right) = -\frac{m}{2}\log(2\pi\sigma^2) \;-\; \frac{1}{2\sigma^2}\sum_{i=1}^{m}\left(y^{(i)} - w^T x^{(i)}\right)^2$$ The first term does not depend on $w$ and the factor $\tfrac{1}{2\sigma^2}$ is a positive constant, so neither moves the argmax. Maximizing $\ell$ is therefore minimizing the sum of squared errors. $\blacksquare$ </details> <details class="proof"> <summary>Proof: the normal equation</summary> With the design matrix, the sum of squares is the quadratic $\lVert Xw - y \rVert^2$, a convex function of $w$, so its global minimum is the point of zero gradient: $$\nabla_w\, \lVert Xw - y \rVert^2 = 2\,X^T(Xw - y) = 0 \;\Longleftrightarrow\; X^T X\, w = X^T y$$ Provided $X^T X$ is invertible (independent features, more examples than features), isolating $w$ gives $w_{\mathrm{MLE}} = (X^T X)^{-1}X^T y$. $\blacksquare$ </details> ## 4.4 Maximum a posteriori: ridge regression Maximum likelihood can overfit, especially when the model is flexible. The maximum a posteriori estimate maximizes the posterior instead, which by Bayes' rule is the likelihood times a prior on the parameters, here a zero-mean Gaussian: $$w_{\mathrm{MAP}} = \arg\max_w \; p(y \mid X, w)\, p(w), \qquad w \sim \mathcal{N}(0, \tau^2 I)$$ Two results again. The Gaussian prior turns into an L2 penalty added to least squares: $$\boxed{ w_{\mathrm{MAP}} = \arg\min_w \; \sum_{i=1}^{m}\left(y^{(i)} - w^T x^{(i)}\right)^2 + \lambda \lVert w \rVert_2^2, \quad \lambda = \frac{\sigma^2}{\tau^2} }$$ and the penalized minimizer keeps a closed form: $$\boxed{ w_{\mathrm{MAP}} = (X^T X + \lambda I)^{-1}X^T y }$$ This is ridge regression, and the penalty is often called weight decay. The Gaussian prior became the L2 penalty of [General concepts](/en/Machine%20Learning/02%20General%20concepts), exactly the prior-to-penalty link of [Probabilistic formulation](/en/Machine%20Learning/03%20Probabilistic%20formulation). *Remark:* $\lambda \to 0$ recovers maximum likelihood, and a growing $\lambda$ shrinks $w$ toward zero and fights overfitting. A stronger prior (small $\tau$) means a larger $\lambda$. Note also that $X^T X + \lambda I$ is always invertible for $\lambda > 0$, which rescues least squares exactly where it breaks down: strongly correlated features, or more features than examples. <details class="proof"> <summary>Proof: the Gaussian prior becomes the L2 penalty</summary> By Bayes' rule the posterior is $$p(w \mid y, X) = \frac{p(y \mid X, w)\, p(w)}{p(y \mid X)}$$ and the denominator does not depend on $w$, so maximizing the posterior is maximizing the likelihood times the prior. The prior covariance is generally unknown, so it is assumed isotropic, $\tau^2 I$, which gives the density $$p(w) = \frac{1}{(2\pi\tau^2)^{(n+1)/2}}\, \exp\!\left(-\frac{\lVert w \rVert^2}{2\tau^2}\right)$$ Taking logarithms and reusing the log-likelihood $\ell(w)$ from the previous proof, $$\log p(y \mid X, w) + \log p(w) = \mathrm{const} \;-\; \frac{1}{2\sigma^2}\sum_{i=1}^{m}\left(y^{(i)} - w^T x^{(i)}\right)^2 \;-\; \frac{1}{2\tau^2}\lVert w \rVert^2$$ where the constant gathers every term independent of $w$. Multiplying by $-2\sigma^2$, a negative constant that flips the argmax into an argmin, leaves $$w_{\mathrm{MAP}} = \arg\min_w \; \sum_{i=1}^{m}\left(y^{(i)} - w^T x^{(i)}\right)^2 + \frac{\sigma^2}{\tau^2}\, \lVert w \rVert^2$$ and $\lambda = \sigma^2 / \tau^2$ names the ratio: the noisier the data or the tighter the prior, the heavier the penalty. $\blacksquare$ </details> <details class="proof"> <summary>Proof: the ridge closed form</summary> In matrix form the objective is $\lVert Xw - y \rVert^2 + \lambda \lVert w \rVert^2$, still a convex quadratic, so the zero-gradient condition finds its global minimum: $$\nabla_w \left( \lVert Xw - y \rVert^2 + \lambda \lVert w \rVert^2 \right) = 2\,X^T(Xw - y) + 2\lambda w = 0 \;\Longleftrightarrow\; (X^T X + \lambda I)\, w = X^T y$$ For $\lambda > 0$ the matrix $X^T X + \lambda I$ is positive definite, hence invertible, with no condition on $X$ this time: for any $v \neq 0$, $v^T (X^T X + \lambda I)\, v = \lVert X v \rVert^2 + \lambda \lVert v \rVert^2 > 0$. Isolating $w$ gives $w_{\mathrm{MAP}} = (X^T X + \lambda I)^{-1} X^T y$. $\blacksquare$ </details> ## 4.5 The lasso: a penalty that selects The ridge penalty came from a Gaussian prior. A Laplace prior yields the L1 penalty instead, the link noted in [Probabilistic formulation](/en/Machine%20Learning/03%20Probabilistic%20formulation): $$\boxed{ w_{\mathrm{lasso}} = \arg\min_w \; \sum_{i=1}^{m}\left(y^{(i)} - w^T x^{(i)}\right)^2 + \lambda \lVert w \rVert_1 }$$ The change looks small, its consequences are not: - **It selects.** The lasso drives some coefficients to exactly zero, performing variable selection while it fits. Ridge only shrinks and never zeroes: ridge stabilizes, the lasso selects. - **The reason is geometric.** The constraint region $\lVert w \rVert_1 \le t$ is a diamond with corners on the axes, and the elliptical contours of the squared error tend to touch a corner first, where a coordinate is zero. The rounded L2 ball has no corners to catch. - **$\lambda$ traces a path.** As $\lambda$ grows, coefficients hit exactly zero one after another, from the full model down to the empty one. As always, $\lambda$ is chosen by the cross-validation of [General concepts](/en/Machine%20Learning/02%20General%20concepts), often the largest $\lambda$ within one standard error of the best. - **No closed form.** The L1 penalty is not differentiable at zero, so the lasso is fitted by convex solvers rather than a formula. - **The elastic net** blends the two penalties, $\lambda\left(\alpha \lVert w \rVert_1 + (1-\alpha)\lVert w \rVert_2^2\right)$, keeping the lasso's selection with the ridge's stability under correlated features. *Remark:* prediction is not inference. Selecting variables with the lasso and then reporting textbook standard errors on the same data is invalid, the winner's curse again: the intervals ignore that the data already chose the variables. Honest inference needs sample splitting or a debiased estimator, the doorway to causal machine learning. ## 4.6 Basis functions: nonlinear in $x$, linear in $w$ A straight line is often too rigid: the underfitting of [General concepts](/en/Machine%20Learning/02%20General%20concepts) appeared precisely when a low-capacity model met a curved trend. The fix is not to abandon the linear machinery but to project the input into a larger space, where the relationship is linear: $$\boxed{ h_w(x) = w^T \phi(x) = \sum_{j=0}^{M-1} w_j\, \phi_j(x), \qquad \phi_0(x) = 1 }$$ The $\phi_j$ are basis functions, fixed before training. With $\phi(x) = (1, x, x^2, \dots, x^d)$ they give polynomial regression, the running example of [General concepts](/en/Machine%20Learning/02%20General%20concepts), and the identity $\phi(x) = x$ recovers everything above. The model can now be wildly nonlinear in $x$ yet stays linear in $w$, so nothing changes in the fit: stack the $\phi(x^{(i)})^T$ as the rows of the design matrix $\Phi \in \mathbb{R}^{m \times M}$ and the two closed forms return verbatim: $$\boxed{ w_{\mathrm{MLE}} = (\Phi^T \Phi)^{-1}\Phi^T y, \qquad w_{\mathrm{MAP}} = (\Phi^T \Phi + \lambda I)^{-1}\Phi^T y }$$ *Remark:* the basis (its family and its size $M$) is a hyperparameter, chosen before training, while $w$ is learned. Choosing $M$ and $\lambda$ is the model-selection problem settled by the cross-validation of [General concepts](/en/Machine%20Learning/02%20General%20concepts). ## 4.7 Multiple outputs Nothing restricts the target to a single number. To predict $K$ values at once (say a house's price, heating cost, and property tax from the same features), let $y^{(i)} \in \mathbb{R}^K$ and give each output its own parameter column, gathered in a matrix $W \in \mathbb{R}^{M \times K}$: $$\boxed{ h_W(x) = W^T \phi(x) \in \mathbb{R}^{K} }$$ Stacking the targets as the rows of $Y \in \mathbb{R}^{m \times K}$, the same derivations give the same closed forms, now solving all $K$ regressions at once: $$\boxed{ W_{\mathrm{MLE}} = (\Phi^T \Phi)^{-1}\Phi^T Y, \qquad W_{\mathrm{MAP}} = (\Phi^T \Phi + \lambda I)^{-1}\Phi^T Y }$$ *Remark:* the expensive factor $(\Phi^T \Phi)^{-1}$ does not depend on the targets, so it is computed once and shared by all $K$ outputs. ## 4.8 Summary | | Formula | | --- | --- | | Model | $h_w(x) = w^T \phi(x)$ | | Maximum likelihood (least squares) | $w_{\mathrm{MLE}} = (\Phi^T \Phi)^{-1}\Phi^T y$ | | Maximum a posteriori (ridge) | $w_{\mathrm{MAP}} = (\Phi^T \Phi + \lambda I)^{-1}\Phi^T y$ | | Parameters, learned | $w$ (or $W$ for $K$ outputs) | | Hyperparameters, chosen by validation | the basis $\phi$ and its size $M$, the penalty $\lambda$ | *The same linear score, passed through a squashing function instead of read directly, turns regression into classification, the subject of the next module.* --- Next: [Linear classification](/en/Machine%20Learning/05%20Linear%20classification) · [Course overview](/en/Machine%20Learning)