Figure sources
Every figure in the ML chapters is an original plot made for these notes; no external artwork or course slides are reproduced. All figures are drawn with D3 and typeset with KaTeX in the style of the Foundations figures, then rendered to PNG at twice their CSS size by headless Chromium. The figures of chapter 1 were redrawn on 27 September 2026 and those of chapters 2 to 17 on 28 September 2026, replacing Matplotlib versions; a redrawn figure keeps the data, seeds, and fitted models of the version it replaces unless its row says otherwise. The source of each figure is Sources/Figure code/js/src/<name>.js. Figures that show a fitted model, such as a scikit-learn estimator, an EM run, or a Gaussian-process fit, read their numbers from js/data/<name>.js, which the chapter’s script in Sources/Figure code writes; the other figures compute their data in JavaScript, drawing random numbers from the seeded generator of the Foundations figure code. Each chapter script, from ch01_nearest_neighbors.py to ch17_smoothing.py, also recomputes and prints every number that its chapter and captions quote from the figures. The tables below summarize the data, seeds, and model settings of each figure so that it can be read and regenerated without opening the code; the computing setup gives the environment and commands.
In the Python scripts, seeds refer to numpy.random.default_rng(seed) unless a scikit-learn random_state is named; makeRng(seed) is the linear congruential generator of the Foundations figure code, which the scripts port to Python where they recompute a JavaScript simulation. Simulated results are single illustrative runs or averages over the stated number of repetitions; they illustrate the claims in the notes but do not replace the stated assumptions of the theorems.
1. Learning problems and nearest neighbors {#1-learning-problems-and-nearest-neighbors}
Each figure is drawn from the stated model with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Random draws use the seeded linear congruential generator of the Foundations figure code, so every figure is reproducible exactly. The script ch01_nearest_neighbors.py recomputes, independently of the drawing code and with the same generator, every number that the chapter and its captions quote from these figures, and the table of asymptotic \(k\)-NN errors in Appendix A.
The classification figures share one model: two equally likely Gaussian classes, \(\mathcal N\bigl((0,0),\operatorname{diag}(1,4)\bigr)\) for class 0 and \(\mathcal N\bigl((2,0),\operatorname{diag}(1,1/4)\bigr)\) for class 1, whose Bayes boundary is the parabola \(x_1=1-\ln2+\tfrac{15}{16}x_2^2\) and whose Bayes error is \(0.099\). Training samples are drawn with the seeded generator of the figure code. The population error of a fitted rule is its conditional error, \(\eta\) or \(1-\eta\), weighted by the density of \(X\) and summed over a regular grid on \([-5.5,7]\times[-9,9]\), which holds all but a negligible fraction of the probability; it is therefore exact up to the grid resolution rather than estimated from a test sample.
| Local figure | Data and construction |
|---|---|
| nn-linear-vs-knn.png | Redrawn. One training sample of 200 points (seed 4), shown in the window \([-3.4,5]\times[-4.6,4.6]\). Least-squares linear fit to the 0/1 labels with an intercept, thresholded at 1/2; 15-NN and 1-NN majority votes with Euclidean distance and ties broken by index. The regions are zero contours on a 264 × 264 grid, and the Bayes boundary is drawn from its formula. Population errors on a 300 × 300 grid: 0.159, 0.109, and 0.151. |
| nn-knn-rule.png | Fourteen hand-placed points at fixed angles and distances 0.95 to 4.3 from the query; the five nearest are three of class 1 and two of class 0. The bars on the right have length equal to the distance of each of the eight nearest points. |
| nn-error-vs-k.png | Redrawn. 30 training samples of 200 points (seeds 101 to 130). For 18 odd values of \(k\) from 1 to 101, the training error (each training point counts as its own neighbor) and the population error on a 120 × 120 grid, averaged over samples; the band spans the 10th to 90th percentiles of the population error. The average population error is within 0.0005 of its minimum, 0.111, for \(k\) from 11 to 17; the linear rule averages 0.161. |
| nn-bias-variance-point.png | The simulation of the chapter’s bias–variance code: \(x_i=(i+1/2)/200\), \(m(x)=\sin 2\pi x\), noise standard deviation 0.3, query \(x_0=0.25\), neighbors ordered by \(\lvert x_i-x_0\rvert\) with ties broken by index. Left: one noisy sample (seed 3) and the neighborhoods for \(k=51\) and \(k=101\). Right: exact squared bias and variance \(\sigma^2/k\) for \(k=1,\ldots,200\); the sum is smallest at \(k=26\). |
| nn-distances.png | Left: the unit balls of \(\ell_1\), \(\ell_2\), and \(\ell_\infty\). Middle and right: 160 points uniform on \([-2,2]^2\) in standardized coordinates (seed 34), class 1 when the first coordinate is positive, query \((-0.25,0)\). Eight nearest neighbors under \(\sqrt{\Delta z_1^2+100\,\Delta z_2^2}\) (raw units, feature 2 on a ten times larger scale; 5 of 8 in class 1) and under Euclidean distance (1 of 8 in class 1). Each ellipse or disk is the smallest one of its shape that holds the eight neighbors. The seed was chosen so that the raw-unit vote is wrong; the geometry of the two neighborhoods does not depend on it. |
| nn-cover-hart.png | Redrawn. Analytic curves \(R^\ast\) and \(2R^\ast(1-R^\ast)\) for \(R^\ast\in[0,1/2]\), the two attaining families marked at \(R^\ast=0.1\) and \(0.25\), and the asymptotic 3-NN and 9-NN errors \(\alpha_k(p)\) of Appendix A for constant \(\eta=p\). |
| nn-curse-of-dimensionality.png | Redrawn. Left: the analytic edge length \(r^{1/d}\) for \(d=1,2,3,10,100\) and \(10^{-4}\le r\le1\). Right: the median distance \(\bigl(1-2^{-1/N}\bigr)^{1/d}\) from the center of the unit ball to the nearest of \(N=500\), \(10^4\), and \(10^6\) uniform points, for \(1\le d\le1000\). |
| nn-distance-concentration.png | For \(d=1,2,3,5,10,20,50,100,200,500,1000\): a uniform query and 500 uniform points in \([0,1]^d\), 20 repetitions (seed 5). Distances divided by their median; the curves average the smallest ratio, the 5th and 95th percentiles, and the largest ratio over repetitions. The table gives the median over repetitions of \((\max-\min)/\min\): 33.8, 2.41, 0.41, and 0.11 for \(d=2,10,100,1000\). |
| nn-kd-tree.png | 64 points uniform on the unit square (seed 12). Median splits alternating between the coordinates, cut halfway between the two middle points, down to 16 cells of 4 points. Query \((0.62,0.41)\); the circle through its nearest neighbor meets 2 of the 16 cells. |
2. The perceptron and linear separation {#2-the-perceptron-and-linear-separation}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Every figure computes its own data in JavaScript, so there are no data files; random draws use the seeded linear congruential generator of the Foundations figure code, so every figure is reproducible exactly. The script ch02_perceptron.py recomputes, independently of the drawing code and with the same generator, every number that the chapter and its captions quote from these figures; it runs in about ten seconds.
Separable samples share one construction. A random unit vector \(u\) is drawn first (\(d\) standard normals, normalized). Each point is then a uniformly random direction, a normalized vector of \(d\) standard normals, scaled by \(U^{1/d}\) with \(U\) uniform, so that it is uniform in the unit ball; it is labeled by the sign of \(u^\top x\) and pushed along \(u\), away from the hyperplane \(u^\top x=0\), until its margin along \(u\) is at least \(\gamma\). \(R\) is the largest norm in the sample and \(\gamma\) the realized margin \(\min_iy_iu^\top x_i\) along \(u\). The perceptron is homogeneous, starts from \(w_1=0\), counts a zero score as a mistake, visits the points in a fresh random order in each pass (a Fisher–Yates shuffle driven by the seeded generator), and stops after a pass without mistakes.
| Local figure | Data and construction |
|---|---|
| perceptron-hyperplane.png | Analytic. Left: \(w=(1.2,0.9)\), so \(\Vert w\Vert _2=1.5\), and \(b=-1.5\), so the origin is at distance 1 from the boundary; the point \(x=(1.75,2.1)\) has signed distance 1.66. Right: \(d=1\), \(w=1.5\), \(b=-1.5\) (threshold at \(x=1\)), \(c=1\), and ten inputs at fixed positions; the lifted normal is \(\tilde w=(1.5,-1.5)\). |
| perceptron-margin.png | 20 points uniform in the unit disk (seed 232), drawn from the square by rejection, labeled by a random unit vector \(u_0\), and kept only when \(\lvert u_0^\top x\rvert\ge0.15\). The worst-case margin of a direction is computed exactly; its maximum is located on a grid of 72,000 angles and refined by golden-section search: \(\gamma(D)=0.237\), attained by one point of each class, with the next margin 0.307. The separating directions form an arc of 55.0°; the second line is 62% of the way from \(u^\ast\) to one end of that arc (\(-20.0°\)) and has worst-case margin 0.134. The seed was chosen so that the two attaining points belong to different classes and the third point is clearly farther away; the construction does not depend on it. |
| perceptron-xor.png | Redrawn. 120 uniform points in \([-1,1]^2\) (seed 2), excluding points within 0.12 of either axis, labeled by the sign of \(x_1x_2\): 91 points remain, 51 of them with \(x_1x_2>0\). Left: three lines through \((0,0.1)\) at angles 0.3, 1.2, and 2.3 radians; with the better of its two labelings, each misclassifies 44, 43, and 36 points. Right: an axonometric view (azimuth \(-36°\), elevation \(11°\), vertical axis scaled by 0.8) of the points at height \(x_1x_2\) above the plane \(x_1x_2=0\), whose quadrants are shaded by the sign of \(x_1x_2\). |
| perceptron-updates.png | Redrawn. 30 separable points in the plane with \(\gamma=0.06\) (seed 28); the visiting orders come from a second generator with the same seed. The run makes 6 updates in 3 passes, and the numbers of misclassified points after the updates are 2, 6, 1, 6, 2, and 0; update 5 does not fix its own example. Every update is shown, with vectors at their true length. The seed was chosen among those giving four to seven updates so that the run shows both kinds of setback. |
| perceptron-potential.png | 200 separable points in \(d=100\) with \(\gamma=0.1\) (seed 1); the visiting orders come from a second generator with seed 1. \(R=1.0046\), realized margin \(0.1000\), \((R/\gamma)^2=100.9\); the run makes \(M=45\) mistakes and ends with \(u^\top w=5.03\) and \(\Vert w\Vert _2=5.75\). The script checks both bounds after every mistake. |
| perceptron-mistake-bound.png | Redrawn. 300 datasets of 200 separable points from one generator (seed 7), which also drives the visiting orders. For each, \(d\) is drawn uniformly from \(\{2,5,20,100\}\) and \(\gamma\) uniformly from \([0.03,0.4]\). \((R/\gamma)^2\) ranges from 7.0 to 1081; the largest ratio of mistakes to bound is 0.68, and the median ratios are 0.12, 0.35, 0.49, and 0.43 for \(d=2,5,20,100\) (62, 101, 71, and 66 datasets). The dimension is shown on an ordered blue scale. |
| perceptron-online-to-batch.png | \(X\) uniform on the unit circle, with the arcs where \(\lvert x_1\rvert<0.1\) removed by rejection, and \(Y=\operatorname{sign}(x_1)\), so \(u=(1,0)\), \(R=1\), \(\gamma=0.1\). One pass of 200 examples. For \(w\) at angle \(\theta\in[0,\pi]\) from \(u\), \(\operatorname{err}_P(w)=2\bigl[(\theta-a)^+-(\theta-\pi+a)^+\bigr]/(2\pi-4a)\) with \(a=\arcsin0.1\), and \(\operatorname{err}_P(0)=1\). Left: one pass (seed 39), with 6 mistakes at steps 1, 3, 19, 38, 81, and 110; the error rises after the third and fifth. Right: 20,000 passes (seeds 1000 to 20999); the mean error of \(w_t\) is drawn at every step, and the mistake frequency at steps 1 to 20 and every sixth step after. \(\mathbb E[M]=5.38\); both averages over \(t\) are 0.0269, and the largest gap at a single step is 0.0049, within Monte Carlo error. Seed 39 was chosen as a pass with a typical number of mistakes in which the error rises after some updates. |
| perceptron-averaging.png | Redrawn. \(d=10\), \(X\sim\mathcal N(0,I/d)\), labels \(\operatorname{sign}(u^\top x)\) for a random unit vector \(u\) with 10% flipped independently of \(X\), and an intercept feature (seed 3); 400 training points, 30 passes in random order, errors recorded after every 20 training examples. The original test sample of 20,000 points is replaced by the exact population error \(0.1+0.8q\), where \(q=P\bigl(\operatorname{sign}(v^\top X+b)\ne\operatorname{sign}(u^\top X)\bigr)\) for weights \((v,b)\) is a bivariate normal probability computed by Simpson’s rule with 4,000 subintervals on each half-line; the script checks it against the bivariate normal CDF. The averaged weights end at 0.151 and stay between 0.150 and 0.151 over the last 15 passes; the current weights range from 0.150 to 0.471 there, with median 0.235. |
| perceptron-multiclass.png | Hand-set weights \(w_1=(1,0.2)\), \(w_2=(-0.4,1)\), \(w_3=(-0.6,-0.9)\) and example \(x=(0.6,0.45)\) of class 2: its scores are \(0.69\), \(0.21\), \(-0.765\) before the update and \(0.1275\), \(0.7725\), \(-0.765\) after it. Nine further hand-placed points, three per class, are all classified correctly before the update and eight after it. Sectors are found by scanning 3,600 directions. |
3. Linear regression and regularization {#3-linear-regression-and-regularization}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Figures that need NumPy’s generator, a fitted model, or the diabetes data take their numbers from the script ch03_linear_regression.py, which writes them to Sources/Figure code/js/data/<name>.js; the drawing code only draws. The geometry, thresholding, and elastic-net figures are analytic and compute their own curves. The script also recomputes, independently of the drawing code, every number that the chapter and its captions quote from the figures; it needs NumPy and scikit-learn and runs in about 6 seconds. The diabetes data are scikit-learn’s load_diabetes (442 patients, 10 features), with features standardized by their means and standard deviations (denominator \(n\)) and the response centered.
| Local figure | Data and construction |
|---|---|
| linreg-polynomial-degree.png | Redrawn. \(y=\sin(2\pi x)+\varepsilon\), \(\varepsilon\sim\mathcal N(0,0.3^2)\), 20 training inputs uniform on \([0,1]\) (seed 0, the same draws as the original figure). Least squares on Legendre polynomials in \(2x-1\) of degree 0 to 16; the fits of degree 1, 3, and 15 are drawn. The population error is \(\sigma^2+\int_0^1(\hat f-m)^2\,dx\) by 200-point Gauss–Legendre quadrature, which replaces the original 5,000 test points. Smallest at degree 3, \(0.127\); \(0.333\) for degree 1 and \(83.2\) for degree 15, of which \(80.9\) comes from \(x\) beyond the largest training input, \(0.935\). |
| linreg-gradient-conditioning.png | The data and loop of the chapter’s gradient-descent code (seed 0, \(n=500\), area \(\mathcal N(90,25^2)\), rooms \(\mathcal N(3,1)\), \(y=12\,\text{area}+150\,\text{rooms}+\mathcal N(0,200^2)\)), recording \(\tfrac1n\lVert X(\beta_t-\hat\beta)\rVert^2\) at 318 logarithmically spaced iterations. Eigenvalues of \(X^\top X/n\): \(0.042\), \(1.54\), \(8{,}630\) raw (\(\kappa=2.03\times10^5\)) and \(0.995\), \(1\), \(1.005\) standardized (\(\kappa=1.01\)). Flattest raw direction \((0.989,-0.006,-0.146)\); \((1-1/\kappa)^{200\,000}=0.374\); \(\lambda_{\max}/\lambda_j=5{,}595\) and \(203{,}366\). |
| linreg-shrinkage-factors.png | Squared singular values of the standardized diabetes design, \(1{,}778.7\) down to \(191.7\), then \(34.6\) and \(3.8\). Shrinkage factors \(\sigma_j^2/(\sigma_j^2+\lambda)\) for \(\lambda\in[0.1,10^5]\), colored by \(\log\sigma_j^2\); at \(\lambda=50\) they are \(0.973\) to \(0.793\), \(0.409\), and \(0.070\), and \(\operatorname{df}(50)=7.51\). |
| linreg-ridge-mse.png | Exact \(\mathbb E\lVert\hat\beta_\lambda-\beta\rVert^2\) from the singular values of the standardized diabetes design, with \(\sigma^2=2{,}932.7\) (residual variance of the least-squares fit, denominator \(n-d-1\)) and \(\theta_j^2=\tau^2=\lVert\hat\beta^{\mathrm{OLS}}\rVert^2/10=429.5\) in every direction. Least squares \(927\), of which 93% from directions 9 and 10; minimum \(413\) at \(\lambda^\ast=\sigma^2/\tau^2=6.83\); ridge beats least squares for \(\lambda\) below about \(117\). Direction 10: \(775\) for least squares, \(276\) for ridge (variance \(99\), squared bias \(178\)). |
| linreg-ridge-lasso-geometry.png | Redrawn. A quadratic residual sum of squares with Hessian \(\bigl(\begin{smallmatrix}1&0.6\\0.6&0.8\end{smallmatrix}\bigr)\) and unconstrained minimum \((1.6,0.55)\); its level sets are drawn as exact ellipses. The constrained minima over the \(\ell_2\) and \(\ell_1\) balls of radius 1 are computed exactly, by bisection on the Lagrange multiplier for the circle and by minimizing over each edge of the diamond, rather than on a grid of the boundary: \((0.852,0.524)\) and the corner \((1,0)\). |
| linreg-thresholding.png | Analytic. The estimates of the orthonormal-design table as functions of \(\hat\beta_j^{\mathrm{OLS}}\), with illustrative settings: best-subset threshold \(c_k=1.4\), ridge factor \(1/(1+\lambda/n)=0.6\), lasso threshold \(\lambda=1\). |
| linreg-coefficient-paths.png | Redrawn. Diabetes data. Ridge path from the SVD over 200 penalties in \([10^{-2},10^5]\), plotted against \(\operatorname{df}(\lambda)\). The lasso path is now the exact piecewise-linear path from lars_path(method="lasso"), with 13 knots from \(\lambda_{\max}=45.16\) to 0; it agrees within \(2.2\times10^{-7}\) with the original lasso_path over 300 penalties from 60 to \(10^{-4}\), and ends exactly at least squares. Entry order bmi, s5, bp, s3, sex, s6, s1, s4, s2, age. Only bmi, s5, bp, s1, and s2 are colored. |
| linreg-elastic-net-grouping.png | Analytic. Two identical columns, so the contours are the lines \(\beta_1+\beta_2=c\), with least-squares solutions on \(\beta_1+\beta_2=1.6\). The \(\ell_1\) ball of radius 1 and the elastic-net ball \(\tfrac12\lVert\beta\rVert_1+\tfrac14\lVert\beta\rVert_2^2\le0.625\) (\(\alpha=1/2\), budget chosen so that it passes through \((\tfrac12,\tfrac12)\); it meets the axes at \(0.871\)). Numerical check in the script: 200 standardized draws \(z\) (seed 3), \(y=2z+\mathcal N(0,1)\) centered, design \([z,z]\); Lasso(alpha=0.1) gives \((1.933,0)\) and ElasticNet(alpha=0.1, l1_ratio=0.5) gives \((0.967,0.967)\). |
4. Generative classifiers {#4-generative-classifiers}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Figures that show fitted scikit-learn models or the digits and wine data read their numbers from Sources/Figure code/js/data/<name>.js, which the script ch04_generative_classifiers.py writes with the original seeds and settings; the drawing code only evaluates and draws them. The other figures are analytic or simulated in the drawing code, the simulation with the seeded linear congruential generator of the Foundations figure code. The script also prints every number that the chapter and its captions quote from the figures, recomputing the analytic and simulated ones independently, with the same generator where one is used. It needs NumPy, SciPy, and scikit-learn and runs in a few seconds.
| Local figure | Data and construction |
|---|---|
| gen-bayes-rule.png | Analytic. One feature with class 0 \(\mathcal N(-1,1.5^2)\) and class 1 \(\mathcal N(1,1.5^2)\), the model of the duplicated-feature code block. Left: \(\pi_kp_k(x)\) for \(\pi_0=\pi_1=1/2\), their sum \(p(x)\), and a stacked bar at \(x=0.75\) whose class-1 share is \(P(Y=1\mid x)=0.661\). Right: \(P(Y=1\mid X=x)\) for \(\pi_1=1/2\) and \(\pi_1'=0.1\) with the same class densities; the posterior at \(x=0.75\) is 0.661 and 0.178, and the boundary moves from 0 to \(\tfrac{1.5^2}{2}\log9=2.47\). |
| gen-nb-digits.png | Multinomial naive Bayes of the chapter’s digits code block (70/30 stratified split, random_state=0, \(\alpha=1\)). Left: \(\hat\theta_{kj}\) as \(8\times8\) images on a common gray scale from 0 to the largest value, 0.048. Right: for each of the 540 test images, \(\log_{10}\bigl(1-\max_k\hat P(Y=k\mid x)\bigr)\), computed from the log posteriors of the other nine classes by log-sum-exp; bins of width 4 ending at \(10^{-3}\), stacked by correct and wrong predictions. 508 images (94%) have posterior above 0.999, and 41 of them (8.1%) are wrong; the median of \(1-\max_k\hat P\) is \(10^{-20.8}\) overall and \(2.9\times10^{-5}\) over the 56 wrong predictions. Image intensities sum to 313 on average. |
| gen-nb-duplicates.png | The duplicated-feature code block: 2,000 examples, class means \(\pm1\), standard deviation 1.5 (default_rng(0)). GaussianNB fitted to \(c=1,2,5,10\) copies; the script exports the fitted log-odds on a grid of 321 points in \([-4,4]\). Left: fitted posteriors and the true posterior \(\sigma(2x/1.5^2)\). Right: posterior at \(x=0.75\) (0.692, 0.823, 0.976, 0.999) and training accuracy (0.749 to 0.754). The class-1 share is 0.5215, the prior term 0.086, and the fitted boundary moves from \(-0.133\) (\(c=1\)) to \(-0.049\) (\(c=10\)). |
| gen-lda-whitening.png | Analytic. Equal priors, shared covariance \(\bigl(\begin{smallmatrix}1&0.85\\0.85&1\end{smallmatrix}\bigr)\), means \((0,0)\) and \((1.1,-0.2)\) (the model of the Fisher figure), query \((0.3,-0.9)\). Ellipses at Mahalanobis distance 1.5; right panel in \(z=L^{-1}x\) with the Cholesky factor \(L\). Euclidean distances from the query to the means 0.95 and 1.06; Mahalanobis distances 2.21 and 0.80. |
| gen-gnb-lda-qda.png | Redrawn. Three Gaussian classes with means \((0,0)\), \((2.6,1)\), \((0.6,3)\), different covariances, and 120, 90, 90 training points (seed 8). Gaussian naive Bayes, LDA, and QDA from scikit-learn; regions from each model’s discriminants (naive Bayes and QDA from their fitted means, variances or covariances, and priors, LDA from its coefficients) on a \(300\times300\) grid extending 5% beyond the panel; ellipses are the fitted two-standard-deviation contours. The dashed curves are the Bayes boundaries of the true model, whose accuracy is 0.929. Training accuracies 0.920, 0.907, 0.930; population accuracies, integrated over the known densities on a grid of spacing 0.02 over \([-8,11]\times[-7,11]\), 0.916, 0.916, 0.928; test accuracies on ten times as many fresh points from the same seed stream, 0.914, 0.913, 0.924. |
| gen-rda-eigenvalues.png | Simulated in the drawing code. Twenty features with diagonal covariance, eigenvalues \(3\cdot9^{-(j-1)/19}\) from 3 to 1/3; \(n=40\) (generator seed 7) and \(n=15\) (seed 8), 200 repetitions each. Maximum-likelihood covariance (divisor \(n\)) and its Ledoit–Wolf shrinkage toward \(\hat\sigma^2I\), \(\hat\sigma^2=\operatorname{tr}(\hat\Sigma)/d\), with the intensity of scikit-learn’s ledoit_wolf_shrinkage; eigenvalues by Jacobi rotations. Averages over repetitions, bands from the 10th to the 90th percentile. For \(n=40\) the sample eigenvalues average 4.28 down to 0.075 and the shrunk ones 2.60 down to 0.70 (intensity 0.55); for \(n=15\), 5.74 down to 0.064 with six exact zeros, shrunk 2.61 down to 0.80 (intensity 0.70). |
| gen-fisher-direction.png | Redrawn. Two classes of 250 points each, with shared covariance \(\bigl(\begin{smallmatrix}1&0.85\\0.85&1\end{smallmatrix}\bigr)\) and means \((0,0)\) and \((1.1,-0.2)\) (seed 2). The Fisher direction uses the pooled sample within-class scatter; the two directions differ by 34°. Sample separation ratios 0.73 and 2.60. Histograms of the projections as densities (26 bins), with the exact projected densities \(\mathcal N(w^\top\mu_k,w^\top\Sigma w)\); the best threshold on each projection has population error 0.260 and 0.113. |
| gen-discriminant-coordinates.png | The 178 wines of load_wine. Left: first two principal components of the standardized features (36% and 19% of the total variance). Right: LinearDiscriminantAnalysis(n_components=2).transform fitted to all wines (69% and 31% of the between-class variance; unit within-class covariance). Nearest-centroid errors in the two coordinates: 5 of 178 for the principal components, 0 for the discriminant coordinates. |
5. Logistic regression and probabilistic prediction {#5-logistic-regression-and-probabilistic-prediction}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. The script ch05_logistic_regression.py fits every model that a figure shows, with the seeds and settings of the original Matplotlib figures, and writes the fitted quantities to Sources/Figure code/js/data/<name>.js, which the drawing code reads; the figures logreg-sigmoid-loss and logreg-proper-scores are analytic and need no data. The script also prints every number that the chapter and its captions quote from the figures, and runs in about 45 seconds. Seeds refer to numpy.random.default_rng(seed) unless a scikit-learn random_state is named. Exact population quantities are computed from the known models, by closed-form Gaussian probabilities, numerical integration, or exhaustive enumeration, rather than estimated from test samples, wherever the figure’s model is known.
| Local figure | Data and construction |
|---|---|
| logreg-sigmoid-loss.png | Analytic. Left: \(\sigma(s)=1/(1+e^{-s})\) on \([-6,6]\), its tangent of slope \(1/4\) at \(s=0\), and the segments of length \(\sigma(-2)=1-\sigma(2)=0.119\). Right: the logistic loss \(\log(1+e^{-m})\), its asymptote \(-m\), and the hinge loss \(\max\{0,1-m\}\) on \([-4,5]\); the loss at \(m=0\) is \(\log2=0.693\). |
| logreg-newton-irls.png | The breast cancer example of the chapter’s code: split with random_state=0, features 0, 1, 4, and 8 standardized with training means and standard deviations, and a constant feature, 398 training examples. Newton’s method from zero for 12 iterations, whose last iterate is taken as \(\hat w\); distances for iterations 0 to 9, the last \(3\times10^{-15}\). Gradient descent on the mean loss from zero with step \(1/L\), \(L=\lambda_{\max}(A^\top A)/(4n)=0.413\), for 3,000 steps, distances every 10 steps: below \(10^{-4}\) after about 990 steps; the contraction per step between steps 1,000 and 2,000 is \(0.9902\), equal to \(1-\mu/L\) with \(\mu=0.0040\) the smallest eigenvalue of the Hessian of the mean loss at \(\hat w\). Right: the weights \(\hat p_i(1-\hat p_i)\) at \(\hat w\); 60% are below 0.01, and 1 of the 20 misclassified training examples is among them. |
| logreg-separation.png | Redrawn. 25 points per class from \(\mathcal N((-1.2,0),0.55^2I)\) and \(\mathcal N((1.2,0.3),0.55^2I)\) (seed 1), linearly separable. Full-batch gradient descent from zero on the mean logistic loss, with the intercept as a constant feature, step 0.5 (below \(1/L=2.36\)), without a penalty and with an \(\ell_2\) penalty \(\lambda=0.01\) on the weights; the gradient is computed from \(\sigma(-\text{margin})\), which stays accurate as the probabilities approach 0 and 1. The runs now continue for \(10^6\) steps instead of 20,000, so that the logarithmic growth is visible; norms at 241 log-spaced iterations. Weight norm without the intercept: 15.83 after 20,000 steps, as in the original figure, and 33.82 after \(10^6\); with the penalty 3.173, within \(10^{-6}\) from step 1,189 on. The dashed asymptote is \(\lVert\hat v_{1:}\rVert_2\log t+c\), with the weight part of the maximum-margin vector of logreg-implicit-bias (norm 4.909) and \(c\) fixed at \(t=10^6\). Right: probabilities along \(x_2=0.15\) after \(10^3\), \(10^4\), and \(10^6\) steps without the penalty, and at the penalized minimizer. |
| logreg-implicit-bias.png | The unpenalized run of logreg-separation. The maximum-margin vector \(\hat v\), the shortest vector with \(\tilde y_i\hat v^\top(1,x_i)\ge1\), solves the dual problem \(\max_{\alpha\ge0}\sum_i\alpha_i-\frac12\lVert\sum_i\alpha_i\tilde y_i(1,x_i)\rVert^2\) by L-BFGS-B: \(\hat v=(0.249,4.576,1.779)\), \(\lVert\hat v\rVert_2=4.916\), three support vectors. The usual hard-margin SVM, with the intercept left out of the norm (scikit-learn SVC, linear kernel, \(C=10^{10}\)), differs from it by \(0.005^\circ\). Angles between \(w_t\) and \(\hat v\): \(17.0^\circ\), \(9.7^\circ\), and \(3.6^\circ\) after 10, \(10^3\), and \(10^6\) steps; between \(10^5\) and \(10^6\) steps \(\lVert w_t\rVert_2\) grows by 4.79 per unit of \(\log t\). |
| logreg-probability-contours.png | Redrawn. 120 points with Gaussian classes centered at \((-0.6,-0.4)\) and \((1.2,0.9)\), coordinate standard deviations 1 and 0.8 (seed 5; 57 in class 1). scikit-learn LogisticRegression with \(C=100\) and \(C=0.02\), that is \(\lambda=1/(nC)\approx8.3\times10^{-5}\) and \(0.417\). The probability surface is evaluated from the fitted coefficients on a 220 × 220 grid extending 5% beyond the panel. \(\lVert w\rVert_2=2.89\) and 0.67, training log loss 0.222 and 0.413; the boundary normal turns by \(7.4^\circ\), the two rules disagree on 1 of the 120 training points, and the width \(2\log9/\lVert w\rVert_2\) of the band between probabilities 0.1 and 0.9 is 1.52 and 6.58. |
| logreg-softmax-ovr.png | Three equally likely classes \(\mathcal N(-3,1)\), \(\mathcal N(0,1)\), \(\mathcal N(3,1)\), 100 training points each (seed 7). Unpenalized multinomial LogisticRegression and three unpenalized binary fits of each class against the rest; the one-versus-rest probabilities are the raw sigmoids. Population log loss and accuracy by integration over \([-12,12]\) with step 0.001: multinomial 0.244 and 0.907, one-versus-rest rescaled to sum to one 0.372 and 0.899, true posterior 0.222 and 0.911. At \(x=0\) the middle class has probability 0.980 (multinomial), 0.334 (one-versus-rest), and 0.978 (true). On \([-6,6]\) the one-versus-rest probabilities sum to between 0.34 and 1.35. |
| logreg-lda-outliers.png | Two classes \(\mathcal N((-1,0),\Sigma)\) and \(\mathcal N((1,0.5),\Sigma)\) with \(\Sigma=\bigl(\begin{smallmatrix}1&0.5\\0.5&1\end{smallmatrix}\bigr)\), 100 points each, and 20 class-1 points \((6,4.5)+0.5Z\) with standard Gaussian \(Z\) (seed 3). scikit-learn LinearDiscriminantAnalysis and unpenalized LogisticRegression, with and without the added points. Population errors are exact, from the Gaussian law of \(w^\top X+b\) within each class: LDA 0.149 and 0.169, logistic regression 0.149 in both cases (identical coefficients to three decimals), Bayes error 0.149. The added points have fitted logistic probabilities above 0.99965. |
| logreg-nb-learning-curves.png | Redrawn. 40 binary features with class-conditional probabilities drawn once (seed 0), the first eight features copied five more times, so naive Bayes’s independence assumption fails. Training sizes 20 to 2,560, 40 repetitions each, 20,000 test points. Bernoulli naive Bayes with Laplace smoothing and logistic regression with \(C=10^4\) and \(C=1\). Lines join the mean test errors, whiskers span the 10th to 90th percentiles. At 20 examples: 0.363, 0.383, 0.369; at 80: 0.290, 0.304, 0.261; at 160: 0.268, 0.257, 0.223; at 2,560: 0.252, 0.173, 0.172. The Bayes error, 0.1654, and the error of the naive Bayes rule with the true probabilities, 0.2447, are exact: the log-likelihood-ratio sum over the 40 base features is enumerated separately for two halves of 20 features (\(2^{20}\) values each) and the halves are combined through sorted cumulative probabilities. |
| logreg-proper-scores.png | Analytic, for \(Y\sim\operatorname{Bernoulli}(0.2)\), the success probability of the cross-entropy figure of Foundations chapter 5: expected log loss (minimum \(H(0.2)=0.500\) nats), expected Brier score (minimum \(0.16\)), and expected zero–one loss of \(\mathbf 1\{\hat p\ge1/2\}\) (0.2 below \(1/2\), 0.8 from \(1/2\) on). |
| logreg-calibration.png | Redrawn. make_classification with 30,000 samples, 20 features, 2 informative and 10 redundant, 5% label noise (random_state=4), split into training, calibration, and test sets of 10,000. Platt scaling is fitted on the exact naive Bayes log-odds and isotonic regression on its probabilities, both on the calibration set; ten equal-width bins, empty bins omitted; histograms with 20 bins on a common scale. Brier score and log loss: 0.125 and 0.400, 0.149 and 1.158, 0.119 and 0.383, 0.119 and 0.379. 80% of the naive Bayes test predictions lie below 0.01 or above 0.99. Areas under the ROC curve: 0.902 for logistic regression, 0.911 for naive Bayes and after Platt scaling, 0.9107 after isotonic regression, which takes 94 distinct values. |
| logreg-recalibration-maps.png | The models of logreg-calibration. Dots: the calibration sample in 25 bins of 400 examples by naive Bayes log-odds. Platt map \(\sigma(0.157\,s-0.112)\) on the exact log-odds; the chapter’s code block, which clips probabilities at \(10^{-12}\) and so truncates 12.7% of the calibration log-odds at \(\pm27.6\), gives slope 0.161 and intercept \(-0.116\), whose threshold 0.72 changes 174 of the 10,000 test predictions. The isotonic map is evaluated at \(\sigma(s)\) on a grid over \([-45,45]\), which holds 98.4% of the calibration log-odds. |
6. Losses, model selection, and evaluation {#6-losses-model-selection-and-evaluation}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. The analytic figures compute their curves in the drawing code. The five figures that show fitted models or repeated simulations draw data that the script ch06_model_selection.py writes to Sources/Figure code/js/data/<name>.js; the script uses NumPy, SciPy, and scikit-learn with the seeds and settings of the earlier Matplotlib figures, so the redrawn figures show the same fitted objects. It also prints every number that the chapter and its captions quote from the figures, including those of the analytic ones, and runs in under a minute. No figure of this chapter uses the seeded generator of the Foundations figure code.
| Local figure | Data and construction |
|---|---|
| select-losses.png | Redrawn. Analytic margin losses on \([-2.5,2.5]\): zero–one \(\mathbf 1\{z\le0\}\), hinge, logistic in base 2, exponential, squared \((1-z)^2\), and perceptron. The regression panel of the earlier version is now the left panel of select-regression-losses, next to the text it illustrates. |
| select-conditional-risk.png | Analytic. Left: \(C_\eta(a)=\eta\phi(a)+(1-\eta)\phi(-a)\) at \(\eta=0.75\) for the losses of select-losses, with the logistic loss in natural logarithms; minimizers \(\log3\approx1.099\) (logistic), \(0.549\) (exponential), \(0.5\) (squared), \(1\) (hinge), and \(0\) (perceptron). Right: the minimizing scores of the chapter’s table for \(0<\eta<1\). |
| select-regression-losses.png | Analytic. Left: squared, absolute, Huber (\(\delta=1\)), and pinball (\(\tau=0.8\)) losses against the residual, as in the right panel of the earlier select-losses. Right: the \(\operatorname{Gamma}(2,1)\) density with its median \(1.678\), Huber location \(1.742\) (root of \(\mathbb E\,\operatorname{clip}(Y-a,-1,1)=0\)), mean \(2\), and 0.8-quantile \(2.994\). |
| select-bias-variance.png | Redrawn. Fixed design of 25 equally spaced inputs, \(m(x)=\sin(2\pi x)\), noise standard deviation 0.3, Legendre polynomial basis. The fits shown are the first 20 of the 2,000 noise draws per degree (seed 0) for degrees 1 and 9. The average fit is now computed exactly, as the least-squares fit to \(m\) itself, instead of as the mean of the 20 fits. Squared bias and variance are computed exactly from the hat matrix for degrees 0 to 12 and averaged over 200 evaluation points in \([0.05,0.95]\); the expected error is smallest at degree 3, \(0.105\). The right panel now stacks the three terms instead of drawing three curves. |
| select-double-descent.png | Redrawn. \(n=40\) observations of 400 standard Gaussian features, noise standard deviation 0.5, \(\lVert\beta\rVert=1\) with either equal coefficients or \(\beta_j\propto1/j\) (seed 0). Minimum-norm least squares on the first \(p\) features; the exact risk \(\lVert\beta_{1:p}-w\rVert^2+\lVert\beta_{p+1:400}\rVert^2+0.25\) of 300 fits per \(p\). Lines are medians, as before; the bands of quartiles are new. Spread signal: median 1.266 at \(p=1\), 85.1 at \(p=40\), 1.228 at \(p=300\), and 1.177 at \(p=400\), against 1.25 for predicting zero; the exact mean at \(p=400\) is 1.178. Concentrated signal: smallest median 0.392 at \(p=7\). |
| select-optimism.png | The design of select-bias-variance evaluated at its 25 inputs. Left: exact expected training error \(\lVert(I-H)\mu\rVert^2/n+\sigma^2(1-\operatorname{df}/n)\) and in-sample prediction error \(\lVert(I-H)\mu\rVert^2/n+\sigma^2(1+\operatorname{df}/n)\), with \(\operatorname{df}\) the degree plus one. Right: \(C_p\) for the first 20 of 2,000 samples (seed 1), each with \(\hat\sigma^2\) equal to its degree-12 residual sum of squares divided by 12. Over the 2,000 samples, \(C_p\) chooses degree 3 in 55%, degree 5 in 16%, and degree 6 or higher in 22%. |
| select-cv-splits.png | Diagram of 20 observations: five folds of four, drawn after shuffling; five groups of sizes 4, 3, 5, 4, 4, each held out whole; four forward-chaining splits that train on the first 8, 11, 14, and 17 observations and validate on the next three. |
| select-cv-one-se.png | Redrawn. scikit-learn diabetes data; ten shuffled folds (random_state=1), with standardization and the response mean fitted inside each training fold; ridge over 40 penalties from \(10^{-2}\) to \(10^4\). Minimum CV error 3011.3 at \(\lambda=24.2\), standard error 90.3; the one-standard-error rule picks \(\lambda=142.5\), 5.88 times larger. The effective degrees of freedom, new in the labels, are those of ridge on all 442 standardized patients: 8.2 and 6.0. |
| select-nested-cv.png | Diagram of nested cross-validation on 20 observations with five outer folds of four and, inside outer split 1, five inner folds of sizes 4, 3, 3, 3, 3, as KFold splits 16 observations. |
| select-early-stopping.png | Analytic filters \(1-(1-u)^t\) and \(u/(u+1/t)\) for \(u=\eta\sigma_j^2\in[10^{-5},1]\) and \(t=10,100,1000\). The gradient-descent filter crosses one half at \(u=1-2^{-1/t}\), which is \(0.0670\), \(0.00691\), and \(0.00069\), close to \(\log2/t\). |
| select-leakage.png | The chapter’s leakage code repeated for data seeds 0 to 199 with the same StratifiedKFold(5, shuffle=True, random_state=0). Selection outside CV: mean accuracy 0.951, range 0.88 to 1.00. Selection inside CV: mean 0.497, standard deviation 0.080, range 0.32 to 0.74. Seed 0 reproduces the code’s 0.94 and 0.52. |
| select-threshold.png | Analytic. Scores \(\mathcal N(0,1)\) for negatives and \(\mathcal N(2,1)\) for positives, prevalence 50%, threshold \(t=1.5\): TPR 0.691, FPR 0.067; at \(t=0.5\), TPR 0.933 and FPR 0.309. The left panel stacks \(0.5\,\varphi(s)\) and \(0.5\,\varphi(s-2)\), where \(\varphi\) is the standard normal density. |
| select-roc-pr.png | Redrawn. Scores \(\mathcal N(\Delta,1)\) for positives and \(\mathcal N(0,1)\) for negatives with \(\Delta=1,2\), at prevalences 50% and 1%. The earlier version plotted curves from simulated samples (seed 2; 5,000 of each class, and 500 positives with 49,500 negatives); the redrawn curves are exact, computed from the normal distribution function over a grid of thresholds, so the two ROC curves of each classifier coincide. AUC \(\Phi(\Delta/\sqrt2)\): 0.760 and 0.921. Average precision, the integral of precision over recall: 0.753 and 0.042 for \(\Delta=1\), 0.922 and 0.269 for \(\Delta=2\), at 50% and 1%. |
7. Statistical learning theory {#7-statistical-learning-theory}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Three figures show simulations that use NumPy’s generator, with the seeds and settings of the original Matplotlib figures: the rectangle learner, the halving run of the chapter’s code block, and weighted majority. For these, the script ch07_learning_theory.py writes the data file Sources/Figure code/js/data/<name>.js, and the drawing code only draws. The structural-risk-minimization figure draws its samples in JavaScript with the seeded linear congruential generator of the Foundations figure code; the other figures are deterministic. The script ports that generator to Python and recomputes, independently of the drawing code, every number that the chapter and its captions quote from the figures. It needs only NumPy and runs in about 15 seconds.
| Local figure | Data and construction |
|---|---|
| theory-rectangle-learner.png | Redrawn. Target rectangle \([0.2,0.7]\times[0.3,0.8]\) under the uniform law on the unit square (NumPy seed 4). Left: 40 examples, 9 of them positive, the tightest fit, whose error is 0.049, and the four strips of probability \(\varepsilon/4\) with \(\varepsilon=0.12\), each holding a positive example. Right: exact error of the tightest fit (the area of the target it misses), mean and 95th percentile over 1,000 samples at each of 25 sizes from 10 to 10,000, with the bound \(4\ln(4/\delta)/n\) for \(\delta=0.05\), which exceeds 1 for \(n\le13\). For \(n\ge100\) the bound is 2.2 to 2.5 times the 95th percentile; for \(n\ge1{,}000\), \(n\) times the mean error lies between 3.90 and 4.09. |
| theory-elimination.png | Hand-chosen example: \(d=4\), target \(x_1\wedge\neg x_3\), examples \((1,0,0,1)\), \((0,1,0,1)\), \((1,1,0,1)\), \((1,0,1,0)\), \((1,1,0,0)\) with labels \(1,0,1,0,1\). The positive examples remove four, one, and one literals, and the output equals the target. |
| theory-sauer-split.png | Intervals on four ordered points: \(\lvert\mathcal H_C\rvert=11=\lvert\mathcal H'\rvert+\lvert\mathcal H''\rvert=7+4\), equal to \(\Phi_2(4)\), \(\Phi_2(3)\), and \(\Phi_1(3)\); \(\mathcal H''=\{000,001,011,111\}\). |
| theory-rectangle-vc.png | Redrawn. The four points \((0,\pm1)\), \((\pm1,0)\) with all sixteen labelings, grouped by the number of positive points; each rectangle is the smallest one containing the positive points, enlarged by 0.2 on every side, which keeps every negative point outside. Five points \((0,1)\), \((1,0.1)\), \((0.1,-1)\), \((-1,-0.1)\), \((0.15,0.2)\), the last one interior. The script checks both claims by enumeration. |
| theory-sine-shattering.png | The points \(x_i=2^{-i}\), \(i=1,\ldots,4\), and the labelings \((1,1,1,1)\), \((1,0,1,0)\), \((0,1,1,0)\), realized by \(\omega=\pi\), \(21\pi\), and \(19\pi\). The script checks all 16 labelings of four points and all 4,096 labelings of twelve points. |
| theory-realizable-agnostic.png | Exact computation for \(\varepsilon=0.1\), \(0.05\), \(0.025\). Realizable: \((1-\varepsilon)^n\). Agnostic: the difference of the two classifiers’ losses is \(+1\), \(-1\), or \(0\) with probabilities \(0.2+\varepsilon\), \(0.2\), and \(0.6-\varepsilon\), and the probability that its sum over \(n\) examples is at most zero is obtained by propagating the distribution of the sum for \(n\le10{,}000\). The probability falls to 0.05 at \(n=29\), 59, 119 (realizable) and \(n=143\), 505, 1,878 (agnostic). |
| theory-srm.png | Inputs uniform on \([0,1]\); label 1 on \([0.15,0.35)\cup[0.5,0.6)\cup[0.75,0.9)\), flipped with probability 0.15; classes of unions of at most \(k\) intervals, \(k=1,\ldots,8\). Training and validation samples of equal size from makeRng(11) (\(n=500\)) and makeRng(12) (\(n=10{,}000\)); each example draws its input, then its flip. Exact empirical risk minimizers by dynamic programming over the sorted inputs, with endpoints halfway between neighboring inputs; exact population risks. SRM bound \(2\sqrt{2v\ln(en/v)/n}+\sqrt{\ln(2/\delta_k)/(2n)}\) with \(v=2k\), \(\delta_k=\delta/(k(k+1))\), \(\delta=0.05\). For \(n=500\), SRM chooses \(k=1\) (objective 0.869, population risk 0.331) and validation \(k=3\) (population risk 0.163); for \(n=10{,}000\), both choose \(k=3\) (SRM objective 0.376, population risk 0.151). The seeds were not selected: over seeds 1 to 20 at \(n=500\), SRM always chooses \(k=1\) and validation chooses \(k=3\) in 17 cases; over seeds 1 to 6 at \(n=10{,}000\), both always choose \(k=3\). |
| theory-halving.png | Left: the run of the chapter’s halving code (1,024 thresholds, target \(700/1024\), 5,000 uniform inputs, NumPy seed 0). Mistakes at rounds 1, 5, 29, 390, and 989, with 1,024, 371, 61, 10, and 2 consistent thresholds before them; one threshold is left from round 989. The adversary halves the version space at each of ten mistakes. Right: the binary-search mistake tree of depth 3 for thresholds on \([0,1]\); the halving learner predicts 1 on an even split, so the adversary’s path answers 0 at every node. |
| theory-weighted-majority.png | Redrawn. 64 experts over 2,000 binary rounds (NumPy seed 1); each expert is independently correct with a fixed probability drawn uniformly from \([0.55,0.8]\), except one with 0.9. Weighted majority halves the weight of every expert that errs. Expert curves are drawn every 20 rounds. Final mistakes: weighted majority 205, best expert 210 (the 90% expert), worst expert 930; bound \(2.409\,(210+6)=520\). The 90% expert holds more than half of the weight from round 64 on and 0.986 of it after 100 rounds; from round 55 on, weighted majority errs exactly when that expert does. |
8. Support vector machines and kernels {#8-support-vector-machines-and-kernels}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Every fitted model (scikit-learn SVC and KernelRidge, cross-validation, Gram-matrix eigenvalues, random Fourier features) is computed by the script ch08_svm_kernels.py, with the seeds and settings of the earlier Matplotlib figures, and written to Sources/Figure code/js/data/<name>.js; the drawing code only evaluates and draws the fitted quantities. The illustrative svm-smo-step and the small example of kernel-representer are computed in the drawing code; the latter uses the seeded linear congruential generator of the Foundations figure code, which the script ports to Python. The script also prints every number that the chapter and its captions quote from these figures; it runs in about 6 seconds.
Seeds refer to numpy.random.default_rng(seed) unless a scikit-learn random_state or the figure generator makeRng is named. The labels are \(y\in\{-1,+1\}\), drawn blue for \(-1\) and orange for \(+1\).
| Local figure | Data and construction |
|---|---|
| svm-max-margin.png | Redrawn. 40 points, two Gaussian classes with standard deviation 0.75 and means \((-0.2,-0.3)\) and \((2.4,2)\) (seed 7). Left: the perceptron with an intercept, run to convergence for eight visiting orders (seeds 0 to 7); geometric margins from 0.12 to 0.58, the extremes highlighted. Right: SVC(kernel="linear", C=1e6) as the hard-margin solution: geometric margin 0.86, band width 1.71, 3 support vectors. |
| svm-soft-margin.png | Redrawn. 80 points, two unit-variance Gaussian classes whose means differ by \((2.5,2)\) (seed 5). Linear SVC with \(C=0.01,0.1,100\); support vectors are sorted by their dual variables into \(0<\alpha_i<C\) and \(\alpha_i=C\). Band widths 3.82, 2.22, 0.49; support vectors 2 + 48, 2 + 19, 3 + 5; training accuracies 0.95, 0.95, 0.97. |
| svm-kkt-groups.png | The sample of the chapter’s first code block: 60 points, unit-variance Gaussian classes whose means differ by \((2,1.5)\) (seed 0), linear SVC with \(C=1\) and tol=1e-8. Left: the fit, with support vectors marked by group. Right: \(\alpha_i\) against \(y_if(x_i)\) with the graph allowed by complementary slackness. Groups of 3, 16 (7 of them misclassified), and 41 points. |
| svm-feature-map.png | Redrawn. make_circles with 160 points, noise 0.08, factor 0.45 (random_state=2). Left: orthographic view of the lift \((x_1,x_2,x_1^2+x_2^2)\) with the plane at height 0.53, halfway between the highest inner point (0.377) and the lowest outer point (0.682). Right: polynomial kernel \((x^\top z+1)^2\) with \(C=10\); its decision function is the explicit quadratic computed from the dual coefficients, drawn with its level sets \(0\) and \(\pm1\) on a grid 5% larger than the panel; 9 support vectors, training accuracy 1.00. |
| kernel-gram-spectra.png | The 200 standard normal points in \(\mathbb R^3\) of the chapter’s second code block (seed 1, drawn after that block’s regression data). Eigenvalues from numpy.linalg.eigvalsh of the Gram matrices of \(e^{-\Vert x-z\Vert^2/2}\), \((x^\top z+1)^3\), and \(\tanh(x^\top z-1)\). Gaussian: all positive, 74 above \(10^{-3}\) of the largest, smallest ratio \(3.8\times10^{-10}\). Cubic: rank 20, the other 180 at round-off, drawn as one dotted segment. Sigmoid: 98 negative eigenvalues, the smallest \(-92.8\), on a symmetric logarithmic scale that is linear within 0.01 of zero. |
| kernel-representer.png | Eight hand-placed inputs on \([0,1]\) (0.06 to 0.47 and 0.78 to 0.95), targets \(\sin(2\pi x)\) plus noise of standard deviation 0.15 (makeRng(8)). Kernel ridge regression with \(e^{-40(x-z)^2}\) and \(\lambda=0.1\); \(f_\perp=k(\cdot,0.62)-\sum_jc_jk(\cdot,x_j)\) with \(c=K^{-1}k(0.62)\). Squared norms \(\Vert f\Vert_{\mathcal H}^2=2.29\) and \(\Vert f+1.5f_\perp\Vert_{\mathcal H}^2=3.46\). |
| kernel-ridge-rff.png | Redrawn. Left: 40 points from \(\sin(2\pi x)+0.5\cos(6\pi x)\) plus noise of standard deviation 0.25 (seed 4); scikit-learn KernelRidge with the Gaussian kernel, \(\gamma=2,60,3000\) (length scales 0.50, 0.09, 0.01), and penalty 0.05, predicted on 801 grid points. Right: a \(300\times300\) Gaussian Gram matrix (\(\gamma=0.2\)) of standard normal points in five dimensions (the same generator, after the regression data), approximated by \(D\) random Fourier features for 13 values of \(D\) from 10 to 10,000, 10 draws each (seed \(100r+D\) for draw \(r\)); the curve is the mean relative Frobenius error and the band its range. Fitted log–log slope \(-0.504\). |
| svm-rbf-grid.png | Redrawn. make_moons with 300 points, noise 0.3 (random_state=0), split in half (random_state=1). Gaussian-kernel SVC for \(\gamma\in\{0.1,1,30\}\) and \(C\in\{0.1,1,1000\}\); each panel evaluates \(f(x)=\sum_ic_ie^{-\gamma\Vert x-x_i\Vert^2}+b\) from the support vectors and dual coefficients on a grid 5% larger than the panel, with shading clipped to \([-2.5,2.5]\). For \(\gamma=30\), \(C=0.1\) all 150 points are support vectors and 99% of the window is predicted \(+1\). |
| svm-cv-heatmap.png | Redrawn. The same 300 points; five-fold stratified cross-validation (random_state=0) over 13 values of \(\gamma\) from \(10^{-3}\) to \(10^3\) and 13 values of \(C\) from \(10^{-2}\) to \(10^4\). Best accuracy 0.943 at \(\gamma=3.16\), \(C=1\); cells within 0.015 of it are outlined. For \(\gamma\le0.0316\) and \(C\le0.1\) the accuracy is 0.777 to 0.787. |
| svm-margin-bound.png | The 150 training and 150 test points of svm-rbf-grid; Gaussian-kernel SVC with \(\gamma=1\) for 21 values of \(C\) from \(10^{-2}\) to \(10^3\). Average training hinge loss of \(g+b\); complexity term \(2Br/\sqrt n\) with \(r^2=2\) and \(B^2=\Vert g\Vert_{\mathcal H}^2+b^2\) (the kernel \(k+1\) covers the intercept); bound = hinge + complexity + \(\sqrt{\ln(1/\delta)/(2n)}\) with \(\delta=0.05\) and \(n=150\) (0.100), as if \(B\) were fixed in advance. The bound is below 1 only for \(C\) from 0.0316 to 0.178 (smallest 0.92 at \(C=0.0562\)), where the test error is 0.127 to 0.18; the smallest test error, 0.073, is at \(C=100\), where the bound is 4.01. |
| svm-smo-step.png | Illustrative, no data: \(C=1\), the restricted dual objective \(-\frac12(a-a^\ast)^\top H(a-a^\ast)\) with \(H=\bigl(\begin{smallmatrix}1&0.35\\0.35&0.7\end{smallmatrix}\bigr)\), contours computed on a grid 5% larger than the panel. Left (\(y_i\ne y_j\)): start \((0.2,0.5)\), \(a^\ast=(1.3,1.02)\); the maximum on the line lies outside the box and is clipped to \((0.7,1)\). Right (\(y_i=y_j\)): start \((0.8,0.5)\), \(a^\ast=(0.4,0.75)\); the maximum on the line lies inside. |
9. Decision and regression trees {#9-decision-and-regression-trees}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Figures that show fitted scikit-learn trees take their numbers from the script ch09_trees.py, which fits the trees with the settings below, writes the data to Sources/Figure code/js/data/<name>.js, and prints every number that the chapter and its captions quote from the figures; the drawing code only draws. The impurity and categorical-split figures are analytic and computed in the drawing code, and the script recomputes their quoted numbers independently. The script runs in under ten seconds.
Two figures use a known population instead of a test sample. For the regression trees, the population mean squared error of a fitted step function \(\hat f\) is \(\sigma^2\) plus the average of \((\hat f-m)^2\) over the uniform input law on \([0,3]\), computed by the midpoint rule on 300,000 points. For the moons, class 0 is centered on \((\cos t,\sin t)\) and class 1 on \((1-\cos t,\tfrac12-\sin t)\) with \(t\) uniform on \([0,\pi]\), plus Gaussian noise of standard deviation 0.3, and the classes are equally likely; the class densities are averages of the Gaussian over 200 values of \(t\), and a classifier’s population accuracy is its conditional accuracy weighted by the density of \(X\) and summed over a 0.01 grid on \([-2.6,3.6]\times[-2.1,2.6]\), which holds all but about \(10^{-8}\) of the probability.
| Local figure | Data and construction |
|---|---|
| tree-partition.png | Redrawn. 240 uniform points in the unit square with three classes defined by axis-aligned regions; each label is redrawn uniformly from the three classes with probability 0.05 (seed 2; 6 labels redrawn). DecisionTreeClassifier(max_depth=3, ccp_alpha=0.01, random_state=0): 5 leaves, training accuracy 0.925. The boxes are drawn from the fitted tree_ arrays; the circled leaf numbers follow the left-to-right order of the leaves in the tree, and each tag sits at the point of its box farthest from the training points. |
| tree-split-scan.png | The 120 observations of tree-regression (seed 7). Children’s total squared error for the cut between each pair of consecutive sorted inputs, from cumulative sums; parent 96.94, best cut \(t=1.650\) (scikit-learn’s depth-1 threshold) with 85.60, a 12% decrease; leaf means \(-0.075\) (66 points) and \(0.543\) (54 points). |
| tree-regression.png | Redrawn. \(m(x)=\sin 4x+0.6\,\mathbf 1\{x>1.7\}\) plus noise of standard deviation 0.35, 120 inputs uniform on \([0,3]\) (seed 7). Regression trees of depth 1, 3, and full depth (2, 8, and 120 leaves). The cost-complexity path of the full tree (93 subtrees, 120 down to 3 leaves) with training, five-fold cross-validated (KFold(5, shuffle=True, random_state=0)), and population mean squared error. Cross-validation chooses 12 leaves (population MSE 0.185); the population MSE is smallest, 0.179, at 16 leaves; the full tree’s is 0.254, 2.07 times \(\sigma^2=0.1225\). The original figure estimated the error from 4,000 test points; the exact population error replaces it and changes none of the conclusions. |
| tree-impurity.png | Redrawn. Analytic impurity curves for two classes, entropy in bits and halved. A parent with \(p=0.7\) and children with \(p=0.55\) and \(0.9\), weighted 0.571 and 0.429 so that the parent proportion is their weighted average. Decreases: misclassification 0, Gini 0.060, entropy 0.078 nats (not drawn). |
| tree-categorical-order.png | Six levels A to F with sizes 40, 25, 30, 15, 35, 20 and mean responses 3.1, 1.2, 4.6, 2.0, 1.8, 5.3, chosen by hand so that the order of the means differs from the alphabetical order. Decrease in squared error of each of the 31 binary splits, \(\sum_{\text{side}}n_{\text{side}}(\mu_{\text{side}}-\bar y)^2\). The best, ABDE against CF (260.1, child means 2.148 and 4.880), respects the order BEDACF; the five order-respecting splits rank 1, 2, 3, 5, and 8. |
| tree-xor-horizon.png | The chapter’s exclusive-or sample: 400 points uniform on \([-1,1]^2\) (seed 0), class 1 when \(x_1x_2>0\). Gini decrease weighted by the node’s share of the data, for every cut of each feature at the root and in the two children of the root split \(x_2\le0.0075\). Largest decreases: 0.0074 (\(x_2\)) and 0.0067 (\(x_1\)) at the root; 0.248 and 0.240 for \(x_1\) near zero in the lower and upper child. |
| tree-pruning.png | The data of tree-partition. DecisionTreeClassifier(max_depth=3, random_state=0) without pruning (7 leaves) and its cost_complexity_pruning_path: breakpoints 0, 0.00016, 0.0082, 0.0854, 0.1275, 0.1673 for subtrees of 7, 6, 5, 4, 3, and 1 leaves, with training risk (leaf Gini weighted by node share) 0.0844, 0.0846, 0.0928, 0.1782, 0.3056, 0.6402. The \(\alpha\) at which each split is pruned is the first breakpoint whose subtree lacks it. \(T(0.01)\) is the tree of tree-partition. |
| tree-instability.png | Redrawn. make_moons with 200 training points (random_state=3) and noise 0.3. Fully grown trees on 100 bootstrap resamples (seed 0); the first three are shown (17, 17, and 16 leaves), each with the distinct points of its resample, and the last panel shades the average of the predicted probabilities of all 100. Population accuracies 0.866, 0.863, 0.838, and 0.897 for the average; Bayes accuracy 0.915. The original figure used 2,000 test points (random_state=4), which gave 0.86, 0.87, 0.84, and 0.89; the script prints both. |
10. Bagging and random forests {#10-bagging-and-random-forests}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. The figures built on fitted scikit-learn models (bag-variance, rf-mtry, rf-oob, rf-weights, rf-importance) read their numbers from Sources/Figure code/js/data/<name>.js, which the script ch10_bagging_forests.py writes; the drawing code only draws. The other three are computed in the drawing code, analytically or with the seeded generator of the Foundations figure code. The script uses the seeds and settings of the earlier Matplotlib version for the four original figures, so they show the same fitted models, and it prints every number that the chapter and its captions quote from the figures, recomputing those of the three JavaScript figures independently (with the same generator for bag-bootstrap). It runs in about 70 seconds.
| Local figure | Data and construction |
|---|---|
| bag-averaging.png | Left: the analytic variance ratio \(\rho+(1-\rho)/B\) for \(\rho=0,0.1,0.3,0.6,1\) and \(1\le B\le1000\). Right: five hand-placed member predictions \(-0.6,-0.2,0.2,0.8,1.3\) with target \(0\); their mean is \(0.3\), and the average member error \(0.554\) equals the ensemble error \(0.090\) plus the diversity \(0.464\). For \(\rho=0.3\), \(B=24\) is the smallest number of predictions whose variance is within 10% of the floor. |
| bag-bootstrap.png | Eight bootstrap samples of \(n=12\) examples, each of 12 draws rng.int(12) with makeRng(5); 33 of the 96 cells are empty against an expected \(96\,(11/12)^{12}\approx33.8\). The seed was chosen for a typical grid, with a count close to its expectation. Right: \((1-1/n)^n\) for \(1\le n\le200\), which is \(0.352\) at \(n=12\) and \(0.366\) at \(n=100\). |
| bag-indicator.png | Bühlmann and Yu’s large-sample model: \(\hat\theta\sim\mathcal N(\theta,s^2)\) and \(\hat\theta^\ast\sim\mathcal N(\hat\theta,s^2)\), so the bagged indicator is \(\Phi\bigl((c-\hat\theta)/s\bigr)\). With \(\delta=(\theta-c)/s\), the variance of the indicator is \(\Phi(\delta)\bigl(1-\Phi(\delta)\bigr)\) and that of the bagged version is \(\operatorname{Var}\Phi(-\delta-Z)\), \(Z\sim\mathcal N(0,1)\), integrated by Simpson’s rule on \([-9,9]\) (the script uses SciPy quadrature). At \(\delta=0\) they are \(1/4\) and \(1/12\); the bagged variance is the larger for \(\lvert\delta\rvert>2.35\). |
| bag-variance.png | Redrawn. The regression function \(\sin 4x+0.6\cdot\mathbf 1\{x>1.7\}\) of chapter 9 with 100 training inputs uniform on \([0,3]\) and noise standard deviation 0.35. Left: 200 fully grown bootstrap trees (seed 1); the six trees and their average are drawn as exact step functions from the fitted split points. Right: squared bias and variance over a 300-point grid, estimated from 150 independent training sets (seeds 1000–1149), for single and bagged trees (\(B=50\)) at full depth and depth 3: variances 0.130, 0.063, 0.085, 0.033 and squared biases 0.002, 0.002, 0.024, 0.022. From the same bootstrap trees, with the unbiased estimator described for rf-mtry, a fully grown bootstrap tree has variance \(\sigma^2=0.137\) and correlation \(\rho=0.45\), and the average of its first \(B\) trees has variance 0.137, 0.098, 0.076, 0.069, 0.065, 0.063 for \(B=1,2,5,10,20,50\); for depth 3, \(\sigma^2=0.110\) and \(\rho=0.29\). |
| rf-mtry.png | Redrawn. make_friedman1 with 300 points, 10 features, noise 1 (random_state 100–119 for 20 training sets); 1,000 uniform test inputs (seed 5) compared with the noise-free function. Forests of 100 trees for each \(m\) from 1 to 10 (random_state 0–19). With variances over trees taken within each forest and over forests across training sets (denominators \(B-1\) and \(R-1\)), the numerator of \(\rho\) is the variance of the forest prediction minus the mean within-forest variance divided by 100, and \(\sigma^2\) adds the mean within-forest variance back; both are averaged over test inputs before the ratio. The squared bias subtracts the forest variance divided by 20 from the squared error of the mean forest. The forest error is smallest at \(m=7\) (4.56); \(\rho\) falls from 0.116 at \(m=10\) to 0.021 at \(m=1\). The earlier version omitted both corrections and reported 0.119 and 0.029. |
| rf-oob.png | Redrawn. make_classification with 800 samples, 20 features, 6 informative, 4 redundant, 5% label noise (random_state=3), split in half (random_state=0). Forests grown with warm_start from 15 to 600 trees at 22 logarithmically spaced sizes, with \(m=\lfloor\sqrt d\rfloor=4\), 1, and \(d\) (random_state=0). Final OOB errors 0.162, 0.200, and 0.180; test errors 0.157, 0.195, and 0.180. At 103 trees and \(m=4\) the OOB and test errors are 0.177 and 0.170, within the binomial standard error 0.018 of a 400-point test error. |
| rf-weights.png | 500 inputs uniform on \([0,1]^2\) and responses \(\sin 2\pi x_1+\mathcal N(0,0.3^2)\) (seed 0). RandomForestRegressor with 500 trees, all features at each split, and min_samples_leaf=5 (random_state=0). The weights at \(x_0=(0.5,0.5)\) use each tree’s in-bag counts, recovered from scikit-learn’s bootstrap indices, and reproduce the forest’s prediction exactly; 50 points have positive weight and \(1/\sum_iw_i^2=19.9\). Root-mean-square distances from \(x_0\): 0.012 along \(x_1\) and 0.26 along \(x_2\) for the forest, 0.056 and 0.054 for the 20 nearest neighbors. Contours of the regression function at levels \(0,\pm0.25,\pm0.5,\pm0.75\). |
| rf-importance.png | Redrawn. 2,000 points: three standard normal features with logistic coefficients 1.5, −1.0, 0.5, plus an irrelevant continuous feature and an irrelevant three-level feature (seed 0), split in half. A 300-tree forest (training accuracy 1.0, test accuracy 0.747); impurity importance and permutation importance with 20 repeats on training and held-out data. MDI shares 0.383, 0.248, 0.189, 0.144, 0.036. |
11. Boosting {#11-boosting}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Figures that show fitted models take their numbers from the script ch11_boosting.py, which fits them with NumPy and scikit-learn, with the seeds and settings of the original Matplotlib figures, and writes them to Sources/Figure code/js/data/<name>.js; the drawing code only draws. AdaBoost is implemented directly, with scikit-learn trees as weak learners. The exponential-loss and Newton-leaf figures are analytic and compute their own curves. The script also prints every number that the chapter and its captions quote from the figures; it runs in about a minute with the pinned environment.
The ESL problem is scikit-learn’s make_hastie_10_2: ten standard normal features, labeled \(+1\) exactly when \(\sum_jx_j^2\) exceeds 9.34, the median of \(\chi^2_{10}\). Seeds refer to numpy.random.default_rng(seed) unless a random_state is named.
| Local figure | Data and construction |
|---|---|
| boost-adaboost-weights.png | Redrawn. 160 uniform points in \([-1,1]^2\), labeled \(+1\) inside the disk \(\lVert x\rVert^2<0.45\), with each label flipped with probability 0.04 (seed 4): 6 flipped labels, 51 points labeled \(+1\). AdaBoost with stumps (max_depth=1, random_state=0); ensembles after rounds 1, 6, 30, and 200 with training errors 0.319, 0.150, 0.069, and 0.000. A stump ensemble is a sum of step functions of \(x_1\) and of \(x_2\), so its prediction is constant on the rectangles cut out by the stump thresholds, and the regions are drawn exactly from the 200 exported stumps; the reconstruction reproduces the training errors. Marker area is proportional to \(D_{t+1}(i)\) on one scale for all panels, with a minimum size. The flipped points carry weight 0.043, 0.060, 0.136, and 0.258 after the four displayed rounds. |
| boost-training-bound.png | The run of the chapter’s first code block: ESL problem with 3,000 points (random_state=0), 1,000 for training and 2,000 for testing, AdaBoost with stumps for 400 rounds. Every round’s \(\varepsilon_t\), training and test error, and \(\prod_tZ_t\); the rows printed by the code are marked. \(\exp(-2\sum_t\gamma_t^2)\) exceeds \(\prod_tZ_t\) by at most 0.0013 and is not drawn. The mean of \(\varepsilon_t\) is 0.440 over rounds 1 to 10 and 0.478 over rounds 301 to 400; the running mean in the right panel is centered over 25 rounds. |
| boost-exp-loss.png | Analytic. Left: \(Z(\alpha)=(1-\varepsilon)e^{-\alpha}+\varepsilon e^{\alpha}\) for \(\varepsilon=0.1\), \(0.25\), \(0.4\), with minima \(0.600\), \(0.866\), and \(0.980\) at \(\alpha=1.099\), \(0.549\), and \(0.203\). Right: the weights \(-\phi'(z)\) of the exponential loss \(e^{-z}\) and of the logistic loss \(\ln(1+e^{-2z})\), which are \(e^{-z}\) and \(2/(1+e^{2z})\); at \(z=-2\) they are 7.39 and 1.96. |
| boost-margins.png | Redrawn. ESL problem with 12,000 points (random_state=1): 1,000 for training and 11,000 for testing. AdaBoost with depth-3 trees (random_state=0) for 1,000 rounds. The training error is first zero at round 120 and last nonzero at round 144; test error 0.265, 0.126, 0.122, 0.103, and 0.105 at rounds 10, 100, 120, 500, and 1,000. Normalized margins \(y_iF_T(x_i)/\sum_t\alpha_t\) at \(T=10\), 100, and 1,000, drawn as step functions, with each ensemble’s test error in the legend; their smallest values are \(-0.360\), \(-0.010\), and \(0.068\). The margin axis now runs to 1 so that the \(T=10\) distribution is shown in full. |
| boost-residuals.png | The run of boost-gradient-1d: the residuals \(y_i-F_{t-1}(x_i)\) and the depth-2 tree fitted to them in rounds 1, 10, and 50, with the tree’s leaves read from its structure. Mean squared residuals 0.808, 0.282, and 0.076; leaf values \((0.34,-0.82,1.16,-0.48)\), \((0.12,-0.42,0.41,-0.30)\), and \((0.00,-0.20,0.36,0.08)\) from left to right. |
| boost-gradient-1d.png | Redrawn. The regression data of chapter 9: 120 inputs uniform on \([0,3]\), \(m(x)=\sin4x+0.6\,\mathbf 1\{x>1.7\}\), noise standard deviation 0.35 (seed 7), and 2,000 validation points drawn next from the same generator. Gradient boosting for squared error implemented directly: \(F_0\) the mean, depth-2 regression trees (random_state=0) fitted to the residuals, \(\nu=0.1\), 1,000 rounds. A tree on these inputs changes value only halfway between consecutive training inputs, so each fit is drawn exactly as a step function from its values at the inputs. The four fits of the original left panel are now separate small panels. Validation error is smallest at \(T=52\), \(0.157\), and is \(0.248\) at \(T=1000\); the noise variance is \(0.1225\). |
| boost-newton-leaf.png | Analytic. One leaf with eight examples, \(F_i=-1\) for all, labels six 1s and two 0s: \(G=-3.848\), \(H=1.573\). Exact leaf log loss, its second-order model at \(w=0\), and the model with \(\lambda=1\); minimizers \(1+\ln3=2.099\), \(-G/H=2.447\), and \(-G/(H+\lambda)=1.496\). |
| boost-shrinkage.png | Redrawn. ESL problem with 12,000 points (random_state=2), labels mapped to \(\{0,1\}\): 2,000 for training and 10,000 for testing. GradientBoostingClassifier with depth-2 trees, 1,500 stages, random_state=0, \(\nu\in\{1,0.2\}\) and subsample \(\in\{1,0.5\}\); staged test log loss and misclassification rate. Smallest log loss: 0.178 after 247 trees (\(\nu=1\)), 0.171 after 982 (\(\nu=0.2\)), 0.140 after 890 (\(\nu=0.2\), half samples), 0.258 after 86 (\(\nu=1\), half samples). Smallest error 0.060 for \(\nu=0.2\) with half samples. Without shrinkage the training log loss falls to about \(10^{-8}\), and no tree after the 1,224th changes the test log loss by more than \(10^{-4}\). The vertical axes are narrowed to 0.08–0.5 and 0.04–0.16, which cuts off the first few rounds. |
| boost-partial-dependence.png | The histogram gradient boosting model of the chapter’s last code block (ESL problem with 24,000 points, random_state=3, 4,000 for training; 757 iterations chosen by early stopping). Partial dependence on the log-odds scale by scikit-learn’s recursion method, on 41-point grids between the 1st and 99th percentiles of each feature. The one-feature curves rise by 5.42 to 7.52 from \(x_j=0\) to \(x_j=2\). The two-feature surface on \((x_1,x_2)\) is bilinearly interpolated on a grid extending beyond the panel, contoured at 0, 2, 4, 6, 8, and 10, and clipped. |
12. Principal components and dimensionality reduction {#12-principal-components-and-dimensionality-reduction}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Figures that show the wine, digits, or make_circles data, fitted scikit-learn models, or the spiked data of the chapter’s code block read their numbers from Sources/Figure code/js/data/<name>.js, which the script ch12_pca.py writes with the original seeds and settings; the drawing code only draws them. The figure pca-fit-transform is simulated in the drawing code with the seeded linear congruential generator of the Foundations figure code, and the script recomputes its numbers independently with the same generator. The script also prints every number that the chapter and its captions quote from the figures. It needs NumPy, SciPy, and scikit-learn and runs in under ten seconds.
| Local figure | Data and construction |
|---|---|
| pca-fit-transform.png | Simulated in the drawing code. 120 training points \(\mu+1.6\,g_1e_1+0.45\,g_2e_2\) with \(\mu=(3,2)\), unit vectors \(e_1\) and \(e_2\) at 30° and 120°, and standard normal \(g_1,g_2\) (generator seed 5). New inputs \(a=\mu+2.4e_1+0.25e_2\) and \(b=\mu-1.3e_1+2.1e_2\), placed by hand so that \(b\) lies inside the training range in each coordinate. PCA from the sample covariance (divisor \(n-1\)) with \(k=1\): fitted eigenvalues 2.765 and 0.228, largest training residual 1.41, residuals of \(a\) and \(b\) 0.06 and 2.07, whitened scores of \(b\) \((-0.49,4.35)\). The dashed circle in the right panel has radius 3. |
| pca-scaling.png | Redrawn. scikit-learn wine data (178 samples, 13 features, three cultivars). PCA of the centered raw features and of the standardized features: scores on the first two components and the loadings of the first. Raw: 99.8% and 0.2% of the variance, first component proline (loading +1.00, magnesium next at +0.02), second component magnesium (+0.999); standard deviations of proline and magnesium 314.0 and 14.2. Standardized: 36.2% and 19.2%; largest loadings flavanoids +0.42, total phenols +0.39, OD280/OD315 +0.38. The raw panel’s vertical axis is stretched 12 times relative to its horizontal axis, which the panel states; the standardized panel uses equal scales. |
| pca-noise-eigenvalues.png | Redrawn. The data of the chapter’s probabilistic-PCA code block: 300 observations in 100 dimensions, standard normal noise plus spikes of variance 8, 3, and 0.4 along three random orthonormal directions (seed 0). Sample covariance eigenvalues (divisor \(n-1\)), 50 column-permuted copies drawn from the same generator for parallel analysis, and the Marchenko–Pastur density for \(\gamma=d/n=1/3\); histogram bins of width 0.2. Top eigenvalues 8.23, 4.17, 2.41; Marchenko–Pastur interval \([0.179,2.488]\); 95th percentiles of the permuted eigenvalues 2.83, 2.67, 2.58, 2.51 for ranks 1 to 4. The absolute cosines between the top three sample eigenvectors and the population directions are 0.97, 0.92, 0.42, against asymptotic limits 0.98, 0.93, 0; the eigenvalue limits of the two detectable spikes are 9.38 and 4.44. |
| pca-spike-phase-transition.png | One spike of size \(\ell\) along the first coordinate axis (the noise is rotation invariant), \(n=300\), \(d=100\), standard normal noise; 50 samples for each of 20 values of \(\ell\) from 0.05 to 16 (seed 12). For each sample, the top eigenvalue of the sample covariance (divisor \(n-1\)) and the squared cosine between its eigenvector and the spike direction; the figure shows the 10th, 50th, and 90th percentiles. At \(\ell=8\) the median top eigenvalue is 9.41 (middle 80%: 8.39 to 10.10); at \(\ell=3\), 4.46 (4.06 to 4.88) with squared cosine 0.87 (0.83 to 0.90); at \(\ell=0.4\), 2.42 (2.36 to 2.55) with squared cosine 0.03 (0.00 to 0.17). The orange points are the three spikes of pca-noise-eigenvalues, with squared cosines 0.93, 0.85, and 0.17. |
| pca-digits-components.png | The digits pipeline of the chapter’s code block: 1,257 training images (70/30 stratified split, random_state=0), StandardScaler, PCA(svd_solver="full"), LogisticRegression(max_iter=5000), 5-fold GridSearchCV over 20 values of \(k\) from 1 to 64, which include the seven of the code block and reproduce its accuracies. Explained-variance ratios of the standardized training images: 0.123 and 0.097 for the first two components, 90% first reached at \(k=30\) (0.904; 0.896 at \(k=29\)), four components of zero variance. Accuracy 0.935 at \(k=15\), 0.955 at \(k=30\), 0.964 at \(k=64\). |
| pca-pcr-ridge.png | Redrawn. Left: 200 Gaussian observations in ten dimensions with standard deviations 3, 2.5, 2, 1.6, 1.3, 1, 0.8, 0.6, 0.4, 0.25 (seed 3), centered; the ridge penalty, found by bisection so that its effective degrees of freedom equal 5, is 226.5, with shrinkage factors from 0.878 down to 0.053. Right: 300 points with standard deviations 2.5 and 0.5 rotated by 0.5 radians, and a response equal to 3 times the minor coordinate plus noise of standard deviation 0.3 (seed 5); points are shaded on a diverging scale clamped at \(\pm4\). The first principal direction carries 96.0% of the input variance; the least-squares coefficient direction is 89.7° from it. \(R^2\) is 0.0004 for PCR with one component and 0.957 for least squares. |
| pca-kernel-circles.png | Redrawn. make_circles with 400 points, factor 0.35, noise 0.06 (random_state=0); linear PCA and KernelPCA with the Gaussian kernel, \(\gamma=3\). scikit-learn fixes the signs of the kernel eigenvectors deterministically, so the panel regenerates without mirroring. Eigenvalues of the centered Gram matrix 53.45 and 47.59; a threshold on the first kernel component classifies all 400 points correctly. |
| pca-kernel-width.png | The rings of pca-kernel-circles with KernelPCA for \(\gamma=0.3\), 10, and 100, chosen to show the three regimes. The best threshold on the first kernel component classifies 0.662, 0.748, and 0.797 of the points (1.000 for \(\gamma=3\)). Mean distance of the scores from the origin: outer ring 0.586, 0.022, 0.011; inner ring 0.262, 0.623, 0.273. At \(\gamma=100\), half of the sum of squared scores on the first component comes from 17 points, all on the inner ring, whose radius is 0.35 times that of the outer ring. |
| pca-isomap-spiral.png | 300 points with \(t\) sorted uniform on \([0,1]\), angle \(\theta=\pi(0.75+2.5t)\), radius rising linearly in \(\theta\) from 0.35 to 1, and Gaussian noise of standard deviation 0.015 in each coordinate (seed 1). Isomap(n_neighbors=10, n_components=1) and PCA(1); the drawn graph is Isomap’s 10-nearest-neighbor graph (1,547 edges). A is the point with \(\theta\) nearest \(\pi\), and B the point of the next turn (\(\theta>2.5\pi\)) nearest to A: Euclidean distance 0.49, graph distance 4.11 over 56 edges. Rank correlation with \(t\): 1.000 for Isomap, 0.257 for the principal component. |
13. Clustering {#13-clustering}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Every figure except clust-lloyd-steps shows scikit-learn or SciPy fits: the script ch13_clustering.py computes them with the original datasets, seeds, and settings and writes them to Sources/Figure code/js/data/<name>.js, and the drawing code only draws them. The figure clust-lloyd-steps is simulated in the drawing code with the seeded linear congruential generator of the Foundations figure code, and the script recomputes its numbers independently with the same generator. The script also prints every number that the chapter and its captions quote from the figures. It needs NumPy, SciPy, and scikit-learn and runs in about ten seconds. All \(k\)-means fits use scikit-learn KMeans with its default Lloyd iterations. Cluster colors are matched to the generating groups by the one-to-one assignment that maximizes the number of agreeing points.
| Local figure | Data and construction |
|---|---|
| clust-lloyd-steps.png | Simulated in the drawing code. Three groups of 15 points around \((0,0)\), \((4,0.4)\), \((1.8,3.4)\) with standard deviation 0.75, and three distinct observations drawn uniformly as initial centers (generator seed 3, chosen so that two initial centers lie in the lower-left group and none in the upper one). Lloyd’s algorithm with ties to the lower index; each panel shows one assignment step, its Voronoi cells, and the following update. \(W\) after assignment and update: 330.8 and 150.2, 136.7 and 110.5, 81.1 and 49.9; the fourth assignment changes nothing, and the final partition equals the generating groups. |
| clust-kmeans-geometry.png | Redrawn. Three make_blobs datasets of 600 points: four groups with standard deviation 0.9 (random_state=6); three groups (random_state=170) sheared by the matrix \(\bigl(\begin{smallmatrix}0.6&-0.64\\-0.41&0.85\end{smallmatrix}\bigr)\); groups of 500, 60, and 60 points with standard deviations 2.2, 0.5, 0.5 (random_state=2). \(k\)-means with 10 initializations (random_state=0). Points are colored by generating group and the exact Voronoi cells of the fitted centers by the matched group; both axes share one scale. Adjusted Rand indices 1.00, 0.58, 0.13; on the right, 252 of the 500 points of the diffuse group fall in the cells of the two small groups. |
| clust-init.png | Redrawn. 800 points in eight groups of unit standard deviation on a \(4\times2\) grid with spacing 6 (random_state=0). 300 single runs each of random and \(k\)-means++ seeding (random_state 0–299); objectives are divided by the best found in any run, 1514.7. Left: the first random-seeding run whose objective exceeds 1.5 times the best (random_state=1, ratio 2.12), with the cluster spanning two groups and the two clusters sharing one group highlighted. Right: histograms in bins of width 0.085. Runs with ratio below 1.001: 119 (40%) for random and 290 (97%) for \(k\)-means++ seeding. Counting the groups whose center is the nearest group center of no fitted center, random seeding leaves 1 group uncovered in 157 runs (ratios 1.99 to 2.21) and 2 groups in 24 runs (3.11 to 3.40); \(k\)-means++ leaves 1 group in 10 runs. |
| clust-dendrogram.png | Redrawn. 30 points in three groups of ten around \((0,0)\), \((4,1)\), \((2,4)\) with standard deviation 0.7 (random_state=4); SciPy Ward linkage, whose merge heights are \(\sqrt{2\Delta(A,B)}\) (checked for every merge). Leaves in SciPy’s order; the cut lies halfway between the second- and third-to-last merges, at 8.99. Largest merge within a cluster 4.73, first merge between clusters 13.24. The three clusters (sizes 10, 9, 11) match the generating groups except for one point between the groups (adjusted Rand index 0.90). |
| clust-linkage.png | Redrawn. make_moons with 400 points, noise 0.05 (random_state=1), a blob of 150 points around \((2.6,1.3)\) with standard deviation 0.12 (random_state=1), and 12 points uniform on \([-1.2,3]\times[-0.8,1.6]\) (seed 0). AgglomerativeClustering into three clusters with single, complete, average, and Ward linkage; adjusted Rand indices on the non-noise points 0.00, 0.57, 0.66, 0.55. Single linkage gives clusters of 559, 2, and 1 points; without the noise points it recovers the three groups (adjusted Rand index 1.00). |
| clust-choose-k.png | Redrawn. 400 points in four unit-variance groups centered at \((0,0)\), \((5,0)\), \((0,5)\), \((6.5,6)\) (random_state=3); distances between centers 5.0 to 8.85. \(W(k)\) from 10 initializations for \(k=1,\ldots,8\) (elbow at 4: 2064 at \(k=3\), 796 at \(k=4\), 705 at \(k=5\)); gap statistic with 20 uniform reference sets over the bounding box (seed 1), maximal at \(k=4\) (1.12), with \(s_k\) between 0.021 and 0.035, choosing \(k=4\); mean silhouette, largest at \(k=4\) (0.648); stability as the mean adjusted Rand index between \(k\)-means fits on pairs of 80% subsamples, 20 pairs per \(k\), largest at \(k=4\) (1.000). The original description “two of them close together” was replaced by the distances, since no pair of groups is markedly closer than the others. |
| clust-structureless.png | The uniform square of the code block in “Comparing two partitions”: the script repeats the block’s draws from numpy.random.default_rng(0), so the 500 points, the ten \(k=4\) fits to 400-point subsamples (n_init=1, random_state 0–9), and the gap statistic with 10 uniform reference sets are the block’s. Pairwise adjusted Rand indices 0.65 to 0.99 (median 0.90); in all ten fits every center lies within 0.1 of a quadrant center. Gap values for \(k=1,\ldots,6\): 0.020, −0.015, −0.002, −0.026, −0.0005, −0.042, with \(s_2=0.032\); the rule chooses \(k=1\). |
| clust-spectral.png | The data of clust-linkage. Symmetrized 10-nearest-neighbor graph with 0/1 weights (3,363 edges), unnormalized Laplacian \(L=D_\Omega-\Omega\), and \(k\)-means (10 initializations, random_state=0) on the rows of the eigenvectors of its three smallest eigenvalues. Eigenvalues 0, 0, 0.004, 0.020, 0.032, 0.084, 0.091, 0.169; the two components are the blob with one noise point and the moons with the other eleven, and no edge joins the two moons directly. Spectral clustering and DBSCAN (eps=0.15, min_samples=5) both reach adjusted Rand index 1.00 on the non-noise points; DBSCAN labels 10 of the 12 noise points and no other point as noise and puts the other two in the lower moon. |
14. Gaussian mixtures and expectation maximization {#14-gaussian-mixtures-and-expectation-maximization}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Figures that show data drawn with NumPy, mixtures fitted by scikit-learn GaussianMixture, or the EM run of the chapter’s code block read their numbers from Sources/Figure code/js/data/<name>.js, which the script ch14_gmm_em.py writes with the original seeds and settings; the drawing code only draws them. The figures gmm-mixture-1d, em-convergence-rate, and gmm-kmeans-limit are computed in the drawing code, the first two with the seeded linear congruential generator of the Foundations figure code, and the script recomputes their quoted numbers independently with the same generator. The script also prints every number that the chapter and its captions quote from the figures. It needs NumPy, SciPy, and scikit-learn and runs in about 20 seconds. Ellipses are drawn at Mahalanobis distance 1 and 2 from each fitted mean, and point colors mix the component colors in proportion to the responsibilities.
The running example is the mixture with weights 0.5, 0.3, 0.2, means \((0,0)\), \((4,3)\), \((5,-1.5)\), and covariances whose entries \((\sigma_{11},\sigma_{12},\sigma_{22})\) are \((2,1.2,1.2)\), \((0.4,0,1.5)\), and \((1,-0.6,0.6)\).
| Local figure | Data and construction |
|---|---|
| gmm-mixture-1d.png | Computed in the drawing code. The mixture with weights 0.5, 0.3, 0.2, means \(-1.5\), \(1.5\), \(3.8\), and standard deviations 1.1, 0.6, 0.9, evaluated on a grid of step 0.02. 80 draws from the two-step story (generator seed 7: a uniform draw picks the label, then a normal draw the value), 40, 26, and 14 from the three components. At \(x_0=0.6\) the weighted component densities are 0.0293, 0.0648, and 0.0002, their sum is 0.0942, and the responsibilities are 0.311, 0.687, and 0.002. |
| gmm-fit.png | Redrawn. 600 points from the running example (seed 0; labels drawn with probabilities 0.5, 0.3, 0.2, giving 274, 191, and 135 points). Full-covariance fit with five initializations (random_state=0): weights 0.446, 0.328, 0.226 and means \((-0.05,-0.13)\), \((3.96,3.06)\), \((5.03,-1.50)\); 33 of the 600 points (5.5%) have no responsibility above 0.9. Right: filled contours of the fitted log density at integer levels from \(-12\), computed on a grid that extends 5% beyond the panel. |
| em-steps.png | The run of the chapter’s EM code block: 300, 180, and 120 points from the three components of the running example (seed 0), equal initial weights, the sample covariance of all points for every component, and initial means at three rows chosen by the same generator, \((-1.86,-1.14)\), \((4.00,1.89)\), \((5.07,-1.47)\). The panels show \(\theta^{(t)}\) for \(t=0,1,4,30\), with log-likelihoods \(-2748.333\), \(-2306.808\), \(-2153.899\), and \(-2102.655\); the stopping rule fires after the E-step of the 31st pass. Responsibilities are recomputed in the drawing code from the stored parameters. |
| em-lower-bound.png | Redrawn. Left: 40 points each from \(\mathcal N(-0.5,1)\) and \(\mathcal N(1,1)\) (seed 3); EM for the first mean from 3.5 with weights, variances, and the second mean fixed at their true values, giving \(\mu_1^{(1)},\mu_1^{(2)},\mu_1^{(3)}=2.033\), \(1.128\), \(0.267\) (the maximizer is \(-0.669\)). The log-likelihood and the bounds \(F(q^{(t)},\mu_1)\) are evaluated exactly on 301 grid points. Right: 600 points in six groups on a \(3\times2\) grid with spacing 5 (make_blobs, random_state=0); EM with six full-covariance components run one iteration at a time with warm_start, from 12 initializations at random observations (random_state 0–11). Six runs reach an average log-likelihood of \(-4.5324\) per observation; the others end at \(-4.6125\), \(-4.618\), \(-4.6335\), \(-4.6373\), \(-4.7152\), and \(-4.755\) after 200 iterations, and continuing them to 1,000 iterations changes none by more than 0.0004. |
| em-convergence-rate.png | Computed in the drawing code. 400 points from \(\tfrac12\mathcal N(-\Delta/2,1)+\tfrac12\mathcal N(\Delta/2,1)\) for \(\Delta=2,3,4\), with generator seed 3 for every \(\Delta\), so only the separation changes. EM for the weight, both means, and both variances, starting from equal weights, means at the sample mean minus and plus one sample standard deviation, and both variances at the sample variance; each run continues until no parameter changes by more than \(10^{-13}\), and its end point is taken as the limit \(\hat\theta\). The rate \(\lambda\) is the largest eigenvalue of \(I_c^{-1}I_m\) at \(\hat\theta\), with \(I_c\) diagonal in the parameters (weight, means, variances) and \(I_m\) the posterior covariance of the complete-data score, summed over observations: 0.9916, 0.9133, and 0.6923. The distance first falls below \(10^{-6}\) after 1,239, 125, and 37 iterations, and for \(\Delta=2\) it is \(2.8\times10^{-3}\) after 300. Right: the same eigenvalue per observation at the true parameters, integrated against the model density on a grid of step 0.005, for \(\Delta\) from 1 to 7 (0.995, 0.932, 0.725 at \(\Delta=2,3,4\)). |
| gmm-degenerate.png | The first loop of the chapter’s degenerate-solutions code block: 50 standard normal points (seed 1), first observation \(x_1=0.346\), sample mean \(-0.036\), and standard deviation 0.881 (divisor \(n\)). The mixture \(0.98\,\mathcal N(\bar x,s^2)+0.02\,\mathcal N(x_1,\sigma_2^2)\) is drawn for \(\sigma_2=0.3\), 0.1, 0.03, and its log-likelihood is evaluated for \(\log_{10}\sigma_2\) from 0.5 to \(-32.5\) in steps of 0.05. It stays between \(-64.8\) and \(-63.7\) for \(\sigma_2\ge10^{-2}\); the asymptote is \(-69.55-\log\sigma_2\). |
| gmm-covariance-types.png | The data of gmm-fit; the \(K=3\) fits of gmm-bic (three initializations, random_state=0). Spherical, diagonal, tied, and full: 11, 14, 11, and 17 free parameters, log-likelihoods \(-2332.9\), \(-2285.3\), \(-2308.2\), \(-2125.2\), and BIC 4736, 4660, 4687, 4359. |
| gmm-bic.png | Redrawn. The data of gmm-fit; BIC for one to six components and spherical, diagonal, tied, and full covariances, each with three initializations (random_state=0). The smallest value is 4359, for full covariances and \(K=3\); the restricted types reach their smallest values, 4535, 4522, and 4521, at \(K=6\). The original grouped bars on an axis starting at 4200 exaggerated the differences, so the redrawn figure uses lines. |
| gmm-kmeans-limit.png | Computed in the drawing code. Equal weights, common covariance \(\sigma^2I\) with \(\sigma=2\), 1, 0.5, and means at the generating means of the running example. The shading mixes tints of the component colors (34% of the way from white) by responsibility, on a raster at the device resolution; the solid curves are the level 0.9 of the largest responsibility, from a grid extended 5% beyond the panel, and the dashed lines are the exact Voronoi boundaries. |
| gmm-vs-kmeans.png | Redrawn. The sheared and unequal-size datasets of the chapter 13 geometry figure: make_blobs with 600 points (random_state=170) mapped by the matrix with rows \((0.6,-0.64)\) and \((-0.41,0.85)\), and 500, 60, 60 points with standard deviations 2.2, 0.5, 0.5 at \((0,0)\), \((4.2,3)\), \((4.2,-3)\) (random_state=2). Full-covariance mixtures with five initializations (random_state=0), adjusted Rand indices 1.00 and 0.94; the fitted components are numbered after the generating groups by the one-to-one assignment that maximizes the number of agreeing points, so each group has the color it has in clust-kmeans-geometry and the colors do not depend on the order in which scikit-learn returns the components; k-means with n_init=10 and random_state=0, as in chapter 13, 0.58 and 0.13. The shaded regions are the largest-responsibility regions of the fitted mixture, from a grid extended 5% beyond each panel. |
15. Gaussian processes {#15-gaussian-processes}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Six figures read their numbers from Sources/Figure code/js/data/<name>.js, which the script ch15_gaussian_processes.py writes: the posteriors, samples, and hyperparameter fits are computed there with NumPy and scikit-learn, by Cholesky factorization as in GPML Algorithm 2.1, and the drawing code only draws. The seventh, gp-covariance, is simulated in the drawing code with the seeded generator of the Foundations figure code. The script uses the seeds and settings of the earlier Matplotlib version for the five original figures, so they show the same samples, data, and fitted models, and it prints every number that the chapter and its captions quote from the figures, recomputing those of gp-covariance independently with the same generator. It runs in about two seconds.
| Local figure | Data and construction |
|---|---|
| gp-bayes-linreg.png | Redrawn. Line \(-0.3+0.5x\) with noise standard deviation 0.2 and 20 inputs uniform on \([-1,1]\) (seed 2); prior precision 2 on both weights, so \(w\sim\mathcal N(0,\frac12I)\). Posterior after 0, 2, and 20 observations, with 12 weight vectors drawn from each (same seed stream). Top: the 95% region of the prior or posterior of \((w_0,w_1)\), the ellipse of Mahalanobis radius \(\sqrt{5.991}\), and the drawn weights. Bottom: the drawn lines, the predictive mean, and the 95% interval for a new observation. The first two inputs are \(-0.477\) and \(-0.403\); after 20 observations the interval’s half-width is 0.402 to 0.443, against 0.392 for noise alone. |
| gp-covariance.png | 300 draws from the squared-exponential prior \(\exp\bigl(-(x-x')^2/2\bigr)\) on the grid \(0,0.05,\ldots,5\), each \(L\xi\) with \(L\) the Cholesky factor of \(K+10^{-8}I\) and \(\xi\) from makeRng(7). Left: the first six draws. Middle and right: the values of all draws at \(x_1=1\) against \(x_2=1.5\) and \(x_3=3.5\), with the exact 95% ellipse of each pair; correlations \(e^{-1/8}=0.882\) and \(e^{-25/8}=0.044\), sample correlations 0.876 and 0.052. |
| gp-prior-kernels.png | Redrawn. Three prior draws on 400 points of \([-3,3]\) (seed 5) for scikit-learn kernels RBF(1), RBF(0.3), Matern(1, nu=0.5), and ExpSineSquared(1, periodicity=2), via Cholesky factors with jitter \(10^{-8}\). The vertical range is \([-4.6,4.6]\), so that the Matérn draw, which reaches 4.42 and was clipped in the earlier version, is shown whole. |
| gp-posterior.png | Redrawn. \(f(x)=x\sin x\) on \([0,10]\), kernel \(9\cdot\)RBF(1.6); 7 noise-free observations (two at 9.49 and 9.50) and 20 observations with noise variance 1 (seed 1). Posterior mean, 95% interval for \(f\), and three posterior samples on a 500-point grid; on the right, the dashed 95% interval for a new observation adds the noise variance. |
| gp-marginal-likelihood.png | Redrawn. The scikit-learn example data: 20 inputs uniform on \([0,5]\) and \(y=0.5\sin3x+\mathcal N(0,0.5^2)\) (NumPy RandomState(0)). Profile log marginal likelihood, with \(s^2\) set to its maximizer \(y^\top R^{-1}y/n\) for \(R=\text{RBF}(\ell)+\rho I\), over \(\log_{10}\ell\in[-1.3,3]\) and \(\log_{10}\rho\in[-2.5,5.5]\) on the earlier \(90\times90\) spacing, extended by three grid steps on each side (\(96\times96\)) and clipped; contours one unit apart down to 12 below the maximum. Two fits of \(1.0\cdot\)RBF + WhiteKernel from \((\ell,\sigma_n^2)=(1,10^{-5})\) and \((100,1)\): \(s^2=0.409\), \(\ell=0.365\), \(\sigma_n^2=0.294\), log marginal likelihood \(-21.81\); and \(s^2=10^{-5}\) (the lower bound), \(\ell=109\), \(\sigma_n^2=0.637\), \(-23.87\), equal to the plateau value \(-\frac n2\bigl(\log(y^\top y/n)+1+\log2\pi\bigr)\) for pure noise. |
| gp-classification.png | 40 inputs uniform on \([0,8]\) and labels with \(P(Y=1\mid x)=1/\bigl(1+e^{-3\sin0.9x}\bigr)\) (seed 0; 19 positive). GaussianProcessClassifier with kernel \(1.0\cdot\)RBF(1.0) (random_state=0) fits \(s^2=3.87\), \(\ell=1.52\). The Laplace posterior is recomputed by Newton’s method (GPML Algorithms 3.1 and 3.2; approximate log marginal likelihood \(-21.53\), as in scikit-learn) on 401 points of \([0,10]\), and the logistic function is averaged over the latent Gaussian by 80-point Gauss–Hermite quadrature, which agrees with scikit-learn’s predict_proba to \(7\times10^{-5}\). The averaged probability differs from the logistic of the latent mean by at most 0.035 on \([0,8]\) and 0.044 overall (at \(x=9.18\)). |
| gp-bayesopt.png | Redrawn. Objective \(\sin3x+0.3x^2-0.6x\) on \([-2,2]\), kernel RBF(0.4) with unit variance and jitter \(10^{-8}\), initial evaluations at \(-1.5\), 0.2, 1.6; three rounds of expected improvement maximized on a 600-point grid, choosing 1.920, 1.285, and 1.513. The sixth evaluation gives \(-1.206\); the minimum on the grid is \(-1.208\) at 1.533. |
16. Semi-supervised and active learning {#16-semi-supervised-and-active-learning}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. All five figures rest on fitted models or simulations with NumPy generators, so each reads its numbers from Sources/Figure code/js/data/<name>.js, which the script ch16_ssl_active.py writes; the drawing code only draws. The script uses the seeds and settings of the earlier Matplotlib version for the two original figures, so they show the same fitted models, repeats the chapter’s threshold code exactly, and prints every number that the chapter and its captions quote from the figures. It runs in about 45 seconds. Label propagation is the harmonic solution on a symmetrized \(k\)-nearest-neighbor graph with Gaussian weights whose width \(\sigma\) is the median edge length.
| Local figure | Data and construction |
|---|---|
| ssl-em-misspecified.png | The model \(p(x,y)=\pi_y\,\mathcal N(x\mid\mu_y,s^2)\), two classes with a shared variance, fitted by EM to the labeled and unlabeled points, starting from the maximum likelihood estimate on the labeled points and stopping when the log-likelihood rises by less than a relative \(10^{-10}\). Model correct: classes \(\mathcal N(-1,1)\) and \(\mathcal N(1,1)\), equally likely (Bayes boundary 0, Bayes error 0.159). Model wrong: groups \(\mathcal N(-3,0.5^2)\) and \(\mathcal N(-0.5,0.5^2)\) of class 0 and \(\mathcal N(1.5,0.5^2)\) of class 1, each with probability 1/3 (Bayes boundary 0.50, Bayes error 0.015). Run \(r=0,\ldots,99\) (seed \(r\)) draws two labeled points per class and 3000 unlabeled points; the fits for \(u=0,10,30,100,300,1000,3000\) use the first \(u\) of them. Errors of the fitted boundary are exact normal probabilities. Mean errors fall from 0.187 to 0.159 when the model is correct and rise from 0.090 to 0.303 when it is wrong. The density panels show run 0 with \(u=1000\): boundaries 0.00 and 0.75 (labels only), errors 0.159 and 0.221; and, for the wrong model, fitted means −2.68 and 0.67, standard deviation 1.02, weights 0.35 and 0.65, boundaries −1.19 and 0.25 (labels only), errors 0.306 and 0.024. |
| ssl-harmonic-graph.png | Eleven hand-placed points, listed in the script, in two groups of five and one point in the gap; the positions were chosen to give a clear gap. Symmetrized 2-nearest-neighbor graph with 13 edges and \(\sigma=1.00\); labeled nodes \((0,0)\) with \(y=0\) and \((6.05,0.05)\) with \(y=1\). Harmonic values by a linear solve (0.07 to 0.21 in the left group, 0.52 in the gap, 0.84 to 0.92 in the right group). Jacobi sweeps of the chapter’s code from \(f_U=0\): the spectral radius of \(D_{UU}^{-1}W_{UU}\) is 0.86, and the largest error is 0.185, 0.037, and 0.002 after 10, 20, and 40 sweeps. The script checks that the values after 10 sweeps are the probabilities of stopping at the node labeled 1 within 10 steps. |
| ssl-label-propagation.png | Redrawn. Top: make_moons with 400 points, noise 0.08 (random_state=0). Bottom: two Gaussian clusters of 200 points centered at \((\pm2.5,0)\) with standard deviations 0.7 and 1.0, labeled by the sign of the second coordinate (seed 1). Two labeled points per class (seed 3); logistic regression with \(C=100\) on the four labels; label propagation on the symmetrized 10-nearest-neighbor graph (2370 and 2501 edges, \(\sigma=0.101\) and \(0.300\)). The left panels draw this graph. The propagated values are extended to a 96 × 64 grid reaching 5% beyond each panel by the Gaussian-weighted average over the 10 nearest data points, and the shading is their 1/2 contour; the earlier version extended the propagated labels with a 5-nearest-neighbor classifier. Accuracies on all 400 points: moons 0.835 and 1.000, clusters 0.955 and 0.670; means over 50 random labelings (seeds 0–49): 0.789 and 0.992, 0.772 and 0.644. |
| active-learning.png | Redrawn. Left: two Gaussian classes of 300 points each with means \((-1.2,0)\) and \((1.2,0.3)\) and unit variances (seed 0); 25 uncertainty-sampling queries for logistic regression (\(C=1\)) from one labeled point per class, colored from light to dark magenta in query order. The dashed boundary is fitted to the two initial labels, the solid one after 25 queries; the queries have median distance 0.19 from it, against 1.26 for all points. Middle: digits 3 and 8 from scikit-learn (357 images), pixels scaled to \([0,1]\). Right: make_classification with 1,500 samples, 20 features, 5 informative, 5 redundant, flip_y=0.02 (random_state=0). Both curves average 20 runs, each with a stratified 60/40 pool–test split (random_state \(r\)) and four initial labels (seed \(r\)), up to 80 labels; bands are ±2 standard errors. Digits: uncertainty sampling 0.976 at 20 labels, random sampling at most 0.973. Synthetic: the largest shortfall of uncertainty sampling is 0.042, at 12 labels, and it is not below random sampling from 38 labels on. With flip_y=0 (not drawn) the shortfall is at most 0.015, at 8 labels, and ends at 27 labels. |
| active-thresholds.png | The chapter’s threshold code: 100,000 pool inputs uniform on \([0,1]\) (seed 0), threshold \(t^\ast=0.3137\). Left: binary search for \(\varepsilon=0.01\), seven queries at 0.4989, 0.2499, 0.3768, 0.3139, 0.2817, 0.2974, 0.3058, ending with the region \([0.3058,0.3139]\) of length 0.0081. Right: passive means over the code’s 200 random orders (seeds 0–199), computed with the same permutations in vectorized form, at \(\varepsilon=0.3,0.1,0.03,0.01,0.003,0.001\): 6.2, 20.1, 68.1, 207.2, 697.0, 2262.4, with standard errors 0.3, 1.0, 3.6, 10.6, 36.8, 113.4; the exact expectation \(2/\varepsilon\) of Appendix B; binary-search counts on 167 values of \(\varepsilon\) from 0.5 to \(10^{-4}\) (13 at \(10^{-4}\)); and the reference \(\log_2(1/\varepsilon)\). A check with 10,000 fresh samples of uniform inputs at \(\varepsilon=0.01\) (seed 1) gives a mean of 200.9. |
17. Smoothing, density estimation, and basis expansions {#17-smoothing-density-estimation-and-basis-expansions}
Each figure is drawn with D3 and typeset with KaTeX, then rendered to PNG at twice its CSS size by headless Chromium, using the drawing library of the Foundations figures. The source of each is Sources/Figure code/js/src/<name>.js, and the computing setup gives the commands. Figures that need NumPy’s generator, a fitted model, or a search over a random sample take their numbers from the script ch17_smoothing.py, which writes them to Sources/Figure code/js/data/<name>.js; the drawing code only draws. The exact bias–variance figure and the spline bases are analytic and compute their own curves; the former takes from the script only the two sample bandwidths it marks. The seeds and settings are those of the original Matplotlib figures and of the chapter’s code blocks, so the redrawn figures show the same samples and fitted objects as before. The script also recomputes, independently of the drawing code, every number that the chapter and its captions quote from the figures; it needs NumPy, SciPy, and scikit-learn and runs in about 20 seconds.
The density figures share the running mixture \(0.35\,\mathcal N(-1,0.35^2)+0.65\,\mathcal N(1,0.7^2)\) and the 200 draws from it made by the chapter’s first code block (seed 0: the 200 component labels first, then the two normal vectors).
| Local figure | Data and construction |
|---|---|
| kde-construction.png | The first 20 of the 200 draws. Density histograms with bin width 0.5 and edges at multiples of 0.5, and shifted by 0.25: counts \(5,3,1,4,1,2,3,1\) from \(-1.5\) against \(1,7,0,4,2,1,2,2,1\) from \(-1.75\). Gaussian kernel estimate with \(h=0.3\), drawn as the sum of the 20 bumps \(K((x-x_i)/h)/(nh)\). |
| kde-bias-variance.png | Analytic, \(n=200\), Gaussian kernel. With \(\phi_v\) the \(\mathcal N(0,v)\) density, \(\mathbb E\hat f_h=\sum_j\pi_j\phi_{s_j^2+h^2}(\cdot-\mu_j)\) and \(n\operatorname{Var}\hat f_h=\sum_j\pi_j\phi_{s_j^2+h^2/2}(\cdot-\mu_j)/(2\sqrt\pi h)-(\mathbb E\hat f_h)^2\); the integrated squared bias and variance are sums of Gaussian products. Bands are \(\pm2\) standard deviations for \(h=0.04\), \(0.21\), and \(0.80\). The MISE is smallest, \(0.00730\), at \(h=0.212\); the AMISE formula gives \(0.191\) with \(R(f'')=5.619\) (a normal density with the sample standard deviation \(1.112\) has \(0.1245\)). At \(h_{\mathrm{cv}}=0.182\) the MISE is \(1.04\) times the minimum, at Silverman’s \(0.347\) it is \(1.57\) times. |
| kde-bandwidth.png | Redrawn. The 200 draws (seed 0). Gaussian kernel estimates with \(h=0.04\), the cross-validated \(h\), and \(h=0.8\) over a histogram with bin width 0.15; leave-one-out log-likelihood over the 200 bandwidths of the chapter’s code, logarithmically spaced from 0.01 to \(10^{0.3}\approx2\) (the original figure used 80, which also gives 0.18): maximum \(-277.0\) at \(h_{\mathrm{cv}}=0.182\); \(-337.0\) at \(h=0.04\) and \(-308.1\) at \(h=0.8\). Silverman’s rule with the robust scale: \(\hat\sigma=1.112\), \(\widehat{\mathrm{IQR}}/1.34=1.480\), \(h=0.347\). |
| local-regression.png | Redrawn. 100 inputs uniform on \([0,1]\), \(m(x)=2.5x+0.4\sin6x\), noise standard deviation 0.25 (seed 2). Nadaraya–Watson and local linear fits with a Gaussian kernel and \(h=0.1\) on 201 grid points: \(0.353\) and \(-0.010\) at \(x=0\), \(2.045\) and \(2.404\) at \(x=1\). Equivalent-kernel weights at \(x_0=0\) and \(0.5\); at \(x_0=0\) the local linear weights fall below \(-0.001\) for inputs in \([0.15,0.34]\), the bias given the inputs is \(0.342\) (local constant) and \(0.023\) (local linear), and \(\sum_iw_i^2\) is 2.94 times larger for the local linear weights. Smoother traces \(4.45\) and \(5.35\); the leave-one-out shortcut agrees with refitting for both. |
| splines-basis.png | Analytic. Interior knots \(k/6\), \(k=1,\ldots,5\), on \([0,1]\). Left: \(1,x,x^2,x^3\) and \((x-\xi_k)_+^3/(1-\xi_k)^3\). Right: the nine cubic B-splines on the clamped knot vector (boundary knots repeated four times) by the Cox–de Boor recursion; the fifth is highlighted with its support \([\xi_1,\xi_5]\), and the dashed line is their sum. The script computes the condition numbers quoted in the text for the ten-knot design of the splines figure: \(38.9\) for SplineTransformer B-splines and \(6.16\times10^4\) for truncated powers with the same eight interior knots. |
| splines.png | Redrawn. 120 inputs uniform on \([0,1]\), \(m(x)=\sin(12(x+0.2))/(x+0.2)\), noise standard deviation 0.6 (seed 4). Left: SplineTransformer cubic B-splines with 4, 10, and 40 uniform knots, including the knots at the smallest and largest input (6, 12, and 42 basis functions), and least squares without a separate intercept, since the B-splines sum to one. (The original figure added an intercept; the design was then exactly collinear, and its 40-knot curve, which dipped to \(-6.4\), was a rounding artifact.) The 40-knot fit reaches \(-3.49\) at \(x=0.020\), between the two smallest inputs \(0.008\) and \(0.042\). Right: SciPy make_smoothing_spline with \(\lambda=10^{-8}\), the GCV choice from 40 values between \(10^{-8}\) and \(10^{-2}\), and \(10^{-2}\); effective degrees of freedom are traces of the hat matrix, \(77.1\), \(12.2\) (at \(\lambda=10^{-4}\)), and \(4.6\). Curves are drawn over the range of the data. |
| splines-smoother.png | The data of the splines figure. The smoother matrix \(S_\lambda\) is built column by column by smoothing the unit vectors. Left: \(\mathrm{GCV}=n\,\mathrm{RSS}/(n-\operatorname{tr}S_\lambda)^2\) against \(\operatorname{tr}S_\lambda\) for the 40 penalties; minimum \(0.425\) at \(\lambda=10^{-4}\), noise variance \(0.36\). Right: rows of \(S_\lambda\) at \(\lambda=10^{-4}\) for the smallest input (\(0.008\); own weight \(0.629\), most negative weight \(-0.040\)) and the input nearest 0.5 (largest weight \(0.055\)). \(S_\lambda\) is symmetric with eigenvalues in \((0,1]\), two of them equal to one. |
| gam-backfitting.png | Redrawn. The additive model of the chapter’s backfitting code (seed 6): 500 points, three uniform features on \([-1,1]\), noise standard deviation 0.4; 20 backfitting sweeps with cubic smoothing splines, \(\lambda=10^{-2}\). The true components are centered by their sample means. |
| kdtree-dimension.png | The chapter’s k-d tree (median splits cycling through the coordinates, leaves of at most 16 points: 11 splits deep, 2,048 leaves of 9 or 10 points) on 20,000 points uniform in \([0,1]^d\), 100 uniform queries per dimension. One generator (seed 0) is used first for \(d=2,5,10,20\), exactly as in the chapter’s code, then for \(d=1,3,4,6,7,8,12,15\). Every search is exact. Fraction of the data examined: 0.05%, 0.08%, 0.18%, 0.41%, 0.78%, 1.46%, 3.52%, 5.69%, 20.5%, 73.7%, 98.9%, 100% for \(d=1,2,3,4,5,6,7,8,10,12,15,20\). Mean number of the 11 splitting planes on the query’s path closer than its nearest neighbor: 0.03, 0.56, 1.58, 2.66, 3.72, 4.56, 6.01, 6.62, 8.04, 10.28, 10.99, 11.00. |