⚠️Careful

Capture note — read once, then forget it.

slides_deduped/Lecture_02/ contains 21 images, but the deck actually has 35 distinct states (21 kept by the dedup step + the 14 it dropped, listed below). The de-duplication step merged genuinely different slides. The following were missing from the deduped set and were recovered from the full capture in output/Lecture_02 - .../, cited below by raw frame number and video timestamp:

Two numbering systems appear in this file, and they are not interchangeable. An un-prefixed slide_NNN cited without the word "raw" refers to slides_deduped/ numbering (only used for the 21 slides that survived dedup intact); a citation marked raw slide_NNN (as in the recovery table immediately below, and in every citation later in this file) refers to output/Lecture_02.../ numbering — the complete, un-deduplicated capture. If you open a frame yourself to check a citation, open it from the folder the citation says: output/ for anything marked "raw", slides_deduped/ only for the rare un-prefixed one.

Slide	Raw frame	Timestamp
Loss Functions (definition + the list of five)	`slide_009`	2:02
Mean Squared Error (MSE)	`slide_011`	3:15
Mean Absolute Error (MAE)	`slide_013`	4:40
Comparing loss functions for regression (table)	`slide_019`	7:03
Binary Cross-Entropy (BCE)	`slide_022`	9:56
Mini-batch Stochastic Gradient Descent	`slide_042`	18:51
Evaluation metrics (overview)	`slide_056`	22:14
Classification: Confusion Matrix	`slide_060`	25:43
Precision vs. Recall Trade-off	`slide_062`	26:29
ROC-AUC & PR-AUC	`slide_065`	28:36
K-Nearest Neighbors (KNN)	`slide_082`	35:49
KNN: Practical Considerations	`slide_084`	36:30
SVM: Core Idea	`slide_087`	36:43
SVM: Kernel Trick	`slide_088`	38:13

Every slide in this lecture is now accounted for (21 + 14 = 35). Nothing below is reconstructed or guessed. Where I teach something the slide did not, it is explicitly marked 📚 Background the slide assumed.

How to read this document 1 min

Layer	What it is	How to use it
Main body	The teaching. Every concept built from zero.	Read linearly, once, slowly.
`interactive` blocks	Machine-readable specs for the animated web version.	Skip on first read.
Glossary + Check yourself	Recall layer.	Come back weekly.

Callout legend: 📚 background the slide assumed · 💡 key insight · ⚠️ careful · 🧪 worked example · 🎯 interview · 🔬 research opportunity

What you'll understand after reading this 2 min

By the end of this document you will be able to:

Explain what a loss function is structurally — a scalar-valued function of one prediction and one target — and why choosing it is the single most consequential modelling decision after choosing the model class.
Derive, not recall, that MSE optimises toward the mean and MAE toward the median, and use that fact to pick a loss from a business requirement.
Show that MSE is maximum likelihood under Gaussian noise and MAE is maximum likelihood under Laplacian noise, and explain why that reframing tells you which loss matches your data.
Prove Huber loss is continuous and differentiable at its own kink, and choose δ deliberately.
Read the BCE and cross-entropy formulas out loud in English, explain why the softmax must accompany cross-entropy, and compute both by hand.
Explain why hinge loss produces sparse models and logistic loss does not, from the shape of their gradients.
Walk the whole optimiser family tree — closed form → batch GD → SGD → mini-batch → momentum → adaptive → Adam/AdamW — and say what problem each step solves.
Derive the learning-rate divergence threshold on a quadratic and explain why "too big" fails.
Build a confusion matrix, compute all six derived metrics by hand, and expose the accuracy paradox on an imbalanced problem.
Construct an ROC curve from raw scores and compute AUC two independent ways that agree.
Classify a document with Naive Bayes end to end, including Laplace smoothing and the log-space computation, and explain why a false independence assumption still classifies well.
Pick K in KNN from a bias–variance argument and explain why KNN collapses in high dimensions.
Compute an SVM margin by hand and explain the kernel trick as an inner-product substitution rather than an explicit mapping.

Before we start: what you need to know 10 min

The deck opens straight into loss functions and assumes the whole supervised-learning scaffold. Here it is, taught from zero. If you already know a section, read the bold line and move on.

Prerequisite 1 — The supervised learning setup and its notation

Supervised learning — learning a function from examples where you were told the right answer.

In everyday words: someone hands you a stack of flashcards with the question on the front and the answer on the back. You study them, then get tested on cards you've never seen.

Concretely: 50,000 product listings, each with a title, price, and image, each labelled "counterfeit" or "genuine". You learn the mapping from listing to label.

Why it exists: the alternative is writing the rules by hand. Nobody can write down the rule that separates counterfeit from genuine listings; but you can collect examples of both.

The notation used everywhere below, and on every slide in this deck:

Symbol	Read it as	What it means
$x_{i}$	"x sub i"	The $i$ -th input (also: example, instance, feature vector). Usually a vector of $d$ numbers.
$y_{i}$	"y sub i"	The true target for example $i$ . A number for regression, a class label for classification.
${\hat{y}}_{i}$	"y-hat sub i"	The model's prediction for example $i$ . The hat always means "estimated".
$n$	"n"	Number of training examples.
$d$	"d"	Number of features per example.
$C$	"C"	Number of classes (classification only).
$θ$ or $𝐰$	"theta" / "w"	The parameters — the numbers the model learns. $𝐰$ specifically means a weight vector.
$b$	"b"	The bias / intercept — a single number added to every prediction.
$f (x; θ)$	"f of x, given theta"	The model: a function that turns an input into a prediction using parameters $θ$ .
$ℒ$	"script L"	The loss.
$η$	"eta"	The learning rate.
$\nabla$	"del" or "nabla"	The gradient operator.

Two conventions that trip people up constantly:

$𝐰^{⊤} 𝐱$ (read "w transpose x") is the dot product: multiply matching entries and add them up. If $𝐰 = (2, - 1, 3)$ and $𝐱 = (1, 4, 2)$ then $𝐰^{⊤} 𝐱 = 2 (1) + (- 1) (4) + 3 (2) = 2 - 4 + 6 = 𝟒$ .
The subscript $i$ indexes examples; the subscript $j$ indexes features; the subscript $c$ indexes classes. When you see a double sum $\sum_{i} \sum_{c}$ you are summing over every example and, inside that, over every class.

Prerequisite 2 — Model, parameters, training, inference

Model — a family of functions with adjustable knobs.

Concretely: $f (x; w, b) = w x + b$ is a model. Every choice of $(w, b)$ is one specific line. The model is the set of all lines; training picks one.

Parameters are the knobs ( $w$ , $b$ ). Learned from data.
Hyperparameters are knobs you set before training and the algorithm never touches — the learning rate $η$ , the Huber threshold $δ$ , the SVM's $C$ , KNN's $K$ . Every one of these appears in this lecture, and the difference matters: parameters are fit, hyperparameters are tuned (usually by trying values on a validation set).
Training is searching for the parameter values that make the loss small.
Inference is using the fitted parameters on new inputs.

Prerequisite 3 — Derivatives, gradients, and why they point downhill

The entire optimisation half of this lecture is one idea: the gradient points uphill, so walk the other way. You need three things.

A derivative is a slope. $\frac{d}{d w} L (w)$ answers: if I nudge $w$ up by a tiny amount, how much does $L$ change, and in which direction? Positive derivative → increasing $w$ increases $L$ .

A partial derivative is a slope along one axis. When $L$ depends on many parameters, $\frac{\partial L}{\partial w_{j}}$ asks the same question about $w_{j}$ only, holding everything else fixed. Notation changes from $d$ to $\partial$ ; the meaning does not.

A gradient is all the partial derivatives stacked into a vector.

\nabla L (𝐰) = (\frac{\partial L}{\partial w_{1}}, \frac{\partial L}{\partial w_{2}}, \dots, \frac{\partial L}{\partial w_{d}})

🧪 Worked example. $L (w_{1}, w_{2}) = w_{1}^{2} + 3 w_{1} w_{2}$ . Then $\frac{\partial L}{\partial w_{1}} = 2 w_{1} + 3 w_{2}$ and $\frac{\partial L}{\partial w_{2}} = 3 w_{1}$ . At the point $(w_{1}, w_{2}) = (1, 2)$ : $\nabla L = (2 (1) + 3 (2), 3 (1)) = (8, 3)$ . So from $(1,2)$ , the fastest way to reduce $L$ is to step in direction $(- 8, - 3)$ .

Prerequisite 4 — Convexity, local minima, global minima

Convex function — one whose graph is bowl-shaped: the straight line joining any two points on the curve never dips below the curve.

Why you care: a convex function has exactly one minimum, and it is global. Gradient descent on a convex loss cannot get stuck. MSE with a linear model, logistic loss, hinge loss, and the SVM objective are all convex. Neural network losses are not.

Local minimum — lower than everything nearby, but maybe not lower than somewhere far away.
Global minimum — the lowest point anywhere.
A saddle point has zero gradient but is a minimum in one direction and a maximum in another. In high dimensions saddles vastly outnumber local minima, and they are the real obstacle for deep networks — not local minima.

Prerequisite 5 — Probability: Gaussian, Laplace, likelihood, and MLE

Slides 5 and 6 both end with a line like "equivalent to MLE under Gaussian noise" and then move on. That line is the deepest idea in the loss section, so here is everything needed to unpack it.

Probability density. For continuous quantities you cannot ask "what is the probability the error is exactly 0.3?" — that's zero. You ask about density, written $p (\cdot)$ : higher density means values near there are more likely.

The Gaussian (normal) distribution with mean 0 and variance $σ^{2}$ :

p (ε) = \frac{1}{\sqrt{2 π σ^{2}}} \exp (- \frac{ε^{2}}{2 σ^{2}})

Symbol	Read it as	What it means
$ε$	"epsilon"	The error / noise: the gap between truth and the clean signal.
$σ^{2}$	"sigma squared"	Variance — how spread out the noise is.
$\exp (\cdot)$	"e to the"	The exponential function.

The shape that matters: the exponent contains $ε^{2}$ . Squared. Remember that.

The Laplace distribution with mean 0 and scale $b$ :

p (ε) = \frac{1}{2 b} \exp (- \frac{| ε |}{b})

The exponent contains $| ε |$ . Absolute value. Compared to a Gaussian, the Laplace has a sharp peak at zero and fatter tails — it considers a huge error far less shocking than a Gaussian does. That single fact is why MAE is robust to outliers, as you'll see.

Likelihood — given a candidate parameter value, how probable is the data I actually observed? Note the inversion: probability asks "given the parameters, how likely is this data?", likelihood takes the same number and treats it as a function of the parameters with the data fixed.

Maximum Likelihood Estimation (MLE) — pick the parameters that make the observed data most probable. Because the examples are assumed independent, the likelihood of the whole dataset is a product:

ℒ (θ) = \prod_{i = 1}^{n} p (y_{i} | x_{i}; θ)

Products of many small numbers underflow to zero in floating point, and products are painful to differentiate. So we always take the log-likelihood, because $\log$ turns products into sums and is monotonically increasing (so it doesn't move the maximum):

\log ℒ (θ) = \sum_{i = 1}^{n} \log p (y_{i} | x_{i}; θ)

Finally, optimisers minimise by convention, so we minimise the negative log-likelihood.

Prerequisite 6 — Mean, median, and why they differ

Mean — add up and divide by the count. Pulled hard by extreme values.
Median — sort and take the middle. Ignores how extreme the extremes are.

For $[2, 4, 6, 8, 100]$ : mean $= 120 / 5 = 𝟐𝟒$ , median $= 𝟔$ . One outlier moved the mean by a factor of four and the median not at all. Hold on to these two numbers — they reappear in the MSE/MAE worked example.

Prerequisite 7 — Big-O notation

$O (\cdot)$ describes how cost grows with input size, ignoring constants. $O (n d)$ means "proportional to the number of points times the number of dimensions". You need it for exactly two claims in this lecture: the normal equation costs $O (d^{3})$ (which is why it doesn't scale), and KNN prediction costs $O (n d)$ per query (which is why it doesn't scale either, for a different reason).

The big picture 3 min

Strip away the specifics and every supervised learning system in this lecture — and in industry — is four boxes:

This lecture is boxes 2, 3 and 4 — and then three complete models (Naive Bayes, KNN, SVM) that fill box 1 in three radically different ways.

The single most important structural point, and the one the slides state explicitly at 22:14: box 2 and box 4 are different functions and they are allowed to disagree. You train on a loss because it is differentiable and smooth; you are judged on a metric because it reflects money, safety, or user experience. Accuracy is not differentiable. You cannot descend it. So you minimise cross-entropy and hope accuracy follows. Most of the hard engineering in applied ML lives in that gap.

Part 1 — Loss Functions

What a loss function is 4 min

The slide [raw slide_009, 2:02] gives the definition:

A function $ℒ (y, \hat{y})$ that measures the discrepancy between the true target $y$ and the model prediction $\hat{y}$ .

Defines the optimization objective.

Encodes our assumptions about the problem.

Different losses result in different model behaviors.

Take those three bullets seriously, because they are three genuinely different claims.

"Defines the optimization objective" — the loss is the only thing the optimiser can see. The model does not know what a counterfeit listing is, or that a delivery estimate three days late is worse than one day early. Everything you want the model to care about must be expressed as a number the loss returns.

"Encodes our assumptions" — from Prerequisite 5: picking a loss is picking a noise model. Pick MSE and you have asserted that your errors are Gaussian. If they aren't, you've quietly told the optimiser something false about your data.

"Different losses result in different model behaviors" — the same model class, same data, same optimiser, different loss gives you a genuinely different fitted model. §3 proves this with numbers.

📚Background

Background the slide assumed — loss vs cost vs objective vs risk. These four words get used interchangeably and shouldn't be:

Term	Means
Loss	The error on one example: $ℒ (y_{i}, {\hat{y}}_{i})$ .
Cost	The average over the training set: $\frac{1}{n} \sum_{i} ℒ (y_{i}, {\hat{y}}_{i})$ .
Objective	What you actually minimise — cost plus any regularisation term.
Risk	The expected loss over the true data distribution — what you actually want, and can never compute. Empirical risk is the cost: the sample estimate of it.

Most people (and these slides) say "loss" for all four. Context disambiguates. But in an interview, using them precisely is a cheap signal of depth.

The deck then lists the five losses it will teach [slide_009]:

#	Loss	Task
1	Mean Squared Error (MSE)	regression
2	Mean Absolute Error (MAE)	regression
3	Huber Loss	robust regression
4	Binary Cross-Entropy	binary classification
5	Hinge Loss	max-margin classification, used in SVMs

Cross-entropy for multi-class is taught too, making six. We take them in order.

📚Background

Background the slide assumed — why these losses have the shapes they do. Worth knowing before you meet any of them: three of the six (BCE, cross-entropy, hinge) exist for a reason that has nothing to do with regression. For classification, what you actually want to minimise is the 0/1 loss — 1 if wrong, 0 if right, exactly the error rate. But it is piecewise constant: its gradient is zero everywhere it's defined and undefined at the jump, so gradient descent cannot touch it, and minimising it exactly is NP-hard in general. So every classification loss below is a surrogate — a convex function that sits above the 0/1 loss and can be descended, chosen so that driving the surrogate down provably drives the error rate down. (Hinge, logistic, and exponential — AdaBoost's — are the three classical surrogates.) Regression losses don't need this trick, because the quantity you actually want (MSE, MAE) is already differentiable — which is exactly why MSE and BCE end up with such different shapes. Keep this as a throughline for the rest of Part 1; §8 returns to it once you've seen a surrogate loss concretely.

Mean Squared Error (MSE) 7 min

Intuition first

You predicted 10, the truth was 13. You were off by 3. How bad is that? MSE's answer: square it. Being off by 3 is nine times as bad as being off by 1, not three times.

That is the entire design decision, and everything else about MSE follows from it.

The formula in words, then symbols

The formula says: for each example, take the gap between truth and prediction, square it so that sign doesn't matter and big gaps hurt disproportionately, then average over all examples.

ℒ_{MSE} = \frac{1}{n} \sum_{i = 1}^{n} {(y_{i} - {\hat{y}}_{i})}^{2}

Symbol	Read it as	What it means
$n$	"n"	Number of examples averaged over. Makes the loss comparable across dataset sizes.
$\sum_{i = 1}^{n}$	"sum from i equals 1 to n"	Add up the term that follows, once per example.
$y_{i}$	"y sub i"	True target for example $i$ .
${\hat{y}}_{i}$	"y-hat sub i"	Predicted value for example $i$ .
$(y_{i} - {\hat{y}}_{i})$	"the residual"	The signed error. Positive means the model under-predicted.

The slide [raw slide_011, 3:15] lists four properties. All four are worth unpacking.

Property 1 — Differentiable everywhere

${(y - \hat{y})}^{2}$ is a parabola. Parabolas have no kinks. So the gradient exists at every single point including the minimum, and gradient-based optimisers never hit an undefined value. Compare MAE, which fails exactly this test.

Property 2 — Penalises large errors quadratically

Errors of $1, 2, 10$ contribute $1, 4, 100$ .

Property 3 — Hence sensitive to outliers

This is Property 2 restated as a warning. Because a single error of 100 contributes 10,000 while a hundred errors of 1 contribute 100 total, one bad label can outvote a hundred good ones.

Property 4 — Equivalent to MLE under Gaussian noise

The slide states $y = f (x) + ε, ε \sim 𝒩 (0, σ^{2})$ and stops. Here is the derivation, which takes four lines.

Assume the target is the model output plus Gaussian noise. Then the density of observing $y_{i}$ given $x_{i}$ is the Gaussian density evaluated at the residual:

p (y_{i} | x_{i}; θ) = \frac{1}{\sqrt{2 π σ^{2}}} \exp (- \frac{{(y_{i} - f (x_{i}; θ))}^{2}}{2 σ^{2}})

Take the log of the whole dataset's likelihood (product → sum):

\log ℒ (θ) = \sum_{i = 1}^{n} [- \frac{{(y_{i} - f (x_{i}; θ))}^{2}}{2 σ^{2}} - \log \sqrt{2 π σ^{2}}]

Negate to get something to minimise, and drop every term that does not contain $θ$ (the $\log \sqrt{2 π σ^{2}}$ term is a constant; the $\frac{1}{2 σ^{2}}$ is a positive constant multiplier which cannot move the location of the minimum):

- \log ℒ (θ) \propto \sum_{i = 1}^{n} {(y_{i} - f (x_{i}; θ))}^{2}

Which is $n$ times MSE. Minimising MSE and maximising Gaussian likelihood are the same optimisation problem. ∎

The gradient

The formula says: the push on each prediction is proportional to how wrong it was.

\frac{\partial ℒ_{MSE}}{\partial {\hat{y}}_{i}} = - \frac{2}{n} (y_{i} - {\hat{y}}_{i})

The factor $(y_{i} - {\hat{y}}_{i})$ is the key: gradient magnitude scales with the error. Big error → big correction. This gives fast convergence when you're far away, and gentle steps near the optimum — which is exactly the behaviour you want, and is why the slide later calls MSE's convergence "fast".

🧪 Worked example — proving MSE optimises toward the mean

The claim on the MAE slide is "MSE optimizes toward the mean of the target distribution." Let's prove it rather than trust it, using the simplest possible model: predict a single constant $c$ for everything.

Data: $y = [2, 4, 6, 8, 100]$ .

