Part I · Foundations of supervised learning | hyperplanes and margins, the perceptron, logistic regression and cross-entropy, separability and regularisation, softmax, discriminant analysis and naive Bayes, confusion matrices, ROC and AUC, calibration, propensity scores | reading: James et al., ISLP, ch. 4; Hastie, Tibshirani & Friedman, ESL, ch. 4
Lecture 3 predicted numbers. Here we predict classes: malignant or benign, which digit, enrolled or not. The simplest classifiers draw a flat boundary, a line in two dimensions or a hyperplane in more, and assign a class according to which side a point falls on. This lecture builds three of them. The perceptron finds a separating boundary when one exists. Logistic regression, the workhorse, attaches a probability to each side and is fitted by maximum likelihood. Discriminant analysis and naive Bayes arrive at the same kind of boundary from the other direction, by modelling each class and applying Bayes' theorem. Then we ask how to judge a classifier, which turns out to be much more than counting mistakes.
By the end of this lecture you should be able to describe a linear classifier geometrically; run the perceptron and prove that it converges on separable data; write down logistic regression as a probability model, derive its loss and gradient, prove the loss is convex, and explain why separable data force regularisation; interpret logistic coefficients as odds ratios; extend to many classes with softmax; derive the linear boundary of discriminant analysis; read a confusion matrix, choose a threshold, and explain ROC curves, AUC and calibration; and estimate a propensity score and use it to adjust a causal comparison.
569 breast masses examined by fine-needle aspiration at the University of Wisconsin Hospitals: 212 malignant, 357 benign. From a digitised image of each sample, 30 features describe the cell nuclei: the mean, standard error and "worst" (largest) value of ten measurements such as radius, texture, area and the number of concave points on the nuclear boundary. Collected by W. H. Wolberg, W. N. Street and O. L. Mangasarian (Street, Wolberg & Mangasarian, 1993); UCI Machine Learning Repository; bundled with scikit-learn as load_breast_cancer. We code malignant as 1.
import numpy as np import pandas as pd from sklearn.datasets import load_breast_cancer bc = load_breast_cancer() X_all = pd.DataFrame(bc.data, columns=bc.feature_names) y_all = 1 - bc.target # scikit-learn codes benign as 1; we make malignant = 1 print(X_all.shape, ' malignant:', y_all.sum(), ' benign:', (1 - y_all).sum()) print(X_all[['mean radius', 'mean texture', 'worst concave points', 'worst area']].describe().loc[['mean', 'std', 'min', 'max']].round(3))
(569, 30) malignant: 212 benign: 357
mean radius mean texture worst concave points worst area
mean 14.127 19.290 0.115 880.583
std 3.524 4.301 0.066 569.357
min 6.981 9.710 0.000 185.200
max 28.110 39.280 0.291 4254.000
A linear classifier scores each point with a linear function and thresholds the score:
$$s(x)=w^\top x+b,\qquad\hat y=\begin{cases}1&s(x)\ge0\\0&s(x)<0.\end{cases}$$The decision boundary \(\{x:w^\top x+b=0\}\) is a hyperplane: a line when \(d=2\), a plane when \(d=3\). The weight vector \(w\) is perpendicular to it and points towards the class-1 side, and the score measures how far a point is from the boundary.
The signed distance from a point \(x\) to the hyperplane \(w^\top x+b=0\) is
$$\frac{w^\top x+b}{\|w\|}.$$For two points \(u,v\) on the hyperplane, \(w^\top(u-v)=0\), so \(w\) is orthogonal to every direction within it.
Let \(x_0\) be the foot of the perpendicular from \(x\), so \(x-x_0=tw/\|w\|\) for some \(t\), and \(|t|\) is the distance. Taking the dot product with \(w\):
$$w^\top x-w^\top x_0=t\|w\|,$$and \(w^\top x_0=-b\), so
$$t=(w^\top x+b)/\|w\|.\qquad\square$$Data are linearly separable if some hyperplane puts every class-1 point strictly on one side and every class-0 point on the other. The smallest distance from a point to that hyperplane is its margin. Separability is rarer than it sounds in low dimensions, where classes overlap, and more common than it sounds in high dimensions, a fact that will cause trouble in Section 3.
How far is the point \((3,4)\) from the line \(3x_1+4x_2-5=0\)?
The perceptron is the oldest learning algorithm in this course and the simplest that learns a boundary. Absorb the bias into the weights by appending a constant feature 1 to every \(x\), and code the labels as \(y=\pm1\). A point is misclassified when \(y\,w^\top x\le0\).
Start with \(w=0\). Repeatedly pass through the training points; whenever a point is misclassified, nudge \(w\) towards it:
$$\text{if }y_i\,w^\top x_i\le0:\qquad w\leftarrow w+y_ix_i.$$Stop when a full pass makes no mistakes.
Why does the update help? After it, \(y_iw^\top x_i\) increases by \(y_i^2\|x_i\|^2=\|x_i\|^2>0\): the boundary moves so that point \(i\) is less wrong. It might make other points more wrong, though, so it is not obvious that the process ever stops. It does, if the data can be separated.
Suppose \(\|x_i\|\le R\) for all \(i\), and some unit vector \(w^*\) separates the data with margin \(\gamma>0\):
$$y_i\,w^{*\top}x_i\ge\gamma$$for all \(i\). Then the perceptron makes at most \((R/\gamma)^2\) updates, whatever the order of the points.
Let \(w_k\) be the weights after \(k\) updates, with \(w_0=0\). Track two quantities.
Alignment grows linearly. Each update adds \(y_ix_i\), so
$$w^{*\top}w_{k}=w^{*\top}w_{k-1}+y_i\,w^{*\top}x_i\ge w^{*\top}w_{k-1}+\gamma.$$Hence \(w^{*\top}w_k\ge k\gamma\).
Length grows only like a square root.
$$\|w_k\|^2=\|w_{k-1}\|^2+2y_i\,w_{k-1}^\top x_i+\|x_i\|^2\le\|w_{k-1}\|^2+R^2,$$because the update happens only when \(y_iw_{k-1}^\top x_i\le0\). Hence \(\|w_k\|^2\le kR^2\).
By Cauchy–Schwarz,
$$k\gamma\le w^{*\top}w_k\le\|w_k\|\le\sqrt k\,R,$$so \(\sqrt k\le R/\gamma\). \(\square\)
The bound depends on the geometry, not on the number of points or the dimension: a wide margin relative to the data's spread means few mistakes. The same ratio \(R/\gamma\) reappears in the generalisation bounds of Lecture 6 and in support vector machines (Lecture 7), which choose the boundary with the widest margin on purpose.
All points lie within distance 1 of the origin and some separating direction achieves margin 0.1. At most how many updates can the perceptron make?
Handwritten zeros and ones are a good test: the digits look very different, so they may be separable in the 784-dimensional space of pixel intensities.
70,000 greyscale images of handwritten digits, 28×28 pixels, written by American high-school students and Census Bureau employees, assembled by Yann LeCun, Corinna Cortes and Christopher Burges from NIST databases (LeCun et al., 1998). We use Michael Nielsen's copy, which splits the 60,000 training images into 50,000 for training and 10,000 for validation, and keeps the standard 10,000 test images. Each image is a row of 784 numbers between 0 (white) and 1 (black).
import gzip, pickle with gzip.open('data/mnist.pkl.gz', 'rb') as f: (Xtr_m, ytr_m), (Xva_m, yva_m), (Xte_m, yte_m) = pickle.load(f, encoding='latin1') # 28x28 images as rows of 784 keep = (ytr_m == 0) | (ytr_m == 1) A, t = Xtr_m[keep], np.where(ytr_m[keep] == 1, 1, -1) # labels +1 for "1", -1 for "0" A = np.column_stack([A, np.ones(len(A))]) # a constant feature plays the role of the bias b w = np.zeros(A.shape[1]) for epoch in range(1, 11): mistakes = 0 for i in np.random.default_rng(epoch).permutation(len(A)): if t[i] * (A[i] @ w) <= 0: # misclassified (or on the boundary) w += t[i] * A[i] # the perceptron update mistakes += 1 print(f'epoch {epoch}: {mistakes} mistakes on {len(A)} training images') if mistakes == 0: break keep_te = (yte_m == 0) | (yte_m == 1) B = np.column_stack([Xte_m[keep_te], np.ones(keep_te.sum())]) print('test error on 0 vs 1:', np.mean(np.sign(B @ w) != np.where(yte_m[keep_te] == 1, 1, -1)))
epoch 1: 44 mistakes on 10610 training images epoch 2: 23 mistakes on 10610 training images epoch 3: 16 mistakes on 10610 training images epoch 4: 19 mistakes on 10610 training images epoch 5: 13 mistakes on 10610 training images epoch 6: 0 mistakes on 10610 training images test error on 0 vs 1: 0.0009456264775413711
After six passes the perceptron makes no mistakes on 10,610 training images, so these classes are linearly separable, and on the 2,115 test zeros and ones it misclassifies two. On data that are not separable, the perceptron never stops: it cycles forever. Drag one rose point deep into the sky cloud in the widget and press "run".
Frank Rosenblatt, a psychologist at the Cornell Aeronautical Laboratory, described the perceptron in 1958 and built it in hardware: the Mark I Perceptron had a 20×20 grid of photocells as its "retina", and its weights were potentiometers turned by electric motors. A US Navy press event that summer produced newspaper stories, including one in the New York Times, predicting machines that would walk, talk, see and be conscious. Albert Novikoff proved the convergence theorem in 1962. In 1969 Marvin Minsky and Seymour Papert's book Perceptrons proved that single-layer perceptrons cannot compute some simple functions, such as whether the number of active inputs is odd, and the field's funding and reputation collapsed for over a decade. The fix, stacking layers of perceptron-like units and training them with gradients, is Lecture 10.
The perceptron outputs a hard yes or no. Often we want a probability: a 51% chance of malignancy calls for a different response than a 99% chance. Logistic regression models the probability of class 1 as a smooth function of the score.
With labels \(y\in\{0,1\}\), the model is
$$P(Y=1\mid x)=\sigma(w^\top x+b),\qquad\sigma(s)=\frac1{1+e^{-s}}.$$The sigmoid (logistic function) \(\sigma\) squeezes any score into \((0,1)\), with \(\sigma(0)=\tfrac12\).
Inverting it, the score is the log-odds (logit):
$$\log\dfrac{p}{1-p}=w^\top x+b.$$So logistic regression is a linear model for the log-odds.
The decision boundary at probability \(\tfrac12\) is still the hyperplane \(w^\top x+b=0\); what is new is the graded confidence on either side, and a principled way to fit \(w\): maximum likelihood. Each label is a Bernoulli trial with success probability \(p_i=\sigma(w^\top x_i+b)\), with likelihood \(p_i^{y_i}(1-p_i)^{1-y_i}\). The negative log-likelihood, averaged over the data, is the cross-entropy loss (or log loss):
$$\mathcal L(w)=-\frac1n\sum_{i=1}^n\Big[y_i\log p_i+(1-y_i)\log(1-p_i)\Big].$$A confident wrong answer is punished heavily: predicting \(p=0.01\) for a malignant tumour costs \(-\log0.01\approx4.6\), while \(p=0.4\) costs only 0.92.
The maximum-likelihood fit puts the midpoint at 0.133 concave points and has log-likelihood −125.2; on this single feature it classifies 90.9% of patients correctly at the ½ threshold. Making the curve steeper makes it more decisive, which helps on points it gets right and costs a lot on points it gets wrong. The likelihood balances the two.
With an intercept absorbed into \(w\) and \(p_i=\sigma(w^\top x_i)\),
$$\nabla\mathcal L(w)=\frac1n\sum_i(p_i-y_i)\,x_i=\frac1nX^\top(p-y),$$ $$\nabla^2\mathcal L(w)=\frac1nX^\top DX,\quad D=\operatorname{diag}\big(p_i(1-p_i)\big).$$The Hessian is positive semi-definite, so \(\mathcal L\) is convex: every local minimum is global, and gradient descent and Newton's method behave well.
Two facts about the sigmoid: \(\sigma'(s)=\sigma(s)(1-\sigma(s))\), and \(1-\sigma(s)=\sigma(-s)\) (Exercise 2).
With \(s_i=w^\top x_i\), each term of the loss can be written
$$\log(1+e^{s_i})-y_is_i.$$Its derivative in \(s_i\) is \(\sigma(s_i)-y_i=p_i-y_i\), and by the chain rule \(\partial s_i/\partial w=x_i\), giving the gradient.
Differentiating \(p_i-y_i\) once more in \(s_i\) gives \(p_i(1-p_i)\), so the Hessian is
$$\frac1n\sum_ip_i(1-p_i)x_ix_i^\top.$$For any \(u\),
$$u^\top X^\top DXu=\sum_ip_i(1-p_i)(x_i^\top u)^2\ge0.\qquad\square$$The gradient has the same form as for least squares, \(X^\top(\text{prediction}-\text{label})\), and that is no coincidence: both are generalised linear models whose loss is a negative log-likelihood from an exponential family (Lecture 5). Unlike least squares there is no closed-form solution, so we iterate. Newton's method for logistic regression is called iteratively reweighted least squares, because each Newton step solves a weighted least-squares problem with weights \(p_i(1-p_i)\).
A logistic model gives a patient probability 0.8 of malignancy. What is the score \(w^\top x+b\) (the log-odds)?
Now use all 30 features. Train by plain gradient descent on 398 patients and test on 171, and watch the size of \(w\).
from sklearn.model_selection import train_test_split from sklearn.preprocessing import StandardScaler Xtr, Xte, ytr, yte = train_test_split(X_all.to_numpy(), y_all, test_size=0.3, stratify=y_all, random_state=0) sc = StandardScaler().fit(Xtr) Ztr = np.column_stack([np.ones(len(Xtr)), sc.transform(Xtr)]) # intercept + 30 standardised features Zte = np.column_stack([np.ones(len(Xte)), sc.transform(Xte)]) sigmoid = lambda s: 1 / (1 + np.exp(-s)) def nll(w, Z, y): # average cross-entropy (negative log-likelihood) p = np.clip(sigmoid(Z @ w), 1e-15, 1 - 1e-15) return -np.mean(y * np.log(p) + (1 - y) * np.log(1 - p)) w = np.zeros(Ztr.shape[1]) for step in range(1, 100_001): w -= 0.5 * Ztr.T @ (sigmoid(Ztr @ w) - ytr) / len(ytr) # gradient of the average NLL if step in (100, 1_000, 10_000, 100_000): err = np.mean((Zte @ w > 0) != yte) print(f'step {step:6d}: |w| = {np.linalg.norm(w):7.2f} train NLL {nll(w, Ztr, ytr):.4f} ' f'test NLL {nll(w, Zte, yte):.4f} test error {err:.3f}')
step 100: |w| = 2.67 train NLL 0.0606 test NLL 0.1075 test error 0.035 step 1000: |w| = 5.31 train NLL 0.0364 test NLL 0.1228 test error 0.047 step 10000: |w| = 12.73 train NLL 0.0196 test NLL 0.2374 test error 0.053 step 100000: |w| = 35.48 train NLL 0.0055 test NLL 0.5256 test error 0.047
The training loss keeps falling towards zero, the weights keep growing, and the test loss gets worse, more than four times worse than at step 100. The training patients are (nearly) linearly separable in 30 dimensions, and on separable data the likelihood has no maximum.
If some \(w_0\) separates the training data strictly (\(w_0^\top x_i>0\) when \(y_i=1\) and \(<0\) when \(y_i=0\)), then \(\mathcal L(cw_0)\to0\) as \(c\to\infty\), while \(\mathcal L(w)>0\) for every finite \(w\).
So no finite \(w\) minimises the loss.
For a class-1 point, \(p_i=\sigma(c\,w_0^\top x_i)\to1\) as \(c\to\infty\) because \(w_0^\top x_i>0\), so its loss \(-\log p_i\to0\); class-0 points are symmetric.
So the infimum of \(\mathcal L\) is 0. But every finite \(w\) gives every \(p_i\) strictly between 0 and 1, so every term, and hence \(\mathcal L(w)\), is strictly positive. \(\square\)
The algorithm is not malfunctioning: it is chasing a solution at infinity, becoming ever more certain, and certainty is what the test loss punishes. The fix is the one from Lecture 3: penalise large weights. Adding \(\frac\lambda2\|w\|^2\) to the loss restores a unique minimum. Scikit-learn's LogisticRegression does this by default, with \(C=1/(n\lambda)\), since it adds the penalty to the summed rather than the average loss.
from sklearn.linear_model import LogisticRegression for C in [0.01, 0.1, 1, 10]: # C = 1/lambda: smaller C, stronger L2 penalty lr = LogisticRegression(C=C, max_iter=5000).fit(sc.transform(Xtr), ytr) p = lr.predict_proba(sc.transform(Xte))[:, 1] print(f'C = {C:5}: |w| = {np.linalg.norm(lr.coef_):6.2f} test NLL {nll(np.r_[lr.intercept_, lr.coef_[0]], Zte, yte):.4f}' f' test error {np.mean((p > 0.5) != yte):.3f}')
C = 0.01: |w| = 0.79 test NLL 0.2025 test error 0.041 C = 0.1: |w| = 1.76 test NLL 0.1187 test error 0.029 C = 1: |w| = 3.67 test NLL 0.1069 test error 0.047 C = 10: |w| = 8.40 test NLL 0.1677 test error 0.053
In the unpenalised run, the test error barely changes (0.035 to 0.047) while the test log loss rises from 0.11 to 0.53. Why do the two measures disagree?
Because the model is linear in the log-odds, each coefficient has a clean meaning: increasing feature \(j\) by \(\Delta\) multiplies the odds of class 1 by \(e^{w_j\Delta}\), the odds ratio, holding the other features fixed (with the same caveats about "holding fixed" as in Lecture 3, Section 7).
two = ['worst concave points', 'worst area'] lr2 = LogisticRegression(C=1e6, max_iter=5000).fit(X_all[two], y_all) # essentially unpenalised b0, (b1, b2) = lr2.intercept_[0], lr2.coef_[0] print(f'log-odds of malignant = {b0:.3f} + {b1:.3f} * concave_pts + {b2:.5f} * area') print('odds ratio for +0.01 in worst concave points:', round(np.exp(0.01 * b1), 3)) print('odds ratio for +100 in worst area :', round(np.exp(100 * b2), 3))
log-odds of malignant = -14.788 + 47.918 * concave_pts + 0.01013 * area odds ratio for +0.01 in worst concave points: 1.615 odds ratio for +100 in worst area : 2.755
A patient has a predicted probability of exactly 0.5. Their worst concave points increase by 0.01, with worst area unchanged. Using the odds ratio 1.615, what is the new probability?
For \(K\) classes, give each class its own weight vector \(w_k\) and score \(s_k=w_k^\top x+b_k\), and turn the scores into probabilities with the softmax function.
The loss is again the negative log-likelihood,
$$-\frac1n\sum_i\log P(Y=y_i\mid x_i),$$the cross-entropy between the one-hot label and the predicted distribution.
With \(K=2\), softmax reduces to the sigmoid of the score difference.
For a single example with label \(y\) and predicted probabilities \(p=\operatorname{softmax}(s)\), the gradient of \(-\log p_y\) with respect to the scores is \(p-e_y\), where \(e_y\) is the one-hot vector of the label. Hence
$$\nabla_{w_k}=(p_k-\mathbf 1[y=k])\,x.$$Differentiating in \(s_k\):
$$-\mathbf 1[y=k]+e^{s_k}/\sum_je^{s_j}=p_k-\mathbf 1[y=k].$$Then \(\partial s_k/\partial w_k=x\). \(\square\)
This "prediction minus target" gradient is the last step of backpropagation in every neural-network classifier (Lecture 10).
import time soft = LogisticRegression(max_iter=200, C=1.0) # multinomial (softmax) regression on 10 classes t0 = time.time(); soft.fit(Xtr_m, ytr_m) print(f'fitted on {len(Xtr_m)} images in {time.time() - t0:.0f} s; weight matrix {soft.coef_.shape}') pred = soft.predict(Xte_m) print('test accuracy:', round(np.mean(pred == yte_m), 4)) cm = pd.crosstab(pd.Series(yte_m, name='true'), pd.Series(pred, name='predicted')) off = [(cm.loc[i, j], i, j) for i in range(10) for j in range(10) if i != j] print('most common confusions (count, true, predicted):', sorted(off, reverse=True)[:4])
fitted on 50000 images in 24 s; weight matrix (10, 784) test accuracy: 0.9246 most common confusions (count, true, predicted): [(np.int64(36), 5, 3), (np.int64(35), 2, 8), (np.int64(32), 7, 9), (np.int64(31), 5, 8)]
A linear model gets 92.5% of test digits right. Each class's weight vector has one entry per pixel, so it can be displayed as an image: where the weight is positive, ink there is evidence for that digit; where it is negative, ink there is evidence against.
The weight images look like blurry templates: the "0" weights reward ink on a ring and penalise ink in the centre, and the "1" weights reward a vertical stroke. A linear model can only compare an image with one fixed template per class, which is why it confuses 5 with 3 and 7 with 9, digits that share most of their strokes. Lecture 11's convolutional networks reach over 99% by learning local stroke detectors instead.
For a "7" that the model gives probability 0.6 of being a 7 and 0.3 of being a 9, the gradient of the loss with respect to the score \(s_9\) is and with respect to \(s_7\) it is .
Lecture 1 showed that the best possible classifier picks the class with the largest posterior probability, and that by Bayes' theorem this is the class maximising \(\pi_k\,p_k(x)\), prior times class density. Logistic regression models the posterior directly: it is discriminative. The alternative is generative: model each class's distribution \(p_k(x)\), estimate the priors \(\pi_k\), and apply Bayes' theorem.
Linear discriminant analysis (LDA) models each class as a multivariate normal with its own mean \(\mu_k\) and a shared covariance matrix \(\Sigma\).
Quadratic discriminant analysis lets each class have its own \(\Sigma_k\).
Naive Bayes assumes instead that, within each class, the features are independent, so
$$p_k(x)=\prod_jp_{kj}(x_j);$$Gaussian naive Bayes takes each \(p_{kj}\) to be a one-dimensional normal.
All parameters are estimated by class-wise sample means, variances and proportions: no optimisation is needed.
Under the LDA model with two classes, the log-odds of class 1 is a linear function of \(x\):
$$\log\frac{P(Y=1\mid x)}{P(Y=0\mid x)}=w^\top x+b,$$ $$w=\Sigma^{-1}(\mu_1-\mu_0),\qquad b=-\frac12\big(\mu_1^\top\Sigma^{-1}\mu_1-\mu_0^\top\Sigma^{-1}\mu_0\big)+\log\frac{\pi_1}{\pi_0}.$$So the posterior has exactly the logistic form of Definition 4.2.
With separate covariances (QDA) the log-odds is quadratic in \(x\).
The log of the normal density is
$$-\frac12(x-\mu_k)^\top\Sigma^{-1}(x-\mu_k)$$plus a constant that is the same for both classes (because \(\Sigma\) is shared). Expanding,
$$-\frac12x^\top\Sigma^{-1}x+\mu_k^\top\Sigma^{-1}x-\frac12\mu_k^\top\Sigma^{-1}\mu_k.$$In the difference
$$\log\pi_1p_1(x)-\log\pi_0p_0(x)$$the quadratic term \(x^\top\Sigma^{-1}x\) cancels, leaving \((\mu_1-\mu_0)^\top\Sigma^{-1}x\) plus constants, as claimed.
With different \(\Sigma_k\) the quadratic terms do not cancel. \(\square\)
So LDA and logistic regression produce the same kind of classifier, a linear log-odds, but estimate it differently. LDA uses the assumed normal shape to estimate fewer, more stable quantities; logistic regression assumes nothing about \(p_k(x)\) and only fits the boundary. A classic study by Ng and Jordan (2002) found that generative classifiers often win when training data are scarce, and discriminative ones win as data grow. Here is the comparison on the breast-cancer data, averaging over 200 random training subsets of each size.
from sklearn.naive_bayes import GaussianNB from sklearn.discriminant_analysis import LinearDiscriminantAnalysis rng = np.random.default_rng(0) models = {'naive Bayes': GaussianNB(), 'LDA': LinearDiscriminantAnalysis(), 'logistic': LogisticRegression(C=1.0, max_iter=5000)} for m in [10, 20, 40, 80, 160, 398]: errs = {k: [] for k in models} for rep in range(200 if m < 398 else 1): idx = rng.choice(len(Xtr), m, replace=False) if m < 398 else np.arange(len(Xtr)) if ytr[idx].min() == ytr[idx].max(): # need both classes present continue s = StandardScaler().fit(Xtr[idx]) for k, model in models.items(): model.fit(s.transform(Xtr[idx]), ytr[idx]) errs[k].append(np.mean(model.predict(s.transform(Xte)) != yte)) print(f'n = {m:3d}: ' + ' '.join(f'{k} {np.mean(v):.3f}' for k, v in errs.items()))
n = 10: naive Bayes 0.205 LDA 0.164 logistic 0.115 n = 20: naive Bayes 0.113 LDA 0.196 logistic 0.085 n = 40: naive Bayes 0.101 LDA 0.218 logistic 0.064 n = 80: naive Bayes 0.098 LDA 0.099 logistic 0.052 n = 160: naive Bayes 0.097 LDA 0.067 logistic 0.045 n = 398: naive Bayes 0.105 LDA 0.058 logistic 0.047
Here, penalised logistic regression wins at every size, and naive Bayes stops improving after about 40 patients: its independence assumption is badly wrong for features like radius, perimeter and area, which are almost deterministic functions of one another, so it keeps double-counting the same evidence. LDA does poorly at 20 and 40 patients, because it must estimate a 30×30 covariance matrix from only 20 or 40 points, which makes \(\Sigma\) nearly singular. Ng and Jordan compared with unpenalised logistic regression, which, as Section 3 showed, behaves badly on small separable samples; the penalty changes the story. Results like this depend on the data and on the details, which is a reason to run the experiment rather than trust the slogan.
LDA's decision boundary is ; QDA's is ; naive Bayes assumes the features are .
Naive Bayes on word counts was the first widely deployed machine-learning system many people met: the Bayesian spam filters of the late 1990s and early 2000s (Sahami et al., 1998; Paul Graham's "A Plan for Spam", 2002) computed \(P(\text{spam}\mid\text{words})\) by multiplying per-word likelihood ratios with a prior, and Lecture 13 builds one for sentiment. The two routes to a classifier are two factorisations of the same joint distribution, \(p(x,y)=p(y)\,p(x\mid y)=p(x)\,p(y\mid x)\). Generative models learn the first factorisation and can also generate data, handle missing features and use unlabelled examples; discriminative models learn only the part needed for prediction. Modern generative models (Lectures 16, 17a and 19) take the first route with far richer \(p(x\mid y)\).
The error rate treats all mistakes alike. In medicine, missing a cancer (a false negative) is usually far worse than a false alarm (a false positive) that leads to a further test. A classifier that outputs probabilities lets us choose the threshold to match those costs, and evaluation should describe performance at every threshold, not one.
At a threshold \(t\), predict positive when the score is at least \(t\).
Count true positives (TP), false negatives (FN), false positives (FP) and true negatives (TN). Then:
The ROC curve plots the true positive rate against the false positive rate as \(t\) moves from 1 to 0; the AUC is the area under it.
from sklearn.metrics import confusion_matrix, roc_auc_score, precision_score, recall_score final = LogisticRegression(C=1.0, max_iter=5000).fit(sc.transform(Xtr), ytr) score = final.predict_proba(sc.transform(Xte))[:, 1] for thr in [0.5, 0.2]: yhat = (score >= thr).astype(int) tn, fp, fn, tp = confusion_matrix(yte, yhat).ravel() print(f'threshold {thr}: TP {tp} FN {fn} FP {fp} TN {tn} | recall {recall_score(yte, yhat):.3f} ' f'precision {precision_score(yte, yhat):.3f} accuracy {np.mean(yhat == yte):.3f}') pos, neg = score[yte == 1], score[yte == 0] pairs = np.mean(pos[:, None] > neg[None, :]) + 0.5 * np.mean(pos[:, None] == neg[None, :]) print('AUC (scikit-learn):', round(roc_auc_score(yte, score), 4), ' P(random malignant scores above random benign):', round(pairs, 4))
threshold 0.5: TP 60 FN 4 FP 4 TN 103 | recall 0.938 precision 0.938 accuracy 0.953 threshold 0.2: TP 61 FN 3 FP 13 TN 94 | recall 0.953 precision 0.824 accuracy 0.906 AUC (scikit-learn): 0.9917 P(random malignant scores above random benign): 0.9917
Lowering the threshold from 0.5 to 0.2 catches one more malignant tumour (recall 0.938 to 0.953) at the price of nine more false alarms (precision 0.938 to 0.824). Whether that trade is worth it is a medical and human question, not a statistical one; what statistics can do is lay out the options, which is what the ROC curve does.
For continuous scores, the AUC equals the probability that a randomly chosen positive example scores higher than a randomly chosen negative one:
$$\mathrm{AUC}=P(S_+>S_-),$$with \(S_+\) and \(S_-\) drawn independently from the positive and negative score distributions.
Let \(F_+\) and \(F_-\) be the score distributions, with \(F_-\) having density \(f_-\).
At threshold \(t\), \(\mathrm{TPR}(t)=P(S_+>t)\) and \(\mathrm{FPR}(t)=P(S_->t)\).
As \(t\) decreases from \(+\infty\) to \(-\infty\), FPR increases from 0 to 1, with \(d\,\mathrm{FPR}=f_-(t)\,dt\) (up to orientation). So
$$\mathrm{AUC}=\int_0^1\mathrm{TPR}\;d\,\mathrm{FPR}=\int_{-\infty}^{\infty}P(S_+>t)\,f_-(t)\,dt=P(S_+>S_-),$$the last step by conditioning on \(S_-=t\) and using independence.
With ties, count each tie as one half, as the code does. \(\square\)
The code box checks this: both computations give 0.9917. AUC measures how well the scores rank patients, and it is unchanged by any increasing transformation of the scores. That makes it blind to calibration: whether patients given probability 0.3 really are malignant 30% of the time. On this test set the penalised model is well calibrated at the extremes (97 patients with average predicted probability 0.014, of whom 3.1% were malignant; 57 with average 0.995, all malignant), but with only 17 patients in between, the middle of the range cannot be checked. Lecture 5 introduces the scores that measure calibration directly.
At threshold 0.2 the confusion matrix is TP 61, FN 3, FP 13, TN 94. What is the precision?
A screening test has recall 0.95 and specificity 0.95, and 1% of the screened population has the disease. Roughly what fraction of positive results are true positives?
Logistic regression is still everywhere that a decision must be explained and audited. Credit scorecards are typically logistic regressions on binned features, partly because regulators require lenders to state the reasons for a refusal. Clinical risk scores often come from logistic models, and large advertising systems have run logistic regression on billions of sparse features to predict clicks (McMahan et al., 2013). Softmax is even more widespread: it is the final layer of nearly every neural-network classifier, and a large language model generating text computes a softmax over its whole vocabulary, tens of thousands of tokens, at every step, trained with exactly the cross-entropy loss of this lecture.
Lecture 3 tried to recover the effect of the NSW job-training program from observational data by regression adjustment. A different strategy uses a classifier. Predict, from the covariates, whether each person enrolled. The fitted probability is the propensity score, \(e(x)=P(T=1\mid X=x)\).
Among people with the same propensity score, treatment is independent of the covariates:
$$T\perp X\mid e(X).$$Consequently, if treatment is unconfounded given \(X\) (all common causes of treatment and outcome are measured), it is also unconfounded given the single number \(e(X)\).
It suffices to show
$$P(T=1\mid X,e(X))=P(T=1\mid e(X)).$$The left side is \(P(T=1\mid X)=e(X)\), since \(e(X)\) is a function of \(X\). For the right side, by the tower property,
$$P(T=1\mid e(X))=\mathbb E\big[P(T=1\mid X)\,\big|\,e(X)\big]=\mathbb E[e(X)\mid e(X)]=e(X).$$They agree.
The second claim is in Rosenbaum & Rubin (1983), Theorem 3. \(\square\)
Instead of matching people on 13 covariates, we can compare people with similar propensity scores, or reweight the comparison group so that its distribution of \(e(X)\) matches the treated group's: a control with score \(e\) gets weight \(e/(1-e)\), the odds of treatment.
nsw = pd.read_csv('data/nsw_mixtape.csv'); cps = pd.read_csv('data/cps_mixtape.csv') obs = pd.concat([nsw[nsw.treat == 1], cps], ignore_index=True) obs = obs.assign(age2=obs.age ** 2, educ2=obs.educ ** 2, u74=(obs.re74 == 0) * 1.0, u75=(obs.re75 == 0) * 1.0, educ_re74=obs.educ * obs.re74) covs = ['age', 'age2', 'educ', 'educ2', 'marr', 'nodegree', 'black', 'hisp', 're74', 're75', 'u74', 'u75', 'educ_re74'] Zp = StandardScaler().fit_transform(obs[covs]) e = LogisticRegression(C=1e6, max_iter=20_000).fit(Zp, obs.treat).predict_proba(Zp)[:, 1] # propensity score t1, y1 = obs.treat.to_numpy() == 1, obs.re78.to_numpy() print('propensity score, treated: median', round(np.median(e[t1]), 3), ' controls: median', f'{np.median(e[~t1]):.5f}') print('controls with e > 0.1:', np.sum(e[~t1] > 0.1), 'of', np.sum(~t1)) w0 = e[~t1] / (1 - e[~t1]) # reweight controls to look like the treated att = y1[t1].mean() - np.sum(w0 * y1[~t1]) / w0.sum() print(f'inverse-propensity-weighted effect on the treated: {att:.0f} dollars (experiment: 1794)')
propensity score, treated: median 0.424 controls: median 0.00010 controls with e > 0.1: 229 of 15992 inverse-propensity-weighted effect on the treated: 1614 dollars (experiment: 1794)
The propensity model exposes the problem the naive comparison hid. The median control has a propensity score of 0.0001: nothing like the participants. Only 229 of the 15,992 survey respondents look even remotely like them (score above 0.1). Reweighting the comparison group by the odds of treatment gives an effect of $1,614, close to the experimental $1,794 and better than regression adjustment's $1,137. The weights put almost all their mass on those few hundred comparable controls, which is both the strength of the method and its fragility: the estimate rests on a small, effectively re-selected sample.
Most survey respondents have propensity scores near 0. What does that tell you?
A propensity score model is judged by different standards from a prediction model. The goal is balance between the reweighted groups and good overlap, not accuracy; a model that predicts treatment perfectly is a disaster, because it says no comparable controls exist. Machine-learning classifiers (boosted trees, Lecture 8) are now often used to estimate propensity scores, combined with an outcome model in doubly robust estimators that are consistent if either model is right (Robins, Rotnitzky & Zhao, 1994). Double/debiased machine learning (Lecture 3) is one such estimator. Every one of them still rests on the untestable assumption that the measured covariates capture all confounding.
Next: Lecture 5 steps back to ask what a loss function really encodes, compares squared, absolute, quantile, cross-entropy and hinge losses, introduces proper scoring rules, and puts the bias–variance trade-off on a precise footing.
\(x_1\): \(y\,w^\top x_1=0\le0\), so update: \(w=(2,1)\). \(x_2\): \(-1\cdot(-2+1)=1>0\), correct. \(x_3\): \(1\cdot(1+1)=2>0\), correct. A second pass makes no mistakes. The boundary is \(2x+1=0\), i.e. \(x=-0.5\).
\(\sigma(-s)=\frac1{1+e^s}=\frac{e^{-s}}{e^{-s}+1}=1-\frac1{1+e^{-s}}\). Differentiating \((1+e^{-s})^{-1}\) gives \(\frac{e^{-s}}{(1+e^{-s})^2}=\sigma(s)\cdot\frac{e^{-s}}{1+e^{-s}}=\sigma(s)(1-\sigma(s))\). Solving \(p=1/(1+e^{-s})\) gives \(e^{-s}=(1-p)/p\), so \(s=\log\frac p{1-p}\).
\(-\log\sigma(s)=\log(1+e^{-s})\) and \(-\log(1-\sigma(s))=\log(1+e^s)\). So the term is \(y\log(1+e^{-s})+(1-y)\log(1+e^{s})\), and \(\log(1+e^{-s})=\log(1+e^s)-s\) gives \(\log(1+e^s)-ys\). With \(\tilde y=2y-1\): for \(y=1\) the term is \(\log(1+e^{-s})\), for \(y=0\) it is \(\log(1+e^{s})\); both are \(\log(1+e^{-\tilde ys})\). This "margin" form is the one Lecture 5 compares with other classification losses.
\(w=\Sigma^{-1}(\mu_1-\mu_0)=2\), \(b=-\tfrac12(4-0)+0=-2\). Log-odds \(2x-2\), zero at \(x=1\): the Bayes threshold. Here LDA's model is exactly right, so its boundary is the optimal one.
Recall \(61/64=0.953\); precision \(61/74=0.824\); specificity \(94/107=0.879\); F1 \(=2(0.824)(0.953)/(0.824+0.953)\approx0.884\).
\(g(S_+)>g(S_-)\) if and only if \(S_+>S_-\), so \(P(S_+>S_-)\) is unchanged. Example: a well-calibrated model and the same model with every probability replaced by its square root; the ranking is identical, but the second claims, say, 0.71 where the truth is 0.5.
Suppose \(w_1x_1+w_2x_2+b\) were positive on \((0,0),(1,1)\) and negative on \((0,1),(1,0)\). Then \(b>0\) and \(w_1+w_2+b>0\), while \(w_2+b<0\) and \(w_1+b<0\). Adding the last two gives \(w_1+w_2+2b<0\), but adding the first two gives \(w_1+w_2+2b>0\): a contradiction. With the extra feature, \(s=x_1+x_2-2x_1x_2-0.5\) is \(-0.5,-0.5\) on the first class and \(+0.5,+0.5\) on the second. Choosing features is how linear models become non-linear (Lecture 3, Section 4); learning them is how neural networks do it.
\(\mathbb E\big[TY/e(X)\big]=\mathbb E\big[TY(1)/e(X)\big]=\mathbb E\Big[\mathbb E[T\mid X]\,\mathbb E[Y(1)\mid X]/e(X)\Big]=\mathbb E\big[\mathbb E[Y(1)\mid X]\big]=\mathbb E[Y(1)]\), using unconfoundedness to factor the conditional expectation and \(\mathbb E[T\mid X]=e(X)\). The positivity condition \(e(X)>0\) is needed to divide; as \(e(X)\to0\) the weights explode, which is the overlap problem.
class_weight='balanced', which multiplies each malignant patient's loss by \(n/(2n_1)\) and each benign patient's by \(n/(2n_0)\). How do recall and precision at threshold 0.5 change, and how is this related to moving the threshold?
Upweighting the minority class pushes its predicted probabilities up, so more patients cross 0.5: recall rises and precision falls, much as lowering the threshold does. For a well-specified model, reweighting the classes is approximately equivalent to shifting the threshold (it changes the intercept by roughly the log of the weight ratio), but it also changes the fitted slopes slightly, because the loss now emphasises different patients.
Each project uses this lecture's methods and public data, and has a clear result.
Data. Breast cancer: W. N. Street, W. H. Wolberg, O. L. Mangasarian, "Nuclear feature extraction for breast tumor diagnosis", Proc. SPIE 1905, 861–870 (1993); UCI Machine Learning Repository, "Breast Cancer Wisconsin (Diagnostic)", doi:10.24432/C5DW2B (CC BY 4.0). MNIST: Y. LeCun, L. Bottou, Y. Bengio, P. Haffner, "Gradient-based learning applied to document recognition", Proceedings of the IEEE 86(11), 2278–2324 (1998); copy from M. Nielsen, Neural Networks and Deep Learning (2015), github.com/mnielsen/neural-networks-and-deep-learning. NSW and CPS samples: see Lecture 3.
every number in the text and widgets is computed in verify_L04.py; code-box outputs are pasted from actual runs