Statistical Learning II

The second half turns from smooth restrictions (linear models, splines — [[06a_Statistical_Learning_I]]) to algorithmic ones: partition the space (trees), average many unstable fits (bagging, forests), fit residuals greedily (boosting), compose functions of functions (neural nets), maximize a margin (SVMs), or impose no labels at all (unsupervised). The organizing frame from 06a still holds — every method is structure + score + search, and bias–variance is the master dial — but here the search carries the intellectual weight: these criteria are non-convex or combinatorial, so we approximate with greedy recursion, gradient descent, and convex relaxations, and we pay for it in variance. Two recurring cures: average to kill variance (bagging, forests) and bet on sparsity (boosting, the lasso’s spirit). Prerequisites cashed in: bias–variance and shrinkage (06a §2–3), the lasso/L1 idea (06a §3), kernels-as-inner-products and the SVD (track 2), EPE and the conditional mean (06a §1). Closes with missing data and a meta-frame for choosing methods at all.

1. Trees (CART)

• Structure: partition the input space into disjoint rectangles $\{R_m\}$ covering it, predict a constant per region: $\hat f(x) = \sum_{m=1}^M \bar y_m\,\mathbf 1(x \in R_m).$ Given the regions, the constants are trivial (the region mean, for squared error); the hard part is the regions. Optimizing over all partitions is NP-hard, so restrict to axis-aligned rectangles built by greedy recursive binary splitting.
• The split criterion (regression): a split is a variable $j$ and cutpoint $s$, cutting the current region into the two half-spaces $R_1(j,s) = \{X_j < s\}$ and $R_2(j,s) = \{X_j \ge s\}$. Pick the $(j,s)$ minimizing the post-split RSS, each child predicted by its own mean: $\min_{j,s}\Big[\sum_{x_i \in R_1(j,s)}(y_i - \bar y_{R_1})^2 + \sum_{x_i \in R_2(j,s)}(y_i - \bar y_{R_2})^2\Big].$ Recurse on the children. Categorical predictors: order the levels by their mean $y$, then treat as ordinal (avoids the $2^{\text{levels}}$ search).
• Why this dodges the curse: it considers one axis at a time, never searching for neighbors in all $p$ dimensions at once — unlike KNN (06a §2).
• Classification — and why misclassification error fails as the split score. Misclassification rate $1 - \max_k \hat p_{mk}$ is not a continuous/sensitive function of the split: two children can both have the same majority class (so zero improvement in error) even when the split sharply purifies them. Greedy search needs a differentiable surrogate that rewards purity. Reframe: estimate class probabilities $\hat p_{mk} = N_{mk}/N_m$ and score the node by squared error on the class indicators $d_{ik} = \mathbf 1(y_i = k)$. Take one class $k$ and split the sum by indicator value: each of the $N_{mk}$ points with $d_{ik} = 1$ contributes $(1 - \hat p_{mk})^2$, each of the $N_m - N_{mk}$ points with $d_{ik} = 0$ contributes $(0 - \hat p_{mk})^2 = \hat p_{mk}^2$:

$\sum_{x_i \in R_m}(d_{ik} - \hat p_{mk})^2 = N_{mk}(1 - \hat p_{mk})^2 + (N_m - N_{mk})\,\hat p_{mk}^2.$

Substitute $N_{mk} = N_m\hat p_{mk}$ and $N_m - N_{mk} = N_m(1 - \hat p_{mk})$:

$= N_m\,\hat p_{mk}(1 - \hat p_{mk})^2 + N_m(1 - \hat p_{mk})\,\hat p_{mk}^2.$

Factor out $N_m\,\hat p_{mk}(1 - \hat p_{mk})$:

$= N_m\,\hat p_{mk}(1 - \hat p_{mk})\underbrace{\big[(1 - \hat p_{mk}) + \hat p_{mk}\big]}_{=\,1} = N_m\,\hat p_{mk}(1 - \hat p_{mk}).$

Sum over classes — the per-node squared-error risk is $N_m$ times the Gini index

$\sum_{k} \hat p_{mk}(1 - \hat p_{mk}),$

