Full search page →

PR 03 · Linear Models for Regression and Classification

Pattern RecognitionIntermediate23 minUpdated Nov 5, 2026

Needs: PR 02 · Density Estimation and Bayesian Learning, ML 01C · Numerical Computation and Gradient Checks

Navigate: this page and this track: Navigate: this page and this track
Explore this chapter 1 interactive experiment

Fit polynomial basis functions with ridge regression and separate training error from recovery of the underlying function.

What you’ll learn

  • Read the geometry of a linear discriminant (weight vector, bias, signed distance) and the pitfalls of building multiclass classifiers from two-class ones.
  • Derive least squares, ridge regression and their Bayesian interpretation, and see why least squares is a fragile classifier.
  • Derive Fisher’s linear discriminant and connect it to Gaussian LDA from PR 01.
  • Train a perceptron, prove its convergence theorem, and explain why it can stop at any separating line.
  • Fit logistic regression by Newton’s method, and explain why separable data push its weights to infinity.
  • Derive the maximum-margin SVM, its Lagrangian dual and its support vectors, and see all of these methods as different losses on the same linear score.

The big picture

Linear models are the first serious classifiers in every pattern-recognition course, and they remain the first thing to try on a new representation. If a straight boundary separates two categories in feature space, a large nonlinear classifier may add cost without useful accuracy. If a linear baseline fails, its errors help identify missing features or nonlinear structure. In modern deep learning, the final layer of almost every classifier is a linear model on learned features, and “how well does a linear classifier do on these features?” is the standard test of a representation.

A linear score is f(x)=w⊤ϕ(x)+bf(x)=w^\top\phi(x)+b. The feature map ϕ\phi might contain raw intensities, squared values, gradients or a frozen neural embedding. “Linear” refers to the parameters ww and bb, not necessarily to the original measurement xx: with ϕ(x)=(x,x2)\phi(x)=(x,x^2) a linear model draws a curved boundary in xx. This chapter follows Duda, Hart and Stork [1, Ch. 5], Bishop [2, Ch. 3–4, 7] and Theodoridis and Koutroumbas [3, Ch. 3], with Hastie et al. [4] for the statistical view. Kernels, which make ϕ\phi implicit and very rich, are the topic of PR 04.

Linear discriminant functions

Plain version. A two-class linear classifier is a flat cut through feature space: a line in 2-D, a plane in 3-D, a hyperplane in general. The weight vector says which way the cut faces; the bias says where it sits.

Precise version. For two classes, decide c1c_1 if g(x)=w⊤x+b>0g(x)=w^\top x+b>0 and c0c_0 otherwise. The decision boundary g(x)=0g(x)=0 is a hyperplane HH. Three facts follow from the geometry of linear classifiers [1, 2, 3]:

  • ww is normal to HH: for two points xa,xbx_a,x_b on HH, w⊤(xa−xb)=0w^\top(x_a-x_b)=0.
  • The signed distance from any xx to HH is r=g(x)/∥w∥r=g(x)/\|w\|. So g(x)g(x) is proportional to how far, and on which side, xx lies.
  • For w≠0w\ne0, the ordinary distance from the origin to HH is ∣b∣/∥w∥|b|/\|w\|. Its signed distance under the convention above is b/∥w∥b/\|w\|; the closest point on HH is −bw/∥w∥2-b w/\|w\|^2. The bias shifts the plane without rotating it.

It is convenient to absorb the bias by augmenting the input with a constant: x~=(x,1)\tilde x=(x,1) and w~=(w,b)\tilde w=(w,b), so that g(x)=w~⊤x~g(x)=\tilde w^\top\tilde x. We do this silently in code. With labels y∈{−1,+1}y\in\{-1,+1\}, a sample is correctly classified exactly when its functional margin y g(x)y\,g(x) is positive. Every method below can be written in terms of this quantity.

More than two classes. Two-class machines can be combined in two obvious ways: one-versus-rest (KK classifiers, each separating one class from all others) and one-versus-one (K(K−1)/2K(K-1)/2 classifiers, one per pair, followed by voting). Both can leave regions of input space where the votes are ambiguous [2, Section 4.1.2]. The clean solution is a linear machine: one discriminant per class, gk(x)=wk⊤x+bkg_k(x)=w_k^\top x+b_k, and assign xx to the class with the largest score. Its decision regions are always convex and simply connected, because if xax_a and xbx_b both have gkg_k largest, so does every point between them (each gjg_j is linear along the segment). The Gaussian LDA of PR 01, multiclass logistic regression and the final layer of a neural network are all linear machines.

Least squares and ridge regression

Plain version. For predicting a quantity, choose the weights that make the squared prediction errors as small as possible. If there are too many weights for the data, also penalize large weights.

Precise version. Let row nn of the design matrix Φ∈RN×M\Phi\in\mathbb R^{N\times M} be the feature vector ϕ(xn)⊤\phi(x_n)^\top, including a constant coordinate for the intercept, and let t∈RNt\in\mathbb R^N hold the targets. Least squares minimizes

L(w)=12∥Φw−t∥22,\mathcal L(w)=\frac12\|\Phi w-t\|_2^2 ,

whose gradient Φ⊤(Φw−t)\Phi^\top(\Phi w-t) vanishes at the normal equations Φ⊤Φw=Φ⊤t\Phi^\top\Phi w=\Phi^\top t. Forming Φ⊤Φ\Phi^\top\Phi squares the 2-norm condition number for a full-column-rank design, and explicitly inverting it is unnecessary; QR- or SVD-based solvers (np.linalg.lstsq) handle near-dependent columns more reliably. Assuming independent Gaussian noise of common variance on the targets, this objective equals the negative log-likelihood up to a positive scale and an additive constant, so least squares is the maximum-likelihood estimate (PR 02). The noise assumption explains the statistical interpretation; it does not make squared error suitable for every target.

Ridge regression [8] adds a penalty λ2∥w∥2\tfrac\lambda2\|w\|^2, giving

(Φ⊤Φ+λI) w=Φ⊤t.(\Phi^\top\Phi+\lambda I)\,w=\Phi^\top t .

The matrix on the left is invertible for any λ>0\lambda>0, even when M>NM>N. Usually the intercept is excluded from the penalty. Feature scaling matters, because the same penalty has different effects on coordinates measured in different units; fit scaling statistics on training data only.

A Bayesian connection

With a Gaussian prior w∼N(0,α−1I)w\sim\mathcal N(0,\alpha^{-1}I) (precision α\alpha) and Gaussian noise of precision β\beta, the posterior over weights is Gaussian with covariance and mean [2, Section 3.3]

