Machine Learning from First Principles

Chapter 6 · Part II: Supervised Learning

Logistic Regression and Classification

To classify, model the probability of each class. That single idea gives the sigmoid, the cross-entropy loss, softmax, and the output layer of essentially every neural classifier, including large language models.

After this chapter you will be able to

  • Model the probability of a class with the sigmoid and interpret weights as log-odds.
  • Derive the cross-entropy loss from the Bernoulli likelihood, and its gradient.
  • Extend to many classes with softmax, implemented stably.
  • Evaluate classifiers with confusion matrices, precision, recall, ROC curves, and AUC.
  • Choose a decision threshold that matches the costs of different errors.

6.1Classification as Probability Estimation

For labels $y\in\{0,1\}$, linear regression on 0/1 targets works poorly: outputs leave $[0,1]$, and easy points far from the boundary drag the fit. Instead, keep a linear score $z = \vw\T\vx + b$ and squash it with the sigmoid:

$$\sigma(z) = \frac{1}{1 + e^{-z}}, \qquad p(y = 1\mid\vx) = \sigma(\vw\T\vx + b). \tag{6.1}$$

Log-odds. Inverting gives $z = \log\frac{p}{1-p}$: the score is the log-odds. Raising $x_j$ by one unit multiplies the odds of class 1 by $e^{w_j}$.

Decision boundary. $p\ge\tfrac12$ exactly when $z\ge 0$, so the boundary $\vw\T\vx + b = 0$ is a hyperplane perpendicular to $\vw$. Logistic regression is a linear classifier; curved boundaries need nonlinear features or neural networks.

6.2The Cross-Entropy Loss

Each label is Bernoulli with probability $\hat p^{(i)} = \sigma(\vw\T\vx^{(i)} + b)$. The average negative log-likelihood is the binary cross-entropy:

$$\Loss(\vw, b) = -\frac1n\sum_{i=1}^n\Big[y^{(i)}\log\hat p^{(i)} + (1 - y^{(i)})\log(1 - \hat p^{(i)})\Big]. \tag{6.2}$$

Each term is $-\log(\text{probability of the true class})$: nearly free when confidently right, unbounded when confidently wrong. The 0–1 loss has zero gradient almost everywhere; squared error on $\sigma$ is non-convex with vanishing gradients when badly wrong. Cross-entropy is convex with strong gradients exactly when the model is wrong.

6.3The Gradient

Using $\sigma'(z) = \sigma(z)(1 - \sigma(z))$ and the chain rule, everything cancels to the prediction error: $\partial\ell/\partial z = \hat p - y$.

Show derivation
$$\pd{\ell}{z} = \Big(-\frac{y}{\hat p} + \frac{1-y}{1-\hat p}\Big)\hat p(1-\hat p) = -y(1-\hat p) + (1-y)\hat p = \hat p - y.$$
$$\nabla_{\vw}\Loss = \frac1n\mX\T(\hat\vp - \vy), \qquad \pd{\Loss}{b} = \frac1n\sum_i(\hat p^{(i)} - y^{(i)}). \tag{6.4}$$

Same form as linear regression: errors mapped back through the features. Both are generalized linear models. There is no closed-form solution, but the loss is convex and smooth, so gradient descent or Newton's method finds the global minimum.

Pitfall: perfectly separable data

If a hyperplane separates the classes, scaling up $\vw$ always increases the likelihood, so the weights grow forever. Add a small $\ell_2$ penalty (scikit-learn does by default).

6.4Multiclass Classification with Softmax

For $K$ classes, compute one score per class, $z_k = \vw_k\T\vx + b_k$, and normalize:

$$p(y = k\mid\vx) = \softmax(\vz)_k = \frac{e^{z_k}}{\sum_{j=1}^K e^{z_j}}. \tag{6.5}$$

With a one-hot label $\vy$, the categorical cross-entropy is $\ell = -\log\hat p_y$, and its gradient with respect to the scores is once again prediction minus truth:

$$\pd{\ell}{\vz} = \hat\vp - \vy. \tag{6.7}$$

Softmax with cross-entropy is the output layer of essentially every neural classifier, including next-token prediction in language models, where $K$ is the vocabulary size.

Numerical stability. Subtract $m = \max_j z_j$ before exponentiating (softmax is unchanged), compute $\log\sum_j e^{z_j} = m + \log\sum_j e^{z_j - m}$ (log-sum-exp), and compute the loss from the scores, never from the log of a probability that may have underflowed.

6.5Evaluating Classifiers

Count true/false positives/negatives on a test set:

MetricFormulaQuestion it answers
Accuracy$\frac{TP+TN}{\text{all}}$What fraction is correct?
Precision$\frac{TP}{TP+FP}$When it says positive, how often is it right?
Recall$\frac{TP}{TP+FN}$What fraction of positives does it find?
False-positive rate$\frac{FP}{FP+TN}$What fraction of negatives does it wrongly flag?
$F_1$$\frac{2PR}{P+R}$Harmonic mean of precision and recall

Pitfall: accuracy on imbalanced data

With 1% fraud, "never fraud" is 99% accurate and useless. Report precision and recall. Precision is the posterior $p(\text{positive}\mid\text{flagged})$ from Chapter 2.

Thresholds. Predict positive when $\hat p\ge\tau$. Lower $\tau$ raises recall and false positives together. For calibrated probabilities with error costs $c_{\mathrm{FP}}$ and $c_{\mathrm{FN}}$, the cost-minimizing threshold is $\tau = c_{\mathrm{FP}}/(c_{\mathrm{FP}} + c_{\mathrm{FN}})$.

ROC and AUC. Sweeping $\tau$ traces recall against false-positive rate. The area under it (AUC) is the probability that a random positive outscores a random negative; it ignores threshold and class balance. Precision–recall curves are more informative when positives are rare.

Calibration. Among examples given probability 0.8, about 80% should be positive. Logistic regression is usually reasonably calibrated; large neural networks are often overconfident.

6.6The Perceptron

Keep the hard step instead of the sigmoid. With $y\in\{-1,+1\}$ and $h(\vx)=\sign(\vw\T\vx)$ (bias absorbed by a constant feature), Rosenblatt's perceptron (1958) cycles through the data and corrects each mistake:

$$\text{if } y^{(i)}\,\vw\T\vx^{(i)}\le0:\qquad \vw\gets\vw+y^{(i)}\vx^{(i)}. \tag{6.8}$$

This is the “error times input” update with an error of $-1$, $0$, or $+1$; equivalently, SGD with step 1 on the perceptron loss $\max(0,-y\,\vw\T\vx)$, a hinge with its corner at 0 instead of 1.

Theorem 6.1 (Perceptron convergence)

If $\norm{\vx^{(i)}}\le R$ and a unit vector $\vw^\star$ separates the data with margin $\gamma$ ($y^{(i)}\vw^{\star\top}\vx^{(i)}\ge\gamma$), the perceptron started at $\mathbf 0$ makes at most $(R/\gamma)^2$ mistakes, in any order and over any number of passes.

Show proof

Progress: each mistake adds $y\,\vx\T\vw^\star\ge\gamma$ to $\vw\T\vw^\star$, so after $k$ mistakes $\vw_k\T\vw^\star\ge k\gamma$. Bounded growth: $\norm{\vw_k}^2=\norm{\vw_{k-1}}^2+2y\,\vw_{k-1}\T\vx+\norm\vx^2\le\norm{\vw_{k-1}}^2+R^2$ because the middle term is $\le0$ on a mistake, so $\norm{\vw_k}^2\le kR^2$. Then $k\gamma\le\vw_k\T\vw^\star\le\norm{\vw_k}\le\sqrt k R$, so $k\le R^2/\gamma^2$.

The bound depends on the margin, not the dimension: an early form of the margin idea behind SVMs (Chapter 9). On nonseparable data the perceptron never stops (the averaged perceptron is the practical fix); on separable data it stops at some separator, not the maximum-margin one; and it gives no probabilities. That a single perceptron cannot represent XOR (Minsky and Papert 1969) motivated multilayer networks (Chapter 15).

6.7Newton's Method and IRLS

Logistic regression usually has few parameters, so Newton's method (Section 3.8) is affordable. The Hessian of the cross-entropy is

$$\nabla^2\Loss(\vw)=\frac1n\mX\T\mathbf D\mX,\qquad \mathbf D=\diag\big(\hat p^{(i)}(1-\hat p^{(i)})\big),$$

which is positive semidefinite (the loss is convex), and the Newton step is

$$\vw\gets\vw-\big(\mX\T\mathbf D\mX\big)^{-1}\mX\T(\hat\vp-\vy). \tag{6.9}$$