maximal ($1 - 1/K$) at uniform, zero at a pure node. Entropy $-\sum_k \hat p_{mk}\log\hat p_{mk}$ is an equivalent purity measure. Use Gini/entropy to grow (they reward confidence gains); use misclassification error to prune when accuracy is the goal. Numbers (2 classes): a node at $\hat p = 0.7$ has misclassification $0.3$ and Gini $2(0.7)(0.3) = 0.42$; a split into $\hat p = 0.9$ and $\hat p = 0.6$ children (equal sizes) leaves misclassification $\frac12(0.1) + \frac12(0.4) = 0.25$ but Gini $\frac12(0.18) + \frac12(0.48) = 0.33$ — both improve, yet had the children stayed majority-same-class, misclassification wouldn’t have moved while Gini still would. That gap is why Gini grows trees.

• Right-sized trees — cost-complexity pruning. A single stopping threshold is short-sighted (a weak split can enable a strong one beneath it — e.g. a symmetric interaction). Instead grow a large tree $T_0$, then prune. Charge $\alpha$ per leaf and minimize penalized RSS over subtrees: $C_\alpha(T) = \sum_{m=1}^{|T|}\sum_{x_i \in R_m}(y_i - \bar y_{R_m})^2 + \alpha|T|, \qquad |T| = \#\text{leaves},$ the Lagrangian form of “best subtree with a budget of leaves.” At $\alpha = 0$ the full tree wins; as $\alpha$ rises, collapsing a leaf pair pays off exactly when the per-leaf RSS reduction it gave up falls below $\alpha$. Always collapsing the current weakest link (smallest reduction-per-leaf) makes the minimizers a nested sequence $T_0 \supset T_1 \supset \cdots$, so one bottom-up pass yields the whole path; choose $\alpha$ by CV.
• Missing values — surrogate splits: when the primary split variable is missing for an observation, send it down using the most-correlated alternative variable’s split (computed locally within the node). A graceful local imputation, also handles missingness at training time.

Implications

• Trees are interpretable (read the path to any prediction), invariant to monotone transforms of $X$ (only order matters ⟹ immune to predictor outliers and scaling), handle mixed/missing data, and do automatic variable selection (a variable matters iff it’s split on).
• But: piecewise-constant ⟹ high bias on smooth/linear truths; data fragmentation ⟹ can’t model dependence on many variables; and high variance — small data changes reshape the tree (the greedy multiplicative structure compounds errors). These three weaknesses are exactly what §2–3 fix.
• The Gini-over-misclassification choice is a general lesson: pick a differentiable surrogate aligned with the goal when the true loss is non-smooth (recurs in SVMs §5, boosting §3).

Core competency set

• Write the regression split objective and the constant-per-region predictor; explain the categorical-ordering trick.
• Explain why misclassification error fails as a split score and derive Gini as squared-error-on-probabilities.
• State cost-complexity pruning and surrogate splits; list trees’ three weaknesses.

2. Bagging and random forests

• Bagging (bootstrap aggregating): trees are high-variance; averaging kills variance. Recall $\mathrm{Var}(\bar X) = \sigma^2/B$ — so fit $B$ trees on bootstrap resamples and average: $\hat f_{\text{bag}}(x) = \frac1B\sum_{b=1}^B \hat f^{*b}(x) \quad\text{(classification: majority vote).}$ Grow the trees deep and unpruned. The reason: averaging leaves bias untouched and only attacks variance. By linearity the bag has the same expectation as a single tree,

$E[\hat f_{\text{bag}}(x)] = \frac1B\sum_b E[\hat f^{*b}(x)] = E[\hat f(x)],$

so $\text{bias}(\hat f_{\text{bag}}) = \text{bias}(\hat f)$ is fixed no matter how you build the trees — the only term averaging can shrink is the variance. So push each tree to low bias (deep, unpruned) and accept its high variance, which averaging then removes. $B$ is not a tuning parameter (more never overfits; pick $B$ where the error settles). Cost: lost interpretability (recover variable importance by total RSS/Gini reduction attributed to each variable, averaged over trees).

• Out-of-bag error: each bootstrap sample omits ~1/3 of points; predict each point from the trees that didn’t see it ⟹ a free test-error estimate, no separate CV.
• Random forests — bagging with a twist that fixes bagging’s limit. If one predictor is dominant, every bagged tree splits on it first ⟹ the trees are correlated, and correlation sets a floor on what averaging can do. For $B$ identically-distributed trees with variance $\sigma^2$ and pairwise correlation $\rho$,

$\mathrm{Var}\big(\hat f_{\text{bag}}\big) = \rho\sigma^2 + \frac{1 - \rho}{B}\sigma^2.$

