Intuition

The three ingredients are easiest to see side by side with a hand-written rule. Suppose an estate agent says "a house is worth $250 per square foot". That is a model with one parameter that a person chose. A learned model has the same form, but the computer chooses the parameters by making a cost small on examples.

Worked example by hand

Use the five houses from Lecture 1.3 (size in 1000 sq ft, price in $1000) and the cost J from Lecture 1.4.

• Hand-written rule, ŷ = 250·x: predictions 250, 375, 500, 625, 750. Residuals −50, −45, 0, −5, 50. Squares 2500, 2025, 0, 25, 2500 sum to 7050, so J = 7050 / 10 = 705.
• Learned line, ŷ = 202·x + 106: residuals 8, −11, 10, −19, 12. Squares 64, 121, 100, 361, 144 sum to 790, so J = 79.

The learned line is nine times better on these houses because it was chosen to be. That alone proves nothing about new houses. To test the promise of learning, hide one house, learn from the other four, and predict the hidden one.

Compare a "memorizer" that answers with the price of the nearest training house. Its training error is exactly zero. For the hidden 2.0 house the nearest training houses are 1.5 and 2.5, at equal distance, so it answers 420 or 630 and misses by 80 or 130. Zero training error, ten times worse on the house that matters.

Why generalization is possible at all

The line has two parameters and is fit to many more points than that, so it cannot bend to follow each one. Whatever it captures has to be shared by most houses, and shared structure is what carries over to a new house. The memorizer has as many "parameters" as houses, so nothing forces it to find shared structure. Course 2 makes this trade precise as bias and variance.

Common mistakes

• Judging a model by its training cost. Symptom: a model that looks perfect in development fails on real data. Fix: always keep examples the model never saw and report error on them.
• Thinking learning removes human choices. The person still picks the model family, the cost and the features. Symptom: blaming "the algorithm" for a bad feature choice. Fix: treat those three choices as part of the design you are responsible for.
• Expecting skill beyond the data. Samuel's program improved because self-play produced endless new games. Symptom: a model trained on houses from 800 to 3,000 sq ft confidently prices a 10,000 sq ft mansion. Fix: know the range your examples cover.

Check yourself

If the memorizer instead averages the prices of the two nearest training houses, what does it predict for the hidden 2.0 house, and what is its error?

Intuition

The type of y fixes two things before you write any code: the last step of the model and the cost. A regression model ends in an unbounded number and is scored with squared error. A classification model ends in a probability for each class and is scored with log loss (Lecture 3.4).

Derivation: why category codes break regression

Suppose you code ticket topics as numbers, billing = 0, bug = 1, feature request = 2, and fit a regression. Consider several tickets with identical features x. The model must give them one prediction c. Squared error picks the c that minimizes Σ(c − yᵢ)². Differentiate with respect to c and set to zero:

Now take four such tickets: two billing (0) and two feature requests (2). The mean is 1, so the model predicts "bug", a topic none of the four tickets had. The codes 0, 1, 2 impose an order and a distance that the categories do not have. A classifier instead reports P(billing) = 0.5, P(bug) = 0, P(feature) = 0.5, which is exactly what the data says.

Edge cases

• Ordered categories such as star ratings 1 to 5 sit in between. Regression respects the order and is often fine; classification ignores the order but cannot predict 3.7.
• The same data, two problems. "Days until a customer cancels" is regression. "Will the customer cancel within 30 days" is classification. The label you define picks the problem.
• Labels you do not have. Anomaly detection is unsupervised when nobody has marked anomalies. Once you have a few thousand labeled frauds it becomes a (very imbalanced) classification problem.

Common mistakes

• Feeding category codes or IDs as numbers. Symptom: a weight on "zip code" or "store id" that means nothing. Fix: one-hot encode, one 0/1 column per category.
• Binning a numeric target to make it a classification. Symptom: predicting "price band 3" loses the information that band 3 is next to band 4. Fix: keep regression unless the decision itself is categorical.
• Reporting accuracy on a regression. Symptom: "92% of predictions within $10k" with no notion of how wrong the rest are. Fix: report RMSE or mean absolute error.

Check yourself

A model predicts tomorrow's electricity demand. Your manager only needs to know whether it will exceed the grid's capacity. Which problem should you train?

Derivation

For one feature the best (w, b) can be found by hand. Set both partial derivatives of J to zero (they are derived in Lecture 1.5). Write x̄ and ȳ for the means of x and y.

1. ∂J/∂b = (1/m)·Σ(w·xᵢ + b − yᵢ) = 0 gives w·x̄ + b − ȳ = 0, so b = ȳ − w·x̄. The best line always passes through the point (x̄, ȳ).
2. ∂J/∂w = (1/m)·Σ(w·xᵢ + b − yᵢ)·xᵢ = 0. Substitute b: Σ(w·(xᵢ − x̄) − (yᵢ − ȳ))·xᵢ = 0.
3. Because Σ(xᵢ − x̄) = 0, you may replace the trailing xᵢ by (xᵢ − x̄) without changing the sum. Solve for w.

Worked example by hand

x̄ = 2.0 and ȳ = 510.

w = 505 / 2.5 = 202 and b = 510 − 202·2 = 106, the numbers the slider demo reports. The residuals are 8, −11, 10, −19, 12. They sum to zero, which is step 1 restated: with an intercept, least-squares residuals always average to zero.

Reading the parameters

w = 202 is in $1000 per 1000 sq ft, which is $202 per square foot. If you had used raw square feet, the same line would have w = 0.202 and the same b = 106. Changing the units of x rescales w and leaves predictions unchanged. b = 106 is the line's value at x = 0, which is far outside the data (the smallest house is 1.0); it is a parameter, not the price of an empty lot.

Common mistakes

• Reading x⁽²⁾ as x squared. Symptom: code like x**2 where x[1] was meant. Fix: superscripts in parentheses are example indices, and Python counts from 0, so x⁽²⁾ is x[1].
• Swapping x and y. Regressing size on price gives slope 505 / 102800 = 0.004912; inverting it gives 203.56, not 202. Symptom: two "best lines" that disagree. Fix: the variable you want to predict goes on the y side; least squares only minimizes vertical misses.
• Interpreting b by extrapolation. Symptom: "a zero-size house costs $106k". Fix: interpret parameters only inside the range of the data.
• Mixing units between training and use. Symptom: pricing a 1,200 sq ft house at 202·1200 + 106 = $242,506k. Fix: feed x in the same units it was trained in (1.2, giving $348.4k).

Derivation: J is a quadratic in (w, b)

Expand the square in J = (1/2m)·Σ(w·xᵢ + b − yᵢ)² and write avg(·) for an average over the m examples:

For the five houses avg(x²) = 4.5, avg(x) = 2, avg(xy) = 1121, avg(y) = 510, avg(y²) = 280660, so

Check at (200, 100): 180000 + 80000 + 10000 − 448400 − 102000 + 280660 = 260, and half of that is 130, matching the hand calculation in the lecture.

Derivation: the bowl has one bottom

The curvature of J is its matrix of second derivatives, the Hessian. From the expanded form, ∂²J/∂w² = avg(x²) = 4.5, ∂²J/∂b² = 1 and ∂²J/∂w∂b = avg(x) = 2. In general, with a column of ones appended to X to carry b, the Hessian is H = XᵀX/m. For any direction v,

Here det H = 4.5·1 − 2·2 = 0.5 > 0, so H is positive definite and the minimum is unique. Its eigenvalues are 0.0925 and 5.4075. Their ratio is 58.5, so the elliptical contours of J are √58.5 ≈ 7.6 times longer in one direction than the other. The bowl is a stretched valley, a fact Lecture 1.6 uses to explain the learning-rate limit.

Why squares and not something else

If each price is the line plus Gaussian noise with spread σ, the probability density of seeing yᵢ is proportional to exp(−(yᵢ − ŷᵢ)² / 2σ²). Taking −log and summing over houses gives Σ(yᵢ − ŷᵢ)² / 2σ² plus a constant. Maximizing the likelihood of the data is exactly minimizing squared error. Lecture 3.4 repeats this argument with a coin instead of a bell curve and gets log loss.

Common mistakes

• Reading J as an error in dollars. J = 79 is half a mean of squared thousands of dollars. Fix: report RMSE = √(2J) = √158 ≈ 12.6, which is in $1000.
• Dropping the 1/m. Symptom: the cost doubles when the dataset doubles and the learning rate that worked yesterday diverges today. Fix: always average.
• Ignoring outliers. One house mispriced by 200 adds 200² / 10 = 4000 to J, fifty times the whole cost of the good fit. Fix: inspect the largest residuals before trusting the fit.
• Thinking the ½ changes the answer. Multiplying a function by a positive constant moves no minimum. It only rescales the gradient, and so the effective learning rate.

Derivation

Name the residual of example i: eᵢ = w·xᵢ + b − yᵢ. Then J = (1/2m)·Σ eᵢ². Differentiate one step at a time.

1. The derivative of a sum is the sum of derivatives, and 1/2m is a constant: ∂J/∂w = (1/2m)·Σ ∂(eᵢ²)/∂w.
2. Chain rule on the square: ∂(eᵢ²)/∂w = 2eᵢ·∂eᵢ/∂w.
3. eᵢ is linear in w with coefficient xᵢ, so ∂eᵢ/∂w = xᵢ. It is linear in b with coefficient 1, so ∂eᵢ/∂b = 1.
4. Combine: ∂J/∂w = (1/2m)·Σ 2eᵢxᵢ = (1/m)·Σ eᵢxᵢ, and ∂J/∂b = (1/m)·Σ eᵢ. The 2 from the square cancels the ½.

Worked example by hand

Start at w = b = 0, α = 0.01. Every prediction is 0, so eᵢ = −yᵢ.

• ∂J/∂b = −avg(y) = −510.
• ∂J/∂w = −avg(x·y) = −(300 + 630 + 1000 + 1575 + 2100)/5 = −5605/5 = −1121.
• Update: w = 0 − 0.01·(−1121) = 11.21 and b = 0 − 0.01·(−510) = 5.10.
• J falls from 140330 to 125572.7. The next step gives (21.81, 9.92) and J = 112368.2.

At the minimum both derivatives must be zero. With w = 202, b = 106 the residuals are 8, −11, 10, −19, 12. Σeᵢ = 0, and Σeᵢxᵢ = 8 − 16.5 + 20 − 47.5 + 36 = 0. Gradient descent stops moving there because there is nothing left to push it.

Code walkthrough: the finite-difference check

eps = 1e-6
num_dw = (cost(w + eps, b) - cost(w - eps, b)) / (2 * eps)   # slope of J along w
num_db = (cost(w, b + eps) - cost(w, b - eps)) / (2 * eps)
# at (0, 0) both agree with the formulas: -1121.0 and -510.0

The centred difference has error proportional to eps², so it matches an exact derivative to about 10 digits on a quadratic. Use it every time you write a gradient by hand.

Common mistakes

• Sequential update. Updating w first and computing ∂J/∂b with the new w gives b = 4.876 instead of 5.10 on the first step above. Symptom: results that differ slightly from everyone else's. Fix: compute both gradients, then assign both, as in w, b = w - a*dw, b - a*db.
• Sign error. Writing eᵢ = yᵢ − ŷᵢ and keeping the minus in the update moves uphill. Symptom: J grows from the first step for every α. Fix: residual is prediction minus target, update subtracts.
• Sum instead of mean. Symptom: a gradient m times larger, so α = 0.1 behaves like α = 0.5 on five houses and diverges. Fix: divide by m, or knowingly scale α down.
• Forgetting the xᵢ in ∂J/∂w. Symptom: w and b receive the same update and the gradient check fails on w only. Fix: run the check.

Derivation in one dimension

For the demo's bowl J(w) = (w − 3)² + 1, dJ/dw = 2(w − 3). One step gives w − 3 ← (w − 3) − α·2(w − 3) = (1 − 2α)(w − 3). The distance to the minimum is multiplied by the same factor (1 − 2α) every step, so it shrinks only if |1 − 2α| < 1, that is 0 < α < 1. The number 2 is the curvature d²J/dw².

A negative factor means the iterate jumps to the other side of the minimum each step. At −0.8 the jumps shrink; at −1.1 they grow.

Derivation for linear regression

Any quadratic cost with Hessian H and minimum θ* has gradient H(θ − θ*). One step gives θ − θ* ← (I − αH)(θ − θ*). Write θ − θ* in the eigenvectors of H. Each component is multiplied by its own factor (1 − αλₖ), where λₖ is the matching eigenvalue. Every component shrinks only if |1 − αλₖ| < 1 for all k:

Worked example: the five houses

H = [[4.5, 2], [2, 1]] has eigenvalues 0.0925 and 5.4075 (Lecture 1.4 deep dive), so α must be below 2 / 5.4075 = 0.3699. Run 200 iterations from (0, 0):

• α = 0.36: factor in the steep direction 1 − 0.36·5.4075 = −0.947. J = 79.00005, essentially converged.
• α = 0.369: factor −0.9954. Still stable, but J = 22089 after 200 steps because the oscillation barely decays.
• α = 0.37: factor −1.0008. J = 192300 and climbing.

The flat direction sets the speed. At α = 0.01 its factor is 1 − 0.01·0.0925 = 0.99908, so shrinking that component by a factor of 10⁶ takes ln(10⁻⁶)/ln(0.99908) ≈ 14,900 steps, while the steep component (factor 0.946) is gone in a few hundred. The best fixed step, 2/(λ_min + λ_max) = 0.364, still leaves a factor of 0.966 per step, set by the ratio λ_max/λ_min = 58.5. Lecture 2.3 shows how scaling shrinks that ratio.

Common mistakes

• Lowering α when the cost falls too slowly. Symptom: training gets even slower. Fix: if the curve decreases smoothly, try a larger α; lower it only when the cost rises or oscillates.
• Using an absolute tolerance across problems. ε = 0.001 means something different when J is 79 and when J is 10⁸. Fix: test the relative change |ΔJ|/J, or the gradient norm.
• Reusing α across datasets. λ_max depends on the scale of the features. Symptom: a learning rate that worked on x in thousands of sq ft diverges on raw sq ft. Fix: rescale features or search α again.
• Calling a near-limit run converged. At α = 0.369 the cost decreases every step yet is still 280 times the minimum after 200 steps. Fix: look at the value, not only the direction, of the curve.

Derivation

With n features, eᵢ = w₁xᵢ₁ + … + wₙxᵢₙ + b − yᵢ. The residual is linear in each weight, and the coefficient of wⱼ is xᵢⱼ, so ∂eᵢ/∂wⱼ = xᵢⱼ. Every other step is the one-feature derivation from Lecture 1.5:

Worked example: the gradient at zero

For the five houses with sqft, bedrooms, floors and age, start at w = 0, b = 0. Then eᵢ = −yᵢ, and ∂J/∂wⱼ = −avg(xⱼ·y). For sqft that is −(2104·460 + 1416·232 + 1534·315 + 852·178 + 1200·250)/5 = −2231218/5 = −446243.6. The four weight derivatives are −446243.6, −1009.4, −396.4 and −10167.6, and ∂J/∂b = −287. The sqft component is 442 times the bedrooms component only because square feet are big numbers. Lecture 2.3 is about that imbalance.

What "holding the others fixed" really means

A weight is the change in prediction when its feature rises by one unit and every other feature stays the same. When features move together, that is a situation the data rarely shows, and the weight can look absurd. The exact least-squares fit on these five houses is

An extra bedroom "costs" $158k. The reason: sqft and bedrooms have correlation 0.957 here, so the data cannot tell their effects apart, and the fit trades one against the other. There is a second problem. Five houses and five parameters (four weights plus b) means five equations in five unknowns, so the plane passes exactly through every house and J = 0. A perfect fit with nonsense weights is the signature of too many parameters for the data. The same model prices a 1,650 sq ft, 3-bedroom, 1-floor, 40-year-old house at $504k, more than the 2,104 sq ft house that sold for $460k.

Common mistakes

• Interpreting weights of correlated features one by one. Symptom: signs that contradict common sense. Fix: interpret groups of correlated features together, or drop one of them.
• Fitting n + 1 ≥ m parameters. Symptom: training cost exactly 0. Fix: get more examples or use fewer features or regularization (Lecture 3.6).
• Mixing up i and j. Symptom: summing over features instead of examples, giving a gradient of the wrong length. Fix: i runs over the m rows, j over the n columns; the derivative for wⱼ sums over i.
• Updating inside the feature loop. Symptom: later weights see already-updated earlier weights. Fix: compute all n + 1 derivatives first, then update.

Derivation

Collect the residuals in a vector e = Xw + b·1 − y of shape (m,), where 1 is a vector of m ones. The cost is J = (1/2m)·eᵀe. Component j of Xᵀe is Σᵢ xᵢⱼeᵢ, which is m times ∂J/∂wⱼ from Lecture 2.1. So all n derivatives at once are

Bias column trick. Prepend a column of ones to X to get X̃ of shape (m, n + 1), and put b first in θ = (b, w₁, …, wₙ). Then ŷ = X̃θ, and the whole gradient is X̃ᵀe/m. The ones column turns b into an ordinary weight whose feature is always 1, which is why the b formula is the w formula with xᵢⱼ = 1.

Shapes table

Worked example

On the five-house, four-feature data at w = 0, b = 0, e = −y, so Xᵀe/m = −Xᵀy/5. The first entry is the dot product of the sqft column with the prices, −2231218/5 = −446243.6, the same number you get from the per-feature sum in Lecture 2.1. One matrix product does the four sums.

Code walkthrough: the broadcasting trap

y_col = y.reshape(-1, 1)          # shape (5, 1), as pandas .values[:, [k]] produces
err = X @ w + b - y_col           # (5,) - (5, 1) broadcasts to (5, 5)
print(err.shape)                  # (5, 5): 25 "residuals", every prediction minus every target
cost = (err ** 2).sum() / (2 * 5) # runs without error and returns the wrong number

Nothing crashes. The cost is simply wrong, and so is every gradient. Add assert err.shape == y.shape or flatten targets with y.ravel().

Common mistakes

• (m, 1) targets against (m,) predictions. Symptom: cost far too large, gradients of shape (n, m). Fix: keep y one-dimensional.
• X @ err instead of X.T @ err. Symptom: a shape error when m ≠ n, and a silent wrong answer when m = n, as with five houses and five columns in X̃. Fix: say the shapes out loud.
• In-place updates on a shared array. w -= alpha * dw inside a function modifies the caller's array too. Symptom: a second training run starts from the first run's result. Fix: write w = w - alpha * dw or pass w.copy().
• * where @ was meant. X * w broadcasts to an (m, n) array of products. Symptom: predictions of shape (m, n). Fix: @ for matrix products, * for elementwise.

Intuition

From Lecture 1.6, gradient descent needs α < 2/λ_max to be stable, and its slowest component shrinks by (1 − αλ_min) per step. The ratio κ = λ_max/λ_min of the Hessian H = X̃ᵀX̃/m, the condition number, therefore decides how many steps you need: roughly κ steps for each factor of e. Scaling is a way of making κ small.

Worked example: the five houses, four features

The diagonal of H holds avg(xⱼ²). For sqft that is 2,190,186; for floors (1, 2, 2, 1, 1) it is 2.2. That spread alone guarantees a huge κ.

With raw features at the largest safe α, the slowest component moves by a factor of 1 − 9 × 10⁻⁷ · 0.006 ≈ 1 − 5.4 × 10⁻⁹ per step, so one factor of e takes about 185 million steps. That is why the lab's raw run at α = 10⁻⁷ barely moves. After z-scoring, α = 0.1 gives a slow factor of 1 − 0.1·0.00557, one factor of e per 1,794 steps, and the lab's 20,000 steps shrink the slowest component by e^−11.1 ≈ 1.4 × 10⁻⁵.

Derivation: why scaling helps and where it stops

• Centering decouples b. The off-diagonal entry of H between b and wⱼ is avg(xⱼ). After subtracting μⱼ it is 0, so b has its own eigenvalue of exactly 1 and its own update. That is why b converges to avg(y) = 287 in the lab.
• Dividing by σⱼ equalizes the diagonal. After scaling, every avg(xⱼ²) = 1, and the off-diagonal entries become the correlations between features.
• What is left is correlation. For two scaled features with correlation r, their 2×2 block of H has eigenvalues 1 + r and 1 − r. sqft and bedrooms have r = 0.957, which alone gives a ratio of 1.957/0.043 ≈ 45. With only five houses for four features the smallest eigenvalue is smaller still, 0.00557. Scaling cannot remove that; more data, fewer features, or regularization can.

Undoing the scaling

Since wⱼ·(xⱼ − μⱼ)/σⱼ = (wⱼ/σⱼ)·xⱼ − wⱼμⱼ/σⱼ, the raw-unit model has w_raw,j = wⱼ/σⱼ and b_raw = b − Σⱼ wⱼμⱼ/σⱼ. For sqft, 252.69 / 412.77 = 0.6122 per square foot, the same as the normal equations give.

Common mistakes

