Logistic Regression

Every model this unit has built assumed the label \(y\) was a real number: cones sold, a house price. Today we close the unit with the other kind, the one the Regression lecture named and then set aside: spam or not spam, which digit is in the image. Regression asked “how much?”; classification asks “which one?” We can reuse the linear score, maximum-likelihood procedure, and gradient descent by choosing a distribution for categorical labels and minimizing its negative log-likelihood. Replacing the Gaussian label model with a Bernoulli model changes the output function and loss, and it removes the closed-form solution.

From a Score to a Probability

Start with binary labels, \(y \in \{0, 1\}\). The linear model from three lectures ago still applies, turning a feature vector into a single real number we will call the score: \[ z = \langle \mathbf{w}, \mathbf{x}\rangle \in \mathbb{R}, \] where \(\mathbf{x} \in \mathbb{R}^d\) is the feature vector and \(\mathbf{w} \in \mathbb{R}^d\) the weights, with the bias folded in as a constant feature as usual. A score is not a probability, so we need a function that squashes any real number into \((0,1)\), and the standard choice is the sigmoid function: \[ \sigma(z) = \frac{1}{1 + e^{-z}}. \]

The sigmoid maps a real-valued score to a probability and turns a linear score boundary into a classification boundary.

In the left panel, \(\sigma(z)\) increases smoothly from \(0\) to \(1\), crossing \(\frac12\) at \(z=0\). A score near zero gives a probability near one half, while a large-magnitude score gives a probability near \(0\) or \(1\). Our model now predicts: \[ f(\mathbf{x}) = \sigma\big(\langle \mathbf{w}, \mathbf{x}\rangle\big), \] read as the probability that \(y = 1\) given \(\mathbf{x}\). Why this particular squashing function, rather than any other S-shaped curve? Problem 10 starts from Bayes’ rule but changes the class-conditional variances. The posterior remains a sigmoid, while its score becomes quadratic, separating the role of the output function from the role of the features.

Because \(\sigma(z) = \frac12\) exactly at \(z=0\), the predicted class flips wherever the score changes sign: the hyperplane \(\langle \mathbf{w}, \mathbf{x}\rangle = 0\) splits \(\mathbb{R}^d\) into a “predict \(1\)” half-space and a “predict \(0\)” half-space. The right panel shows this decision boundary for two features, with the background shading giving the predicted probability over two point clouds. The boundary where the shading crosses \(\frac12\) is a straight line, because the model underneath is still linear and only its output has been reinterpreted.

If the prediction only depends on the sign of the score, why bother with the sigmoid at all? A probability is more useful than a verdict: a doctor ordering a second test needs to know whether the model said \(0.51\) or \(0.99\). A hard threshold has zero derivative almost everywhere, while the sigmoid has a usable derivative for optimization. To fit it, we need a loss.

The Likelihood of a Label

Given a class probability, maximum likelihood works as it did for regression, with a different noise model. A binary label is naturally modeled as a Bernoulli random variable with success probability \(f(\mathbf{x})\), and both of its cases fit in one expression: \[ \Pr(y \mid \mathbf{x}) = f(\mathbf{x})^{\,y}\,\big(1-f(\mathbf{x})\big)^{1-y}. \] Plug in \(y=1\) and the second factor becomes \(1\), and vice versa: the exponents are switches rather than arithmetic.