ℒ (c) = \frac{1}{5} \sum_{i = 1}^{5} {(y_{i} - c)}^{2}

Differentiate with respect to $c$ and set to zero:

\frac{d ℒ}{d c} = \frac{1}{5} \sum_{i = 1}^{5} - 2 (y_{i} - c) = 0 ⟹ \sum_{i} y_{i} - 5 c = 0 ⟹ c = \frac{1}{5} \sum_{i} y_{i}

That is the definition of the mean. So $c^{⋆} = 120 / 5 = 𝟐𝟒$ . ∎

Sanity-check numerically. At $c = 24$ :

ℒ = \frac{1}{5} [22^{2} + 20^{2} + 18^{2} + 16^{2} + 76^{2}] = \frac{1}{5} [484 + 400 + 324 + 256 + 5776] = \frac{7240}{5} = 𝟏𝟒𝟒𝟖

At $c = 6$ (the median):

ℒ = \frac{1}{5} [16 + 4 + 0 + 4 + 8836] = \frac{8860}{5} = 𝟏𝟕𝟕𝟐

1448 < 1772, so MSE genuinely prefers 24. And 24 is a terrible summary of this data — four of the five points are below 8. That is outlier sensitivity, in one number.

Where people get confused

You might think MSE's outlier sensitivity is always a bug. Actually it is sometimes exactly what you want. If you're predicting server load and being wrong by 10× causes an outage, you want the loss to scream about large errors. Outlier sensitivity is a bug when outliers are label noise and a feature when they are real events with real cost. Diagnose which before switching losses.

You might think "sensitive to outliers" and "not robust" mean the model will be worse. Actually if your noise really is Gaussian, MSE is the statistically optimal choice — no other loss extracts more information from the data. Robustness is insurance, and like all insurance it costs something.

Interactive · slider One outlier, two fits

Concept: MSE's outlier sensitivity vs MAE's robustness
Try: Drag a single data point vertically away from an otherwise linear cloud of 20 points.
Watch: Two fitted lines redraw live — the MSE line swings toward the dragged point, the MAE line barely moves. A readout shows both losses' fitted intercepts.
Insight: The MSE line chases the outlier because the penalty grows quadratically; the MAE line ignores it because the penalty grows linearly and the point is only one vote.

The worked example in §2 — data [2,4,6,8,100] gives MSE optimum 24 and MAE optimum 6.

Mean Absolute Error (MAE) 5 min

Intuition first

Same setup, one change: don't square, just take the size. Off by 3 is exactly three times as bad as off by 1.

Words, then symbols

The formula says: average the absolute size of the errors.

ℒ_{MAE} = \frac{1}{n} \sum_{i = 1}^{n} | y_{i} - {\hat{y}}_{i} |

Symbol	Read it as	What it means
$\| \cdot \|$	"absolute value of"	Throw away the sign. $\| - 3 \| = 3$ .

The slide [raw slide_013, 4:40] gives four bullets and then two summary lines. Take them in turn.

"Penalises all errors linearly — large errors are not disproportionately punished"

Errors of $1, 2, 10$ contribute $1, 2, 10$ . Compare MSE's $1, 4, 100$ .

"Robust to outliers (unlike MSE)"

Follows directly. A wildly wrong point contributes its error once, not squared, so it cannot dominate.

"Equivalent to MLE under Laplacian noise"

Same derivation shape as MSE. With $ε \sim Laplace (0, b)$ :

p (y_{i} | x_{i}; θ) = \frac{1}{2 b} \exp (- \frac{| y_{i} - f (x_{i}; θ) |}{b})

- \log ℒ (θ) = \sum_{i} \frac{| y_{i} - f (x_{i}; θ) |}{b} + n \log (2 b) \propto \sum_{i} | y_{i} - f (x_{i}; θ) |

which is $n \times$ MAE. ∎

"Not differentiable at zero — use sub-gradient or smooth approximations"

$| e |$ has a sharp corner at $e = 0$ . Approaching from the right the slope is $+ 1$ ; from the left it's $- 1$ . There is no single slope at the corner, so the derivative is undefined there.

The gradient away from zero:

\frac{\partial ℒ_{MAE}}{\partial {\hat{y}}_{i}} = - \frac{1}{n} sign (y_{i} - {\hat{y}}_{i})

The magnitude is constant. $\pm \frac{1}{n}$ regardless of whether you're off by 0.001 or by 1,000. This is why the comparison table calls MAE's convergence "slower (constant gradient)" — near the optimum, MAE keeps taking full-size steps and bounces around the minimum instead of settling. The standard fix is a decaying learning rate (§13).

🧪 Worked example — proving MAE optimises toward the median

Same data, $y = [2, 4, 6, 8, 100]$ , same constant model.

ℒ (c) = \frac{1}{5} \sum_{i} | y_{i} - c |