As $B \to \infty$ the second term vanishes but the first, $\rho\sigma^2$, does not — that is the floor. Driving $B$ up can’t beat it; the only lever left is lowering $\rho$. Fix: at each split consider only a random subset of $m \approx \sqrt p$ predictors. This decorrelates the trees — on average $(p-m)/p$ of splits ignore the dominant variable, letting others contribute — so averaging bites harder.

• Gain in variance reduction outweighs the small bias from splitting on weaker variables. $m = p$ recovers bagging; small $m$ helps most with many correlated predictors. Forests work better for classification than regression (classification is nearly piecewise-constant anyway). Numbers: $p = 100$ predictors ⟹ $m = \sqrt{100} = 10$ candidates per split, so a dominant predictor is off the menu at $\frac{90}{100} = 90\%$ of splits — that’s the decorrelation. Picture to hold: bagged trees are a forest of near-copies all forking on the same first variable; the random-subset rule forces them to branch differently, so their errors cancel on averaging.

Implications

• Bagging is the canonical variance-reduction move and applies to any unstable learner, not just trees (dropout in neural nets is its spiritual cousin — averaging over perturbed models).
• The decorrelation insight — averaging helps only to the extent the things averaged are independent — is why RF beats bagging and is a general principle for ensembles.
• OOB makes forests nearly tuning-free off the shelf, a big part of their popularity.

Core competency set

• Explain bagging via $\mathrm{Var}(\bar X) = \sigma^2/B$ and why trees are grown deep/unpruned; define OOB.
• Explain the correlation problem and how $m \approx \sqrt p$ decorrelates; state the $m = p$ limit.

3. Boosting and gradient boosting (MART)

The crown jewel: instead of averaging independent trees (bagging), grow them sequentially, each correcting the last. Boosting any weak learner — especially shallow trees — yields top-tier accuracy.

• The model is an additive expansion $F(x) = \sum_{j} a_j\,T_j(x)$ over a base class (trees). Treating each candidate tree as a feature $X_j = T_j(x)$, this is a (huge, regularized) linear regression in the tree weights. The parameter space is astronomically large ⟹ regularize, and do it by a path, not a full solve.
• The generalized residual (pseudo-response) — the central object. To reduce a general loss $L(y, F)$ by gradient descent in function space, the steepest-descent direction at the current fit $F$ is the negative functional gradient $\ell_i = -\frac{\partial L(y_i, F_i)}{\partial F_i}.$ Squared-error loss ⟹ $\ell_i = y_i - F_i$ (the ordinary residual). Absolute loss ⟹ $\ell_i = \mathrm{sign}(y_i - F_i)$. So “fit the residual” generalizes to “fit the negative gradient of whatever loss you chose.”
• Gradient boosting (MART) — the algorithm. Initialize $F \equiv$ const. Repeat:
  1. Compute generalized residuals $\ell_i = -\partial L/\partial F_i$ at the current $F$.
  2. Fit a tree to the $\ell_i$ by least squares — this yields the regions $\{R_m\}$ (we keep the partition, discard its leaf values).
  3. Re-optimize the leaf values for the actual loss. Step 2 fit the tree to the pseudo-residuals by least squares, so its regions track the gradient but its leaf constants are calibrated to that squared-error surrogate, not to $L$ — for any non-squared loss the two disagree. So keep the regions, discard their values, and re-solve each region’s constant against the true loss: $\gamma_m = \arg\min_\gamma \sum_{x_i \in R_m} L(y_i, F_i + \gamma)$ — disjoint regions make this a separate 1-D optimization each (squared loss ⟹ region mean of residuals, recovering plain residual-fitting; absolute loss ⟹ region median).
  4. Update $F \leftarrow F + \nu\,\sum_m \gamma_m \mathbf 1(x \in R_m)$ with a small learning rate $\nu$ (shrinkage). Stop by monitoring held-out error (it does overfit eventually — visible if you watch probabilities, not just misclassification).