S=(αI+βΦ⊤Φ)−1,m=βSΦ⊤t.S=(\alpha I+\beta\Phi^\top\Phi)^{-1}, \qquad m=\beta S\Phi^\top t .

For a new feature vector ϕ∗\phi_*, the predictive distribution is

p(t∗∣x∗,D)=N(t∗∣m⊤ϕ∗, β−1+ϕ∗⊤Sϕ∗).p(t_*\mid x_*,D)= \mathcal N\bigl(t_*\mid m^\top\phi_*,\ \beta^{-1}+\phi_*^\top S\phi_*\bigr).

The first variance term is observation noise; the second expresses uncertainty about the weights, which is larger along feature directions that the training data rarely visited. The posterior mean mm equals the ridge solution with λ=α/β\lambda=\alpha/\beta: ridge is a MAP estimate, the same story as the Gaussian mean in PR 02.

Least squares for classification

Plain version. You can treat class labels as numbers (+1+1 and −1-1, or one-hot vectors) and fit them with least squares. It is fast and has a closed form, but it is the wrong tool: it punishes points for being too correct.

Precise version. For KK classes, encode the targets as one-hot vectors tn∈{0,1}Kt_n\in\{0,1\}^K and fit a linear machine g(x)=W⊤x~g(x)=W^\top\tilde x by least squares, W=(X~⊤X~)−1X~⊤TW=(\tilde X^\top\tilde X)^{-1}\tilde X^\top T, then classify by the largest output. For two classes with suitable target values (N/N1N/N_1 for class 1 and −N/N0-N/N_0 for class 0), the least-squares direction is exactly Fisher’s direction derived in the next section [2, Section 4.1.5], so the method is not unreasonable.

It has two well-known failure modes:

  1. Sensitivity to points far on the correct side. Squared error penalizes g(x)=5g(x)=5 for a target of +1+1 as severely as g(x)=−3g(x)=-3. Figure 1 adds twenty red points that are correctly classified but far away; least squares rotates its boundary to reduce their “error” and starts misclassifying blue points. Logistic regression barely moves.
  2. Masking with three or more classes. When classes lie roughly along a line, the output for the middle class can be dominated everywhere by one of its neighbors, so the middle class is never predicted [4, Section 4.2].

In probabilistic terms, the Gaussian noise model behind least squares is simply wrong for binary targets. The remedy is to use a loss designed for classification, which the rest of the chapter does.

Two panels. Left: two compact classes; least-squares and logistic-regression boundaries both separate them. Right: twenty extra red points far to the right; the least-squares boundary rotates to almost horizontal and cuts through the blue class, while the logistic boundary is unchanged.
Figure 1 — Least squares versus logistic regression. Adding red points that are already correctly classified (right) pulls the least-squares boundary (green) into the blue class; logistic regression (dashed) is unaffected.

Fisher’s linear discriminant

Plain version. Project all points onto one line and look at the two classes’ 1-D histograms. A good line makes the class means far apart and each class narrow. Fisher’s direction is the line that maximizes this ratio.

Precise version. Fisher [5] proposed choosing a projection z=w⊤xz=w^\top x that maximizes the separation of the projected class means relative to the spread within each class. Let mk=1Nk∑n∈ckxnm_k=\frac1{N_k}\sum_{n\in c_k}x_n be the class means. The projected means are w⊤mkw^\top m_k, and the projected within-class scatter of class kk is ∑n∈ck(w⊤xn−w⊤mk)2=w⊤Skw\sum_{n\in c_k}(w^\top x_n-w^\top m_k)^2=w^\top S_kw, with Sk=∑n∈ck(xn−mk)(xn−mk)⊤S_k=\sum_{n\in c_k}(x_n-m_k)(x_n-m_k)^\top. Fisher’s criterion is

J(w)=(w⊤m1−w⊤m0)2w⊤S0w+w⊤S1w=w⊤SBww⊤SWw,J(w)=\frac{(w^\top m_1-w^\top m_0)^2}{w^\top S_0w+w^\top S_1w} =\frac{w^\top S_Bw}{w^\top S_Ww},

where

SB=(m1−m0)(m1−m0)⊤,SW=S0+S1S_B=(m_1-m_0)(m_1-m_0)^\top,\qquad S_W=S_0+S_1

are the between-class and within-class scatter matrices. JJ does not depend on the length of ww, only on its direction.

Derivation. Setting the gradient of the ratio to zero gives

(w⊤SBw) SWw=(w⊤SWw) SBw.(w^\top S_Bw)\,S_Ww=(w^\top S_Ww)\,S_Bw .

Both bracketed terms are scalars. Moreover SBw=(m1−m0) [(m1−m0)⊤w]S_Bw=(m_1-m_0)\,\bigl[(m_1-m_0)^\top w\bigr] always points along m1−m0m_1-m_0. Hence SWw∝m1−m0S_Ww\propto m_1-m_0, and since only the direction matters,

w⋆∝SW−1(m1−m0).w^\star\propto S_W^{-1}(m_1-m_0).

If SWS_W is a multiple of the identity (isotropic, uncorrelated classes), Fisher’s direction is just the mean difference. Otherwise SW−1S_W^{-1} rotates it away from directions in which the classes are spread out. Figure 2 shows the effect for two elongated, correlated classes: projecting on the mean difference gives heavily overlapping histograms (J=0.70J=0.70), while Fisher’s direction separates them well (J=3.18J=3.18).

Left: two elongated correlated Gaussian classes with the mean-difference direction (gray, nearly horizontal) and the Fisher direction (black, tilted). Middle and right: histograms of the projections, heavily overlapping for the mean difference and well separated for Fisher.
Figure 2 — Two correlated classes projected onto the mean difference (middle, J = 0.70) and onto Fisher's direction (right, J = 3.18). Per-class covariances were used for S_W; with equal class sizes this only rescales J.

Relationship with Gaussian LDA. Fisher’s criterion makes no distributional assumption; it is a criterion for a representation. Yet its direction coincides with the Gaussian LDA direction Σ−1(μ1−μ0)\Sigma^{-1}(\mu_1-\mu_0) of PR 01 when SWS_W is (proportional to) the pooled within-class covariance. The two differ only in the threshold: Fisher leaves the cut point on the projected axis open, while Gaussian LDA fixes it from the class means and priors. So “LDA” is used for both. (In topic modelling, LDA also means latent Dirichlet allocation, which is unrelated.) Fisher projections do not by themselves provide calibrated probabilities.

