Statistical Learning I

Supervised learning is an impossible problem made tractable by restriction: any function passing through the training points has zero training error, so without a constraint on the class of functions there is nothing to learn. Every method is therefore a triple — a structural model (the function class), a score (the loss it minimizes), and a search (how it optimizes) — and the whole subject is choosing a restriction matched to the unknown truth. One tradeoff governs all of it: bias vs variance, with the curse of dimensionality the reason local methods need help. This first half builds the frame, then the restrictions that are smooth — linear models, shrinkage, generative and discriminative classifiers, and basis expansions — plus the machinery to assess any of them. The algorithmic restrictions (trees, ensembles, margins, unsupervised structure) are the second half, [[06b_Statistical_Learning_II]]. Prerequisites cashed in: projection, SVD, eigendecomposition (track 2); MLE, CLT, bias–variance, sufficiency (track 3); priors and ridge/lasso-as-MAP (track 7 §3).

1. The frame: what we estimate and why we must restrict

• The data model: $Y = f(X) + \varepsilon$, with $E(\varepsilon) = 0$ and $\varepsilon \perp X$. Two goals pull in opposite directions — prediction (treat $f$ as a black box, only $\hat Y$ matters) and inference (understand how $X$ drives $Y$, so $f$ must be interpretable). Restrictive models serve inference; flexible models serve prediction.
• The regression function is the conditional mean — derived. Under squared-error loss the expected prediction error of any $f$ is $\mathrm{EPE}(f) = E_{X,Y}\big[(Y - f(X))^2\big] = E_X\,E_{Y\mid X}\big[(Y - f(X))^2 \mid X\big].$ Minimize pointwise: for fixed $x$, choose the constant $c = f(x)$ minimizing $E[(Y-c)^2 \mid X=x]$. Differentiate in $c$: $\frac{d}{dc}E[(Y-c)^2\mid x] = -2\,E[Y - c\mid x] = 0 \Rightarrow c = E[Y\mid x]$. So

$f^*(x) = E[Y \mid X = x],$ the regression function — the best possible predictor under squared error. (Absolute-error loss instead gives the conditional median — more robust.)

• The Bayes classifier — derived from 0–1 loss. For classification with loss matrix $L(k,\ell)$, the risk of predicting $g$ at $x$ is $\sum_k L(\mathcal G_k, g)\,P(\mathcal G_k \mid x)$. Under 0–1 loss this is $1 - P(g \mid x)$, minimized by $\hat G(x) = \arg\max_k P(\mathcal G_k \mid X = x).$ Predict the most probable class. Its error rate is the Bayes rate — the classification analogue of irreducible error $\mathrm{Var}(\varepsilon)$, a floor no method can beat.
• Why restriction is forced. Minimizing $\mathrm{RSS}(f) = \sum_i (y_i - f(x_i))^2$ over all functions has infinitely many solutions — any $f$ interpolating the points scores zero. Useless: under a fresh sample with different noise, an interpolator errs everywhere. We must shrink the class of admissible $f$. Almost every restriction is some form of smoothness — “the function is roughly constant in small neighborhoods” — imposed explicitly (linearity, splines) or implicitly (the neighborhood size in KNN).
• KNN as the canonical local estimator. Approximate the conditional mean by a local average: $\hat f(x) = \frac{1}{k}\sum_{x_i \in N_k(x)} y_i,$ $N_k(x)$ the $k$ nearest training points. As $N \to \infty$ and $k/N \to 0$ this converges to $E[Y\mid x]$ — KNN is universal. Its effective number of parameters is $\approx N/k$ (imagine $N/k$ non-overlapping neighborhoods, one mean each), so small $k$ = flexible.

Implications

• The conditional mean is the target every regression method is trying to estimate; methods differ only in how they approximate it (global linear fit vs local average vs basis expansion).
• The Bayes classifier and the regression function are the same idea — best pointwise prediction — and both are unattainable (we don’t know $P(Y\mid X)$); methods are estimates of them.
• “No restriction ⟹ interpolation ⟹ zero training error ⟹ useless test error” is the seed of overfitting and of the entire bias–variance story (§2).

Core competency set

• Derive $f^*(x) = E[Y\mid x]$ from squared-error EPE; state the L1 analogue.
• Derive the Bayes classifier from 0–1 loss; relate the Bayes rate to irreducible error.
• Explain why unrestricted RSS minimization fails and name smoothness as the usual fix.

2. Bias, variance, and the curse of dimensionality

• The decomposition — derived. Test point $x_0$, $Y = f + \varepsilon$, with $\varepsilon$ fresh noise independent of the training-set estimate $\hat f$. Insert $f$ and expand:

$E[(Y - \hat f)^2] = E[\varepsilon^2] + 2E[\varepsilon(f - \hat f)] + E[(f - \hat f)^2].$

Middle term $= 0$ ($\varepsilon \perp \hat f$, $E[\varepsilon] = 0$), leaving $\sigma^2 + E[(f - \hat f)^2]$. Insert $E\hat f$ and expand again:

$E[(f - \hat f)^2] = (f - E\hat f)^2 + 2(f - E\hat f)E[E\hat f - \hat f] + E[(E\hat f - \hat f)^2].$

Middle term $= 0$ ($E[E\hat f - \hat f] = 0$). So

