« Phase 32 README · Warmup · Hitchhiker's · Principal Deep Dive · Core Contributor · Staff Notes

Phase 32 — Deep Dive: ML/DL Foundations

The load-bearing idea of this entire phase is a fixed-point iteration: repeatedly nudge a parameter vector down the gradient of a scalar loss until it stops moving. Everything else — logistic regression, k-means, PCA, Q-learning — is that same shape wearing different clothes. This doc traces the mechanism at the level where the arithmetic is exposed, using the actual routines Lab 01–03 implement in pure Python. If you can trace one training step by hand, you can debug any loop that stalls.

The forward pass is a compute graph, not a formula

In Lab 01 the "model" is LogisticRegression, and one prediction is a three-node graph: z = dot(w, x) + b, then p = sigmoid(z), then the per-example loss L = -(y·log p + (1-y)·log(1-p)). Read that as a directed graph: x, w, b → z → p → L. The forward pass evaluates it left to right, caching every intermediate (z, p) because the backward pass will need them. sigmoid is implemented branch-stable — 1/(1+exp(-z)) for z >= 0 and exp(z)/(1+exp(z)) for z < 0 — so that exp never overflows on a large-magnitude score. bce_loss clamps p into [eps, 1-eps] before taking the log, because log(0) is the single most common way a real training run produces NaN. These are not decorations; they are the invariants that keep the graph evaluable at the extremes the optimizer will drive it toward.

Backprop is reverse-mode autodiff, and the residual is not a coincidence

The backward pass walks the same graph right to left, multiplying local derivatives — the chain rule, organized so that every parameter's gradient falls out of one sweep costing about what the forward pass cost. For the logistic node the chain is ∂L/∂w = (∂L/∂p)·(∂p/∂z)·(∂z/∂w). Term by term: ∂L/∂p = (p-y)/(p(1-p)), ∂p/∂z = p(1-p), and ∂z/∂w = x. The middle factor p(1-p) is exactly the denominator of the first, so it cancels, and the whole messy product collapses to the residual:

∂L/∂z = p - y          # prediction error IS the gradient signal
∂L/∂w_j = (p - y)·x_j
∂L/∂b   = (p - y)

This is precisely what compute_gradients computes: err = probability(w, b, x) - y, then accumulate err·x_j across the batch, divide by n, and add the L2 term l2·w_j (the derivative of (l2/2)·Σw²; the bias is left unregularized on purpose). The cancellation is why logistic regression pairs sigmoid with cross-entropy and not squared error: under MSE the surviving σ'(z) = p(1-p) factor drives the gradient toward zero exactly when the model is confidently wrong (p saturated near 0 or 1), so a badly-wrong model learns slowest when it should learn fastest. The mechanism, not a style preference, forces the loss choice.

One training step, traced end to end

Take w = [0, 0], b = 0, learning rate η = 0.1, one example x = [2, -1], y = 1.

1. Forward. z = 0·2 + 0·(-1) + 0 = 0. p = sigmoid(0) = 0.5. L = -log(0.5) ≈ 0.693.
2. Backward. err = p - y = 0.5 - 1 = -0.5. ∂L/∂w = [-0.5·2, -0.5·(-1)] = [-1.0, 0.5]; ∂L/∂b = -0.5.
3. Step (SGD). w ← w - η·∂L/∂w = [0,0] - 0.1·[-1.0, 0.5] = [0.1, -0.05]; b ← 0 - 0.1·(-0.5) = 0.05.

Re-run the forward pass: z = 0.1·2 + (-0.05)·(-1) + 0.05 = 0.30, p ≈ 0.574, L ≈ 0.555. The loss dropped because we moved against the gradient. LogisticRegression.fit does exactly this per mini-batch, with a seeded shuffle each epoch (a fixed order correlates consecutive gradients and biases the trajectory), records train/val loss into TrainHistory, and early-stops with best-weight restore. Adam changes only step 3: it keeps per-parameter EMAs of the gradient (m) and its square (v), bias-corrects them, and steps by η·m̂/(√v̂+ε) — large-gradient parameters get damped, rarely-updated ones amplified — but the gradient it consumes is the identical p-y quantity.