More than two classes. With KK classes and overall mean mm, define SW=∑kSkS_W=\sum_kS_k and SB=∑kNk(mk−m)(mk−m)⊤S_B=\sum_kN_k(m_k-m)(m_k-m)^\top. The projection W∈Rd×(K−1)W\in\mathbb R^{d\times(K-1)} that maximizes the multiclass criterion is spanned by the leading eigenvectors of SW−1SBS_W^{-1}S_B [1, 2]. Because SBS_B is a sum of KK rank-one terms constrained by the overall mean, its rank is at most K−1K-1, so Fisher can produce at most K−1K-1 useful features. This is the supervised dimensionality reduction of PR 05.

Code: Fisher’s direction

Code · Python · 21 lines
import numpy as np
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

rng = np.random.default_rng(2)
cov = np.array([[3.0, 2.4], [2.4, 2.4]])
X0 = rng.multivariate_normal([0, 0], cov, 200)
X1 = rng.multivariate_normal([2, 0], cov, 200)
m0, m1 = X0.mean(0), X1.mean(0)
S_W = np.cov(X0.T) + np.cov(X1.T)       # within-class scatter (per-class covariances)
w = np.linalg.solve(S_W, m1 - m0)                          # Fisher direction

def J(v):                       # Fisher criterion for two classes
    return (v @ (m1 - m0)) ** 2 / (v @ S_W @ v)

lda = LinearDiscriminantAnalysis().fit(np.vstack([X0, X1]), np.repeat([0, 1], 200))
cos = w @ lda.coef_[0] / np.linalg.norm(w) / np.linalg.norm(lda.coef_[0])
angles = np.linspace(0, np.pi, 3601)
best = max(J(np.array([np.cos(a), np.sin(a)])) for a in angles)
print(f"J(mean difference) = {J(m1 - m0):.4f}, J(Fisher) = {J(w):.4f}, "
      f"grid maximum = {best:.4f}")
print(f"cosine between Fisher direction and LDA coef_: {cos:.6f}")

The closed form attains the grid maximum (J=3.1841J=3.1841), more than four times the mean-difference value (0.69530.6953), and its direction agrees with scikit-learn’s Gaussian LDA coefficients to six decimals (cosine 1.0000001.000000).

The perceptron

Plain version. Start with any line. Go through the training points; whenever one is on the wrong side, nudge the line towards classifying it correctly. If the classes can be separated by a line, this process is guaranteed to stop.

Precise version. Rosenblatt’s perceptron [6] uses labels yn∈{−1,+1}y_n\in\{-1,+1\} and augmented features x~n\tilde x_n. It minimizes the perceptron criterion

JP(w)=−∑n∈Myn w⊤x~n,J_P(w)=-\sum_{n\in\mathcal M}y_n\,w^\top\tilde x_n ,

where M\mathcal M is the set of misclassified samples (those with ynw⊤x~n≤0y_nw^\top\tilde x_n\le0). Each term is non-negative, and JP=0J_P=0 exactly when every sample is correctly classified. Stochastic gradient descent on one misclassified sample at a time gives the update

w←w+η ynx~n.w\leftarrow w+\eta\,y_n\tilde x_n .

With ww initialized at zero, the learning rate η>0\eta>0 only rescales ww and does not change the sequence of decisions, so η=1\eta=1 is common. The IP 13 perceptron section presents the same rule in the language of image patterns and connects it to multilayer networks.

Convergence theorem. Suppose the data are linearly separable with margin γ>0\gamma>0: some unit vector uu satisfies ynu⊤x~n≥γy_nu^\top\tilde x_n\ge\gamma for all nn. Let R=max⁡n∥x~n∥R=\max_n\|\tilde x_n\|. Then the perceptron (started at w0=0w_0=0) makes at most (R/γ)2(R/\gamma)^2 updates. The proof takes three lines. After tt updates:

  • each update adds ynx~n⊤u≥γy_n\tilde x_n^\top u\ge\gamma to w⊤uw^\top u, so wt⊤u≥tγw_t^\top u\ge t\gamma;
  • each update happens on a mistake, where ynw⊤x~n≤0y_nw^\top\tilde x_n\le0, so ∥wt∥2=∥wt−1∥2+2ynwt−1⊤x~n+∥x~n∥2≤∥wt−1∥2+R2\|w_{t}\|^2=\|w_{t-1}\|^2+2y_nw_{t-1}^\top\tilde x_n+\|\tilde x_n\|^2\le\|w_{t-1}\|^2+R^2, hence ∥wt∥2≤tR2\|w_t\|^2\le tR^2;
  • by Cauchy–Schwarz, tγ≤wt⊤u≤∥wt∥≤t Rt\gamma\le w_t^\top u\le\|w_t\|\le\sqrt t\,R, so t≤R2/γ2t\le R^2/\gamma^2.

The bound does not depend on the number of samples or the dimension, only on how “fat” the gap between the classes is relative to the data’s size.

Limitations. If the classes overlap, the perceptron never stops; the weights keep cycling (variants that keep the best weights seen so far are a common practical fix). Even when it converges, it stops at the first separating hyperplane it reaches, which depends on initialization and data order (Figure 3, left). And its score is not a probability. In terms of losses, the perceptron uses max⁡(0,−y g(x))\max(0,-y\,g(x)), which is zero for any correct classification, however marginal. Both logistic regression and the SVM fix this by asking for more than “just barely correct”.

Code: perceptron updates versus the bound

Code · Python · 35 lines
import numpy as np
from sklearn.svm import SVC

rng = np.random.default_rng(1)
X = np.vstack([rng.normal([-1.0, -0.7], 0.6, (30, 2)),
               rng.normal([1.0, 0.7], 0.6, (30, 2))])
y = np.r_[-np.ones(30), np.ones(30)]
Phi = np.c_[X, np.ones(len(X))]          # augmented features (bias as last weight)

def perceptron(Phi, y, rng, max_epochs=1000):
    w, updates = np.zeros(Phi.shape[1]), 0
    for epoch in range(max_epochs):
        errors = 0
        for i in rng.permutation(len(y)):
            if y[i] * (w @ Phi[i]) <= 0:  # misclassified or on the boundary
                w += y[i] * Phi[i]        # learning rate 1 (scale is irrelevant)
                errors += 1
        updates += errors
        if errors == 0:
            return w, updates
    return w, updates