$\mathrm{EPE}(x_0) = \underbrace{\sigma^2}_{\text{irreducible}} + \underbrace{(f - E\hat f)^2}_{\text{bias}^2} + \underbrace{\mathrm{Var}(\hat f)}_{\text{variance}}.$

Flexibility trades the last two: flexible ⟹ lower bias, higher variance.

• KNN bias–variance, explicitly. With $\hat f(x_0) = \frac1k\sum_{\ell} f(x_{(\ell)}) + \frac1k\sum_\ell \varepsilon_\ell$, $\mathrm{EPE}(x_0) = \sigma^2 + \Big[f(x_0) - \tfrac1k\textstyle\sum_{\ell=1}^k f(x_{(\ell)})\Big]^2 + \frac{\sigma^2}{k}.$ Variance $\sigma^2/k$ falls as $k$ grows; bias grows as the neighborhood widens off $x_0$. (If $f$ is linear and the neighborhood symmetric, the average is unbiased — bias is a curvature/asymmetry effect.)
• OLS vs 1-NN — the worked comparison. Condition on the training $X$‘s, so $\hat f = X\hat\beta = Ay$ with $A = X(X^TX)^{-1}X^T$. The fit’s average variance:

$\frac1N\sum_i \mathrm{Var}(\hat f_i) = \frac{\sigma^2}{N}\mathrm{tr}(A) = \frac{p}{N}\sigma^2 \qquad (\mathrm{tr}\,A = p).$

OLS pays $\frac pN\sigma^2$; 1-NN pays a full $\sigma^2$ (one noisy neighbor):

$\mathrm{EPE}_{\text{OLS}} \approx \sigma^2 + \tfrac pN\sigma^2 + \text{bias}^2, \qquad \mathrm{EPE}_{\text{1-NN}} \ge 2\sigma^2 + \text{bias}^2.$

When the linear model is even approximately right, $\frac pN\sigma^2 \ll \sigma^2$ — if the linear model is correct, KNN does much worse.

• The curse of dimensionality. To capture a fraction $r$ of uniform data in a $p$-cube needs edge length

$e_p(r) = r^{1/p}.$

At $p = 10$, $r = 0.1$: $0.1^{1/10} \approx 0.80$ — you span 80% of every coordinate. “Local” is no longer local: a neighborhood holding any useful fraction is nearly the whole space, so a local average is secretly global and KNN’s bias creeps back. Most points also sit near the boundary, and density falls as $N^{1/p}$. Any method averaging over small isotropic neighborhoods is cursed.

Implications

• Bias–variance is the master dial: every tuning parameter (the $k$ in KNN, $\lambda$ in ridge, tree size, spline df) is a point on this tradeoff, chosen to minimize test error not training error.
• The curse is why we bother with structured models: a global linear fit doesn’t need local neighborhoods, so it sidesteps the dimensionality explosion at the cost of bias.
• The OLS-$\frac{p}{N}$ vs 1-NN-$\sigma^2$ comparison is the quantitative case for parametric models in low-data / high-noise / sparse regimes.

Core competency set

• Derive the bias–variance decomposition (both cross terms dying) and the KNN special case.
• Reproduce the OLS $\frac{p}{N}\sigma^2$ variance and the 1-NN $\sigma^2$, and state the conclusion.
• Compute $e_p(r) = r^{1/p}$ for a concrete $(p, r)$ and state the three faces of the curse.

3. Linear methods and shrinkage

Least squares as projection.

• Model $f(X) = \beta_0 + \sum_j X_j\beta_j$ — linear in the parameters, $X$ any transform. Minimize $\mathrm{RSS}(\beta) = \|y - X\beta\|^2$. Differentiate:

$\frac{\partial \mathrm{RSS}}{\partial\beta} = -2X^T(y - X\beta).$

Set to zero — the normal equations, which say the residual is orthogonal to the columns:

$X^TX\hat\beta = X^Ty \;\Rightarrow\; \hat\beta = (X^TX)^{-1}X^Ty.$

So $\hat y = X\hat\beta = Hy$ is the orthogonal projection of $y$ onto $C(X)$, with hat matrix $H = X(X^TX)^{-1}X^T$ (symmetric, idempotent, $\mathrm{tr}\,H = p$). Rank-deficient $X$: $\hat y$ is still the projection, only $\hat\beta$ is non-unique.

• Solve by QR, not by inverting $X^TX$. Since orthogonal $Q$ preserves norm, $X = QR$ gives

$\|y - X\beta\|^2 = \|Q^Ty - R\beta\|^2 = \|Q_1^Ty - R_1\beta\|^2 + \|Q_2^Ty\|^2.$

The first term is zeroed by $\hat\beta = R_1^{-1}Q_1^Ty$ (a triangular solve, numerically stable); the second is the irreducible $\mathrm{RSS} = \|Q_2^Ty\|^2$, and $\hat y = Q_1Q_1^Ty$.

• Add Gaussian errors $\varepsilon \sim N(0, \sigma^2 I)$ and $\hat\beta \sim N(\beta, (X^TX)^{-1}\sigma^2)$, $s^2 = \mathrm{RSS}/(N-p)$ unbiased for $\sigma^2$, and the coefficient $t$-statistics and the $F$-test for nested models follow (cross-link track 4).
• Gram–Schmidt reading. Regressing $y$ on orthogonalized predictors gives $\hat\beta_p = \frac{\langle z_p, y\rangle}{\langle z_p, z_p\rangle}$, where $z_p$ is $x_p$ with the other predictors regressed out. So $\mathrm{Var}(\hat\beta_p) = \sigma^2/\|z_p\|^2$ — correlated predictors shrink $\|z_p\|$ and inflate the variance, the seed of collinearity trouble (VIF, track 4).
• Equivariance. OLS is equivariant under nonsingular linear reparametrization of $X$ ($\hat\beta$ transforms back exactly). PCA, ridge, and lasso are not — which is why they require standardizing the inputs.

