Machine Learning · Lecture 4

Lecture 4
Linear Methods II: Classification

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

Cartoon: a fence between two flocksTwo kinds of dots, filled and hollow, with a straight fence between them. One stick figure holding a fence post says: a straight fence keeps them apart. The other points at a hollow dot on the wrong side and says: and when one wanders over, tell me how sure you are. A straight fence divides them. And when one wanders over,tell me how sure you are.
A linear classifier draws a boundary; logistic regression also says how confident it is on each side
In this lecture
  1. Drawing a line between classes
  2. The perceptron
  3. Logistic regression
  4. More than two classes: softmax regression
  5. Generative classifiers: discriminant analysis and naive Bayes
  6. Evaluating a classifier
  7. Propensity scores: classification for causal inference
  8. Summary, exercises, projects, reading

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.

1 — Drawing a line between classes

data — Wisconsin diagnostic breast cancer

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.

code — the data
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.

proposition 4.1 — the score measures distance

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.

spot check 4.1

How far is the point \((3,4)\) from the line \(3x_1+4x_2-5=0\)?

Use \(|w^\top x+b|/\|w\|\) with \(w=(3,4)\), \(b=-5\).
\(|9+16-5|/5=20/5=4\). The point is on the positive side, the side \(w\) points to.

2 — The perceptron

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\).

definition 4.1 — the perceptron algorithm

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.

The perceptron, one update at a time

Sky points are class +1, rose points class −1. The amber arrow is \(w\) (its first two coordinates) and the line is the boundary; ringed points are currently misclassified. Drag points, or choose a class and tap empty space to add one.

theorem 4.2 — perceptron convergence (Novikoff, 1962)

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.

spot check 4.2

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?

\((R/\gamma)^2\).
\((1/0.1)^2=100\). Halving the margin quadruples the bound.

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.

data — MNIST handwritten digits

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).

code — a perceptron for 0 versus 1
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".

history — the perceptron, its hype and its winter

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.

3 — Logistic regression

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.

definition 4.2 — logistic regression

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.

Fitting a sigmoid by hand

All 569 patients, one feature: the worst (largest) number of concave points on a cell nucleus. Malignant patients are plotted along the top, benign along the bottom (with a little vertical jitter). The sky curve is \(P(\text{malignant}\mid x)\). Adjust its midpoint (where it crosses ½) and its steepness, and watch the log-likelihood.

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.

theorem 4.3 — gradient and convexity of the logistic loss

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)\).

spot check 4.3

A logistic model gives a patient probability 0.8 of malignancy. What is the score \(w^\top x+b\) (the log-odds)?

\(\log\frac{p}{1-p}\) with \(p=0.8\).
\(\log4\approx1.386\). Odds of 4 to 1. A score of 0 is even odds; each extra unit of score multiplies the odds by \(e\approx2.72\).

Separable data: when the maximum does not exist

Now use all 30 features. Train by plain gradient descent on 398 patients and test on 171, and watch the size of \(w\).

code — unpenalised logistic regression, by gradient descent
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.

proposition 4.4 — no maximum-likelihood estimate on separable data

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.

code — L2-penalised logistic regression
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
spot check 4.4

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?

What happens to \(-\log p\) for a misclassified patient as \(\|w\|\) grows?
As \(\|w\|\to\infty\) with a fixed direction, the boundary barely moves but every probability is pushed to 0 or 1. A misclassified patient with \(p\to0\) costs \(-\log p\to\infty\). If you need probabilities, you need the penalty.

Reading the coefficients

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).

code — odds ratios with two features
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
spot check 4.5

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?

Probability 0.5 is odds 1. Multiply the odds by 1.615, then convert back with \(p=\text{odds}/(1+\text{odds})\).
\(1.615/2.615\approx0.618\). Odds ratios multiply odds, not probabilities: the same odds ratio moves a probability of 0.5 much more than a probability of 0.99.

4 — More than two classes: softmax regression

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.

definition 4.3 — softmax (multinomial logistic) regression $$P(Y=k\mid x)=\operatorname{softmax}(s)_k=\frac{e^{s_k}}{\sum_{j=1}^Ke^{s_j}},\qquad k=1,\dots,K.$$

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.

proposition 4.5 — the softmax gradient

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.$$
$$-\log p_y=-s_y+\log\sum_je^{s_j}.$$

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).

code — softmax regression on all ten digits
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.

What softmax regression sees

Top: the ten weight vectors as images (sky = positive weight, rose = negative). Below: a test digit and the model's probabilities. Twenty of these 120 test digits are ones the model gets wrong.

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.

spot check 4.6

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 .

Use \(p_k-\mathbf 1[y=k]\).
Gradient descent subtracts the gradient, so it raises \(s_7\) (by an amount proportional to 0.4) and lowers \(s_9\) (proportional to 0.3): push up the right answer, push down the competitors in proportion to how much probability they stole.

5 — Generative classifiers: discriminant analysis and naive Bayes

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.

definition 4.4 — linear discriminant analysis and naive Bayes

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.

theorem 4.6 — LDA has a linear boundary

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.

code — generative versus discriminative as the training set grows
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.

spot check 4.7

LDA's decision boundary is ; QDA's is ; naive Bayes assumes the features are .

Look at Theorem 4.6 and Definition 4.4.
The naive Bayes assumption is about features within a class. Features can still be strongly related overall because they depend on the class, as tumour size measurements do.
bayes — naive Bayes, the spam filter, and two routes to one posterior

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)\).

6 — Evaluating a classifier

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.

