Supervised learning

The setting

Definition. In supervised learning we are given labelled examples $(x_1, y_1), \dots, (x_n, y_n)$, where each $x_i \in \mathbb{R}^d$ is a feature vector and $y_i$ its label, and we learn a function $f$ so that $f(x) \approx y$ on new data. If $y$ is a real number the task is regression; if $y$ is one of a few classes it is classification.

Training, validation and test data. We fit the model on the training set, choose settings (hyperparameters such as $k$ in k-NN or $\lambda$ in ridge regression) on a validation set, and report performance once on a test set that was never used for choices.

Exam point. A model is judged by its error on unseen data, not on the data it was trained on. A model with zero training error can still generalise badly.

Linear regression

Simple linear regression fits $\hat y = \beta_0 + \beta_1 x$ by minimising the sum of squared errors $\sum_i (y_i - \beta_0 - \beta_1 x_i)^2$. Setting the derivatives to zero gives

$\beta_1 = \frac{\sum_i (x_i - \bar x)(y_i - \bar y)}{\sum_i (x_i - \bar x)^2} = \frac{\operatorname{Cov}(x,y)}{\operatorname{Var}(x)}, \qquad \beta_0 = \bar y - \beta_1 \bar x .$

So the fitted line always passes through the point $(\bar x, \bar y)$.

Multiple linear regression stacks the inputs as rows of a matrix $X$ (with a column of 1s for the intercept) and fits $\hat y = X\beta$. The least-squares solution satisfies the normal equations

$X^\top X \beta = X^\top y \quad\Rightarrow\quad \beta = (X^\top X)^{-1} X^\top y \ \text{ when } X^\top X \text{ is invertible.}$

Ridge regression adds a penalty on large weights: minimise $\lVert y - X\beta\rVert^2 + \lambda \lVert\beta\rVert^2$ with $\lambda \ge 0$. The solution is

$\beta_{\text{ridge}} = (X^\top X + \lambda I)^{-1} X^\top y .$

Adding $\lambda I$ makes the matrix invertible for every $\lambda > 0$, shrinks the weights towards 0, and trades a little bias for lower variance.

Exam point. $\lambda = 0$ gives ordinary least squares; as $\lambda \to \infty$ the weights go to 0. Ridge never makes a weight exactly zero (that is what the L1 penalty, lasso, does).

Solved examples

Example 1: slope from data. Points $(1,2), (2,3), (3,5)$. Here $\bar x = 2$, $\bar y = 10/3$.

1. $\sum (x_i-\bar x)(y_i-\bar y) = (-1)(-4/3) + 0 + (1)(5/3) = 3$.
2. $\sum (x_i-\bar x)^2 = 1 + 0 + 1 = 2$.
3. $\beta_1 = 3/2 = 1.5$ and $\beta_0 = 10/3 - 1.5 \times 2 = 1/3$.
4. Fitted line: $\hat y = 1/3 + 1.5x$.

Example 2: ridge in one dimension. With one feature and no intercept, least squares gives $\beta = \frac{\sum x_i y_i}{\sum x_i^2}$ and ridge gives $\beta = \frac{\sum x_i y_i}{\sum x_i^2 + \lambda}$. If $\sum x_i y_i = 12$ and $\sum x_i^2 = 4$: least squares gives $3$, ridge with $\lambda = 2$ gives $12/6 = 2$. The penalty shrinks the weight.

Logistic regression

Definition. For two classes $y \in \{0,1\}$, logistic regression models the probability of class 1 as

$P(y=1 \mid x) = \sigma(w^\top x + b), \qquad \sigma(z) = \frac{1}{1+e^{-z}} .$

The sigmoid maps any real number into $(0,1)$; $\sigma(0) = 0.5$, and $\sigma(-z) = 1 - \sigma(z)$. We predict class 1 when $\sigma(w^\top x + b) \ge 0.5$, that is when $w^\top x + b \ge 0$, so the decision boundary is linear.

The weights are found by maximising the likelihood, equivalently minimising the cross-entropy (log) loss $-\sum_i [y_i \log p_i + (1-y_i)\log(1-p_i)]$. There is no closed form; gradient descent is used, and the loss is convex, so there is a single minimum.

Exam point. The log-odds are linear: $\log \frac{p}{1-p} = w^\top x + b$. Despite the name, logistic regression is a classification method.

Solved example

Example 3. $w = (2, -1)$, $b = -1$, $x = (1, 1)$. Then $z = 2 - 1 - 1 = 0$, so $P(y=1\mid x) = \sigma(0) = 0.5$: the point lies on the decision boundary.

k-nearest neighbours (k-NN)

Definition. To classify a new point, find the $k$ training points closest to it (usually by Euclidean distance) and take a majority vote of their labels (for regression, average their values). There is no training step: k-NN is a lazy, non-parametric method.