Gauss–Markov, derived. Among all linear unbiased estimators of an estimable $c^T\beta$, OLS has minimum variance (BLUE). Proof: any linear estimator is $a^Ty$; unbiasedness $E[a^Ty] = a^TX\beta = c^T\beta$ for all $\beta$ forces $a^TX = c^T$. The OLS estimator $c^T\hat\beta = a^{*T}y$ has weight $a^* = X(X^TX)^{-1}c$, which lies in $C(X)$; split any competitor as $a = a^* + (a - a^*)$, where $a - a^* \perp C(X)$ (both satisfy the same constraint $a^TX = c^T$, so $(a-a^*)^TX = 0$). Then $\mathrm{Var}(a^Ty) = \sigma^2\|a\|^2 = \sigma^2\big(\|a^*\|^2 + \|a - a^*\|^2\big) \ge \sigma^2\|a^*\|^2 = \mathrm{Var}(c^T\hat\beta),$ with equality iff $a = a^*$. Off-subspace mass is pure variance cost — the same split-orthogonally-and-drop move as the projection itself.

• The loophole. Unbiasedness is a self-imposed restriction: a biased estimator can have smaller MSE. Since $\mathrm{MSE} = \mathrm{Var} + \mathrm{bias}^2$, shrinking coefficients toward zero can shrink the variance faster than it grows the bias (James–Stein) — the entire motivation for the shrinkage methods below.

Ridge regression.

• $\hat\beta^{\text{ridge}} = \arg\min_\beta \|y - X\beta\|^2 + \lambda\|\beta\|_2^2$, equivalently constrain $\sum\beta_j^2 \le t$. Centered $X$, solve by setting the gradient to zero: $-2X^T(y - X\beta) + 2\lambda\beta = 0 \;\Rightarrow\; \hat\beta^{\text{ridge}} = (X^TX + \lambda I)^{-1}X^Ty.$ Adding $\lambda I$ makes the system always invertible — ridge fixes the singularity of $p > N$ as a bonus.
• SVD reveals what it does — derive it. Write $X = UDV^T$, so $X^TX = VD^2V^T$. Because $VV^T = I$, write $\lambda I = V(\lambda I)V^T$ and combine inside one $V(\cdot)V^T$:

$X^TX + \lambda I = V(D^2 + \lambda I)V^T \;\Rightarrow\; (X^TX + \lambda I)^{-1} = V(D^2 + \lambda I)^{-1}V^T.$

With $X^Ty = VDU^Ty$, the $V^TV = I$ in the middle cancels:

$\hat\beta^{\text{ridge}} = V(D^2 + \lambda I)^{-1}V^T \cdot VDU^Ty = V\,(D^2 + \lambda I)^{-1}D\,U^Ty.$

Push through to fitted values $\hat y = X\hat\beta = UDV^T\hat\beta$; another $V^TV = I$ cancels and the diagonal factors $D\cdot(D^2+\lambda I)^{-1}\cdot D$ combine entrywise:

$\hat y_\lambda = \sum_{j=1}^p u_j\,\frac{d_j^2}{d_j^2 + \lambda}\,u_j^Ty.$

Ridge projects $y$ onto each left singular vector $u_j$ and shrinks that coordinate by $\frac{d_j^2}{d_j^2+\lambda}$ — small-$d_j$ (low-variance) directions are shrunk hardest. It implicitly assumes the response varies most where the inputs vary most. Effective df: $\mathrm{df}(\lambda) = \mathrm{tr}(H_\lambda) = \sum_j \frac{d_j^2}{d_j^2 + \lambda},$ ranging from $p$ (at $\lambda = 0$) to $0$ (as $\lambda \to \infty$). Orthonormal $X$: $\hat\beta^{\text{ridge}} = \hat\beta/(1+\lambda)$ — uniform scaling. Numbers: with singular values $d = (3, 1, 0.2)$ and $\lambda = 1$, the shrinkage factors are $\frac{9}{10} = 0.90$, $\frac12 = 0.50$, $\frac{0.04}{1.04} \approx 0.04$ — the strong direction barely touched, the weak (noisy) direction nearly erased; df $= 0.90 + 0.50 + 0.04 = 1.44$.

Lasso.

• $\hat\beta^{\text{lasso}} = \arg\min_\beta \frac12\|y - X\beta\|^2 + \lambda\|\beta\|_1$, equivalently $\sum|\beta_j| \le t$. The L1 penalty sets coefficients exactly to zero — simultaneous shrinkage and selection, a convex relaxation of best-subset’s L0 count.
• Soft thresholding — derived (orthonormal case). With orthonormal columns the objective separates coordinatewise into

$\tfrac12(\beta_j - \beta_j^*)^2 + \lambda|\beta_j|,$

where $\beta_j^* = x_j^Ty$ is the OLS coordinate (the cross term drops because the OLS residual is orthogonal to $x_j$). Minimize over $\beta_j$ by cases on its sign, since $|\beta_j|$ has a kink at $0$:

• $\beta_j > 0$: differentiable, $(\beta_j - \beta_j^*) + \lambda = 0 \Rightarrow \beta_j = \beta_j^* - \lambda$ — feasible only if $\beta_j^* > \lambda$.
• $\beta_j < 0$: symmetrically $\beta_j = \beta_j^* + \lambda$ — feasible only if $\beta_j^* < -\lambda$.
• $|\beta_j^*| \le \lambda$: neither branch is feasible, so the minimum sits at the kink, $\beta_j = 0$.

Stitch the cases into one expression:

$\hat\beta_j = \mathrm{sign}(\beta_j^*)\,(|\beta_j^*| - \lambda)_+ \quad\text{— soft thresholding.}$

Contrast ridge’s proportional shrinkage $\beta_j^*/(1+\lambda)$: lasso translates toward zero and truncates. Numbers ($\lambda = 1$): $S(3, 1) = 2$ (shrink the survivor); $S(0.8, 1) = 0$ (kill the small one). Ridge at $\lambda = 1$ would instead give $3/2 = 1.5$ and $0.8/2 = 0.4$ — nothing zeroed.

• $\lambda_{\max}$: the smallest $\lambda$ killing all coefficients equals $\max_j|\langle x_j, y\rangle|$ — the first variable to enter is the most correlated with $y$. The path is piecewise linear (LARS), computable in one OLS-cost sweep. Active-set variables satisfy $|\langle x_j, r\rangle| = \lambda$.
• The geometry. Elliptical RSS contours first touch the constraint region at the optimum. The L2 ball is a disk (touch point generically off-axis ⟹ no zeros); the L1 ball is a diamond with corners on the axes (touch point often at a corner ⟹ a zero). In high dimensions the diamond has many corners — sparsity is generic.

Choosing among them.

• All coefficients nonzero ⟹ ridge wins (lower variance, similar bias). Few nonzero (sparse truth) ⟹ lasso wins. Elastic net $\lambda\sum(\alpha\beta_j^2 + (1-\alpha)|\beta_j|)$ interpolates: it produces zeros like lasso but averages correlated groups like ridge (lasso arbitrarily picks one of a correlated pair; ridge splits the weight).
• Bayesian reading (track 7 §3): ridge = posterior mode under a Gaussian prior, lasso = under a Laplace prior, best-subset = under a spike-at-zero prior. Every penalty is a log-prior; $|\beta_j|^q$ is the power family ($q = 2, 1, 0$).

Derived-direction methods.

• PCR: regress $y$ on the first $M$ principal components $z_j = Xv_j$ (the eigenvectors of $X^TX$, or the SVD right vectors). Unsupervised — directions chosen by input variance, blind to $y$. In the SVD basis PCR keeps components $1..M$ at full weight and discards the rest; ridge keeps all but shrinks smoothly by $\frac{d_j^2}{d_j^2+\lambda}$ — PCR is a hard-threshold cousin of ridge.
• PLS: supervised — directions with high variance and high correlation with $y$ (regress $y$ on each $x_j$, weight by the coefficients, form $z_1$, orthogonalize, repeat). Variance usually dominates, so PLS behaves much like PCR/ridge. Equivalent to OLS after $M = p$ steps.

Implications

• Ridge/lasso/PCR/PLS all operate through the SVD of $X$ — they are different shrinkage profiles on the principal coordinates (smooth, threshold-at-zero, hard-cut, $y$-weighted). Seeing them as one family is the payoff.
• Shrinkage beats best-subset on noisy data because subset selection is a discrete search (high variance); continuous shrinkage is stable. Subset df overcounts (it spends df hunting and keeps coefficients unshrunk).
• For prediction, ridge is the safe default; lasso when you also want a short interpretable list; elastic net when predictors come in correlated groups.

Core competency set

• Derive the normal equations and the projection/QR forms; state the Gram–Schmidt variance $\sigma^2/\|z_p\|^2$.
• Derive ridge’s SVD shrinkage and its df; derive lasso soft-thresholding and contrast with ridge.
• State $\lambda_{\max}$, the L1-vs-L2 geometry, and the ridge↔PCR SVD relationship.
• Give the penalty↔prior dictionary and place elastic net.

4. Classification I — generative (density) methods

Model the class-conditional densities, then invert with Bayes. The prior is $\pi_k = P(G = k)$, the density $f_k(x) = P(X = x \mid G = k)$, and $P(G = k \mid X = x) = \frac{\pi_k f_k(x)}{\sum_\ell \pi_\ell f_\ell(x)}.$

LDA — derived. Model each class as multivariate Gaussian with a common covariance, $f_k(x) = N(\mu_k, \Sigma)$. Compare two classes by the log posterior-ratio, which by Bayes splits into a prior part and a density part:

$\log\frac{P(G=k\mid x)}{P(G=\ell\mid x)} = \log\frac{\pi_k}{\pi_\ell} + \log\frac{f_k(x)}{f_\ell(x)}.$

The Gaussian log-density is $\log f_k(x) = -\tfrac12(x-\mu_k)^T\Sigma^{-1}(x-\mu_k) + c$, where $c = -\tfrac p2\log 2\pi - \tfrac12\log|\Sigma|$ is the same for every class (shared $\Sigma$) and so cancels in the ratio. Expand the surviving quadratic:

$(x-\mu_k)^T\Sigma^{-1}(x-\mu_k) = x^T\Sigma^{-1}x - 2\mu_k^T\Sigma^{-1}x + \mu_k^T\Sigma^{-1}\mu_k.$

The leading $x^T\Sigma^{-1}x$ is identical for $k$ and $\ell$ — again because $\Sigma$ is shared — so it cancels in the difference, and only terms linear in $x$ remain:

$\log\frac{f_k}{f_\ell} = (\mu_k - \mu_\ell)^T\Sigma^{-1}x - \tfrac12\big(\mu_k^T\Sigma^{-1}\mu_k - \mu_\ell^T\Sigma^{-1}\mu_\ell\big).$

Linear in $x$ ⟹ linear decision boundaries. Reading off the per-class piece gives the discriminant function

$\delta_k(x) = x^T\Sigma^{-1}\mu_k - \tfrac12\mu_k^T\Sigma^{-1}\mu_k + \log\pi_k, \qquad \hat G(x) = \arg\max_k \delta_k(x).$ Plug in $\hat\pi_k = N_k/N$, $\hat\mu_k =$ class mean, and the pooled covariance $\hat\Sigma = \frac{1}{N-K}\sum_k\sum_{g_i=k}(x_i - \hat\mu_k)(x_i - \hat\mu_k)^T$.

• Picture to hold: the discriminant direction $\Sigma^{-1}(\mu_2 - \mu_1)$ is a skew projection — the presence of $\Sigma^{-1}$ tilts it off the line joining the means so that the projected Gaussians overlap as little as possible.

QDA: drop the common-covariance assumption; the quadratic terms survive ⟹ quadratic boundaries. Cost: a separate $\Sigma_k$ per class (many parameters when $p$ is large). Regularized DA shrinks $\hat\Sigma_k$ toward the pooled $\hat\Sigma$ (parameter $\alpha$: $\alpha=1$ QDA, $\alpha=0$ LDA), and the pooled $\hat\Sigma$ toward a scalar $\gamma I$ — a ridge for covariance.

Fisher / reduced-rank LDA. The $K$ class centroids span an affine subspace of dimension $\le K-1$; since classification depends only on distances to centroids (in the $\Sigma$ metric), project onto that subspace — free dimension reduction. Fisher’s criterion: find $a$ maximizing between-class over within-class variance, $\max_a \frac{a^T B a}{a^T W a} \quad\text{(Rayleigh quotient)},$ $B$ = between-class, $W$ = pooled within-class covariance. Reformulate as $\max a^TBa$ s.t. $a^TWa = 1$ — a generalized eigenvalue problem (whiten by $W^{-1/2}$, then ordinary PCA on the centroids). The leading discriminant coordinates often separate the classes in 2–3 dimensions for visualization.