• Why small trees. A depth-$d$ tree is a $d$-way interaction (each split multiplies indicators). The functional ANOVA decomposition $F(x) \approx \sum_j f_j(x_j) + \sum_{j,k} f_{jk}(x_j, x_k) + \cdots$ shows most real functions are dominated by low-order interactions. So a stump (depth 1) = additive/main-effects model; depth 2 = pairwise interactions; rarely more. Tree depth directly controls interaction order — another bias–variance knob.
• Shrinkage + many trees. Small $\nu$ (e.g. 0.01) means many similar trees and a smoother fit; $\nu$ trades against $B$. The optimal-leaf step makes the procedure scale-invariant. Picture to hold: each tree is a small chisel-stroke at the part of the signal the current model still gets wrong; with a tiny learning rate, thousands of gentle strokes accrete into a smooth surface — the opposite of one deep tree’s coarse cuts.
• Classification: model $K$ functions $F_k$ with softmax $\hat p_k = e^{F_k}/\sum_\ell e^{F_\ell}$; under the multinomial deviance the generalized residual is the simple residual on the probability scale $\ell_{ik} = d_{ik} - \hat p_k(x_i)$ ($d_{ik}$ the class indicator). Boost $K$ trees per round (K-MART).
• Robust losses: absolute loss (median updates) is fully robust to $y$-outliers; Huber (quadratic near zero, linear in the tails) gets the efficiency of squared loss with the robustness of absolute — the practical default for messy regression.

Interpreting the black box.

• Variable importance: sum the split-improvements attributed to each variable, averaged over all trees — $\hat J_j^2 = \frac1M\sum_m \sum_{\text{splits on }j} \hat I^2$. More stable than a single tree’s.
• Partial dependence: to see how $F$ depends on a subset $x_S$ marginalizing the rest, average over the data: $\bar F_S(x_S) = \frac1N\sum_{i=1}^N F(x_S, x_{iC}),$ then plot. It is the best additive approximation in $x_S$ — not the same as conditioning on $x_S$ (which would confound through correlated variables; the hospital-success-rate paradox).

Implications

• Boosting operates on the output of a weak learner, not its internals — a generic accuracy amplifier (it boosts any base learner, trees just respond especially well).
• The generalized-residual view unifies regression, classification, and robust losses under one algorithm: change $L$, the only thing that changes is the residual you fit.
• Boosting (sequential, bias-reducing) and bagging/RF (parallel, variance-reducing) are complementary — XGBoost adds explicit regularization on top of the boosting path and dominates tabular competitions.

Core competency set

• Derive the generalized residual $\ell_i = -\partial L/\partial F_i$ and give it for squared and absolute loss.
• State the MART loop (residual → tree for regions → re-optimize leaves → shrunken update) and why it re-optimizes leaves.
• Explain tree depth = interaction order via the ANOVA decomposition; define partial dependence and why it ≠ conditioning.

4. Neural networks