Each step is a weighted least-squares solve with weight $\hat p^{(i)}(1-\hat p^{(i)})$, largest near the boundary: iteratively reweighted least squares (IRLS), which Chapter 7 extends to every GLM. It reaches machine precision in 5–10 iterations where GD needs thousands, with no learning rate or feature scaling, at $O(nd^2+d^3)$ per step. For large $d$, L-BFGS (scikit-learn's default solver) approximates the Hessian. On separable data $\mathbf D\to\mathbf 0$ and the iteration diverges; add $\lambda\mI$ to the Hessian and $\lambda\vw$ to the gradient.

6.8Implementation

import numpy as np

def sigmoid(z):
    out = np.empty_like(z, dtype=float)       # stable for large |z|
    pos = z >= 0
    out[pos] = 1 / (1 + np.exp(-z[pos]))
    ez = np.exp(z[~pos])
    out[~pos] = ez / (1 + ez)
    return out

def bce_from_logits(z, y):
    return np.mean(np.logaddexp(0, z) - y * z)  # log(1 + e^z) - y z

def fit_logreg(X, y, lam=1e-3, lr=0.5, steps=2000):
    n, d = X.shape
    w, b = np.zeros(d), 0.0
    for _ in range(steps):
        p = sigmoid(X @ w + b)
        w -= lr * (X.T @ (p - y) / n + lam * w)
        b -= lr * np.mean(p - y)
    return w, b

def softmax(Z):
    Z = Z - Z.max(axis=1, keepdims=True)
    E = np.exp(Z)
    return E / E.sum(axis=1, keepdims=True)

def fit_softmax(X, y, K, lam=1e-3, lr=0.5, steps=2000):
    n, d = X.shape
    W, b, Y = np.zeros((d, K)), np.zeros(K), np.eye(K)[y]
    for _ in range(steps):
        P = softmax(X @ W + b)
        W -= lr * (X.T @ (P - Y) / n + lam * W)
        b -= lr * (P - Y).mean(axis=0)
    return W, b

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import confusion_matrix, roc_auc_score

X, y = load_breast_cancer(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
sc = StandardScaler().fit(Xtr)
Xtr, Xte = sc.transform(Xtr), sc.transform(Xte)
w, b = fit_logreg(Xtr, ytr)
p_test = sigmoid(Xte @ w + b)
print(confusion_matrix(yte, p_test >= 0.5))
print("AUC:", roc_auc_score(yte, p_test))

In scikit-learn use LogisticRegression(C=1/lam); $C$ is the inverse regularization strength.

6.9Common Pitfalls

Pitfall: treating scores as probabilities without checking

Check calibration on held-out data before making cost-based decisions with $\hat p$.

Pitfall: choosing the threshold on the test set

The threshold is a hyperparameter: choose it on validation data, then report test performance at that fixed value.

6.10Summary

  • $p(y=1\mid\vx) = \sigma(\vw\T\vx + b)$; the score is the log-odds; the boundary is a hyperplane.
  • The Bernoulli likelihood gives the convex binary cross-entropy, with gradient $\frac1n\mX\T(\hat\vp - \vy)$.
  • Softmax handles $K$ classes; the score gradient is again $\hat\vp - \vy$.
  • Compute sigmoid, softmax, and losses from logits stably.
  • Evaluate with precision, recall, ROC/AUC, and calibration; set the threshold from error costs.
  • The perceptron corrects mistakes with $\vw\gets\vw+y\vx$; on separable data it makes at most $(R/\gamma)^2$ mistakes, but it cycles on nonseparable data.
  • Newton's method for logistic regression is IRLS: weighted least squares with weights $\hat p(1-\hat p)$, converging in a handful of iterations.

6.11Exercises

  1. MathShow that the BCE Hessian is $\frac1n\mX\T\mathbf D\mX$ with $\mathbf D = \diag(\hat p^{(i)}(1-\hat p^{(i)}))$, so the loss is convex.
  2. MathShow that two-class softmax gives $p(y=1) = \sigma(z_1 - z_0)$. Why is one weight vector redundant?
  3. MathDerive Equation (6.7) from the softmax Jacobian.
  4. MathProve the cost-minimizing threshold $\tau = c_{\mathrm{FP}}/(c_{\mathrm{FP}} + c_{\mathrm{FN}})$ for a calibrated classifier.
  5. MathProve that the area under the step-function ROC curve equals the fraction of correctly ranked (positive, negative) pairs.
  6. CodingImplement Newton's method for logistic regression and compare iterations to convergence with gradient descent.
  7. CodingTrain fit_softmax on load_digits. Which digits are most often confused?
  8. CodingConstruct four points in $\R^2$ on which the perceptron never stops making mistakes. Then run the perceptron and the averaged perceptron for 100 epochs on a larger noisy data set and compare the training accuracy of the final and averaged weights.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.