Apply the maximum-likelihood derivation from the Mean Squared Error lecture. The \(n\) labels are independent, so the likelihood of the dataset is a product, and a logarithm turns that product into a sum: \[ \begin{align*} \arg\max_\mathbf{w} \prod_{i=1}^n \Pr\big(y^{(i)} \mid \mathbf{x}^{(i)}\big) &= \arg\max_\mathbf{w} \sum_{i=1}^n \log \Pr\big(y^{(i)} \mid \mathbf{x}^{(i)}\big) \\&= \arg\max_\mathbf{w} \sum_{i=1}^n \Big[ y^{(i)} \log f(\mathbf{x}^{(i)}) + \big(1-y^{(i)}\big) \log\big(1 - f(\mathbf{x}^{(i)})\big) \Big]. \end{align*} \] The first equality is the Mean Squared Error lecture’s log moves, unchanged; the second substitutes the Bernoulli probability above and splits the logarithm, \(\log(a^y b^{1-y}) = y\log a + (1-y)\log b\). Flipping the sign turns the maximization into a minimization, and dividing by \(n\) moves nothing, so we are minimizing the binary cross-entropy loss: \[ \mathcal{L}(\mathbf{w}) = -\frac1n\sum_{i=1}^n \Big[ y^{(i)} \log f(\mathbf{x}^{(i)}) + \big(1-y^{(i)}\big) \log\big(1 - f(\mathbf{x}^{(i)})\big) \Big]. \] Each point contributes \(-\log\) of the probability assigned to the correct answer. The contribution is near zero for a confident correct prediction and grows without bound as that probability approaches zero, so one confident mistake can contribute more loss than a hundred uncertain correct predictions. The Gaussian likelihood produces squared error, while the Bernoulli likelihood produces cross-entropy.

Many classification problems have more than two classes, such as ten digits or thousands of words.

Many Classes: Softmax and Categorical Cross-Entropy

Generalize the single score to a vector of \(k\) scores, one per class, called the logits: \[ \mathbf{z} = \mathbf{W}^\top\mathbf{x} \in \mathbb{R}^k, \] where the weight matrix \(\mathbf{W} \in \mathbb{R}^{d\times k}\) holds one column of weights per class, so that \(z_j = \langle [\mathbf{W}]_{,j}, \mathbf{x}\rangle\) is class \(j\)’s score. The softmax function turns these \(k\) scores into a probability distribution over the \(k\) classes: \[ [\mathrm{softmax}(\mathbf{z})]_j = \frac{e^{z_j}}{\sum_{l=1}^k e^{z_l}}, \] exponentiating so every entry is positive, then normalizing to sum to \(1\). Softmax depends only on differences between logits because adding the same constant to every \(z_j\) cancels. When one logit is much larger than the others, its probability approaches \(1\). Setting \(k=2\) and reading off the probability of class \(1\) recovers the sigmoid exactly. (Can you check that? Divide the numerator and denominator by \(e^{z_1}\) and compare with \(\sigma(z_1 - z_2)\).)

The label is now categorical, encoded as a one-hot vector: \[ \mathbf{y} \in \{0,1\}^k, \qquad \textstyle\sum_{j=1}^k y_j = 1, \] carrying its single \(1\) in the true class’s slot. Using a categorical distribution in place of the Bernoulli gives the categorical cross-entropy loss: \[ \mathcal{L}(\mathbf{W}) = -\frac1n\sum_{i=1}^n \sum_{j=1}^k y_j^{(i)} \log p_j^{(i)}, \qquad \mathbf{p}^{(i)} = \mathrm{softmax}\big(\mathbf{W}^\top\mathbf{x}^{(i)}\big), \] where \(\mathbf{p}^{(i)} \in \mathbb{R}^k\) is the model’s predicted distribution over classes for the \(i\)th point. Since \(\mathbf{y}^{(i)}\) is one-hot, the inner sum reduces to the negative log-probability of the true class; the binary case is this formula at \(k=2\).

We have a model and a loss. Minimizing the loss needs its gradient.

The Cross-Entropy Gradient

The gradient is simple because the logarithm in cross-entropy cancels the exponential in the true class’s softmax numerator, leaving the normalizer. We derive it at the board in class.

Claim: For a single example with logits \(\mathbf{z} \in \mathbb{R}^k\), one-hot label \(\mathbf{y}\) carrying its \(1\) in slot \(c\), and prediction \(\mathbf{p} = \mathrm{softmax}(\mathbf{z})\), the per-example cross-entropy \(\ell = -\log p_c\) has gradient \[ \nabla_\mathbf{z}\, \ell = \mathbf{p} - \mathbf{y}, \] which we read aloud as “softmax minus one-hot.”