definition 4.5 — confusion matrix and its rates

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.

code — thresholds, precision, recall and AUC
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.

Choosing a threshold

The 171 test patients' predicted probabilities of malignancy, split by their true diagnosis (rose malignant, sky benign). Move the threshold; everyone to its right is predicted malignant. The ROC curve on the right traces every threshold at once, and the dot marks yours.

theorem 4.7 — what the AUC measures

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.

spot check 4.8

At threshold 0.2 the confusion matrix is TP 61, FN 3, FP 13, TN 94. What is the precision?

\(\mathrm{TP}/(\mathrm{TP}+\mathrm{FP})\).
\(61/74\approx0.824\). Of the patients flagged as malignant, about 82% are.
spot check 4.9

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?

Per 10,000 people: 100 have the disease, 95 are caught; 9,900 do not, and 5% of them, 495, test positive.
\(95/(95+495)\approx0.16\). With rare positives, precision collapses even for an accurate test. This is the base-rate effect of Bayes' theorem, and it is why AUC and accuracy can look excellent on imbalanced data while most alarms are false.
big picture — logistic regression and softmax in 2026

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.

7 — Propensity scores: classification for causal inference

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)\).

proposition 4.8 — the propensity score balances covariates (Rosenbaum & Rubin, 1983)

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.

code — a propensity score for the NSW program
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.

spot check 4.10

Most survey respondents have propensity scores near 0. What does that tell you?

What weight \(e/(1-e)\) does a control with \(e=0.0001\) receive?
Causal comparisons need overlap (also called positivity): for each kind of treated person, some untreated people of the same kind. Proposition 4.8 helps only where overlap exists. When propensity scores pile up at 0 and 1, no adjustment method can manufacture comparable people that are not in the data.
causal — good classifiers, bad propensity scores

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.

8 — Summary, exercises, projects, reading

summary

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.

exercises 4
  1. Run the perceptron by hand on three points, each with a constant feature appended: \(x_1=(2,1)\) with \(y=+1\), \(x_2=(-1,1)\) with \(y=-1\), \(x_3=(0.5,1)\) with \(y=+1\). Visit them in order, starting from \(w=0\). Where is the final boundary?

    \(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\).

  2. Show that \(\sigma(-s)=1-\sigma(s)\), \(\sigma'(s)=\sigma(s)(1-\sigma(s))\), and that the inverse of \(\sigma\) is the logit \(\log\frac{p}{1-p}\).

    \(\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}\).

  3. Show that one term of the logistic loss, \(-y\log\sigma(s)-(1-y)\log(1-\sigma(s))\), equals \(\log(1+e^{s})-ys\), and that with labels coded \(\pm1\) it equals \(\log(1+e^{-ys})\).

    \(-\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.

  4. For one-dimensional classes \(X\mid Y=0\sim N(0,1)\) and \(X\mid Y=1\sim N(2,1)\) with equal priors, compute the LDA log-odds from Theorem 4.6 and recover the Bayes classifier of Lecture 1, Example 1.2.

    \(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.

  5. At threshold 0.2 (TP 61, FN 3, FP 13, TN 94), compute recall, precision, specificity and F1.

    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\).

  6. Prove that the AUC is unchanged if every score \(s\) is replaced by \(g(s)\) for a strictly increasing \(g\). Give an example of two models with the same AUC whose probabilities differ greatly in calibration.

    \(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.

  7. Explain why the perceptron cannot learn the XOR pattern: points \((0,0)\) and \((1,1)\) in one class, \((0,1)\) and \((1,0)\) in the other. Then show that adding the feature \(x_1x_2\) makes the data separable.

    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.

  8. Show that inverse probability weighting identifies the average treated outcome: if \(T\perp Y(1)\mid X\) and \(0<e(X)<1\), then \(\mathbb E\big[TY/e(X)\big]=\mathbb E[Y(1)]\), where \(Y=Y(1)\) when \(T=1\).

    \(\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.

  9. In code, refit the 30-feature logistic regression with 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.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Generative versus discriminative, 25 years on

question
Does Ng and Jordan's finding, that naive Bayes beats logistic regression with little data, survive when logistic regression is penalised and tuned?
data
Thirty or more binary classification datasets from OpenML or the UCI repository, including the ones Ng and Jordan used.
method
Learning curves (error against training size, averaged over many random subsets) for naive Bayes, LDA, unpenalised and penalised logistic regression; record where, if anywhere, the curves cross.
outcome
A careful replication with a clear answer to a question every textbook repeats. Replications of this kind are welcomed by reproducibility venues.

2. Is a risk model calibrated for everyone?

question
Do logistic risk models fitted on a national health survey give calibrated probabilities across age, sex and region, or only on average?
data
The CDC Behavioral Risk Factor Surveillance System (BRFSS) or NHANES, public files.
method
Fit models for an outcome such as diagnosed diabetes; compute reliability diagrams and calibration errors by subgroup; test whether recalibrating within subgroups helps.
outcome
Evidence on subgroup calibration, a question that matters for fairness (Lecture 13) and for clinical use.

3. How separable is MNIST?

question
For each of the 45 pairs of digits, are the training images linearly separable, and how does the perceptron's mistake count relate to the margin?
data
MNIST, as in this lecture.
method
Run the perceptron to convergence (or a cap) for every pair; estimate margins with a linear SVM (Lecture 7); compare mistake counts with the \((R/\gamma)^2\) bound and with test error.
outcome
A "separability map" of the digits, a striking figure, and an empirical look at how loose the Novikoff bound is in practice.

Reading and sources

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