runs = [perceptron(Phi, y, np.random.default_rng(s)) for s in range(200)]
updates = np.array([u for _, u in runs])
print(f"updates over 200 random orders: mean {updates.mean():.1f}, "
      f"max {updates.max()}")
print("all runs separate the data:",
      all(np.all(np.sign(Phi @ w) == y) for w, _ in runs))

# convergence bound (R / gamma)^2, with gamma from the max-margin separator
svm = SVC(kernel="linear", C=1e6).fit(X, y)
u = np.r_[svm.coef_[0], svm.intercept_[0]]
gamma = np.min(y * (Phi @ u)) / np.linalg.norm(u)
R = np.max(np.linalg.norm(Phi, axis=1))
print(f"bound (R/gamma)^2 = {(R / gamma) ** 2:.1f}")

Over 200 random presentation orders the perceptron needs on average 2.72.7 updates (at most 1010), and every run separates the data. The worst-case bound is 691691: it is a guarantee, not a prediction. The bound needs a valid margin γ\gamma; we take it from a hard-margin SVM (the subject of the SVM section below). Because the SVM does not penalize the bias, the true maximum margin in the augmented space may be slightly larger, which would give a slightly tighter bound.

Logistic regression

Plain version. Instead of a hard yes/no, output a probability by squashing the linear score through an S-shaped curve. Fit the weights so that the probabilities assigned to the true labels are as high as possible.

Precise version. With labels y∈{0,1}y\in\{0,1\}, binary logistic regression [7] models

P(y=1∣x)=σ(w⊤x~),σ(z)=11+e−z.P(y=1\mid x)=\sigma\bigl(w^\top\tilde x\bigr), \qquad \sigma(z)=\frac1{1+e^{-z}} .

The score w⊤x~w^\top\tilde x is the log-odds ln⁡P(y=1∣x)P(y=0∣x)\ln\frac{P(y=1\mid x)}{P(y=0\mid x)}. This form is not arbitrary. PR 01 showed that for Gaussian classes with a shared covariance the posterior is exactly σ(w⊤x+w0)\sigma(w^\top x+w_0) with w=Σ−1(μ1−μ0)w=\Sigma^{-1}(\mu_1-\mu_0); the same holds for many other class-conditional families. Logistic regression keeps the functional form of that posterior but fits ww directly, with d+1d+1 parameters instead of the 2d+d(d+1)/2+12d+d(d+1)/2+1 of the Gaussian model. Ng and Jordan [18] analysed this generative–discriminative trade-off (PR 02).

Training. The negative log-likelihood of the Bernoulli model is the cross-entropy

E(w)=−∑n=1N[ynln⁡pn+(1−yn)ln⁡(1−pn)],pn=σ(w⊤x~n).E(w)=-\sum_{n=1}^N\Bigl[y_n\ln p_n+(1-y_n)\ln(1-p_n)\Bigr],\qquad p_n=\sigma(w^\top\tilde x_n).

Because σ′(z)=σ(z)(1−σ(z))\sigma'(z)=\sigma(z)(1-\sigma(z)), its gradient and Hessian are remarkably simple [2, Section 4.3]:

∇E=∑n(pn−yn) x~n=X~⊤(p−y),H=X~⊤R X~,R=diag⁡(pn(1−pn)).\nabla E=\sum_n(p_n-y_n)\,\tilde x_n=\tilde X^\top(p-y), \qquad H=\tilde X^\top R\,\tilde X,\quad R=\operatorname{diag}\bigl(p_n(1-p_n)\bigr).

The gradient has the same “prediction minus target, times input” form as least squares. HH is positive semidefinite, so EE is convex and has no spurious local minima. Newton’s method, w←w−H−1∇Ew\leftarrow w-H^{-1}\nabla E, can be rewritten as a weighted least-squares problem with weights RR that change every iteration: iteratively reweighted least squares (IRLS). In code, compute losses from logits with a stable formula such as ln⁡(1+ez)=\ln(1+e^z)= np.logaddexp(0, z) rather than taking logarithms of rounded probabilities.

Separable data. If a hyperplane separates the training classes, scaling ww up pushes every pnp_n closer to its label, so EE keeps decreasing towards zero and the unregularized solution does not exist: ∥w∥→∞\|w\|\to\infty. In practice, always regularize, e.g. add λ2∥w∥2\tfrac\lambda2\|w\|^2 (scikit-learn’s C is 1/λ1/\lambda). Remarkably, how the weights diverge is well defined: plain gradient descent on separable data converges in direction to the maximum-margin SVM solution [19], which the Modern view returns to.

Multiclass. Replace the sigmoid with the softmax P(y=k∣x)=exp⁡(wk⊤x~)/∑jexp⁡(wj⊤x~)P(y=k\mid x)=\exp(w_k^\top\tilde x)/\sum_j\exp(w_j^\top\tilde x) and the cross-entropy with its KK-class version. This is a linear machine with probabilistic outputs, and it is exactly the last layer plus loss of a standard neural classifier. Probability outputs are not automatically calibrated under label noise or distribution shift (PR 01).

Code: Newton’s method (IRLS) and separable data

Code · Python · 27 lines
import numpy as np
from sklearn.linear_model import LogisticRegression

rng = np.random.default_rng(0)
X = np.vstack([rng.normal(-1, 1, (100, 2)), rng.normal(1, 1, (100, 2))])
y = np.r_[np.zeros(100), np.ones(100)]
Phi = np.c_[np.ones(len(X)), X]

def nll(w, lam):
    z = Phi @ w
    # log(1 + e^z) - y z, written stably with logaddexp
    return np.sum(np.logaddexp(0, z) - y * z) + 0.5 * lam * np.sum(w[1:] ** 2)

# Newton's method (iteratively reweighted least squares)
lam, w = 1.0, np.zeros(3)
for it in range(20):
    p = 1 / (1 + np.exp(-(Phi @ w)))
    grad = Phi.T @ (p - y) + lam * np.r_[0, w[1:]]
    H = Phi.T @ (Phi * (p * (1 - p))[:, None]) + lam * np.diag([0, 1, 1])
    step = np.linalg.solve(H, grad)
    w -= step
    if np.linalg.norm(step) < 1e-10:
        break
sk = LogisticRegression(C=1 / lam, tol=1e-10, max_iter=1000).fit(X, y)
print(f"Newton converged in {it + 1} iterations, loss {nll(w, lam):.4f}")
print("Newton:      ", np.round(w, 4))
print("scikit-learn:", np.round(np.r_[sk.intercept_, sk.coef_[0]], 4))