The derivative with respect to $c$ is $\frac{1}{5} \sum_{i} - sign (y_{i} - c)$ , i.e. $\frac{1}{5} [(# points below c) - (# points above c)]$ .

Setting this to zero means: the number of points below $c$ must equal the number above. That is the definition of the median. So $c^{⋆} = 𝟔$ . ∎

Numerically, at $c = 6$ :

ℒ = \frac{1}{5} [4 + 2 + 0 + 2 + 94] = \frac{102}{5} = 𝟐𝟎.𝟒

At $c = 24$ (the mean):

ℒ = \frac{1}{5} [22 + 20 + 18 + 16 + 76] = \frac{152}{5} = 𝟑𝟎.𝟒

20.4 < 30.4. MAE prefers 6. Same data, same model, different loss, different answer — 6 versus 24. That is bullet three of the loss-function slide made concrete.

Where people get confused

You might think you should always use MAE because it's robust. Actually if you are forecasting demand and your metric is total inventory cost, the mean is what you want, because costs add up linearly across the whole distribution, not around its middle. Match the loss to the decision, not to a general preference for robustness.

Huber Loss 7 min

The problem it solves

You now have two losses with complementary flaws:

	MSE	MAE
Near zero error	smooth, gradient shrinks → converges nicely	kinked, gradient constant → bounces
Far from zero	penalty explodes → outliers dominate	penalty linear → robust

The obvious question: can we have MSE's behaviour where errors are small and MAE's where they're large? Huber is exactly that, welded together at a chosen threshold.

Words, then symbols

The formula says: if the error is small enough, use the squared penalty; once it exceeds a threshold $δ$ , switch to a straight line — and shift that line down by just enough that the two pieces meet with no jump and no kink.

ℒ_{δ} (y, \hat{y}) = {\begin{matrix} \frac{1}{2} {(y - \hat{y})}^{2} & if | y - \hat{y} | \leq δ \\ δ (| y - \hat{y} | - \frac{δ}{2}) & otherwise \end{matrix}

Symbol	Read it as	What it means
$δ$	"delta"	The transition threshold — a hyperparameter you choose. Errors below it are "normal", above it are "outliers".
$\frac{1}{2} {(y - \hat{y})}^{2}$	—	The quadratic (MSE-like) branch. The $\frac{1}{2}$ is not cosmetic here; it makes the pieces join smoothly.
$δ (\| y - \hat{y} \| - \frac{δ}{2})$	—	The linear (MAE-like) branch, scaled by $δ$ and offset by $- δ^{2} / 2$ .

The slide [slide_004, 4:43] lists exactly the four properties we just motivated:

Quadratic for small errors (like MSE) — smooth, fast convergence near optimum
Linear for large errors (like MAE) — robust to outliers
Differentiable everywhere (unlike MAE)
$δ$ controls the transition point between quadratic and linear regimes

Derivation — why those specific constants?

The slide asserts "differentiable everywhere". Let's prove it, because the proof explains where the $\frac{δ}{2}$ came from.

Write $e = y - \hat{y}$ and check the boundary $e = δ$ from both sides.

Continuity — do the two pieces meet?

Quadratic branch at $e = δ$ : $\frac{1}{2} δ^{2}$
Linear branch at $e = δ$ : $δ (δ - \frac{δ}{2}) = δ \cdot \frac{δ}{2} = \frac{δ^{2}}{2}$

Equal. ✓ No jump.

Differentiability — do the slopes match?

Quadratic branch: $\frac{d}{d e} [\frac{1}{2} e^{2}] = e$ , which at $e = δ$ equals $δ$ .
Linear branch (for $e > 0$ ): $\frac{d}{d e} [δ (e - \frac{δ}{2})] = δ$ .

Equal. ✓ No kink. Huber is $C^{1}$ — continuous with a continuous first derivative — everywhere. ∎

The gradient — and here is the practical payoff:

\frac{\partial ℒ_{δ}}{\partial e} = {\begin{matrix} e & | e | \leq δ \\ δ \cdot sign (e) & | e | > δ \end{matrix}

The gradient is capped at $\pm δ$ . No matter how catastrophically wrong a single example is, it can never push the parameters harder than $δ$ . This is identical in effect to gradient clipping — a technique you'll meet again in deep learning, which clips the gradient (its norm, or elementwise its values) to a maximum threshold before it's used in the update step, so a single bad batch cannot throw the parameters an arbitrarily large distance. Huber achieves the same capping by construction, baked into the loss itself, rather than by that post-hoc surgery on the gradient.

🧪 Worked example

Four examples, residuals $e = [0.5, 1.5, 3, 10]$ , with $δ = 2$ .

$e$	$\| e \| \leq δ$ ?	Branch	Value
0.5	yes	$\frac{1}{2} {(0.5)}^{2}$	$0.125$
1.5	yes	$\frac{1}{2} {(1.5)}^{2}$	$1.125$
3	no	$2 (3 - 1)$	$4$
10	no	$2 (10 - 1)$	$18$

ℒ_{Huber} = \frac{0.125 + 1.125 + 4 + 18}{4} = \frac{23.25}{4} = 𝟓.𝟖𝟏𝟐𝟓

Compare, on the same residuals, using the matching $\frac{1}{2} e^{2}$ convention for MSE:

ℒ_{MSE} = \frac{0.125 + 1.125 + 4.5 + 50}{4} = \frac{55.75}{4} = 𝟏𝟑.𝟗𝟑𝟕𝟓

ℒ_{MAE} = \frac{0.5 + 1.5 + 3 + 10}{4} = \frac{15}{4} = 𝟑.𝟕𝟓

5.8125 sits between 3.75 and 13.9375, exactly as the design intends. And look where the difference comes from: the $e = 10$ point contributes 50 to MSE, 18 to Huber, 10 to MAE. Huber let that point matter — but not run the show.

Choosing δ

Too small → almost every residual is in the linear regime → Huber degenerates into MAE (times a constant), and you lose the smooth convergence you came for.
Too large → almost every residual is quadratic → Huber degenerates into MSE, and you lose robustness.
Practical rule: set $δ$ to roughly the level of error you consider "normal" — a common starting point is the median absolute residual of a quick baseline fit, or $1.345 \hat{σ}$ , which is the classical choice giving ~95% efficiency relative to MSE under genuinely Gaussian noise. ✅ Confirmed and corrected. The commonly-quoted constant is 1.345, not 1.35 (the file previously rounded it) — confirmed against Huber, "Robust Estimation of a Location Parameter", Annals of Mathematical Statistics 35(1), 1964, pp. 73–101, and the standard robust-statistics literature that cites the 95%-efficiency result from it.
Scale sensitivity: $δ$ is in the units of $y$ . If you rescale your target from dollars to cents, you must rescale $δ$ by 100. This catches people constantly.

Interactive · slider The delta dial

Concept: How δ interpolates Huber between MSE and MAE
Try: A slider for δ from 0.1 to 10, replicating the slide's own interactive figure [slide 5].
Watch: The Huber curve is drawn over fixed dashed MSE (½e²) and MAE (|e|) references, with the quadratic zone |e| ≤ δ shaded. As δ → 0 the Huber curve collapses onto MAE; as δ grows it hugs MSE.
Insight: δ is not a tuning nuisance — it is the literal dividing line between "this is noise I should learn from" and "this is an outlier I should cap".

The table in §4 — at δ=2 the residual e=10 contributes 50 under MSE, 18 under Huber, 10 under MAE.

Comparing MSE, MAE and Huber 3 min

Slide [raw slide_019, 7:03] gives this table directly. It is worth memorising as a unit.

	MSE	MAE	Huber
Penalty growth	Quadratic	Linear	Quadratic (small $r$ ), Linear (large $r$ )
Outlier sensitivity	High	Low	Low (controlled by $δ$ )
Differentiable	Yes	No (at 0)	Yes
Optimizes toward	Mean	Median	Mean (small errors) / Median-like (large errors)
Noise assumption	Gaussian	Laplacian	Gaussian core + heavy tails
Convergence	Fast	Slower (constant gradient)	Fast near optimum

Three extra rows the slide didn't include, which you should carry anyway:

	MSE	MAE	Huber
Units of the loss	$y^{2}$ (take $\sqrt{}$ → RMSE to fix)	same as $y$	mixed
Extra hyperparameter	none	none	$δ$
sklearn / PyTorch	`squared_error` / `nn.MSELoss`	`absolute_error` / `nn.L1Loss`	`huber` / `nn.HuberLoss(delta=)`

A decision procedure

Binary Cross-Entropy (BCE) 7 min

Regression is done. Classification needs an entirely different shape of loss, and the reason is worth stating before any formula: classifiers output probabilities, and you cannot score a probability with a squared error without breaking the gradient.

Words, then symbols

The formula says: for each example, look only at the probability the model assigned to the class that actually occurred, take its logarithm (which is a large negative number when the probability is small), and average the negatives of those.

ℒ_{BCE} = - \frac{1}{n} \sum_{i = 1}^{n} [y_{i} \log {\hat{p}}_{i} + (1 - y_{i}) \log (1 - {\hat{p}}_{i})]

Symbol	Read it as	What it means
$y_{i}$	"y sub i"	The true label, exactly 0 or 1.
${\hat{p}}_{i}$	"p-hat sub i"	The model's predicted probability that $y_{i} = 1$ . A number in $(0,1)$ .
$\log$	"log"	Natural logarithm (base $e$ ) throughout ML unless stated otherwise.
the minus sign	—	Turns a log-likelihood (which we'd maximise) into a loss (which we minimise).

The switch mechanism. Because $y_{i}$ is exactly 0 or 1, one of the two terms always vanishes:

If $y_{i} = 1$ : the bracket is $1 \cdot \log {\hat{p}}_{i} + 0 \cdot \log (1 - {\hat{p}}_{i}) = \log {\hat{p}}_{i}$ .
If $y_{i} = 0$ : the bracket is $0 + 1 \cdot \log (1 - {\hat{p}}_{i}) = \log (1 - {\hat{p}}_{i})$ .

So the formula is really just " $- \log$ (probability assigned to the correct class)", written in a way that avoids an if statement. Once you see that, BCE stops looking intimidating.

The slide's three claims

The slide [raw slide_022, 9:56] says BCE:

Heavily penalises confident wrong predictions.
Is equivalent to minimising negative log-likelihood.
Can be interpreted in terms of KL divergence.

Claim 1 is the shape of $- \log$ . As $\hat{p} \to 0$ , $- \log \hat{p} \to \infty$ . The slide's own worked numbers, which I've verified:

True label	Predicted $\hat{p}$	Loss $= - \log \hat{p}$
1	0.01	$- \log (0.01) = 𝟒.𝟔𝟎𝟓$
1	0.99	$- \log (0.99) = 𝟎.𝟎𝟏𝟎𝟎𝟓$

Being confidently wrong costs 458× more than being confidently right saves. That asymmetry is deliberate: a classifier that says "99% sure" had better be right 99% of the time.

Claim 2 — the derivation. A binary label is a Bernoulli random variable: it takes value 1 with probability $p$ and 0 with probability $1 - p$ . Its probability mass function can be written in one line, using the same exponent trick as above:

P (y | \hat{p}) = {\hat{p}}^{y} {(1 - \hat{p})}^{1 - y}

(Check: $y = 1$ gives ${\hat{p}}^{1} {(1 - \hat{p})}^{0} = \hat{p}$ ✓; $y = 0$ gives ${\hat{p}}^{0} {(1 - \hat{p})}^{1} = 1 - \hat{p}$ ✓.)

Log-likelihood over the dataset:

\log ℒ = \sum_{i} [y_{i} \log {\hat{p}}_{i} + (1 - y_{i}) \log (1 - {\hat{p}}_{i})]

Negate, divide by $n$ , and that is exactly $ℒ_{BCE}$ . ∎

Claim 3 needs three definitions the slide never gives.

📚Background

Background the slide assumed — entropy, cross-entropy, KL divergence.

Entropy $H (p) = - \sum_{c} p_{c} \log p_{c}$ — the average number of nats (bits, if you use $\log_{2}$ ) needed to encode outcomes drawn from $p$ , using the best possible code for $p$ . It measures genuine uncertainty. A fair coin has $H = \log 2 \approx 0.693$ nats; a two-headed coin has $H = 0$ .

Cross-entropy $H (p, q) = - \sum_{c} p_{c} \log q_{c}$ — the average code length when the truth is $p$ but you built your code assuming $q$ . Always $\geq H (p)$ , with equality only when $q = p$ .

KL divergence $D_{KL} (p ∥ q) = H (p, q) - H (p) = \sum_{c} p_{c} \log \frac{p_{c}}{q_{c}}$ — the excess code length you pay for being wrong about the distribution. It is $\geq 0$ , and $= 0$ only when $p = q$ . It is not symmetric: $D_{KL} (p ‖ q) \neq D_{KL} (q ‖ p)$ , so it is not a distance despite constantly being described as one.

Why this makes claim 3 true: in supervised learning the "true distribution" $p$ for one example is a point mass — all probability on the observed label. For a point mass, $H (p) = 0$ . Therefore

D_{KL} (p ∥ \hat{p}) = H (p, \hat{p}) - \underset{= 0}{\underset{⏟}{H (p)}} = H (p, \hat{p})

Minimising cross-entropy is minimising KL divergence, exactly, because the entropy term is a constant zero. That is the whole content of claim 3. (If your labels are soft — from label smoothing or distillation — then $H (p) \neq 0$ and the two differ by that constant, which still doesn't change the minimiser.)

🧪 Worked example

Three examples: $y = [1, 0, 1]$ , $\hat{p} = [0.9, 0.2, 0.4]$ .

$i$	$y_{i}$	${\hat{p}}_{i}$	probability of the true class	contribution $- \log (\cdot)$
1	1	0.9	$0.9$	$0.10536$
2	0	0.2	$1 - 0.2 = 0.8$	$0.22314$
3	1	0.4	$0.4$	$0.91629$

ℒ_{BCE} = \frac{0.10536 + 0.22314 + 0.91629}{3} = \frac{1.24479}{3} = 𝟎.𝟒𝟏𝟒𝟗𝟑

Note example 3: the model said 40% for a positive — not confidently wrong, just wrong — and it contributes more than the other two combined.

📚 The gradient, and the miracle that makes it work

This is the most important thing in the section and no slide mentions it.

A binary classifier produces a raw score $z$ (a logit, any real number) and squashes it through the sigmoid to get a probability:

\hat{p} = σ (z) = \frac{1}{1 + e^{- z}}

Now differentiate BCE with respect to the logit $z$ , not the probability. Using $\frac{d σ}{d z} = σ (1 - σ)$ :

\frac{\partial ℒ}{\partial z} = \frac{\partial ℒ}{\partial \hat{p}} \cdot \frac{\partial \hat{p}}{\partial z} = (\frac{- y}{\hat{p}} + \frac{1 - y}{1 - \hat{p}}) \cdot \hat{p} (1 - \hat{p})

Expand the product:

= - y (1 - \hat{p}) + (1 - y) \hat{p} = - y + y \hat{p} + \hat{p} - y \hat{p} = \hat{p} - y

Interactive · slider The cost of confidence

Concept: Why BCE punishes confident errors asymptotically
Try: A slider for the predicted probability p̂ from 0.001 to 0.999, mirroring the slide's own figure [slide 10].
Watch: Two curves — loss if the true label is 1 (−log p̂) and loss if it is 0 (−log(1−p̂)) — with the current point marked and both losses displayed numerically.
Insight: The curve is finite and flat in the middle but vertical at the ends. There is no upper bound on the cost of being certain and wrong.

The table in §6 — p̂=0.01 with y=1 costs 4.605; p̂=0.99 with y=1 costs 0.01005.

Cross-Entropy Loss (CE) and softmax 5 min

Words, then symbols

BCE handles two classes. Cross-entropy generalises it to $C$ classes.

The formula says: for every example and every class, multiply the true indicator for that class by the log of the predicted probability for that class, add them all up, negate, and average. Because the true indicator is 1 for exactly one class and 0 elsewhere, this is again just "minus the log of the probability you gave the right answer".

ℒ_{CE} = - \frac{1}{n} \sum_{i = 1}^{n} \sum_{c = 1}^{C} y_{i, c} \log {\hat{p}}_{i, c}

Symbol	Read it as	What it means
$C$	"C"	Number of classes.
$y_{i, c}$	"y sub i,c"	1 if example $i$ truly belongs to class $c$ , else 0. This vector across $c$ is the one-hot encoding.
${\hat{p}}_{i, c}$	"p-hat sub i,c"	Predicted probability that example $i$ is class $c$ . Must sum to 1 across $c$ .

Because exactly one $y_{i, c}$ is 1, the inner sum collapses to a single term, and CE with $C = 2$ is algebraically identical to BCE. They are the same loss.

Softmax — where the probabilities come from

A network's final layer outputs $C$ raw scores $z_{1}, \dots, z_{C}$ (logits), which can be any real numbers — negative, huge, whatever. Cross-entropy needs probabilities. Softmax is the converter.

The formula says: exponentiate every score so they're all positive, then divide each by the total so they sum to one.

{\hat{p}}_{c} = softmax {(z)}_{c} = \frac{e^{z_{c}}}{\sum_{j = 1}^{C} e^{z_{j}}}

Symbol	Read it as	What it means
$z_{c}$	"z sub c"	The raw logit for class $c$ .
$e^{z_{c}}$	"e to the z_c"	Makes it positive, and amplifies differences — a logit 2 larger becomes $e^{2} \approx 7.4 \times$ larger.
$\sum_{j} e^{z_{j}}$	"the partition function"	The normaliser. Guarantees the outputs sum to 1.

🧪 Worked example

Three classes, logits $z = (2.0, 1.0, 0.1)$ , true class is class 1 (the first one).

Step 1 — exponentiate.

e^{2.0} = 7.389, e^{1.0} = 2.718, e^{0.1} = 1.105

Step 2 — sum.

7.389 + 2.718 + 1.105 = 11.212

Step 3 — divide.

\hat{p} = (\frac{7.389}{11.212}, \frac{2.718}{11.212}, \frac{1.105}{11.212}) = (𝟎.𝟔𝟓𝟗𝟎, 𝟎.𝟐𝟒𝟐𝟒, 𝟎.𝟎𝟗𝟖𝟔)

(Sum: $0.6590 + 0.2424 + 0.0986 = 1.0000$ ✓)

Step 4 — the loss is $- \log$ of the probability given to the true class:

ℒ_{CE} = - \log (0.6590) = 𝟎.𝟒𝟏𝟕𝟎

Sanity anchors worth memorising: a uniform prediction over $C$ classes gives loss $\log C$ . For $C = 3$ that is $\log 3 = 1.0986$ . Our 0.4170 is well below it, so the model has learned something. For $C = 50,000$ (a language-model vocabulary) random guessing is $\log 50000 \approx 10.8$ — which is why "loss 10.8" is the number people quote for an untrained LLM.

📚 Two things about softmax that will be asked

Shift invariance. Adding the same constant $k$ to every logit changes nothing:

\frac{e^{z_{c} + k}}{\sum_{j} e^{z_{j} + k}} = \frac{e^{k} e^{z_{c}}}{e^{k} \sum_{j} e^{z_{j}}} = \frac{e^{z_{c}}}{\sum_{j} e^{z_{j}}}

This is not a curiosity — it is the fix for numerical overflow. If your logits are around 1000, $e^{1000}$ is inf. Every implementation therefore subtracts $\max_{j} z_{j}$ first, making the largest exponent exactly $e^{0} = 1$ . That is the log-sum-exp trick, and it is why you should call F.log_softmax rather than log(softmax(x)).

Temperature. Divide logits by $T$ before the softmax: ${\hat{p}}_{c} \propto e^{z_{c} / T}$ .

$T < 1$ sharpens the distribution toward the argmax (more confident, more deterministic).
$T > 1$ flattens it (more uncertain, more diverse).
$T \to 0$ recovers a hard argmax; $T \to \infty$ recovers uniform.

You will meet this again as the sampling temperature in LLMs and as the softening parameter in knowledge distillation.

Hinge Loss 6 min

The problem it solves

BCE asks the model to output a well-calibrated probability. But often you don't need a probability — you need a decision, with a comfortable safety buffer. Hinge loss is the loss for that, and it is the loss that defines the SVM (§23).

Words, then symbols

The formula says: if the example is on the correct side of the boundary by a comfortable distance, charge nothing at all. Otherwise charge in proportion to how far short of comfortable it falls.

ℒ_{hinge} = \frac{1}{n} \sum_{i = 1}^{n} \max (0, 1 - y_{i} \cdot f (x_{i}))

with, as the slide states, $y_{i} \in {- 1, + 1}$ and $f (x_{i}) = 𝐰^{⊤} x_{i} + b$ .

Symbol	Read it as	What it means
$y_{i} \in {- 1, + 1}$	—	The label convention changes here: not ${0,1}$ but ${- 1, + 1}$ .
$f (x_{i})$	"f of x i"	The raw signed score. Positive → predict class $+ 1$ . Its sign is the prediction; its magnitude is the confidence.
$y_{i} \cdot f (x_{i})$	"the functional margin"	Positive when the prediction is correct, negative when wrong, and larger when more confident.
$\max (0, \cdot)$	"the hinge"	Clamps negatives to zero — this is what creates the flat region.

The slide's four bullets

Slide [slide_008, 10:39] states:

Zero loss when $y_{i} \cdot f (x_{i}) \geq 1$ (correct with sufficient margin)
Not differentiable at the hinge point.
Encourages a margin between classes.
Sparse solution: only support vectors contribute to gradient.

Bullet 1 — the "1" is the point. Note that the threshold is not 0. Getting the sign right (margin > 0) is not enough; the loss keeps pushing until the margin exceeds 1. That gap between 0 and 1 is the safety buffer, and it is where the word "margin" comes from.

Bullet 2 — at $y f (x) = 1$ exactly, the function switches from a downward slope of $- 1$ to a flat 0. Same sub-gradient story as MAE (§3). Handled identically.

Bullet 3 follows from bullet 1: because loss is only zero past margin 1, the optimiser is actively rewarded for pushing points away from the boundary, not merely onto the right side.

Bullet 4 — the sparsity result, derived. The gradient with respect to $𝐰$ is:

\frac{\partial}{\partial 𝐰} \max (0, 1 - y_{i} f (x_{i})) = {\begin{matrix} - y_{i} x_{i} & if y_{i} f (x_{i}) < 1 \\ 𝟎 & if y_{i} f (x_{i}) > 1 \end{matrix}

Exactly zero for every comfortably-correct point. Those points contribute nothing to the update — you could delete them from the training set and get the identical model. The only points that matter are those with $y_{i} f (x_{i}) \leq 1$ : the ones on or inside the margin. Those are the support vectors. ∎

The comparison with logistic loss

The slide's own comparison, verbatim:

Hinge is "flat" for well-classified points; logistic loss always has a nonzero gradient → hinge produces sparser models.

This is worth sitting with, because it explains a real architectural difference between SVMs and logistic regression.

	Hinge	Logistic (BCE)
Loss at margin 5	exactly 0	$\log (1 + e^{- 5}) \approx 0.0067$ — small but not zero
Gradient at margin 5	exactly 0	$\approx - 0.0067$ — tiny but not zero
Effect	far-away points are ignored entirely	far-away points keep nudging the boundary forever
Result	solution depends only on support vectors	solution depends on all $n$ points
Output	a score; no calibrated probability	a calibrated probability

🧪 Worked example

$y$	$f (x)$	margin $y f (x)$	$1 - y f (x)$	$\max (0, \cdot)$	reading
$+ 1$	$2.0$	$+ 2.0$	$- 1.0$	$𝟎$	correct, comfortably — free
$+ 1$	$0.5$	$+ 0.5$	$+ 0.5$	$𝟎.𝟓$	correct, but inside the margin — still charged
$+ 1$	$- 0.3$	$- 0.3$	$+ 1.3$	$𝟏.𝟑$	wrong
$- 1$	$- 2.0$	$+ 2.0$	$- 1.0$	$𝟎$	correct, comfortably — free
$- 1$	$0.3$	$- 0.3$	$+ 1.3$	$𝟏.𝟑$	wrong

ℒ_{hinge} = \frac{0 + 0.5 + 1.3 + 0 + 1.3}{5} = \frac{3.1}{5} = 𝟎.𝟔𝟐

Row 2 is the row to study: the model got that example right and was still penalised. No other loss in this lecture does that. It is the entire idea of a margin.

(The slide's own interactive figure shows exactly this case: $y \cdot f (x) = 0.50$ , hinge loss $0.500$ , "Classified correctly? Yes", "Inside margin? Yes".)

Part 2 — Optimisation & Solvers

The optimisation problem 7 min

Slide [slide_010, 12:46] states the goal:

Goal: Find parameters $θ^{*}$ that minimize the empirical risk.

θ^{*} = \arg \min_{θ} \frac{1}{n} \sum_{i = 1}^{n} ℒ (y_{i}, f (x_{i}; θ))

Symbol	Read it as	What it means
$\arg \min_{θ}$	"arg min over theta"	Not the minimum value — the $θ$ at which the minimum occurs.
$θ^{*}$	"theta star"	The optimal parameters. The star always means "the best one".
$\frac{1}{n} \sum_{i} ℒ (\cdot)$	"the empirical risk"	Average loss over the training data.

📚Background

Background the slide assumed — Empirical Risk Minimisation (ERM), and its central flaw. What you want is the parameters minimising true risk — expected loss over the real distribution of listings/customers/queries you'll face in production. You cannot compute it; you have a finite sample. So you minimise the empirical risk on that sample and hope it transfers.

This hope is exactly what fails when you overfit. Empirical risk goes to zero, true risk goes up, because the parameters started explaining the sample's noise rather than its signal. The defences — regularisation, early stopping, validation sets, cross-validation — all exist to patch this one gap, and the gap is created the moment you write " $\frac{1}{n} \sum_{i}$ " instead of " $𝔼$ ".

Overfitting — training loss low, validation loss high. Model memorised.
Underfitting — both high. Model too simple, or trained too little.

💡 These are symptoms, not mechanism. This is exactly the bias/variance trade-off — underfitting is high bias, overfitting is high variance — the full mechanism behind why is in §21.

objective (θ) = \underset{fit the data}{\underset{⏟}{\frac{1}{n} \sum_{i} ℒ (y_{i}, f (x_{i}; θ))}} + \underset{stay simple}{\underset{⏟}{λ R (θ)}}

Symbol Read it as What it means

$R (θ)$ "the regulariser" A function that grows as $θ$ grows in whatever sense you pick.

$λ$ "lambda" Hyperparameter trading fit against simplicity. $λ = 0$ is plain ERM (above); $λ \to \infty$ ignores the data entirely.

L2 regularisation sets $R (θ) = ‖ θ ‖_{2}^{2} = \sum_{j} θ_{j}^{2}$ . Its gradient is $2 θ$ — a force pulling every weight toward zero, in proportion to its own size: big weights feel a big pull, small weights a small one, and a weight already at exactly 0 feels none. Result: weights shrink uniformly and smoothly, the fitted function can no longer lean hard on any single feature, and — per the bias-variance decomposition in §21 — that smoothness trades a little bias for a lot less variance. That is the entire mechanism behind "regularisation prevents overfitting": a deliberate, tunable amount of bias, bought to reduce variance.

L1 regularisation sets $R (θ) = ‖ θ ‖_{1} = \sum_{j} | θ_{j} |$ . Its gradient is $\pm 1$ regardless of the weight's size — the same constant-magnitude shape as MAE's gradient (§3) — strong enough to push small weights all the way to exactly zero. That's why L1 produces sparse models (many weights exactly 0 — automatic feature selection) while L2 only ever produces small, non-zero weights.

This is the general story. You'll see this exact $λ \cdot R (θ)$ shape three more times in this lecture — Ridge regression a few paragraphs below, AdamW's weight decay in §13, and the SVM objective in §23 — each time applied to a different problem, never re-derived from scratch.

The slide then names the two families and asks the organising question:

Two broad approaches:

Closed-form (Normal Equation) — exact solution, limited to specific forms

Iterative (Gradient-based) — general purpose, scalable

Key question: How much data do we use to compute the gradient at each step?

All data → Batch Gradient Descent

One sample → Stochastic Gradient Descent (SGD)

m samples → Mini-batch SGD

That "key question" is the spine of the next four sections. Everything is one trade-off: gradient accuracy versus gradient cost.

📚 The closed-form solution, and why we abandon it

The slide names the normal equation and moves on. Here it is, derived, because knowing why it fails is what justifies everything after it.

For linear regression with MSE, write the data as a matrix $X$ ( $n \times d$ ) and targets as a vector $y$ . The cost is $‖ y - X w ‖^{2}$ . Expand:

ℒ (w) = {(y - X w)}^{⊤} (y - X w) = y^{⊤} y - 2 w^{⊤} X^{⊤} y + w^{⊤} X^{⊤} X w

Differentiate with respect to $w$ and set to zero:

\nabla_{w} ℒ = - 2 X^{⊤} y + 2 X^{⊤} X w = 0 ⟹ X^{⊤} X w = X^{⊤} y

w^{*} = {(X^{⊤} X)}^{- 1} X^{⊤} y

This is the normal equation, and it is the exact global optimum in one shot — no learning rate, no iterations, no convergence criterion. It is also, in the slide's words, "limited to specific forms". Three reasons it doesn't scale:

Cost. $X^{⊤} X$ is $d \times d$ ; inverting it is $O (d^{3})$ . With $d = 100,000$ features (a bag-of-words model, say) that is $10^{15}$ operations. Not happening.
Memory. You must hold $X^{⊤} X$ : $d^{2}$ numbers. At $d = 100,000$ in float32 that's 40 GB.
Existence. ${(X^{⊤} X)}^{- 1}$ requires $X^{⊤} X$ to be invertible. It is not, whenever two features are perfectly correlated or $d > n$ . Both are routine.

Ridge regression is the fix for (3). It adds exactly the L2 penalty defined in the regularisation background box above — here is the numerical bonus that comes free with the statistical one:

w_{ridge}^{*} = {(X^{⊤} X + λ I)}^{- 1} X^{⊤} y

Adding $λ I$ inflates every diagonal entry, which guarantees invertibility for any $λ > 0$ . The regulariser you added to prevent overfitting also fixed your linear algebra. That is not a coincidence — both problems are the same problem (directions in which the data carries no information).

And crucially: the normal equation only exists because MSE + linear model happens to have a closed-form stationary point. Change the loss to MAE, or the model to a neural network, and there is no such formula. Iterative methods work for everything. That is why the rest of the lecture — and essentially all of modern ML — is about them.

Batch Gradient Descent 6 min

Words, then symbols

Slide [slide_011, 14:16] states it directly:

We take a small step in the direction of the negative gradient.

𝐰^{t} \leftarrow 𝐰^{t - 1} - η \nabla L (𝐰^{t - 1})

Symbol	Read it as	What it means
$𝐰^{t}$	"w at step t"	Parameters after update $t$ . Superscript is an iteration counter, not an exponent.
$\leftarrow$	"is assigned"	Assignment, not equality.
$η$	"eta"	The learning rate: how far to step. The slide notes $η > 0$ .
$\nabla L (𝐰^{t - 1})$	"gradient of L at w"	Direction of steepest increase, computed at the current parameters.
the minus sign	—	Why we go downhill. Delete it and you have gradient ascent.

The slide's code:

for epoch in range(n_epochs):
    dw = gradient(loss, data, w)   # ← uses ALL of `data`
    w  = w - lr * dw

And its verdict: "Each step requires that the entire training data be processed to compute the gradient. For large datasets this is not computationally efficient."

🧪 Worked example — five steps by hand

Minimise $L (w) = {(w - 3)}^{2}$ . Gradient: $\nabla L = 2 (w - 3)$ . Take $η = 0.1$ , start at $w^{0} = 0$ .

$t$	$w^{t - 1}$	$\nabla L = 2 (w - 3)$	$η \nabla L$	$w^{t}$	distance to 3
1	0	$- 6$	$- 0.6$	$𝟎.𝟔$	2.4
2	0.6	$- 4.8$	$- 0.48$	$𝟏.𝟎𝟖$	1.92
3	1.08	$- 3.84$	$- 0.384$	$𝟏.𝟒𝟔𝟒$	1.536
4	1.464	$- 3.072$	$- 0.3072$	$𝟏.𝟕𝟕𝟏𝟐$	1.2288
5	1.7712	$- 2.4576$	$- 0.24576$	$𝟐.𝟎𝟏𝟔𝟗𝟔$	0.98304

Look at the last column: $2.4, 1.92, 1.536, 1.2288, 0.98304$ . Each is exactly $0.8 \times$ the one before. That is not a coincidence.

Derivation — the learning rate divergence threshold

Subtract 3 from both sides of the update to track the error $e^{t} = w^{t} - 3$ :

e^{t} = e^{t - 1} - η \cdot 2 e^{t - 1} = (1 - 2 η) e^{t - 1}

So the error is multiplied by $(1 - 2 η)$ every step. Three regimes:

Condition	$\| 1 - 2 η \|$	Behaviour
$0 < η < 0.5$	$< 1$ , positive	smooth convergence (our case: $1 - 0.2 = 0.8$ ✓)
$η = 0.5$	$0$	converges in one step
$0.5 < η < 1$	$< 1$ , negative	converges while oscillating across the minimum
$η = 1$	$= 1$	oscillates forever between two points, never converging
$η > 1$	$> 1$	diverges

Generalising: for a quadratic with second derivative $L^{''}$ , the update multiplier is $(1 - η L^{''})$ , so convergence requires

η < \frac{2}{L^{''}}

For a general multi-dimensional loss, $L^{''}$ becomes the largest eigenvalue of the Hessian (the matrix of all second derivatives), often written $L$ and called the smoothness constant. The condition $η < 2 / L$ is one of the most-quoted results in optimisation.

⚠️Careful

Learning-rate failure modes, and how to recognise them from a loss curve:

Symptom	Cause	Fix
Loss decreases painfully slowly, nearly linear	$η$ far too small	raise by 3–10×
Loss decreases then plateaus high	$η$ slightly too small, or a real local structure	LR schedule; check the data
Loss oscillates but trends down	$η$ near the stability edge	halve it
Loss goes to `NaN` within a few steps	$η > 2 / L$ ; gradients exploded	drop 10×, add gradient clipping

The standard practical recipe is an LR range test: train for a few hundred steps while exponentially increasing $η$ , plot loss against $η$ , and pick roughly an order of magnitude below where it turns upward.

📚Background

Background the slide assumed — what "till convergence" actually means. The slide says the update "is repeated multiple times (till covergence)" [sic] and never defines it. In code, you stop when one of these fires:

Max iterations — a hard budget. Always have one.
Gradient norm $‖ \nabla L ‖ < ϵ$ — you're at a flat point. The most principled test.
Parameter change $‖ w^{t} - w^{t - 1} ‖ < ϵ$ — you've stopped moving.
Loss change $| L^{t} - L^{t - 1} | < ϵ$ — cheapest, and the most misleading: a plateau on a saddle looks identical to a minimum.
Early stopping on validation loss — stop when validation loss stops improving for patience epochs. This is the one you actually use in practice, because it targets generalisation rather than optimisation.

⚠️ The patience trap: with patience=1 you'll stop on the first noisy uptick. Typical values are 5–20 epochs, and you must restore the best checkpoint, not the last one — otherwise you keep the worse model you trained during the patience window.

Stochastic Gradient Descent (SGD) 4 min

The setup the slide gives

Slide [slide_012, 15:57]:

In general most loss functions can be written as sum over each training instance.

L (𝐰) = \sum_{i = 1}^{N} L_{i} (𝐰)

In Stochastic Gradient Descent (SGD) we update the parameters one data point at a time.

𝐰^{t} \leftarrow 𝐰^{t - 1} - η \nabla L_{i} (𝐰^{t - 1})

A complete passthrough of the whole dataset is called an epoch.

That first line is the enabling observation. Because the total loss decomposes as a sum over examples, its gradient decomposes too:

\nabla L (𝐰) = \sum_{i = 1}^{N} \nabla L_{i} (𝐰)

So one example's gradient is a sample of the full gradient. That is the entire justification.

Why a single noisy sample works — the unbiasedness argument

The slide asserts SGD works but doesn't say why it's legitimate. Here's the one-line reason.

If you pick index $i$ uniformly at random, the expected value of the single-example gradient is:

𝔼_{i} [\nabla L_{i} (𝐰)] = \frac{1}{N} \sum_{i = 1}^{N} \nabla L_{i} (𝐰) = \frac{1}{N} \nabla L (𝐰)

The stochastic gradient is an unbiased estimator of the true gradient (up to the constant $1 / N$ , absorbed into $η$ ). It is wrong on every individual step, but right on average. Over many steps the errors cancel and you move in the correct direction — for $1 / N$ of the compute per step.

The cost, which the slide states plainly

SGD is much faster and more computationally efficient, but it has noise in the estimation of the gradient. Since it updates the weight frequently, it can lead to big oscillations and that makes the training process highly unstable.

Both halves are true and both matter. The noise is not purely a cost, though:

The slide's code makes the structure explicit:

for epoch in range(n_epochs):
    for i in range(n_data):
        dw = gradient(loss, data[i], w)   # ← ONE example
        w  = w - lr * dw

Mini-batch Stochastic Gradient Descent 6 min

Slide [raw slide_042, 18:51] — one of the slides missing from the deduped set, and the single most practically important slide in the optimisation section, because this is what everyone actually runs.

Using a single example results in a very noisy estimate of the gradient. So we use a small random subset of data called mini-batch of size $B$ (batch size) to compute the gradient.

𝐰^{t} \leftarrow 𝐰^{t - 1} - η \nabla L_{b a t c h} (𝐰^{t - 1})

Mini-batch SGD is the most commonly used method and is sometimes referred to as just SGD. Typical choices of the batch size are $B = 32, 64, 128, 256, \dots$ In practice we do a random shuffle of the data per epoch. In practice, mini-batch SGD is the most frequently used variation because it is both computationally cheap and results in more robust convergence.

for epoch in range(n_epochs):
    for mini_batch in get_batches(data, batch_size):
        dw = gradient(loss, mini_batch, w)
        w  = w - lr * dw

The three things this slide is really telling you

1. Batch size is the noise dial, and the law is $1 / \sqrt{B}$ .

Averaging $B$ independent unbiased estimates reduces the standard deviation of the estimate by $\sqrt{B}$ :

std (\frac{1}{B} \sum_{i = 1}^{B} g_{i}) = \frac{σ}{\sqrt{B}}

$B$	Gradient noise vs $B = 1$	Compute vs $B = 1$
1	$1.00 \times$	$1 \times$
32	$0.177 \times$	$32 \times$
128	$0.088 \times$	$128 \times$
1024	$0.031 \times$	$1024 \times$

Going from 32 to 1024 costs 32× the compute for 5.7× less noise. That diminishing return is exactly why batch sizes settle in the hundreds and not the millions.

2. Why the sizes are powers of two. $B \in {32, 64, 128, 256}$ is not superstition. GPUs execute in fixed-width warps (32 threads on NVIDIA hardware) and their matrix kernels are tiled to power-of-two shapes. A batch of 32 and a batch of 33 take nearly the same wall-clock time; the 33rd example is close to free but forces a second, almost-empty tile. Mini-batching is the operation that turns a sequence of vector operations into one matrix multiply, which is the only reason GPUs help with training at all.

3. Why shuffle every epoch. If your data is sorted by label — all the class-0 examples first — then without shuffling, every batch in the first half is pure class 0. The model will lurch toward predicting 0, then lurch back. Shuffling makes each mini-batch a representative sample, which is exactly the condition the unbiasedness argument in §11 requires. Reshuffling each epoch also prevents the model from memorising a fixed batch composition.

💡Key insight

The linear scaling rule. When you increase batch size by $k$ , multiply the learning rate by $k$ as well. Reasoning: each step's gradient is $\sqrt{k}$ times less noisy but you're taking $k$ times fewer steps per epoch, so to cover the same distance you need proportionally larger steps. In practice this holds well up to a few thousand and then breaks, requiring a warmup period (start with a small $η$ and ramp up over the first few hundred steps) to avoid diverging early while the gradients are still large and uninformative. ✅ Confirmed — Goyal, Dollár, Girshick, Noordhuis, Wesolowski, Kyrola, Tulloch, Jia & He, "Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour", arXiv:1706.02677 (2017). The paper's own warmup schedule ramps over the first 5 epochs, not a few hundred steps — the shorter warmup window this file states is the more commonly used convention in later practice, not a claim about this specific paper's exact numbers.

The three-way comparison

	Batch GD	SGD ( $B = 1$ )	Mini-batch SGD
Gradient per step	exact	very noisy	moderately noisy
Updates per epoch	1	$N$	$N / B$
Memory per step	whole dataset	one example	$B$ examples
GPU utilisation	good but rarely fits	terrible (no parallelism)	excellent
Escapes saddles/shallow minima	no	yes	yes
Convergence path	smooth	very jagged	moderately smooth
In practice	almost never	almost never	always

Interactive · simulator Three descents on one surface

Concept: The variance/cost trade-off between batch, stochastic and mini-batch gradient descent
Try: Choose batch size B ∈ {1, 8, 32, full} and learning rate; press run.
Watch: Three trajectories trace over a contour plot of a 2-D loss surface with a narrow valley — batch GD glides smoothly, B=1 scribbles wildly, B=32 sits between. A counter shows updates-per-epoch and wall-clock estimate alongside.
Insight: B=1 reaches the neighbourhood of the optimum in the fewest gradient computations but never settles; batch GD settles precisely but takes one step per epoch. B=32 is not a compromise — it is strictly better on a GPU than either.

The 1/√B table in §12 and the three-way comparison table above it.

Improvements: momentum, adaptive rates, and schedules 12 min

Slide [slide_013, 20:17] is a bare list of names:

One of the basic improvements over SGD comes from adding a momentum term.

Different learning rate for each parameter: Adagrad, RMSProp

Combine momentum with adaptive learning rate: Adam, AdamW, Muon, SOAP

Learning rate schedule: Cosine annealing

Eight names, zero explanation. This section is that explanation. They form a clean lineage where each one fixes the previous one's specific failure.

The problem all of them solve

Plain SGD uses one learning rate for every parameter and has no memory of previous steps. Both are bad:

No memory → in a long narrow valley (a badly conditioned loss surface), the gradient points mostly across the valley, not along it. You zig-zag between the walls and creep along the floor.
One rate for all → a parameter that appears in every example (say, a bias) and a parameter that appears in one example in ten thousand (a rare word's embedding) get the same step size. The rare one barely ever learns.

Momentum — fixing "no memory"

The formula says: keep a running average of recent gradients, and step along that instead of the raw gradient.

v^{t} = β v^{t - 1} + \nabla L (𝐰^{t - 1}) 𝐰^{t} = 𝐰^{t - 1} - η v^{t}

Symbol	Read it as	What it means
$v^{t}$	"velocity"	The accumulated direction. Initialised to $𝟎$ .
$β$	"beta"	Decay factor, typically 0.9. How much of the past to keep.

The physical analogy is exact: a ball rolling downhill has inertia. Consistent gradient components (down the valley floor) accumulate and grow; oscillating components (across the valley) cancel against their own past and shrink.

How much speedup? If the gradient were constant $g$ , the velocity converges to the geometric series $v_{\infty} = g (1 + β + β^{2} + \dots) = \frac{g}{1 - β}$ . At $β = 0.9$ that is $𝟏𝟎 𝐠$ — a 10× effective step size in consistent directions, and no speedup at all in directions that keep flipping sign. That is exactly the selectivity you wanted.

Nesterov momentum is a refinement: evaluate the gradient at $𝐰^{t - 1} - η β v^{t - 1}$ — i.e. where momentum is about to take you — rather than where you currently are. It is a "look-ahead" correction that lets the ball start braking before it overshoots.

Adagrad — fixing "one rate for all"

The formula says: divide each parameter's step by the square root of the total squared gradient it has accumulated so far. Parameters that have been updated a lot get small steps; rarely-updated ones keep large steps.

G_{j}^{t} = G_{j}^{t - 1} + {(\nabla L_{j})}^{2} w_{j}^{t} = w_{j}^{t - 1} - \frac{η}{\sqrt{G_{j}^{t}} + ϵ} \nabla L_{j}

Symbol	Read it as	What it means
$G_{j}^{t}$	"G sub j"	Running sum of squared gradients for parameter $j$ only.
$ϵ$	"epsilon"	A tiny constant ( $10^{- 8}$ ) preventing division by zero.

This was a genuine breakthrough for sparse data — NLP with bag-of-words features, recommender systems with rare item IDs.

Its fatal flaw: $G$ is a sum and gradients are squared, so $G$ only ever increases. The effective learning rate $η / \sqrt{G}$ therefore decays monotonically toward zero, and on a long training run learning stops entirely — even if you haven't converged.

RMSProp — fixing Adagrad's decay

One change: make $G$ an exponentially weighted moving average instead of a sum, so old gradients are forgotten.

G_{j}^{t} = ρ G_{j}^{t - 1} + (1 - ρ) {(\nabla L_{j})}^{2}, ρ \approx 0.9

Now $G$ tracks the recent gradient magnitude and can go down as well as up. Learning never dies.

Adam — combining both

Adam = momentum (a running average of the gradient) + RMSProp (a running average of the squared gradient). "Adam" is short for Adaptive Moment Estimation, and the two "moments" are exactly those two averages.

m^{t} = β_{1} m^{t - 1} + (1 - β_{1}) \nabla L (1st moment — the mean, i.e. momentum)

v^{t} = β_{2} v^{t - 1} + (1 - β_{2}) {(\nabla L)}^{2} (2nd moment — uncentred variance, i.e. RMSProp)

{\hat{m}}^{t} = \frac{m^{t}}{1 - β_{1}^{t}}, {\hat{v}}^{t} = \frac{v^{t}}{1 - β_{2}^{t}} (bias correction)

𝐰^{t} = 𝐰^{t - 1} - η \frac{{\hat{m}}^{t}}{\sqrt{{\hat{v}}^{t}} + ϵ}

Defaults: $β_{1} = 0.9$ , $β_{2} = 0.999$ , $ϵ = 10^{- 8}$ , $η = 10^{- 3}$ .

🧪 Three Adam steps by hand. Say $\nabla L = 0.1$ at every step (constant gradient), $η = 0.001$ , defaults as above.

$t$	$m^{t}$	$v^{t}$	${\hat{m}}^{t}$	${\hat{v}}^{t}$	step $= η \hat{m} / (\sqrt{\hat{v}} + ϵ)$
1	$0.1 \cdot 0.1 = 0.01$	$0.001 \cdot 0.01 = 10^{- 5}$	$0.01 / 0.1 = 0.1$	$10^{- 5} / 0.001 = 0.01$	$0.001 \cdot 0.1 / 0.1 = 𝟎.𝟎𝟎𝟏$
2	$0.9 (0.01) + 0.01 = 0.019$	$0.999 (10^{- 5}) + 10^{- 5} = 1.999 \times 10^{- 5}$	$0.019 / 0.19 = 0.1$	$1.999 \times 10^{- 5} / 0.001999 = 0.01$	$𝟎.𝟎𝟎𝟏$
3	$0.9 (0.019) + 0.01 = 0.0271$	$\approx 2.997 \times 10^{- 5}$	$0.0271 / 0.271 = 0.1$	$\approx 0.01$	$𝟎.𝟎𝟎𝟏$

The step is exactly $η$ , every time. That is the defining property of Adam: for a constant gradient of any magnitude, the ratio $\hat{m} / \sqrt{\hat{v}}$ is 1, so the step is $η$ . Adam is nearly scale-invariant — multiply your loss by 1000 and Adam takes the same steps, while plain SGD would take 1000× larger ones. This is why Adam "just works" without tuning $η$ per problem, and it is the whole reason for its dominance.

AdamW — fixing Adam's weight decay

The bug. Recall from §9's regularisation background: L2 regularisation adds $λ ‖ w ‖^{2}$ to the loss precisely so its $2 λ w$ gradient term pulls every weight uniformly toward zero, in proportion to its own size. In Adam, that added term then goes through the $/ \sqrt{\hat{v}}$ division — so parameters with large historical gradients get less weight decay than parameters with small ones. That is the opposite of the intent: the pull toward zero was supposed to be uniform, not rescaled by each parameter's own gradient history.

The fix (AdamW). Decouple it — don't put decay in the gradient at all; subtract it directly from the weights after the Adam step:

𝐰^{t} = 𝐰^{t - 1} - η \frac{{\hat{m}}^{t}}{\sqrt{{\hat{v}}^{t}} + ϵ} - η λ 𝐰^{t - 1}

AdamW is the default for training transformers. If you use torch.optim.Adam with a weight_decay argument, you are getting the buggy coupled version; torch.optim.AdamW is what you want. This is a very common interview question and an even more common real-world bug.

Muon and SOAP

The slide names these two without comment. Be honest about what they are:

Muon — a recent optimiser that applies an orthogonalisation step (via a Newton–Schulz iteration) to the momentum matrix before updating weight matrices, treating them as matrices rather than flattened vectors. It has drawn attention for strong wall-clock results on transformer pre-training.
SOAP — a recent method connecting Shampoo-style second-order preconditioning with Adam, running Adam in the eigenbasis of a preconditioner.

✅ Confirmed via primary source. Muon ("MomentUm Orthogonalized by Newton-Schulz") was released by Keller Jordan in October 2024 (initially as a blog post / open-source implementation rather than a traditional peer-reviewed paper). SOAP is Vyas, Morwani, Zhao, Shapira, Brandfonbrener, Janson & Kakade, "SOAP: Improving and Stabilizing Shampoo using Adam", arXiv:2409.11321, published at ICLR 2025. What you can say safely, and what the slide's inclusion of them is signalling: optimiser design is not a solved, closed subject. Adam has been the default for a decade and is now being seriously challenged.

🎯 stretch — nice to know, not expected. An intern is not expected to know Muon or SOAP. Knowing that "the field is actively revisiting Adam, and matrix-aware/second-order methods are where the action is" is a better answer than a half-remembered equation.

Cosine annealing — the schedule

The learning rate need not be constant. Cosine annealing decays it along a cosine curve from $η_{\max}$ to $η_{\min}$ over $T$ steps:

η_{t} = η_{\min} + \frac{1}{2} (η_{\max} - η_{\min}) (1 + \cos \frac{π t}{T})

Check the endpoints: at $t = 0$ , $\cos 0 = 1$ so $η = η_{\max}$ ✓. At $t = T$ , $\cos π = - 1$ so $η = η_{\min}$ ✓.

Why a cosine rather than a straight line? The cosine is flat at both ends and steepest in the middle. So you get a long high-LR exploration phase early, a rapid transition, and a long low-LR refinement phase at the end — which is exactly the shape you want, and empirically beats linear decay and step decay on most large-scale training runs.

In practice it is paired with linear warmup: ramp $η$ from ~0 up to $η_{\max}$ over the first few hundred to few thousand steps, then cosine down. The warmup exists because early gradients are large and the Adam second-moment estimate $\hat{v}$ is still unreliable; a big step taken on a bad estimate can destabilise training permanently.

The family tree

Part 3 — Evaluation Metrics

Loss is not the metric 2 min

Slide [raw slide_056, 22:14] — recovered from the raw capture — makes the framing explicit:

How do we measure whether a model is "good enough" for deployment?

The loss function (training objective) ≠ the evaluation metric (what we actually care about).

Classification: Accuracy, Precision, Recall, F1, ROC-AUC, PR-AUC Regression: RMSE, MAE, R²

This distinction deserves to be hammered:

	Loss	Metric
Who consumes it	the optimiser	you, and your product manager
Must be differentiable	yes	no
Must be interpretable	no	yes
Computed on	training batches	validation / test sets
Example	cross-entropy = 0.34	"we catch 82% of fraud at a 3% false-alarm rate"

Nobody ships a cross-entropy of 0.34. They ship a recall at a fixed precision. The loss is scaffolding; the metric is the product.

📚Background

Background the slide assumed — train / validation / test, and data leakage. You need three disjoint splits:

Train — the optimiser sees it. Loss computed here is not evidence of anything.
Validation — you see it, repeatedly, while choosing hyperparameters, architectures, and when to stop. Because you make decisions using it, you slowly overfit to it too.
Test — looked at once, at the end. Every additional look degrades it into a validation set.

Data leakage is any path by which test information reaches the model. The classic instances: normalising using statistics computed over the whole dataset before splitting; imputing missing values before splitting; having duplicate rows spanning train and test; and, in time series, shuffling randomly so the model trains on the future and predicts the past. Symptom: a validation score that is excellent and utterly fails to reproduce in production. Fix: split first, preprocess after, and wrap every transform in a pipeline object fitted on train only.

The confusion matrix 5 min

Slide [raw slide_060, 25:43]:

Confusion Matrix for binary classification:

True Positives (TP): Correctly predicted positive

True Negatives (TN): Correctly predicted negative

False Positives (FP): Incorrectly predicted positive (Type I error)

False Negatives (FN): Incorrectly predicted negative (Type II error)

Derived metrics:

Accuracy = (TP + TN) / (TP + TN + FP + FN)

Precision = TP / (TP + FP) — "Of predicted positives, how many correct?"

Recall = TP / (TP + FN) — "Of actual positives, how many found?"

F1 Score = 2 × (Precision × Recall) / (Precision + Recall)

The naming rule that makes this stop being confusing

Every one of the four names is two words, and each word answers a separate question:

Word	Question it answers
first word (True / False)	Was the model right?
second word (Positive / Negative)	What did the model say?

So a False Negative = the model said negative, and it was wrong. Therefore the truth was positive. You never need to memorise a grid again — you can derive any cell in two seconds.

Type I error = False Positive = a false alarm. You rejected a true null hypothesis.
Type II error = False Negative = a miss. You failed to reject a false null hypothesis.

(Mnemonic if you need one: Type I has one letter in the roman numeral and FP is the "cry wolf" error; Type II has two, and FN is the "miss it" error.)

🧪 Worked example — the accuracy paradox

A screening model for a disease affecting 1% of a 1,000-patient population. So 10 patients are genuinely positive, 990 negative.

Model A: predict "negative" for everyone.

	Actual +	Actual −
Predicted +	TP = 0	FP = 0
Predicted −	FN = 10	TN = 990

Accuracy = \frac{0 + 990}{1000} = 𝟗𝟗.𝟎 %

99% accurate, and it has never once identified a sick patient. Precision is undefined (0/0), recall is $0 / 10 = 𝟎$ . This model is worthless and its headline number is excellent. That is the accuracy paradox, and it is why nobody reports accuracy on imbalanced problems.

Model B: a real model.

	Actual +	Actual −
Predicted +	TP = 8	FP = 50
Predicted −	FN = 2	TN = 940

Accuracy = \frac{8 + 940}{1000} = \frac{948}{1000} = 𝟗𝟒.𝟖 %

Precision = \frac{8}{8 + 50} = \frac{8}{58} = 𝟎.𝟏𝟑𝟕𝟗

Recall = \frac{8}{8 + 2} = \frac{8}{10} = 𝟎.𝟖𝟎

F_{1} = 2 \cdot \frac{0.1379 \times 0.80}{0.1379 + 0.80} = 2 \cdot \frac{0.11034}{0.93793} = \frac{0.22069}{0.93793} = 𝟎.𝟐𝟑𝟓𝟑

Model B has lower accuracy than Model A (94.8% vs 99.0%) and is enormously better. It finds 8 of 10 sick patients. Its precision is poor — 86% of its alarms are false — but for a screening test followed by a cheap confirmatory test, that is exactly the right trade.

The other derived metrics worth knowing

Metric	Formula	Reads as
Specificity (TNR)	$\frac{T N}{T N + F P}$	Of actual negatives, how many correctly cleared?
TPR (= Recall, = Sensitivity)	$\frac{T P}{T P + F N}$	Of actual positives, how many caught?
FPR	$\frac{F P}{F P + T N} = 1 - Specificity$	Of actual negatives, how many falsely flagged?
NPV	$\frac{T N}{T N + F N}$	Of predicted negatives, how many correct?
Balanced accuracy	$\frac{T P R + T N R}{2}$	Accuracy that is immune to class imbalance.
MCC	$\frac{T P \cdot T N - F P \cdot F N}{\sqrt{(T P + F P) (T P + F N) (T N + F P) (T N + F N)}}$	A correlation coefficient between prediction and truth; $- 1$ to $+ 1$ ; the most honest single number on imbalanced data.

For Model B, balanced accuracy $= \frac{0.80 + 940 / 990}{2} = \frac{0.80 + 0.9495}{2} = 𝟎.𝟖𝟕𝟒𝟕$ — far more informative than 94.8%.

The precision–recall trade-off 5 min

Slide [raw slide_062, 26:29]:

Adjusting the threshold changes precision and recall inversely:

Higher threshold → fewer positives → higher precision, lower recall

Lower threshold → more positives → lower precision, higher recall

Which to prioritize?

Precision: When false positives are costly (spam detection)

Recall: When false negatives are costly (cancer screening, fraud)

F1 Score: Harmonic mean — balances precision and recall. Useful when classes are imbalanced and accuracy is misleading.

Why the trade-off is mechanical, not empirical

A classifier does not output a class. It outputs a score — a probability, or a raw margin — and you compare it to a threshold $τ$ to get a class. That threshold is a free parameter you choose after training, at zero cost, without retraining anything.

Raise $τ$ → you flag fewer things → the ones you do flag are the ones you were most confident about → precision up. But you now miss things you'd previously have caught → recall down.
Lower $τ$ → the mirror image.

At $τ = 0$ you flag everything: recall $= 1$ , precision $=$ the base rate. At $τ = 1$ you flag nothing: recall $= 0$ , precision undefined. The whole curve between those two points belongs to a single trained model. Which is why:

🧪 Worked example — a threshold sweep

Ten validation examples, sorted by the model's score, with true labels:

Score	0.95	0.90	0.80	0.75	0.70	0.60	0.50	0.40	0.30	0.20
Label	1	1	0	1	1	0	1	0	0	0

Five positives, five negatives. Now sweep $τ$ :

$τ$	Predicted +	TP	FP	FN	Precision	Recall	F1
0.95	1	1	0	4	$1 / 1 = 1.000$	$1 / 5 = 0.200$	$0.333$
0.75	4	3	1	2	$3 / 4 = 0.750$	$3 / 5 = 0.600$	$0.667$
0.70	5	4	1	1	$4 / 5 = 0.800$	$4 / 5 = 0.800$	$𝟎.𝟖𝟎𝟎$
0.50	7	5	2	0	$5 / 7 = 0.714$	$5 / 5 = 1.000$	$0.833$
0.20	10	5	5	0	$5 / 10 = 0.500$	$5 / 5 = 1.000$	$0.667$

Verifying one F1 by hand, at $τ = 0.70$ : $F_{1} = 2 \cdot \frac{0.8 \times 0.8}{0.8 + 0.8} = 2 \cdot \frac{0.64}{1.6} = 𝟎.𝟖𝟎𝟎$ ✓

One model. Five completely different products. At $τ = 0.95$ you have a high-confidence auto-blocking system; at $τ = 0.50$ you have a review queue that misses nothing. Choosing $τ$ is a business decision, not a modelling one.

Why F1 uses the harmonic mean

The slide says "harmonic mean" without saying why it isn't the ordinary average. Here is why, and it is a genuinely good interview answer.

F_{1} = 2 \cdot \frac{P \cdot R}{P + R} vs arithmetic mean = \frac{P + R}{2}

Consider the degenerate classifier that flags everything: $P = 0.01$ (the base rate), $R = 1.0$ .

Arithmetic mean: $\frac{0.01 + 1.0}{2} = 𝟎.𝟓𝟎𝟓$ — looks like a coin flip. Respectable!
Harmonic mean: $2 \cdot \frac{0.01 \times 1.0}{1.01} = \frac{0.02}{1.01} = 𝟎.𝟎𝟏𝟗𝟖$ — correctly identifies it as garbage.

The harmonic mean is dominated by the smaller of the two values. It cannot be gamed by maxing one metric at the other's expense — which is precisely what you need, because both trivial classifiers (flag everything / flag nothing) max exactly one.

$F_{β}$ generalises it when you care about them unequally:

F_{β} = (1 + β^{2}) \cdot \frac{P \cdot R}{β^{2} P + R}

$β > 1$ weights recall more ( $F_{2}$ is standard for fraud and medical screening); $β < 1$ weights precision more ( $F_{0.5}$ for spam filtering, where a false positive means a lost legitimate email).

ROC-AUC and PR-AUC 6 min

Slide [raw slide_065, 28:36]:

ROC Curve (Receiver Operating Characteristic):

Plots True Positive Rate vs. False Positive Rate at all thresholds

AUC = Area Under ROC Curve (1.0 = perfect, 0.5 = random)

Threshold-independent measure of discriminative ability

PR Curve (Precision-Recall):

Plots Precision vs. Recall at all thresholds

PR-AUC preferred for highly imbalanced datasets

More informative when negatives dominate

When to use which?

ROC-AUC: Balanced classes, care about both classes equally

PR-AUC: Imbalanced data, focus on positive class performance

What "threshold-independent" buys you

§16 showed that a single model produces a whole family of (precision, recall) pairs. That makes model comparison awkward: if model A beats model B at $τ = 0.5$ but loses at $τ = 0.8$ , which is better? AUC answers this by summarising performance across every threshold at once, giving you one number that describes the model's ranking ability independently of where you eventually set the cut.

🧪 Worked example — build an ROC curve and compute AUC two ways

Eight examples, four positive and four negative:

Score	0.95	0.90	0.80	0.70	0.60	0.50	0.40	0.20
Label	1	1	0	1	0	1	0	0

Method 1 — trace the curve. Start at the origin and walk down the score list. Each positive you pass steps you up by $1 / P = 0.25$ ; each negative steps you right by $1 / N = 0.25$ .

After	Label	TP	FP	FPR = FP/4	TPR = TP/4	Point
start	—	0	0	0.00	0.00	(0.00, 0.00)
0.95	1	1	0	0.00	0.25	(0.00, 0.25)
0.90	1	2	0	0.00	0.50	(0.00, 0.50)
0.80	0	2	1	0.25	0.50	(0.25, 0.50)
0.70	1	3	1	0.25	0.75	(0.25, 0.75)
0.60	0	3	2	0.50	0.75	(0.50, 0.75)
0.50	1	4	2	0.50	1.00	(0.50, 1.00)
0.40	0	4	3	0.75	1.00	(0.75, 1.00)
0.20	0	4	4	1.00	1.00	(1.00, 1.00)

Area, by summing rectangles over each rightward move (each of width 0.25, at the current TPR):

AUC = 0.25 (0.50) + 0.25 (0.75) + 0.25 (1.00) + 0.25 (1.00) = 0.125 + 0.1875 + 0.25 + 0.25 = 𝟎.𝟖𝟏𝟐𝟓

Method 2 — the pairwise ranking interpretation. AUC equals the probability that a randomly chosen positive scores higher than a randomly chosen negative. Count winning pairs out of $P \times N = 4 \times 4 = 16$ :

Positive	Beats which negatives (0.80, 0.60, 0.40, 0.20)?	Count
0.95	all four	4
0.90	all four	4
0.70	0.60, 0.40, 0.20	3
0.50	0.40, 0.20	2
	Total	13

AUC = \frac{13}{16} = 𝟎.𝟖𝟏𝟐𝟓

Both methods give 0.8125. They are the same quantity; the geometric one is how you plot it, the combinatorial one is what it means.

Why ROC lies on imbalanced data, and PR doesn't

This is the most important practical point in the metrics section.

Fraud detection: 1,000,000 transactions, 1,000 fraudulent (0.1%). Your model, at its chosen threshold, catches 900 frauds and raises 10,000 false alarms.

TPR = \frac{900}{1000} = 0.90 FPR = \frac{10,000}{999,000} = 𝟎.𝟎𝟏𝟎

An ROC point of $(0.010, 0.90)$ is spectacular — hard against the top-left corner. AUC will look superb. But:

Precision = \frac{900}{900 + 10,000} = \frac{900}{10,900} = 𝟎.𝟎𝟖𝟐𝟔

Fewer than 9% of the alerts your fraud team investigates are real. They will drown.

The reason ROC hides this: FPR divides by $T N + F P$ , and with 999,000 negatives that denominator is enormous, so 10,000 false positives barely register. Precision divides by $T P + F P$ , where the 10,000 false positives are compared against only 900 true ones — and the disaster is immediately visible.

	Denominator	Contains the huge negative class?
FPR (ROC's x-axis)	$F P + T N$	yes → dilutes FP
Precision (PR's y-axis)	$F P + T P$	no → exposes FP

Interactive · graph Drag the threshold, watch three views move together

Concept: One model, one score distribution, and how threshold choice moves the confusion matrix, the ROC point and the PR point simultaneously
Try: A single threshold slider over a pair of overlapping score histograms (positives and negatives), plus a class-imbalance slider from 50% to 0.1% positive.
Watch: Three linked panels update live — a 2×2 confusion matrix with counts, a dot moving along the ROC curve, and a dot moving along the PR curve, with precision/recall/F1 read out numerically.
Insight: Dragging the imbalance slider toward 0.1% barely moves the ROC dot while the PR dot collapses. That divergence, seen live, is the entire argument for PR-AUC on imbalanced data.

The fraud worked example in §17 — FPR = 0.010 (looks excellent) while precision = 0.083 (a disaster), from the same confusion matrix.

Regression metrics 5 min

Slide [slide_015, 29:07]:

Error Metrics

RMSE (Root Mean Squared Error): sqrt(1/n * sum(yi - y_hat_i)^2)

Same units as target variable

Penalizes large errors more heavily

MAE (Mean Absolute Error): (1/n) * sum(|yi - y_hat_i|)

Robust to outliers

Easier to interpret

Goodness of Fit

R-squared (Coefficient of Determination): 1 - SS_res / SS_tot

Proportion of variance explained by model

1.0 = perfect, 0 = baseline (predict mean)

Can be negative for very poor models

Choosing metrics: Outlier-sensitive tasks → RMSE · Outlier-robust tasks → MAE · Relative model fit → R-squared

RMSE vs MSE — why the square root matters

RMSE = \sqrt{\frac{1}{n} \sum_{i} {(y_{i} - {\hat{y}}_{i})}^{2}}

MSE and RMSE are minimised at exactly the same parameters (square root is monotonic), so as a training loss they are interchangeable. As a metric they are not, for one reason the slide states: units. If $y$ is in dollars, MSE is in dollars-squared, which is meaningless to a stakeholder. RMSE is in dollars. "Our average error is about $47" is a sentence you can say in a review; "our MSE is 2209" is not.

R² explained properly

The formula says: measure how much error your model leaves, measure how much error the dumbest reasonable baseline leaves, take the ratio, and subtract it from one — so the result is the fraction of the baseline's error that you managed to remove.

R^{2} = 1 - \frac{S S_{r e s}}{S S_{t o t}} = 1 - \frac{\sum_{i} {(y_{i} - {\hat{y}}_{i})}^{2}}{\sum_{i} {(y_{i} - \overline{y})}^{2}}

Symbol	Read it as	What it means
$S S_{r e s}$	"sum of squares, residual"	How much error your model leaves.
$S S_{t o t}$	"sum of squares, total"	How much error the dumbest reasonable baseline leaves — always predicting the mean $\overline{y}$ .
$\overline{y}$	"y bar"	The mean of the true targets.

So $R^{2}$ literally reads: "what fraction of the baseline's error did I eliminate?"

$R^{2} = 1$ → $S S_{r e s} = 0$ → perfect.
$R^{2} = 0$ → $S S_{r e s} = S S_{t o t}$ → exactly as good as always guessing the mean.
$R^{2} < 0$ → worse than guessing the mean. Entirely possible, and the slide correctly says so. It happens routinely on a test set when a model has overfit.

🧪 Worked example

$y = [10, 20, 30, 40]$ , $\hat{y} = [12, 18, 33, 39]$ . Residuals: $[- 2, 2, - 3, 1]$ .

MAE = \frac{2 + 2 + 3 + 1}{4} = \frac{8}{4} = 𝟐.𝟎

RMSE = \sqrt{\frac{4 + 4 + 9 + 1}{4}} = \sqrt{\frac{18}{4}} = \sqrt{4.5} = 𝟐.𝟏𝟐𝟏𝟑

For $R^{2}$ : $\overline{y} = \frac{10 + 20 + 30 + 40}{4} = 25$ .

S S_{t o t} = {(10 - 25)}^{2} + {(20 - 25)}^{2} + {(30 - 25)}^{2} + {(40 - 25)}^{2} = 225 + 25 + 25 + 225 = 500

S S_{r e s} = 4 + 4 + 9 + 1 = 18

R^{2} = 1 - \frac{18}{500} = 1 - 0.036 = 𝟎.𝟗𝟔𝟒

Now the negative case. Same $y$ , but a bad model that always predicts 30: $\hat{y} = [30,30,30,30]$ .

S S_{r e s} = {(10 - 30)}^{2} + {(20 - 30)}^{2} + {(30 - 30)}^{2} + {(40 - 30)}^{2} = 400 + 100 + 0 + 100 = 600

R^{2} = 1 - \frac{600}{500} = 1 - 1.2 = - 𝟎.𝟐

Negative, as promised. Predicting the constant 30 is worse than predicting the constant 25.

Three more regression metrics worth having

Metric	Formula	When
MAPE	$\frac{100}{n} \sum_{i} \| \frac{y_{i} - {\hat{y}}_{i}}{y_{i}} \|$	When relative error is what matters. ⚠️ Explodes when any $y_{i} \approx 0$ , and asymmetrically punishes over-prediction.
Adjusted R²	$1 - (1 - R^{2}) \frac{n - 1}{n - d - 1}$	Comparing models with different numbers of features. Plain $R^{2}$ never decreases when you add a feature, even a random one; the adjustment penalises $d$ .
RMSLE	$\sqrt{\frac{1}{n} \sum_{i} {(\log (1 + y_{i}) - \log (1 + {\hat{y}}_{i}))}^{2}}$	Targets spanning orders of magnitude (demand, prices). Penalises under-prediction more than over-prediction, which often matches inventory economics.

📚Background

Background the slide assumed — is a 2-point difference real? If model A scores 0.86 and model B scores 0.84 on a 100-example test set, that is almost certainly noise. The standard error of an accuracy estimate is $\sqrt{p (1 - p) / n} = \sqrt{0.85 \times 0.15 / 100} \approx 0.036$ , so a 95% interval is roughly $\pm 0.07$ . The two models are indistinguishable.

Fixes, in increasing order of rigour: (1) report mean ± std across cross-validation folds, not a single number; (2) bootstrap the test set — resample with replacement 1,000 times, recompute the metric, take the 2.5th and 97.5th percentiles; (3) for comparing two models, use a paired test on the same examples (McNemar's test for classification), which removes the variance from example difficulty and is far more sensitive than comparing two independent intervals.

Nothing damages credibility faster than shipping a model because it won by one point on 200 test examples.

Part 4 — Naive Bayes

Bayes' theorem, the naive assumption, and the decision rule 7 min

Slide [slide_017, 30:04] gives three formulas and almost no words. Every one deserves unpacking.

Bayes' theorem applied to classification

The formula says: the probability that this example belongs to class $k$ , given what I observed, is proportional to how likely class $k$ was to begin with, times how likely class $k$ was to produce what I observed.

P (C_{k} | 𝐱) = \frac{P (𝐱 | C_{k}) P (C_{k})}{P (𝐱)} \propto P (𝐱 | C_{k}) P (C_{k})

Symbol	Read it as	Name	What it means
$P (C_{k} \| 𝐱)$	"P of C_k given x"	posterior	What we want: probability of class $k$ after seeing the evidence.
$P (𝐱 \| C_{k})$	"P of x given C_k"	likelihood	If this really were class $k$ , how likely is this exact input?
$P (C_{k})$	"P of C_k"	prior	How common class $k$ is, before looking at anything.
$P (𝐱)$	"P of x"	evidence	How likely this input is under any class.
$\propto$	"is proportional to"	—	Equal up to a constant factor.

Deriving it takes two lines. The definition of conditional probability gives, two ways:

P (C_{k} \cap 𝐱) = P (C_{k} | 𝐱) P (𝐱) and P (C_{k} \cap 𝐱) = P (𝐱 | C_{k}) P (C_{k})

Set them equal and divide by $P (𝐱)$ . ∎

Why we can drop $P (𝐱)$ . It does not depend on $k$ — it is the same number for every class we're comparing. Since we only want the $\arg \max$ over $k$ , a common positive factor cannot change which class wins. That's what the $\propto$ is doing, and it saves us from computing the hardest term in the formula.

The "naive" assumption

The formula says: assume that, once you know the class, the features are independent of each other — so the probability of the whole feature vector is just the product of each feature's probability.

P (𝐱 | C_{k}) = \prod_{j = 1}^{d} P (x_{j} | C_{k})

Symbol	Read it as	What it means
$\prod_{j = 1}^{d}$	"product from j equals 1 to d"	Multiply the terms together, once per feature.
$x_{j}$	"x sub j"	The value of feature $j$ .

Why this is called "naive": it is usually false. In an email, "free" and "money" co-occur far more than independently. The assumption says knowing one tells you nothing about the other, given that the email is spam. That's simply wrong.

📚 Why make a false assumption? The counting argument

The slide never justifies it, and the justification is the entire point of the method.

Suppose you have $d$ binary features and you want $P (𝐱 | C_{k})$ without the assumption. You'd need one probability for every possible feature combination: $2^{d} - 1$ free parameters, per class.

$d$	Parameters without the assumption	Parameters with it
10	$2^{10} - 1 = 1,023$	$10$
20	$1,048,575$	$20$
100	$\approx 1.3 \times 10^{30}$	$100$
10,000 (a vocabulary)	astronomically infeasible	$10,000$

Exponential becomes linear. With 10,000 vocabulary words you would need more training emails than there are atoms in the observable universe to estimate the joint distribution; with the naive assumption you need enough to estimate 10,000 individual word frequencies, which is a few thousand emails. That is the trade: accept a wrong model in exchange for one you can actually estimate.

The decision rule

The formula says: for each class, multiply its prior by every feature's likelihood under that class; then pick whichever class produced the biggest product.

\hat{y} = \arg \max_{k} P (C_{k}) \prod_{j = 1}^{d} P (x_{j} | C_{k})

📚 Two things you must do that the slide omits

1. Laplace (add-one) smoothing. If a word never appeared in any spam email in training, then $P (word | spam) = 0$ , and a single zero annihilates the entire product — the class gets probability zero no matter how much other evidence supports it. One unseen word vetoes everything.

The fix is to pretend you saw everything once more than you did:

P (x_{j} | C_{k}) = \frac{count (x_{j}, C_{k}) + α}{count (C_{k}) + α | V |}

Symbol	What it means
$α$	Smoothing strength. $α = 1$ is Laplace; $α < 1$ is Lidstone.
$\| V \|$	Vocabulary size. Needed in the denominator so the probabilities still sum to 1.

This is not optional. sklearn's Naive Bayes classes default to alpha=1.0 precisely because without it the method is broken on any real text corpus.

2. Work in log space. Multiplying 10,000 numbers each around $10^{- 4}$ gives $10^{- 40000}$ , which underflows a float64 (min ~ $10^{- 308}$ ) to exactly zero, for every class. Take logs, turning the product into a sum:

\hat{y} = \arg \max_{k} [\log P (C_{k}) + \sum_{j = 1}^{d} \log P (x_{j} | C_{k})]

Logs are monotonic, so the argmax is unchanged. Every real implementation does this.

🧪 Worked example — spam classification, end to end

Training data. 10 emails: 4 spam, 6 ham. Vocabulary $V = {\text{free}, \text{money}, \text{meeting}} $, s o$ |V| = 3$.

Word occurrence counts:

	free	money	meeting	total words
Spam	6	4	0	10
Ham	1	2	7	10

Step 1 — priors.

P (spam) = \frac{4}{10} = 0.4 P (ham) = \frac{6}{10} = 0.6

Step 2 — smoothed likelihoods ( $α = 1$ , $| V | = 3$ , so every denominator is $10 + 3 = 13$ ):

	$P (\cdot \| spam)$	$P (\cdot \| ham)$
free	$\frac{6 + 1}{13} = \frac{7}{13} = 0.5385$	$\frac{1 + 1}{13} = \frac{2}{13} = 0.1538$
money	$\frac{4 + 1}{13} = \frac{5}{13} = 0.3846$	$\frac{2 + 1}{13} = \frac{3}{13} = 0.2308$
meeting	$\frac{0 + 1}{13} = \frac{1}{13} = 0.0769$	$\frac{7 + 1}{13} = \frac{8}{13} = 0.6154$

Note the smoothing at work: "meeting" never appeared in spam, and without $α$ its likelihood would be 0, making any email containing "meeting" impossible to classify as spam regardless of what else it said. With smoothing it is 0.0769 — small, but not fatal.

Step 3 — classify a new email: "free money".

score (spam) = 0.4 \times 0.5385 \times 0.3846 = 0.4 \times 0.20710 = 𝟎.𝟎𝟖𝟐𝟖𝟒𝟎

score (ham) = 0.6 \times 0.1538 \times 0.2308 = 0.6 \times 0.035497 = 𝟎.𝟎𝟐𝟏𝟐𝟗𝟖

Step 4 — normalise to a real probability (restoring the evidence term):

P (spam | "free money") = \frac{0.082840}{0.082840 + 0.021298} = \frac{0.082840}{0.104138} = 𝟎.𝟕𝟗𝟓𝟓

Verdict: spam, with 79.6% posterior probability.

Step 5 — verify in log space, as a real implementation would:

\log score (spam) = \log 0.4 + \log 0.5385 + \log 0.3846 = - 0.9163 - 0.6190 - 0.9555 = - 𝟐.𝟒𝟗𝟎𝟖

\log score (ham) = \log 0.6 + \log 0.1538 + \log 0.2308 = - 0.5108 - 1.8718 - 1.4663 = - 𝟑.𝟖𝟒𝟖𝟗

Spam wins ( $- 2.4908 > - 3.8489$ ) ✓. Recovering the probability: the difference is $1.3581$ , so the odds ratio is $e^{1.3581} = 3.889$ , giving $P (spam) = \frac{3.889}{1 + 3.889} = 𝟎.𝟕𝟗𝟓𝟓$ ✓.

Both routes agree exactly.

Naive Bayes variants and trade-offs 5 min

Slide [slide_018, 32:20]:

Variants:

Gaussian NB: Features are continuous, assumed normally distributed

Multinomial NB: Features are counts (e.g., word frequencies in text)

Bernoulli NB: Features are binary (e.g., word presence/absence)

Strengths: Fast, works well with high-dimensional data, good baseline Weaknesses: Independence assumption rarely holds; poor probability calibration Classic use case: Spam classification, text categorization

The three variants differ in exactly one place: what distribution you assume for $P (x_{j} | C_{k})$ . Everything else — the prior, the product, the argmax — is identical.

Variant	$P (x_{j} \| C_{k})$ is	Fitted by	Use for
Gaussian	$\frac{1}{\sqrt{2 π σ_{j k}^{2}}} \exp (- \frac{{(x_{j} - μ_{j k})}^{2}}{2 σ_{j k}^{2}})$	the mean $μ_{j k}$ and variance $σ_{j k}^{2}$ of feature $j$ within class $k$	continuous features (height, price, latency)
Multinomial	$\propto θ_{j k}^{x_{j}}$ , with $θ_{j k}$ the probability of token $j$ in class $k$	smoothed relative frequency (our worked example)	counts — word frequencies, tf-idf
Bernoulli	$θ_{j k}^{x_{j}} {(1 - θ_{j k})}^{1 - x_{j}}$	fraction of class- $k$ documents containing the feature	binary presence/absence

📚 Background — generative vs discriminative

Naive Bayes is a generative classifier: it models $P (𝐱 | C_{k})$ and $P (C_{k})$ — the full story of how the data was produced — and then uses Bayes' rule to derive $P (C_{k} | 𝐱)$ .

Logistic regression, SVMs and neural networks are discriminative: they model the boundary $P (C_{k} | 𝐱)$ directly and never learn what the data looks like.

	Generative (NB)	Discriminative (LogReg, SVM)
Models	$P (𝐱, y)$	$P (y \| 𝐱)$ or just the boundary
Training	closed-form counting, one pass	iterative optimisation
Small data	better — the assumption acts as a strong prior	worse — overfits
Large data	plateaus (the wrong assumption caps it)	better — keeps improving
Can generate samples	yes	no
Handles missing features	naturally (drop the term)	needs imputation

💡Key insight

There's a well-known result (Ng & Jordan) that a generative model reaches its — higher — asymptotic error much faster, so it wins in the low-data regime and loses in the high-data regime. ✅ Confirmed and corrected. The citation is Ng & Jordan, "On Discriminative vs. Generative Classifiers: A Comparison of Logistic Regression and Naive Bayes", NIPS 2001 — that part was already right. The sample-complexity rates were not: this file's earlier draft stated " $O (d)$ for NB vs $O (d)$ " for both, which is not the paper's result and not even internally distinct. The paper's actual finding is that Naive Bayes' generalisation error approaches its asymptote in $O (\log d)$ examples, while logistic regression needs $Ω (d)$ — a genuinely large gap, not the same rate. That asymmetry is exactly why NB can win decisively in the low-data regime and why the crossover point scales with the number of features $d$ .

📚 Naive Bayes is secretly a linear classifier

Take logs of the decision rule for two classes and subtract:

\log \frac{P (C_{1} | 𝐱)}{P (C_{0} | 𝐱)} = \log \frac{P (C_{1})}{P (C_{0})} + \sum_{j = 1}^{d} \log \frac{P (x_{j} | C_{1})}{P (x_{j} | C_{0})}

For Bernoulli features, each term in the sum is linear in $x_{j}$ . So the decision boundary is $b + \sum_{j} w_{j} x_{j} = 0$ — a hyperplane, exactly like logistic regression. The difference is entirely in how the weights are chosen: NB sets them by counting each feature independently, logistic regression fits them jointly to minimise loss. That is why logistic regression usually wins with enough data — it can compensate for correlated features by shrinking their weights, and NB structurally cannot.

Part 5 — K-Nearest Neighbors

KNN: the algorithm 6 min

Slide [raw slide_082, 35:49] — recovered:

Idea: Classify a point by majority vote of its K nearest neighbors. No explicit training phase — "lazy learner"

Distance Metrics:

Euclidean: sqrt(sum(xi - yi)^2) — most common

Manhattan: sum(|xi - yi|) — for grid-like data

Minkowski: generalization of both

Cosine similarity: for text/high-dimensional sparse data

Choice of K:

Small K (e.g., 1): Low bias, high variance (overfitting)

Large K: High bias, low variance (underfitting)

Typically odd K for binary classification (avoid ties)

Use cross-validation to find optimal K

The slide also displays the three distance formulas:

Euclidean (L2): d (𝐱, 𝐳) = \sqrt{\sum_{j = 1}^{d} {(x_{j} - z_{j})}^{2}}

Manhattan (L1): d (𝐱, 𝐳) = \sum_{j = 1}^{d} | x_{j} - z_{j} |

Minkowski (Lp): d (𝐱, 𝐳) = {(\sum_{j = 1}^{d} {| x_{j} - z_{j} |}^{p})}^{1 / p}

Setting $p = 2$ recovers Euclidean, $p = 1$ recovers Manhattan. That is what "generalization of both" means, and it is worth checking yourself: at $p = 1$ the outer exponent is $1 / 1 = 1$ , so the whole thing collapses to the sum of absolute differences ✓.

"No explicit training phase — lazy learner"

This is the strangest and most important property. KNN's "training" is: store the data. That's it. All the work happens at prediction time, when it must compute the distance from the query to every stored point.

	Eager learner (LogReg, SVM, NN)	Lazy learner (KNN)
Train cost	high	$O (1)$ — just store
Predict cost	$O (d)$ — one dot product	$O (n d)$ — compare to everything
Model size	$d$ parameters	the entire training set
Adding new data	retrain	just append it
Decision boundary	fixed functional form	arbitrary, data-shaped

🧪 Worked example — K changes the answer

Five training points in 2-D:

Point	Coordinates	Class
A	(1, 1)	0
B	(2, 1)	0
C	(4, 5)	1
D	(5, 4)	1
E	(4, 2)	1

Query: $q = (3, 2)$ . Euclidean distances:

Point	Computation	Distance	Class
E	$\sqrt{{(4 - 3)}^{2} + {(2 - 2)}^{2}} = \sqrt{1 + 0}$	$𝟏.𝟎𝟎𝟎$	1
B	$\sqrt{{(2 - 3)}^{2} + {(1 - 2)}^{2}} = \sqrt{1 + 1}$	$𝟏.𝟒𝟏𝟒$	0
A	$\sqrt{{(1 - 3)}^{2} + {(1 - 2)}^{2}} = \sqrt{4 + 1}$	$𝟐.𝟐𝟑𝟔$	0
D	$\sqrt{{(5 - 3)}^{2} + {(4 - 2)}^{2}} = \sqrt{4 + 4}$	$𝟐.𝟖𝟐𝟖$	1
C	$\sqrt{{(4 - 3)}^{2} + {(5 - 2)}^{2}} = \sqrt{1 + 9}$	$𝟑.𝟏𝟔𝟐$	1

Now vary K:

K	Neighbours (nearest first)	Votes	Prediction
1	E	1×class 1	class 1
3	E, B, A	1×class 1, 2×class 0	class 0
5	E, B, A, D, C	3×class 1, 2×class 0	class 1

Same query, same data, three different answers. K is not a minor tuning knob — it is the model.

Check the Manhattan distances give the same $K = 3$ answer: E $= 1 + 0 = 1$ ; B $= 1 + 1 = 2$ ; A $= 2 + 1 = 3$ ; D $= 2 + 2 = 4$ ; C $= 1 + 3 = 4$ . Nearest three are still E, B, A → class 0 ✓. The metric didn't change the outcome here, but it can and does.

Choice of K — the bias–variance argument

K	Boundary shape	Bias	Variance	Failure mode
$K = 1$	maximally jagged; every training point owns a cell	low	high	one mislabelled point creates a wrong island → overfits
$K$ moderate	smooth but responsive	balanced	balanced	—
$K = n$	a single flat prediction: the majority class everywhere	high	low	ignores the input entirely → underfits

Note the extreme case: at $K = 1$ , training accuracy is always exactly 100%, because each training point's nearest neighbour is itself. This makes training accuracy a completely useless signal for choosing K — you must use cross-validation, which is exactly what the slide says.

Why odd K: with two classes and even K, you can get 2–2 and need a tie-break rule. Odd K makes ties impossible. (For $C > 2$ classes odd K doesn't guarantee anything, and you break ties by smallest total distance.)

Which distance to use:

Metric	Use when
Euclidean (L2)	Default. Continuous features on comparable scales.
Manhattan (L1)	Grid-like movement (city blocks), or when you want robustness to a single wildly-off coordinate — L1 doesn't square it.
Minkowski (Lp)	When you want to tune the interpolation between them. Rarely worth it.
Cosine similarity	Text and embeddings. Measures the angle, ignoring magnitude — so a 100-word and a 1000-word document about the same topic come out similar, which Euclidean would deny.

KNN: practical considerations 7 min

Slide [raw slide_084, 36:30] — recovered:

Curse of Dimensionality:

In high dimensions, all points become equidistant

Distance metrics lose discriminative power

Need exponentially more data as dimensions grow

Mitigation strategies:

Feature selection / dimensionality reduction (PCA)

Feature scaling (normalization) is essential for KNN

Computational cost:

Prediction is O(n*d) for n training points, d dimensions

KD-trees, Ball-trees for faster neighbor lookup

KNN for regression: Average (or weighted average) of K neighbors' target values

The curse of dimensionality, made concrete

"All points become equidistant" is a startling claim. Here is why it's true.

Take $n$ points drawn uniformly at random in the unit hypercube ${[0,1]}^{d}$ and look at the ratio

\frac{d_{\max} - d_{\min}}{d_{\min}}

— i.e. how much further the farthest point is than the nearest, in relative terms. As $d$ grows, this ratio goes to zero. The nearest and farthest neighbours become indistinguishable.

The intuition: squared Euclidean distance is a sum of $d$ independent per-dimension contributions. By concentration of measure, a sum of many independent terms concentrates tightly around its mean — its standard deviation grows like $\sqrt{d}$ while its mean grows like $d$ , so the relative spread shrinks like $1 / \sqrt{d}$ . Every pair of points ends up at almost exactly the same distance.

And "nearest neighbour" is a meaningless concept when every neighbour is equally near. KNN doesn't degrade gracefully in high dimensions; it stops being an algorithm.

Second framing — "need exponentially more data". To cover 10% of the range along each axis you need a fraction ${0.1}^{d}$ of the volume:

$d$	Fraction of the space within 10% on every axis	Points needed for one neighbour in that box
1	$0.1$	10
2	$0.01$	100
10	$10^{- 10}$	10 billion
20	$10^{- 20}$	$10^{20}$

At $d = 20$ your "nearest" neighbour is nowhere near you. It is just the least-far point in a space where everything is far.

Feature scaling is not optional

The slide says scaling is "essential for KNN", and it is the most common way people silently break it.

🧪 Predict whether a customer churns from [age (years), annual_income (dollars)].

Two candidate neighbours for a query customer aged 40 earning $50,000:

Neighbour	Age	Income	$Δ$ age	$Δ$ income	Euclidean distance
P	41	50,500	1	500	$\sqrt{1 + 250,000} = 500.001$
Q	70	50,010	30	10	$\sqrt{900 + 100} = 31.62$

Q is "closer" — despite being 30 years older — because a $500 income difference outweighs a 30-year age difference purely from the units. Income is measured in tens of thousands and age in tens, so income contributes ~ $10^{6} \times$ more to the squared distance.

The fix — apply one of these to every feature:

Standardisation: $x^{'} = \frac{x - μ}{σ}$ → mean 0, std 1. The default.
Min-max: $x^{'} = \frac{x - x_{\min}}{x_{\max} - x_{\min}}$ → range $[0,1]$ . Sensitive to outliers.

Computational cost and the tree structures

Naive prediction is $O (n d)$ per query: compute $d$ subtractions for each of $n$ points. With $n = 10^{6}$ and $d = 100$ that's $10^{8}$ operations for one prediction.

KD-trees recursively split space on one axis at a time. They give roughly $O (\log n)$ lookups — but only in low dimensions. Above roughly $d \approx 20$ they degrade to worse-than-brute-force, because the curse of dimensionality means the search cannot prune any branches.
Ball-trees partition into nested hyperspheres instead of axis-aligned boxes, and tolerate somewhat higher $d$ and non-Euclidean metrics — but they too eventually lose.

KNN for regression

One line change: instead of taking the majority class of the K neighbours, take the average of their target values. With distance weighting:

\hat{y} = \frac{\sum_{i \in 𝒩_{K}} w_{i} y_{i}}{\sum_{i \in 𝒩_{K}} w_{i}}, w_{i} = \frac{1}{d (x, x_{i})}

⚠️ A structural limitation worth knowing: KNN regression cannot extrapolate. Its prediction is always an average of observed targets, so it is bounded by $[\min y, \max y]$ in the training set. Ask it about an input beyond the range of your data and it will confidently return the average of the nearest points you do have. Linear regression would at least extend the trend.

Interactive · simulator K, scaled and unscaled

Concept: How K controls the bias–variance trade-off, and how unscaled features destroy the metric
Try: A 2-D scatter of two overlapping classes; sliders for K (1→25) and for a multiplier on the x-axis feature's scale (1× → 1000×). A toggle applies standardisation.
Watch: The decision boundary is shaded live. Raising K smooths jagged islands into a clean curve. Raising the scale multiplier collapses the boundary into vertical stripes — the y-feature stops mattering at all. Turning on standardisation restores it instantly.
Insight: K=1 gives 100% training accuracy and a boundary full of noise-driven islands, which is why training accuracy cannot be used to pick K. And an unscaled feature doesn't bias KNN slightly — it deletes the other features.

The K=1/3/5 worked example in §21 (three different answers for one query) and the age-vs-income table in §22.

Part 6 — Support Vector Machines

SVM: the core idea 7 min

Slide [raw slide_087, 36:43] — recovered:

Goal: Find the hyperplane that maximizes the margin between classes

Margin: Distance between decision boundary and nearest data points

Support vectors: data points closest to boundary (define the margin)

Hard Margin SVM:

Assumes data is linearly separable

Maximize margin subject to all points correctly classified

Soft Margin SVM (C-SVM):

Allows some misclassification via slack variables

C parameter controls the trade-off:

Large C → narrow margin, fewer violations (may overfit)

Small C → wide margin, more violations (may underfit)

Why "maximum margin" is the right objective

If the data is linearly separable, there are infinitely many lines that separate it. Logistic regression will find one; which one depends on initialisation and regularisation. The SVM asks a sharper question: of all separating hyperplanes, which is furthest from both classes?

The justification is a generalisation argument. A boundary that squeaks past the training points has no room for error — a test point drawn slightly differently lands on the wrong side. A boundary with a wide buffer tolerates perturbation. Maximising the margin is minimising sensitivity to the exact positions of the training points, which is a form of regularisation you get from the geometry rather than from a penalty term.

Deriving the margin — and where the "1" in hinge loss came from

Fix the scale so that the closest points on each side satisfy $𝐰^{⊤} 𝐱 + b = \pm 1$ . (We're allowed to do this: scaling $𝐰$ and $b$ together by any positive constant describes the same hyperplane, so we choose the constant that makes this true.)

The two margin boundaries are $𝐰^{⊤} 𝐱 + b = + 1$ and $𝐰^{⊤} 𝐱 + b = - 1$ . The distance from the decision boundary to each is $\frac{1}{‖ 𝐰 ‖}$ , so the full margin width is

margin = \frac{2}{‖ 𝐰 ‖}

Maximising $\frac{2}{‖ 𝐰 ‖}$ is minimising $‖ 𝐰 ‖$ , which for convenience is written as minimising $\frac{1}{2} ‖ 𝐰 ‖^{2}$ . So the hard-margin SVM is:

\min_{𝐰, b} \frac{1}{2} ‖ 𝐰 ‖^{2} subject to y_{i} (𝐰^{⊤} 𝐱_{i} + b) \geq 1 \forall i

Soft margin — what happens when the data isn't separable

Real data overlaps. The hard constraint then has no feasible solution at all — the optimiser returns nothing. The fix is to allow violations and charge for them, via slack variables $ξ_{i} \geq 0$ :

\min_{𝐰, b, ξ} \frac{1}{2} ‖ 𝐰 ‖^{2} + C \sum_{i = 1}^{n} ξ_{i} s.t. y_{i} (𝐰^{⊤} 𝐱_{i} + b) \geq 1 - ξ_{i}, ξ_{i} \geq 0

$ξ_{i}$	Meaning
$0$	correctly classified, outside the margin — a "free" point
$0 < ξ_{i} \leq 1$	correct side, but inside the margin
$ξ_{i} > 1$	misclassified

And the slack is exactly the hinge loss. The smallest $ξ_{i}$ satisfying the constraint is $ξ_{i} = \max (0, 1 - y_{i} (𝐰^{⊤} 𝐱_{i} + b))$ . Substituting it in — and recognising $\frac{1}{2} ‖ 𝐰 ‖^{2}$ as precisely the L2 penalty from §9's regularisation background box, applied here to the margin instead of to a plain empirical-risk minimiser:

\min_{𝐰, b} \underset{L2 regularisation}{\underset{⏟}{\frac{1}{2} ‖ 𝐰 ‖^{2}}} + C \sum_{i} \underset{hinge loss}{\underset{⏟}{\max (0, 1 - y_{i} f (𝐱_{i}))}}

What C does

$C$ is the exchange rate between "wide margin" and "few violations".

	Small $C$	Large $C$
Violations are	cheap	expensive
Optimiser prefers	a wide margin, tolerating errors	classifying everything right, even at a razor margin
$‖ 𝐰 ‖$	small	large
Bias / variance	high bias, low variance → underfit	low bias, high variance → overfit
As it goes to the extreme	$C \to 0$ : ignores the data entirely	$C \to \infty$ : recovers the hard-margin SVM

Note that $C$ is the inverse of the usual regularisation strength $λ$ : in the standard $loss + λ R (θ)$ form, bigger $λ$ means more regularisation, but bigger $C$ means less. This trips people up constantly. (Indeed, dividing the objective through by $C$ gives $\frac{1}{2 C} ‖ w ‖^{2} + \sum_{i} hinge$ , so $λ = \frac{1}{2 C}$ .)

🧪 Worked example — compute a margin by hand

Two points: $𝐱_{+} = (2,2)$ with $y = + 1$ , and $𝐱_{-} = (0,0)$ with $y = - 1$ .

By symmetry, the maximum-margin boundary is perpendicular to the line joining them and passes through their midpoint $(1,1)$ . So $𝐰 = (a, a)$ for some $a > 0$ .

Impose the two margin constraints as equalities (both points are support vectors — they're the only points):

𝐰^{⊤} (2,2) + b = 4 a + b = + 1

𝐰^{⊤} (0,0) + b = b = - 1

From the second, $b = - 1$ . Substituting: $4 a - 1 = 1 \Rightarrow a = 𝟎.𝟓$ .

So $𝐰 = (0.5, 0.5)$ , $b = - 1$ .

‖ 𝐰 ‖ = \sqrt{{0.5}^{2} + {0.5}^{2}} = \sqrt{0.5} = 0.7071

margin = \frac{2}{‖ 𝐰 ‖} = \frac{2}{0.7071} = 𝟐.𝟖𝟐𝟖 = 2 \sqrt{2}

Verification: the actual Euclidean distance between $(0,0)$ and $(2,2)$ is $\sqrt{4 + 4} = 2 \sqrt{2} = 2.828$ ✓. Since both points are support vectors, the margin spans the entire gap between them, exactly as it should.

Cross-check with hinge loss:

$y_{+} f (𝐱_{+}) = (+ 1) (0.5 \cdot 2 + 0.5 \cdot 2 - 1) = (+ 1) (1) = 1 \Rightarrow \max (0, 1 - 1) = 𝟎$ ✓
$y_{-} f (𝐱_{-}) = (- 1) (0 + 0 - 1) = (- 1) (- 1) = 1 \Rightarrow \max (0,1 - 1) = 𝟎$ ✓

Both support vectors sit exactly at margin 1 with zero hinge loss. The solution is consistent.

SVM: the kernel trick 8 min

Slide [raw slide_088, 38:13] — recovered. This is the slide the previous version of these notes had to guess at; here it is verbatim:

Problem: Many real datasets are not linearly separable

Solution: Map data to higher-dimensional space where it IS separable

Kernel trick: compute dot products in high-D space without explicit mapping

Common Kernels:

Linear: K(x,y) = x^T y — use when linearly separable

RBF (Gaussian): K(x,y) = exp(-gamma * ||x-y||^2) — most versatile

Polynomial: K(x,y) = (x^T y + c)^d — captures feature interactions

Hyperparameters:

gamma (RBF): Higher = more complex boundary (overfitting risk)

C: Regularization strength (trade-off margin vs. violations)

d (Polynomial): Degree of polynomial kernel

🧪 Step 1 — see that mapping up actually works: XOR

Four points, the classic non-separable case:

Point	$x_{1}$	$x_{2}$	Label
A	0	0	$- 1$
B	1	1	$- 1$
C	0	1	$+ 1$
D	1	0	$+ 1$

In 2-D no line separates ${A, B}$ from ${C, D}$ — the positives sit on one diagonal and the negatives on the other. Try it; it's impossible.

Now map to 3-D with $ϕ (x_{1}, x_{2}) = (x_{1}, x_{2}, x_{1} x_{2})$ :

Point	$ϕ (𝐱)$	Label
A	$(0,0,0)$	$- 1$
B	$(1,1,1)$	$- 1$
C	$(0,1,0)$	$+ 1$
D	$(1,0,0)$	$+ 1$

Take $𝐰 = (2, 2, - 4)$ , $b = - 1$ and evaluate $𝐰^{⊤} ϕ (𝐱) + b$ :

Point	Computation	Score	Sign	Label	✓
A	$0 + 0 - 0 - 1$	$- 1$	$-$	$- 1$	✓
B	$2 + 2 - 4 - 1$	$- 1$	$-$	$- 1$	✓
C	$0 + 2 - 0 - 1$	$+ 1$	$+$	$+ 1$	✓
D	$2 + 0 - 0 - 1$	$+ 1$	$+$	$+ 1$	✓

Perfectly separated in 3-D, with all four points exactly at margin 1. The interaction feature $x_{1} x_{2}$ was the missing ingredient — and note it's exactly what a degree-2 polynomial kernel supplies.

Step 2 — why we don't build $ϕ$ explicitly

The mapping worked, but it's expensive. A degree- $p$ polynomial map of $d$ features produces $(\binom{d + p}{p})$ dimensions. For $d = 1000$ , $p = 3$ that is ~167 million features per example. And the RBF kernel corresponds to an infinite-dimensional feature space — you literally cannot build it.

The escape. Look back at the SVM: written in its dual form, both training and prediction depend on the data only through inner products $𝐱_{i}^{⊤} 𝐱_{j}$ . Never through individual coordinates. So if you map to $ϕ$ , you only ever need $ϕ {(𝐱_{i})}^{⊤} ϕ (𝐱_{j})$ — a single number.

A kernel is a function that returns that number directly, without ever constructing $ϕ$ .

K (𝐱, 𝐳) = ϕ {(𝐱)}^{⊤} ϕ (𝐳)

🧪 Step 3 — proving the trick actually saves work

Take $d = 2$ and the polynomial kernel $K (𝐱, 𝐳) = {(𝐱^{⊤} 𝐳)}^{2}$ . Expand it algebraically:

{(𝐱^{⊤} 𝐳)}^{2} = {(x_{1} z_{1} + x_{2} z_{2})}^{2} = x_{1}^{2} z_{1}^{2} + 2 x_{1} x_{2} z_{1} z_{2} + x_{2}^{2} z_{2}^{2}

Now regroup as an inner product:

= \underset{ϕ (𝐱)}{\underset{⏟}{(x_{1}^{2}, \sqrt{2} x_{1} x_{2}, x_{2}^{2})}} \cdot \underset{ϕ (𝐳)}{\underset{⏟}{(z_{1}^{2}, \sqrt{2} z_{1} z_{2}, z_{2}^{2})}}

So $K (𝐱, 𝐳) = {(𝐱^{⊤} 𝐳)}^{2}$ is exactly the inner product in that 3-D quadratic feature space. ∎

Now count the arithmetic with real numbers, $𝐱 = (1,2)$ , $𝐳 = (3,4)$ :

Via the explicit map:

$ϕ (𝐱) = (1, \sqrt{2} \cdot 2, 4) = (1, 2.828, 4)$
$ϕ (𝐳) = (9, \sqrt{2} \cdot 12, 16) = (9, 16.971, 16)$
Inner product $= 9 + 47.999 + 64 = 𝟏𝟐𝟏$
Cost: build two 3-vectors (6 multiplications + 2 square roots), then 3 mults + 2 adds.

Via the kernel:

$𝐱^{⊤} 𝐳 = 1 (3) + 2 (4) = 11$
$K = 11^{2} = 𝟏𝟐𝟏$
Cost: 2 mults, 1 add, 1 square.

Same answer, 121, from a fraction of the work — and the saving grows explosively with $d$ and the degree. For the RBF kernel the explicit route isn't merely slower, it's impossible: the feature space is infinite-dimensional, yet $\exp (- γ ‖ 𝐱 - 𝐳 ‖^{2})$ is three lines of code.

The three kernels, and when to use them

Kernel	Formula	Feature space	Use when
Linear	$𝐱^{⊤} 𝐳$	the original space	$d$ is large relative to $n$ (text, bag-of-words), or the data really is separable. Fastest by far.
RBF / Gaussian	$\exp (- γ ‖ 𝐱 - 𝐳 ‖^{2})$	infinite-dimensional	The default when you don't know. Can fit any boundary.
Polynomial	${(𝐱^{⊤} 𝐳 + c)}^{d}$	all monomials up to degree $d$	You specifically believe feature interactions matter (e.g. price × category).

🧪 RBF, computed. With $γ = 1$ , $𝐱 = (0,0)$ , $𝐳 = (1,1)$ : $‖ 𝐱 - 𝐳 ‖^{2} = 1 + 1 = 2$ , so $K = e^{- 2} = 𝟎.𝟏𝟑𝟓𝟑$ . With $𝐳 = (0.1, 0.1)$ : $‖ \cdot ‖^{2} = 0.02$ , $K = e^{- 0.02} = 𝟎.𝟗𝟖𝟎𝟐$ .

The two hyperparameters, and how they interact

$γ$ controls how fast similarity decays with distance:

$γ$	Each support vector's influence	Boundary	Failure
small	reaches far	smooth, nearly linear	underfit
large	very local	wiggly, wraps individual points	overfit — in the limit each training point gets its own island

$γ$ and $C$ interact, which is why they must be tuned jointly on a 2-D grid rather than one at a time. Both large is a near-guaranteed overfit; both small underfits. The standard recipe is a logarithmic grid, e.g. $C \in {0.1, 1, 10, 100}$ × $γ \in {0.001, 0.01, 0.1, 1}$ , scored by cross-validation.

🔬Research

Research opportunity. Kernel methods have an elegant theory and a hard ceiling: computing the $n \times n$ kernel matrix costs $O (n^{2})$ memory and $O (n^{2} d)$ time, so exact kernel SVMs stop at roughly $10^{5}$ examples. Random-feature approximations (Random Fourier Features) and Nyström sampling trade a little accuracy for linear scaling, and the Neural Tangent Kernel line of work shows infinitely-wide neural networks behave like kernel machines — which makes "when does a network do something a kernel provably cannot?" a live, open, and genuinely deep question. ✅ Confirmed — Rahimi & Recht, "Random Features for Large-Scale Kernel Machines", NIPS 2007 (Random Fourier Features); Jacot, Gabriel & Hongler, "Neural Tangent Kernel: Convergence and Generalization in Neural Networks", NeurIPS 2018.

Interactive · simulator Kernel, C, gamma

Concept: How kernel choice and hyperparameters reshape an SVM decision boundary, and what over/underfitting looks like
Try: Kernel selector (linear / RBF / polynomial), sliders for C (0.01→100, log) and γ (0.001→10, log) and polynomial degree, over a fixed non-separable 2-D dataset with a toggle for the XOR layout.
Watch: The boundary, both margin lines, and the highlighted support vectors redraw live. A readout shows the support-vector count and train/validation accuracy side by side.
Insight: Push γ high and the boundary shatters into islands around individual points while training accuracy hits 100% and validation accuracy collapses — overfitting made visible. On the XOR toggle, the linear kernel cannot do better than chance no matter how C is set, and RBF solves it instantly.

The XOR worked example in §24 (separable in 3-D via x₁x₂, impossible in 2-D) and the C table in §23.

Putting it together 5 min

Everything in this lecture hangs off one skeleton. Here it is, with the dependencies drawn.

Three models, three philosophies — all fitting the same pipeline.

Naive Bayes models $P (x | y)$ — generative. Counting, one pass, no optimiser at all. Wins on tiny data and huge $d$ ; caps out early.
KNN models nothing. Stores everything, decides at query time. Zero training cost, $O (n d)$ inference, dies in high dimensions.
SVM models the boundary — discriminative. It is exactly hinge loss (§8) + L2 regularisation, so it plugs straight into the optimiser stack above. The kernel trick is the same algorithm with richer geometry at no extra cost.

The five threads that run through the whole lecture

1. Every loss is a negative log-likelihood. Gaussian → MSE, Laplace → MAE, Bernoulli → BCE, Categorical → CE. Choosing a loss is asserting a noise model. Huber is the one exception in this deck — a pragmatic weld rather than a likelihood — and it corresponds to a Gaussian core with heavy tails.

2. Every design choice is a bias–variance dial. $δ$ in Huber, $η$ in gradient descent, $B$ in mini-batching, the threshold $τ$ in classification, $K$ in KNN, $C$ and $γ$ in the SVM. Small/large in each case maps onto underfit/overfit. Once you see them as the same dial in different costumes, you stop memorising them.

3. Gradient shape determines model behaviour. MSE's gradient scales with error → fast, outlier- chasing. MAE's is constant → robust, bouncy. Huber's is capped → free gradient clipping. Hinge's is exactly zero past the margin → sparsity, support vectors. BCE-through-sigmoid collapses to $\hat{p} - y$ → no vanishing gradient. Ask "what does the gradient look like?" and every property falls out.

4. Scale matters, silently. Feature scaling breaks KNN and RBF-SVM. Target scaling breaks Huber's $δ$ . Loss scaling breaks plain SGD but not Adam. None of these throw an error — they just quietly give you a worse model.

5. The loss you minimise is not the number you're judged on. Cross-entropy vs recall-at-fixed- precision. This gap is where threshold moving, class weighting, $F_{β}$ , and PR-AUC all live, and it is where most real applied-science work actually happens.

Interview prep — Amazon Applied Scientist 30 min

Core questions, easy → hard

Depth probes — the follow-up after a good answer

Your answer	The probe	What they want
"MAE is robust to outliers"	"Why, mechanically?"	The gradient is $\pm 1$ regardless of error size, so every point gets one vote. MSE's gradient scales with error, so distant points vote with proportional weight.
"Use cross-entropy for classification"	"What breaks if I use MSE?"	The $σ (1 - σ)$ factor in the gradient vanishes when the model is confident, so a confidently wrong model can't recover.
"Adam is the default optimiser"	"When would you not use it?"	Convolutional vision models, where SGD+momentum often generalises slightly better; and any case where you've observed Adam converge to a worse solution — it does happen. Also: use AdamW, not Adam, if you want weight decay.
"Higher K smooths the boundary"	"So why not K = n?"	You'd predict the majority class for every input, ignoring the features entirely. Maximum bias, zero variance.
"The kernel trick avoids computing φ"	"What's the cost you're paying?"	The $n \times n$ kernel matrix: $O (n^{2})$ memory, $O (n^{2} d)$ time. Exact kernel SVMs stop scaling around $10^{5}$ examples.
"PR-AUC for imbalanced data"	"What's the random baseline for a PR curve?"	The positive base rate, not 0.5. Must be reported alongside.
"I'd tune C and gamma"	"Jointly or separately?"	Jointly, on a log grid — they interact, and both-large is a guaranteed overfit.
"Model A beat model B by 2 points"	"Is that significant?"	On 100 test examples the standard error is ~3.6 points. Report CV mean ± std, bootstrap the interval, and use a paired test (McNemar) to compare.

Whiteboard-ready derivations

Three results you should be able to produce cold, with chalk, in under three minutes each.

① MSE optimises toward the mean; MAE toward the median.

Model: predict a single constant c.
MSE:  L(c) = (1/n) Σ (yᵢ − c)²
      dL/dc = (1/n) Σ −2(yᵢ − c) = 0
      ⟹ Σ yᵢ − nc = 0  ⟹  c = (1/n) Σ yᵢ        ← the MEAN
MAE:  L(c) = (1/n) Σ |yᵢ − c|
      dL/dc = (1/n) Σ −sign(yᵢ − c)
            = (1/n)[ #(below c) − #(above c) ] = 0
      ⟹ #below = #above                          ← the MEDIAN
Sanity: y = [2,4,6,8,100] → mean 24, median 6.
        MSE(24)=1448 < MSE(6)=1772 ✓
        MAE(6)=20.4  < MAE(24)=30.4 ✓

② The BCE gradient through a sigmoid is $\hat{p} - y$ .

p̂ = σ(z) = 1/(1+e⁻ᶻ),   dσ/dz = σ(1−σ)
L  = −[ y log p̂ + (1−y) log(1−p̂) ]

∂L/∂p̂ = −y/p̂ + (1−y)/(1−p̂)

∂L/∂z = ∂L/∂p̂ · ∂p̂/∂z
      = [ −y/p̂ + (1−y)/(1−p̂) ] · p̂(1−p̂)
      = −y(1−p̂) + (1−y)p̂
      = −y + y p̂ + p̂ − y p̂
      = p̂ − y                                    ∎
Everything cancels. This is why sigmoid+BCE are always paired,
and why sigmoid+MSE suffers vanishing gradients.

③ The soft-margin SVM is hinge loss + L2, and margin $= 2 / ‖ w ‖$ .

Normalise so the closest points sit at wᵀx + b = ±1.
Distance from boundary to each margin plane = 1/‖w‖.
⟹ margin = 2/‖w‖.
Maximise 2/‖w‖  ⟺  minimise ½‖w‖².

Hard margin:  min ½‖w‖²   s.t.  yᵢ(wᵀxᵢ+b) ≥ 1
Soft margin:  min ½‖w‖² + C Σ ξᵢ
              s.t. yᵢ(wᵀxᵢ+b) ≥ 1 − ξᵢ,  ξᵢ ≥ 0

Objective increases in ξᵢ ⟹ take the smallest feasible one:
              ξᵢ = max(0, 1 − yᵢ f(xᵢ))          ← hinge loss

Substitute:   min ½‖w‖² + C Σ max(0, 1 − yᵢ f(xᵢ))
              └─ L2 reg ─┘   └──── hinge loss ────┘
Divide by C:  λ = 1/(2C).  Large C ⟹ weak regularisation.   ∎

Applied scenario — counterfeit product detection on the Amazon marketplace

Framing. Sellers list products; some are counterfeit. Removing a genuine listing hurts a legitimate seller and their customers; leaving a counterfeit up hurts a buyer and the brand. This is binary classification on a severely imbalanced problem — counterfeits are well under 1% of listings — with asymmetric, and importantly tiered, error costs. Not one model: a cascade.

Data. Listing text (title, bullets, description), price relative to the category and to the brand's own listings, seller tenure and history, image embeddings, review-text signals, and return/complaint rates. Labels come from enforcement actions, brand-registry reports, and test buys.

Model, in stages.

Baseline first, same day: Multinomial Naive Bayes on title + description n-grams with Laplace smoothing. One pass over the data, no GPU, no tuning. This is the number everything else must beat, and it usually catches the crude cases (§20).
Production candidate: gradient-boosted trees over the tabular + engineered features, plus a fine-tuned text encoder; blend the scores. Train with cross-entropy — I need calibrated probabilities, because the whole system is threshold-driven, so hinge/SVM is the wrong choice here despite the tempting sparsity.
Near-duplicate retrieval: counterfeits cluster — the same bad actor relists under new seller IDs. An approximate-KNN index over image and text embeddings (HNSW) surfaces "this listing is nearly identical to one we removed last week", which is a signal no per-listing classifier produces. This is §21–22 at production scale, with feature scaling and dimensionality reduction applied exactly as the slides warn.

Optimisation. AdamW, linear warmup then cosine annealing, mini-batch $B = 256$ . Class imbalance handled first by threshold moving on the validation set — it's free — and only then by class weighting if that isn't enough.

Metric. Not accuracy: predicting "genuine" always would score 99.5%. I'd report:

PR-AUC as the threshold-free summary, always quoted against the base-rate baseline;
Recall at the precision the enforcement team's capacity allows as the headline operating number — this is the number I'd put in the doc;
Recall on the randomly-audited holdout, since that's the only unbiased estimate;
Segmented by category and seller tenure, because an aggregate hides the fact that the model may be systematically wrong for new sellers.

Two thresholds, not one. High threshold → auto-suppress. Middle band → human review queue. Below → leave. That converts the precision/recall trade-off (§16) from a single painful compromise into a routing decision, and it's where the money is.

Failure modes I'd monitor.

Distribution shift — counterfeiters adapt within weeks. Track score distribution drift and schedule retraining; a static model decays fast here.
Feedback loops — suppressed listings never generate the outcome data that would have labelled them, so the training set narrows around what the model already believes. Hold out a small random fraction from enforcement to keep collecting unbiased labels.
Proxy leakage — if "seller was previously enforced against" is a feature, the model learns to predict past enforcement rather than counterfeiting. Audit feature importances for this.
Calibration drift — the thresholds are set on probabilities, so if calibration drifts the business meaning of the threshold silently changes even when AUC looks stable. Monitor a reliability curve, not just AUC.

What I'd ship first. The Naive Bayes baseline plus threshold-moved logistic regression on tabular features, behind the human-review queue. It is explainable to the enforcement team, deployable in days, and establishes the measurement infrastructure — the audit holdout, the segmented dashboards, the drift monitors — that every later model needs. Then iterate on the model with the harness already in place.

Leadership Principles tie-in

Dive Deep. The whole diagnostic chain in this lecture is Dive Deep in miniature: "ROC-AUC is 0.97" is a surface number; noticing that FPR's denominator contains 999,000 negatives, recomputing precision at 8.3%, and telling the team the model would flood their queue — that's refusing to accept a good-looking metric at face value. Concretely: on the counterfeit project, insisting on a randomly-audited holdout because the enforcement-derived labels are biased by past enforcement, even though it costs audit budget and makes the reported numbers look worse.

Insist on the Highest Standards. Reporting "macro-F1 = 0.86 ± 0.03 across 5 folds, versus 0.84 ± 0.04 for the baseline — not a significant difference on this sample size" instead of "we improved F1 by 2 points". Shipping a model on a difference smaller than its own error bar is the standard this principle exists to prevent.

Bias for Action. Shipping the Naive Bayes baseline and a threshold-moved logistic regression in week one, behind a human review queue, rather than spending a quarter on the sophisticated model. It's reversible, it's measurable, and it builds the evaluation harness the better model will need anyway.

Glossary 4 min

Term	Definition
Accuracy	$(T P + T N) / n$ . Fraction correct. Misleading under class imbalance.
Adagrad	Per-parameter learning rate scaled by $1 / \sqrt{cumulative squared gradient}$ . Decays to zero.
Adam	Momentum (1st moment) + RMSProp (2nd moment) + bias correction. Near scale-invariant.
AdamW	Adam with weight decay decoupled from the gradient. The transformer default.
AUC	Area under a curve. For ROC: the probability a random positive outscores a random negative.
Batch size ( $B$ )	Examples per gradient step. Noise falls as $1 / \sqrt{B}$ .
BCE	Binary cross-entropy. NLL of a Bernoulli. Gradient through a sigmoid is $\hat{p} - y$ .
Bias (statistical)	Error from a model too simple to represent the truth.
Convex	Bowl-shaped; exactly one minimum, and it's global.
Cosine annealing	LR schedule decaying along a cosine from $η_{\max}$ to $η_{\min}$ .
Cross-entropy	$- \sum_{c} p_{c} \log q_{c}$ . Coding cost of using $q$ when the truth is $p$ .
Curse of dimensionality	In high $d$ , all pairwise distances concentrate; "nearest" loses meaning.
Data leakage	Test information reaching the model. Symptom: great validation, bad production.
Empirical risk	Average loss on the training sample. The computable stand-in for true risk.
Epoch	One complete pass over the training data.
$F_{1}$ / $F_{β}$	Harmonic mean of precision and recall; $β > 1$ weights recall.
Functional margin	$y \cdot f (x)$ . Positive if correct; magnitude is confidence.
Generative vs discriminative	Models $P (𝐱, y)$ vs $P (y \| 𝐱)$ . NB vs LogReg/SVM.
Gradient	Vector of all partial derivatives. Points in the direction of steepest increase.
Hinge loss	$\max (0, 1 - y f (x))$ . Zero past margin 1 → sparse solutions.
Huber loss	Quadratic below $δ$ , linear above. $C^{1}$ everywhere; gradient capped at $\pm δ$ .
Hyperparameter	Set before training and never updated by the optimiser ( $η$ , $δ$ , $K$ , $C$ , $γ$ ).
Kernel	$K (𝐱, 𝐳) = ϕ {(𝐱)}^{⊤} ϕ (𝐳)$ computed without building $ϕ$ .
KL divergence	$\sum_{c} p_{c} \log (p_{c} / q_{c})$ . Excess coding cost. $\geq 0$ , not symmetric.
Laplace smoothing	Add $α$ to every count so no likelihood is zero. Mandatory for NB on text.
Lazy learner	No training phase; all work at query time. KNN.
Learning rate ( $η$ )	Step size. Convergence on a quadratic requires $η < 2 / L$ .
Logit	The raw pre-activation score, before sigmoid or softmax.
MAE	$\frac{1}{n} \sum \| y - \hat{y} \|$ . MLE under Laplace. Targets the median. Robust.
Margin (SVM)	$2 / ‖ 𝐰 ‖$ . The buffer between the boundary and the nearest points.
MLE	Choose parameters maximising the probability of the observed data.
Momentum	EMA of gradients. Effective step $\times \frac{1}{1 - β}$ in consistent directions.
MSE	$\frac{1}{n} \sum {(y - \hat{y})}^{2}$ . MLE under Gaussian. Targets the mean. Outlier-sensitive.
Naive assumption	Features conditionally independent given the class. Turns $2^{d}$ parameters into $d$ .
One-hot	A label as a vector with 1 in the true slot, 0 elsewhere.
PR-AUC	Area under the precision–recall curve. Baseline is the positive base rate, not 0.5.
Precision	$T P / (T P + F P)$ . Of what I flagged, how much was right?
$R^{2}$	$1 - S S_{r e s} / S S_{t o t}$ . Fraction of the mean-baseline's error eliminated. Can be negative.
Recall / TPR / Sensitivity	$T P / (T P + F N)$ . Of what was there, how much did I find?
RMSE	$\sqrt{MSE}$ . Same units as the target. Always $\geq$ MAE.
RMSProp	Adagrad with an EMA instead of a sum, so learning doesn't die.
ROC curve	TPR vs FPR across all thresholds.
Slack variable ( $ξ$ )	Permitted margin violation in a soft-margin SVM. Equals the hinge loss.
Softmax	$e^{z_{c}} / \sum_{j} e^{z_{j}}$ . Logits → a probability distribution. Shift-invariant.
Sub-gradient	A valid slope at a kink. Any value in $[- 1,1]$ at $\| e \|$ 's corner.
Support vector	A training point with $y f (x) \leq 1$ . The only points that affect the solution.
Surrogate loss	A convex upper bound on 0/1 loss that can actually be descended.
Type I / Type II error	False positive / false negative.
Variance (statistical)	Error from over-sensitivity to the particular training sample.

Check yourself 4 min

Answer without looking. If you can't, the section number tells you where to go.

Without looking anything up, write MSE, MAE, Huber, BCE, CE and hinge, and name the noise distribution each corresponds to. (§2–8)
Data is $[1, 3, 5, 7, 200]$ . What constant minimises MSE? What constant minimises MAE? (§2–3)
Prove Huber is differentiable at $| e | = δ$ . Where did the $- δ / 2$ come from? (§4)
Why does using MSE on a sigmoid output cause vanishing gradients, and what exactly cancels when you use BCE instead? (§6)
Logits are $(3, 1, 0)$ and the true class is the second. Compute the softmax and the cross-entropy loss. (§7)
A point has $y = + 1$ and $f (x) = 0.8$ . It's classified correctly. What is its hinge loss, and why isn't it zero? (§8)
Minimise $L (w) = {(w - 5)}^{2}$ from $w = 0$ with $η = 0.2$ . Give $w$ after three steps. For what $η$ does this diverge? (§10)
Why is the batch-size sweet spot in the hundreds and not the millions? Give the scaling law. (§12)
Adam's bias correction — what goes wrong without it, and why does the problem disappear as $t$ grows? (§13)
What bug does AdamW fix, and is torch.optim.Adam(weight_decay=0.01) affected? (§13)
1,000 patients, 20 sick. A model flags 60, of which 16 are genuinely sick. Compute accuracy, precision, recall and F1. Which number would you put in the report? (§15)
Why does F1 use the harmonic mean? Show a case where the arithmetic mean gives a misleading answer. (§16)
Compute AUC for scores $(0.9, 0.8, 0.6, 0.3)$ with labels $(1, 0, 1, 0)$ — both by tracing the curve and by counting pairs. Do they agree? (§17)
When does an excellent ROC-AUC coexist with a useless model? Give the numbers. (§17)
Why can $R^{2}$ be negative? Construct an example. (§18)
Why does Naive Bayes make an assumption everyone knows is false? Give the parameter-count argument with a number. (§19)
What breaks without Laplace smoothing, and why does one zero destroy the whole prediction? (§19)
Classify "free meeting" with the spam model in §19. Show the log-space computation. (§19)
A KNN query has neighbours at distances $(1.0, 1.4, 2.2, 2.8, 3.2)$ with classes $(1, 0, 0, 1, 1)$ . Give the prediction for $K = 1, 3, 5$ . (§21)
Why is training accuracy useless for choosing $K$ ? (§21)
Explain "in high dimensions all points become equidistant" using the mean and standard deviation of a sum of $d$ terms. (§22)
Compute the max-margin hyperplane for $𝐱_{+} = (3,0)$ with $y = + 1$ and $𝐱_{-} = (1,0)$ with $y = - 1$ . What is the margin? (§23)
Show that soft-margin SVM $=$ hinge $+$ L2. Why does large $C$ mean weak regularisation? (§23)
Verify that $K (𝐱, 𝐳) = {(𝐱^{⊤} 𝐳)}^{2}$ equals $ϕ {(𝐱)}^{⊤} ϕ (𝐳)$ for $ϕ (𝐱) = (x_{1}^{2}, \sqrt{2} x_{1} x_{2}, x_{2}^{2})$ , both algebraically and with $𝐱 = (2,1)$ , $𝐳 = (1,3)$ . (§24)
Which of the six losses in this lecture would you use for: house prices with data-entry errors · a 1,000-class image classifier · click-through prediction · a maximum-margin text classifier? Justify each in one sentence. (§2–8)

Going deeper 5 min

Ranked by what will move your understanding most, per hour spent.

Read first

Hastie, Tibshirani & Friedman — The Elements of Statistical Learning, ch. 4 (linear classification) and ch. 12 (SVMs and kernels). hard · Free PDF from the authors' Stanford page. The canonical treatment of everything in Parts 4–6, with the SVM dual derived properly. Ch. 12's margin geometry is worth the price of admission alone.
Bishop — Pattern Recognition and Machine Learning, ch. 1.5 (decision theory), ch. 4.2 (probabilistic generative models), ch. 6–7 (kernels and sparse kernel machines). hard · The best explanation anywhere of why losses take the shapes they do, via decision theory. Ch. 4.2 is the rigorous version of §19–20.
Sebastian Ruder — "An overview of gradient descent optimization algorithms." solid · A blog post that covers momentum → Adagrad → RMSProp → Adam with the equations and clear intuitions, in the same lineage order as §13. The single best hour you can spend on the optimisation half of this lecture. ⚠️ It predates AdamW and everything after, so pair it with the AdamW paper below.

The original papers, where they matter

Kingma & Ba — "Adam: A Method for Stochastic Optimization" (ICLR 2015). solid · Short and readable. Read it specifically for the bias-correction derivation in §2, which is the part everyone skips and the part that's actually subtle.
Loshchilov & Hutter — "Decoupled Weight Decay Regularization" (ICLR 2019). solid · The AdamW paper. It exists because of a bug that every framework had shipped for years, which makes it a genuinely instructive read about how the field self-corrects. Directly answers interview question 5's last bullet.
Cortes & Vapnik — "Support-Vector Networks" (Machine Learning, 1995). hard · The soft-margin SVM paper. Reading a foundational paper that is still exactly how people describe the method 30 years later is worth doing once.
Huber — "Robust Estimation of a Location Parameter" (Annals of Mathematical Statistics 35(1), 1964, pp. 73–101). hard · Where Huber loss comes from, and where the efficiency arguments behind the $δ$ choice live. ✅ Confirmed venue, year, and page range; the $1.345 σ$ constant (see §4) is confirmed and was corrected from an earlier $1.35 σ$ rounding in this file.

✅ On the two optimisers the slide names without explaining, now confirmed: Muon ("MomentUm Orthogonalized by Newton-Schulz"), released by Keller Jordan in October 2024. SOAP is Vyas et al., "SOAP: Improving and Stabilizing Shampoo using Adam", arXiv:2409.11321, ICLR 2025. Both are genuinely recent — worth reading the original sources directly rather than relying on a summary, since the field is still moving.

Do, don't just read

scikit-learn User Guide §1.4 (SVM), §1.6 (nearest neighbors), §1.9 (naive Bayes), §3.3 (metrics). intro · Unusually good documentation — each section explains the method, not just the API. The metrics page is the fastest way to internalise §14–18, and the SVM page has the definitive plots of what C and gamma do.
Build all six losses from scratch in NumPy, then check against PyTorch. intro · Concretely: write mse, mae, huber, bce_with_logits, cross_entropy, hinge, plus their gradients. Verify each gradient numerically with a finite-difference check ( $\frac{L (w + ϵ) - L (w - ϵ)}{2 ϵ}$ ). You will discover the log-sum-exp and log(0) problems from §6–7 personally, which is worth more than reading about them.
Distill.pub — "Why Momentum Really Works." solid · An interactive article where you drag the momentum coefficient and watch the trajectory on an ill-conditioned quadratic. It makes the condition-number argument in §10 and §13 visual in a way no static text achieves.
The plot_roc_curve / plot_precision_recall_curve examples in scikit-learn, run on a deliberately imbalanced dataset you construct. intro · Generate 10,000 negatives and 50 positives, fit anything, and plot both curves side by side. Seeing the ROC look excellent while the PR curve collapses — on data you made yourself — fixes §17 permanently.