Lecture notes · Foundations of Deep Learning · Chapter 5
Single-layer Networks: Classification
A classifier assigns an input \(\mathbf{x}\in\R^D\) to one of \(K\) classes. This chapter studies the models whose decision surfaces are hyperplanes: one layer of weights followed, at most, by a fixed output nonlinearity. It meets them three times. First as discriminant functions fitted directly (least squares). Then through decision theory, which says what an optimal decision is once the posterior probabilities are known, and how to measure a classifier (confusion matrix, precision, recall, ROC curve). Then as probabilistic models: generative (class densities plus Bayes' theorem, which produces a logistic sigmoid or softmax of linear functions) and discriminative (logistic, softmax and probit regression fitted by maximum likelihood). The chapter ends with the pairing of output activation and error function, the canonical link, that the rest of the book uses for deep networks. Every step the book leaves to the reader is written out below.
They follow the book. Sections carry the book's numbers (5.1, 5.4.3, ...) and every displayed equation that appears in the book carries the book's own equation number, e.g. (5.75), so the notes can be read next to the book. Equations without a number are steps that the book skips.
Filling the gaps. Wherever the book says that a result is easily verified, states a property without proof, or leaves it as an exercise, an orange Filling the gap box or a proof gives the complete argument. Proofs start hidden: open one with its bar, or use the button below.
Figures, code and demonstrations. Every figure of the chapter that is computed from a model or from data is reproduced from scratch by the Python code. The ▶ Demo boxes open an interactive demonstration already set to the case being discussed.
Main reference
C. M. Bishop and H. Bishop, Deep Learning: Foundations and Concepts, Springer (2024), Chapter 5, pages 131–169. Section, equation, figure and exercise numbers below refer to this book; its website is www.bishopbook.com. The exercises are compared with the official solutions manual (version 1.0).
The explanations, derivations, figures and code are my own; equations are cited by their numbers in the book.
Companion course
Most of this chapter overlaps the companion course Bayesian and Probabilistic Machine Learning (Bishop 2006), where several of these results are proved in full. Where the statement is the same, the notes below give it with a short proof and link the full derivation there.
Discriminant functions, least squares for classification: Section 4.1 (4.1.1–4.1.3) ↔ Section 5.1 here.
Decision theory (misclassification rate, expected loss, reject option, inference and decision): Section 1.5 ↔ Sections 5.2.1–5.2.4 here. Classifier accuracy and ROC curves (5.2.5, 5.2.6) are new in this book and are treated in full here.
5.1 A linear discriminant \(y(\mathbf{x})=\mathbf{w}^\T\mathbf{x}\)\({}+w_0\) cuts space with a hyperplane; \(y(\mathbf{x})/\|\mathbf{w}\|\) is the signed distance to it. \(K\) classes need \(K\) linear functions compared by "largest wins" (the regions are then convex); gluing two-class classifiers together leaves ambiguous regions. Least squares on 1-of-\(K\) targets has a closed form and its outputs sum to one, but it is not robust: far, correctly classified points pull the boundary.
5.2 With the posteriors \(p(\cC{k}\given\mathbf{x})\) known, the fewest mistakes come from choosing the largest posterior, the smallest expected loss from minimising \(\sum_kL_{kj}p(\cC{k}\given\mathbf{x})\), and rejecting where the largest posterior is below \(\theta\) lowers the error on the rest. Accuracy, precision, recall, the F-score and the ROC curve describe performance; the ROC curve of the posterior threshold dominates every other classifier (Neyman–Pearson) and its area is the probability that a positive scores above a negative.
5.3 Bayes' theorem writes the posterior as \(\sigma(a)\) or a softmax of \(a_k\)\({}=\ln p(\mathbf{x}\given\cC{k})p(\cC{k})\). Gaussian classes with a shared covariance, naive Bayes discrete features and exponential-family classes with a shared scale all make \(a_k\) linear in \(\mathbf{x}\); maximum likelihood gives class fractions, class means and the pooled covariance.
5.4 Fit the posterior directly: logistic regression has \(M\) parameters instead of \(M(M+5)/2+1\), a convex cross-entropy with gradient \(\sum_n(y_n-t_n)\bm\phi_n\), and no maximum on separable data. Softmax regression has the same gradient form, probit regression is less robust to mislabelled points, and the "error times input" gradient is a general consequence of the canonical link.
Notation. Inputs \(\mathbf{x}\in\R^D\), features \(\bm\phi=\bm\phi(\mathbf{x})\in\R^M\) (with \(\phi_0=1\) when a bias is wanted), training pairs \((\mathbf{x}_n,\mathbf{t}_n)\), \(n=1,\dots,N\), with \(N_k\) points in class \(\cC{k}\). Two-class targets are \(t\in\{0,1\}\); \(K\)-class targets use the 1-of-\(K\) code. \(\sigma(a)=1/(1+e^{-a})\) is the logistic sigmoid and \(\Phi(a)\) the standard normal distribution function. \(L_{kj}\) is the loss for deciding \(\cC{j}\) when the truth is \(\cC{k}\). \(\Ind[\cdot]\) is the indicator function.
Prerequisites. Linear regression and the pseudo-inverse (Chapter 4 of the book), Gaussian maximum likelihood and the exponential family (Chapter 3; companion course Chapter 2), the chain rule and gradients of quadratic forms.
Derivations start hidden: click any bar to open one.
pp. 131–132 The book distinguishes three ways to build a classifier, in increasing order of what they model: a discriminant function maps \(\mathbf{x}\) straight to a class; a discriminative probabilistic model represents \(p(\cC{k}\given\mathbf{x})\) directly; a generative probabilistic model represents \(p(\mathbf{x}\given\cC{k})\) and \(p(\cC{k})\) and obtains the posterior from Bayes' theorem,
See also: companion course, Section 4.1, discriminant functions (which also covers Fisher's discriminant and the perceptron, not in this book).
Definition 5.1 (decision regions, linear separability) pp. 131–132
A classifier splits the input space into decision regions \(\cR{k}\) (the inputs assigned to \(\cC{k}\)); their boundaries are decision boundaries or decision surfaces. The classifier is linear if the boundaries are pieces of hyperplanes, i.e. \((D-1)\)-dimensional affine subspaces. A two-class data set is linearly separable if there are \(\mathbf{w},w_0\) with \(\mathbf{w}^\T\mathbf{x}_n+w_0>0\) for every point of one class and \(<0\) for every point of the other.
5.1.1 Two classes
pp. 132–133 The simplest discriminant is an affine function of the input,
with the rule "assign \(\mathbf{x}\) to \(\cC{1}\) if \(y(\mathbf{x})\ge0\), otherwise to \(\cC{2}\)". The weight vector \(\mathbf{w}\) sets the orientation of the surface \(y(\mathbf{x})=0\) and the bias \(w_0\) its position.
Result 5.1 (geometry of a linear discriminant) pp. 132–133, (5.3)–(5.6), Figure 5.1
Assume \(\mathbf{w}\ne\mathbf{0}\). (a) \(\mathbf{w}\) is orthogonal to every vector lying in the surface \(y=0\). (b) For \(\mathbf{x}\) on the surface,
where \(\mathbf{x}_\perp\) is the point of the surface closest to \(\mathbf{x}\); \(|r|\) is the distance from \(\mathbf{x}\) to the surface and the sign of \(r\) says on which side \(\mathbf{x}\) lies. (d) With \(\tilde{\mathbf{w}}=(w_0,\mathbf{w})\) and \(\tilde{\mathbf{x}}=(1,\mathbf{x})\), \(y(\mathbf{x})\)\({}=\tilde{\mathbf{w}}^\T\tilde{\mathbf{x}}\) (5.6), and the surface becomes a hyperplane through the origin of \(\R^{D+1}\).
Proof
(a) If \(y(\mathbf{x}_A)=y(\mathbf{x}_B)=0\), subtracting gives \(\mathbf{w}^\T(\mathbf{x}_A\)\({}-\mathbf{x}_B)=0\), and every vector lying in the surface is such a difference. (b) Divide \(\mathbf{w}^\T\mathbf{x}+w_0=0\) by \(\|\mathbf{w}\|\); the left side of (5.3) is the component of \(\mathbf{x}\) along the unit normal, which is the same for every point of the surface, so it is the signed distance of the surface from the origin. (c) Put \(\mathbf{x}_\perp=\mathbf{x}\)\({}-r\mathbf{w}/\|\mathbf{w}\|\) with \(r=y(\mathbf{x})/\|\mathbf{w}\|\). Then \(y(\mathbf{x}_\perp)\)\({}=y(\mathbf{x})-r\|\mathbf{w}\|=0\), so \(\mathbf{x}_\perp\) lies on the surface. For any other point \(\mathbf{z}\) of the surface, \(\mathbf{x}-\mathbf{x}_\perp\) is parallel to \(\mathbf{w}\) and \(\mathbf{x}_\perp-\mathbf{z}\) is orthogonal to \(\mathbf{w}\) by (a), so by Pythagoras \(\|\mathbf{x}-\mathbf{z}\|^2\)\({}=r^2+\|\mathbf{x}_\perp\)\({}-\mathbf{z}\|^2\ge r^2\), with equality only at \(\mathbf{z}=\mathbf{x}_\perp\). (d) \(\tilde{\mathbf{w}}^\T\tilde{\mathbf{x}}\)\({}=w_0\cdot1+\mathbf{w}^\T\mathbf{x}\); the set \(\{\tilde{\mathbf{x}}:\tilde{\mathbf{w}}^\T\tilde{\mathbf{x}}\)\({}=0\}\) is a linear subspace of dimension \(D\). ∎
Figure 5.1. The geometry of Result 5.1 drawn for the actual discriminant \(\mathbf{w}=(1,1.6)\), \(w_0=-2.2\): the boundary is perpendicular to \(\mathbf{w}\), sits at signed distance \(-w_0/\|\mathbf{w}\|\) from the origin, and a point \(\mathbf{x}\) is at signed distance \(y(\mathbf{x})/\|\mathbf{w}\|\) from its projection \(\mathbf{x}_\perp\). Reproduces Bishop and Bishop (2024), Figure 5.1. Download: PDF · SVG
5.1.2 Multiple classes
pp. 134–135 Building a \(K\)-class classifier from two-class ones runs into trouble. A one-versus-the-rest scheme uses \(K-1\) classifiers "\(\cC{k}\) or not"; a one-versus-one scheme uses \(K(K-1)/2\) classifiers, one per pair, and a majority vote. Both leave regions where the class is not determined (Figure 5.2). A single \(K\)-class discriminant avoids this:
\[ y_k(\mathbf{x})=\mathbf{w}_k^\T\mathbf{x}+w_{k0},\qquad \text{assign }\mathbf{x}\text{ to }\cC{k}\text{ if }y_k(\mathbf{x})>y_j(\mathbf{x})\text{ for all }j\ne k, \tag{5.7} \]
and the boundary between \(\cC{k}\) and \(\cC{j}\) is the hyperplane
Filling the gap 5.1: why glued two-class classifiers leave ambiguous regions p. 134, Figure 5.2
The book shows pictures; here is the argument behind them, for \(D=2\) and \(K=3\).
Derivation
One versus the rest. Take the \(K-1=2\) classifiers \(y_1\) ("\(\cC{1}\) if \(y_1>0\)") and \(y_2\) ("\(\cC{2}\) if \(y_2>0\)"); a point that both reject is put in \(\cC{3}\). If the two lines are not parallel they cross, and the four sign patterns \((\pm,\pm)\) all occur, each on an unbounded wedge. On the wedge where \(y_1>0\) and \(y_2>0\) both classifiers claim the point: it is ambiguous. (With \(K\) classifiers, one per class, there is in addition a region claimed by nobody when the lines are in general position.) The ambiguity disappears only for special configurations, e.g. parallel lines oriented so that the "both" wedge is empty.
One versus one. For each pair \(i<j\) let \(s_{ij}(\mathbf{x})\) be affine, voting \(\cC{i}\) if \(s_{ij}>0\) and \(\cC{j}\) otherwise. At each \(\mathbf{x}\) the three votes form a tournament on three classes: either one class wins both its contests (a unique winner with two votes), or the votes are cyclic (\(\cC{1}\) beats \(\cC{2}\), \(\cC{2}\) beats \(\cC{3}\), \(\cC{3}\) beats \(\cC{1}\)) and every class has exactly one vote, a three-way tie. Three lines in general position bound a triangle, and the sign pattern inside it is the one obtained by flipping, relative to any outside cell, the signs of the lines one crosses to get in. Choosing the orientations so that the pattern inside is cyclic (our Figure 5.2 does this explicitly, with offsets \(+0.45,+0.45,-0.45\) of the three bisectors) produces a bounded ambiguous triangle. So majority voting is not well defined everywhere. ∎
Figure 5.2. Ambiguity when two-class discriminants are combined, drawn from actual linear functions. Left: one-versus-the-rest with two classifiers; the green wedge is claimed by both. Right: one-versus-one with three pairwise classifiers and a majority vote; inside the green triangle the votes are cyclic and every class gets one vote. Reproduces Bishop and Bishop (2024), Figure 5.2. Download: PDF · SVG
Result 5.2 (the regions of a linear \(K\)-class discriminant are convex) p. 135, (5.9), (5.10), Figure 5.3
Each decision region of (5.7) is an intersection of \(K-1\) open half-spaces, hence convex; in particular it is connected, and it has no holes.
Proof
By (5.7), \(\mathbf{x}\in\cR{k}\) if and only if \((\mathbf{w}_k\)\({}-\mathbf{w}_j)^\T\mathbf{x}+(w_{k0}\)\({}-w_{j0})>0\) for every \(j\ne k\): a finite intersection of open half-spaces, which is convex. The book's argument is the same fact written out: if \(\mathbf{x}_A,\mathbf{x}_B\in\cR{k}\) and \(\widehat{\mathbf{x}}\)\({}=\lambda\mathbf{x}_A+(1\)\({}-\lambda)\mathbf{x}_B\) with \(0\le\lambda\le1\) (5.9), linearity gives \(y_j(\widehat{\mathbf{x}})\)\({}=\lambda y_j(\mathbf{x}_A)+(1\)\({}-\lambda)y_j(\mathbf{x}_B)\) (5.10) for every \(j\), and a convex combination of the strict inequalities \(y_k>y_j\) at \(\mathbf{x}_A\) and \(\mathbf{x}_B\) is again strict. A convex set is path-connected (the segment is a path) and simply connected (every loop shrinks to a point along straight lines), which is what the book's "singly connected" means. ∎
A numerical test draws 1200 random segments with both ends in the same region of a random four-class discriminant and finds no segment that leaves its region.
Figure 5.3. The decision regions of a three-class linear discriminant (5.7) with our own weights; the segment from \(\mathbf{x}_A\) to \(\mathbf{x}_B\) stays inside \(\cR{k}\), as Result 5.2 says. Reproduces Bishop and Bishop (2024), Figure 5.3. Download: PDF · SVG
5.1.3 1-of-K coding
pp. 135–136 Two classes are coded by \(t\in\{0,1\}\) (\(t=1\) for \(\cC{1}\)). For \(K>2\) classes the 1-of-\(K\) or one-hot code uses a vector with a single 1 in the position of the class; for \(K=5\) and class 2,
\[ \mathbf{t}=(0,1,0,0,0)^\T. \tag{5.11} \]
Result 5.3 (the regression function of a 1-of-K target is the posterior; Exercise 5.1) p. 136
\(\E[\mathbf{t}\given\mathbf{x}]\)\({}=\big(p(\cC{1}\given\mathbf{x}),\dots,p(\cC{K}\given\mathbf{x})\big)^\T\). Consequently the function minimising the expected squared error \(\E\|\mathbf{y}(\mathbf{x})\)\({}-\mathbf{t}\|^2\) over all functions is the vector of posterior probabilities.
Proof
Component \(t_k\) is 1 exactly when the class is \(\cC{k}\), so \(\E[t_k\given\mathbf{x}]\)\({}=1\cdot p(\cC{k}\given\mathbf{x})\)\({}+0\cdot(1-p(\cC{k}\given\mathbf{x}))\). The second statement is the fact that the conditional mean minimises the expected squared error (companion course, Result 1.18): \(\E\|\mathbf{y}-\mathbf{t}\|^2\)\({}=\E\|\mathbf{y}(\mathbf{x})\)\({}-\E[\mathbf{t}\given\mathbf{x}]\|^2\)\({}+\E\|\mathbf{t}\)\({}-\E[\mathbf{t}\given\mathbf{x}]\|^2\), because the cross term has zero conditional mean. ∎
where column \(k\) of \(\widetilde{\mathbf{W}}\) is \(\tilde{\mathbf{w}}_k\)\({}=(w_{k0},\mathbf{w}_k^\T)^\T\), and classify by the largest \(y_k\). With \(\mathbf{T}\) the \(N\times K\) matrix of one-hot rows \(\mathbf{t}_n^\T\) and \(\widetilde{\mathbf{X}}\) the \(N\times(D+1)\) matrix of rows \(\tilde{\mathbf{x}}_n^\T\), the sum-of-squares error and its minimiser are
The book says "setting the derivative with respect to \(\widetilde{\mathbf{W}}\) to zero". Here is that derivative, and when the solution is unique.
Derivation
Write the trace as a double sum: \(E_D\)\({}=\tfrac12\sum_{n=1}^N\sum_{k=1}^K(\tilde{\mathbf{x}}_n^\T\tilde{\mathbf{w}}_k\)\({}-t_{nk})^2\). The \(K\) columns \(\tilde{\mathbf{w}}_k\) appear in separate terms, so the problem splits into \(K\) ordinary least-squares problems, one per class. Differentiating with respect to the entry \(\widetilde W_{ik}\) (input \(i\), class \(k\)) gives \(\partial E_D/\partial\widetilde W_{ik}\)\({}\)\({}=\sum_n\tilde x_{ni}(\tilde{\mathbf{x}}_n^\T\tilde{\mathbf{w}}_k\)\({}-t_{nk})\), which in matrix form is
\(E_D\) is a convex quadratic (its Hessian in each column is \(\widetilde{\mathbf{X}}^\T\widetilde{\mathbf{X}}\), positive semi-definite), so every stationary point is a global minimum, and the stationary points solve the normal equations \(\widetilde{\mathbf{X}}^\T\widetilde{\mathbf{X}}\widetilde{\mathbf{W}}\)\({}=\widetilde{\mathbf{X}}^\T\mathbf{T}\). If \(\widetilde{\mathbf{X}}\) has full column rank \(D+1\) (at least \(D+1\) inputs that are affinely independent), \(\widetilde{\mathbf{X}}^\T\widetilde{\mathbf{X}}\) is invertible and (5.15) is the unique solution; \(\widetilde{\mathbf{X}}^\dagger\)\({}=(\widetilde{\mathbf{X}}^\T\widetilde{\mathbf{X}})^{-1}\widetilde{\mathbf{X}}^\T\) is then the Moore–Penrose pseudo-inverse. Without full rank, \(\widetilde{\mathbf{X}}^\dagger\mathbf{T}\) (with the general pseudo-inverse) is the minimiser of smallest norm. Finally (5.16) is \(\widetilde{\mathbf{W}}^\T\tilde{\mathbf{x}}\)\({}=(\widetilde{\mathbf{X}}^\dagger\mathbf{T})^\T\tilde{\mathbf{x}}\). Both the gradient formula and the stationarity of (5.15) are checked against finite differences. ∎
Result 5.4 (linear constraints on the targets are inherited; Exercises 5.3, 5.4) p. 137, (5.17), (5.18)
Suppose \(\widetilde{\mathbf{X}}\) has full column rank and its first column is all ones (a bias input). If every target satisfies \(\mathbf{A}\mathbf{t}_n+\mathbf{b}\)\({}=\mathbf{0}\) (one or several linear constraints, the rows of \(\mathbf{A}\)), then the least-squares prediction satisfies
and likewise \(\mathbf{A}\mathbf{y}(\mathbf{x})\)\({}+\mathbf{b}=\mathbf{0}\). For one-hot targets (\(\mathbf{a}=\one\), \(b=-1\)) the \(K\) outputs therefore sum to one at every \(\mathbf{x}\), although they need not lie in \((0,1)\).
Proof
The constraints say \(\mathbf{T}\mathbf{A}^\T=\)\({}-\one_N\mathbf{b}^\T\), where \(\one_N\) is the column of \(N\) ones. Because the first column of \(\widetilde{\mathbf{X}}\) is \(\one_N\), we have \(\one_N\)\({}=\widetilde{\mathbf{X}}\mathbf{e}_1\) with \(\mathbf{e}_1=(1,0,\dots,0)^\T\), and full column rank gives \(\widetilde{\mathbf{X}}^\dagger\widetilde{\mathbf{X}}\)\({}=\mathbf{I}\), so \(\widetilde{\mathbf{X}}^\dagger\one_N\)\({}=\mathbf{e}_1\). Then
since the first entry of \(\tilde{\mathbf{x}}\) is 1. One constraint is the case of a single row. This route avoids the centring argument of the solutions manual and makes clear where the bias is needed: without a constant input, \(\one_N\) need not lie in the column space of \(\widetilde{\mathbf{X}}\) and the conclusion fails. ∎
Filling the gap 5.3: what least squares estimates, and why it is not robust pp. 136–137, Figure 5.4
The book says least squares "approximates the conditional expectation" and "gives too much weight to data points that are a long way from the decision boundary". Both statements can be made precise.
Derivation
What it estimates. By Result 5.3 the unrestricted minimiser of \(\E\|\mathbf{y}(\mathbf{x})\)\({}-\mathbf{t}\|^2\) is the posterior vector. Restricted to affine functions, the population minimiser is the \(L^2(p(\mathbf{x}))\) projection of \(\mathbf{x}\mapsto\E[\mathbf{t}\given\mathbf{x}]\) onto affine functions (expand the square as in Result 5.3: only the first term depends on \(\mathbf{y}\)). An affine function is unbounded unless it is constant, so the fitted "probabilities" leave \((0,1)\) far enough from the data, and a sigmoidal posterior is approximated by a straight line.
Why far points pull. Take two classes with targets \(t\in\{0,1\}\), a single output \(y\)\({}=\tilde{\mathbf{w}}^\T\tilde{\mathbf{x}}\) and the boundary \(y=\tfrac12\). The normal equations say \(\sum_n(y_n-t_n)\tilde{\mathbf{x}}_n\)\({}=\mathbf{0}\): every point pushes with a force proportional to its residual \(y_n-t_n\). A point of class 0 that lies at distance \(r\) beyond the boundary on its own (correct) side has \(y_n=\tfrac12-r\|\mathbf{w}\|\), so its residual \(-(r\|\mathbf{w}\|-\tfrac12)\) grows linearly with \(r\) once \(r\|\mathbf{w}\|>\tfrac12\): the better it is classified, the harder it pulls, and the boundary rotates to reduce these large residuals. For logistic regression (Section 5.4.3) the stationarity condition is again \(\sum_n(y_n-t_n)\bm\phi_n=\mathbf{0}\) but with \(y_n=\sigma(a_n)\); for the same point \(|y_n-t_n|=\sigma(a_n)\le e^{a_n}\) with \(a_n\to-\infty\), so its influence decays exponentially. In our Figure 5.4 data, adding ten such points rotates the least-squares boundary by 29 degrees and raises its training errors on the original 100 points from 2 to 10, while the logistic boundary does not move measurably: the far points have activations near \(-46\), so they contribute about \(e^{-46}\) to the gradient. ∎
Figure 5.4. Least squares (magenta) and logistic regression fitted by maximum likelihood (green) on 50 points per class drawn from two Gaussians with a common covariance (our own data). Right: ten extra blue points, all on the correct side, pull the least-squares boundary until it misclassifies ten of the original points; the logistic boundary does not move. Reproduces Bishop and Bishop (2024), Figure 5.4. Code: fig_5_4. Download: PDF · SVG
The failure is not surprising: least squares is maximum likelihood for Gaussian noise, and a 0/1 target is as far from Gaussian as a distribution can be. The probabilistic models of Sections 5.3 and 5.4 replace it.
pp. 138–139 Prediction splits into inference (learning \(p(\mathbf{x},\mathcal{C}_k)\) or \(p(\cC{k}\given\mathbf{x})\) from data, the hard part) and decision (choosing an action given those probabilities, usually easy). The running example is a skin-lesion image \(\mathbf{x}\), with \(\cC{1}\) = no cancer ("normal") and \(\cC{2}\) = cancer. Bayes' theorem,
turns the prior \(p(\cC{k})\) (how common cancer is before the image is seen) into the posterior. (The book writes "\(p(\cC{1})\) represents the probability that a person has cancer"; with its own labelling that is \(p(\cC{2})\). See the corrections.)
5.2.1 Misclassification rate
pp. 139–140 A decision rule is a partition of input space into regions \(\cR{1},\dots,\cR{K}\). For two classes
Result 5.5 (the largest posterior gives the fewest mistakes) p. 140
Among all decision rules, including randomised ones, \(p(\text{correct})\) is maximised by assigning each \(\mathbf{x}\) to a class with the largest posterior \(p(\cC{k}\given\mathbf{x})\), and the minimum probability of a mistake is \(1\)\({}-\int\max_kp(\mathbf{x},\cC{k})\,\d\mathbf{x}\); for two classes, \(\int\min\{p(\mathbf{x},\cC{1}),p(\mathbf{x},\cC{2})\}\,\d\mathbf{x}\). Any rule that differs from it on a set of positive probability, where the largest posterior is unique, does strictly worse.
Proof
A (possibly randomised) rule assigns \(\mathbf{x}\) to \(\cC{k}\) with probability \(\delta_k(\mathbf{x})\ge0\), \(\sum_k\delta_k=1\); a deterministic rule has \(\delta_k=\Ind[\mathbf{x}\in\cR{k}]\). Then \(p(\text{correct})\)\({}=\int\sum_k\delta_k(\mathbf{x})p(\mathbf{x},\cC{k})\,\d\mathbf{x}\). For each \(\mathbf{x}\) the integrand is a weighted average of the numbers \(p(\mathbf{x},\cC{k})\), so it is at most \(\max_kp(\mathbf{x},\cC{k})\), with equality exactly when all the weight sits on maximising classes. Integrating gives the bound, attained by the argmax rule. Since \(p(\mathbf{x},\cC{k})\)\({}=p(\cC{k}\given\mathbf{x})p(\mathbf{x})\) with a factor \(p(\mathbf{x})\ge0\) common to all \(k\), maximising the joint is maximising the posterior. If another rule puts weight on a non-maximising class on a set of positive probability where the maximum is unique, the integrand is strictly smaller there and the integral strictly smaller. For two classes, \(1-\max(a,b)\) integrated against \(p(\mathbf{x})\) is \(\int\min\) of the two joints, because \(p(\mathbf{x},\cC{1})\)\({}+p(\mathbf{x},\cC{2})=p(\mathbf{x})\). ∎
Figure 5.5. Joint densities \(p(x,\cC{1})=0.42\,\N(x\given\)\({}-1.2,0.55^2)\)\({}+0.23\,\N(x\given1.5,0.6^2)\) and \(p(x,\cC{2})=0.35\,\N(x\given1.7,0.7^2)\) (our choice). The probability of a mistake is the shaded area: green and blue do not depend on the boundary \(\widehat{x}\) within the overlap, the red area does. (a) \(\widehat{x}=x_0+0.75\). (b) \(\widehat{x}=x_0\), the crossing point: the red area vanishes and the error is minimal, as Result 5.5 says. Reproduces Bishop and Bishop (2024), Figure 5.5. Download: PDF · SVG
▶ DemoMinimum misclassification rate (Fig 5.5)Move the threshold by hand and watch the error area and the expected-loss curve; the optimum sits where the joint densities cross.
5.2.2 Expected loss
pp. 140–142 When mistakes have different costs, a loss matrix \(L_{kj}\) (true class \(k\), decision \(j\)) records them; for the screening problem the book uses the matrix of Figure 5.6. The average loss of a rule with regions \(\cR{j}\) is
Figure 5.6. The screening loss matrix: rows are the true class, columns the decision. A false alarm costs 1, a missed cancer 100, a correct decision nothing. (A table, typeset here.) Reproduces Bishop and Bishop (2024), Figure 5.6.
Result 5.6 (minimum expected loss; Exercises 5.7, 5.8) p. 142, (5.23)
The expected loss (5.22) is minimised by assigning each \(\mathbf{x}\) to a class \(j\) that minimises
so with the matrix of Figure 5.6, "cancer" as soon as \(p(\cC{2}\given\mathbf{x})\ge1/101\)\({}\approx0.0099\). For \(L_{kj}=1-I_{kj}\), (5.23) is \(1-p(\cC{j}\given\mathbf{x})\) and the rule is that of Result 5.5.
Proof
Exactly as in Result 5.5: for a randomised rule \(\delta_j(\mathbf{x})\), \(\E[L]\)\({}=\int\sum_j\delta_j(\mathbf{x})\,r_j(\mathbf{x})\,p(\mathbf{x})\,\d\mathbf{x}\) with \(r_j(\mathbf{x})\)\({}=\sum_kL_{kj}p(\cC{k}\given\mathbf{x})\), the conditional risk of decision \(j\). The integrand is at least \(\min_jr_j(\mathbf{x})\,p(\mathbf{x})\), attained by putting all weight on a minimising \(j\). Two classes: \(r_1=L_{21}p(\cC{2}\given\mathbf{x})\), \(r_2=L_{12}p(\cC{1}\given\mathbf{x})\), so \(r_2\le r_1\) if and only if \(L_{12}(1-p_2)\le L_{21}p_2\), i.e. \(p_2\ge L_{12}/(L_{12}+L_{21})\), writing \(p_2=p(\cC{2}\given\mathbf{x})\). For \(L_{kj}=1-I_{kj}\), \(r_j\)\({}=\sum_{k\ne j}p(\cC{k}\given\mathbf{x})\)\({}=1-p(\cC{j}\given\mathbf{x})\). ∎
The rule needs only the posteriors; if the loss matrix changes, the decisions change with no retraining. A direct computation confirms on the demo's one-dimensional problem that \(\tau^\star\) beats 99 other thresholds.
pp. 142–143 Where the largest posterior is well below one, decisions are unreliable. The reject option refuses to decide (e.g. sends the case to a human) when \(\max_kp(\cC{k}\given\mathbf{x})\)\({}\le\theta\).
Result 5.7 (the reject option; Exercise 5.10) p. 143, Figure 5.7
(a) \(\theta=1\) rejects every input; any \(\theta<1/K\) rejects none. (b) If rejecting costs \(\lambda\) and deciding \(j\) costs \(L_{kj}\) when the truth is \(k\), the minimum-expected-loss rule is: compute \(r_j(\mathbf{x})\)\({}=\sum_kL_{kj}p(\cC{k}\given\mathbf{x})\); decide \(\argmin_jr_j\) if \(\min_jr_j(\mathbf{x})<\lambda\), otherwise reject. (c) For \(L_{kj}=1-I_{kj}\) this is the threshold rule with \(\theta=1-\lambda\).
Proof
(a) The posteriors are \(K\) numbers summing to one, so the largest is at least \(1/K>\theta\); and it is at most \(1=\theta\). (b) Rejection is one more action with conditional risk \(\lambda\) (the same whatever the class); by the pointwise argument of Result 5.6 the best action at \(\mathbf{x}\) is the one with the smallest conditional risk among \(r_1(\mathbf{x}),\dots,r_K(\mathbf{x}),\lambda\). (c) Then \(\min_jr_j=1\)\({}-\max_jp(\cC{j}\given\mathbf{x})\), and \(1-\max_jp_j<\lambda\) if and only if \(\max_jp_j>1-\lambda\). (At equality both actions have the same risk; the convention of rejecting on \(\max\le\theta\) breaks the tie towards rejection.) ∎
Filling the gap 5.4: rejecting lowers the error on the inputs that are kept p. 142
The book motivates rejection by "a lower error rate on those examples for which a classification decision is made". This is true for every threshold, not just on average.
Derivation
Let \(M=\max_kp(\cC{k}\given\mathbf{x})\) for \(\mathbf{x}\sim p(\mathbf{x})\). With the largest-posterior decision, the probability of a mistake at \(\mathbf{x}\) is \(1-M\), so the error rate on the accepted inputs is \(e(\theta)=\E[1-M\given M>\theta]\). Take \(\theta<\theta'\) with \(P(M>\theta')>0\). The event \(\{M>\theta\}\) is the disjoint union of \(\{M>\theta'\}\) and \(\{\theta<M\le\theta'\}\), so \(e(\theta)\) is a weighted average of \(\E[1-M\given M>\theta']\le1-\theta'\) and \(\E[1-M\given\theta<M\le\theta']\ge1\)\({}-\theta'\). An average of two numbers lies between them, hence \(e(\theta)\ge e(\theta')\): raising \(\theta\) never increases the error on the kept inputs. For the demo's problem (\(d=1.5\)) the error on kept inputs falls from 0.226 at \(\theta=0.5\) to 0.029 at \(\theta=0.95\). ∎
Figure 5.7. Posteriors for \(p(x\given\cC{k})=\N(x\given\mp1,1)\) with equal priors, so \(p(\cC{1}\given x)=\sigma(-2x)\). With \(\theta=0.85\) the inputs with \(|x|\le\tfrac12\ln(\theta/(1-\theta))\)\({}=0.87\) are rejected. Reproduces Bishop and Bishop (2024), Figure 5.7. Download: PDF · SVG
▶ DemoReject option, theta = 0.9 (Fig 5.7)The amber band is rejected; the scoreboard shows the rejected fraction and the error on the decided cases.
5.2.4 Inference and decision
pp. 143–147 There are three ways to solve a classification problem: (a) generative: model \(p(\mathbf{x}\given\cC{k})\) and \(p(\cC{k})\), then use
(b) discriminative: model \(p(\cC{k}\given\mathbf{x})\) directly; (c) a discriminant function \(f(\mathbf{x})\) that outputs a class, with no probabilities. (a) is the most demanding but also gives \(p(\mathbf{x})\), useful for novelty detection. Much of the structure of \(p(\mathbf{x}\given\cC{k})\) may be irrelevant to the posterior (Figure 5.8). Posteriors, however, are worth having: for minimising risk when the loss matrix changes, for the reject option, for correcting for class priors, and for combining models.
Figure 5.8. Class densities \(p(x\given\cC{1})=0.4\,\N(0.2,0.1^2)\)\({}+0.6\,\N(0.5,0.12^2)\) and \(p(x\given\cC{2})=\N(0.7,0.12^2)\) (our choice) and the posteriors for equal priors. The left mode of \(p(x\given\cC{1})\) leaves no trace on the posteriors, which are flat there; the green line is the minimum-error boundary. Reproduces Bishop and Bishop (2024), Figure 5.8. Download: PDF · SVG
▶ DemoA far mode that does not matter (Fig 5.8)Class C1 gets a second mode at x = -3: the posterior, the boundary and the errors in the overlap region do not change.
Filling the gap 5.5: correcting for class priors, and combining models pp. 145–147, (5.26), (5.27)
The book describes both procedures in words; here are the formulas, the assumptions they need, and the proofs.
Derivation
Prior correction. Suppose the model was trained on a re-balanced data set with class fractions \(\pi'_k\) (e.g. equal), whereas the population has priors \(\pi_k\). The assumption that makes correction possible is that re-balancing samples whole classes, so the class-conditional densities \(p(\mathbf{x}\given\cC{k})\) are the same in both. Then the trained model approximates \(p'(\cC{k}\given\mathbf{x})\)\({}=p(\mathbf{x}\given\cC{k})\pi'_k/Z'(\mathbf{x})\), and
because the common factor \(Z'(\mathbf{x})\) cancels: divide by the training fractions, multiply by the population priors, normalise. A discriminant function has no posterior to correct, which is the book's point.
Combining models. Assume conditional independence given the class, \(p(\mathbf{x}_I,\mathbf{x}_B\given\cC{k})\)\({}=p(\mathbf{x}_I\given\cC{k})p(\mathbf{x}_B\given\cC{k})\) (5.26). By Bayes' theorem \(p(\mathbf{x}_I\given\cC{k})\)\({}=p(\cC{k}\given\mathbf{x}_I)p(\mathbf{x}_I)/p(\cC{k})\), and likewise for \(\mathbf{x}_B\), so
the proportionality being in \(k\), so normalising over \(k\) gives the posterior. The joint marginal \(p(\mathbf{x}_I,\mathbf{x}_B)\)\({}=\sum_kp(\mathbf{x}_I\given\cC{k})p(\mathbf{x}_B\given\cC{k})p(\cC{k})\) is a mixture of products, which is not itself a product unless, for instance, one of the factors does not depend on \(k\). Both formulas are checked exactly (to \(10^{-13}\)) against direct Bayes computations. ∎
5.2.5 Classifier accuracy
pp. 147–148 Call "cancer" the positive class. Each tested person is a true positive, false positive (type 1 error), true negative or false negative (type 2 error), with counts adding to
Precision estimates \(P(\text{cancer}\given\text{test positive})\), recall (the true positive rate, sensitivity) \(P(\text{test positive}\given\text{cancer})\), the false positive rate \(P(\text{test positive}\given\text{normal})\). Accuracy is misleading with rare classes: if 1 in 1000 has cancer, "nobody has cancer" is 99.9% accurate and useless.
true \ decided
normal
cancer
normal
\(N_\mathrm{TN}\)
\(N_\mathrm{FP}\)
cancer
\(N_\mathrm{FN}\)
\(N_\mathrm{TP}\)
Figure 5.9. The confusion matrix, laid out like the loss matrix of Figure 5.6. Multiplying the two entrywise and summing gives the total loss. (A table, typeset here.) Reproduces Bishop and Bishop (2024), Figure 5.9.
Result 5.8 (the F-score; Exercise 5.5) p. 150, (5.38), (5.39)
The F-score is the harmonic mean of precision \(P\) and recall \(R\) (the book's text says "geometric mean", a slip):
It satisfies \(\min(P,R)\le F\le\sqrt{PR}\le(P+R)/2\), so it is dominated by the worse of the two.
Proof
With \(a=N_\mathrm{TP}\), \(P=a/(a+N_\mathrm{FP})\), \(R=a/(a+N_\mathrm{FN})\): \(1/P+1/R=(2a+N_\mathrm{FP}\)\({}+N_\mathrm{FN})/a\), so \(F=2/(1/P+1/R)=2a/(2a+N_\mathrm{FP}\)\({}+N_\mathrm{FN})\); and \(2PR/(P+R)=2/(1/R+1/P)\) is the same number. The harmonic mean of two positive numbers is at least their minimum (each reciprocal is at most \(1/\min\)), and HM \(\le\) GM \(\le\) AM: \(\sqrt{PR}-2PR/(P+R)=\sqrt{PR}(\sqrt P\)\({}-\sqrt R)^2/(P+R)\ge0\), and \((P+R)/2-\sqrt{PR}=(\sqrt P\)\({}-\sqrt R)^2/2\ge0\). For \(P=0.9\), \(R=0.1\) the harmonic mean is 0.18 but the geometric mean 0.30, so the two names are not interchangeable. ∎
Filling the gap 5.6: the labelled regions of Figure 5.10 p. 148, (5.34)–(5.37)
The book lists \(N_\mathrm{FP}/N=E\), \(N_\mathrm{TP}/N=D+E\), \(N_\mathrm{FN}/N=B+C\), \(N_\mathrm{TN}/N=A+C\) without comment. They hold, but the regions overlap in a way worth seeing.
Derivation
One-dimensional input, \(\cC{2}\) = cancer, rule "cancer if \(x\ge\widehat{x}\)", so \(\cR{1}=\{x<\widehat{x}\}\). Write \(j_k(x)=p(x,\cC{k})\) and \(m=\min(j_1,j_2)\). The letters denote areas: on \(\cR{1}\), \(C=\int_{\cR{1}}m\) (green), \(A=\int_{\cR{1}}(j_1-m)\) (under \(j_1\), above green) and \(B=\int_{\cR{1}}(j_2-m)\) (red); on \(\cR{2}\), where the figure has \(j_2\ge j_1\), \(E=\int_{\cR{2}}j_1\) (blue) and \(D=\int_{\cR{2}}(j_2-j_1)\). As \(N\to\infty\) the law of large numbers turns each count fraction into a probability:
The green area \(C\) and the blue area \(E\) lie under both curves, so they are counted twice: the four fractions sum to 1, hence \(A+B+2C+D+2E=1\), not \(A+B+C+D+E=1\). For our Figure 5.10, \((A,B,C,D,E)\)\({}=(0.431,0.030,0.105,0.101,0.113)\) and the identity holds to \(10^{-6}\). ∎
Figure 5.10. The densities of Figure 5.5(a) with the areas \(A\)–\(E\) of (5.34)–(5.37); \(\cR{1}\) is "normal", \(\cR{2}\) "cancer". Reproduces Bishop and Bishop (2024), Figure 5.10. Download: PDF · SVG
▶ DemoRare disease: accuracy misleads (Section 5.2.5)At a prevalence of 0.1% the minimum-error rule hardly ever says "cancer": accuracy near 99.9%, recall near zero; raise the loss of a miss and watch recall and precision trade off.
5.2.6 ROC curve
pp. 148–150 A probabilistic classifier says "positive" when its output exceeds a threshold. Sweeping the threshold from \(+\infty\) to \(-\infty\) traces the receiver operating characteristic (ROC) curve: true positive rate against false positive rate. The point \((0,0)\) is "everyone normal", \((1,1)\) "everyone positive", \((0,1)\) perfection; one confusion matrix is one point. The area under the curve (AUC) summarises it.
Result 5.9 (properties of ROC curves) pp. 148–150
Let a classifier have score \(s(\mathbf{x})\), and write \(S_+\), \(S_-\) for the score of a random positive and of a random negative (independent).
Random guessing, "positive with probability \(\rho\)" regardless of \(\mathbf{x}\), has TPR = FPR = \(\rho\): sweeping \(\rho\) gives the diagonal.
AUC as a probability. \(\text{AUC}=P(S_+>S_-)+\tfrac12P(S_+\)\({}=S_-)\). So AUC = 1/2 for a score unrelated to the class and 1 for a perfectly separating one.
Prior invariance. TPR and FPR are conditional on the class, so the ROC curve depends only on \(p(\mathbf{x}\given\cC{k})\), not on the prevalence.
Optimality (Neyman–Pearson). Among all rules, randomised or not, with false positive rate at most \(\alpha\), the largest true positive rate is achieved by thresholding the likelihood ratio \(\ell(\mathbf{x})\)\({}=p(\mathbf{x}\given\cC{2})/p(\mathbf{x}\given\cC{1})\), equivalently the posterior \(p(\cC{2}\given\mathbf{x})\). Its ROC curve lies on or above the ROC curve of every other classifier, and it is concave.
Operating point. The expected loss \(\E[L]=L_{12}p(\cC{1})\,\mathrm{FPR}\)\({}+L_{21}p(\cC{2})\,(1-\mathrm{TPR})\) is minimised on the optimal curve where its slope equals \(L_{12}p(\cC{1})/(L_{21}p(\cC{2}))\), which is the threshold \(\tau^\star\) of Result 5.6.
Proof
(1) The decision is independent of the class, so \(P(\text{positive}\given\cC{2})\)\({}=P(\text{positive}\given\cC{1})=\rho\).
(2) For continuous scores, at threshold \(c\): \(\mathrm{FPR}(c)=P(S_->c)\), \(\mathrm{TPR}(c)=P(S_+>c)\). As \(c\) decreases, FPR increases, and \(\d\,\mathrm{FPR}=f_-(c)\,(-\d c)\) with \(f_-\) the density of \(S_-\). Hence \(\text{AUC}\)\({}=\int\mathrm{TPR}\,\d\,\mathrm{FPR}\)\({}=\int_{-\infty}^{\infty}P(S_+\)\({}>c)f_-(c)\,\d c=P(S_+>S_-)\) by independence. With ties (finite samples) the ROC curve moves diagonally across a tied block, and the trapezoid it adds counts each tied pair as one half; this is the Mann–Whitney statistic (Hanley and McNeil 1982). The trapezoidal area and the pair count on 1000 scores agree to \(10^{-12}\).
(3) Immediate from the definitions. In terms of the posterior, changing the prior only relabels the thresholds (\(p(\cC{2}\given\mathbf{x})\ge\tau\) is \(\ell(\mathbf{x})\ge k\) with \(k=\tau p(\cC{1})/((1-\tau)p(\cC{2}))\)), so the set of rules, and the curve, is the same.
(4) Let \(\delta^\star(\mathbf{x})\)\({}=\Ind[\ell(\mathbf{x})>k]\), randomised on \(\{\ell=k\}\) so that its FPR is exactly \(\alpha\), and let \(\delta\) be any rule with FPR \(\le\alpha\). Writing \(p_k(\mathbf{x})\)\({}=p(\mathbf{x}\given\cC{k})\), the function \((\delta^\star-\delta)(p_2-kp_1)\) is non-negative everywhere: where \(p_2>kp_1\), \(\delta^\star=1\ge\delta\); where \(p_2<kp_1\), \(\delta^\star=0\le\delta\). Integrating, \(\mathrm{TPR}^\star-\mathrm{TPR}\)\({}\ge k(\mathrm{FPR}^\star-\mathrm{FPR})\)\({}=k(\alpha-\mathrm{FPR})\ge0\). The posterior is an increasing function of \(\ell\), so thresholding it gives the same rules. Concavity: randomising between two rules on the optimal curve achieves every point on the chord between them; since the optimal curve is the largest achievable TPR at each FPR, it lies above its chords. A numerical example exhibits a case with unequal class variances where the optimal region is two-sided and beats every one-sided rule \(x\ge c\) at the same FPR (TPR 0.653 against 0.629 at FPR 0.2).
(5) Minimising a linear function of \((\mathrm{FPR},\mathrm{TPR})\) over a concave curve picks the point where the curve is tangent to the level lines \(\mathrm{TPR}\)\({}=\mathrm{FPR}\cdot L_{12}p(\cC{1})/(L_{21}p(\cC{2}))\)\({}+\const\). Along the likelihood-ratio curve, \(\d\,\mathrm{TPR}/\d\,\mathrm{FPR}\)\({}=p_2(\mathbf{x})/p_1(\mathbf{x})=k\) at the boundary, so \(k=L_{12}p(\cC{1})/(L_{21}p(\cC{2}))\), which in terms of the posterior is \(\tau=L_{12}/(L_{12}+L_{21})\). ∎
Filling the gap 5.7: the ROC curve of a Gaussian score Figure 5.11
The book draws two ROC curves without saying where they come from. Ours are exact curves of a simple model.
Derivation
Let the score be \(\N(0,1)\) for negatives and \(\N(d,1)\) for positives (for two Gaussian classes with a shared covariance, the activation \(a(\mathbf{x})\) of Section 5.3.1 is exactly of this form, with \(d\) the Mahalanobis distance between the means). At threshold \(c\), \(\mathrm{FPR}=1-\Phi(c)\) and \(\mathrm{TPR}=1-\Phi(c-d)=\Phi(d-c)\). Eliminating \(c=\Phi^{-1}(1-\mathrm{FPR})=\)\({}-\Phi^{-1}(\mathrm{FPR})\):
since \(S_+-S_-\sim\N(d,2)\). For \(d=2\), AUC = 0.921; for \(d=0.9\), 0.738. ∎
Figure 5.11. ROC curves of two classifiers whose scores are Gaussian (Filling the gap 5.7) with separations \(d=2\) (blue) and \(d=0.9\) (red); the dashed diagonal is random guessing. Reproduces Bishop and Bishop (2024), Figure 5.11. Download: PDF · SVG
A loss matrix and a confusion matrix combine into the empirical loss by multiplying entrywise and summing. ROC curves extend to more classes but quickly become unwieldy.
These rewrites are content-free until \(a\) has a constrained form; the rest of the section finds class densities that make it linear.
Result 5.10 (properties of the sigmoid and the softmax; Exercises 5.11, 5.18) pp. 151–152, (5.43), (5.44), (5.72)
\(\sigma(-a)=1-\sigma(a)\) (5.43), \(\sigma'(a)=\sigma(a)(1-\sigma(a))\) (5.72), and the inverse is the logit \(a=\ln\{\sigma/(1-\sigma)\}\) (5.44), the log odds \(\ln\{p(\cC{1}\given\mathbf{x})/p(\cC{2}\given\mathbf{x})\}\).
The softmax is unchanged if the same constant is added to every \(a_k\); with \(K=2\) it is \(\sigma(a_1-a_2)\).
If \(a_k>a_j+\Delta\) for all \(j\ne k\), then \(p(\cC{k}\given\mathbf{x})>1-(K\)\({}-1)e^{-\Delta}\): the softmax is a smoothed "max", and \(\mathrm{softmax}(\mathbf{a}/T)\) tends to the indicator of the largest \(a_k\) as the temperature \(T\to0\).
Proof
(1) \(1-\sigma(a)=\frac{e^{-a}}{1+e^{-a}}\)\({}=\frac1{e^a+1}=\sigma(-a)\). Differentiating, \(\sigma'(a)=\frac{e^{-a}}{(1+e^{-a})^2}\)\({}=\sigma(a)\,\frac{e^{-a}}{1+e^{-a}}\)\({}=\sigma(a)(1-\sigma(a))\). Solving \(y=1/(1+e^{-a})\): \(e^{-a}=(1-y)/y\), so \(a=\ln\{y/(1-y)\}\); \(\sigma\) is strictly increasing (\(\sigma'>0\)), so this inverse is unique. (2) \(e^{a_k+c}/\sum_je^{a_j+c}\)\({}=e^{a_k}/\sum_je^{a_j}\); and \(e^{a_1}/(e^{a_1}+e^{a_2})=1/(1\)\({}+e^{-(a_1-a_2)})\). (3) \(1-p(\cC{k}\given\mathbf{x})\)\({}=\sum_{j\ne k}e^{a_j-a_k}/(1\)\({}+\sum_{j\ne k}e^{a_j-a_k})\)\({}<\sum_{j\ne k}e^{a_j-a_k}<(K\)\({}-1)e^{-\Delta}\); dividing \(\mathbf{a}\) by \(T\) multiplies \(\Delta\) by \(1/T\). ∎
Figure 5.12. The logistic sigmoid \(\sigma(a)\) (red) and the probit \(\Phi(\lambda a)\) with \(\lambda^2=\pi/8\) (dashed blue), which has the same slope at \(a=0\) (Exercise 5.24); the largest vertical gap is 0.018. Reproduces Bishop and Bishop (2024), Figure 5.12. Download: PDF · SVG
(Strictly, (5.46) gives \(a_k\) plus a term common to all classes, which the softmax ignores; (5.51) is \(a_k\) with that term dropped.) The priors enter only the biases, so changing them moves every contour of constant posterior parallel to itself.
Proof
Substitute (5.47) into (5.41). The normalising constants are the same for both classes and cancel, leaving
Expand each quadratic with the symmetry of \(\bm\Sigma^{-1}\): \((\mathbf{x}\)\({}-\bm\mu)^\T\bm\Sigma^{-1}(\mathbf{x}\)\({}-\bm\mu)\)\({}\)\({}=\mathbf{x}^\T\bm\Sigma^{-1}\mathbf{x}\)\({}-2\bm\mu^\T\bm\Sigma^{-1}\mathbf{x}\)\({}+\bm\mu^\T\bm\Sigma^{-1}\bm\mu\). The terms \(\mp\tfrac12\mathbf{x}^\T\bm\Sigma^{-1}\mathbf{x}\) cancel because the covariance is shared; the linear terms give \((\bm\mu_1\)\({}-\bm\mu_2)^\T\bm\Sigma^{-1}\mathbf{x}\)\({}=\mathbf{w}^\T\mathbf{x}\); the constants give \(w_0\). For \(K\) classes, \(\ln\{p(\mathbf{x}\given\cC{k})p(\cC{k})\}\)\({}=g(\mathbf{x})\)\({}+\bm\mu_k^\T\bm\Sigma^{-1}\mathbf{x}\)\({}-\tfrac12\bm\mu_k^\T\bm\Sigma^{-1}\bm\mu_k\)\({}+\ln p(\cC{k})\) with \(g(\mathbf{x})=\)\({}-\tfrac12\mathbf{x}^\T\bm\Sigma^{-1}\mathbf{x}\)\({}-\tfrac D2\ln2\pi\)\({}-\tfrac12\ln|\bm\Sigma|\) the same for all \(k\); by Result 5.10(2) it may be dropped. Changing \(p(\cC{1})\) to \(p'(\cC{1})\) adds \(\ln\{p'(\cC{1})p(\cC{2})/(p(\cC{1})p'(\cC{2}))\}\) to \(w_0\) and leaves \(\mathbf{w}\) alone; the contour \(\sigma(\mathbf{w}^\T\mathbf{x}+w_0)=c\) is the hyperplane \(\mathbf{w}^\T\mathbf{x}=\sigma^{-1}(c)\)\({}-w_0\), whose normal does not change. ∎
Filling the gap 5.8: different covariances give quadratic boundaries p. 153, Figure 5.14
The book says only that the cancellation "will no longer occur". Here is the resulting discriminant.
Derivation
With \(p(\mathbf{x}\given\cC{k})\)\({}=\N(\mathbf{x}\given\bm\mu_k,\bm\Sigma_k)\), dropping the common \(-\tfrac D2\ln2\pi\):
The boundary between \(\cC{k}\) and \(\cC{j}\), \(a_k=a_j\), is \(\tfrac12\mathbf{x}^\T(\bm\Sigma_j^{-1}\)\({}-\bm\Sigma_k^{-1})\mathbf{x}\)\({}+(\bm\Sigma_k^{-1}\bm\mu_k\)\({}-\bm\Sigma_j^{-1}\bm\mu_j)^\T\mathbf{x}\)\({}+c_{kj}=0\): a quadric (in the plane, a conic: ellipse, parabola, hyperbola or pair of lines), which reduces to a hyperplane exactly when \(\bm\Sigma_k=\bm\Sigma_j\). That is why, in Figure 5.14, the red–blue boundary is straight while the boundaries with the green class curve. When the quadratic form is indefinite the region of a class can be disconnected (a hyperbola has two branches), unlike the convex regions of Result 5.2. A direct computation verifies that the log odds of two Gaussians with different covariances is fitted exactly by a quadratic in \(\mathbf{x}\) (residual \(10^{-12}\)) and not by an affine function. ∎
Figure 5.13. Left: two Gaussian class densities with means \((\mp0.7,\pm0.4)\) and the shared covariance \(\bigl(\begin{smallmatrix}1&0.45\\0.45&0.8\end{smallmatrix}\bigr)\). Right: the posterior \(p(\cC{1}\given\mathbf{x})\)\({}=\sigma(\mathbf{w}^\T\mathbf{x}+w_0)\) for equal priors, coloured by the proportion of red ink \(p(\cC{1}\given\mathbf{x})\); it is constant along lines perpendicular to \(\mathbf{w}=\bm\Sigma^{-1}(\bm\mu_1\)\({}-\bm\mu_2)\). Reproduces Bishop and Bishop (2024), Figure 5.13. Download: PDF · SVG
Figure 5.14. Three Gaussian classes with equal priors (our parameters); red and blue share a covariance, green has its own. Right: each pixel mixes red, blue and green in proportion to the three posteriors; the white boundaries are linear between red and blue and quadratic with green (Filling the gap 5.8). Reproduces Bishop and Bishop (2024), Figure 5.14. Download: PDF · SVG
Result 5.12 (maximum likelihood for the shared-covariance model; Exercises 5.13, 5.14) pp. 155–156, (5.55)–(5.63), (5.101)–(5.105)
For \(K\) classes with 1-of-\(K\) targets \(t_{nk}\) and \(N_k=\sum_nt_{nk}\), the maximum-likelihood estimates are the class fractions, the class means and the pooled covariance:
For two classes these are (5.56), (5.58), (5.59) and (5.61)–(5.63). Like every Gaussian maximum-likelihood fit, it is not robust to outliers.
Proof (sketch; full version in the companion course, Result 4.10)
The log likelihood is \(\sum_n\sum_kt_{nk}\{\ln\pi_k\)\({}+\ln\N(\mathbf{x}_n\given\bm\mu_k,\bm\Sigma)\}\), a sum of a part in \(\bm\pi\), parts in each \(\bm\mu_k\) and a part in \(\bm\Sigma\). Priors: maximise \(\sum_kN_k\ln\pi_k\) subject to \(\sum_k\pi_k=1\); the Lagrangian condition \(N_k/\pi_k+\lambda=0\) gives \(\pi_k=-N_k/\lambda\), and summing over \(k\) gives \(\lambda=-N\). (It is the maximum: \(\sum_kN_k\ln\pi_k\) is concave, or, by Gibbs' inequality, \(\sum_k\frac{N_k}N\ln\frac{N_k/N}{\pi_k}\)\({}\ge0\).) Means: the gradient \(\sum_nt_{nk}\bm\Sigma^{-1}(\mathbf{x}_n\)\({}-\bm\mu_k)\) vanishes at the class mean, the maximiser of a concave quadratic. Covariance: with the means plugged in, the \(\bm\Sigma\)-dependent part is \(-\frac N2\ln|\bm\Sigma|\)\({}-\frac12\sum_n\sum_kt_{nk}(\mathbf{x}_n\)\({}-\bm\mu_k)^\T\bm\Sigma^{-1}(\mathbf{x}_n\)\({}-\bm\mu_k)\)\({}=-\frac N2\big\{\ln|\bm\Sigma|\)\({}+\Tr(\bm\Sigma^{-1}\mathbf{S})\big\}\) (5.60) with \(\mathbf{S}=\sum_k(N_k/N)\mathbf{S}_k\), using \(\mathbf{v}^\T\mathbf{A}\mathbf{v}\)\({}=\Tr(\mathbf{A}\mathbf{v}\mathbf{v}^\T)\). In terms of \(\bm\Lambda=\bm\Sigma^{-1}\) this is \(\frac N2\{\ln|\bm\Lambda|\)\({}-\Tr(\bm\Lambda\mathbf{S})\}\), concave in \(\bm\Lambda\), with gradient \(\frac N2(\bm\Lambda^{-1}-\mathbf{S})\), zero at \(\bm\Sigma=\mathbf{S}\). A computation confirms by finite differences that the log likelihood is stationary there, and by a numerical maximisation over all covariance matrices (Cholesky parametrisation) that \(\mathbf{S}\) is the maximiser. ∎
p. 156 For \(D\) binary features a general class-conditional table has \(2^D-1\) free numbers per class. The naive Bayes assumption, features independent given the class, cuts this to \(D\):
Result 5.13 (naive Bayes is linear, and its maximum-likelihood fit is counting; Exercises 5.15–5.17) p. 156
(a) \(a_k(\mathbf{x})\)\({}=\sum_ix_i\ln\frac{\mu_{ki}}{1-\mu_{ki}}\)\({}+\sum_i\ln(1-\mu_{ki})+\ln p(\cC{k})\) is affine in \(\mathbf{x}\). (b) The maximum-likelihood estimate is \(\mu_{ki}\)\({}=\frac1{N_k}\sum_{n\in\cC{k}}x_{ni}\), the fraction of class-\(k\) points with \(x_i=1\). (c) For \(M\) features with \(L\) states each, coded 1-of-\(L\) as \(\phi_{ml}\in\{0,1\}\), \(a_k=\sum_m\sum_l\phi_{ml}\ln\mu_{kml}\)\({}+\ln p(\cC{k})\) is linear in the codes, and \(\mu_{kml}=N_{kml}/N_k\), where \(N_{kml}\) counts the class-\(k\) points whose feature \(m\) is in state \(l\).
Proof
(a) Regroup (5.65). (b) The log likelihood \(\sum_n\sum_kt_{nk}\ln p(\mathbf{x}_n\given\cC{k})\)\({}+\dots\) splits over classes and features; for one pair \((k,i)\) it is \(n_1\ln\mu+n_0\ln(1-\mu)\) with \(n_1\) (\(n_0\)) the number of class-\(k\) points with \(x_i=1\) (0). Its derivative \(n_1/\mu-n_0/(1-\mu)\) vanishes at \(\mu=n_1/(n_0+n_1)=n_1/N_k\), and the function is concave. (c) \(p(\bm\phi_m\given\cC{k})\)\({}=\prod_l\mu_{kml}^{\phi_{ml}}\), so the log is linear in the \(\phi_{ml}\). Maximise \(\sum_lN_{kml}\ln\mu_{kml}\) subject to \(\sum_l\mu_{kml}=1\), separately for each \(k,m\): the Lagrange condition \(N_{kml}/\mu_{kml}+\lambda_{km}=0\) and the constraint give \(\lambda_{km}=-N_k\) and \(\mu_{kml}=N_{kml}/N_k\). (Estimates of exactly 0 make \(\ln\mu\) infinite; in practice one adds pseudo-counts, which is what the smooth argument of naive_bayes_fit does.) ∎
Corrections. The book prints (5.67) and (5.68) without the factor \(1/s\) (the same slip was corrected in the errata of Bishop 2006, (4.85)–(4.86)), and writes the prefactor of (5.66) as \(1/s\), which normalises the density only for \(D=1\). Neither affects linearity.
Proof
\(\ln\{p(\mathbf{x}\given\bm\lambda_k,s)p(\cC{k})\}\)\({}=\ln\{s^{-D}h(\mathbf{x}/s)\}\)\({}+\ln g(\bm\lambda_k)\)\({}+\frac1s\bm\lambda_k^\T\mathbf{x}\)\({}+\ln p(\cC{k})\). The first term is the same for every class, so it cancels from \(a_1-a_2\) and from the softmax. The prefactor. With \(\mathbf{u}=\mathbf{x}/s\), \(\d\mathbf{x}=s^D\d\mathbf{u}\), so \(\int s^{-D}h(\mathbf{x}/s)g(\bm\lambda)e^{\bm\lambda^\T\mathbf{x}/s}\d\mathbf{x}\)\({}=\int h(\mathbf{u})g(\bm\lambda)e^{\bm\lambda^\T\mathbf{u}}\d\mathbf{u}\)\({}=1\) when \(g(\bm\lambda)\) normalises the \(s=1\) family; with \(1/s\) instead of \(1/s^D\) the total mass would be \(s^{D-1}\). Examples. A 1-D Gaussian \(\N(x\given s\lambda,s^2)\) is of this form with \(h=\N(\cdot\given0,1)\), \(g(\lambda)=e^{-\lambda^2/2}\); computing its log odds directly gives \((\lambda_1-\lambda_2)x/s+\dots\) exact, while the printed form is wrong by more than 0.5 at \(s=2\). Gaussians with a shared covariance are the case \(s=1\), \(\bm\lambda_k=\bm\Sigma^{-1}\bm\mu_k\), \(g(\bm\lambda)\)\({}=\exp(-\tfrac12\bm\lambda^\T\bm\Sigma\bm\lambda)\), and give back (5.52)–(5.53); a Bernoulli feature has \(\lambda=\ln\{\mu/(1-\mu)\}\), \(g=1-\mu\), and gives (5.65). ∎
p. 157 Instead of fitting class densities and applying Bayes' theorem, fit the generalised linear form of the posterior directly by maximising the conditional likelihood \(\prod_np(t_n\given\mathbf{x}_n)\). This needs fewer parameters and is not hurt when the class densities are not of the assumed form.
5.4.1 Activation functions
p. 158 Pass the linear function through a nonlinear activation function \(f\):
(The book's (5.70) is misprinted as \(f(\mathbf{w}^\T\mathbf{w}+w+0)\).) The inverse \(f^{-1}\) is the link function of statistics, and (5.70) is a generalised linear model (McCullagh and Nelder 1989): linear decision surfaces, but a likelihood that is no longer quadratic in the parameters.
Filling the gap 5.9: when are the decision surfaces of (5.70) linear? p. 158
Derivation
A decision surface is a level set \(\{\mathbf{x}:f(a(\mathbf{x}))=c\}\) with \(a(\mathbf{x})=\mathbf{w}^\T\mathbf{x}\)\({}+w_0\). It equals \(\{\mathbf{x}:a(\mathbf{x})\in f^{-1}(c)\}\), a union of parallel hyperplanes \(a(\mathbf{x})=a^\ast\), one for each \(a^\ast\) in the preimage. If \(f\) is strictly monotone (the sigmoid, the probit, the identity), the preimage is a single point and the surface is one hyperplane, which is the book's claim; for a non-monotone \(f\) (say \(f(a)=a^2\)) one level set can be two hyperplanes, still flat but not a single boundary. In all cases the dependence on \(\mathbf{x}\) is through \(a(\mathbf{x})\) only, so the surfaces are parallel to each other. ∎
pp. 158–159 Everything above works with a fixed nonlinear feature map \(\bm\phi(\mathbf{x})\), usually with \(\phi_0=1\): boundaries linear in \(\bm\phi\) are curved in \(\mathbf{x}\) (Figure 5.15). But a feature map cannot remove class overlap.
Result 5.15 (features cannot lower the Bayes error) p. 158
Let \(\mathbf{z}=\bm\phi(\mathbf{x})\) for a measurable map \(\bm\phi\). The minimum probability of a mistake achievable from \(\mathbf{z}\) is at least that achievable from \(\mathbf{x}\), with equality if \(\bm\phi\) is one-to-one (more generally, if \(p(\cC{k}\given\mathbf{x})\) depends on \(\mathbf{x}\) only through \(\bm\phi(\mathbf{x})\)). A non-injective \(\bm\phi\) can create overlap where there was none.
Proof
Short proof. Any rule \(g\) acting on \(\mathbf{z}\) defines the rule \(g\circ\bm\phi\) acting on \(\mathbf{x}\), with the same error; so the best \(\mathbf{z}\)-rule is no better than the best \(\mathbf{x}\)-rule. Quantitative form. By the tower property, \(p(\cC{k}\given\mathbf{z})\)\({}=\E[p(\cC{k}\given\mathbf{x})\given\bm\phi(\mathbf{x})\)\({}=\mathbf{z}]\). By Result 5.5 the Bayes errors are \(1-\E\max_kp(\cC{k}\given\mathbf{x})\) and \(1-\E\max_kp(\cC{k}\given\mathbf{z})\). The function \(\mathbf{p}\mapsto\max_kp_k\) is convex, so by Jensen's inequality \(\max_k\E[p(\cC{k}\given\mathbf{x})\given\mathbf{z}]\)\({}\le\E[\max_kp(\cC{k}\given\mathbf{x})\given\mathbf{z}]\); take expectations. Equality holds when the posterior is a function of \(\mathbf{z}\), in particular when \(\bm\phi\) is injective. Created overlap. Let \(x\) be \(+1\) for \(\cC{1}\) and \(-1\) for \(\cC{2}\) (no overlap) and \(\phi(x)=x^2=1\) for both: from \(\phi\) the posteriors are the priors. ∎
Figure 5.15. Our data: a red class around the origin and a blue class in two clusters. The Gaussian basis functions \(\phi_j(\mathbf{x})=\exp(-\|\mathbf{x}\)\({}-\bm\mu_j\|^2/(2s^2))\), \(\bm\mu_1=(-1,-1)\), \(\bm\mu_2=(0,0)\), \(s^2=0.5\) (green crosses; circles at \(\phi_j=0.5\) and \(0.1\)) map the data to the right panel, where logistic regression finds a straight boundary; back in input space it is the closed black curve. The classes are separable in feature space, so we added a small weight decay \(0.01\|\mathbf{w}\|^2/2\) to keep \(\mathbf{w}\) finite (Result 5.17). Reproduces Bishop and Bishop (2024), Figure 5.15. Download: PDF · SVG
▶ DemoGaussian basis functions (Fig 5.15)Switch the features between the raw inputs and the two Gaussian basis functions: no line works in x-space, a line works in feature space.
Fixed basis functions have serious limitations in high dimensions; later chapters let the network learn them.
with \(M\) parameters for \(M\) features, against \(2M+M(M+1)/2+1=M(M+5)/2+1\) for the Gaussian generative model (two means, a shared covariance, a prior). For \(t_n\in\{0,1\}\) and \(y_n=\sigma(a_n)\), \(a_n=\mathbf{w}^\T\bm\phi_n\), the likelihood and the cross-entropy error are
with \(\mathbf{R}=\diag(y_n(1-y_n))\). The Hessian is positive semi-definite, and positive definite when \(\bm\Phi\) has full column rank, so \(E\) is convex (strictly convex in the full-rank case): any stationary point is the global minimum, and Newton's method on it is the IRLS algorithm.
Proof
Per data point, \(\partial E/\partial y_n=-t_n/y_n+(1\)\({}-t_n)/(1-y_n)=(y_n-t_n)/\{y_n(1-y_n)\}\); by (5.72) \(\partial y_n/\partial a_n=y_n(1-y_n)\); and \(\nabla a_n=\bm\phi_n\). The chain rule multiplies the three and the factor \(y_n(1-y_n)\) cancels, which is the point of the book's remark. Differentiating \(\sum_n(y_n-t_n)\bm\phi_n\) once more gives \(\sum_ny_n(1-y_n)\bm\phi_n\bm\phi_n^\T\). For any \(\mathbf{u}\), \(\mathbf{u}^\T\bm\Phi^\T\mathbf{R}\bm\Phi\mathbf{u}\)\({}=\sum_ny_n(1\)\({}-y_n)(\bm\phi_n^\T\mathbf{u})^2\ge0\), with equality only if \(\bm\Phi\mathbf{u}=\mathbf{0}\), since every \(y_n\in(0,1)\). A twice-differentiable function with a positive semi-definite Hessian everywhere is convex. The IRLS update \(\mathbf{w}\leftarrow\mathbf{w}-(\bm\Phi^\T\mathbf{R}\bm\Phi)^{-1}\bm\Phi^\T(\mathbf{y}-\mathbf{t})\) is derived in the companion course (Filling the gap 4.6). The gradient is checked against torch.autograd and the Hessian against finite differences; on random data IRLS converges in 5 steps to the point that 20000 steps of gradient descent reach. ∎
The gradient (5.75) has the same "error times input" form as the sum-of-squares gradient of linear regression (Section 4.1.3 of the book); Section 5.4.6 explains why. Each term \(\nabla E_n=(y_n-t_n)\bm\phi_n\) is what stochastic gradient descent uses.
Result 5.17 (maximum likelihood on separable data; Exercise 5.20) p. 161
Write \(\tilde t_n=2t_n-1\in\{-1,+1\}\). (a) If the data are linearly separable in feature space (some \(\hat{\mathbf{w}}\) has \(\tilde t_n\hat{\mathbf{w}}^\T\bm\phi_n\)\({}>0\) for all \(n\)), then \(E(\mathbf{w})>0\) for every \(\mathbf{w}\), \(E(\kappa\hat{\mathbf{w}})\to0\) as \(\kappa\to\infty\), so the likelihood has supremum 1 and no maximiser; every sequence with \(E(\mathbf{w}_j)\to0\) has \(\|\mathbf{w}_j\|\to\infty\), and every separating direction gives such a sequence. (b) Conversely, if no \(\mathbf{w}\ne\mathbf{0}\) satisfies \(\tilde t_n\mathbf{w}^\T\bm\phi_n\ge0\) for all \(n\), then \(E\) is coercive and a maximum-likelihood solution exists.
Proof
Each term of (5.74) equals \(\ln(1+e^{-\tilde t_na_n})\), which is positive for every finite \(a_n\). (a) Along \(\kappa\hat{\mathbf{w}}\), each term is \(\ln(1+e^{-\kappa c_n})\) with \(c_n\)\({}=\tilde t_n\hat{\mathbf{w}}^\T\bm\phi_n\)\({}>0\), decreasing to 0. If a sequence with \(E(\mathbf{w}_j)\to0\) had a bounded subsequence, a further subsequence would converge to some \(\mathbf{w}^\ast\) with \(E(\mathbf{w}^\ast)=0\) by continuity, which is impossible; so \(\|\mathbf{w}_j\|\to\infty\). The limiting probabilities at the training points are \(\sigma(\pm\infty)\in\{0,1\}\) for every separating direction, which is why maximum likelihood cannot prefer one separating hyperplane to another. (b) The function \(\mathbf{u}\mapsto\max_n(-\tilde t_n\mathbf{u}^\T\bm\phi_n)\) is continuous and, by assumption, positive on the unit sphere, which is compact; so it has a positive minimum \(\delta\). For \(\mathbf{w}=r\mathbf{u}\) some term of \(E\) is at least \(\ln(1+e^{r\delta})\ge r\delta\), so \(E(\mathbf{w})\)\({}\ge\delta\|\mathbf{w}\|\to\infty\). A continuous coercive function attains its minimum. ∎
Filling the gap 5.10: what gradient descent does on separable data p. 161
The book says that the solution found "will depend on the choice of optimization algorithm". For batch gradient descent one can say exactly what happens to the error and the norm.
Derivation
The Hessian satisfies \(\bm\Phi^\T\mathbf{R}\bm\Phi\preceq\frac14\bm\Phi^\T\bm\Phi\), so \(\nabla E\) is Lipschitz with constant \(L=\frac14\|\bm\Phi\|_2^2\). For a convex \(L\)-smooth function and step \(\eta\le1/L\), the iterates \(\mathbf{w}_{t+1}=\mathbf{w}_t\)\({}-\eta\nabla E(\mathbf{w}_t)\) satisfy, for every comparison point \(\mathbf{u}\),
(Proof: the descent lemma gives \(E(\mathbf{w}_{t+1})\le E(\mathbf{w}_t)\)\({}-\frac\eta2\|\nabla E(\mathbf{w}_t)\|^2\); convexity gives \(E(\mathbf{w}_t)\le E(\mathbf{u})\)\({}+\nabla E(\mathbf{w}_t)^\T(\mathbf{w}_t\)\({}-\mathbf{u})\); combining, \(E(\mathbf{w}_{t+1})\le E(\mathbf{u})\)\({}+\frac1{2\eta}(\|\mathbf{w}_t\)\({}-\mathbf{u}\|^2-\|\mathbf{w}_{t+1}\)\({}-\mathbf{u}\|^2)\); sum over \(t\), telescope, and use that \(E(\mathbf{w}_t)\) is non-increasing.) Take \(\mathbf{w}_0=\mathbf{0}\) and \(\mathbf{u}=\kappa\hat{\mathbf{w}}\) with \(\hat{\mathbf{w}}\) separating with margin \(c=\min_nc_n>0\): then \(E(\mathbf{w}_t)\le Ne^{-\kappa c}\)\({}+\kappa^2\|\hat{\mathbf{w}}\|^2/(2\eta t)\). Choosing \(\kappa=\ln t/c\) gives \(E(\mathbf{w}_t)=O((\ln t)^2/t)\to0\), and by Result 5.17(a), \(\|\mathbf{w}_t\|\to\infty\). Since \(E(\mathbf{w})\ge\ln(1\)\({}+e^{-\|\mathbf{w}\|\max_n\|\bm\phi_n\|})\)\({}\ge e^{-\|\mathbf{w}\|\max_n\|\bm\phi_n\|}/2\) (for \(\|\mathbf{w}\|\) large), \(E\to0\) at rate \(1/t\) up to logs forces \(\|\mathbf{w}_t\|\) to grow at least like \(\ln t\): slow, unbounded growth, which is what the demo shows on a logarithmic iteration axis. A weight-decay term \(\frac\alpha2\|\mathbf{w}\|^2\) makes the error coercive and restores a unique finite minimiser (Chapter 9 of the book). ∎
where \(w_{ki}\) is the weight from feature \(i\) to output \(k\). The Jacobian \(\mathbf{J}=\diag(\mathbf{y})\)\({}-\mathbf{y}\mathbf{y}^\T\) is symmetric positive semi-definite with \(\mathbf{J}\one=\mathbf{0}\); \(E\) is convex in \((\mathbf{w}_1,\dots,\mathbf{w}_K)\) but never strictly convex, because adding the same vector \(\mathbf{v}\) to every \(\mathbf{w}_k\) changes nothing. With \(K=2\) the model is logistic regression with \(\mathbf{w}=\mathbf{w}_1-\mathbf{w}_2\).
Proof
Jacobian. With \(Z=\sum_ie^{a_i}\): \(\partial y_k/\partial a_k=e^{a_k}/Z\)\({}-e^{2a_k}/Z^2=y_k(1-y_k)\), and for \(j\ne k\), \(\partial y_k/\partial a_j=\)\({}-e^{a_k}e^{a_j}/Z^2=-y_ky_j\). Both cases are \(y_k(I_{kj}-y_j)\). For any \(\mathbf{u}\), \(\mathbf{u}^\T\mathbf{J}\mathbf{u}\)\({}=\sum_ky_ku_k^2-(\sum_ky_ku_k)^2\), the variance of \(u_k\) under the distribution \(\mathbf{y}\), hence \(\ge0\), and zero exactly when \(\mathbf{u}\) is constant: \(\mathbf{J}\one=\mathbf{0}\). Gradient. Per data point, \(\partial E_n/\partial y_{nk}=\)\({}-t_{nk}/y_{nk}\), so \(\partial E_n/\partial a_{nj}\)\({}=\sum_k(-t_{nk}/y_{nk})\,y_{nk}(I_{kj}\)\({}-y_{nj})=-t_{nj}+y_{nj}\sum_kt_{nk}\)\({}=y_{nj}-t_{nj}\), using \(\sum_kt_{nk}=1\); then \(\nabla_{\mathbf{w}_j}a_{nj}=\bm\phi_n\). Component \(i\) of this is (5.82) (the book's (5.82) has \(w_{ij}\) on the left and \(k\) on the right; the indices must match). Convexity. The Hessian of \(E_n\) in the stacked weights is \(\mathbf{J}_n\otimes\bm\phi_n\bm\phi_n^\T\), a Kronecker product of positive semi-definite matrices, hence positive semi-definite; the shift \(\mathbf{w}_k\mapsto\mathbf{w}_k\)\({}+\mathbf{v}\) adds \(\mathbf{v}^\T\bm\phi\) to every \(a_k\), which the softmax ignores (Result 5.10), so the minimiser is never unique without a constraint or weight decay. \(K=2\): Result 5.10(2). All of this is checked against torch.autograd. ∎
Figure 5.16. Multi-class logistic regression as a network with a single layer of weights: one node per basis function (the filled node is \(\phi_0=1\), the bias), one node per output \(y_1,\dots,y_K\) (the book's caption says \(y_N\)), one link per weight \(w_{ki}\). By (5.82) the gradient for a link is the input at its left end times the error \(y_{nk}-t_{nk}\) at its right end, the pattern that backpropagation generalises. (A diagram, redrawn.) Reproduces Bishop and Bishop (2024), Figure 5.16.
pp. 163–164 Other activation functions arise from a noisy threshold model: with \(a_n=\mathbf{w}^\T\bm\phi_n\), set \(t_n=1\) if \(a_n\ge\theta\) and \(t_n=0\) otherwise, where the threshold \(\theta\) is random with density \(p(\theta)\). Then
Result 5.19 (the threshold model, erf, and the probit approximation; Exercises 5.23, 5.24) pp. 163–164, (5.87), (5.88), Figure 5.12
\(p(t=1\given a)=P(\theta\le a)=f(a)\), the distribution function of \(\theta\). A Gaussian threshold \(\N(m,s^2)\) gives \(\Phi((a-m)/s)\), which is the standard probit model with weights \(\mathbf{w}/s\) and the bias shifted by \(-m/s\): nothing new.
With the book's definition \(\erf(a)\)\({}=\frac2{\sqrt\pi}\int_0^a\exp(-\theta^2/2)\,\d\theta\) (5.87),
\[ \Phi(a)=\frac12\Big\{1+\frac1{\sqrt2}\erf(a)\Big\}. \tag{5.88} \]
The error function of numerical libraries has \(\exp(-\theta^2)\) in the integrand; with it, \(\Phi(a)=\tfrac12\{1+\erf(a/\sqrt2)\}\). The two are related by \(\erf_{\text{book}}(a)\)\({}=\sqrt2\,\erf(a/\sqrt2)\), so the book's version tends to \(\sqrt2\), not 1.
\(\Phi(\lambda a)\) and \(\sigma(a)\) have the same slope at \(a=0\) exactly when \(\lambda^2=\pi/8\); then \(\max_a|\sigma(a)-\Phi(\lambda a)|\)\({}\approx0.018\).
Proof
(1) \(t=1\) if and only if \(\theta\le a\), and \(P(\theta\le a)\)\({}=\int_{-\infty}^ap(\theta)\d\theta\). If \(\theta\sim\N(m,s^2)\), \(P(\theta\le a)=\Phi((a-m)/s)\), and \((a-m)/s=(\mathbf{w}/s)^\T\bm\phi-m/s\) is again linear in \(\bm\phi\) (absorb \(-m/s\) in the bias weight). (2) By symmetry of the standard normal, \(\Phi(a)=\tfrac12\)\({}+\frac1{\sqrt{2\pi}}\int_0^ae^{-\theta^2/2}\d\theta\) for every real \(a\) (for \(a<0\) the integral is negative), and \(\frac1{\sqrt{2\pi}}\)\({}=\frac12\cdot\frac1{\sqrt2}\cdot\frac2{\sqrt\pi}\), which is (5.88). Substituting \(\theta=\sqrt2u\) instead, \(\frac1{\sqrt{2\pi}}\int_0^ae^{-\theta^2/2}\d\theta\)\({}=\frac1{\sqrt\pi}\int_0^{a/\sqrt2}e^{-u^2}\d u\)\({}=\tfrac12\erf(a/\sqrt2)\) with the library erf; comparing the two expressions gives the conversion. (3) \(\sigma'(0)=\tfrac14\) by Result 5.10, and \(\frac{\d}{\d a}\Phi(\lambda a)\big|_0\)\({}=\lambda\N(0\given0,1)\)\({}=\lambda/\sqrt{2\pi}\); equality gives \(\lambda=\sqrt{2\pi}/4\), \(\lambda^2=2\pi/16=\pi/8\). The maximum gap is computed on a fine grid. ∎
Figure 5.17. A threshold density \(p(\theta)=0.7\,\N(1.5,0.4^2)\)\({}+0.3\,\N(3.1,0.32^2)\) (blue) and its distribution function \(f(a)\) (red), the activation function of the corresponding threshold model. At the green line \(a=2.8\), the red value is the shaded area and the red slope is the blue value. Reproduces Bishop and Bishop (2024), Figure 5.17. Download: PDF · SVG
Filling the gap 5.11: tails, and why the probit model is less robust to mislabelled points p. 164
The book says the logistic tails decay like \(\exp(-x)\) and the probit tails "like \(\exp(-x^2)\)", hence the probit model "can be significantly more sensitive to outliers". The precise tail is \(e^{-x^2/2}/x\), and the mechanism is the size of the gradient.
Derivation
Tails. \(\sigma(-x)=1/(1+e^x)\sim e^{-x}\). For the normal tail with \(\varphi=\N(\cdot\given0,1)\) and \(x>0\): since \(u/x\ge1\) for \(u\ge x\) and \(u\varphi(u)=-\varphi'(u)\), \(1-\Phi(x)=\int_x^\infty\varphi\)\({}\le\frac1x\int_x^\infty u\varphi(u)\d u\)\({}=\varphi(x)/x\). Since \(\frac{\d}{\d u}\{-\varphi(u)/u\}=(1\)\({}+u^{-2})\varphi(u)\), \(\varphi(x)/x=\int_x^\infty(1\)\({}+u^{-2})\varphi\le(1+x^{-2})(1\)\({}-\Phi(x))\). Together,
Influence of one mislabelled point. Take a point with \(t=1\) whose activation is \(a=-r\), \(r\) large (it lies far on the wrong side). Its error term and its derivative with respect to \(a\) are
The last ratio, the inverse Mills ratio, lies between \(r\) and \(r+1/r\) by the tail bounds. So in the gradient \(\sum_n(\partial E_n/\partial a_n)\bm\phi_n\) the logistic model caps every point's weight at \(\|\bm\phi_n\|\), while the probit model lets a point's weight grow in proportion to how wrong it is: the fit is dragged towards the mislabelled point. A numerical computation confirms the ratio \(\varphi(r)/(r\Phi(-r))\to1\) and finds that one mislabelled point at \(x_1=10\) moves the probit boundary about nine times as far as the logistic one (0.20 against 0.02). ∎
Away from such points, probit and logistic fits are usually close: by Result 5.19(3) a probit weight vector is roughly \(\lambda=0.63\) times the logistic one.
pp. 164–165 Linear regression with Gaussian noise, logistic regression with the cross-entropy and softmax regression with the multi-class cross-entropy all have gradient "error \(y_n-t_n\) times feature \(\bm\phi_n\)". The reason is a matching of the activation function to an exponential-family distribution of the target,
with conditional mean \(y=\E[t\given\eta]\) related to \(\eta\) by \(\eta=\psi(y)\), and a generalised linear model \(y=f(\mathbf{w}^\T\bm\phi)\) (5.91) (Nelder and Wedderburn 1972).
Result 5.20 (the canonical link gives the error-times-feature gradient) pp. 164–165, (5.90)–(5.95)
\(y\equiv\E[t\given\eta]=\)\({}-s\frac{\d}{\d\eta}\ln g(\eta)\) (5.90), and \(\frac{\d y}{\d\eta}\)\({}=\var[t\given\eta]/s\ge0\), so \(\psi\) is increasing.
For \(N\) observations with a common \(s\), \(\ln p(\mathbf{t}\given\bm\eta,s)\)\({}=\sum_n\{\ln g(\eta_n)+\eta_nt_n/s\}\)\({}+\const\) (5.92) and, with \(a_n=\mathbf{w}^\T\bm\phi_n\), \(y_n=f(a_n)\),
\[ \nabla_{\mathbf{w}}\ln p(\mathbf{t}\given\bm\eta,s)=\sum_{n=1}^N\frac1s\{t_n-y_n\}\,\psi'(y_n)\,f'(a_n)\,\bm\phi_n. \tag{5.93} \]
If the activation is the inverse of \(\psi\), the canonical link \(f^{-1}(y)=\psi(y)\) (5.94), then \(\eta_n=a_n\), \(\psi'(y_n)f'(a_n)=1\), and for the error \(E=-\ln p\)
\[ \nabla E(\mathbf{w})=\frac1s\sum_{n=1}^N\{y_n-t_n\}\bm\phi_n,\qquad \nabla\nabla E(\mathbf{w})=\frac1{s}\sum_{n=1}^Nf'(a_n)\bm\phi_n\bm\phi_n^\T\succeq0. \tag{5.95} \]
So with the canonical link the negative log likelihood is always convex. (The book's (5.95) writes \(\nabla\ln E\); the gradient of \(E\) is meant.)
Proof
(1) Normalisation: \(g(\eta)\int\frac1sh(t/s)e^{\eta t/s}\d t\)\({}=1\), so \(\ln g(\eta)=-\ln Z(\eta)\) with \(Z(\eta)\)\({}=\int\frac1sh(t/s)e^{\eta t/s}\d t\). Differentiating under the integral, \(Z'(\eta)/Z(\eta)=\E[t]/s\), so \(\E[t]=s(\ln Z)'=-s(\ln g)'\). Differentiating once more, \((\ln Z)''=\E[t^2]/s^2-(\E[t]/s)^2\)\({}=\var[t]/s^2\), so \(\d y/\d\eta=s(\ln Z)''=\var[t]/s\). (2) By (1), \(\frac{\d}{\d\eta_n}\{\ln g(\eta_n)\)\({}+\eta_nt_n/s\}=(t_n-y_n)/s\); the chain rule through \(\eta_n=\psi(y_n)\), \(y_n=f(a_n)\), \(a_n=\mathbf{w}^\T\bm\phi_n\) gives (5.93). (3) If \(f=\psi^{-1}\) then \(\psi(f(a))=a\), so \(\psi'(y)f'(a)=1\) and \(\eta_n=a_n\); negate (5.93). Differentiating \(\frac1s\sum_n(f(a_n)-t_n)\bm\phi_n\) again gives the Hessian, and \(f'(a)=\d y/\d\eta=\var[t]/s\ge0\) by (1). Examples (all checked numerically): Bernoulli, \(p(t\given\eta)=\sigma(-\eta)e^{\eta t}\), \(s=1\), \(g=\sigma(-\eta)\), mean \(\sigma(\eta)\): canonical link the logit, activation the sigmoid, (5.75). Gaussian with variance \(s\), \(g(\eta)=e^{-\eta^2/(2s)}\): mean \(\eta\), identity link, linear regression. Poisson, \(g(\eta)=\exp(-e^\eta)\), \(s=1\): mean \(e^\eta\), log link. The probit link is not canonical for the Bernoulli, and its gradient is not of the error-times-feature form (companion course, Filling the gap 4.7). ∎
The pairing of output activation and error function (identity with sum of squares, sigmoid with binary cross-entropy, softmax with multi-class cross-entropy) carries over unchanged to the output layer of the deep networks of the following chapters, where the output "delta" \(y_n-t_n\) starts backpropagation.
Exercises
Each exercise is restated in my own words with the book's number and difficulty; the solutions are my own, compared afterwards with the official solutions manual. Where a solution there has a slip, a short note says so (see also Corrections). "Companion" links point to the same exercise in Bishop (2006).
Exercise 5.1 (★). With 1-of-\(K\) targets, show that \(\E[\mathbf{t}\given\mathbf{x}]\) is the vector of posterior probabilities.
Solution
\(t_k\in\{0,1\}\) and \(t_k=1\) exactly when the class is \(\cC{k}\), so \(\E[t_k\given\mathbf{x}]=P(t_k\)\({}=1\given\mathbf{x})\)\({}=p(\cC{k}\given\mathbf{x})\). See Result 5.3. (Agrees with the manual.)
Exercise 5.2 (★★). The convex hull of \(\{\mathbf{x}_n\}\) is the set of all \(\sum_n\alpha_n\mathbf{x}_n\) with \(\alpha_n\ge0\), \(\sum_n\alpha_n=1\). Two point sets are linearly separable if some \(\hat{\mathbf{w}},w_0\) have \(\hat{\mathbf{w}}^\T\mathbf{x}_n+w_0\)\({}>0\) for all \(\mathbf{x}_n\) and \(\hat{\mathbf{w}}^\T\mathbf{y}_m+w_0\)\({}<0\) for all \(\mathbf{y}_m\). Show that intersecting hulls rule out separability, and that separable sets have disjoint hulls. (Companion: Exercise 4.1.)
Solution
Suppose \(\mathbf{z}=\sum_n\alpha_n\mathbf{x}_n\)\({}=\sum_m\beta_m\mathbf{y}_m\) lies in both hulls and \((\hat{\mathbf{w}},w_0)\) separates. Because the weights sum to one, \(\hat{\mathbf{w}}^\T\mathbf{z}+w_0\)\({}=\sum_n\alpha_n(\hat{\mathbf{w}}^\T\mathbf{x}_n\)\({}+w_0)>0\) (a convex combination of positive numbers, with at least one \(\alpha_n>0\)), and by the same computation with the \(\mathbf{y}_m\), \(\hat{\mathbf{w}}^\T\mathbf{z}+w_0<0\): a contradiction. The second statement is the contrapositive of the first, so there is nothing more to prove. (For finite sets the converse also holds, disjoint hulls imply separability, by the separating hyperplane theorem for disjoint compact convex sets.) The manual's argument is the same; its (131) writes \(\mathbf{y}_m\) where \(\mathbf{x}_n\) is meant.
Exercise 5.3 (★★). If every target row satisfies \(\mathbf{a}^\T\mathbf{t}_n+b=0\), show that the least-squares prediction (5.16) satisfies \(\mathbf{a}^\T\mathbf{y}(\mathbf{x})+b\)\({}=0\) for every \(\mathbf{x}\), assuming a constant basis function \(\phi_0=1\). (Companion: Exercise 4.2.)
Solution
Result 5.4 with a single constraint: \(\mathbf{T}\mathbf{a}=-b\one_N=\)\({}-b\widetilde{\mathbf{X}}\mathbf{e}_1\), so \(\mathbf{a}^\T\mathbf{y}(\mathbf{x})\)\({}=\tilde{\mathbf{x}}^\T\widetilde{\mathbf{X}}^\dagger\mathbf{T}\mathbf{a}\)\({}=-b\,\tilde{\mathbf{x}}^\T\mathbf{e}_1\)\({}=-b\). The manual instead eliminates the bias, centres the data and works with the centred pseudo-inverse; both are correct. In its derivative (134) the factor 2 is spurious (the error carries a \(\tfrac12\)); it does not affect the solution.
Exercise 5.4 (★★). Extend Exercise 5.3 to several simultaneous linear constraints. (Companion: Exercise 4.3.)
Solution
Stack the constraints as \(\mathbf{A}\mathbf{t}_n+\mathbf{b}\)\({}=\mathbf{0}\); the computation in Result 5.4 is written for this matrix case and gives \(\mathbf{A}\mathbf{y}(\mathbf{x})\)\({}+\mathbf{b}=\mathbf{0}\). Checked numerically with two random constraints (residual \(10^{-14}\)). (Agrees with the manual.)
Exercise 5.5 (★). From (5.38), (5.30), (5.31), derive (5.39).
Solution
See Result 5.8: \(1/P+1/R=(2N_\mathrm{TP}+N_\mathrm{FP}\)\({}+N_\mathrm{FN})/N_\mathrm{TP}\) and \(F=2/(1/P+1/R)\). (Agrees with the manual, which multiplies out instead.)
Exercise 5.6 (★★). Show that \(0\le a\le b\) implies \(a\le(ab)^{1/2}\), and deduce that the minimum-error rule has \(p(\text{mistake})\)\({}\le\int\{p(\mathbf{x},\cC{1})p(\mathbf{x},\cC{2})\}^{1/2}\d\mathbf{x}\) (5.99). (Companion: Exercise 1.21.)
Solution
Multiply \(\sqrt a\le\sqrt b\) by \(\sqrt a\ge0\). For the minimum-error rule, by Result 5.5, \(p(\text{mistake})\)\({}=\int\min\{j_1,j_2\}\d\mathbf{x}\) with \(j_k=p(\mathbf{x},\cC{k})\), and \(\min\{j_1,j_2\}\le\sqrt{j_1j_2}\) pointwise by the first part (with \(a\) the smaller, \(b\) the larger). This Bhattacharyya-type bound is 0.377 against the true 0.227 for the demo's problem with \(d=1.5\). (Agrees with the manual, whose reference "(??)" is a broken cross-reference to (5.20).)
Exercise 5.7 (★). Show that \(L_{kj}=1-I_{kj}\) turns the minimum-expected-loss rule into the largest-posterior rule, and interpret this loss. (Companion: Exercise 1.22.)
Solution
\(\sum_k(1\)\({}-I_{kj})p(\cC{k}\given\mathbf{x})=1\)\({}-p(\cC{j}\given\mathbf{x})\), minimised by the largest posterior. The loss counts one per mistake and nothing for a correct decision, so its expectation is the misclassification rate. (Agrees with the manual.)
Exercise 5.8 (★). Give the minimum-expected-loss criterion for a general loss matrix and general priors. (Companion: Exercise 1.23.)
Solution
Assign \(\mathbf{x}\) to \(\argmin_j\sum_kL_{kj}p(\mathbf{x}\given\cC{k})p(\cC{k})\), which is (5.23) multiplied by \(p(\mathbf{x})>0\). For two classes with zero diagonal: decide \(\cC{2}\) when \(p(\mathbf{x}\given\cC{2})/p(\mathbf{x}\given\cC{1})\)\({}\ge L_{12}p(\cC{1})/(L_{21}p(\cC{2}))\): the loss ratio and the prior ratio enter only through their product. (Agrees with the manual.)
Exercise 5.9 (★). Show that \(\frac1N\sum_{n=1}^Np(\cC{k}\given\mathbf{x}_n)\) tends to \(p(\cC{k})\) as \(N\to\infty\). (The book's sum index is misprinted as \(N=1\).)
Solution
If the \(\mathbf{x}_n\) are independent draws from \(p(\mathbf{x})\), the strong law of large numbers gives convergence (almost surely) to \(\E[p(\cC{k}\given\mathbf{x})]\)\({}=\int p(\cC{k}\given\mathbf{x})p(\mathbf{x})\d\mathbf{x}\)\({}=\int p(\mathbf{x},\cC{k})\d\mathbf{x}\)\({}=p(\cC{k})\); the summands lie in \([0,1]\), so the expectation exists. Monte Carlo with 400000 draws gives 0.3001 for \(p(\cC{2})=0.3\). The assumption that the \(\mathbf{x}_n\) come from the same distribution as the training data matters: this is the basis of a simple check for prior shift. (Agrees with the manual.)
Exercise 5.10 (★★). With loss matrix \(L_{kj}\) and a loss \(\lambda\) for rejecting, find the minimum-expected-loss decision, check that it reduces to the reject rule of Section 5.2.3 for \(L_{kj}=1-I_{kj}\), and relate \(\lambda\) to \(\theta\). (Companion: Exercise 1.24.)
Solution
Result 5.7(b), (c): decide \(\argmin_jr_j(\mathbf{x})\) if \(\min_jr_j(\mathbf{x})<\lambda\), otherwise reject; for 0–1 loss this is "reject if \(\max_kp(\cC{k}\given\mathbf{x})\le1\)\({}-\lambda\)", so \(\theta=1-\lambda\). Rejecting never pays if \(\lambda\ge1-1/K\) (every input is then decided) and always if \(\lambda=0\). (Agrees with the manual.)
Exercise 5.11 (★). Show \(\sigma(-a)=1-\sigma(a)\) and \(\sigma^{-1}(y)=\ln\{y/(1-y)\}\). (Companion: Exercise 4.7.)
Exercise 5.12 (★). Derive (5.48) with (5.49), (5.50) from (5.40), (5.41) for Gaussian classes with a shared covariance. (Companion: Exercise 4.8.)
Solution
Result 5.11. The manual reaches the same result, but its intermediate lines drop the inverse on \(\bm\Sigma\) (they show \(\mathbf{x}\bm\Sigma^\T\mathbf{x}\), \(\bm\mu_1^\T\bm\Sigma\bm\mu_1\) and \(\bm\mu_2^\T\bm\Sigma\bm\mu_2\) where \(\bm\Sigma^{-1}\) is meant).
Exercise 5.13 (★). A generative model has priors \(\pi_k\) and any class densities \(p(\bm\phi\given\cC{k})\). For independent labelled data with 1-of-\(K\) targets, show that the maximum-likelihood priors are \(\pi_k=N_k/N\) (5.101). (Companion: Exercise 4.9.)
Solution
The log likelihood is \(\sum_n\sum_kt_{nk}\{\ln p(\bm\phi_n\given\cC{k})\)\({}+\ln\pi_k\}\); only \(\sum_kN_k\ln\pi_k\) depends on the priors. Lagrange (or Gibbs' inequality) as in Result 5.12 gives \(\pi_k=N_k/N\), whatever the class densities. (Agrees with the manual.)
Exercise 5.14 (★★). With Gaussian class densities \(\N(\bm\phi\given\bm\mu_k,\bm\Sigma)\) sharing \(\bm\Sigma\), show that the maximum-likelihood means are the class means (5.103) and that \(\bm\Sigma=\sum_k(N_k/N)\mathbf{S}_k\) (5.104), (5.105). (Companion: Exercise 4.10.)
Solution
Result 5.12, where the covariance step is done in the precision \(\bm\Lambda=\bm\Sigma^{-1}\), in which the objective is concave, so the stationary point is the maximum. The manual's version has typos in (154) (\((\bm\phi-\bm\mu)\) for \((\bm\phi_n-\bm\mu_k)\)) and (157) (a sum written \(\sum^T_k\), and \(\bm\mu_n\) for \(\bm\mu_k\)); the result is right.
Exercise 5.15 (★★). Find the maximum-likelihood \(\mu_{ki}\) for the binary naive Bayes model of Section 5.3.3.
Solution
Result 5.13(b): \(\mu_{ki}\)\({}=\frac1{N_k}\sum_{n\in\cC{k}}x_{ni}\), the fraction of class-\(k\) points with \(x_i=1\). The manual's (160) writes \(\frac1N\sum_{n=1}^N x_{ni}\), reusing \(N\) for the number of points in class \(k\) and summing over those points only; read literally (all \(N\) points) it would give the same estimate for every class.
Exercise 5.16 (★★). \(M\) features with \(L\) states each, coded 1-of-\(L\), independent given the class: show that the activations \(a_k\) of (5.46) are linear in the codes. (Companion: Exercise 4.11.)
Solution
Result 5.13(c): \(a_k=\sum_{m,l}\phi_{ml}\ln\mu_{kml}\)\({}+\ln p(\cC{k})\). (Agrees with the manual.)
Exercise 5.17 (★★). Find the maximum-likelihood parameters of the model of Exercise 5.16.
Solution
Result 5.13(c): \(\mu_{kml}=N_{kml}/N_k\), with one Lagrange multiplier per (class, feature) pair. The manual writes the denominator as \(\sum_n\sum_l\phi_{nml}\), which is \(N_k\) because each point has exactly one active state per feature; its sums run over the points of class \(k\).
Exercise 5.20 (★). Show that for linearly separable data the maximum-likelihood logistic regression solution is obtained by a separating \(\mathbf{w}\) with \(\|\mathbf{w}\|\to\infty\). (Companion: Exercise 4.14.)
Solution
Result 5.17: the likelihood approaches its supremum 1 along \(\kappa\hat{\mathbf{w}}\), \(\kappa\to\infty\), for any strictly separating \(\hat{\mathbf{w}}\), and is not attained; strictly speaking there is no maximum-likelihood solution, only a maximising sequence. The manual's argument uses "\(\mathbf{w}^\T\bm\phi_n\ge0\) if \(t_n=1\)", which allows points on the boundary; such a point keeps \(y_n=\tfrac12\) for every \(\kappa\), so the separation must be strict.
Exercise 5.21 (★). Show that the softmax derivatives are (5.78). (Companion: Exercise 4.17.)
Exercise 5.22 (★). Using (5.78), show that the gradients of (5.80) are (5.81). (Companion: Exercise 4.18.)
Solution
Result 5.18; the step that needs \(\sum_kt_{nk}=1\) is \(\partial E_n/\partial a_{nj}=y_{nj}\)\({}-t_{nj}\). (Agrees with the manual.)
Exercise 5.23 (★). Show that the probit function (5.86) and the erf function (5.87) are related by (5.88). (Companion: Exercise 4.21.)
Solution
Result 5.19(2): with the book's (5.87), \(\Phi(a)=\tfrac12\)\({}+\frac1{\sqrt{2\pi}}\int_0^ae^{-\theta^2/2}\d\theta\)\({}=\tfrac12\{1+\erf(a)/\sqrt2\}\), which is (5.88) directly, no substitution needed. The manual's solution substitutes \(\theta=\sqrt2u\) and obtains \(\Phi(a)=\tfrac12\{1+\erf(a/\sqrt2)\}\) "using (5.87)"; that step uses the library definition \(\erf(z)\)\({}=\frac2{\sqrt\pi}\int_0^ze^{-u^2}\d u\), not (5.87), and under the book's own definition \(\tfrac12\{1+\erf(a/\sqrt2)\}\ne\Phi(a)\) (at \(a=1\): 0.868 against 0.841). Both final formulas are right in their own convention; the manual mixes the two. Verified numerically.
Exercise 5.24 (★★). Approximating \(\sigma(a)\) by \(\Phi(\lambda a)\) with equal derivatives at \(a=0\), show \(\lambda^2=\pi/8\). (Companion: Exercise 4.25.)
Solution
Result 5.19(3): \(\tfrac14=\lambda/\sqrt{2\pi}\). (Agrees with the manual.)
Corrections to the book and the solutions manual
Found while writing these notes; each is checked either by direct algebra or numerically.
Book (first edition, 2024).
p. 139: "\(p(\cC{1})\) represents the probability that a person has cancer": the same page defines \(\cC{1}\) as the absence of cancer, so this is \(p(\cC{2})\) (and likewise \(p(\cC{2}\given\mathbf{x})\) in the next sentence).
p. 149: the F-score is called "the geometric mean of precision and recall"; (5.38) is the harmonic mean, which differs (Result 5.8).
(5.66)–(5.68): the factor \(1/s\) is missing in front of \(\bm\lambda^\T\mathbf{x}\) in (5.67) and (5.68), and the prefactor of (5.66) should be \(1/s^D\) for \(\mathbf{x}\in\R^D\) (Result 5.14; numerically the printed log odds are wrong by more than 0.5 for \(s=2\)).
(5.70) is misprinted as \(f(\mathbf{w}^\T\mathbf{w}+w+0)\); it should be \(f(\mathbf{w}^\T\mathbf{x}+w_0)\).
Figure 5.16 caption: the outputs are \(y_1,\dots,y_K\), not \(y_1,\dots,y_N\).
(5.82): the left side should be \(\partial E/\partial w_{ki}\) (or the right side should use \(j\)); the text's "output unit \(t_k\)" means \(y_k\).
(5.87): the integrand \(\exp(-\theta^2/2)\) does not define the erf that "many numerical packages" evaluate (\(\exp(-\theta^2)\)). With the printed definition (5.88) is correct; with the library erf the relation is \(\Phi(a)=\tfrac12\{1+\erf(a/\sqrt2)\}\).
p. 164: the probit tail decays like \(\exp(-x^2/2)/x\), not \(\exp(-x^2)\) (Filling the gap 5.11); the conclusion about outliers stands.
(5.95): "\(\nabla\ln E(\mathbf{w})\)" should be \(\nabla E(\mathbf{w})\).
Exercise 5.9: the summation index is printed as \(N=1\); it should be \(n=1\).
Solutions manual (version 1.0).
5.2: in (131) the last sum has \(\mathbf{y}_m\) where \(\mathbf{x}_n\) is meant.
5.3: the derivative (134) has a spurious factor 2; harmless, since it is set to zero.
5.6: the reference to (5.20) is printed as "(??)".
5.12: intermediate lines omit the inverse on \(\bm\Sigma\); the final result is right.
5.14: index typos in (154) and (157); the result is right.
5.15: (160) normalises by \(N\) and sums over \(n=1,\dots,N\), meaning the \(N_k\) points of class \(k\); as printed it reads like the overall mean.
5.20: uses \(\mathbf{w}^\T\bm\phi_n\ge0\) where strict separation is needed, and calls the limit a maximum, which is not attained.
5.23: claims to use (5.87) but uses the library definition of erf, reaching a formula that differs from (5.88) under the book's definition (see Exercise 5.23).
Demonstrations for this chapter
Each demonstration runs in the browser and links back to these notes; the ▶ Demo boxes above open them already set to the case under discussion. The Python code computes the same numbers: the decision-theory quantities, the generative fits and the training errors after 100 gradient steps agree with the pages to about \(10^{-14}\).
A one-dimensional screening problem: joint densities with the false positives and false negatives shaded, the posteriors with the threshold and the reject band, the ROC curve with the operating point, the expected loss against the threshold, and the confusion matrix with precision, recall and F-score. Presets: 1 minimum misclassification rate (Fig. 5.5); 2 a missed cancer costs 100 (Fig. 5.6); 3 reject option (Fig. 5.7); 4 rare disease, accuracy misleads; 5 a far mode that does not matter (Fig. 5.8).
Two or three Gaussian classes: the density ellipses, the posterior as a colour mix with the decision boundaries, shared or different covariances, the prior slider and the maximum-likelihood fit from a sample. Presets: 1 shared covariance (Fig. 5.13); 2 a prior shifts the boundary in parallel; 3 three classes (Fig. 5.14); 4 quadratic boundaries; 5 maximum-likelihood fit.
Gradient descent from w = 0 with hand-written forward and backward passes: the probability map and boundaries, the error and the weight norm against the iteration, least squares for comparison, weight decay and Gaussian basis functions. Presets: 1 far points (Fig. 5.4); 2 separable data; 3 softmax for three classes; 4 basis functions (Fig. 5.15); 5 probit against logistic.
Bishop, C. M. and Bishop, H. (2024). Deep Learning: Foundations and Concepts. Solutions to the Exercises, version 1.0 (Chapters 2–10).
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer, New York. Sections 1.5 and 4.1–4.3 (and the official errata).
Berger, J. O. (1985). Statistical Decision Theory and Bayesian Analysis, 2nd ed. Springer, New York.
Duda, R. O. and Hart, P. E. (1973). Pattern Classification and Scene Analysis. Wiley, New York.
Fawcett, T. (2006). An introduction to ROC analysis. Pattern Recognition Letters, 27(8), 861–874. doi:10.1016/j.patrec.2005.10.010.
Hanley, J. A. and McNeil, B. J. (1982). The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology, 143(1), 29–36.
McCullagh, P. and Nelder, J. A. (1989). Generalized Linear Models, 2nd ed. Chapman and Hall, London.
Nelder, J. A. and Wedderburn, R. W. M. (1972). Generalized linear models. Journal of the Royal Statistical Society, Series A, 135(3), 370–384.
Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Kluwer, Boston. (The convergence bound used in Filling the gap 5.10.)
Neyman, J. and Pearson, E. S. (1933). On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London, Series A, 231, 289–337.
All numerical statements in the text (gradients against finite differences and torch.autograd, the decision-theory integrals, the convergence and separability claims, and the corrections) were confirmed numerically.