• Mixing ddof conventions. NumPy's std uses ddof = 0 (σ = 412.77 here), pandas' .std() uses ddof = 1 (461.49). The z-score of 2104 sq ft is 1.654 with one and 1.480 with the other. Fix: compute μ and σ once and store them.
• Fitting the scaler on all data. Symptom: test error slightly optimistic, because test statistics leaked into training. Fix: fit on the training split, transform the rest.
• A constant column. σ = 0 produces NaN everywhere. Fix: drop constant features, or divide by max(σ, tiny).
• Scaling the new house with its own statistics. A single row has σ = 0 and μ equal to itself. Fix: always reuse the training μ and σ.

Intuition

Adding x², x³ keeps the model linear in w, so everything from Lectures 2.1 to 2.3 applies. The catch is that powers of a positive variable look alike. Over the range of the data, x, x² and x³ all rise together, so the columns are almost parallel, and Lecture 2.3 showed that correlated columns make κ large even after scaling.

Worked example: 100 houses

In houses_100.csv, sqft runs from 809 to 3,139, so x³ reaches 3.09 × 10¹⁰. The correlations are 0.988 between x and x², 0.992 between x² and x³ and 0.961 between x and x³. After z-scoring, the eigenvalues of XᵀX/m are 0.000153, 0.0392 and 2.961, so κ ≈ 19,400.

The lab trains for 5,000 steps at α = 0.1. The slowest component shrinks by (1 − 0.1·0.000153)⁵⁰⁰⁰ ≈ 0.93, so it is barely touched. The lab's weights come out as (77.0, 62.6, −32.7) with J = 733.2. The exact least-squares weights on the same scaled columns are (−95.7, 434.1, −235.1) with J = 717.2. Reading "the x³ weight is small, so the cubic term is not needed" from an unconverged run would be reading the starting point, not the data.

A cheap fix: center before taking powers. With c = x − x̄, the columns c, c², c³ have correlations −0.175, −0.258 and 0.914, and after z-scoring κ drops to 24.6. The model is the same polynomial; only the basis changed.

Worked example by hand: degree versus fit

On the five houses, training J falls as the degree rises: 79 (line), 61.14 (quadratic), 57.14 (cubic) and 0 (quartic, five coefficients through five points). The quartic is ŷ = −133.3x⁴ + 1053.3x³ − 2986.7x² + 3786.7x − 1420. Its coefficients are thousands, with alternating signs that cancel at the five data points and nowhere else. Huge, cancelling weights are the fingerprint of overfitting that Lecture 3.6 attacks with regularization.

Common mistakes

• Choosing the degree by training cost. Training cost can only fall as you add columns. Fix: compare degrees on held-out data (Lecture 3.5 deep dive does this for the five houses).
• Interpreting weights from an unconverged run. Symptom: weights that change a lot when you double the iterations. Fix: compare against np.linalg.lstsq, or train until the gradient norm is tiny.
• Powering raw large numbers. Symptom: overflow warnings, or float64 losing digits when x³ is 10¹⁰ next to x. Fix: rescale x (to thousands, or centered) before powering, then z-score.
• Extrapolating a polynomial. A cubic goes to ±∞ outside the data. Symptom: absurd prices for a house slightly bigger than any in training. Fix: clip inputs to the training range or prefer low degrees.

Derivation

Use the bias column trick: X̃ is X with a leading column of ones, θ = (b, w). Then J(θ) = (1/2m)·‖X̃θ − y‖². Expand the squared norm:

The gradient of θᵀAθ is 2Aθ for symmetric A, and the gradient of θᵀc is c. So ∇J = (1/m)·(X̃ᵀX̃θ − X̃ᵀy). The cost is convex (Lecture 1.4 deep dive), so the minimum is where the gradient is zero:

The name comes from the geometry: X̃ᵀ(y − X̃θ) = 0 says the residual vector is perpendicular (normal) to every column of X̃.

Worked example by hand

Five houses, one feature. X̃ᵀX̃ = [[5, Σx], [Σx, Σx²]] = [[5, 10], [10, 22.5]] and X̃ᵀy = [Σy, Σxy] = [2550, 5605]. The determinant is 5·22.5 − 10·10 = 12.5. By Cramer's rule:

• b = (22.5·2550 − 10·5605) / 12.5 = (57375 − 56050) / 12.5 = 106
• w = (5·5605 − 10·2550) / 12.5 = (28025 − 25500) / 12.5 = 202

Code walkthrough

Xt = np.c_[np.ones(len(X)), X]                    # (m, n+1): ones column carries b
theta = np.linalg.solve(Xt.T @ Xt, Xt.T @ y)      # solves the system; never form the inverse
theta_ls, *_ = np.linalg.lstsq(Xt, y, rcond=None) # SVD-based: works even when Xt.T @ Xt is singular

Cost. Forming X̃ᵀX̃ takes about m·n² operations and solving takes about n³/3. For n in the hundreds this is instant; for n = 100,000 the n×n matrix alone needs 80 GB.

Accuracy. The condition number of X̃ᵀX̃ is the square of that of X̃. For the raw four-feature houses it is 3.65 × 10⁸, so about 9 of float64's 16 digits are at risk. lstsq (and scikit-learn's LinearRegression, which calls it) works on X̃ directly and avoids the squaring.

Singularity. If m < n + 1, or one column is a combination of others (sqft and sqft in m², say), X̃ᵀX̃ cannot be inverted and there are infinitely many minimizers. solve fails or returns garbage; lstsq returns the one with the smallest ‖θ‖; adding λI (ridge, Lecture 3.6 deep dive) makes it invertible.

Common mistakes

• Forgetting the ones column. Symptom: the fitted line is forced through the origin, with w = 5605/22.5 = 249.1 on the five houses. Fix: add the column, or center x and y first.
• Using np.linalg.inv. Symptom: slower and less accurate, and no warning near singularity. Fix: solve or lstsq.
• Feeding SGDRegressor unscaled features. It is gradient descent, so Lecture 2.3 applies. Symptom: huge or NaN coefficients. Fix: put a StandardScaler in front.
• Forgetting SGDRegressor's default penalty. It adds L2 regularization with alpha = 0.0001 unless you set penalty=None. Symptom: coefficients slightly smaller than LinearRegression's. Fix: expect it, or turn it off.

Worked example by hand

Six tumors of size 1 to 6 with labels 0, 0, 0, 1, 1, 1. Using the closed form from Lecture 1.3: x̄ = 3.5, ȳ = 0.5, Σ(x − x̄)(y − ȳ) = 4.5 and Σ(x − x̄)² = 17.5, so the line is ŷ = 0.2571·x − 0.4. It crosses 0.5 at x = (0.5 + 0.4)/0.2571 = 3.5, exactly between the classes. Every tumor is classified correctly.

Add a seventh tumor of size 20, label 1. Before refitting, the old line predicts 0.2571·20 − 0.4 = 4.743 for it, a residual of −3.743 whose square, 14.0, is larger than all other squared residuals combined. Least squares pays almost any price to shrink it. The refitted line is ŷ = 0.0461·x + 0.3013, and its 0.5 crossing moves to x = (0.5 − 0.3013)/0.0461 = 4.31. The malignant tumor of size 4 now gets 0.486 and is called benign. An obviously malignant example made the classifier wrong on a borderline one.