Why the naive gradient fails as a training mechanism

You could skip the chain rule and estimate every gradient numerically: perturb w_j by ±ε, difference the two losses, (L(w+ε) - L(w-ε))/2ε. It works — Lab 01's test suite uses exactly this finite-difference check as the ground truth that the analytic compute_gradients is correct (torch.autograd.gradcheck is the same idea industrialized). But as a training method it is fatal: each gradient component needs two full forward passes, so a d-parameter model costs 2d forward passes per step. Reverse-mode autodiff gets all d components in one backward sweep. That single asymptotic fact — O(1) backward passes versus O(d) forward passes — is why neural networks are trainable at all and why the finite-difference method survives only as a unit test.

Lloyd's algorithm: coordinate descent with a monotonicity guarantee

k-means (Lab 02) minimizes inertia Σ_i ‖x_i - μ_{c(i)}‖². Lloyd's algorithm is block coordinate descent on that objective, alternating two steps that provably never increase it: assign_clusters fixes the centroids and sends each point to its nearest one (optimal assignment given centroids); update_centroids fixes the assignment and moves each centroid to its cluster mean — and the mean is exactly the point minimizing summed squared distance, so this step is optimal too. Two monotone-decreasing steps on a nonnegative bounded-below objective over finitely many partitions ⇒ convergence in finite steps. But only to a local minimum: the assignment is discrete, so the algorithm can settle into a partition no single reassignment improves yet is far from optimal. Hence kmeans_pp_init seeds with the D²-weighted draw (first centroid uniform, each subsequent one chosen with probability proportional to squared distance from the nearest chosen centroid) to spread seeds, and update_centroids carries empty-cluster repair — a centroid that wins zero points is relocated to the farthest point, because the mean of an empty set is undefined and the naive implementation silently divides by zero. The invariant to assert in tests: inertia is non-increasing across iterations, monotonically.

PCA: variance maximization solved by power iteration

PCA (Lab 02) seeks the orthonormal directions of maximum variance. Center the data (center_data — uncentered "PCA" finds the mean, not the variance), form the covariance C = (1/(n-1))·Xcᵀ·Xc (covariance_matrix), and the top eigenvector of C is the first principal axis, its eigenvalue the variance explained. Lab 02 does not call an eigensolver; it runs power_iteration: start from a random unit vector v, repeatedly set v ← normalize(C·v). Write v in the eigenbasis; each multiply by C scales each component by its eigenvalue, so the dominant component grows fastest relative to the rest and v converges to the top eigenvector. The convergence rate is governed by the ratio λ₂/λ₁ — close eigenvalues converge slowly. To get the next component, deflate subtracts the found direction's contribution: C' = C - λ₁·v₁·v₁ᵀ, which zeroes that eigenvalue and leaves the rest, then power-iterate again. reconstruction_error (project down via project, map back via reconstruct, take the MSE) equals the sum of discarded eigenvalues — the same quantity, viewed as lost variance, and it doubles as an anomaly score.

The Bellman update: bootstrapped regression on your own estimates

Q-learning (Lab 03) has no labels, so it manufactures a target from the Bellman optimality equation. On each experienced transition (s, a, r, s'), QLearningAgent.update computes target = r if terminal else r + γ·max_a' Q(s',a'), the TD error δ = target - Q(s,a), and nudges Q(s,a) ← Q(s,a) + α·δ. It is regression where the label is bootstrapped from the agent's own improving Q. The load-bearing symbol is the max: the target uses the best next action, not the exploratory action the policy will actually take — which is what makes Q-learning off-policy. Lab 03 proves this the sharp way: train with ε = 1 (fully random behavior) and greedy_path still extracts the optimal route, bellman_residual ≈ 0. That property is the reason DQN's replay buffer — training on transitions from stale policies — is legal at all.

Complexity and invariants at a glance

The through-line: every one of these is an iterative descent (or ascent) with a checkable monotonicity or fixed-point invariant. When a real loop misbehaves — NaN, flat loss, rising inertia, a residual that won't shrink — you debug it by asking which invariant broke, and the answer is always one of the four moves: forward, loss, backward, step.