• Small $k$ (e.g. $k=1$): very flexible boundary, low bias, high variance, sensitive to noise.
• Large $k$: smoother boundary, higher bias, lower variance. $k = n$ always predicts the majority class.
• Features must be on comparable scales, because distance mixes them.

Example 4. Training points: A $(0,0)$ class +, B $(1,0)$ class +, C $(3,3)$ class −, D $(4,3)$ class −. Query $(1,1)$. Squared distances: A 2, B 1, C 8, D 13. With $k=3$ the nearest are B, A, C: two + and one −, so predict +.

Naive Bayes

Definition. Bayes' theorem gives $P(y \mid x) \propto P(y)\,P(x \mid y)$. Naive Bayes assumes the features are conditionally independent given the class:

$P(x_1,\dots,x_d \mid y) = \prod_{j=1}^{d} P(x_j \mid y), \qquad \hat y = \arg\max_y \; P(y)\prod_j P(x_j \mid y).$

The probabilities are estimated by counting in the training data. A zero count makes the whole product zero, so Laplace (add-one) smoothing is used: $P(x_j = v \mid y) = \frac{\text{count} + 1}{\text{class total} + \text{number of values}}$.

Example 5. Classes: Spam with prior 0.4, Ham with prior 0.6. $P(\text{"offer"} \mid \text{Spam}) = 0.5$, $P(\text{"offer"} \mid \text{Ham}) = 0.1$. For an email containing "offer": Spam score $0.4 \times 0.5 = 0.20$, Ham score $0.6 \times 0.1 = 0.06$. Normalising, $P(\text{Spam} \mid \text{offer}) = 0.20 / 0.26 \approx 0.77$. Predict Spam.

Linear discriminant analysis (LDA)

Definition. LDA assumes each class is Gaussian with its own mean $\mu_c$ but a shared covariance matrix $\Sigma$. Then the boundary between classes is linear. For two classes, Fisher's LDA projects onto the direction

$w \propto \Sigma^{-1}(\mu_1 - \mu_2),$

which maximises the separation of the projected means relative to the spread within each class.

Exam point. Shared covariance gives a linear boundary (LDA); separate covariances give a quadratic boundary (QDA).

Support vector machines (SVM)

Definition. For linearly separable data, the SVM finds the hyperplane $w^\top x + b = 0$ with the largest margin. With the scaling $y_i(w^\top x_i + b) \ge 1$ for every point, the margin width is $\frac{2}{\lVert w\rVert}$, so we

$\text{minimise } \tfrac12 \lVert w\rVert^2 \quad \text{subject to } y_i(w^\top x_i + b) \ge 1 .$

The points with $y_i(w^\top x_i + b) = 1$ lie on the margin and are the support vectors; only they determine the boundary. The soft-margin SVM allows some violations with a cost $C$ (large $C$: fewer violations, narrower margin). Kernels (polynomial, RBF) replace dot products $x_i^\top x_j$ by $K(x_i,x_j)$ to get non-linear boundaries.

Example 6. If the optimal $w = (3, 4)$, then $\lVert w\rVert = 5$ and the margin width is $2/5 = 0.4$.

Decision trees

Definition. A decision tree splits the data on one feature at a time, choosing the split that makes the child nodes as pure as possible. Two common impurity measures for a node with class proportions $p_1, \dots, p_k$:

$\text{Entropy } H = -\sum_c p_c \log_2 p_c, \qquad \text{Gini } = 1 - \sum_c p_c^2 .$

Information gain of a split = entropy of the parent − weighted average entropy of the children. The split with the largest gain is chosen. Deep trees overfit; limiting depth or pruning helps.

Example 7. A node with 4 positive and 4 negative examples has $H = 1$ bit and Gini $0.5$. A split sends (4+, 0−) left and (0+, 4−) right: both children have entropy 0, so the information gain is 1 bit, the best possible.

Example 8. Node with 6 positive, 2 negative: $p = (0.75, 0.25)$, Gini $= 1 - (0.5625 + 0.0625) = 0.375$.

Bias, variance and model complexity

Definition. The expected squared error of a model at a point splits into

$\text{error} = \text{bias}^2 + \text{variance} + \text{irreducible noise}.$

• Bias: error from wrong assumptions (a straight line for curved data). High bias means underfitting: high training and test error.
• Variance: sensitivity to the particular training set. High variance means overfitting: low training error, high test error.
• More complex models (deeper trees, smaller $k$, higher-degree polynomials, smaller $\lambda$) lower bias and raise variance.

Exam point. Regularisation (ridge, pruning, larger $k$) reduces variance at the cost of some bias. More training data reduces variance but not bias.

Cross-validation

k-fold cross-validation splits the data into $k$ equal folds. Each fold is used once as the validation set while the model trains on the other $k-1$; the $k$ validation errors are averaged. Each model is trained $k$ times. Leave-one-out (LOOCV) is the case $k = n$.