(The logistic rows use scikit-learn's default regularization, C = 1.) The sigmoid of the size-20 tumor is already about 1, so its residual f − y is nearly 0 and it exerts almost no pull. Lecture 3.4 shows that the logistic gradient is a sum of exactly these residuals.

Derivation: why the line has to tilt

The squared-error gradient for w is (1/m)·Σ eᵢxᵢ. The new point has e = −3.743 and x = 20, contributing −74.9 to the sum, while each of the original six contributes at most a few tenths. Distance from the threshold multiplies the pull, which is the opposite of what a classifier should want: a point far on the correct side is the least informative about where the boundary belongs.

Edge cases

• Outputs outside [0, 1]. Even without the outlier, the line predicts −0.143 at size 1 and 1.143 at size 6. Those cannot be probabilities.
• Balanced, clean data. On symmetric data like the first six tumors the line happens to put the threshold in the right place. That is luck, not a property of the method.

Common mistakes

• Removing "outliers" to rescue a linear classifier. The size-20 tumor is correct data. Fix: change the model, not the data.
• Clipping line outputs to [0, 1] and calling them probabilities. Clipping hides the symptom; the threshold is still in the wrong place.
• Judging on accuracy alone. Accuracy dropped by just one tumor here; the threshold moved by 0.81 size units. Fix: look at the boundary, not only the score.

Derivation: g′ = g(1 − g)

1. Write g(z) = (1 + e^−z)⁻¹.
2. Chain rule: g′(z) = −(1 + e^−z)⁻² · (−e^−z) = e^−z / (1 + e^−z)².
3. Split the fraction: = [1 / (1 + e^−z)] · [e^−z / (1 + e^−z)].
4. The first factor is g. The second is (1 + e^−z − 1)/(1 + e^−z) = 1 − g.

Values: g′(0) = 0.25, g′(±2) = 0.105, g′(5) = 0.00665. Also g(−z) = 1 − g(z): the curve is symmetric about (0, 0.5).

Derivation: the linear part is the log-odds

Let p = g(z). Then 1 − p = e^−z/(1 + e^−z), so p/(1 − p) = 1/e^−z = e^z, and

This gives w a precise meaning: raising x by one unit adds w to the log-odds, which multiplies the odds by e^w. It does not add a fixed amount to the probability.

Worked example: the demo's defaults

w = 2, b = −6.

• Size 3: z = 0, p = 0.5, odds 1.
• Size 4: z = 2, p = 0.8808, odds 0.8808/0.1192 = 7.389 = e².
• Size 5: z = 4, p = 0.9820. The step from 3 to 4 added 0.38 to p; from 4 to 5 only 0.10. The odds multiplied by 7.389 both times.
• Moving the threshold to 0.2 means z ≥ ln(0.2/0.8) = −1.386, so size ≥ (−1.386 + 6)/2 = 2.31. Same model, different decision.

Code walkthrough: a sigmoid that never overflows

def sigmoid_stable(z):
    z = np.asarray(z, dtype=float)
    out = np.empty_like(z)
    pos = z >= 0
    out[pos] = 1.0 / (1.0 + np.exp(-z[pos]))      # exp of a non-positive number: at most 1
    ez = np.exp(z[~pos])                           # exp of a negative number: no overflow
    out[~pos] = ez / (1.0 + ez)                    # same value, rearranged
    return out

Common mistakes

• Reading w as a change in probability. Symptom: "each cm adds 2 to the probability". Fix: w is a change in log-odds; the probability change depends on where you start.
• Overflow in np.exp(-z). For z = −1000 it returns inf with a warning, and later code may produce NaN. Fix: the stable version above, or scipy.special.expit.
• Applying the sigmoid twice. Symptom: probabilities squeezed into (0.5, 0.73). Fix: one sigmoid, at the very end.
• Retraining to change the threshold. The threshold is applied after the model. Fix: keep the probabilities and choose the cut-off separately.

Derivation: w points across the boundary

Take two points x_A and x_B on the boundary. Both satisfy w·x + b = 0, so subtracting gives w·(x_A − x_B) = 0. Every direction along the boundary is perpendicular to w, so w is the boundary's normal vector, pointing toward the y = 1 side.

For any point x, write it as a point x₀ on the boundary plus t steps of length 1 along w/‖w‖. Then w·x + b = w·x₀ + b + t‖w‖ = t‖w‖, so

Lines of equal probability are parallel to the boundary, because p depends on x only through z.

Worked example: the lab's six points

After 10,000 steps the lab finds w = (5.281, 5.078), b = −14.222, so ‖w‖ = 7.327. At x₁ = 0 the boundary is at x₂ = 14.222/5.078 = 2.80.

Edge case: separable data has no finite answer

Every point is correctly classified, so the line separates the classes. Multiplying w and b by any c > 1 keeps the same boundary but pushes every p closer to its label, which lowers the log loss. The loss can always be reduced, so the minimum is at infinity. Run 100,000 steps instead of 10,000 and you get w = (8.35, 8.15), b = −22.69: almost the same boundary, much larger weights, and J falls from 0.0171 to 0.0017. Regularization (Lecture 3.6) gives a finite answer by charging for ‖w‖.

Worked example: the circle

With features (x₁, x₂, x₁², x₂²), w = (0, 0, 1, 1) and b = −1, z = x₁² + x₂² − 1. At (0.5, 0.5) z = −0.5 and p = 0.378 (inside, predicted 0). At (1, 1) z = 1 and p = 0.731. At (0, 1) z = 0, on the boundary, p = 0.5.

Common mistakes

• Dividing by w₂ when it is near zero. Symptom: a boundary drawn off the chart or a division warning. Fix: if |w₂| is small, solve for x₁ instead, or use plt.contour of z = 0 over a grid.
• Plotting the boundary in scaled coordinates on raw axes. Symptom: a line nowhere near the data. Fix: draw in the same space you trained in, or convert w and b back to raw units (Lecture 2.3 deep dive).
• Reading ‖w‖ as confidence in the boundary. On separable data ‖w‖ grows with training time. Fix: compare boundaries, or regularize.

Derivation: log loss is maximum likelihood

Treat each label as a biased coin: P(y = 1 | x) = f(x) and P(y = 0 | x) = 1 − f(x). Because y is 0 or 1, both cases are one formula: P(y | x) = f^y·(1 − f)^1−y. The probability of all m labels, assuming independent examples, is the product Πᵢ fᵢ^yᵢ(1 − fᵢ)^1−yᵢ. Maximizing it is the same as minimizing the average negative log, which turns the product into a sum:

By hand: three examples with labels (1, 0, 1) and predictions (0.9, 0.2, 0.7). The likelihood is 0.9 · 0.8 · 0.7 = 0.504, and the log loss is −ln(0.504)/3 = 0.2284.

Derivation: the gradient

For one example, L = −[y ln f + (1 − y) ln(1 − f)] with f = g(z) and z = w·x + b. Chain rule in three links:

1. ∂L/∂f = −y/f + (1 − y)/(1 − f) = (f − y) / (f(1 − f)).
2. ∂f/∂z = f(1 − f), from Lecture 3.2.
3. ∂z/∂wⱼ = xⱼ and ∂z/∂b = 1.

Multiply: the f(1 − f) cancels and ∂L/∂wⱼ = (f − y)·xⱼ. Averaging over examples gives the lecture's formula.

Derivation: convexity

Differentiate (f − y)xⱼ once more with respect to wₖ: only f depends on w, giving f(1 − f)·xⱼxₖ. So the Hessian is H = (1/m)·Σᵢ fᵢ(1 − fᵢ)·xᵢxᵢᵀ. Each term is a nonnegative number times xxᵀ, and vᵀxxᵀv = (v·x)² ≥ 0, so H is positive semidefinite everywhere and J is convex.

Why squared error on a sigmoid fails

Take one example with y = 0 and squared loss L(z) = g(z)². Then L′ = 2g·g′ = 2g²(1 − g), and

Negative curvature means the loss is not convex. It also goes flat exactly when the model is confidently wrong. At z = 5 (p = 0.9933 for a true 0), the squared-error gradient with respect to z is 2g²(1 − g) = 0.0132, while the log-loss gradient is f − y = 0.9933, 75 times larger. Log loss pushes hardest on the worst mistakes; squared error on a sigmoid barely notices them.

Common mistakes

• log(0). A prediction of exactly 0 or 1 for the wrong class gives an infinite loss and NaN gradients. Fix: clip p to [10⁻¹², 1 − 10⁻¹²], or compute the loss from z directly.
• Labels coded −1/+1. The formula assumes 0/1. Symptom: negative losses. Fix: map labels to 0/1.
• Expecting a closed form. Setting the gradient to zero gives equations with sigmoids inside; there is no normal-equation shortcut. Fix: iterate.
• Reading a small log loss as accuracy. J = 0.693 = ln 2 is chance level for balanced classes; J = 0.017 on six points says nothing about new ones. Fix: also measure accuracy on held-out data.

Worked example by hand: leave-one-out on five houses

With five examples, the most honest split is leave-one-out: fit on four houses, predict the fifth, repeat five times, average the squared errors. Do it for polynomial degrees 0 to 3. (Degree 4 cannot be tested this way: four points do not determine five coefficients.)

Training MSE (2J) falls every time the degree rises; it must, because a higher degree contains every lower one. Held-out MSE falls from degree 0 to 1 and then rises. Degree 0 underfits (high bias). Degree 3 fit to four points passes through all four exactly, so its held-out errors are pure extrapolation, worst at the ends (200 at x = 1.0 and x = 3.0). The line wins.

Derivation: why m points allow degree m − 1

A degree-d polynomial has d + 1 coefficients. Requiring it to pass through m points with distinct x gives m linear equations whose matrix has rows (1, xᵢ, xᵢ², …, xᵢᵈ). For d = m − 1 the matrix is square and, for distinct xᵢ, invertible. So there is always exactly one degree-(m − 1) polynomial through m points, and its training cost is zero whatever the data. Zero training cost is then a statement about counting, not about learning.

Derivation: bias and variance

Let the true price be y = h(x) + noise with variance σ², and let ŷ(x) be the prediction of a model trained on a random training set. Add and subtract the average prediction E[ŷ]:

A constant model has large bias and small variance. A degree-3 fit on four points has small bias and huge variance: drop a different house and the curve changes completely, as the 200-sized errors show. The best degree minimizes the sum.

Common mistakes

• Picking the degree on the test set. Symptom: a reported test error that is too optimistic, because you chose the model that happened to do best on it. Fix: choose on a validation split and touch the test set once.
• A single tiny split. With 14 points split 8/6, the winning degree can change with the random seed. Fix: repeat with several splits or use cross-validation.
• Scaling with statistics from all data. Symptom: slightly optimistic held-out error. Fix: fit μ and σ on the training part only, inside each split.
• Calling high training error overfitting. High training error is underfitting. Overfitting is the gap between training and held-out error.

Derivation: ridge for one feature

Minimize J = (1/2m)·[Σ(w·xᵢ + b − yᵢ)² + λw²], with b unpenalized.

1. ∂J/∂b = 0 gives b = ȳ − w·x̄, as without the penalty.
2. Substitute and write S_xx = Σ(xᵢ − x̄)², S_xy = Σ(xᵢ − x̄)(yᵢ − ȳ). Then ∂J/∂w = (1/m)·[w·S_xx − S_xy + λw] = 0.

For the five houses S_xy = 505 and S_xx = 2.5 (Lecture 1.3 deep dive).

As λ grows the line flattens toward the mean price, 510.

Derivation: the matrix form and shrinkage

With centered X and y, the same steps give (XᵀX + λI)w = Xᵀy. Adding λI raises every eigenvalue of XᵀX by λ, so the system is always solvable, even for the five houses with five parameters. In the eigenvector basis of XᵀX, with eigenvalues dₖ, each component of the unregularized solution is multiplied by dₖ/(dₖ + λ). Directions the data pins down well (large dₖ) barely shrink; poorly determined directions (small dₖ), where overfitting lives, shrink the most.

Weight decay

The gradient step is w ← w − α(∂J/∂w + (λ/m)w) = w·(1 − αλ/m) − α·∂J/∂w. With α = 0.1, λ = 1 and m = 5, every step first multiplies w by 0.98.

L1 versus L2

Replace λw² with λ|w|. For w ≠ 0 the derivative of |w| is sign(w), so step 2 becomes w·S_xx − S_xy + (λ/2)·sign(w) = 0, which gives

On the five houses with λ = 10 this gives (505 − 5)/2.5 = 200, and w is exactly 0 for every λ ≥ 1010. Ridge divides instead of subtracting, so its w is never exactly zero. That is why L1 (lasso) performs feature selection and L2 (ridge) does not.

Matching library conventions

Multiply our cost by 2m: Σe² + λ‖w‖². scikit-learn's Ridge(alpha=a) minimizes ‖y − Xw‖² + a‖w‖², so a = λ. Its LogisticRegression(C=c) minimizes c·Σ(log loss) + ½‖w‖²; dividing by c shows C = 1/λ.

Common mistakes

• Regularizing unscaled features. The penalty treats a weight of 0.6 per sq ft and 158 per bedroom on the same scale. Symptom: λ hits one feature far harder than another. Fix: z-score first.
• Penalizing b. Symptom: predictions pulled toward 0 instead of toward the mean. Fix: leave b out of the penalty.
• Choosing λ on training cost. Training cost is smallest at λ = 0 by construction. Fix: choose on validation data.
• Mixing conventions. λ in λ/(2m)·Σw² is not alpha in SGDRegressor, which multiplies a per-example average. Fix: write both costs out before comparing numbers.

Derivation

Neuron j of layer l computes z_j = w_j · a^[l−1] + b_j, then a_j = g(z_j). Write each weight vector w_j as a row and stack the rows into a matrix W^[l]. Row j times a^[l−1] is exactly w_j · a^[l−1], so all neurons of the layer are computed at once:

A layer with n_in inputs and n_out neurons therefore has n_out · n_in weights plus n_out biases. The activation g is applied element by element, so a layer is one matrix product, one vector addition and one elementwise function.

Worked example by hand

Input x = (1, 2), three sigmoid neurons:

As a matrix, W = [[0.5, −0.25], [1, 0.5], [−1, 1]] has shape 3×2 and b = (0, −1, 0.5). The layer maps a 2-vector to the 3-vector a = (0.5, 0.7311, 0.8176), and that vector is the input to the next layer.

Intuition: a feature one neuron cannot compute

XOR outputs 1 when exactly one of two bits is on. No single logistic unit can do it (Lecture 1.5 proves this), but two layers can. Set the hidden neurons by hand to h₁ = σ(20x₁ + 20x₂ − 10), which behaves like OR, and h₂ = σ(−20x₁ − 20x₂ + 30), which behaves like NAND. The output neuron σ(20h₁ + 20h₂ − 30) is an AND of the two.

For x = (0, 1): the output pre-activation is 20 · 0.99995 + 20 · 0.99995 − 30 = 9.998, and σ(9.998) = 0.99995. The hidden layer invented two intermediate features, OR and NAND, that make the final decision linear. Training does the same thing without being told which features to build; it will rarely find these exact ones.

Common mistakes

• Counting the input as a layer. The 64–25–15–1 network has three layers with parameters; layer 0 is just x. Symptom: parameter counts or layer indices off by one. Fix: number weight matrices, not vectors of values.
• Mixing the two indices. a^[2]₃ is neuron 3 of layer 2; x⁽⁷⁾ is example 7. Writing code where a loop over examples indexes layers produces shape errors that are hard to read. Fix: keep examples on the first array axis, layers in a Python list.
• Forgetting the biases. Counting only n_in · n_out gives 2,000 for the digit network instead of 2,031.
• Reading meaning into a hidden unit. "Affordability" in the lecture is an illustration. Permuting the 25 hidden units, with their rows and columns, gives an identical function, so unit 3 has no fixed identity across training runs.

Check yourself

A layer reads 3 inputs and has 4 neurons. What is the shape of W and how many parameters does it have?

Derivation of the shape rule

In z^[l] = W^[l] a^[l−1] + b^[l], a matrix of shape (p, q) can multiply a vector only if the vector has q entries, and the result has p entries. With n_l neurons in layer l, W^[l] must be (n_l, n_l−1) and b^[l] must have n_l entries. The parameter count follows: Σ_l n_l(n_l−1 + 1). The cost of one forward pass is Σ_l n_l · n_l−1 multiply-adds.

The first layer holds 80% of the parameters because it touches the widest vector. That pattern holds in most networks: the layers next to a wide input or a large vocabulary dominate the count.

Worked example by hand: a 2-2-1 network

This small network comes back in Lecture 2.2, where we backpropagate through it. Sigmoid on both layers, input x = (1, 0.5).

1. z^[1]₁ = 0.5 · 1 − 0.4 · 0.5 + 0.1 = 0.4 and z^[1]₂ = 0.3 · 1 + 0.8 · 0.5 − 0.2 = 0.5.
2. a^[1] = (σ(0.4), σ(0.5)) = (0.598688, 0.622459).
3. z^[2] = 1.2 · 0.598688 − 0.7 · 0.622459 + 0.05 = 0.718426 − 0.435721 + 0.05 = 0.332704.
4. a^[2] = σ(0.332704) = 0.582417, the predicted probability.
5. If the label is y = 1, the log loss is −ln 0.582417 = 0.540568.

Every intermediate number here is cached during a real forward pass, because backpropagation needs a^[1] and a^[2] again.

Common mistakes

• Transposed weights. Writing W^[1] as 64×25 in the lecture convention raises a shape error, which is the good case. If a layer is square, the transposed matrix multiplies without complaint and gives wrong numbers. Fix: assert shapes after building parameters.
• Nonlinearity missing on a hidden layer. The network still trains but behaves like logistic regression. Symptom: accuracy stuck at the linear baseline.
• Sigmoid on a regression output. Predictions are trapped in (0, 1) and house prices of 300 cannot be reached. Fix: linear output for regression.
• Applying the sigmoid twice. Taking σ of an output that is already a probability squeezes everything into (0.5, 0.73). Symptom: every prediction is "positive" at threshold 0.5.

Check yourself

How many parameters does a 784–128–10 network have?

Code walkthrough: shapes for a batch of 32

Row i of the batch matrix holds example i. Transposing the single-example rule gives (W^[l]a)^T = a^T(W^[l])^T, so the code's W is the lecture's W transposed, with shape (n_in, n_out).

X  (32, 64) @ W1 (64, 25) -> (32, 25)  + b1 (25,)  # b1 broadcast to every row
A1 (32, 25) @ W2 (25, 15) -> (32, 15)  + b2 (15,)
A2 (32, 15) @ W3 (15, 1)  -> (32, 1)   + b3 (1,)   # one probability per example

Broadcasting aligns trailing dimensions: (32, 25) + (25,) treats b as (1, 25) and repeats it 32 times. A bias of shape (25, 1) fails, which is helpful. The dangerous case is silent: probabilities of shape (32, 1) minus labels of shape (32,) broadcast to a (32, 32) matrix, and the mean of that matrix is a valid-looking but meaningless loss. Flatten one side with .ravel() before comparing.

Derivation: why the scale of random weights matters

For one neuron, z = Σ_k=1..n w_ka_k with weights drawn independently, mean 0, variance s². Independence makes the variance of the sum the sum of variances, and for each term Var(w_ka_k) = E[w_k²]E[a_k²] = s² E[a²]. So

If the previous layer is roughly linear around 0 (tanh near 0), E[a²] ≈ Var(z_prev), and keeping Var(z) constant across layers needs s² = 1/n. This is Xavier/LeCun initialization. For ReLU, a = max(0, z) with z symmetric about 0, so half the mass is zeroed and E[a²] = ½ Var(z_prev). Keeping the variance constant now needs s² = 2/n. This is He initialization.

Worked example: ten ReLU layers

Feed 1,000 standard normal vectors through ten ReLU layers of width 256 and print the standard deviation of the activations after layers 1, 5 and 10.

With std 0.01, each layer multiplies the scale by about 0.01 · √256 · √½ = 0.113, and ten such factors leave nothing. With std 1 the factor is 11.3 and activations overflow. Xavier with ReLU loses a factor √½ per layer. Only He keeps the signal, and the same argument applies to gradients flowing backwards.

Why not zeros

If all of W^[1] is zero, every hidden unit computes the same value and receives the same gradient, so after any number of steps the units are still copies. With ReLU and all-zero weights it is worse: the hidden activations are 0 and the gradient to W^[1] is exactly 0, so nothing moves.

Common mistakes

• Labels shaped (m,) against outputs shaped (m, 1). Symptom: loss that barely changes or accuracy near 50% on an easy task. Fix: y.reshape(-1, 1) or out.ravel().
• Bias stored as (1, n_out) in one place and (n_out,) in another. Works by broadcasting but breaks code that checks shapes. Pick one.
• std 1 initialization in a deep net. Symptom: nan loss in the first step. Fix: scale by √(2/n_in).
• Looping over examples. A Python loop over 1,000 rows pays interpreter overhead 1,000 times, where one matrix product pays it once and runs in optimized BLAS code. Fix: vectorize the batch.

Code walkthrough: inside nn.Linear

nn.Linear(64, 25) stores weight with shape (25, 64), the lecture convention of one row per neuron, and computes x @ weight.T + bias. That is why Lab 1 transposes the weight before using it in NumPy. Both tensors are nn.Parameters, which means autograd tracks them and model.parameters() finds them.

The default initialization draws weights and biases uniformly from (−1/√n_in, 1/√n_in). For n_in = 64 the bound is 0.125, so the largest weight you see is just under 0.125, and the standard deviation is 0.125/√3 = 0.072. A uniform distribution on (−c, c) has variance c²/3, so the weight variance is 1/(3n_in), a third of the Xavier value. Shallow networks do not care. For deep ReLU stacks, call nn.init.kaiming_normal_ yourself.

Derivation: the stable binary cross-entropy

With p = σ(z), the loss is −y log σ(z) − (1 − y) log(1 − σ(z)). Use two identities: log σ(z) = −log(1 + e^−z) and log(1 − σ(z)) = −z − log(1 + e^−z). Substituting:

To see the two forms agree for z < 0, write log(1 + e^−z) = −z + log(1 + e^z); the first form becomes −yz + log(1 + e^z), which is the second. Differentiating either form gives ∂loss/∂z = σ(z) − y.

Worked example by hand

Take a confidently wrong logit z = 40 with y = 0. In float32, σ(40) = 1 − 4.2·10⁻¹⁸ rounds to exactly 1.0. Sigmoid followed by nn.BCELoss must compute −log(1 − 1) = −log 0. PyTorch clamps the log at −100 and reports a loss of 100, and the gradient through the saturated sigmoid is 0, so the model cannot learn from this example. BCEWithLogitsLoss computes 40 + log(1 + e⁻⁴⁰) = 40.0 with gradient σ(40) − 0 = 1.

Why zero_grad exists

backward() adds into .grad rather than overwriting it. With w = 3 and loss w², the first backward() leaves w.grad = 6; calling it again without zeroing leaves 12. Accumulation is deliberate (it lets you sum gradients over several small batches), but in a normal loop forgetting zero_grad() means every step uses the sum of all past gradients.

Common mistakes

• Integer labels for BCE. BCEWithLogitsLoss needs float targets of the same shape as the logits. Symptom: a dtype error, or a size-mismatch error if the logits are (m, 1) and labels (m,). Fix: .float() and .squeeze(1).
• Float64 NumPy arrays into a float32 model. Symptom: "mat1 and mat2 must have the same dtype". Fix: torch.tensor(X, dtype=torch.float32).
• Evaluating with gradients on. Memory grows because every test forward builds a graph. Fix: with torch.no_grad():.
• Sigmoid layer inside the model plus BCEWithLogitsLoss. The sigmoid is applied twice and the loss can never go to 0. Fix: let the model output logits.

Check yourself

What are nn.Linear(64, 25).weight.shape and its parameter count?

Derivation: stacked linear layers are one layer

Without activations, W^[2](W^[1]x + b^[1]) + b^[2] = (W^[2]W^[1])x + (W^[2]b^[1] + b^[2]). The product of the matrices is a single matrix W and the bracket is a single vector b. By induction this holds for any depth.

Numeric check: W^[1] = [[1, 2], [0, 1]], b^[1] = (1, 0), W^[2] = [1, −1], b^[2] = 0.5. Then W = W^[2]W^[1] = [1, 1] and b = 1 · 1 − 1 · 0 + 0.5 = 1.5. For x = (2, 3): the two-layer path gives hidden values (2 + 6 + 1, 3) = (9, 3) and output 9 − 3 + 0.5 = 6.5; the collapsed layer gives 2 + 3 + 1.5 = 6.5.

Derivation: no single linear boundary solves XOR

Suppose w₁x₁ + w₂x₂ + b is positive exactly on the XOR-true points. Then (0, 0) gives b < 0; (1, 0) gives w₁ + b > 0; (0, 1) gives w₂ + b > 0; (1, 1) gives w₁ + w₂ + b < 0. Adding the middle two: w₁ + w₂ + 2b > 0, so w₁ + w₂ + b > −b > 0, contradicting the last inequality. The crescents in the demo fail for the same reason, only less cleanly.

Derivation: why one hidden unit is no better than logistic regression

With h = 1, the output is σ(v · tanh(w · x + b) + c). Both σ and tanh are monotone, so the output is a monotone function of the single number w · x + b. Any threshold on the output is a threshold on w · x + b, which is a straight line in the plane. Setting h = 1 in the demo always gives a straight boundary. The same argument holds for a ReLU unit, because ReLU is also monotone.

Worked example: building a bump from two units

Two sigmoid units with opposite signs make a bump: f(x) = σ(10(x − 0.3)) − σ(10(x − 0.7)).

The function is high between 0.3 and 0.7 and low outside. An output layer can scale and add many such bumps, two hidden units each, to approximate any continuous function of one variable on an interval as closely as you like, provided you have enough units. This is the idea behind the universal approximation theorem. It promises that a wide enough network can represent the function; it says nothing about whether gradient descent will find the weights or how many examples that takes.

Counting the demo network

The demo's 2 → 8 → 1 network has 8 · 2 + 8 = 24 hidden parameters and 8 + 1 = 9 output parameters, 33 in total, against sixty training points. That ratio is why the boundary can wrap around individual points when you train long enough.

Common mistakes

• Adding depth without activations. The model is still linear. Symptom: same accuracy as logistic regression however many layers you add.
• Taking the approximation theorem as a guarantee. A network that could represent the function can still underfit if training is too short or the learning rate is wrong.
• Too few hidden units for the shape. h = 2 can draw at most two lines; a crescent boundary needs several. Symptom: training accuracy plateaus well below 100%.
• Too many units and too few points. h = 100 on sixty points produces islands around single examples. Check on held-out points.

Derivation

Write the loss for one example with true class y directly in terms of the logits. Since a_y = e^z_y / Σ_je^z_j,

Differentiate with respect to one logit z_k. The first term contributes −1 if k = y and 0 otherwise. The derivative of log Σ_je^z_j is e^z_k / Σ_je^z_j = a_k. So

The same result comes out of the long route. The softmax Jacobian is ∂a_i/∂z_k = a_i(δ_ik − a_k), and ∂L/∂a_i = −y_i/a_i. Multiplying and summing over i gives −Σ_i y_i(δ_ik − a_k) = −y_k + a_kΣ_iy_i = a_k − y_k, because the one-hot entries sum to 1. The awkward 1/a_i cancels, which is why frameworks fuse softmax and cross-entropy into one operation.

With K = 2, a₁ = e^z₁/(e^z₁ + e^z₂) = 1/(1 + e^{−(z₁−z₂)}) = σ(z₁ − z₂). Only the difference of the two logits matters, and the gradient a − y is the familiar one from logistic regression.

Worked example by hand

Logits z = (2, 1, 0.1), true class 0.

1. Exponentials: e² = 7.389, e¹ = 2.718, e^0.1 = 1.105; sum 11.213.
2. Probabilities: 7.389/11.213 = 0.659, 0.242, 0.099.
3. Loss: −ln 0.659 = 0.417.
4. Gradient: (0.659 − 1, 0.242, 0.099) = (−0.341, 0.242, 0.099). It sums to zero, so a step raises the true logit and lowers the others by the same total.

Stability: for z = (1000, 1001), e¹⁰⁰⁰ overflows to inf and the ratio becomes nan. Subtracting the max gives (−1, 0), probabilities (0.269, 0.731), and log-sum-exp = 1001 + log(e⁻¹ + 1) = 1001.3133.

A sanity check you can run on every new model

A freshly initialized K-class network outputs logits near zero, so all probabilities are near 1/K and the loss is near ln K. For ten digits that is ln 10 = 2.303. If your first printed loss is 23 instead, the logits are far too large (bad initialization or unscaled inputs). If it is 0.69, you are using a binary loss by mistake.

Common mistakes

• Softmax in the model and in the loss. CrossEntropyLoss then applies softmax to numbers in [0, 1]. With ten classes the best it can reach is e/(e + 9) = 0.232 for the true class, so the loss cannot fall below −ln 0.232 = 1.461 and gradients are small. Symptom: loss stalls around 1.5 while accuracy looks fine.
• Labels from 1 to K. Class index K is out of range. Symptom: "index out of bounds" or a CUDA assert. Fix: labels 0..K−1.
• One-hot float targets of the wrong shape. CrossEntropyLoss expects integer labels (m,), or class probabilities with the same shape as the logits. Mixing them gives shape errors.
• log(softmax(z)) in two steps. An underflowed probability of 0 gives −inf. Fix: compute log-softmax as z − logsumexp(z).
• log base confusion. Losses use natural log; 2.303 for ten classes in nats is 3.32 in bits. Compare like with like.

Derivation for the output unit

For a sigmoid output a = σ(z) with log loss L = −y ln a − (1 − y) ln(1 − a): ∂L/∂a = −y/a + (1 − y)/(1 − a) and ∂a/∂z = a(1 − a). Multiplying, the a(1 − a) cancels the denominators and leaves ∂L/∂z = a − y. That is the dZ2 = A2 − y line in the lecture code.

Derivation for a dense layer in matrix form

For a batch, Z = A_prevW + b with δ = ∂L/∂Z known. Entry Z_nk = Σ_iA_prev,niW_ik + b_k. Weight W_ik appears in Z_nk for every example n, with coefficient A_prev,ni, so ∂L/∂W_ik = Σ_nA_prev,niδ_nk, which is (A_prev^Tδ)_ik. Input A_prev,ni appears in Z_nk for every neuron k with coefficient W_ik, so ∂L/∂A_prev,ni = Σ_kδ_nkW_ik = (δW^T)_ni. The bias appears once per example, so ∂L/∂b = Σ_nδ_n. Each layer needs two matrix products backwards against one forwards, which is where "about twice a forward pass" comes from.

Worked example by hand

Use the network and forward values from Lecture 1.2 (lecture convention, W^[1] rows are neurons): x = (1, 0.5), y = 1, a^[1] = (0.598688, 0.622459), a^[2] = 0.582417, loss 0.540568.

Gradient check: nudge W^[1]₁₁ from 0.5 to 0.5 ± 10⁻⁵, rerun the forward pass, and take (L₊ − L₋)/(2 · 10⁻⁵). The result is −0.1203945, matching the table. One gradient-descent step with learning rate 0.5 on all eight parameters lowers the loss from 0.540568 to 0.386820.

Read the signs: dW^[2]₂ is negative, so the step increases the weight from hidden unit 2 even though it started at −0.7, because raising it raises the output toward y = 1. The gradient to hidden unit 1's weights is negative and to unit 2's is positive, because they reach the output through weights of opposite sign.

Common mistakes

• Forgetting the 1/m. If the loss is a batch mean, dZ must be divided by m. Symptom: the effective learning rate grows with batch size; a gradient check fails by a factor of exactly m.
• Using σ′(a) instead of σ′(z). The sigmoid derivative is a(1 − a), written in terms of the output. Computing σ(a)(1 − σ(a)) applies the sigmoid twice. For ReLU, (Z > 0) and (A > 0) are the same mask, which hides this bug until you switch activations.
• Not summing the bias gradient over the batch. db must have shape (n_out,), not (m, n_out).
• Gradient checks in float32 or with tiny ε. Rounding error dominates. Use float64, ε around 10⁻⁵ and a central difference; agreement to about 10⁻⁷ relative is a pass.

Derivation

Take a chain of scalar layers a_l = g(w_la_l−1). By the chain rule, ∂a_L/∂a₀ = Π_l=1..L w_lg′(z_l). For vectors each factor becomes a matrix W_l^Tdiag(g′(z_l)), but the conclusion is the same: the gradient at layer 1 is a product of L terms. If each term is typically below 1 the product shrinks geometrically; above 1 it grows.

Worked example: gradient norms in a 10-layer network

Ten hidden layers of width 64, batch of 256 random inputs, loss = mean squared output, biases zero. Sigmoid and tanh use Xavier initialization, ReLU uses He. Compare the gradient norm of the first layer's weights with the tenth's:

With sigmoid the first layer gets a gradient five million times smaller than the last, a factor of about 0.18 per layer over nine layers. With one learning rate for all layers, the early layers do not move. Tanh and ReLU keep the ratio within a factor of five. Tanh does well here because it is centered at zero and its slope is 1 at the origin; sigmoid's outputs are centered at 0.5 and its slope never exceeds 0.25.

Dead ReLUs

A ReLU unit computes max(0, w · x + b). If a large update pushes b to, say, −10 while the inputs lie in [0, 1] and the weights are small, w · x + b is negative for every example. The output is always 0, the local derivative is always 0, and no gradient ever reaches w or b again. Leaky ReLU, max(0.01z, z), keeps a slope of 0.01 for negative inputs so the unit can recover. GELU, z · Φ(z) with Φ the standard normal CDF, is smooth: GELU(1) = 0.8413, GELU(−1) = −0.1587, GELU(−3) = −0.0040.

Output activations and the loss that goes with them

Pair the sigmoid output with log loss, not squared error. With squared error ½(a − y)², the gradient at z is (a − y) · a(1 − a). For a confidently wrong prediction a = 0.001 with y = 1, that is −0.999 · 0.001 · 0.999 = −0.000998: almost no signal exactly when the model is most wrong. With log loss the gradient is a − y = −0.999.

Common mistakes

• Sigmoid in the hidden layers of a deep net. Symptom: training loss flat for many epochs, early-layer weights unchanged. Fix: ReLU or GELU with He initialization.
• ReLU on a regression output. The network cannot predict negative values. Symptom: all negative targets predicted as 0. Fix: linear output.
• Learning rate so high that many ReLUs die. Symptom: accuracy drops and never recovers; many hidden activations are exactly 0 for every input. Fix: lower the learning rate or use leaky ReLU.
• Sigmoid output with MSE. Learning stalls on confident mistakes, as computed above.

Setup

Minimize f(w) = w² starting from w = 1 with learning rate α = 0.1. The gradient is g = 2w.

Worked example: plain SGD and momentum

Plain gradient descent multiplies w by 1 − 0.1 · 2 = 0.8 each step: 0.8, 0.64, 0.512. Momentum with v ← 0.9v + g and w ← w − αv:

Momentum reaches 0.062 where SGD is at 0.512, because the velocity keeps growing while gradients agree in sign. The same speed makes it overshoot zero on the next steps and oscillate with decreasing amplitude. In a narrow valley, gradient components across the valley change sign every step and cancel in v, while the component along the valley accumulates.

Worked example: Adam

β₁ = 0.9, β₂ = 0.999, ε = 10⁻⁸, m and v start at 0. Bias-corrected m̂ = m/(1 − β₁^t), v̂ = v/(1 − β₂^t), step = α m̂/(√v̂ + ε).

Check step 2: v = 0.999 · 0.004 + 0.001 · 1.8² = 0.007236; v̂ = 0.007236/(1 − 0.999²) = 0.007236/0.001999 = 3.61981; m̂ = 0.36/0.19 = 1.894737; step = 0.1 · 1.894737/1.902580 = 0.099588. Each step is close to α = 0.1, whatever the size of the gradient. On f(w) = 1000w² the first step is still 0.1. That scale invariance is what lets one learning rate serve layers whose gradients differ by orders of magnitude.

Derivation of the bias correction

Unrolling m_t = β₁m_t−1 + (1 − β₁)g_t from m₀ = 0 gives m_t = (1 − β₁)Σ_i=1..tβ₁^t−ig_i. If the gradient were constant g, the geometric sum gives m_t = g(1 − β₁^t), so dividing by 1 − β₁^t recovers g. The same holds for v. Without correction, the first step would be α · 0.1g/√(0.001g²) = 3.16α, more than three times too large, because v starts further below its target than m does. The averages remember roughly 1/(1 − β) steps: about 10 for m and 1,000 for v.

Mini-batch noise

If per-example gradients have variance σ², the mean over a batch of B has variance σ²/B. Going from batch 32 to 256 cuts the gradient's standard deviation by √8 = 2.83 at eight times the cost per step.

Common mistakes

• Using Adam's learning rate with SGD, or the reverse. lr 1e-3 is slow for plain SGD on many problems; lr 0.1 usually makes Adam diverge.
• Skipping bias correction in a hand-written Adam. Symptom: unstable first few hundred steps. Fix: divide by 1 − β^t.
• Recreating the optimizer inside the epoch loop. m and v reset to zero every epoch. Create it once.
• Adam's weight_decay is not AdamW's. In Adam the decay term λw is added to the gradient and then divided by √v̂, so weights with large gradients are barely decayed. AdamW subtracts αλw from the weights directly.

Steps and batch bookkeeping

10,000 examples with batch size 64 give ⌈10000/64⌉ = 157 steps per epoch, and the last batch has 10,000 − 156 · 64 = 16 examples. In Lab 2, 1,077 training digits give 17 steps with a last batch of 53. Averaging the 17 batch losses equally would overweight those 53 examples slightly. That is why the lab accumulates loss.item() * len(xb) and divides by the dataset size.

Derivation: cosine decay and warmup

With η_max = 10⁻³, η_min = 0 and T = 30: t = 0 gives 1e-3; t = 10 gives 7.5e-4; t = 15 gives 5e-4; t = 20 gives 2.5e-4; t = 29 gives 2.7e-6. Because sched.step() runs at the end of each epoch, epoch t trains at η_t. The curve is flat at both ends: it keeps a high rate for the early epochs and spends the last few at very small steps. Linear warmup for S steps uses η_s = η_peak(s + 1)/S for s < S, then hands over to the decay.

Derivation: inverted dropout

During training, each activation is kept with probability 1 − p and zeroed otherwise, and kept values are divided by 1 − p. With mask entry m_i ∈ {0, 1}, the output is a_im_i/(1 − p), whose expectation is a_i(1 − p)/(1 − p) = a_i. Because the expected activation already matches, evaluation mode can simply pass activations through unchanged. Example with p = 0.2 (scale 1/0.8 = 1.25): a = (2, 4, 6, 8, 10) with mask (1, 0, 1, 1, 0) becomes (2.5, 0, 7.5, 10, 0). Each step trains a different thinned network, so no unit can rely on one specific partner being present.

Weight decay in numbers

AdamW multiplies every weight by 1 − η · λ each step before the Adam update. With η = 10⁻³ and λ = 0.01 that factor is 0.99999. Over 10,000 steps at constant η, a weight that received no gradient would shrink to 0.99999¹⁰⁰⁰⁰ = 0.905 of its value. Decay is gentle per step and adds up over a long run.

Early stopping with patience

The lecture loop keeps the best checkpoint but still runs all epochs. Adding patience stops once the validation loss has not improved for k consecutive epochs. With k = 10 on a run whose minimum is at epoch 18, training ends after epoch 28 and the epoch-18 weights are restored.

Common mistakes

• Saving the state dict without .clone(). state_dict() returns references to the live tensors, which keep changing. Symptom: the "best" checkpoint is identical to the last epoch. Fix: clone each tensor, or copy.deepcopy.
• Validating in train mode. Dropout stays active, so validation loss is noisy and too high. Fix: model.eval() before evaluation and model.train() after.
• Calling sched.step() per batch with T_max in epochs. The rate reaches zero after 30 batches, and because CosineAnnealingLR is periodic it then rises again. Symptom: a sawtooth loss curve. Fix: match the unit of T_max to where you call step().
• No shuffling on sorted data. If examples are sorted by class, each batch contains one class and the model chases the latest batch. Fix: shuffle=True.
• Peeking at the test set inside the loop. Choosing the checkpoint by test loss turns the test set into a validation set.

Derivation: the optimism of picking the best

Suppose you try k configurations that are all equally good, with true error e. Each validation estimate is an average over n examples, so it is approximately normal with mean e and standard deviation s = √(e(1 − e)/n). You keep the configuration with the lowest observed error. The expected minimum of k independent normals is e − c_ks, where c_k is the expected maximum of k standard normals: c₅ = 1.163, c₂₀ = 1.867, c₁₀₀ = 2.508.

Worked example by hand

e = 0.10, n = 500 validation examples, k = 20 configurations.

1. s = √(0.1 · 0.9/500) = √0.00018 = 0.0134.
2. Expected best observed error = 0.10 − 1.867 · 0.0134 = 0.0749.

Every configuration is a 10% model, yet the winner reports 7.5% on the set used to choose it. The test set exists to measure the winner on data that played no part in the choice. The same arithmetic explains why a public leaderboard that you submit to hundreds of times stops telling the truth.

How precise is a test score?

The 95% interval for an accuracy measured on n examples is about ±1.96√(acc(1 − acc)/n). Lab 2 splits the 1,797 digits into 1,077 / 360 / 360 (test_size 0.2, then 0.25 of the remaining 80%, which is another 20%). For acc = 0.97 on 360 test digits, the half-width is 1.96 · 0.0090 = 0.0176. Two models at 96.9% and 97.8% on that test set are not reliably different.

k-fold cross-validation in numbers

With 5 folds over the 1,437 non-test digits, each model trains on about 1,150 examples and validates on about 287, and every example is used for validation exactly once. The cost is five trainings per configuration. After choosing, retrain once on all 1,437 examples. For classification, use stratified folds so each fold keeps the class proportions; with 10 digit classes and 287 examples per fold, an unlucky unstratified fold can be visibly short of one digit.

Leakage: when the test set is not as sealed as it looks

• Preprocessing fit on all data. A scaler or PCA fit before splitting has seen the test rows. Fit it on the training split only, or use a scikit-learn Pipeline inside cross-validation.
• Groups split across sets. Several scans from one patient, or several photos of one product, end up on both sides. The model recognizes the patient rather than the disease. Use GroupKFold or split by group ID.
• Time. A random split of time-ordered data lets the model train on the future. Split by date: train on the past, validate on the following period, test on the period after that.
• Duplicates. Exact or near-duplicate rows on both sides inflate scores. Deduplicate before splitting.

Common mistakes

• Tuning on the test set "just once more". Each look spends it. Symptom: test score drifts up over a project while production performance does not.
• A validation set too small to resolve the differences you care about. With 100 examples, s ≈ 0.03 at 10% error, so differences of a couple of points are noise.
• Reporting cross-validation error after choosing on it. That number is optimistic for the same reason as above. Keep a separate test set, or use nested cross-validation.

Check yourself

With 100 equally good configurations, n = 500 and e = 0.10, what is the expected best observed error?

Derivation

Assume y = f(x) + ε with E[ε] = 0 and Var(ε) = σ², and let f̂ be the model trained on a random training set D. Fix a point x and average the squared error over both the noise and the training set. Write f̂ for f̂(x) and f̄ = E_D[f̂].

1. E[(y − f̂)²] = E[(f + ε − f̂)²] = E[ε²] + 2E[ε(f − f̂)] + E[(f − f̂)²].
2. The noise at the test point is independent of D and has mean 0, so the middle term is 0, and E[ε²] = σ².
3. Add and subtract f̄: E[(f − f̂)²] = (f − f̄)² + 2(f − f̄)E[f̄ − f̂] + E[(f̂ − f̄)²].
4. E[f̄ − f̂] = f̄ − f̄ = 0, so the cross term vanishes.

Worked example by hand

The true value at x₀ is f = 2 and the noise variance is σ² = 0.1. Train the same model on four different training sets and get predictions 1.5, 2.5, 2.0, 3.0 at x₀.

1. f̄ = (1.5 + 2.5 + 2.0 + 3.0)/4 = 2.25, so bias² = 0.25² = 0.0625.
2. Variance = (0.75² + 0.25² + 0.25² + 0.75²)/4 = (0.5625 + 0.0625 + 0.0625 + 0.5625)/4 = 0.3125.
3. Check directly: mean of (f̂ − f)² = (0.25 + 0.25 + 0 + 1)/4 = 0.375 = 0.0625 + 0.3125.
4. Expected test error = 0.1 + 0.375 = 0.475.

Variance dominates here, so the fixes are the variance fixes: more data, regularization, or averaging several models (which divides the variance term, as Lecture 3.6 shows).

From the formula to the diagnostic table

You cannot compute f̄ in practice, so the lecture's table uses observable proxies. The baseline stands in for σ²; training error minus baseline approximates bias; validation minus training error approximates variance. Reading the table's four rows that way: the first has 8 points of bias and 1 of variance; the second 1 and 9; the third 8 and 10; the fourth 1 and 1 on top of a 10% baseline. The exact decomposition only holds for squared error. For 0/1 classification error it is not additive, so treat the table as a heuristic that points you at the bigger problem, not as an exact split.

Sweeping λ

At λ = 0 the model is free to chase each training set, so f̂ moves a lot between sets: high variance, low bias. As λ grows the weights are pulled toward zero, f̂ becomes nearly the same for every D (variance falls) but sits further from f (bias rises). Validation error is the sum, so it is U-shaped in λ, and the minimum is where the two rates of change balance.

Common mistakes

• Comparing training error to 0 instead of the baseline. 8% training error on a task where humans get 7% is not high bias.
• Diagnosing from validation error alone. 15% validation error can be either problem; you need the training error to tell which.
• Collecting data for a high-bias model. The learning curve (Lecture 3.3) is flat; more data buys almost nothing.
• Regularizing a model that underfits. Raising λ or adding dropout to a high-bias model makes training error worse.

Check yourself

Baseline 5%, training 6%, validation 15%. Diagnosis and first fix?

Derivation: a power law for validation error

Across many model families, validation error as a function of training-set size n is well described by err(n) ≈ c + a · n^−b: a floor c set by noise and model bias, and a term that shrinks as a power of n. Three measurements at sizes in a fixed ratio are enough to solve for all three constants.

Worked example by hand

Validation errors: 0.25 at n = 100, 0.15 at n = 400, 0.10 at n = 1,600.

1. Each step quadruples n. The drops are 0.25 − 0.15 = 0.10 and 0.15 − 0.10 = 0.05. For a power law, successive drops shrink by the factor 4^b, so 4^b = 0.10/0.05 = 2 and b = 0.5.
2. The second drop is a(400^−0.5 − 1600^−0.5) = a(0.05 − 0.025) = 0.025a = 0.05, so a = 2.
3. The floor: c = 0.10 − 2 · 1600^−0.5 = 0.10 − 0.05 = 0.05.
4. Predictions: n = 3,200 gives 0.05 + 2/√3200 = 0.0854; n = 6,400 gives 0.05 + 2/80 = 0.075.

Doubling the data from 1,600 to 3,200 buys about 1.5 points; quadrupling buys 2.5; no amount of data goes below 5%. If the baseline is 2%, the remaining 3 points are bias, and capacity, not data, is the next investment. Fit on log axes and treat the extrapolation as a rough guide: it is reliable for a doubling or two, not for a factor of a hundred.

Reading the two curves

At small n the training error is near 0 because a flexible model can memorize a few examples, and validation error is high. As n grows the two curves approach each other. High bias: they meet early, both above the baseline, and the validation curve is flat. High variance: a wide gap remains at the largest n and the validation curve still slopes down.

Error analysis as arithmetic

A model has 10% validation error. You inspect 100 misclassified examples: 60 are category A, 25 category B, 15 category C. Fixing every A error would bring the error to 10% · 0.40 = 4%. A realistic fix that removes half the A errors brings it to 7%. Fixing every C error, the best case for C, only brings it to 8.5%. These ceilings tell you which project can possibly pay off before you start it.

Augmentation must preserve the label

Shifting a digit by one pixel or rotating it by 10 degrees keeps it the same digit. Rotating a 6 by 180 degrees makes a 9, and horizontally flipping text produces characters that do not exist. Check each transform against the label before using it.

Common mistakes

• Fixed epochs at every size. With batch 64, 107 examples give 2 steps per epoch and 1,077 give 17. Thirty epochs is 60 updates for the small subset against 510 for the full set, so small subsets may look worse partly because they were undertrained. Fix: fix the number of steps, or train each size to convergence with early stopping.
• Non-random subsets. Taking the first n rows of a sorted file changes the class mix with n. Shuffle (or stratify) once, then take prefixes.
• One seed per point. Small-n points are noisy. Average two or three seeds before reading a trend.
• Measuring training error on the full training set. It must be computed on the n examples the model was trained on.

Worked example: one confusion matrix, every metric

1,000 transactions, 60 of them fraud. The model flags 50, of which 40 are fraud.

• Accuracy = (40 + 930)/1000 = 0.97. Flagging nothing gets 0.94, so accuracy says little.
• Precision = 40/50 = 0.80. Recall = 40/60 = 0.667.
• F1 = 2 · 0.8 · 0.667/(0.8 + 0.667) = 0.727.
• False-positive rate = 10/940 = 0.0106; specificity = 930/940 = 0.989.

Derivation: why the harmonic mean

F1 = 2PR/(P + R) is the harmonic mean, 1/F1 = ½(1/P + 1/R). It is dominated by the smaller value. A model that flags one sure case out of a hundred frauds has P = 1, R = 0.01: the arithmetic mean is 0.505, the harmonic mean is 2 · 0.01/1.01 = 0.0198. When recall matters more, use F_β = (1 + β²)PR/(β²P + R); β = 2 weights recall more heavily, and for the matrix above F₂ = 0.690.

Worked example: ROC curve and AUC by hand

Nine examples sorted by score. Positives: 0.9, 0.8, 0.55, 0.4. Negatives: 0.7, 0.5, 0.3, 0.2, 0.1. Lower the threshold one score at a time; each positive passed raises TPR by 1/4, each negative raises FPR by 1/5.

The area under this staircase is 0.2 · 0.5 + 0.2 · 0.75 + 0.6 · 1 = 0.85. Equivalently, AUC is the probability that a random positive scores above a random negative. Of the 4 · 5 = 20 positive-negative pairs, only three are misordered (0.55 below 0.7, 0.4 below 0.7, 0.4 below 0.5), so AUC = 17/20 = 0.85. The pair view explains why AUC ignores the threshold and depends only on the ranking.

Why ROC is less sensitive to class ratio than precision

TPR is computed only over positives and FPR only over negatives, so duplicating every negative ten times leaves the ROC curve unchanged. Precision mixes the two classes: the same duplication multiplies FP by ten and precision in the example above falls from 0.80 to 40/140 = 0.29. A precision-recall curve's no-skill line sits at the positive rate (0.06 here), while ROC's sits at the diagonal, AUC 0.5.

Common mistakes

• AUC from hard labels. roc_auc_score(y, probs > 0.5) gives a curve with one corner and throws away the ranking. Pass the scores.
• Wrong positive class. With labels where 0 means malignant, average="binary" scores class 1 by default. Flip the labels or set pos_label.
• Choosing the threshold on the test set. Choose it on validation, then report test once.
• Undefined precision. If nothing is flagged, TP + FP = 0. scikit-learn warns and returns 0; your own code divides by zero unless you guard it.

Worked example: information gain for every root split

The ten animals from the lab: five cats. Root entropy H(0.5) = 1. For each feature, "left" is the examples with value 1.

Check one entry: H(0.8) = −0.8 log₂0.8 − 0.2 log₂0.2 = 0.8 · 0.3219 + 0.2 · 2.3219 = 0.2575 + 0.4644 = 0.7219. For round face, 0.7 · 0.9852 + 0.3 · 0.9183 = 0.6897 + 0.2755 = 0.9651.

Second level. On the pointy-ear side (4 cats, 1 not), round face separates it perfectly, gain 0.7219, against 0.171 for whiskers. On the floppy-ear side (1 cat, 4 not), whiskers separates it perfectly, gain 0.7219, against 0.3219 for round face. The depth-2 tree is: ears, then face on one side and whiskers on the other, and it classifies all ten animals correctly.

Derivation: Gini impurity and how it compares

Gini impurity is the probability that two examples drawn at random from the node, with replacement, have different labels: 1 − p² − (1 − p)² = 2p(1 − p).

Both are zero for a pure node, peak at p = 0.5 and are strictly concave, so they rank splits the same way almost always. On the cat data the Gini gains are 0.18, 0.0238 and 0.0833: same order as entropy. Gini avoids a logarithm and is scikit-learn's default. Entropy is in bits, which makes the gain readable as information.

Derivation: why not just use the error rate?

Strict concavity guarantees that a split which changes the class mix lowers the weighted impurity (Jensen's inequality). The misclassification rate min(p, 1 − p) is only piecewise linear, so many useful splits score zero. A node with 7 cats out of 10 has error 0.3. Split it into 4 of 5 cats and 3 of 5 cats: the errors are 0.2 and 0.4, weighted 0.3, gain 0. Entropy sees a gain of 0.8813 − ½(0.7219 + 0.9710) = 0.0349, and the left child is now easier to split further.

Continuous features: thresholds at midpoints

x = (2, 3, 5, 6, 8, 9) with labels (0, 0, 1, 0, 1, 1). The candidate thresholds are the midpoints 2.5, 4, 5.5, 7, 8.5, with gains 0.191, 0.459, 0.082, 0.459, 0.191. Thresholds 4 and 7 tie; an implementation keeps the first it finds. With n distinct values there are n − 1 candidates; sorting once makes each candidate's counts an update rather than a recount.

Regression trees

For x = (1, 2, 3, 4) and y = (3, 5, 9, 11) the variance is 10. Splitting at 2.5 leaves {3, 5} and {9, 11}, each with variance 1, so the weighted variance is 1.0, a reduction of 9. Splitting at 1.5 or 3.5 leaves 4.667. The tree picks 2.5 and predicts 4 and 10 in the leaves.

Common mistakes

• No stopping rule. An unlimited tree reaches pure leaves of one example each: 100% training accuracy and high variance. Set max_depth or min_samples_leaf on validation.
• Treating category codes as numbers. Encoding colors as 1, 2, 3 lets a threshold group 1 with 2 but never 1 with 3. One-hot encode, or use a library with native categorical support.
• Reading feature importance as causation. Correlated features split importance between them unpredictably.
• log of 0 in your own entropy. 0 · log 0 is defined as 0; guard pure nodes explicitly as the lab does.

Derivation: the variance of an average of correlated trees

Let T₁, …, T_B be the predictions of B trees at a point, each with variance σ² and pairwise correlation ρ, so Cov(T_b, T_c) = ρσ² for b ≠ c. The variance of a sum is the sum of all entries of the covariance matrix: B diagonal terms σ² and B(B − 1) off-diagonal terms ρσ².

Beyond about 100 trees, adding more barely helps; the floor ρσ² does not move. Lowering ρ is the only way to lower the floor, and that is what the random feature subset does: trees that may not use the same dominant feature at the root are less alike. Adding trees never increases the variance, which is why a forest does not overfit by having too many trees.

Bootstrap arithmetic

A bootstrap sample draws m examples with replacement. A given example is missed by all m draws with probability (1 − 1/m)^m, which tends to e⁻¹ = 0.368. Each tree sees about 63.2% of the distinct examples (63.24% for m = 569). The remaining 36.8% are that tree's out-of-bag examples, a free validation set for that tree.

Derivation: boosting as gradient descent on predictions

Treat the ensemble's predictions F_i = F(x_i) on the training set as the parameters, and minimize Σ_iL(y_i, F_i). A gradient step would move each F_i by −ν ∂L/∂F_i. A tree cannot move points independently, so fit a small regression tree h to the negative gradients and update F ← F + νh, which also generalizes the step to new x. For squared error L = ½(y − F)², −∂L/∂F = y − F, the residual. For log loss with F as the log-odds, −∂L/∂F = y − σ(F): the label minus the predicted probability.

Worked example by hand

x = (1, 2, 3, 4), y = (3, 5, 9, 11), stumps, learning rate ν = 0.5.

1. F₀ = mean(y) = 7 everywhere. MSE = (16 + 4 + 4 + 16)/4 = 10.
2. Residuals (−4, −2, 2, 4). Best stump: x ≤ 2.5, leaf values −3 and +3. F₁ = 7 + 0.5 · (−3, −3, 3, 3) = (5.5, 5.5, 8.5, 8.5). MSE = (6.25 + 0.25 + 0.25 + 6.25)/4 = 3.25.
3. Residuals (−2.5, −0.5, 0.5, 2.5). Same split, leaves −1.5 and +1.5. F₂ = (4.75, 4.75, 9.25, 9.25). MSE = 1.5625.

The pattern: the within-group part of the error (1.0) cannot be reduced by this split, and each round removes half of the between-group part (9). MSE after t rounds of this split is 1 + 9 · 0.25^t: 3.25, then 1.5625. A third round finds that a different split (x ≤ 1.5) now helps more. A smaller ν needs more trees but averages over more splits, which usually generalizes better.

For classification, start from the log-odds of the positive rate. For breast cancer with 212 malignant out of 569, F₀ = ln(212/357) = −0.521.

Common mistakes

• Too many boosting rounds without early stopping. Unlike a forest, boosting keeps fitting residuals and eventually fits noise. Monitor validation loss and stop at its minimum.
• Deep trees in boosting. Depth 10 trees fit the residuals in one round and leave nothing for the ensemble to average. Use depth 3 to 6.
• A forest considering every feature at every split. That is plain bagging; ρ stays high. Keep the default √n features for classification.
• Comparing ensembles on training AUC. Both can reach 1.0 on training data. Compare on validation.

Derivation

K-means minimizes one cost over two sets of variables: the assignments c⁽¹⁾…c^(m) and the centroids μ₁…μ_K.

Assignment step. Hold μ fixed. J is a sum of m separate terms and c⁽ⁱ⁾ appears only in term i. Choosing c⁽ⁱ⁾ = argmin_k ‖x⁽ⁱ⁾ − μ_k‖² makes each term as small as it can be given μ. The old assignment was one of the candidates, so each term is less than or equal to its old value, and so is the sum.

Update step. Hold c fixed. Now J splits into K separate problems, one per cluster: minimize f(μ_k) = Σ_{i in cluster k} ‖x⁽ⁱ⁾ − μ_k‖². Take the gradient: ∂f/∂μ_k = −2 Σ (x⁽ⁱ⁾ − μ_k) = −2(Σ x⁽ⁱ⁾ − n_kμ_k). Setting it to zero gives μ_k = (1/n_k) Σ x⁽ⁱ⁾, the mean. f is a sum of convex quadratics, so this stationary point is the global minimum, and the old centroid cannot have done better.

Convergence. J never increases and J ≥ 0. There are at most K^m possible assignments, and each centroid set is determined by its assignment, so the algorithm can visit only finitely many states. A sequence that never increases through a finite set of values must stop changing. It stops at a point where neither step can improve J alone: a local minimum of this coordinate descent, not necessarily the global one.

Worked example by hand

Six points on a line, x = 1, 2, 3, 7, 8, 12, with K = 2 and starting centroids μ = (1, 4).

J falls at every half step: 15.17, 6.92, 3.92, 2.67. Point 3 switched clusters in the second assignment because, once the right centroid moved to 7.5, it was 4.5 away from it and only 1.5 away from the left centroid. Of the five ways to cut six sorted points into two contiguous groups, the cut after 3 has the lowest distortion (2.6667; the next best, after 2, gives 6.9167), so here the local minimum is also the global one.

Common mistakes

• Using distance instead of squared distance in the update. The mean minimizes squared distance; the point minimizing summed absolute distance is the median (that is K-medians). Symptom: your "proof" of monotone decrease fails in tests. Fix: keep both steps on ‖·‖².
• Empty clusters. A centroid that wins no points makes the mean 0/0 and fills the array with NaN. Fix: keep the old centroid, or re-seed it at the point farthest from its centroid.
• Checking convergence on J with a tight tolerance. Floating-point noise can make J wobble in the last digit. Fix: stop when assignments stop changing, or compare centroids with np.allclose.
• Unscaled features. A feature measured in thousands dominates the distance. Symptom: clusters are slices along one axis. Fix: standardize first.

Check yourself

Start the same six points from μ = (1, 2). Which clustering do you reach?

Derivation

k-means++ chooses the first centroid uniformly at random from the data. For every later centroid it computes, for each point x, D(x) = distance from x to the nearest centroid chosen so far, and samples the next centroid from the data with probability

Points far from every existing centroid are likely, but not certain, to be chosen. Picking the single farthest point instead (a deterministic rule) would chase outliers. Arthur and Vassilvitskii proved that the expected distortion right after k-means++ seeding, before any Lloyd iteration, is at most 8(ln K + 2) times the optimal distortion. Plain random initialization has no such bound.

Worked example by hand

Points 0, 1, 2, 10, 11, 12 on a line, K = 2, and suppose the first centroid is 0. The squared distances are 0, 1, 4, 100, 121, 144, summing to 370.

The second centroid lands in the right-hand group with probability 365/370 = 0.9865. With uniform random seeding the chance that both centroids come from the same group is 2 · (3/6) · (2/5) = 0.4. If K were 3 and the centroids so far were 0 and 12, the distances squared would be 0, 1, 4, 4, 1, 0 (sum 10), so 1 and 11 each get 0.1 and 2 and 10 each get 0.4.

Choosing K: why distortion alone fails

For these six points the best possible distortion for K = 1…6 is 25.6667, 0.6667, 0.4167, 0.1667, 0.0833, 0. It always decreases, because with one more centroid you could keep the old solution and move the extra centroid onto any point, which cannot increase J. So "minimize J over K" always answers K = m. The elbow is the K after which the decrease becomes small: here the drop from 25.67 to 0.67 is huge and every later drop is tiny, so K = 2. On real data the curve is usually smooth and the elbow is a matter of opinion.

The silhouette is a second hint that does not automatically favour large K. For point i, a_i is its mean distance to the other members of its cluster and b_i its mean distance to the nearest other cluster; s_i = (b_i − a_i) / max(a_i, b_i). For the point 3 in the clustering {1, 2, 3} {7, 8, 12}: a = (2 + 1)/2 = 1.5, b = (4 + 5 + 9)/3 = 6, s = 4.5/6 = 0.75. Values near 1 mean well separated, near 0 on a boundary, negative probably misassigned.

Common mistakes

• Sampling with D instead of D². The squared weighting is what gives the log K guarantee. Symptom: seeds still bunch up on dense groups. Fix: square the distance.
• Distance to the first centroid only. D(x) is to the nearest chosen centroid. Using only the first one keeps picking from the same far group.
• Comparing distortion across K from single runs. A bad local minimum at K = 4 can be worse than K = 3. Fix: use the best of many restarts per K before plotting.
• Choosing K from the plot when the use case decides. If clusters become product sizes or sales regions, the cost of an extra cluster is a business number. Use it.

Check yourself

In the table, why is P(0) exactly 0 and what does that guarantee?

Derivation: the maximum-likelihood μ and σ²

Given m values x⁽¹⁾…x^(m) of one feature, choose μ and σ² to maximize the probability density of the data. Independence of examples turns the joint density into a product; the log turns it into a sum:

∂ℓ/∂μ = Σ (x⁽ⁱ⁾ − μ)/σ² = 0 gives Σ x⁽ⁱ⁾ = mμ, so μ = (1/m) Σ x⁽ⁱ⁾.

∂ℓ/∂σ² = −m/(2σ²) + Σ (x⁽ⁱ⁾ − μ)² / (2σ⁴) = 0. Multiply by 2σ⁴: −mσ² + Σ (x⁽ⁱ⁾ − μ)² = 0, so σ² = (1/m) Σ (x⁽ⁱ⁾ − μ)². This is the 1/m (population) variance, np.var with its default ddof=0. The 1/(m−1) version is unbiased; for anomaly detection with hundreds of examples the difference is negligible.

Why multiply

If features are independent, P(x₁ and x₂) = P(x₁) · P(x₂), and the same holds for densities. The product of per-feature Gaussians is exactly a multivariate Gaussian whose covariance matrix is diagonal. In practice features are rarely independent, but the model still works when each anomaly is unusual in at least one feature.

Worked example by hand

Throughput readings 12.3, 11.8, 13.1, 12.6, 12.0, 12.9, 11.5. Sum 86.2, so μ = 12.3143. Squared deviations sum to 2.0686, so σ² = 0.2955 and σ = 0.5436. For x = 14.0, z = (14.0 − 12.3143)/0.5436 = 3.10 and

The density at the mean is 0.7339, which is above 0.5 and could exceed 1 for a narrower Gaussian. Densities are not probabilities; only their ordering against ε matters.

The multivariate Gaussian

Take two standardized features with correlation 0.8: Σ = [[1, 0.8], [0.8, 1]], |Σ| = 0.36, Σ⁻¹ = [[2.778, −2.222], [−2.222, 2.778]]. For x = (1, −1) the quadratic form is 2.778 + 2.222 + 2.222 + 2.778 = 10, so p = 0.2653 · e⁻⁵ = 0.00179. For x = (1, 1) the form is 1.111 and p = 0.1522. The diagonal model gives both points the same density, φ(1)·φ(1) = 0.0585, because it cannot see that (1, −1) breaks the correlation. The full model separates them by a factor of 85. The engineered-feature trick in the lecture (CPU ÷ traffic) is a manual way to get the same effect with the cheaper model.

Common mistakes

• Fitting on data that contains the anomalies. They inflate σ² and hide themselves. Fit on normal examples only.
• Underflow. A product of 50 small densities becomes 0.0. Fix: sum log densities and compare with ln ε.
• Singular covariance. With m < n, or duplicated features, Σ is not invertible. Symptom: LinAlgError or huge densities. Fix: drop redundant features, add a small multiple of the identity, or keep the diagonal model.
• Choosing ε on the test set. Pick it on validation data with F1, then report test metrics once.

Check yourself

Why does the full model need m clearly larger than n, while the diagonal one does not?

Derivation

Center the data so every feature has mean zero, and let Σ = (1/m) Xᵀ X be the n × n covariance matrix. Project each point onto a unit vector u: its score is z⁽ⁱ⁾ = uᵀ x⁽ⁱ⁾. The scores have mean zero and variance

Maximize uᵀΣu subject to uᵀu = 1 (without the constraint you could scale u forever). The Lagrangian is L = uᵀΣu − λ(uᵀu − 1). Its gradient with respect to u is 2Σu − 2λu; setting it to zero gives Σu = λu. So u must be an eigenvector of Σ. Multiplying both sides by uᵀ gives uᵀΣu = λ uᵀu = λ: the projected variance equals the eigenvalue. The best direction is the eigenvector with the largest eigenvalue. The second component maximizes the same quantity with the extra constraint u₂ᵀu₁ = 0, which gives the eigenvector with the second-largest eigenvalue, and so on. Because Σ is symmetric, its eigenvectors are orthogonal and its eigenvalues are real and non-negative.

The same components minimize reconstruction error. A point splits into its projection and a perpendicular residual; by Pythagoras ‖x‖² = ‖projection‖² + ‖residual‖². The left side is fixed, so maximizing projected variance is the same as minimizing mean squared residual, which equals the sum of the discarded eigenvalues.

Worked example by hand

Four centered points: (2, 1), (1, 2), (−2, −1), (−1, −2). Then Σxx = (4+1+4+1)/4 = 2.5, Σyy = 2.5, Σxy = (2+2+2+2)/4 = 2, so Σ = [[2.5, 2], [2, 2.5]]. The characteristic equation (2.5 − λ)² − 4 = 0 gives λ = 4.5 and λ = 0.5, with eigenvectors (1, 1)/√2 and (1, −1)/√2. The first component explains 4.5/5 = 90% of the variance.

Scores on PC1: (2 + 1)/√2 = 2.1213 for the first two points and −2.1213 for the others; their variance is 2.1213² = 4.5, the eigenvalue. Reconstructing from one component gives z · u = (1.5, 1.5) for the first point, residual (0.5, −0.5), squared length 0.5. The mean squared residual over the four points is 0.5, the discarded eigenvalue.

The SVD connection

Write the centered data matrix as X = U S Vᵀ. Then XᵀX = V S Uᵀ U S Vᵀ = V S² Vᵀ, so the columns of V are the eigenvectors of Σ and the eigenvalues are S²/m (or S²/(m−1) for the sample covariance, which is what scikit-learn reports). For the four points the singular values are 4.2426 and 1.4142, and 4.2426²/4 = 4.5, 1.4142²/4 = 0.5. The SVD never forms XᵀX, which squares the condition number, so it is the numerically preferred route. The scores are X V = U S.

Common mistakes

• Forgetting to center. The first "component" then points at the mean. Symptom: PC1 explains nearly all variance and looks like the average row.
• Not scaling mixed units. A feature in dollars beats one in percentages purely by magnitude. Standardize unless the units are shared.
• Reading signs. u and −u are equally valid; two libraries can disagree in sign. Compare |u₁ · u₂|.
• Fitting PCA on train and test together. That leaks test information into features. Fit on train, apply transform to test.

Check yourself

Add a fifth point (0, 0) to the example. What happens to the explained-variance ratio?

Derivation

Write e^(i,j) = w^(j) · x⁽ⁱ⁾ + b^(j) − y^(i,j) for every rated pair. The cost is ½ Σ e² plus the two regularizers. A given w^(j) appears only in the terms of movies that user j rated, and in its own regularizer. By the chain rule, ∂(½e²)/∂w^(j) = e · ∂e/∂w^(j) = e · x⁽ⁱ⁾. Collecting terms:

The two vector gradients are mirror images: the user's update uses the movie vectors as inputs, and the movie's update uses the user vectors as inputs. That symmetry is why the problem is not convex in (w, x) jointly but is a convex ridge regression in either one when the other is held fixed. Alternating least squares exploits that by solving each side in closed form: w^(j) = (X_jᵀX_j + λI)⁻¹ X_jᵀ y_j.

Worked example by hand

One rating y = 4, with w = (1, 0.5), x = (2, 1), b = 0.5, λ = 0.1. Prediction 2 + 0.5 + 0.5 = 3, so e = −1.

• ∂J/∂w = −1 · (2, 1) + 0.1 · (1, 0.5) = (−1.9, −0.95)
• ∂J/∂x = −1 · (1, 0.5) + 0.1 · (2, 1) = (−0.8, −0.4)
• ∂J/∂b = −1

One gradient step with α = 0.1: w = (1.19, 0.595), x = (2.08, 1.04), b = 0.6. New prediction 1.19 · 2.08 + 0.595 · 1.04 + 0.6 = 2.4752 + 0.6188 + 0.6 = 3.694, closer to 4. Note that both w and x moved: one rating teaches both the user and the movie.

The matrix-factorization view

Stack the user vectors as rows of W (n_u × k) and the movie vectors as rows of X (n_m × k). Every prediction at once is the matrix X Wᵀ (movies × users), plus biases. Collaborative filtering says the full ratings matrix is approximately rank k, and it fits the factors only on the observed entries. For MovieLens 100k with k = 20 there are (943 + 1,682) · 20 = 52,500 vector parameters, against 943 · 1,682 = 1,586,126 cells of which 100,000 (6.3%) are observed. Plain SVD cannot be used directly because it needs every cell; filling the missing ones with zeros tells the model that unrated means "rated 0".

Common mistakes

• Summing the loss over all cells. Multiply by the mask or index only observed triples. Symptom: every prediction collapses toward 0.
• Initializing all vectors to zero. Then every gradient for w is a sum of e · 0 = 0 and nothing moves except the biases. Fix: small random values.
• Using torch.randn(...) * 0.1 with requires_grad=True inside. The multiplication makes a non-leaf tensor whose .grad stays None. Fix: wrap in nn.Parameter or call requires_grad_() after scaling.
• Regularizing the bias. Harmless but unnecessary; the lecture's cost leaves b unregularized, as in linear regression.

Check yourself

A movie nobody has rated yet: what does gradient descent do to its x?

Derivation: why a new user predicts zero

A user with no ratings contributes no error terms. Her gradient is only λw (and 0 for b if b is unregularized). Gradient descent gives w ← (1 − αλ)w, which decays to zero, and her predictions w · x + b become b, which also stays at its initial 0. With mean normalization the model predicts w · x + b + μ_i for movie i, so the same zero vector now yields μ_i, the movie's average.

Worked example by hand

Three movies, three existing users and a new user, Eve. Rows are movies, as in the lecture.

Eve now gets a sensible ranking (movies 1 and 3 first) before she has rated anything. Normalizing by movie solves the new-user problem. Normalizing by user (the lab does this) instead helps users with unusual rating scales, a harsh critic whose 3 means "good", but gives a new movie a default of each user's own mean. Many systems subtract a global mean plus learned user and item biases, which handles both.

Mean normalization also makes regularization honest. The penalty λ‖w‖² pulls w toward zero, so zero should mean "average opinion". Without normalization, zero means "rates everything 0 stars", a strange default to shrink toward.

Derivation: the binary version

For clicks y ∈ {0, 1}, predict p = σ(z) with z = w · x + b, and use log loss L = −y ln p − (1 − y) ln(1 − p). With σ′(z) = σ(z)(1 − σ(z)):

So the gradients are the same as in the squared-error case with e replaced by p − y: ∂L/∂w = (p − y) x, ∂L/∂x = (p − y) w. Example: z = 0.5 gives p = 0.6225. If the user clicked, L = −ln 0.6225 = 0.4741 and ∂L/∂z = −0.3775; if not, L = −ln 0.3775 = 0.9741 and ∂L/∂z = 0.6225. At z = 2 a non-click costs −ln(1 − 0.8808) = 2.1269: confident mistakes are expensive.

Common mistakes

• Computing the mean over all cells. Unrated zeros drag the mean down. Divide by the number of observed ratings, not the number of users.
• Forgetting to add the mean back. Predictions come out centered near 0, and RMSE looks terrible.
• A movie with no ratings. Its mean is 0/0. Fall back to the global mean.
• Treating unobserved as negative in implicit data. Not clicking may mean "never saw it". Sample a limited number of negatives, ideally from items that were shown, and weight them lower than positives.

Check yourself

Eve rates movie 2 with 5 stars. With w still near zero, which sign will the first gradient step give her bias, and why?

Derivation

Let f_u be the user tower and f_m the item tower, both small neural networks ending in a linear layer of width d. The prediction is ŷ = f_u(user features) · f_m(item features). With squared error L = ½(ŷ − y)², write v_u and v_m for the tower outputs. Then ∂L/∂v_u = (ŷ − y) v_m and ∂L/∂v_m = (ŷ − y) v_u, exactly the collaborative-filtering gradients, and backpropagation carries them into each tower's weights. Collaborative filtering is the special case where each tower is a lookup table indexed by ID.

The key structural fact: nothing in f_m depends on the user. So all item vectors can be computed once and stored, and serving one request costs one forward pass of f_u plus a nearest-neighbour search. Ten million items with d = 32 in float32 take 10⁷ · 32 · 4 bytes = 1.28 GB, which fits in memory on one machine.

Dot product versus cosine

The dot product rewards long vectors; the cosine ignores length. Long item vectors often mean "popular", so a raw dot product leans toward popular items. Normalizing both towers' outputs to unit length makes the dot product equal to the cosine.

Worked example by hand

User vector u = (1, 2, 0), ‖u‖ = √5 = 2.2361.

C points exactly along u: cosine 1 regardless of its length. E has a larger dot product than A (6 against 4) only because it is long; by cosine A is much closer (0.7303 against 0.3162). Which ranking you want is a product decision: dot product if magnitude carries useful signal such as quality, cosine if you want pure similarity of taste.

Cold start, concretely

A movie released today has no ratings, so its collaborative x is noise near zero. Its item tower output depends only on genre, year, cast and description, so it gets a vector in the same space as movies with similar metadata the moment it is added. A new user with only age and country gets a user vector the same way. Hybrid systems concatenate a learned ID embedding with the content features; for a new item the ID embedding starts at zero and the content features carry the prediction until ratings accumulate.

Common mistakes

• Towers with different output widths. The dot product needs equal d. Symptom: a shape error at the final layer.
• A ReLU on the last layer. Non-negative vectors can never have a negative dot product, so the model cannot express dislike. Keep the last layer linear.
• Feature leakage across towers. Putting the item's average rating into the item tower is fine; putting the user's rating of this item anywhere is the label.
• Stale item vectors. After retraining the towers, recompute and re-index every item vector, or old and new vectors live in different spaces.

Check yourself

If you L2-normalize both tower outputs, what range can the prediction take, and what does that imply for a 1 to 5 rating target?

Intuition: why two stages

Suppose the full ranking model costs 1 microsecond per item on one core. Scoring 10 million items is 10⁷ · 10⁻⁶ = 10 seconds per request, against a latency budget of perhaps 100 milliseconds. Retrieval cuts the candidate set to a few hundred with cheap methods (approximate nearest-neighbour search over stored vectors, popularity lists, co-occurrence), and the ranking model spends its budget on those. The final quality is bounded by retrieval recall: an item retrieval misses can never be ranked first. So the first offline measurement is recall@N of the retrieval stage, the fraction of items the user later engaged with that appear among the N candidates.

Derivation: ranking metrics

For a ranked list of length k with relevance labels rel₁…rel_k ∈ {0, 1}:

• precision@k = (number relevant in top k) / k
• recall@k = (number relevant in top k) / (total relevant for this user)

Neither cares about order within the top k. Discounted cumulative gain does: each relevant item contributes 1/log₂(position + 1), so position 1 counts 1, position 2 counts 0.6309, position 3 counts 0.5, position 4 counts 0.4307, position 5 counts 0.3869.

Worked example by hand

Top 5 recommendations, relevance 1, 0, 1, 0, 0; the user has exactly two relevant items in total.

• precision@5 = 2/5 = 0.4; recall@5 = 2/2 = 1.0; precision@1 = 1.
• DCG@5 = 1/1 + 1/2 = 1.5 (positions 1 and 3).
• Ideal order puts both relevant items first: IDCG@5 = 1 + 0.6309 = 1.6309.
• NDCG@5 = 1.5 / 1.6309 = 0.9197.

Swapping the items at positions 2 and 3 would raise NDCG to 1 without changing precision or recall at 5.

What you are optimizing

A model trained on clicks learns P(click | user, item). Ranking by it maximizes expected clicks per impression, which is not the same as satisfaction. Three common gaps: position bias (items shown first get clicked more regardless of quality, so the logs reward whatever the old system ranked high); feedback loops (the model only learns about items it chose to show); and proxy drift (watch time rewards long content, purchases reward expensive items). Practical counters are logging the position and modelling it separately, reserving a small share of traffic for randomized exploration, and evaluating changes with online A/B tests on a long-term metric such as 28-day retention rather than on the training metric alone.

Common mistakes

• Evaluating on a random split of interactions. Future interactions leak into training. Split by time: train on the past, test on the next week.
• Recommending what the user already has. Exclude seen items before computing precision@k, or the metric rewards repeats.
• Comparing NDCG across users with different numbers of relevant items without normalizing. That is what the I in IDCG is for.
• Optimizing ranking while retrieval recall is 40%. Measure the stages separately; fix the weaker one first.

Check yourself

Same list, but the user has four relevant items in total. Which of the numbers above change?

Derivation

The return from time t is G_t = R_t+1 + γR_t+2 + γ²R_t+3 + … Factor out γ from everything after the first term:

If every reward satisfies |R| ≤ R_max, the geometric series bounds the return: |G| ≤ R_max(1 + γ + γ² + …) = R_max/(1 − γ). With γ = 0.9 and R_max = 10 no return can exceed 100, even for an episode that never ends. That finiteness is the mathematical reason for γ < 1 in continuing tasks.

A useful rule of thumb is the effective horizon 1/(1 − γ): about 2 steps for γ = 0.5, 10 for γ = 0.9, 100 for γ = 0.99. Rewards much farther away than that barely affect decisions.

Worked example by hand

A reward of 100 arriving three steps from now (on the fourth reward) is worth 100γ³:

Grid world from the lecture: −0.1 per step and +10 at the goal, γ = 0.9. A path of seven steps followed by the goal on the eighth reward returns

A detour that takes eleven steps before the goal returns 2.4519. Notice that the step penalty contributes little; most of the preference for the short path comes from discounting the goal. The step penalty matters more when γ is close to 1.

Reward design

The agent maximizes the reward you wrote, not the one you meant. Classic failures: a boat-racing agent that circles forever collecting respawning bonus targets instead of finishing; a cleaning robot rewarded for "no visible mess" could learn to cover its camera. Two principles help. Reward outcomes, not methods you guess are useful, because the agent will satisfy the method without the outcome. And if you add shaping rewards to speed up learning, make them a difference of a potential function, F = γΦ(s′) − Φ(s); Ng, Harada and Russell showed that this form leaves the optimal policy unchanged, while arbitrary bonuses can change it.

Common mistakes

• Mixing reward conventions. The lecture writes R(s), a reward for being in a state; many libraries give R(s, a, s′) for the transition. The algorithms are the same, but hand-computed numbers shift by one step. Pick one and stay with it.
• γ = 1 in a task that can loop forever. Returns diverge or become meaningless. Use γ < 1 or a step limit.
• Huge reward scales. Rewards of ±10,000 make value targets enormous and network training unstable. Scale or clip rewards.
• Positive living reward. +0.1 per step makes the agent avoid the goal, since ending the episode stops the income.

Check yourself

With γ = 0.9 and a reward of +1 on every step forever, what is the return?

Derivation

Start from the return recursion G_t = R_t+1 + γG_t+1. Q(s, a) is the return when you take a in s and then act optimally. Acting optimally from s′ means choosing the action with the largest Q there, so the return from s′ onward is max_a′ Q(s′, a′). Substituting gives the Bellman optimality equation. With random dynamics the next state is uncertain, so you average over it:

Value iteration turns the equation into an algorithm: start with Q = 0, compute the right-hand side for every (s, a) using the current table, replace the table, repeat. Each sweep shrinks the largest error by at least a factor γ (the Bellman operator is a γ-contraction in the max norm), so the table converges to the unique solution from any start.

Worked example by hand: γ = 0.5

Cells 1 to 6, R = 100, 0, 0, 0, 0, 40, cells 1 and 6 terminal (Q = R). The best value V(s) = max_a Q(s, a) after each sweep:

Sweep 5 changes nothing. Information travels one cell per sweep from each end. Cell 4 first sees the 40 (via cell 5: 0.5 · 20 = 10), then one sweep later the 100 (via cell 3: 0.5 · 25 = 12.5), and switches direction. The final table:

This confirms the lecture: Q(2, left) = 0 + 0.5 · 100 = 50 and Q(2, right) = 0 + 0.5 · V(3) = 0.5 · 25 = 12.5, and only cell 5, next to the 40, goes right.

Changing γ and adding noise

With γ = 0.9 the Q(s, left) values become 90, 81, 72.9, 65.61 for cells 2 to 5, and Q(5, right) = 0.9 · 40 = 36 < 65.61, so every cell heads for the 100. A patient agent walks farther for the bigger reward.

Now make moves slip: with probability 0.1 the agent goes the opposite way (γ = 0.5). Then Q(2, left) = 0.5 · (0.9 · 100 + 0.1 · V(3)). Iterating to convergence gives Q(2, left) = 46.06, Q(2, right) = 14.56, Q(4, left) = 10.49, Q(4, right) = 9.40, Q(5, right) = 18.52. Every value of the best action drops because some steps are wasted, and cell 4's margin for going left narrows from 2.5 to 1.09.

Common mistakes

• Updating terminal states with the recursion. A terminal has no next state; Q = R there. Bootstrapping past it double-counts the reward.
• Using max over s′ instead of the expectation. With random dynamics, average over where you might land, then maximize over your own next action. Swapping them gives an optimistic, wrong Q.
• In-place versus synchronous sweeps. Updating cells in place (Gauss-Seidel) converges too, often faster, but intermediate numbers differ from the table above. Neither is wrong; just do not compare one against the other step by step.
• Stopping on "policy looks right". The greedy policy can settle before values do. Stop on the max change in Q.

Check yourself

At what γ is cell 4 indifferent between left and right in the deterministic world?

Derivation

Q-learning is a stochastic approximation of value iteration. Value iteration needs the expectation Σ_s′ P(s′|s, a)[R + γ max Q(s′, ·)], which requires the dynamics. One observed transition gives a single sample of that quantity, the target y = R + γ max_a′ Q(s′, a′). The update Q ← Q + α(y − Q) = (1 − α)Q + αy is a running average of samples. With α_n = 1/n on the n-th visit it is exactly the sample mean of the targets seen so far.

Watkins and Dayan proved convergence to the optimal Q with probability 1 under two conditions:

1. Every state-action pair is visited infinitely often.
2. The step sizes for each pair satisfy Σ_n α_n = ∞ and Σ_n α_n² < ∞ (the Robbins-Monro conditions). The first lets the updates travel any distance; the second makes the noise die out.

α_n = 1/n satisfies both. A constant α violates the second: the table keeps fluctuating around Q* with variance proportional to α, which is often what you want when the environment can change. Q-learning is off-policy: the target uses max regardless of which action the agent will actually take, so it learns the optimal Q while behaving exploratorily.

Worked example by hand

On the lab's 4 × 4 grid, α = 0.5, γ = 0.9, table all zeros. In the first episode, the agent wanders and eventually steps down from (2, 3) into the goal:

Every earlier transition in that episode had target 0 + 0.9 · 0 = 0 and changed nothing. In the second episode, suppose the agent reaches (1, 3), steps down to (2, 3), then down to the goal:

• Q((1,3), down) ← 0 + 0.5 · (0 + 0.9 · 5 − 0) = 2.25
• Q((2,3), down) ← 5 + 0.5 · (10 − 5) = 7.5

Value has moved one cell further back. Repeated, Q((2,3), down) approaches 10 and Q((1,3), down) approaches 9, the optimal values.

ε-greedy, exactly

With probability ε choose uniformly among all |A| actions (including the greedy one), otherwise choose greedily. The greedy action's total probability is 1 − ε + ε/|A|. For ε = 0.2 and four actions: 0.85 for the greedy action and 0.05 for each other. To satisfy "visited infinitely often" while ending up greedy, decay ε toward zero slowly (GLIE: greedy in the limit with infinite exploration), for example ε_t = 1/t. A practical schedule multiplies ε by 0.995 per episode; going from 1.0 to 0.05 takes ln 0.05 / ln 0.995 = 598 episodes.

Common mistakes

• Bootstrapping from a terminal state. Use y = R when the episode ended. Using R + γ max Q(s′) adds value from a state that has no future. Symptom: values near the goal exceed the goal reward.
• Ending the episode at a time limit and treating it as terminal. Hitting a 100-step cap is not a real terminal; the state still had a future. Bootstrap there.
• Ties in argmax. np.argmax returns the first maximum, so an all-zero table always picks action 0. Break ties at random or the agent may never try the other actions.
• ε = 0 from the start. As the lecture's demo shows, the agent repeats its first lucky path forever.

Check yourself

In the second episode above, why did Q((1,3), down) get 2.25 and not 0.5 · 0.9 · 10 = 4.5?

Intuition: why naive DQN diverges

Three ingredients together can make value learning diverge, which Sutton and Barto call the deadly triad: function approximation (a network generalizes, so updating one state changes others), bootstrapping (the target contains the network's own prediction), and off-policy data (the replay buffer holds transitions from older policies). In a table, updating Q(s, a) changes only that cell. In a network, the gradient step that raises Q(s, a) also raises Q(s′, ·) for similar states, which raises the target for s, which pushes Q(s, a) up again. That loop can grow without bound.

Derivation: what the target network changes

With a live target the loss is L(θ) = (Q_θ(s, a) − [r + γ max_a′ Q_θ(s′, a′)])². DQN treats the bracket as a constant (torch.no_grad) but it still moves after every step. With a target network θ⁻ held fixed for C steps,

For those C steps this is ordinary supervised regression on fixed labels, which gradient descent handles well. Every C steps the labels jump to the new network's opinion, much like one sweep of value iteration. Soft updates replace the jump by θ⁻ ← τθ + (1 − τ)θ⁻ every step. The old target's weight decays as (1 − τ)ⁿ; with τ = 0.005 it halves after ln 0.5 / ln 0.995 = 138 steps, with τ = 0.001 after 693.

Overestimation bias, with numbers

The max in the target is applied to noisy estimates. Even if every action's estimate is unbiased, E[max_a Q̂(a)] ≥ max_a E[Q̂(a)]. Example: ten actions whose true values are all 0, each estimated with independent N(0, 1) noise. The expected maximum of ten standard normals is 1.5388, so the target is inflated by about 1.54 although every action is worth 0. With two actions it is 1/√π = 0.5642. The bias grows with the number of actions and the noise, and bootstrapping propagates it backward through states.

Double DQN

The bias comes from using the same noisy numbers to choose the best action and to value it. Double Q-learning decouples them: one estimator selects, an independent one evaluates. Double DQN uses the networks DQN already has:

with torch.no_grad():
    a2 = net(s2).argmax(1, keepdim=True)              # select with the online network
    y = r + gamma * target_net(s2).gather(1, a2).squeeze(1) * (1 - done)   # evaluate with the target network

If the online network's noise makes a bad action look best, the target network's independent noise is unlikely to agree, so the inflated value is not used. It is one changed line and on Atari reduced overestimation substantially and improved scores in most games.

Common mistakes

• Forgetting (1 − done). The agent bootstraps from the state after a crash. Symptom: Q values far above any achievable return.
• Gradients through the target. Without no_grad or detach, the loss also moves the target, and learning becomes erratic.
• Replay buffer too small. A buffer of a few thousand transitions is nearly on-policy and correlated, so the main stabilizer is lost. Typical sizes are 10⁵ to 10⁶.
• Unclipped rewards or huge losses. One −1,000 reward produces a giant gradient. Clip rewards or use the Huber loss (smooth_l1_loss).
• Evaluating with ε still at 0.1. Report the greedy policy's return separately from training returns.

Check yourself

If the target network were refreshed every step (C = 1), what would it be equivalent to?

Decision table

Worked example

Workload: extract order fields as JSON from 50,000 support emails a day. Each email is 300 tokens and each answer 150 tokens. The prices below are assumptions chosen to make the arithmetic concrete; substitute your provider's numbers.

• Prompt with a frontier API at $3 per million input tokens and $15 per million output tokens. Instructions and five worked examples add 1,500 tokens, so each request sends 1,800 input tokens. Cost per request = 1,800 · 3·10⁻⁶ + 150 · 15·10⁻⁶ = $0.0054 + $0.00225 = $0.00765. Per day: $382.50. Per 30 days: $11,475.
• RAG on top of that, with three retrieved chunks of 400 tokens: 3,000 input tokens, $0.01125 per request, $562.50 per day, $16,875 per 30 days.
• Fine-tuned 1.5B model on one rented GPU at an assumed $1.20 per hour, running all day: $28.80 per day, $864 per 30 days. The load is 50,000 / 86,400 = 0.58 requests per second, which one GPU serves easily.

Break-even: the GPU costs a fixed $28.80 a day, the prompt option $0.00765 a request, so fine-tuning is cheaper above 28.80 / 0.00765 ≈ 3,765 requests a day, before counting the one-off cost of building the dataset.

Latency, with assumed speeds (API: prefill 5,000 tokens/s, decode 80 tokens/s; small self-hosted model: prefill 20,000 tokens/s, decode 150 tokens/s):

The decode term dominates all three; shorter prompts help less than a faster model. The fine-tuned model's input is 300 tokens plus about 30 template tokens because the instructions now live in the weights.

Combining them

The options stack. A fine-tuned model can still receive retrieved documents: fine-tune for the output format and the habit of citing the retrieved text, retrieve for the facts. Teaching facts by fine-tuning is the one combination to avoid.

Common mistakes

• Fine-tuning before measuring the prompt baseline. Symptom: no way to say whether the fine-tune helped. Fix: build the gold set first and score the best prompt on it.
• Training prices or policies into the weights. Symptom: confident, outdated answers months later. Fix: retrieve anything that changes.
• Comparing cost per request without volume. Below the break-even volume an idle GPU is the expensive option. Fix: compute fixed and per-request costs separately.
• Ignoring the data cost. Five hundred reviewed examples can take more hours than the training run. Budget it.

Check yourself

At 2,000 requests a day, which option is cheaper in the example?

Derivation: parameters of one layer

Write d for the hidden size, d_ff for the intermediate size, h for the head dimension and n_kv for the number of key/value heads, so the key/value width is kv = n_kv·h. With grouped-query attention several query heads share one key/value head, so kv is smaller than d. A layer holds:

• q_proj d×d, o_proj d×d, k_proj d×kv, v_proj d×kv
• gate_proj d×d_ff, up_proj d×d_ff, down_proj d_ff×d (the SwiGLU block has three matrices, not two)
• two RMSNorm weight vectors of length d, and in Qwen2.5 biases on q, k and v

Worked example: Qwen2.5-0.5B

d = 896, L = 24, d_ff = 4,864, 14 query heads and 2 KV heads of dimension 64, so kv = 128, vocabulary V = 151,936.

That matches the published 0.49 B. The feed-forward block holds 88% of each layer, and the embedding holds 27.6% of the whole model; in small models with large vocabularies the embedding is not negligible. Untied, the model would have 630,167,424 parameters.

Attention FLOPs and the KV cache

For one new token at context length n, each linear map of shape a×b costs 2ab FLOPs (a multiply and an add per weight). Scores QKᵀ cost 2·n·d_q per layer and the weighted sum of values another 2·n·d_q, where d_q = 14·64 = 896 is the total query width.

During generation the keys and values of earlier tokens are cached. Per token that is 2 (K and V) · L · kv · bytes per number.

Without grouped-query attention Llama-3.1-8B would cache kv = 4,096 per layer, four times as much, 512 KiB per token.

Common mistakes

• Counting two feed-forward matrices. SwiGLU models have three; the count comes out a third too low.
• Using d for k_proj and v_proj. With GQA they map to kv, not d. For Qwen2.5-0.5B that overstates each by 7×.
• Thinking GQA cuts attention FLOPs. Every query head still attends over n keys; GQA cuts KV-cache memory and k/v projection cost, not the score computation.
• Double-counting tied embeddings. Check tie_word_embeddings in config.json before adding V·d twice.

Check yourself

Llama-3.1-8B: d = 4,096, L = 32, d_ff = 14,336, kv = 1,024, V = 128,256, no biases, untied head. Does the formula give 8.03 B?

Derivation

At position t the model outputs a score vector z of length V. Softmax turns it into probabilities p_j = e^z_j / Σ_k e^z_k. The loss for the true next token y is its negative log-probability:

The gradient follows by differentiating each term: ∂(−z_y)/∂z_j = −1[j = y] and ∂ log Σ e^z_k/∂z_j = e^z_j/Σ e^z_k = p_j. Example: z = (2.0, 1.0, 0.1), y = 0. Then p = (0.659, 0.242, 0.099), ℓ = 0.417 and the gradient is (−0.341, 0.242, 0.099).

The sequence loss averages over the scored positions S: L = (1/|S|) Σ_t∈S ℓ_t. Perplexity is e^L, the geometric mean of 1/p_y. A model that knows nothing assigns 1/V to every token, so its loss is log V: for Qwen's V = 151,936 that is 11.93. A freshly initialised model should start near that value; a pretrained one on your data typically starts between 1 and 3.

Worked example: label masking

A rendered conversation, simplified to one token per word:

Labels equal the input ids, with −100 wherever the loss must ignore the token; PyTorch's cross-entropy skips −100 by default (ignore_index=-100). The model shifts internally: logits at position t are scored against the label at t+1. Four tokens are scored. If the model gives them probabilities 0.5, 0.8, 0.9, 0.95, the losses are 0.6931, 0.2231, 0.1054, 0.0513, the mean is 0.2682 and the perplexity 1.31.

Without the mask, suppose the four question tokens get probabilities 0.02, 0.1, 0.05, 0.3 (losses 3.912, 2.303, 2.996, 1.204). Averaging all eight gives 1.436: the loss is now dominated by predicting the user's words, which the model cannot know and should not learn to produce.

The <|im_end|> after the answer must keep its label. It is how the model learns to stop.

Common mistakes

• Shifting labels yourself. Hugging Face causal LMs shift inside the forward pass. Shifting again trains the model to predict two tokens ahead; loss plateaus high.
• Masking the end-of-turn token. Symptom: the model never stops generating. Fix: score the closing token of each assistant turn.
• Pad token equal to end-of-sequence, masked as padding. Every real EOS is then masked too. Use a distinct pad token or mask by attention mask, not by token id.
• Comparing loss across tokenizers. Per-token loss depends on how many tokens a text becomes. Compare models with the same tokenizer, or use bits per character.
• Averaging per sequence instead of per token. Short answers then weigh as much as long ones. Know which one your trainer does.

Check yourself

Eval loss falls from 1.2 to 0.9. By what factor did perplexity fall?

Near-duplicates with Jaccard similarity

Exact matching after normalization catches copies that differ in case and punctuation. Reworded copies need a similarity measure. Split each text into word 3-grams (shingles) and compute the Jaccard similarity J(A, B) = |A ∩ B| / |A ∪ B|.

Worked example. "where is my order 1832 it has not arrived yet" and "where is my order 1832 it still has not arrived" have 10 words each, so 8 shingles each. Shared: "where is my", "is my order", "my order 1832", "order 1832 it", "has not arrived": 5. Union: 8 + 8 − 5 = 11. J = 5/11 = 0.45. At a threshold of 0.8 these are kept as distinct; at 0.4 they would be merged. MinHash estimates J without comparing every pair: the probability that two sets share the same minimum hash value equals J, so the fraction of agreeing values over 128 hash functions estimates it.

Packing and padding

Eight rows of 120, 340, 80, 610, 200, 450, 90 and 300 tokens hold 2,190 real tokens.

• Padded to the longest row in the batch: 8 · 610 = 4,880 slots, 55.1% of them padding.
• Packed end to end into 1,024-token sequences: 3 sequences, 3,072 slots, 28.7% padding.

Packing saves compute but creates a trap: if attention is not blocked at row boundaries, tokens of one example attend to the previous, unrelated example. Correct packing resets position ids at each boundary and uses a block-diagonal mask (variable-length attention kernels do this). TRL's packing does it when the attention implementation supports it; check before turning packing on.

How large must the gold set be?

A gold-set accuracy p measured on n rows has standard error √(p(1−p)/n). At p = 0.8 and n = 50 the 95% half-width is 1.96 · √(0.16/50) = 0.111, so "80%" means somewhere between 69% and 91%. Fifty rows tell you whether the model works at all and show its failure modes; to resolve a 5-point improvement you need hundreds of rows or a paired test (Lecture 3.3).

Decontamination beyond exact match

Exact normalized matching misses paraphrases. A stricter check flags any training row that shares a long n-gram (13 words was used for GPT-3's benchmark checks) with a gold question or answer. For a few hundred gold rows, an n-gram set lookup over the training set takes seconds.

How much data

For format and behavior, 500 to a few thousand reviewed examples is typical; LIMA used 1,000. A useful test: train on 25%, 50% and 100% of the data and plot the gold metric. If the curve is still rising at 100%, more data helps; if it is flat from 50%, spend the effort on quality.

Common mistakes

• Splitting before deduplicating. Copies land on both sides and eval loss looks too good. Dedupe first, then split.
• Deduplicating on the whole row. The same question with two answers survives and teaches inconsistency. Key on the user turn, then decide which answer to keep.
• Synthetic data without a checker. The generator's mistakes become the model's habits. Keep only rows a program or a person has accepted.
• Packing with cross-example attention. Symptom: answers that drift into content from other rows. Fix: boundary-aware masks or no packing.

Check yourself

The lab holds out 5% of 84 rows. How many evaluation rows is that, and what does it imply for reading eval loss?

Derivation: 16 bytes per parameter

Mixed-precision AdamW keeps, for every trainable parameter:

Why keep an fp32 copy? bf16 has 8 significant bits. Near 0.05 the spacing between bf16 numbers is 2⁻¹² ≈ 0.000244. A full fine-tuning update of lr · g = 10⁻⁵ · 0.1 = 10⁻⁶ is far below half that spacing, so adding it in bf16 rounds back to the old weight and the model never learns. The fp32 copy has spacing about 3.7·10⁻⁹ near 0.05 and accumulates the small updates; the bf16 weights are re-derived from it after each step.

8-bit Adam stores m and v in one byte each, giving 2 + 2 + 4 + 2 = 10 bytes per parameter: 15.4 GB for the same model.

Activations

The backward pass needs intermediate results from the forward pass. For batch b, sequence length s and hidden size d, each stored tensor of width w costs b·s·w·2 bytes in bf16.

• The SwiGLU block alone stores gate, up and their product at width d_ff. Qwen2.5-1.5B (d_ff = 8,960), b = 4, s = 1,024: 4·1,024·8,960·2 = 73.4 MB each, × 3 × 28 layers = 6.17 GB, before attention and norms.
• With gradient checkpointing only each layer's input is kept: 28 · 4·1,024·1,536·2 = 0.35 GB, and the rest is recomputed during backward (about one extra forward pass).
• The logits are the surprise. b·s·V scores in fp32 = 4·1,024·151,936·4 = 2.49 GB, and the softmax gradient needs as much again. Large-vocabulary models often run out of memory at the loss, not in the layers.

Worked example

Can you fully fine-tune Qwen2.5-0.5B on a 16 GB card? Parameters 0.494 B · 16 = 7.90 GB. Checkpointed activations at b = 4, s = 1,024: 24 · 4·1,024·896·2 = 0.18 GB. Logits and their gradient: about 5.0 GB. Total about 13 GB plus framework overhead: it fits, barely. The 1.5B model at 24.64 GB does not, which is why the next lecture exists.

Common mistakes

• Budgeting only the weights. "The model is 3 GB in bf16, so it trains on 8 GB" is off by a factor of eight.
• Pure bf16 training without a master copy. Symptom: loss stalls after the first few hundred steps as updates round away. Fix: mixed precision (bf16=True in the trainer keeps fp32 master weights).
• Raising batch size to fix out-of-memory. It makes activations larger. Lower per-device batch, raise gradient accumulation.
• Forgetting the logits. Out-of-memory at the loss line with long sequences. Fix: shorter max length, smaller micro-batch, or a fused/chunked cross-entropy.

Check yourself

How much optimizer and weight memory does full fine-tuning of Llama-3.1-8B need with 8-bit Adam?

Derivation: the gradients

For one adapted layer, h = Wx + s·BAx with s = α/r, A of shape r×d_in, B of shape d_out×r and W frozen. Let g = ∂L/∂h. By the chain rule, with u = Ax:

At initialisation B = 0, so ∂L/∂A = 0 and only B moves on the first step; ∂L/∂B is nonzero because A is random. From the second step both move. If both started at zero, both gradients would be zero forever. If both started random, BA ≠ 0 and the model would start from a perturbed base. Zero B with random A is the one choice that starts exactly at the base model and still learns.

Worked example: one 4096×4096 matrix

Full matrix: 4,096² = 16,777,216 parameters. LoRA with r = 16: A has 16·4,096 and B has 4,096·16, together 131,072, which is 0.78%. In general the fraction for a square d×d matrix is 2r/d.

For Qwen2.5-0.5B with r = 8 on all seven maps: per layer 8·[2(896+896) + 2(896+128) + 2(896+4,864) + (4,864+896)] = 8·22,912 = 183,296; × 24 layers = 4,399,104 parameters, an adapter file of 8.8 MB in bf16.

Why the α/r scale, and rank-stabilised LoRA

The adapter's output on one coordinate is s · Σ_k=1..r B_ik(Ax)_k, a sum of r terms. If those terms are roughly independent with similar size, the sum's standard deviation grows like √r. With s = α/r and α fixed, the output then scales like α/√r: doubling the rank shrinks the update, and high ranks learn more slowly at the same learning rate. Rank-stabilised LoRA (Kalajdzievski, 2023) uses s = α/√r, which keeps the output size independent of r. In PEFT it is use_rslora=True.

The common convention α = 2r fixes s = 2 for every rank, which sidesteps the shrinkage; when you sweep r with α fixed, expect the higher ranks to look worse unless you also raise the learning rate or switch to rsLoRA.

Compute, not only memory

A training step normally costs about 6N FLOPs per token: 2N forward, 2N for gradients with respect to activations, 2N for gradients with respect to weights. Frozen weights skip the last term, so LoRA costs about 4N. For 2.4 M training tokens on a 0.494 B model that is 4.7·10¹⁵ instead of 7.1·10¹⁵ FLOPs.

Merging

W' = W + s·BA is exact in real arithmetic: W'x = Wx + s·BAx for every x. The merged model has the base model's shapes and speed.

Common mistakes

• Changing r and keeping α. The effective scale changes with it; results confound rank with step size.
• Full fine-tuning learning rate on an adapter. 1e-5 barely moves a zero-initialised B. Start near 2e-4.
• Targeting only q_proj and v_proj. On Llama-3.1-8B at r = 16 that is 6.8 M parameters against 42 M for all seven; quality drops on harder tasks.
• Loading an adapter on a different base. Another fine-tune of the same base has identical shapes, so the adapter loads without an error and the outputs are quietly wrong. Record the exact base model id with the adapter.

Check yourself

After one optimizer step from initialisation, which of A and B has changed?

Intuition

Trained weights are close to normally distributed. A 4-bit code has 16 values. Uniform spacing wastes codes in the sparse tails; NF4 places its 16 levels at quantiles of a standard normal, so each level is used about equally often. Each block of 64 weights is divided by its largest absolute value (absmax) so it fits in [−1, 1], and the block's absmax is stored as a scale.

The 16 NF4 levels

−1, −0.6962, −0.5251, −0.3949, −0.2844, −0.1848, −0.0910, 0, 0.0796, 0.1609, 0.2461, 0.3379, 0.4407, 0.5626, 0.7230, 1. The set is asymmetric (8 positive, 7 negative and an exact zero) so that zero is representable.

Worked example by hand

Quantize the block (0.010, −0.022, 0.035, −0.004).

1. absmax = 0.035. Normalized: (0.2857, −0.6286, 1.0, −0.1143).
2. Nearest levels: 0.2461 (index 10), −0.6962 (index 1), 1.0 (index 15), −0.0910 (index 6). Store the four 4-bit indices.
3. Dequantize by multiplying back by 0.035: (0.00861, −0.02437, 0.035, −0.00319).
4. Errors: (−0.00139, −0.00237, 0, +0.00081).

On simulated Gaussian weights (σ = 0.02, blocks of 64) NF4's root-mean-square error is 0.092σ, against 0.101σ for 16 evenly spaced levels over the same range.

Derivation: bits per parameter

Each block of 64 stores one fp32 scale, 32 bits shared by 64 weights:

Double quantization quantizes the scales themselves to 8 bits in groups of 256, with one fp32 scale per group:

On a 65 B model the saving is 0.373 · 65·10⁹ / 8 = 3.03 GB, the figure in the QLoRA paper. Llama-3.1-8B's base at 4.127 bits is 4.14 GB, against 16.06 GB in bf16.

What actually happens in a forward pass

The 4-bit weights are never multiplied directly. For each matrix, the kernel dequantizes blocks to the compute dtype (bf16), multiplies, and discards the result. Gradients flow through the dequantized weights to the input (needed for earlier adapters) but are never applied to the 4-bit storage. The extra dequantization is why steps are slower.

DoRA in one line

DoRA writes the adapted weight as W' = m ⊙ (W + BA) / ‖W + BA‖_col, where the norm is taken per column and m is a trainable vector of column magnitudes initialised to ‖W‖_col. LoRA then changes direction and m changes length separately.

Common mistakes

• Compute dtype left at fp16 or fp32. fp16 can overflow on some layers, fp32 is slow. Set bnb_4bit_compute_dtype to bfloat16 on hardware that supports it.
• Skipping prepare_model_for_kbit_training. Norms stay in low precision and training is unstable.
• Expecting bitsandbytes on Apple Silicon. 4-bit training needs CUDA; on a Mac use bf16 LoRA on a smaller model.
• Merging into the original bf16 base. The adapter was trained against the dequantized NF4 weights, not the original ones. Merge into the dequantized weights (Lecture 3.4).

Check yourself

Without double quantization, what fraction of the 4-bit model's memory is spent on scales?

Gradient accumulation

Run k micro-batches forward and backward, add their gradients, then take one optimizer step. The step sees the same gradient as one batch k times larger, at the memory cost of one micro-batch.

Worked example: 4,000 training rows, batch 4, accumulation 4, one GPU: effective batch 16, ⌈4,000/16⌉ = 250 steps per epoch, 500 steps for two epochs. With warmup_ratio=0.03 the trainer warms up for ⌈0.03 · 500⌉ = 15 steps.

Normalization across micro-batches

The loss should be the mean over all scored tokens in the effective batch. Suppose micro-batch 1 has 10 scored tokens with mean loss 2.0 and micro-batch 2 has 90 with mean 1.0. Averaging the two means gives 1.5; the token mean is (20 + 90)/100 = 1.1. Averaging means overweights the tokens in short micro-batches. Recent versions of Hugging Face Transformers normalize by the total token count across accumulation steps; older versions did not, which made accumulation and large batches give different results.

Derivation: cosine with warmup

With peak rate η, warmup W steps and total T steps:

At t = W the cosine is cos 0 = 1 and the rate is η; at t = T it is cos π = −1 and the rate is 0. Halfway through the decay the rate is η/2.

Worked example

η = 2·10⁻⁴, W = 15, T = 500.

Gradient clipping

With max norm c, if ‖g‖ > c the whole gradient is rescaled: g ← g · c/‖g‖. A gradient of norm 2.5 with c = 1.0 is multiplied by 0.4. Direction is kept, length capped. In a healthy LoRA run the norm sits below c after warmup; frequent clipping means the rate is too high.

Common mistakes

• Warmup in steps copied from a bigger run. 100 warmup steps in a 200-step run spends half of training ramping up. Use a ratio.
• Changing accumulation without changing the step count expectation. Doubling accumulation halves the number of optimizer steps per epoch, so checkpoints every 100 steps now come half as often.
• Scheduler stepped per micro-batch. In a hand-written loop the schedule ends k times too early. Step the scheduler with the optimizer.
• Comparing runs with different effective batch at the same rate. Larger batches tolerate higher rates; sweep the rate for each batch size.

Check yourself

12,000 rows, batch 2, accumulation 8, one GPU, 3 epochs, warmup ratio 0.03. How many steps, and how many warmup steps?

Reading the lab's log

The run in trainer_log.json evaluates every 100 steps. Evaluation loss falls from 1.55 at step 100 to 0.93 at step 600, then rises to 1.19 at step 1,000, while training loss ends at 0.563. In perplexity: 2.53 at the best checkpoint, 3.29 at the end, 1.76 on the training data. The final model is noticeably less certain on new data than the step-600 model, although its training loss is lower.

How much of a difference is real?

Eval loss is a mean over rows, so it has a standard error. If the per-row mean loss has standard deviation s across rows, the eval loss over n rows has standard error s/√n.

The lab's split leaves 4 evaluation rows; with s = 0.4 the standard error is 0.2, larger than every step-to-step change after step 400. The step 600 and step 700 values (0.93 and 0.94) are indistinguishable even with 200 rows. What you can trust is the shape: a minimum followed by a sustained rise over several evaluations. For decisions between close checkpoints, use the gold-set metric.

Diagnosis table

The ten-row overfit test

Training on ten rows for 30 epochs should drive training loss below about 0.05 (perplexity under 1.05). Ten rows have no generalization requirement, so failure isolates the pipeline: the mask, the template, the rate or the frozen parameters. It costs a minute and saves a day.

Learning-rate sweep

Run the rate at ×3 and ÷3 of the default (6e-4, 2e-4, 7e-5). Compare evaluation minima, not final values. The usual picture: the high rate reaches its minimum earliest and rises fastest, the low rate has not reached its minimum by the end. Pick the rate with the lowest minimum, then the checkpoint at that minimum.

Common mistakes

• Keeping the last checkpoint. In the lab's log it is 0.26 worse in eval loss than the best one. Set load_best_model_at_end=True with metric_for_best_model="eval_loss", or pick by hand.
• save_total_limit deleting the best checkpoint. With a limit of 2 and no best-model tracking, step 600 is deleted by step 800. Track the best or raise the limit.
• Reading single evaluations as trends. A 0.01 change on a few rows is noise.
• Smoothing hides spikes. Look at the raw training loss once before trusting a smoothed curve.

Check yourself

Eval loss at three checkpoints is 0.95, 0.93, 0.94 on 50 rows with s = 0.5. Can you tell them apart?

Derivation 1: the optimal policy

RLHF maximizes reward with a penalty for moving away from the reference π_ref (the SFT model):

Write the KL out and divide by −β, turning the maximum into a minimum: Σ_y π(y) [log π(y)/π_ref(y) − r(y)/β]. Define Z(x) = Σ_y π_ref(y) e^r(y)/β and π*(y) = π_ref(y) e^r(y)/β / Z. Then log π_ref(y) + r(y)/β = log π*(y) + log Z, and the sum becomes Σ π(y) log(π(y)/π*(y)) − log Z = KL(π ‖ π*) − log Z. Z does not depend on π, and a KL is zero only when its arguments are equal, so the optimum is π = π*:

Derivation 2: the reward in terms of the policy

Take logs and solve for r: r(x, y) = β log[π*(y|x)/π_ref(y|x)] + β log Z(x). Any policy defines an implicit reward this way, up to a term that depends only on x.

Derivation 3: Bradley–Terry and the loss

The Bradley–Terry model says the probability that y_w is preferred to y_l is σ(r(y_w) − r(y_l)). Substitute the implicit reward; β log Z appears in both terms and cancels:

The intractable Z was the reason RLHF needed a separate reward model and sampling; the cancellation is why DPO needs neither.

The gradient

With margin m = β[(log π(y_w) − log π_ref(y_w)) − (log π(y_l) − log π_ref(y_l))] and d/dm[−log σ(m)] = −σ(−m):

Each pair is weighted by σ(−m): close to 1 when the policy ranks the pair the wrong way, close to 0 when it already ranks it correctly by a wide margin.

Worked example

β = 0.1. Sequence log-probabilities: chosen −42.0 under the policy, −45.0 under the reference; rejected −50.0 and −48.0. Implicit rewards: 0.1·3 = 0.3 and 0.1·(−2) = −0.2. Margin 0.5. Loss −log σ(0.5) = 0.474; gradient weight σ(−0.5) = 0.378. At the start of training the policy equals the reference, m = 0, the loss is ln 2 = 0.693 and the weight 0.5.

What β does to the optimum: two answers with reference probability 0.5 each and rewards 1 and 0. π*(better) = e^1/β/(e^1/β + 1): 0.622 at β = 2, 0.731 at β = 1, 0.881 at β = 0.5, 0.99995 at β = 0.1. Small β lets the policy move almost all its mass; large β keeps it near the reference.

Common mistakes

• Reference that is not the starting policy. If π_ref is the base model but training starts from the SFT model, the margin starts nonzero and the loss is meaningless at step 0. Start where the reference is.
• SFT learning rate. 2e-4 on DPO wrecks fluency within a few hundred steps; use about 5e-6.
• Reading the chosen log-probability alone. Both chosen and rejected log-probabilities often fall while the margin grows. Track the margin and the gold metric.
• Length bias. Sequence log-probabilities are sums, and if chosen answers are systematically longer the policy learns length. Balance lengths in the pairs or normalize.

Derivation: a baseline does not bias the gradient

The policy gradient is E_y∼π[r(y) ∇log π(y)]. Subtract any b that does not depend on y. The extra term is b · E[∇log π(y)] = b Σ_y π(y) ∇log π(y) = b Σ_y ∇π(y) = b ∇Σ_y π(y) = b ∇1 = 0. So the gradient's expectation is unchanged, while its variance falls when b is close to the typical reward. PPO learns b with a value network; GRPO uses the mean reward of a group of answers to the same prompt.

The GRPO advantage

The per-token objective is PPO's clipped surrogate with ratio ρ = π_θ/π_old: min(ρÂ, clip(ρ, 1−ε, 1+ε)Â), minus β times a KL estimate to the reference. A common per-token estimator is k3 = q − log q − 1 with q = π_ref/π_θ; it is never negative and is zero only at q = 1. For q = 0.8 it is 0.0231.

Worked example: a group of 4

Four answers to one math problem; a checker gives 1 to the correct one: r = (1, 0, 0, 0). Mean 0.25. Sample standard deviation √[(0.75² + 3·0.25²)/3] = √(0.75/3) = 0.5.

The advantages sum to zero: the correct answer's tokens are pushed up three times as hard as each wrong answer's tokens are pushed down. Implementations differ on sample versus population standard deviation; torch's std defaults to the sample version.

Other groups: r = (1, 0, 0, 1) gives mean 0.5, sample std 0.577, advantages ±0.866. r = (1, 1, 1, 1) gives std 0 and advantage 0 for everyone (implementations add a small ε to the denominator): a group where every answer is right, or every answer is wrong, teaches nothing.

Why prompt difficulty matters

If the model solves a prompt with probability p and the group has G = 8 answers, the chance that all are wrong is (1−p)⁸. For p = 0.1 that is 0.430, so 43% of such groups produce no gradient; for p = 0.9 the chance that all are right is also 0.430. The useful prompts are the ones the model solves sometimes. Filter the training set to prompts with intermediate pass rates.

ORPO and KTO in one formula each

ORPO adds to the SFT loss λ · (−log σ(log odds(y_w) − log odds(y_l))), with odds(y) = P(y)/(1 − P(y)) under the policy itself, so no reference is needed. KTO scores single answers: it raises the implicit reward of thumbs-up answers above a reference point and lowers thumbs-down answers below it.

Common mistakes

• A reward the checker can be fooled on. If any string containing a number scores 1, the model learns to print many numbers. Parse strictly and test the checker on adversarial outputs.
• Groups of 2. The advantage is then always ±0.707 or 0 (sample std), so the size of a reward difference is lost. Use 8 or more.
• No length control. Per-sequence normalization can reward long wrong answers less per token than short ones, and lengths grow. Watch mean completion length.
• Only tracking reward. The reward can climb while general ability falls. Run the three fixed evaluation sets after each job.

Check yourself

Rewards (0.9, 0.2, 0.5, 0.0) from a graded checker. Which answers get a positive advantage?

A win rate with its interval

n prompts, w wins: the win rate p̂ = w/n is a binomial proportion with standard error √(p̂(1−p̂)/n).

Worked example: 39 wins out of 60. p̂ = 0.65, SE = √(0.65·0.35/60) = 0.0616, 95% interval 0.65 ± 1.96·0.0616 = 0.65 ± 0.121, that is [0.529, 0.771]. The Wilson interval, better near 0 or 1 and for small n, is

To get a half-width of ±5 points near p = 0.5 you need n = (1.96 · 0.5 / 0.05)² = 384 prompts.

Ties

With position swapping, a pair is a win only if it wins in both orders. Report wins, ties and losses. Two summaries are common: the score (w + t/2)/n, and a sign test on decisive pairs only. Example: 33 wins, 12 ties, 15 losses. Score (33 + 6)/60 = 0.65. Sign test: 33 of 48 decisive pairs, two-sided binomial p = 0.013 against a fair coin.

Derivation: McNemar's test for paired accuracy

Both models answer the same 100 gold rows. Only discordant rows carry information about the difference: b = rows the fine-tune gets right and the base gets wrong, c = the reverse. Under the null hypothesis of equal accuracy each discordant row is equally likely to fall either way, so b ~ Binomial(b + c, ½). The normal approximation with continuity correction gives

Worked example: base 62/100, fine-tune 74/100, with b = 18 and c = 6. χ² = (12 − 1)²/24 = 121/24 = 5.04, p = 0.025; the exact binomial test gives p = 0.023. An unpaired two-proportion z-test on 62% versus 74% gives p = 0.069 and would call the same data inconclusive, because it ignores that both models were tested on the same rows. With b = 14, c = 6 (fine-tune 70/100) McNemar gives χ² = 2.45, p = 0.118: an 8-point gain on 100 rows is not yet evidence.

Bootstrap

For metrics without a formula (field F1, a rubric score), resample the n prompts with replacement 1,000 times, recompute the metric difference between the models on each resample, and take the 2.5th and 97.5th percentiles. Resample prompts, not individual model outputs, so the pairing is kept.

Common mistakes

• Reporting a win rate without n. 65% on 20 prompts and on 400 prompts are different claims. Always give the interval.
• Different sampling settings for the two models. Temperature differences show up as quality differences. Fix temperature, max tokens and system prompt.
• Unpaired tests on paired data. They waste power, as the example shows. Use McNemar or a paired bootstrap.
• Tuning prompts on the gold set. After twenty iterations against it, the gold set is a training set. Keep a second, untouched set for the final number.
• Trusting the judge without calibration. Label 30 to 50 pairs by hand and measure agreement before using its win rates.

Merging: exact in math, rounded in storage

W' = W + (α/r)·BA gives W'x = Wx + (α/r)·BAx for every input, so the merged model computes the same function. The only loss is rounding when W' is stored in bf16. bf16 numbers in [0.5, 1) are spaced 2⁻⁸ = 0.0039 apart, so the rounding error is at most half that, 0.00195, a relative error below 2⁻⁹ ≈ 0.2%.

Worked example: a weight of 0.5 with a merged correction of +0.001. 0.501 is closer to 0.5 than to 0.50390625, so the stored weight is still 0.5 and that correction is gone. A correction of +0.003 rounds to 0.50390625. Individual small corrections can vanish, but the errors are unbiased and spread over millions of weights; measured differences in outputs are usually tiny. Merge in fp32 and cast once at the end, and compare a few outputs before and after.

Merging a QLoRA adapter

The adapter was trained against the dequantized NF4 weights Q(W), not W. Merging into the original bf16 W gives W + BA, which differs from what was trained, Q(W) + BA, by W − Q(W): on the order of 0.09σ of the weights per entry, from the previous lecture's measurement. The usual practice is to load the base in bf16 and merge, accepting this mismatch, or to dequantize Q(W) and merge into that; whichever you choose, rerun the gold set on the merged model before exporting.

Derivation: quantization error

A uniform quantizer with step Δ makes an error spread evenly over [−Δ/2, Δ/2]. Its mean square is ∫ e² de / Δ over that interval = Δ²/12, so the RMS error is Δ/√12 = 0.289Δ. With 16 levels over a block's range [−a, a], Δ = 2a/15 and RMS = 0.0385a. For Gaussian weights the absmax of a 64-weight block averages 2.60σ, so the predicted RMS is 0.100σ; a simulation gives 0.101σ. At 8 bits Δ = 2a/255, 17 times smaller.

GGUF bits per weight

Q4_K_M stores most tensors as Q4_K and some sensitive ones (parts of the attention value and feed-forward down projections) as Q6_K, so the file averages somewhat above 4.5 bits per weight.

Speed on a laptop

Generating one token reads every weight once, so decode speed is bounded by memory bandwidth / model size. Qwen2.5-7B at 4.5 bits is 4.29 GB; on a machine with 100 GB/s bandwidth the ceiling is about 23 tokens per second. Halving the bits roughly doubles the ceiling, which is why quantization matters more for speed than for disk.

Common mistakes

• Quantizing the only copy. Re-quantizing from a quantized file compounds the error. Keep the merged bf16 checkpoint.
• Skipping the post-quantization eval. Run the gold set on the GGUF file; small models lose more at 4 bits than large ones.
• Template lost in conversion. If the GGUF lacks the chat template, Ollama formats prompts differently from training. Check the rendered prompt in a verbose run.
• Serving the adapter on the wrong base. vLLM's multi-LoRA serving needs the exact base the adapter was trained on.

Check yourself

Estimate the Q8_0 file size of Llama-3.1-8B.

Derivation

Let the corpus be a multiset of symbol sequences w with counts c(w). The training objective at each step is greedy compression: choose the pair (a, b) that maximizes the number of symbols removed. Merging (a, b) removes one symbol per non-overlapping occurrence, so the saving is n(a, b) = Σ_w c(w) · occ(a, b, w). After merging, recount only the pairs that touched a merged occurrence: in x a b y, the pairs (x, a) and (b, y) each lose one count and the new pairs (x, ab) and (ab, y) each gain one. Efficient trainers update counts incrementally this way; the lab simply recounts, which is fine for a few thousand bytes.

Overlaps matter. In a a a, the pair (a, a) occurs twice in a count of windows but only once can be merged, leaving aa a. Counting with a sliding window therefore overstates the saving for repeated characters, and the merge function must scan left to right and skip past each replacement.

Worked example by hand

Continue the lecture corpus for one more merge. After merge 6 the corpus is low(5) · low e r(2) · new est(6) · w i d est(3). Pair counts: (new, est) 6, (w, i) 3, (i, d) 3, (d, est) 3, (low, e) 2, (e, r) 2. Merge 7 is (new, est) → newest, and the corpus drops from 35 to 29 symbols. Encoding newer with these seven merges: n e w e r → (n e) gives ne w e r → (ne w) gives new e r. Three tokens. The pair (e, r) was never merged because it reached only 2.

Code walkthrough

def encode(text, merges):
    ids = list(text.encode("utf-8"))
    while len(ids) >= 2:
        counts = get_pair_counts(ids)
        pair = min(counts, key=lambda p: merges.get(p, float("inf")))   # earliest-learned merge present
        if pair not in merges:
            break                                                     # no learned pair left
        ids = merge(ids, pair, merges[pair])
    return ids

Choosing the lowest-rank pair at each step reproduces the training-time order. Decoding is a lookup: each id maps to its bytes, concatenate, decode UTF-8. A token boundary can fall inside a multi-byte character, so decode the joined bytes, never token by token.

Common mistakes

• Decoding each token separately and joining strings. Symptom: replacement characters in streamed Vietnamese or emoji output. Fix: buffer bytes until they form complete UTF-8 characters.
• Encoding by longest match in the vocabulary. Symptom: ids that differ from the reference tokenizer on a few percent of words. Fix: apply merges by rank.
• Letting special-token strings in user text become special tokens. Symptom: a user can type <|im_end|> and close the assistant turn. Fix: encode user text with special tokens disabled.
• Measuring lengths in characters. Symptom: truncated answers after you set max_length from character counts. Fix: tokenize the dataset and use the token-count percentile.

Check yourself

With the six merges in the table, how many tokens does widest encode to?

Derivation

Take one pair of coordinates and write it as a complex number z = x₀ + i·x₁. Rotating by angle a is multiplication by e^ia. The real dot product of two 2-vectors u and v equals Re(u · v̄), where v̄ is the complex conjugate. For a query pair q at position m and a key pair k at position n:

Rotations preserve length, so RoPE never changes ‖q‖ or ‖k‖; it only changes the angle between them. With many pairs at different frequencies, the score for a fixed content pair, as a function of distance, is a sum of cosines, and for random vectors it tends to decay with distance. That gives a mild bias toward nearby tokens without any learned bias term.

Worked example by hand

Sinusoidal check: d = 4, position p = 3. Pair 0 has frequency 1, pair 1 has frequency 10000^−2/4 = 0.01. PE[3] = [sin 3, cos 3, sin 0.03, cos 0.03] = [0.1411, −0.9900, 0.0300, 0.9996]. RoPE check with θ = 0.5: query (1, 0) at position 2 becomes (cos 1, sin 1) = (0.5403, 0.8415). Key (0.6, 0.8) at position 5 is rotated by 2.5: x′ = 0.6·cos 2.5 − 0.8·sin 2.5 = 0.6·(−0.8011) − 0.8·0.5985 = −0.9595, y′ = 0.6·0.5985 + 0.8·(−0.8011) = −0.2818. Dot product: 0.5403·(−0.9595) + 0.8415·(−0.2818) = −0.7556.

Edge cases

Implementations disagree on which coordinates form a pair. The lab and the RoPE paper pair neighbours (0,1), (2,3), …; Hugging Face Llama code pairs coordinate j with j + d/2 ("rotate half"). Both are valid, but weights trained with one layout give wrong outputs with the other. When you port a checkpoint, check which layout its code uses.

Common mistakes

• Rotating the values. Symptom: outputs that drift with position. Fix: rotate q and k only.
• Restarting positions at 0 for each new token during cached decoding. Symptom: generation is fine for the prompt and degrades immediately after. Fix: pass the absolute position offset, as the Week 5 lab does with start_pos.
• Changing rope_theta or the pairing layout when loading weights. Symptom: perplexity near that of random text. Fix: copy the base model's config exactly.
• Adding learned position embeddings on top of RoPE. Symptom: worse extrapolation and no gain. Fix: use one mechanism.

Check yourself

A query and key sit 3 positions apart. You move both 1,000 positions later. By how much does their RoPE score change?

Derivation

For one row of scores s, the weights are a_i = e^s_i / Σ_j e^s_j. Differentiate a_i with respect to s_j by the quotient rule. When j = i, the numerator and denominator both depend on s_i: ∂a_i/∂s_i = (e^s_i Σ − e^s_i e^s_i) / Σ² = a_i(1 − a_i). When j ≠ i, only the denominator does: ∂a_i/∂s_j = −e^s_i e^s_j / Σ² = −a_ia_j.

If one weight is near 1 and the rest near 0, every term a_i(δ_ij − a_j) is near zero. That is the saturation the √d_k scaling prevents. With scores [8, 0], a₁ = 0.99966 and the largest derivative is a₁(1 − a₁) = 0.00034, compared with 0.25 for equal scores.

Numerical stability

e^x overflows float32 above x ≈ 88.72. Softmax is unchanged by subtracting a constant from every score, since the constant's exponential cancels between numerator and denominator, so implementations subtract the row maximum first: the largest exponent becomes e⁰ = 1 and nothing overflows. Masked entries use −∞ (or the most negative finite number) so that e^−∞ = 0 exactly. A row in which every entry is masked would give 0/0; causal masks never produce one, because every position may see itself.

Worked example by hand

Unmasked row 2 of the lecture: scores 0.7071, 0.7071, 1.4142. Subtract the max: −0.7071, −0.7071, 0. Exponentials: 0.4931, 0.4931, 1. Sum 1.9862. Weights 0.2483, 0.2483, 0.5035. Output 0.2483·(1, 0) + 0.2483·(0, 2) + 0.5035·(3, 1) = (1.7587, 1.0000). Compare (0.5, 1) with the mask: the first coordinate is dominated by token 3's value when the mask is missing.

Common mistakes

• Masking after the softmax by zeroing weights. Symptom: rows that no longer sum to 1. Fix: mask the scores with −∞ before the softmax.
• Softmax along the wrong axis. Symptom: columns sum to 1, outputs mix information from the future. Fix: softmax(dim=-1) over keys.
• Using triu(0) instead of triu(1). Symptom: a position cannot see itself and the first row is all −∞, producing NaN. Fix: mask strictly above the diagonal.
• Forgetting the scale. Symptom: training starts slowly or attention entropy collapses early. Fix: divide by √d_k per head, where d_k is the head size, not d.

Check yourself

In the example, what weight does position 3 put on itself, and why is it equal to its weight on position 2?

Derivation

Stack L residual blocks: x_L = x₀ + Σ_l f_l(x_l−1). The Jacobian ∂x_L/∂x₀ is the product of (I + J_l) over layers, which expands to I plus terms of every order in the J_l. The identity term means the gradient at the input is at least the gradient at the output, however small the J_l. With post-norm, each factor becomes N_l(I + J_l), where N_l is the normalization's Jacobian, and products of L such matrices can shrink or grow geometrically. Pre-norm keeps the bare identity on the main path.

A second reason for pre-norm: since every sublayer adds to the stream, ‖x‖ grows with depth. Normalizing the sublayer's input means each sublayer sees inputs of unit scale regardless of depth, so the same initialization works for layer 1 and layer 32.

Worked example by hand

RMSNorm versus LayerNorm on x = (3, 4), gain 1. RMSNorm: mean(x²) = (9 + 16)/2 = 12.5, divide by 3.5355: (0.8485, 1.1314). LayerNorm: mean 3.5, centred (−0.5, 0.5), standard deviation 0.5, output (−1, 1). LayerNorm discards the shared offset 3.5; RMSNorm keeps the direction of x and fixes only its scale.

The counting formula for a block with d = 32, h = 88 (the lab's test block): 4 · 32² = 4,096 for attention, 3 · 32 · 88 = 8,448 for SwiGLU, 2 · 32 = 64 for the norms, total 12,608. The lab prints exactly this.

Code walkthrough

def count_params(V, d, L, hidden):
    attn = 4 * d * d                 # q, k, v, o: d x d each, no bias
    mlp  = 3 * d * hidden            # gate, up: d x h; down: h x d
    norm = 2 * d                     # two RMSNorm gains per block
    return V * d + L * (attn + mlp + norm) + d + d * V
count_params(32000, 4096, 32, 11008)  # 6,738,415,616

Common mistakes

• Forgetting the untied head. Symptom: your count is short by V·d (131 M for Llama 2). Fix: check tie_word_embeddings in the config.
• Leaving bias=True on the linear maps. Symptom: a count that exceeds the formula by a few thousand per layer. Fix: Llama-style models have no biases; Qwen2.5 has biases on q, k and v only, so add them.
• Using 4d² for attention in a GQA model. Symptom: Llama-3-8B counts as 8.84 B. Fix: K and V are d × (n_kv · d_head).
• Normalizing the residual stream in a pre-norm block. Symptom: training is unstable at depth. Fix: normalize only what goes into the sublayer.

Check yourself

How many parameters does one SwiGLU block with d = 896 and h = 4,864 (the Qwen2.5-0.5B shape) contain?

Derivation

At initialization the output logits are small random numbers, so the softmax is close to uniform over V tokens and every target has probability about 1/V. Cross-entropy is −log(1/V) = log V. For V = 42, log 42 = 3.738; for Llama 2's 32,000 tokens, 10.37; for Llama 3's 128,256, 11.76. A first-step loss far above log V means the logits are too large (bad initialization or a missing norm); far below means the targets leak into the inputs, usually a missing mask or an unshifted label.

Temperature as a power: exp(z_i/T) = (exp z_i)^1/T, and exp z_i is proportional to p_i, so p_i(T) ∝ p_i^1/T. At T = 0.5 that squares the probabilities: 0.25, 0.09, 0.0225, 0.0025, sum 0.365, normalized 0.685, 0.247, 0.062, 0.007.

Worked example by hand

Top-p implementation detail: sort probabilities descending, compute the cumulative sum, and drop a token when the mass before it already reaches p. For p = 0.9 and [0.5, 0.3, 0.15, 0.05], the mass before each token is 0, 0.5, 0.8, 0.95; only the last has mass before it ≥ 0.9, so three tokens survive with total 0.95. The rule keeps the token that crosses the threshold, and it always keeps the first token, so top-p never empties the distribution. Applied after top-k = 2, top-p 0.9 sees [0.625, 0.375]; mass before is 0 and 0.625, so both stay.

Edge cases

Temperature exactly 0 divides by zero; implementations special-case it as argmax. Top-k with k ≥ V does nothing. Ties at the k-th logit keep all tied tokens in a logits < kth implementation, which is harmless. Repetition penalties, which divide the logits of tokens already generated, are a heuristic on top of these and change the distribution in ways that are hard to evaluate; prefer fixing the model.

Common mistakes

• Shifting labels twice. Hugging Face models shift internally when you pass labels=input_ids; shifting yourself as well trains the model to predict two tokens ahead. Symptom: loss stalls high. Fix: shift in exactly one place.
• Not cropping the context to the block size in a model with learned positions. Symptom: an index error after T tokens. Fix: feed idx[:, -block_size:].
• Comparing models with different decoding settings. Symptom: a "better" model that only had a lower temperature. Fix: fix temperature, top-p and seed across models.
• Reporting sampled text from a model evaluated at its last checkpoint instead of its best. Symptom: memorized training sentences in the output. Fix: reload the checkpoint at the validation minimum.

Check yourself

With p = [0.5, 0.3, 0.15, 0.05] and top-p = 0.75, which tokens survive and with what probabilities?

Derivation

For a normal number with e exponent bits and m mantissa bits, the stored exponent E runs from 1 to 2^e − 2 (all zeros means zero or subnormal, all ones means infinity or NaN), and the bias is 2^e−1 − 1: 127 for fp32 and bf16, 15 for fp16. The largest value is the largest mantissa, 2 − 2^−m, at the largest exponent, 2^e−1 − 1.

Epsilon is 2^−m: the next number after 1.000…0 is 1.000…1. Round-to-nearest moves a value by at most half a step, and the step relative to the value is between 2^−m−1 and 2^−m, so the relative error is at most 2^−m−1.

Worked example by hand

Store 0.1 in bf16. 0.1 = 1.6 × 2⁻⁴. The mantissa field holds the fraction 0.6 in 7 bits: 0.6 × 128 = 76.8, rounded to 77. The stored value is (1 + 77/128) × 2⁻⁴ = 1.6015625 / 16 = 0.10009765625, a relative error of 0.098%. In fp16 the fraction gets 10 bits: 0.6 × 1024 = 614.4, rounded to 614, giving (1 + 614/1024)/16 = 0.0999755859375, error 0.024%. Both match what PyTorch prints.

Common mistakes

• Running fp16 inference on a model trained in bf16. Symptom: inf or NaN in a few layers' activations, garbage output. Fix: use bf16, or fp32 on hardware without bf16.
• Accumulating sums in bf16. Symptom: a running loss or a long dot product that stops changing. Fix: accumulate in fp32; matrix-multiply kernels already do.
• Expecting bf16 weights to round-trip fp32 checkpoints exactly. Symptom: tiny diffs after save and load. Fix: compare with a tolerance of about 0.4% relative.
• Confusing range with precision. Symptom: choosing fp16 "for accuracy" and overflowing. Fix: range from exponent bits, precision from mantissa bits; LLM activations need range.

Check yourself

What is the gap between consecutive fp16 numbers in the interval [1024, 2048)?

Derivation

Let e = ŵ − w be the rounding error. If w is spread over many steps of size Δ, its position within a step is close to uniform, so e is uniform on [−Δ/2, Δ/2]. Its mean is 0 and its variance is ∫ e² de / Δ over that interval, which is (1/Δ) · [e³/3] from −Δ/2 to Δ/2 = (1/Δ) · (Δ³/24 + Δ³/24) = Δ²/12.

For b-bit absmax on values bounded by A, Δ = A / (2^b−1 − 1). The signal power of w is σ². SQNR = σ² / (Δ²/12) and in decibels 10·log₁₀(12σ²/Δ²). Each extra bit roughly halves Δ, adding 20·log₁₀2 = 6.02 dB. For Gaussian weights, A is the maximum of the group, about 3σ for a group of 64 and larger for bigger groups, which is why smaller groups give higher SQNR.

Now the matrix product. With y = Wx and errors e_ij independent of each other and of x, the error in output i is Σ_j e_ijx_j, with variance d_in · (Δ²/12) · E[x²]. The output itself has variance d_in · σ² · E[x²]. The ratio is the same Δ²/(12σ²): a matrix product does not amplify relative weight error, it carries it through. Stacking 32 layers does add the errors up, which is why large models are more sensitive than the lab's two-layer one.

Worked example by hand

Absmax on the lecture vector, value 0.08: 0.08 / 0.018898 = 4.233, round to 4, back to 4 × 0.018898 = 0.0756, error 0.0044. Zero-point, same value: 0.08 / 0.014392 = 5.559, round to 6, plus z = 94, back to (94 − 88) × 0.014392 = 0.0864, error 0.0064.

Common mistakes

• Using −128 in symmetric quantization. Symptom: the most negative weight gets more error than the most positive. Fix: clamp to [−127, 127].
• Computing the scale from a calibration subset, then meeting larger values. Symptom: clipped weights or activations. Fix: for weights use the true max; for activations, calibrate on representative data and clamp.
• Forgetting z in dequantization. Symptom: every reconstructed value is shifted by z · scale. Fix: ŵ = (q − z) · scale.
• One scale for a whole tensor with outliers. Symptom: accuracy falls sharply at 8 bits on a large model. Fix: per-channel or per-group scales.

Check yourself

A tensor has max |w| = 2.54. What is the absmax int8 scale, and what code does 1.27 receive?