Newton’s method converges in 88 iterations to the same weights as scikit-learn, (0.0777,1.7205,1.5300)(0.0777, 1.7205, 1.5300) for (intercept, w1w_1, w2w_2). The penalty excludes the intercept, matching scikit-learn’s convention.

The next snippet runs plain gradient descent on unregularized logistic loss for data that a line through the origin separates. It tracks the weight norm and the cosine between ww and the max-margin direction.

Code · Python · 20 lines
import numpy as np
from sklearn.svm import LinearSVC

rng = np.random.default_rng(1)
X = np.vstack([rng.normal([2.0, 1.0], 0.6, (40, 2)),
               rng.normal([-2.0, -1.0], 0.6, (40, 2))])
y = np.r_[np.ones(40), -np.ones(40)]              # separable through the origin

# max-margin direction without bias (hard margin approximated by large C)
svm = LinearSVC(fit_intercept=False, loss="hinge", C=1e4, max_iter=200000).fit(X, y)
u = svm.coef_[0] / np.linalg.norm(svm.coef_[0])

w, lr = np.zeros(2), 0.1
for t in range(1, 100001):
    m = y * (X @ w)
    grad = -(X * (y / (1 + np.exp(m)))[:, None]).mean(0)   # logistic loss gradient
    w -= lr * grad
    if t in (10, 100, 1000, 10000, 100000):
        print(f"step {t:6d}: ||w|| = {np.linalg.norm(w):6.2f}, "
              f"cos(w, SVM) = {w @ u / np.linalg.norm(w):.5f}")

The norm grows without bound but only slowly (0.680.68 after 10 steps, 8.648.64 after 10510^5), while the cosine with the SVM direction creeps from 0.870.87 to 0.980.98. This is the logarithmically slow convergence to the max-margin direction predicted by Soudry et al. [19].

Support vector machines: maximum margin

Plain version. Among all lines that separate the classes, pick the one with the widest empty “street” around it. Only the points on the edges of the street matter; move any other point (without crossing the street) and the answer does not change.

Precise version. Use labels yn∈{−1,+1}y_n\in\{-1,+1\} and score f(x)=w⊤x+bf(x)=w^\top x+b (bias kept separate here). For a separating hyperplane, the distance of xnx_n to the boundary is ynf(xn)/∥w∥y_nf(x_n)/\|w\|. Since (w,b)(w,b) and (cw,cb)(cw,cb) define the same plane, fix the scale so that the closest points satisfy ynf(xn)=1y_nf(x_n)=1 (the canonical form). The margin on each side is then 1/∥w∥1/\|w\| and the street has width 2/∥w∥2/\|w\|. Maximizing it is equivalent to the convex quadratic program [9, 10]

min⁡w,b 12∥w∥2subject toyn(w⊤xn+b)≥1,n=1,…,N.\min_{w,b}\ \frac12\|w\|^2 \quad\text{subject to}\quad y_n(w^\top x_n+b)\ge1,\quad n=1,\ldots,N .

Lagrangian and dual. Introduce multipliers an≥0a_n\ge0, one per constraint:

L(w,b,a)=12∥w∥2−∑nan[yn(w⊤xn+b)−1].\mathcal L(w,b,a)=\frac12\|w\|^2-\sum_n a_n\bigl[y_n(w^\top x_n+b)-1\bigr].

Setting ∂L/∂w=0\partial\mathcal L/\partial w=0 and ∂L/∂b=0\partial\mathcal L/\partial b=0 gives

w=∑nanyn xn,∑nanyn=0.w=\sum_n a_ny_n\,x_n,\qquad \sum_n a_ny_n=0 .

Substituting back eliminates ww and bb and leaves the dual problem

max⁡a ∑nan−12∑n∑manamynym xn⊤xmsubject toan≥0,  ∑nanyn=0.\max_{a}\ \sum_n a_n-\frac12\sum_n\sum_m a_na_my_ny_m\,x_n^\top x_m \quad\text{subject to}\quad a_n\ge0,\ \ \sum_n a_ny_n=0 .

Three consequences matter [2, 11]:

  • Support vectors. The Karush–Kuhn–Tucker conditions include complementary slackness, an[ynf(xn)−1]=0a_n\bigl[y_nf(x_n)-1\bigr]=0. So an>0a_n>0 only for points exactly on the margin. These are the support vectors; all other points have an=0a_n=0 and can be removed without changing the solution. The bias follows from any support vector ss: b=ys−w⊤xsb=y_s-w^\top x_s (average over all of them for numerical stability).
  • Sparsity of the prediction. f(x)=∑n∈Sanyn xn⊤x+bf(x)=\sum_{n\in\mathcal S}a_ny_n\,x_n^\top x+b depends only on support vectors S\mathcal S.
  • Only inner products. The data appear in the dual and in the prediction only through inner products xn⊤xmx_n^\top x_m. Replacing them with a kernel k(xn,xm)k(x_n,x_m) gives a nonlinear SVM without ever computing ϕ\phi. That is the kernel trick, developed in PR 04.

Soft margin and the hinge loss. Real classes overlap, so the constraints cannot all hold. Cortes and Vapnik [10] added slack variables ξn≥0\xi_n\ge0, constraints ynf(xn)≥1−ξny_nf(x_n)\ge1-\xi_n, and a penalty C∑nξnC\sum_n\xi_n. At the optimum ξn=max⁡(0,1−ynf(xn))\xi_n=\max(0,1-y_nf(x_n)), so the soft-margin SVM is equivalent to the unconstrained problem

min⁡w,b 12∥w∥2+C∑nmax⁡(0, 1−ynf(xn)).\min_{w,b}\ \frac12\|w\|^2+C\sum_n\max\bigl(0,\ 1-y_nf(x_n)\bigr).

The second term is the hinge loss: zero for points beyond the margin, linear inside it and on the wrong side. In the dual the only change is a box constraint 0≤an≤C0\le a_n\le C. So a linear SVM is “ridge-regularized hinge-loss minimization”, directly comparable to regularized logistic regression. The roles of CC, kernel bandwidth and feature scaling, and the fact that an SVM score is not a probability, are treated in PR 04.

Left: six different perceptron separating lines through the gap between two clusters, from six random data orders. Right: the single hard-margin SVM line with its two dashed margin lines and three circled support vectors; margin width 1.60.
Figure 3 — Left: the perceptron stops at whichever separating line it reaches first (six random orders). Right: the hard-margin SVM picks the unique line with the widest margin; only the three circled support vectors determine it.