• Structure: a linear combination of nonlinear functions of linear combinations — one hidden layer: $F(x) = b_0 + \sum_{m=1}^M b_m\,S\Big(a_{0m} + \sum_j a_{jm}x_j\Big),$ $S$ an activation (sigmoid, tanh, ReLU). For $M$ large enough this is a universal approximator — but so are trees and boosting; the win is when the truth is itself a function of functions (vision, where CNNs wrap local structure into abstractions — the organized-data point: pixel locations carry information a flat model throws away).
• Score + search: squared error (or cross-entropy), minimized by gradient descent. The criterion is convex in the output weights $b$ but not in the hidden weights $a$ ⟹ many local minima, sensitivity to initialization. This non-convexity (vs logistic regression’s single optimum, 06a §5) is the price of the extra flexibility — and what makes NNs unstable (and thus baggable).
• Backpropagation — the gradient by the chain rule. Per-example squared-error cost $q_i = \frac12(y_i - F(x_i))^2$, with $F = b_0 + \sum_m b_m S_m$ and $S_m = S(\eta_m)$, $\eta_m = a_{0m} + \sum_j a_{jm}x_{ij}$. Differentiate layer by layer. Output weight (chain through $F$): $-\frac{\partial q_i}{\partial b_m} = (y_i - F(x_i))\,\frac{\partial F}{\partial b_m} = (y_i - F(x_i))\,S_m \quad(\text{error}\times\text{hidden output}).$ Input weight $a_{jm}$ sits deeper — the dependence runs $q \to F \to S_m \to \eta_m \to a_{jm}$, so the chain rule is a product of four factors: $-\frac{\partial q_i}{\partial a_{jm}} = \Big(-\frac{\partial q_i}{\partial F}\Big)\frac{\partial F}{\partial S_m}\frac{\partial S_m}{\partial \eta_m}\frac{\partial \eta_m}{\partial a_{jm}}.$ Evaluate the four factors one at a time (the third uses the sigmoid identity $S' = S(1-S)$): $-\frac{\partial q_i}{\partial F} = y_i - F(x_i), \quad \frac{\partial F}{\partial S_m} = b_m, \quad \frac{\partial S_m}{\partial \eta_m} = S_m(1 - S_m), \quad \frac{\partial \eta_m}{\partial a_{jm}} = x_{ij}.$ Multiply them back together: $-\frac{\partial q_i}{\partial a_{jm}} = (y_i - F(x_i))\,b_m\,S_m(1 - S_m)\,x_{ij}.$ Read it right to left as the network error, routed to node $m$ by its outgoing weight $b_m$ (node $m$‘s share of the error), bent by the local slope $S'$, and attributed to input $j$ in proportion to $x_{ij}$. Each node needs only its local share ⟹ fully parallelizable. Training = forward pass (propagate signal to output) + backward pass (propagate error-shares to weights).
• Stochastic / online gradient descent with momentum ($g \leftarrow \alpha g_i + (1-\alpha)g$): smooths the noisy per-example gradient (a decaying-average of recent gradients), damping the zig-zag in elongated valleys. Small $\alpha$ early (any step helps far from the optimum), larger later.
• Regularization is essential (NNs overfit by construction). Weight decay = an explicit L2 penalty $\lambda w^Tw$ (ridge on the weights). Early stopping = implicit regularization: monitor validation error and stop when it turns up — equivalent to penalizing the number of steps. Dropout = bagging-by-sampling-units.
• Basis-function reading: $F = b_0 + \sum_m b_m B(x; a_m)$ — NNs are adaptive basis expansions (06a §7), the basis learned rather than fixed. The radial basis function $B(x;a) = \exp(-\frac{1}{2a_0^2}\sum_j(x_j - a_j)^2)$ is the alternative that varies in all directions (concentric bumps) — ideal for isolated peaks where a sigmoid net struggles.

Implications

• The structure/score/search frame makes NNs un-mysterious: a flexible adaptive-basis class, a standard loss, and gradient search — the novelty is depth (functions of functions) and the engineering of the search.
• Non-convexity is the defining tradeoff: NNs trade logistic regression’s guaranteed optimum for representational power, which is why they need the most data, the most regularization, and restarts.
• “Treat organized data as organized” (use pixel locations via convolution) is the conceptual bridge to modern deep learning (track 11).

Core competency set

• Write the one-hidden-layer model and explain universal approximation + the win condition (function-of-functions).
• Derive the backprop gradients and read them as error-shares; explain momentum.
• Contrast weight decay vs early stopping as regularization; place RBF vs sigmoid.

5. Support vector machines and kernels

• Maximal margin classifier: with separable $\pm1$ labels and a separating hyperplane $\beta_0 + \beta^Tx = 0$ ($\|\beta\| = 1$), maximize the margin $M$: $\max_{\beta_0,\beta,M} M \ \text{ s.t. } \ y_i(\beta_0 + \beta^Tx_i) \ge M \ \forall i.$ $y_i(\cdot)$ is the signed distance (positive when correct); the widest “slab” between the classes. Equivalently $\min \|\beta\|$ s.t. $y_i(\beta_0 + \beta^Tx_i) \ge 1$ (set $M = 1/\|\beta\|$). The solution depends only on the points on the margin — the support vectors. Picture to hold: the widest slab you can slide between the two classes; only the points touching its faces hold it in place — slide an interior point around and the boundary doesn’t move.
• Support vector classifier (soft margin): allow violations with slack $\xi_i \ge 0$, budget $\sum\xi_i \le C$: $\max M \ \text{ s.t. } \ y_i(\beta_0 + \beta^Tx_i) \ge M(1 - \xi_i),\ \ \xi_i \ge 0,\ \ \textstyle\sum_i\xi_i \le C.$ $\xi_i > 0$: inside the margin; $\xi_i > 1$: misclassified. Larger budget ⟹ wider margin, more support vectors, more bias / less variance — $C$ (or its dual $\gamma$) is the regularization knob, set by CV.
• Why the solution is sparse in the data — Lagrangian sketch. Attach multipliers $\alpha_i \ge 0$ to the margin constraints $y_i(\beta_0 + \beta^Tx_i) \ge 1$. Stationarity of the Lagrangian in $\beta$ gives $\beta = \sum_i \alpha_i y_i x_i,$ so the normal vector is a linear combination of the training points. The KKT complementary-slackness condition $\alpha_i[\,y_i(\beta_0 + \beta^Tx_i) - 1\,] = 0$ forces $\alpha_i = 0$ for every point strictly outside the margin (its constraint is slack) — so only points on the margin (the support vectors) have $\alpha_i \ne 0$ and enter $\beta$.
• The kernel trick. Substituting $\beta = \sum_i\alpha_i y_i x_i$ back, the classifier depends on the data only through inner products, $f(x) = \beta_0 + \sum_{i} \alpha_i y_i \langle x, x_i\rangle,$ with $\alpha_i \ne 0$ only for support vectors. Replace $\langle x, x_i\rangle$ by a kernel $K(x, x_i)$ — an inner product in some (possibly infinite-dimensional) feature space $\langle \Phi(x), \Phi(x_i)\rangle$ — and you get a nonlinear boundary at linear cost. A linear boundary in the enlarged space is nonlinear in the original. Polynomial $K = (1 + \langle x, x_i\rangle)^d$; radial $K = \exp(-\gamma\|x - x_i\|^2)$ (infinite-dimensional feature map, yet computable). Valid kernels are exactly the positive-semidefinite ones (Gram matrix PSD); sums/products of kernels are kernels.
• SVM as loss + penalty. The SVC is equivalent to $\min_{\beta_0,\beta}\ \sum_i [1 - y_if(x_i)]_+ + \lambda\|\beta\|^2,$ hinge loss + ridge penalty. The hinge $[1 - yf]_+$ is a kinked, convex surrogate for 0–1 loss; logistic’s $\log(1 + e^{-yf})$ is a smooth version of the same shape. So SVM and logistic regression differ mainly in the loss kink — as $\lambda \to 0$ on separable data they give the same boundary.
• When which: SVM behaves better when classes are well-separated and for $p > N$ (data is then separable); logistic is preferred in overlapping regimes, gives probabilities, and extends to multiclass more naturally (SVM multiclass is one-vs-one / one-vs-all hacks).
• The kernel idea generalizes: any method depending only on inner products (PCA → kernel PCA, ridge, etc.) can be kernelized — replace $\langle\cdot,\cdot\rangle$ with $K$.

Implications

• The hinge-loss-+-penalty view places SVM in the same family as ridge/lasso/logistic (06a §3, §5): a convex loss plus a shrinkage penalty, tuned by CV — demystifying the “margin” mystique.
• The kernel trick is the deepest idea here: nonlinearity for free wherever an algorithm touches data only through inner products — and it built a decade of nonparametric methods.
• Support-vector sparsity (only boundary points matter) is the classification echo of the lasso’s “few things matter.”

Core competency set

• Write the hard- and soft-margin programs and the $\min\|\beta\|$ reformulation; define support vectors and the role of $C$.
• State the kernel trick (inner-product dependence → replace with $K$) and the PSD validity condition; give polynomial/radial kernels.
• Write SVM as hinge + ridge and compare hinge vs logistic loss.

6. Unsupervised learning

No labels — find structure: a low-dimensional representation (PCA, manifold methods) or homogeneous groups (clustering).

• PCA — derived. The first principal component is the unit direction $\phi_1$ of maximal projected variance: $\max_{\|\phi\|=1}\ \frac1N\sum_i\Big(\sum_j \phi_j x_{ij}\Big)^2 = \max_{\|\phi\|=1}\ \phi^T\widehat\Sigma\,\phi.$ Enforce the unit-norm constraint $\|\phi\|^2 = \phi^T\phi = 1$ with a multiplier $\theta$:

$\mathcal L = \phi^T\widehat\Sigma\phi - \theta(\phi^T\phi - 1).$

Differentiate, using $\nabla_\phi(\phi^T\widehat\Sigma\phi) = 2\widehat\Sigma\phi$ ($\widehat\Sigma$ symmetric) and $\nabla_\phi(\phi^T\phi) = 2\phi$, and set to zero:

$\nabla_\phi\mathcal L = 2\widehat\Sigma\phi - 2\theta\phi = 0.$

Divide by 2 — that is the eigenvector equation:

$\widehat\Sigma\phi = \theta\phi.$

On an eigenvector the objective reads $\phi^T\widehat\Sigma\phi = \phi^T(\theta\phi) = \theta\|\phi\|^2 = \theta$, so maximizing projected variance means taking the largest eigenvalue — $\phi_1$ is the top eigenvector of $\widehat\Sigma$. Later PCs are the next eigenvectors (add $\phi_2 \perp \phi_1$ to the same Lagrangian). Equivalently the SVD of centered $X$: right singular vectors = loadings, $\sigma^2/N$ = variances; scores $z_{im} = \sum_j \phi_{jm}x_{ij}$ are the data in the new basis.

• Two readings: directions of maximal variance, and the affine subspace closest to the data (the first $M$ PCs give the best rank-$M$ Euclidean approximation). PVE of component $m$ = its eigenvalue / total variance; scree plot to choose $M$. Scale-dependent ⟹ standardize unless units match. Unique up to sign.
• K-means. Minimize within-cluster scatter $\sum_k \frac{1}{|C_k|}\sum_{i,i'\in C_k}\|x_i - x_{i'}\|^2 = 2\sum_k\sum_{i\in C_k}\|x_i - \bar x_k\|^2$ (twice the sum of squared distances to centroids). Lloyd’s algorithm: alternate (a) assign each point to the nearest centroid, (b) recompute centroids. Each step is non-increasing ⟹ converges, but to a local minimum (restart from several seeds). Works best on convex, equal-sized clusters. (It is a degenerate Gaussian-mixture / EM limit — track 7 §7.)
• Hierarchical (agglomerative) clustering: start with $N$ singletons, repeatedly merge the two least-dissimilar clusters; the merge height in the dendrogram is the dissimilarity. Linkages: complete (max pairwise — compact clusters), single (min — chaining), average, centroid (can invert). Read similarity by merge height, not horizontal proximity. Correlation-based distance groups by pattern regardless of magnitude. Best when clusters are genuinely nested.
• Nonlinear dimension reduction (high signal-to-noise manifolds — the “Swiss roll”):
  • Kernel PCA: PCA on $\langle\Phi(x_i),\Phi(x_j)\rangle = K$ — captures nonlinear variation (e.g. concentric circles a linear PCA can’t separate).
  • MDS: find low-D points preserving pairwise distances, $\min\sum_{i,j}(d(i,j) - \|z_i - z_j\|)^2$.
  • Isomap: MDS on geodesic distances (shortest paths in a nearest-neighbor graph) — unrolls the manifold.
  • LLE: reconstruct each point from its neighbors ($x_i \approx \sum_k W_{ik}x_k$), then find low-D $z_i$ preserving the same weights. LLE/Isomap reduce to kernel PCA with particular kernels.

Implications

• PCA, kernel PCA, and the SVD-shrinkage methods of 06a §3 are one linear-algebra family — eigen/SVD structure of a covariance or kernel matrix, used to compress, denoise, or regularize.
• Clustering decisions (distance, $K$, scaling, linkage) are modeling choices with no labels to check against — results are exploratory, not validated; this is the defining caution of unsupervised work.
• Manifold methods all assume the data lives near a low-dimensional surface with high signal-to-noise; raise the noise and the structure dissolves.

Core competency set

• Derive PC1 as the top eigenvector of the covariance; give both readings and PVE.
• State the K-means objective and Lloyd’s algorithm; explain the local-minimum issue.
• List the linkages and how to read a dendrogram; sketch what Isomap/LLE/kernel-PCA each do.

7. Missing data and the meta-frame

• Missingness mechanisms (the distinction that dictates what’s valid):
  • MCAR (completely at random): missingness ⊥ everything — dropping rows is unbiased, just wasteful.
  • MAR (at random): missingness depends only on observed variables — recoverable by conditioning/imputation.
  • MNAR (not at random): missingness depends on the missing value itself (high earners hide income; censoring) — not fixable without a model of the mechanism.
• Adjustments: treat “missing” as a category; CART surrogate splits (§1); single imputation (mean/median/regression-on-other-predictors — biases variances down, understates uncertainty); multiple imputation (impute many times from a model, pool — propagates uncertainty); iterative imputation (cycle, imputing each variable from the rest — backfitting again). Bootstrap the whole imputation pipeline to get honest SEs.
• Low-rank matrix completion (Netflix). $\hat y$ is a projection onto $C(X)$, so the column space is what matters; if the data matrix is approximately low rank, fill missing entries from a rank-$k$ approximation: $\min_{\mathrm{rank}(X') = k}\|X' - X\|_\Omega$ over observed entries $\Omega$. Solve by hard-impute (fill, SVD-truncate, refill, repeat) or the convex nuclear-norm relaxation $\min \|X' - X\|_\Omega + \lambda\sum_p \sigma_p(X')$ — the SVD analogue of the lasso (penalize singular values ⟹ low rank), $\lambda$ inversely controlling rank.
• The meta-frame — choosing a method at all.
  • No free lunch: averaged over all possible target functions, no method beats any other. Performance is about situations — the (unknown) target, the sample size, and the signal-to-noise ratio. Large noise ⟹ restricted methods (more bias, less variance); high signal + large $N$ ⟹ flexible methods (KNN, NNs) shine.
  • Bet on sparsity: “use a procedure that does well in sparse problems, because no procedure does well in dense problems.” With many predictors, assume few matter — it’s the only regime where you can win, so design for it (lasso, boosting, trees).
  • Comparison caution: published method comparisons are biased — selection effects (papers appear when the new method wins), expert bias (the author tunes their own method best). Trust CV on your data over leaderboards.

Implications

• The MCAR/MAR/MNAR ladder tells you whether a fix exists before you reach for one — MNAR needs a mechanism model no imputation can supply.
• Matrix completion ties the whole course together: projection (06a §3), low-rank/SVD (track 2), and the lasso’s convex-relaxation trick (nuclear norm) in one method.
• “No free lunch + bet on sparsity” is the honest summary of the entire two-part guide: there is no best method, only a best match to the situation, and the situations worth betting on are sparse.

Core competency set

• Define MCAR/MAR/MNAR and which admit a fix; contrast single vs multiple imputation.
• State low-rank completion and the nuclear-norm relaxation as the SVD-lasso.
• State no-free-lunch and bet-on-sparsity and what they imply for method choice.

8. Memorize cold

• Tree: $\hat f = \sum_m \bar y_m \mathbf 1(x\in R_m)$; greedy split minimizes child RSS; Gini $\sum_k \hat p_{mk}(1-\hat p_{mk})$ = squared-error-on-probabilities (misclassification not smooth enough to split on); cost-complexity $\mathrm{RSS} + \alpha|T|$, prune + CV.
• Bagging: average $B$ deep unpruned trees, $\mathrm{Var}(\bar X)=\sigma^2/B$; OOB = free test error. RF: split on random $m\approx\sqrt p$ predictors to decorrelate; $m=p$ ⟹ bagging.
• Boosting: generalized residual $\ell_i = -\partial L/\partial F_i$ (= residual for L2, sign for L1); MART = fit tree to $\ell$ for regions, re-optimize each leaf $\arg\min_\gamma\sum L(y_i, F_i+\gamma)$, update $F \mathrel{+}= \nu\sum\gamma_m\mathbf 1(R_m)$; tree depth = interaction order (stump = additive); partial dependence = average over other vars.
• NN: $F = b_0 + \sum_m b_m S(a_{0m} + \sum_j a_{jm}x_j)$; backprop $-\partial q/\partial a_{jm} = (y-F)b_m S_m(1-S_m)x_j$; non-convex in $a$; regularize by weight decay (L2) or early stopping.
• SVM: $\max M$ s.t. $y_i(\beta_0+\beta^Tx_i)\ge M(1-\xi_i)$, $\sum\xi_i\le C$; $= \min\|\beta\|$ s.t. margin $\ge1$; depends on $\langle x,x_i\rangle$ ⟹ kernel trick (PSD $K$); $=$ hinge $[1-yf]_+$ + ridge.
• PCA: PC1 = top eigenvector of covariance = $\max_{\|\phi\|=1}\phi^T\widehat\Sigma\phi$; = SVD of centered $X$; PVE = eigenvalue share.
• K-means: minimize within-cluster SS, Lloyd alternation, local min (restart). Hierarchical linkages: complete/single/average/centroid; read merge height.
• Missing: MCAR (drop ok) / MAR (impute) / MNAR (need mechanism); multiple imputation propagates uncertainty; low-rank completion + nuclear-norm = SVD-lasso.
• No free lunch (performance is situational); bet on sparsity.

Named moves (cross-track glossary): greedy-recursive-partition (CART); differentiable-surrogate-for-a-nonsmooth-loss (Gini for misclassification, hinge for 0–1); average-to-kill-variance (bagging/forests/dropout); decorrelate-then-average (random forests); fit-the-(generalized)-residual (boosting); function-space-gradient-descent (MART); back-propagate-the-error-share (NN backprop); kernel-trick = replace-inner-products (SVM, kernel PCA — track 2); convex-relaxation (L0→L1 lasso, rank→nuclear-norm); bet-on-sparsity (whole course).