Proof of Claim Write \(\ell = -\log p_c = -z_c + \log \sum_{l=1}^k e^{z_l}\), using the definition of \(p_c\) and the logarithm of a quotient. Differentiate with respect to each logit \(z_j\). For the first term, \(\partial(-z_c)/\partial z_j\) is \(-1\) if \(j=c\) and \(0\) otherwise, which is exactly \(-y_j\). For the second term, the chain rule through the logarithm gives: \[ \frac{\partial}{\partial z_j} \log \sum_{l=1}^k e^{z_l} = \frac{e^{z_j}}{\sum_{l=1}^k e^{z_l}} = p_j. \] Adding the two pieces, \(\partial \ell/\partial z_j = p_j - y_j\) for every \(j\), which stacked into a vector is \(\nabla_\mathbf{z}\ell = \mathbf{p}-\mathbf{y}\).

The gradient is the predicted distribution minus the true one, the residual of the Regression lecture written in probabilities instead of cones. It is zero exactly when the model puts all probability on the true class. Its only negative entry is the true class’s, \(p_c - 1\), and every entry lies in \([-1,1]\), so the logit gradient from one example is bounded even though its loss is not.

The chain rule through \(\mathbf{z} = \mathbf{W}^\top\mathbf{x}\) gives the gradient on the weights. Logit \(z_j\) depends only on column \(j\) of \(\mathbf{W}\), and linearly, so \(\partial z_j / \partial [\mathbf{W}]_{,j} = \mathbf{x}\) and the per-example gradient is an outer product: \[ \nabla_\mathbf{W}\, \ell = \mathbf{x}\,(\mathbf{p} - \mathbf{y})^\top \in \mathbb{R}^{d \times k} . \] Averaging over the dataset gives the gradient of the loss itself: \[ \nabla_\mathbf{W}\mathcal{L}(\mathbf{W}) = \frac1n \sum_{i=1}^n \mathbf{x}^{(i)}\big(\mathbf{p}^{(i)} - \mathbf{y}^{(i)}\big)^\top = \frac1n \mathbf{X}^\top\big(\mathbf{P} - \mathbf{Y}\big), \] where \(\mathbf{X} \in \mathbb{R}^{n\times d}\) is the design matrix from the Linear Model lecture and \(\mathbf{P}, \mathbf{Y} \in \mathbb{R}^{n \times k}\) stack the predicted and one-hot distributions as rows; the second equality is the outer-product form of matrix multiplication from Unit 1.

The least-squares gradient from the Optimization lecture had the same form: \(\frac{2}{n}\mathbf{X}^\top(\mathbf{X}\mathbf{w} - \mathbf{y})\), the transposed design matrix times a residual. The coincidence has one cause: in both cases the derivative of the loss with respect to the score is the residual, and the score is linear in the weights, so the chain rule multiplies that residual by \(\mathbf{x}\) and stops. The same form appears at the output layer of the classifiers in the next unit and in the final unit’s policy update, where the residual is scaled by a reward.

Information theory gives another interpretation of the quantity minimized by cross-entropy.

Entropy and KL Divergence

Cross-entropy borrows its name from information theory, where the entropy of a distribution over \(k\) outcomes is the average surprise of a draw from it: \[ H(\mathbf{y}) = -\sum_{j=1}^k y_j \log y_j, \] where an outcome of probability \(y_j\) carries surprise \(-\log y_j\), so probability spread thinly over many outcomes means high entropy: a fair die has more entropy than a loaded one. The Kullback-Leibler divergence measures the extra surprise we suffer by holding the distribution \(\mathbf{p}\) while outcomes actually arrive from \(\mathbf{y}\): \[ D_{\mathrm{KL}}(\mathbf{y} \,\|\, \mathbf{p}) = \sum_{j=1}^k y_j \log \frac{y_j}{p_j}. \] The cross-entropy of the pair is the total surprise we suffer under \(\mathbf{p}\) when reality is \(\mathbf{y}\): \[ \mathrm{CE}(\mathbf{y}, \mathbf{p}) = -\sum_{j=1}^k y_j \log p_j, \] which is exactly the per-example loss from two sections ago.

The identity relating the three is one line of algebra we do live in class.