Shrunken centroids (the wide-data classifier, $p \gg N$). Standardize each class-centroid deviation from the overall centroid by the pooled within-class SD, then soft-threshold it (lasso again): deviations below $\Delta$ collapse to zero, removing that gene/feature from that class’s rule. The discriminant becomes $\delta_k(x^*) = \log\pi_k - \frac12\sum_j (x_j^* - \bar x'_{jk})^2/s_j^2$ with shrunken centroids $\bar x'_{jk}$. Performs feature selection LDA can’t.

Naive Bayes. Assume the within-class features are independent: $f_k(x) = \prod_j f_{kj}(x_j)$. High bias, low variance — and for classification you can tolerate a lot of bias (you only need the argmax right). It is exactly a GAM on the logit: $\log\frac{P(y=1\mid x)}{P(y=0\mid x)} = \alpha + \sum_j g_j(x_j)$, fit by densities rather than likelihood.

Generative vs discriminative. LDA models the full joint $P(X, G)$ (assumes Gaussians); logistic regression (§5) models only the conditional $P(G \mid X)$, leaving $P(X)$ arbitrary. Same linear-logit form, different estimation:

• LDA has lower variance when the Gaussian assumption holds (it uses more structure), but is non-robust to outliers (every point informs $\hat\Sigma$).
• Logistic is more general and robust, the safer default when the densities are non-Gaussian.

Linear regression of an indicator matrix is a third option (one-hot $Y$, regress, classify to largest fitted value) but suffers masking: with $K \ge 3$ collinear classes, a middle class can be dominated everywhere and never predicted; up to degree $K-1$ polynomials are needed to fix an artifact LDA doesn’t have. Avoid it for $K \ge 3$.

Implications

• All of LDA/QDA/naive Bayes/shrunken-centroids are the same Bayes-rule skeleton with different density assumptions — the assumption is the bias–variance knob (common $\Sigma$ → linear/low-variance; per-class $\Sigma$ → quadratic/higher-variance; independence → highest bias).
• LDA’s robustness track record despite non-Gaussian data is the recurring lesson: the data often only supports a simple boundary, and the stable Gaussian estimate beats fancier alternatives.
• Shrinkage reappears here as soft-thresholded centroids — the lasso idea is method-agnostic.

Core competency set

• Derive the LDA discriminant from the Gaussian log-ratio and explain why the boundary is linear; write the pooled $\hat\Sigma$.
• State QDA/RDA, the Fisher Rayleigh quotient and its eigen-reformulation, and shrunken centroids.
• Contrast generative vs discriminative (variance/robustness) and describe masking.

5. Classification II — discriminative (logistic regression)

• Model the logit linearly: $\log\frac{P(Y=1\mid x)}{P(Y=0\mid x)} = \beta_0 + \beta^Tx$, equivalently $p(x) = \frac{e^{\beta_0 + \beta^Tx}}{1 + e^{\beta_0 + \beta^Tx}}$ (the logistic squashes $R$ into $(0,1)$). The coefficient is a log-odds effect, not a probability effect — $\partial p/\partial x$ depends on $x$.
• Fit by MLE — derive the gradient. Conditioning on $X$, each $y_i$ is Bernoulli$(p_i)$ with $p_i = p(x_i)$, so the conditional log-likelihood is

$\ell(\beta) = \sum_i \big[y_i\log p_i + (1-y_i)\log(1 - p_i)\big].$

Substitute the model ($\log\frac{p_i}{1-p_i} = \beta^Tx_i$, $1-p_i = (1+e^{\beta^Tx_i})^{-1}$); each term collapses to

$y_i\,\beta^Tx_i - \log\!\big(1 + e^{\beta^Tx_i}\big).$

Differentiate one term, using $\frac{d}{d\eta}\log(1+e^\eta) = p_i$:

$\frac{\partial}{\partial\beta}\Big[y_i\,\beta^Tx_i - \log(1+e^{\beta^Tx_i})\Big] = y_ix_i - p_ix_i = (y_i - p_i)\,x_i.$

Sum over $i$ — the gradient is just the covariate-weighted prediction error:

$\nabla\ell(\beta) = \sum_i (y_i - p_i)\,x_i = X^T(y - p).$

• The Hessian, and why the problem is concave. Differentiate the gradient; only $p_i$ depends on $\beta$, and the logistic derivative is $\frac{\partial p_i}{\partial\beta} = p_i(1-p_i)\,x_i^T$ (i.e. $\sigma' = \sigma(1-\sigma)$):

$\nabla^2\ell(\beta) = -\sum_i p_i(1-p_i)\,x_ix_i^T = -X^TWX, \qquad W = \mathrm{diag}\big(p_i(1-p_i)\big).$

Every weight $p_i(1-p_i) > 0$, so $X^TWX \succeq 0$ and $\ell$ is concave — one global maximum, no local traps (contrast the non-convex networks of [[06b_Statistical_Learning_II]] §4).

• Newton’s method is reweighted least squares (IRLS). The Newton update is $\beta \leftarrow \beta - (\nabla^2\ell)^{-1}\nabla\ell$:

$\beta^{\text{new}} = \beta + (X^TWX)^{-1}X^T(y - p).$

Pull $X^TW$ out of the last term by defining the working response $z = X\beta + W^{-1}(y - p)$; the update becomes a weighted least-squares fit:

$\beta^{\text{new}} = (X^TWX)^{-1}X^TW\,z.$

So each step regresses $z$ on $X$ with weights $W$, then $p, W, z$ are recomputed and the step repeats — iteratively reweighted least squares. (The weight $p_i(1-p_i)$ is the inverse variance of the logit; this is the delta-method bridge to WLS, track 3.)

• Deviance plays the role of RSS: $\mathrm{dev} = -2\ell(\hat\beta)$. For nested models, $\mathrm{dev}_0 - \mathrm{dev}_1 \to \chi^2_{p-q}$ (a $\chi^2$, not an $F$ — there is no global $\sigma^2$). Asymptotically $\mathrm{Cov}(\hat\beta) = (X^TWX)^{-1}$ (the inverse Fisher information — track 3).
• Separable-data blow-up. If the classes are linearly separable, the MLE is undefined — to push fitted probabilities to $0/1$ some coefficient must run to $\pm\infty$. Near-separable data ⟹ exploding variance. The fix is regularization (ridge/lasso logit), which is also required for a solution when $p > N$.
• Multiclass: model $K-1$ logits against a base class, or use the symmetric softmax $P(G = j\mid x) = e^{\eta_j}/\sum_\ell e^{\eta_\ell}$ (the natural form under a penalty).

Implications

• Concavity is why logistic/Poisson GLMs are reliable workhorses — one optimum, no restarts (contrast the non-convex NNs of [[06b_Statistical_Learning_II]]).
• The IRLS view unifies GLM fitting with weighted least squares: every GLM is “OLS in a loop” on a linearized response.
• Separability is the discriminative twin of the curse: in high dimensions data is usually separable, so regularization is not optional.

Core competency set

• Write the logistic log-likelihood, gradient $X^T(y-p)$, and Hessian $-X^TWX$; argue concavity.
• Explain IRLS as Newton = weighted least squares; define deviance and the $\chi^2$ nested test.
• Explain the separable-data blow-up and the $p>N$ regularization need.

6. Model assessment and selection

• The goal is test error, estimated honestly. Training error is biased down and monotone in flexibility — it cannot select models. Two routes: adjust training error analytically, or resample to estimate test error directly.
• Analytic criteria (for a fit with $d$ effective parameters, $\hat\sigma^2$ from a low-bias model): $C_p = \frac1N(\mathrm{RSS} + 2d\hat\sigma^2), \quad \mathrm{AIC} \propto C_p, \quad \mathrm{BIC} = \frac{1}{N\hat\sigma^2}(\mathrm{RSS} + d\hat\sigma^2\log N), \quad \text{adj-}R^2 = 1 - \tfrac{\mathrm{RSS}/(N-d-1)}{\mathrm{TSS}/(N-1)}.$ $C_p$/AIC add $2d$ per parameter (prediction-oriented, asymptotically like CV); BIC adds $d\log N$ (heavier ⟹ smaller models, selection-consistent — recovers the true model as $N\to\infty$). For non-Gaussian models replace RSS with deviance.
• Cross-validation. Partition into $K$ folds; fit on $K-1$, test on the held-out fold, average. LOOCV ($K = N$) is deterministic and low-bias but high-variance (the $N$ training sets are nearly identical ⟹ correlated estimates); $K = 5$ or $10$ is the usual sweet spot. OLS shortcut (LOOCV without refitting): $\mathrm{CV}_{(N)} = \frac1N\sum_i\Big(\frac{y_i - \hat y_i}{1 - h_{ii}}\Big)^2,$ with $h_{ii}$ the leverage. For model selection, CV chooses the tuning parameter (e.g. subset size); the actual model is then refit on all the data — different folds may pick different subsets of that size, and that’s fine.
• The wrong way to CV — the canonical trap. Proposed: (1) screen all $p$ predictors on the full data, keep the 200 most correlated with $y$; (2) CV a classifier on those 200. With $p \gg N$, even pure-noise predictors will correlate with $y$ by chance; screening on the full data lets the lucky ones leak into every fold, so CV reports a low error for a model with no real signal. Fix: the entire pipeline — screening included — must happen inside each fold, refit fresh on each training split. Anything done to the data before CV must be CV’d.
• Bootstrap. Resample $N$ points with replacement $B$ times; the spread of a statistic across replicates estimates its standard error — substituting computation for analytic SEs, and valuable when $X$ is random or the SE has no closed form (e.g. SEs after model selection, which the naive formulas get wrong).
• The 1-SE rule. Among models within one standard error of the CV minimum, pick the simplest — bias toward parsimony when the extra complexity buys nothing significant.

Implications

• AIC-for-prediction vs BIC-for-truth is the one-line rule; both are cheap shadows of CV / the Bayesian evidence (track 7 §4).
• “CV the whole pipeline” generalizes far beyond screening — imputation, scaling parameters, feature learning all must live inside the fold or the estimate is optimistic.
• CV estimates have real variance (with small $N$, a null problem can show 20–80% error across runs) — report it, and don’t over-trust a single CV number.

Core competency set

• Write $C_p$/AIC/BIC/adj-$R^2$ and state the prediction-vs-truth roles.
• Explain LOOCV’s bias/variance, the OLS leverage shortcut, and that CV selects the tuning parameter.
• Reproduce the wrong-way-to-CV failure and the fix; say what the bootstrap buys.

7. Basis expansions and smoothing

Stay linear-in-parameters but enrich $X$: $f(x) = \sum_m \theta_m h_m(x)$ for chosen basis functions $h_m$ (polynomials, indicators, splines, sigmoids). Fitting is still least squares — flexibility without leaving the linear machinery.

• Step functions / piecewise constant: indicators $h_m(x) = \mathbf 1(c_m \le x < c_{m+1})$ — bin and average. Discontinuous.
• Regression splines. Piecewise cubics joined at $K$ knots with continuous value, first, and second derivatives — an order-$M$ spline is piecewise degree $M-1$ with continuity up to derivative $M-2$. The truncated-power basis: $f(x) = \beta_0 + \beta_1 x + \beta_2 x^2 + \beta_3 x^3 + \sum_{k=1}^K \beta_{3+k}(x - \xi_k)_+^3,$ each $(x-\xi_k)_+^3$ adding a curvature change at knot $\xi_k$ while preserving the lower-derivative continuity. Natural cubic splines add linearity beyond the boundary knots — spending 4 df to tame the wild polynomial tails (Gibbs/Runge behavior), which can be reinvested as more interior knots. Knots typically at quantiles of $x$; specify by df and let the data place them.
• Smoothing splines — the penalty route. Instead of choosing knots, put a knot at every $x_i$ and penalize curvature: $\min_f \sum_i (y_i - f(x_i))^2 + \lambda\int f''(t)^2\,dt.$ Remarkably the unique minimizer is a natural cubic spline with knots at the data points — an infinite-dimensional problem with a finite-dimensional solution. In basis form $\mathrm{RSS}(\theta) = (y - N\theta)^T(y - N\theta) + \lambda\theta^T\Omega\theta$ with $\Omega_{jk} = \int N_j''N_k''$, giving $\hat\theta = (N^TN + \lambda\Omega)^{-1}N^Ty$ and a linear smoother $\hat f = S_\lambda y$.
• Effective df = $\mathrm{tr}(S_\lambda)$, monotone in $\lambda$ — invert it to specify df directly. $S_\lambda$’s eigenvalues are $\le 1$ (it shrinks, never amplifies), and the two eigenvalues exactly $1$ correspond to the unpenalized constant and linear functions (curvature-free ⟹ no penalty). Each row of $S_\lambda$ is an equivalent kernel — the smoother is a local weighted average in disguise. $\lambda$ chosen by (efficient LOO) CV.
• Local regression. Fit a low-degree polynomial at each target $x_0$ weighted by a kernel $K_\lambda(x_0, \cdot)$: $\min_\beta \sum_i K_\lambda(x_0, x_i)(y_i - \beta_0 - \beta_1 x_i)^2$. Local linear corrects the boundary bias of local constant (kernel smoothing) — at the edge a kernel reaches asymmetrically, biasing a plain average; the linear fit compensates. Generalizes cleanly to a few dimensions (then the curse bites).
• GAMs — additivity beats the curse: $f(x) = \alpha + \sum_j f_j(x_j)$, each $f_j$ a smooth (spline/loess). Flexible per-coordinate, no interactions (the price), interpretable (plot each $f_j$). Fit by backfitting (block coordinate descent): cycle, fitting $f_j$ to the partial residual $y - \alpha - \sum_{k\neq j}f_k(x_k)$ with a smoother, until convergence. For logistic GAMs wrap backfitting in the Newton/IRLS loop.

Implications

• Smoothing splines are ridge for functions: the curvature penalty is an L2 penalty on the spline coefficients, and df = $\mathrm{tr}(S_\lambda)$ mirrors ridge’s $\mathrm{tr}(H_\lambda)$ — same shrinkage idea, different basis.
• “Linear in the parameters” is the unifying thread of §3 and §7: splines, polynomials, and indicators all keep you in least-squares-land, so all the §6 assessment machinery applies unchanged.
• GAMs are the sweet spot between linear models and full nonparametrics — they buy flexibility while dodging the dimensionality explosion by forbidding interactions, the same bet trees and boosting will revisit ([[06b_Statistical_Learning_II]]).

Core competency set

• Write the truncated-power cubic-spline basis and say what natural splines fix.
• State the smoothing-spline penalty, its natural-cubic-spline minimizer, and df = $\mathrm{tr}(S_\lambda)$.
• Explain local linear’s boundary-bias correction and the GAM backfitting loop.

8. Memorize cold

• $f^*(x) = E[Y\mid x]$ minimizes squared-error EPE; Bayes classifier $= \arg\max_k P(k\mid x)$; Bayes rate = classification irreducible error.
• Unrestricted RSS ⟹ interpolation ⟹ must restrict (smoothness); KNN $\hat f = \frac1k\sum_{N_k}y_i$, eff. params $N/k$, universal.
• Bias–variance: $\mathrm{EPE} = \sigma^2 + \mathrm{bias}^2 + \mathrm{Var}$; KNN variance $\sigma^2/k$.
• OLS variance $\frac{p}{N}\sigma^2$ (= $\frac{\sigma^2}{N}\mathrm{tr}\,H$) vs 1-NN $\sigma^2$; curse edge length $e_p(r) = r^{1/p}$.
• Normal equations $\hat\beta = (X^TX)^{-1}X^Ty$; $\hat y = Hy$ projection; QR: $\hat\beta = R_1^{-1}Q_1^Ty$; $\mathrm{Var}(\hat\beta_p) = \sigma^2/\|z_p\|^2$.
• Ridge $\hat\beta = (X^TX + \lambda I)^{-1}X^Ty$; SVD shrink $\frac{d_j^2}{d_j^2+\lambda}$; df $= \sum\frac{d_j^2}{d_j^2+\lambda} = \mathrm{tr}(H_\lambda)$.
• Lasso soft-threshold $\mathrm{sign}(\beta^*)(|\beta^*| - \lambda)_+$; $\lambda_{\max} = \max_j|\langle x_j, y\rangle|$; L1 diamond corners ⟹ zeros.
• ridge=Gaussian-prior MAP, lasso=Laplace, subset=L0; PCR hard-thresholds PCs, ridge shrinks them; PLS supervised.
• LDA discriminant $\delta_k = x^T\Sigma^{-1}\mu_k - \frac12\mu_k^T\Sigma^{-1}\mu_k + \log\pi_k$; common $\Sigma$ ⟹ linear; QDA per-class $\Sigma$ ⟹ quadratic.
• Fisher: $\max_a a^TBa/a^TWa$ (Rayleigh); shrunken centroids = soft-thresholded LDA.
• generative (LDA, full joint, low-var, non-robust) vs discriminative (logistic, conditional, robust); indicator regression masks for $K\ge3$.
• Logistic: $\nabla\ell = X^T(y-p)$, $\nabla^2\ell = -X^TWX$ (concave), Newton = IRLS; deviance $-2\ell$; nested $\to\chi^2$; separable ⟹ MLE blows up.
• $C_p = \frac1N(\mathrm{RSS} + 2d\hat\sigma^2)$; AIC for prediction, BIC ($d\log N$) for truth; LOOCV $= \frac1N\sum(\frac{y_i - \hat y_i}{1-h_{ii}})^2$.
• CV the whole pipeline (screening inside the fold); 1-SE rule; bootstrap for SEs after selection.
• Smoothing spline: minimizer is natural cubic spline at the data; $\hat f = S_\lambda y$, df $= \mathrm{tr}(S_\lambda)$; GAM $f = \alpha + \sum f_j$ by backfitting.

Named moves (cross-track glossary): split-orthogonally-and-project (OLS/QR, Gauss–Markov — track 4); trade-bias-for-variance (shrinkage, James–Stein — track 7); shrink-in-the-SVD-basis (ridge/PCR); soft-threshold (lasso, shrunken centroids); recognize-the-shape via Bayes rule (LDA/QDA — track 7); Newton-as-reweighted-least-squares (IRLS); CV-the-whole-pipeline; penalize-curvature (smoothing splines); additivity-beats-the-curse (GAMs).