Supervised Learning

Linear Regression

Linear regression learns a linear predictor $\hat{y}=⟨w,x⟩$ by minimizing squared residuals. It is the foundational supervised learning method: convex, closed-form, and the MLE under Gaussian noise.

Setup

Given $(x_1,y_1),\dots ,(x_n,y_n){\sim }_{i.i.d.}P$ with $x_i\in {\mathbf{R}}^d$, $y_i\in \mathbf{R}$ (continuous labels, unlike classification).

Use the padding trick $x\to (x,1)$, $w\to (w,b)$ so the line need not pass through the origin.

Empirical Risk Minimization (ERM)

The general learning goal is $\arg {\min }_w{\mathbb{E}}_{(x,y)\sim P}[{\ell }_w(x,y)]$, but $P$ is unknown. ERM minimizes the empirical distribution instead:

$\arg {\min }_w\frac{1}{n}{\sum }_{i=1}^n{\ell }_w(x_i,y_i)$

This converges to the true risk as $n\to \infty$.

Squared Loss

${\ell }_w(x,y)=(y-⟨w,x⟩{)}^2$

Stacking feature vectors into $A\in {\mathbf{R}}^{n\times d}$ and labels into $z\in {\mathbf{R}}^n$:

$\mathcal{L}(w)=\Vert Aw-z{\Vert }_2^2$

Intuition

Squared loss punishes big misses far more than small ones: being off by 10 costs 100x as much as being off by 1, not 10x. This makes the fit chase outliers. L1 loss (absolute value) would be robust but non-differentiable; squared loss trades robustness for clean calculus.

Convexity

$\Vert Aw-z{\Vert }_2^2=w^{\top }{A}^{\top }Aw-2w^{\top }{A}^{\top }z+z^{\top }z$. The Hessian is ${\nabla }_w^2\Vert Aw-z{\Vert }_2^2=2A^{\top }A⪰0$ (since $v^{\top }{A}^{\top }Av=\Vert Av{\Vert }_2^2\ge 0$), so the loss is convex.

Normal Equations (Closed Form)

Setting ${\nabla }_w\Vert Aw-z{\Vert }_2^2=2A^{\top }Aw-2A^{\top }z=0$:

$A^{\top }A\hat{w}=A^{\top }z$

If $A^{\top }A$ is invertible: $\hat{w}=(A^{\top }A{)}^{-1}{A}^{\top }z$. In practice, solve the linear system directly: the matrix inverse is slow and numerically imprecise for ill-conditioned $A^{\top }A$.

Geometric picture

$\hat{w}$ is the projection of $z$ onto the column space of $A$. The residual $A\hat{w}-z$ is orthogonal to every column of $A$ (which is exactly what $A^{\top }(A\hat{w}-z)=0$ says). You are finding the closest point to $z$ that is reachable by a linear combination of features.

Why squared loss?

Squared loss falls out of Gaussian-noise MLE.

Assume $y=⟨w,x⟩+z$ where $z\sim \mathcal{N}(0,{\sigma }^2)$. Then $y\mid x,w\sim \mathcal{N}(⟨w,x⟩,{\sigma }^2)$.

$\hat{w}=\arg {\max }_w{\prod }_i\mathrm{Pr}[y_i\mid x_i,w]=\arg {\max }_w{\sum }_i\log \frac{1}{\sqrt{2\pi }\sigma }\exp \left(-\frac{(y_i-⟨w,x_i⟩{)}^2}{2{\sigma }^2}\right)$

Dropping constants:

$\hat{w}=\arg {\min }_w{\sum }_i(y_i-⟨w,x_i⟩{)}^2$

Regularization

Pure least squares can overfit, especially with $d\gtrsim n$ or collinear features.

Ridge regression (Tikhonov): penalize ${\ell }_2$ norm of weights. $\arg {\min }_w\Vert Aw-z{\Vert }_2^2+\lambda \Vert w{\Vert }_2^2$ Closed form: $\hat{w}=(A^{\top }A+\lambda I{)}^{-1}{A}^{\top }z$. Always invertible for $\lambda >0$.

Ridge shrinks weights toward zero, spreading influence across correlated features instead of letting one spike. The $+\lambda I$ adds a floor to the eigenvalues of $A^{\top }A$, which is why ill-conditioned problems become solvable.

Lasso: penalize ${\ell }_1$ norm, prefers sparse solutions. $\arg {\min }_w\Vert Aw-z{\Vert }_2^2+\lambda \Vert w{\Vert }_1$

The ${\ell }_1$ ball has corners on the axes. The squared-loss contours first touch it at a corner (with high probability), and a corner means some coordinates are exactly zero. That is why Lasso does feature selection while ridge does not.

See Regularization, L1 Regularization, L2 Regularization, Weight Decay.

Hyperparameter Selection

Pick $\lambda$ via a held-out validation set, or Cross Validation if no separate validation set is available. Often regularization is turned off at validation/test time: train with $\Vert Aw-z{\Vert }_2^2+\lambda \Vert w{\Vert }_2^2$ but score on $\Vert Aw-z{\Vert }_2^2$ alone.

From CS480 lec2.

Related

• Logistic Regression (classification analogue via logit transform)
• Gradient Descent (alternative to normal equations when $A^{\top }A$ is huge)
• MLE
• Cross Validation
• CS480