Claim: For any two distributions \(\mathbf{y}\) and \(\mathbf{p}\) over the same \(k\) outcomes, cross-entropy splits into entropy plus divergence: \[ \mathrm{CE}(\mathbf{y}, \mathbf{p}) = H(\mathbf{y}) + D_{\mathrm{KL}}(\mathbf{y}\,\|\,\mathbf{p}). \]

Proof of Claim Split the logarithm inside the divergence, \(\log(y_j/p_j) = \log y_j - \log p_j\), and separate the sum: \[ \begin{align*} D_{\mathrm{KL}}(\mathbf{y}\,\|\,\mathbf{p}) &= \sum_{j=1}^k y_j \log y_j - \sum_{j=1}^k y_j \log p_j \\&= -H(\mathbf{y}) + \mathrm{CE}(\mathbf{y}, \mathbf{p}), \end{align*} \] where the second equality reads the definitions of \(H\) and \(\mathrm{CE}\) backwards, and rearranging gives the claim.

Cross-entropy is the entropy of \(\mathbf{y}\) plus the additional surprise from predicting \(\mathbf{p}\) when outcomes follow \(\mathbf{y}\). Only the second term depends on the model. When we train, \(\mathbf{y}^{(i)}\) is a one-hot label, its entropy is \(0\) because no surprise is left once the answer is certain (with \(0\log 0 = 0\)), and the entire loss is a divergence: \[ \mathcal{L}(\mathbf{W}) = \frac1n\sum_{i=1}^n D_{\mathrm{KL}}\big(\mathbf{y}^{(i)} \,\|\, \mathbf{p}^{(i)}\big). \] Minimizing cross-entropy therefore minimizes the KL divergence from each target distribution \(\mathbf{y}^{(i)}\) to the prediction \(\mathbf{p}^{(i)}\). In the final unit, a KL penalty will limit how far a policy update moves from its previous action distribution.

Unlike least squares, logistic regression has no closed-form solution for the minimizing weights.

Fitting by Gradient Descent

Setting the gradient to zero gives \(\mathbf{X}^\top\mathbf{P} = \mathbf{X}^\top\mathbf{Y}\), but every entry of \(\mathbf{P}\) depends on \(\mathbf{W}\) through the softmax’s exponentials, and no rearrangement isolates \(\mathbf{W}\) the way the normal equations isolated \(\mathbf{w}^\star\). We will fit it with gradient descent, the iterative method introduced two lectures ago: \[ \mathbf{W}^{(t+1)} = \mathbf{W}^{(t)} - \frac{\alpha}{n}\,\mathbf{X}^\top\big(\mathbf{P}^{(t)} - \mathbf{Y}\big), \] where \(\alpha > 0\) is the learning rate from that lecture and \(\mathbf{P}^{(t)} \in \mathbb{R}^{n\times k}\) holds the predicted distributions at the current weights \(\mathbf{W}^{(t)}\).

Cross-entropy is convex in \(\mathbf{W}\), the same property that made least squares a bowl. Under the usual step-size conditions, gradient descent converges to a global minimum when a finite minimizer exists. One step is also cheap: \(O(ndk)\), dominated by forming \(\mathbf{X}\mathbf{W}\) and \(\mathbf{X}^\top(\mathbf{P}-\mathbf{Y})\), so \(T\) steps cost \(O(Tndk)\) against the \(O(nd^2 + d^3)\) the closed form would have cost.

The class demo runs this update on MNIST digit images, plots training and validation loss, and visualizes the fitted weights.

From Linear to Nonlinear Boundaries

The decision boundary in the last figure is a hyperplane because each class score is linear in the input. Each column of \(\mathbf{W}\) provides one template for its class. That limit is why no linear model can separate data that is not linearly separable, like the XOR pattern on four points, which you will prove is out of reach next lecture. The Neural Networks unit begins there, stacking simple nonlinear pieces until the boundary can bend while retaining today’s softmax-and-cross-entropy output layer in many later classifiers.

The label distribution determines the likelihood and therefore the loss; the rest of the fitting machinery is unchanged.