Code: the dual in practice

This check fits a (nearly) hard-margin linear SVM and verifies the dual relations numerically: w=∑nanynxnw=\sum_na_ny_nx_n, ∑nanyn=0\sum_na_ny_n=0, and ynf(xn)=1y_nf(x_n)=1 on the support vectors.

Code · Python · 19 lines
import numpy as np
from sklearn.svm import SVC

rng = np.random.default_rng(7)
X = np.vstack([rng.normal([-1.5, -1.0], 0.6, (30, 2)),
               rng.normal([1.5, 1.0], 0.6, (30, 2))])
y = np.r_[-np.ones(30), np.ones(30)]

svm = SVC(kernel="linear", C=1e6).fit(X, y)          # huge C ~ hard margin
alpha_y = svm.dual_coef_[0]                          # alpha_n * y_n for SVs
w_dual = alpha_y @ svm.support_vectors_              # w = sum_n alpha_n y_n x_n
f = X @ svm.coef_[0] + svm.intercept_[0]

print("support vectors:", len(svm.support_), "of", len(y))
print("w from dual:", np.round(w_dual, 4), " coef_:", np.round(svm.coef_[0], 4))
print("sum_n alpha_n y_n =", round(float(alpha_y.sum()), 8))
print("y f(x) on support vectors:", np.round(y[svm.support_] * f[svm.support_], 4))
print("smallest y f(x) over all points:", round(float(np.min(y * f)), 4))
print("margin width 2/||w|| =", round(2 / np.linalg.norm(svm.coef_[0]), 4))

Only 33 of the 6060 points are support vectors (the circled points in Figure 3). The weight vector rebuilt from the dual coefficients matches coef_ exactly, the dual coefficients sum to zero, the support vectors sit at yf(x)≈1y f(x)\approx1 (to solver tolerance), no point is inside the margin, and the margin width is 1.601.60. scikit-learn’s SVC wraps LIBSVM [16]; for large sparse problems, LinearSVC and LogisticRegression(solver="liblinear") use LIBLINEAR [14], and stochastic sub-gradient solvers such as Pegasos [15] scale to very large datasets.

One picture: linear classifiers as losses

Plain version. All the methods in this chapter score a point with the same linear function. They differ in how much they charge for each value of the margin y g(x)y\,g(x): nothing once correct (perceptron), nothing once safely correct (SVM), a smoothly decreasing amount (logistic), or a parabola centred at exactly 11 (least squares).

Precise version. With labels y∈{−1,+1}y\in\{-1,+1\} and margin m=y g(x)m=y\,g(x), each method minimizes a (possibly regularized) average of a surrogate loss φ(m)\varphi(m) that stands in for the non-convex zero-one loss 1[m≤0]\mathbb 1[m\le0] (Figure 4):

MethodLoss φ(m)\varphi(m)Behaviour
Perceptronmax⁡(0,−m)\max(0,-m)zero for any correct point; scale-free, so w=0w=0 is a trivial minimizer
Hinge (SVM)max⁡(0,1−m)\max(0,1-m)zero beyond the margin; sparse solutions (support vectors)
Logisticln⁡(1+e−m)\ln(1+e^{-m})smooth, never exactly zero; gives probabilities
Squared(1−m)2=(y−g(x))2(1-m)^2=(y-g(x))^2penalizes m>1m>1: “too correct” points pull the boundary
Plot of five loss functions against the margin m: the zero-one step, perceptron loss max(0, -m), hinge max(0, 1 - m), logistic log2(1 + exp(-m)) and squared (1 - m)^2, which rises again for m greater than 1.
Figure 4 — Surrogate losses as functions of the margin m = y f(x). The logistic loss is scaled by 1/ln 2 so that it passes through (0, 1). Only the squared loss increases for m > 1, which explains Figure 1.

Which surrogates lead to the Bayes-optimal classifier when there is enough data? Bartlett, Jordan and McAuliffe [12] answered this precisely: a convex surrogate is classification-calibrated (minimizing its expected value yields the Bayes decision sign⁡(2η(x)−1)\operatorname{sign}(2\eta(x)-1), with η(x)=P(y=1∣x)\eta(x)=P(y=1\mid x)) if and only if it is differentiable at 00 with φ′(0)<0\varphi'(0)\lt0. Hinge, logistic, squared and exponential losses all qualify; the perceptron loss does not. They also relate the excess surrogate risk to the excess classification risk. Rosasco et al. [13] compared the convergence rates implied by different convex losses and concluded that, for classification, the hinge loss converges about as fast as the logistic loss and much faster than the square loss. The losses still differ in what they estimate: minimizing the expected logistic loss pointwise gives g(x)=ln⁡η(x)1−η(x)g(x)=\ln\frac{\eta(x)}{1-\eta(x)}, so its scores are log-odds (probabilities after a sigmoid), whereas the pointwise minimizer of the expected hinge loss is sign⁡(2η(x)−1)\operatorname{sign}(2\eta(x)-1), which carries no probability information. That is why SVM scores need separate calibration.

Code: compare linear classifiers on digits

The built-in digits dataset (8×8 images, 10 classes) requires no download. This is a single reproducible hold-out demonstration, not a benchmark ranking. Every scaler is fitted inside a pipeline, on training data only.

Code · Python · 25 lines
from sklearn.datasets import load_digits
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from sklearn.linear_model import LogisticRegression, Perceptron, RidgeClassifier
from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC

X, y = load_digits(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(
    X, y, test_size=0.25, stratify=y, random_state=7)
models = {
    "least squares (ridge)": make_pipeline(StandardScaler(), RidgeClassifier(alpha=1.0)),
    "perceptron": make_pipeline(StandardScaler(),
                                Perceptron(max_iter=1500, random_state=7)),
    "logistic": make_pipeline(StandardScaler(),
                              LogisticRegression(C=1, max_iter=1500)),
    "linear SVM": make_pipeline(StandardScaler(),
                                LinearSVC(C=0.1, max_iter=20000, random_state=7)),
    "Gaussian LDA": LinearDiscriminantAnalysis(solver="lsqr", shrinkage="auto"),
}
for name, model in models.items():
    model.fit(Xtr, ytr)
    print(f"{name:22s} test accuracy: {accuracy_score(yte, model.predict(Xte)):.4f}")

On this split, logistic regression reaches 97.1%97.1\%, the linear SVM 96.4%96.4\%, the perceptron 95.1%95.1\%, and ridge-regularized least squares and shrinkage LDA 94.7%94.7\% each. All five are linear machines on the same 64 pixels; the differences come from the losses and regularization alone. Changing regularization after seeing these test results would turn this test set into a validation set. A real model-selection study needs a separate validation split or cross-validation inside the training partition (PR 09).

Modern view

Linear classifiers have not been replaced by deep learning; they have moved to the top of it. Three lines of recent work explain why they still matter, and the classic survey literature remains useful for the methods themselves.

Surveys and solvers. Burges’s tutorial [11] remains the most readable derivation of SVMs, from VC-dimension motivation through the dual and kernels. Cervantes et al. [17] survey SVM classification as of 2020: variants, applications, and challenges such as training cost on large datasets, class imbalance and model selection. On the computational side, LIBLINEAR [14] made linear SVMs and logistic regression with millions of sparse features routine, LIBSVM [16] is the reference kernel-SVM implementation behind scikit-learn’s SVC, and Pegasos [15] showed that stochastic sub-gradient descent on the SVM primal reaches a given accuracy with a run time that, for linear kernels, does not depend directly on the training-set size, the same idea as training neural networks with SGD.

Linear probes as the yardstick of representations. Alain and Bengio [21] proposed training independent linear classifiers (“probes”) on every layer of a network, and observed that linear separability increases monotonically with depth. Kornblith, Shlens and Le [22] compared 16 networks on 12 datasets and found that, with features used as fixed extractors under a logistic-regression classifier, ImageNet accuracy and transfer accuracy are strongly correlated, though some regularizers that slightly improve ImageNet accuracy produce much worse penultimate-layer features. CLIP [23] compares its zero-shot classifier with logistic-regression probes on frozen features, and DINOv2 [24] evaluates its self-supervised features largely with linear classifiers on frozen backbones. Kumar et al. [25] showed that full fine-tuning can distort good pretrained features and underperform a linear probe out of distribution, and proposed fitting a linear probe first and then fine-tuning (LP-FT). In other words: a well-regularized logistic regression on top of a frozen foundation model is a strong baseline, and often the right first experiment.

Implicit bias: logistic regression secretly finds the SVM. Soudry et al. [19] proved that gradient descent on unregularized logistic (or cross-entropy) loss over linearly separable data converges in direction to the hard-margin SVM solution, extending the result to other losses with exponential tails, to multiclass problems and to a restricted deep-network setting. Convergence is only logarithmic, which helps explain why continuing to train after zero training error can keep improving the margin. The gradient-descent code above shows the effect in two dimensions.

Neural collapse: Fisher’s picture at the end of training. Papyan, Han and Donoho [20] observed, across three architectures and seven datasets, that in the terminal phase of training (after zero training error) the last-layer features of each class collapse to their class mean, the class means arrange themselves into a maximally separated, symmetric configuration (a simplex equiangular tight frame), the classifier weights align with the class means, and the decision rule becomes the nearest class mean. In this chapter’s language, the within-class scatter SWS_W shrinks towards zero, Fisher’s criterion grows without bound, and the network’s last layer becomes the minimum-distance classifier of PR 01.

Open problems. When should one trust a linear probe as a measure of representation quality, given that probe results depend on regularization and data size? How do implicit-bias results extend to realistic, non-separable, data-augmented training? And when do probabilities from linear heads stay calibrated under distribution shift? These questions link the oldest classifier in this track to current research.

Key takeaways

  • A linear discriminant g(x)=w⊤x+bg(x)=w^\top x+b is a hyperplane with normal ww; g(x)/∥w∥g(x)/\|w\| is the signed distance. Use one discriminant per class (a linear machine) for multiclass problems.
  • Least squares and ridge have closed forms and a Bayesian MAP interpretation, but least squares is a poor classifier: it punishes points that are “too correct” and can mask classes.
  • Fisher’s direction w∝SW−1(m1−m0)w\propto S_W^{-1}(m_1-m_0) maximizes between-class over within-class spread; it equals the Gaussian LDA direction, which adds a threshold from means and priors.
  • The perceptron converges in at most (R/γ)2(R/\gamma)^2 updates on separable data, but stops at an arbitrary separator and cycles on overlapping data.
  • Logistic regression fits the log-odds by convex cross-entropy minimization (Newton/IRLS); without regularization its weights diverge on separable data, in the direction of the max-margin solution.
  • The hard-margin SVM maximizes the margin 2/∥w∥2/\|w\|; its dual shows that only support vectors matter and that data enter only through inner products, which opens the door to kernels (PR 04). The soft margin is ridge-regularized hinge loss.
  • All these methods are one linear score with different surrogate losses; hinge, logistic and squared losses are classification-calibrated, but only the logistic loss estimates probabilities.

Exercises

  1. Linear in the parameters. Show that fitting g(x)=w0+w1x+w2x2g(x)=w_0+w_1x+w_2x^2 by least squares is a linear regression problem, and describe the decision regions in xx if the same features are used for a two-class linear classifier.
Hint

Build rows (1,x,x2)(1,x,x^2) of a design matrix; the model is linear in (w0,w1,w2)(w_0,w_1,w_2). A quadratic in xx changes sign at most twice, so the region for one class can be an interval and the other class its complement (two half-lines).

  1. Units and ridge. Two features measure the same distance, one in metres and one in millimetres. Explain what ridge regression does without feature scaling, and why standardizing fixes it.
Hint

The millimetre coefficient can be 1,000 times smaller while describing the same effect, so it is penalized far less; ridge will load almost all weight onto the millimetre feature. After standardization both coordinates are penalized on the same scale.

  1. Fisher by hand. Two classes have means m0=(0,0)m_0=(0,0), m1=(2,0)m_1=(2,0) and within-class scatter SW=[2112]S_W=\begin{bmatrix}2&1\\1&2\end{bmatrix}. Compute Fisher’s direction and compare it with the mean difference. When would the two directions coincide?
Hint

SW−1=13[2−1−12]S_W^{-1}=\tfrac13\begin{bmatrix}2&-1\\-1&2\end{bmatrix}, so w∝SW−1(2,0)⊤=13(4,−2)∝(2,−1)w\propto S_W^{-1}(2,0)^\top=\tfrac13(4,-2)\propto(2,-1), rotated away from the mean difference (1,0)(1,0) because the classes are stretched along (1,1)(1,1). The directions coincide exactly when m1−m0m_1-m_0 is an eigenvector of SWS_W, e.g. for m1=(2,2)m_1=(2,2).

  1. A perceptron that never stops. Construct a one-dimensional dataset on which the perceptron updates forever, and explain which assumption of the convergence theorem fails.
Hint

Put two points at the same coordinate with opposite labels (or any overlapping classes). No uu with γ>0\gamma>0 exists, so the bound does not apply; each update that fixes one point breaks the other.

  1. SVM by hand. Find the hard-margin SVM for the two points x1=(1,1)x_1=(1,1) with y1=+1y_1=+1 and x2=(−1,−1)x_2=(-1,-1) with y2=−1y_2=-1. Give ww, bb, the dual variables and the margin width, and check the KKT conditions.
Hint

By symmetry b=0b=0 and w=c(1,1)w=c(1,1). The constraint y1w⊤x1=1y_1w^\top x_1=1 gives 2c=12c=1, so w=(12,12)w=(\tfrac12,\tfrac12) and the width is 2/∥w∥=222/\|w\|=2\sqrt2, the distance between the points. From w=a1x1−a2x2w=a_1x_1-a_2x_2 and a1=a2a_1=a_2, a1=a2=14a_1=a_2=\tfrac14. Both points are support vectors.

  1. Logistic versus hinge. Using the digits pipeline, fit LogisticRegression and LinearSVC for several values of C with 5-fold cross-validation on the training set only. Compare their best validation accuracies, then compare their scores: which one gives meaningful probabilities, and how would you obtain probabilities from the other?
Hint

Accuracies are typically close, as the loss analysis predicts. Only logistic regression’s predict_proba estimates posteriors; for the SVM, fit a calibration map (Platt scaling or isotonic regression, e.g. CalibratedClassifierCV) on held-out data.

References

  1. R. O. Duda, P. E. Hart and D. G. Stork, Pattern Classification, 2nd ed., Wiley, 2001 (Ch. 5, linear discriminant functions). publisher page
  2. C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006 (Sections 3.1–3.3, 4.1–4.3 and 7.1). official page and free PDF
  3. S. Theodoridis and K. Koutroumbas, Pattern Recognition, 4th ed., Academic Press, 2008 (Ch. 3, linear classifiers). publisher page
  4. T. Hastie, R. Tibshirani and J. Friedman, The Elements of Statistical Learning, 2nd ed., Springer, 2009 (Ch. 3–4 and 12). official page
  5. R. A. Fisher, “The use of multiple measurements in taxonomic problems,” Annals of Eugenics, vol. 7, no. 2, pp. 179–188, 1936. doi
  6. F. Rosenblatt, “The perceptron: a probabilistic model for information storage and organization in the brain,” Psychological Review, vol. 65, no. 6, pp. 386–408, 1958. doi
  7. D. R. Cox, “The regression analysis of binary sequences,” Journal of the Royal Statistical Society, Series B, vol. 20, no. 2, pp. 215–232, 1958. doi
  8. A. E. Hoerl and R. W. Kennard, “Ridge regression: biased estimation for nonorthogonal problems,” Technometrics, vol. 12, no. 1, pp. 55–67, 1970. doi
  9. B. E. Boser, I. M. Guyon and V. N. Vapnik, “A training algorithm for optimal margin classifiers,” in Proc. 5th Annual Workshop on Computational Learning Theory (COLT), pp. 144–152, 1992. doi
  10. C. Cortes and V. Vapnik, “Support-vector networks,” Machine Learning, vol. 20, no. 3, pp. 273–297, 1995. doi
  11. C. J. C. Burges, “A tutorial on support vector machines for pattern recognition,” Data Mining and Knowledge Discovery, vol. 2, no. 2, pp. 121–167, 1998. doi
  12. P. L. Bartlett, M. I. Jordan and J. D. McAuliffe, “Convexity, classification, and risk bounds,” Journal of the American Statistical Association, vol. 101, no. 473, pp. 138–156, 2006. doi
  13. L. Rosasco, E. De Vito, A. Caponnetto, M. Piana and A. Verri, “Are loss functions all the same?,” Neural Computation, vol. 16, no. 5, pp. 1063–1076, 2004. doi
  14. R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang and C.-J. Lin, “LIBLINEAR: a library for large linear classification,” Journal of Machine Learning Research, vol. 9, pp. 1871–1874, 2008. paper
  15. S. Shalev-Shwartz, Y. Singer, N. Srebro and A. Cotter, “Pegasos: primal estimated sub-gradient solver for SVM,” Mathematical Programming, vol. 127, no. 1, pp. 3–30, 2011. doi
  16. C.-C. Chang and C.-J. Lin, “LIBSVM: a library for support vector machines,” ACM Transactions on Intelligent Systems and Technology, vol. 2, no. 3, article 27, 2011. doi
  17. J. Cervantes, F. Garcia-Lamont, L. Rodríguez-Mazahua and A. Lopez, “A comprehensive survey on support vector machine classification: applications, challenges and trends,” Neurocomputing, vol. 408, pp. 189–215, 2020. doi
  18. A. Y. Ng and M. I. Jordan, “On discriminative vs. generative classifiers: a comparison of logistic regression and naive Bayes,” in Advances in Neural Information Processing Systems (NIPS), 2001. paper
  19. D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar and N. Srebro, “The implicit bias of gradient descent on separable data,” Journal of Machine Learning Research, vol. 19, no. 70, pp. 1–57, 2018. paper
  20. V. Papyan, X. Y. Han and D. L. Donoho, “Prevalence of neural collapse during the terminal phase of deep learning training,” Proceedings of the National Academy of Sciences, vol. 117, no. 40, pp. 24652–24663, 2020. doi
  21. G. Alain and Y. Bengio, “Understanding intermediate layers using linear classifier probes,” arXiv:1610.01644, 2016. arXiv
  22. S. Kornblith, J. Shlens and Q. V. Le, “Do better ImageNet models transfer better?,” in Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019. paper
  23. A. Radford et al., “Learning transferable visual models from natural language supervision,” in Proc. International Conference on Machine Learning (ICML), PMLR 139, 2021. paper
  24. M. Oquab et al., “DINOv2: learning robust visual features without supervision,” Transactions on Machine Learning Research, 2024. arXiv
  25. A. Kumar, A. Raghunathan, R. Jones, T. Ma and P. Liang, “Fine-tuning can distort pretrained features and underperform out-of-distribution,” in Proc. International Conference on Learning Representations (ICLR), 2022. arXiv

Check your understanding

This tutorial has 6 exercises. Can you solve them without opening the hints?

Go to the exercises ↑

Next PR 04 · Neighbors, Kernels and Nonlinear Classifiers · 28 min