Machine Learning

Machine learning is the study of algorithms that improve their performance on a task by using data rather than by being explicitly programmed with rules. A widely used framing, due to Tom Mitchell, is operational: a program learns from experience E with respect to a task T and a performance measure P if its performance on T, measured by P, improves with E. For a spam filter, T is labeling email as spam or not, E is a corpus of past emails with known labels, and P is the fraction classified correctly on new mail.

The big picture

Traditional software is a pile of rules a person wrote down. Asked in 1995 to build a spam filter that way, you would sit and enumerate: block anything containing "free money", block anything from this list of domains, block anything with more than four exclamation marks. The approach works until the spammers read your rules, and then it fails all at once. The machine learning move is to stop writing rules and instead hand the computer tens of thousands of emails already sorted into spam and not-spam, and let it find the rules itself. When the spammers change tactics, you do not rewrite the program; you retrain it on newer mail.

Arthur Samuel made this concrete at IBM in the late 1950s with a checkers program that improved by playing games and adjusting the weights of a position-scoring function, eventually beating its author. Nothing in the program encoded "good checkers strategy" directly. What it encoded was a way to score positions and a way to adjust that scoring in light of experience. That separation, between the shape of a solution and the tuning of a solution, is the structural idea underneath every method in this course.

Key idea: machine learning replaces "write the rules" with "specify the space of possible rules, define what a good rule means, and let an optimizer search". You still make all three decisions. You just make them one level up.

The three ingredients of a learning method

Almost every method in this course is assembled from three parts, and naming them keeps your thinking clear:

• The hypothesis class (or model family) is the set of candidate functions we are willing to consider, for example all straight lines, or all decision trees of depth 4. It encodes our assumptions about the world.
• The loss function measures how wrong a single prediction is. Averaging it over data gives a cost (or risk) we want to make small.
• The learning algorithm (the optimizer) searches the hypothesis class for the member with the lowest cost on the training data.

Learning, then, is optimization guided by data: pick a family, define what "wrong" means, and search for the best member.

These three dials turn independently, and confusing them is the most common source of muddled thinking about a model. Take "all straight lines" as the hypothesis class and squared error as the loss, and you get ordinary least squares, solvable in one matrix operation. Keep the same class but swap the loss for absolute error, and you get median regression: same candidate functions, a different notion of wrong, a different answer, and a harder optimization because absolute error has no derivative at zero. Keep squared error but swap the class to "all trees of depth 4", and you get a regression tree with a completely different shape of prediction. Same data, three different models, because two dials moved.

The restrictions built into a hypothesis class have a name: the model's inductive bias, the assumptions that let it say anything at all about inputs it has never seen. A learner with no inductive bias cannot generalize, because infinitely many functions agree with any finite training set and disagree everywhere else; something has to break the tie, and the hypothesis class is what breaks it. Choosing a linear model asserts "the relationship is roughly additive in the features". Choosing a tree asserts "the relationship is a set of nested threshold rules". Neither assertion is neutral, and the one that matches the problem usually wins.

The real goal is generalization

It is tempting to think the aim is a tiny error on the data we already have. It is not. A lookup table that memorizes every training example has zero training error and is useless on anything new. The true target is generalization: low expected loss on unseen data drawn from the same distribution. We estimate that expected loss by holding out a test set the model never sees during training. The central tension of the whole field is that we can only minimize error on data we have, while we care about error on data we do not.

Make the failure concrete. Suppose your "model" stores every training email verbatim and labels a new email spam only when it exactly matches a stored spam message. Training error is exactly zero, since every training email matches itself, and test error is essentially the base rate of the majority class, since no new email is ever an exact match. This is not a strawman. The 1-nearest-neighbor classifier, a real and genuinely useful method, has precisely this property: the nearest neighbor of a training point is itself, so its training error is always zero. Any procedure that selects models by training error alone will therefore rank 1-NN above everything else, which is a decisive reason never to select that way.

Key idea: training error is a number you can measure; generalization error is the number you actually care about. Learning is the discipline of using the first as a proxy for the second without being fooled by it.

Formal setup and notation

We write a training set of n examples as pairs, where each input is a feature vector x with d components and (in supervised learning) each has a label or target y. We assume the pairs are drawn independently from an unknown but fixed distribution. A model is a function that maps an input x to a prediction. This i.i.d. (independent and identically distributed) assumption is what makes a test-set estimate trustworthy: past and future come from the same source.

Training data: (x_1, y_1), ..., (x_n, y_n),  each x in R^d
Model:         f_theta(x) with parameters theta
Empirical risk (training cost):
    J(theta) = (1/n) * sum over i of  loss( f_theta(x_i), y_i )
Goal: choose theta so that the EXPECTED loss on new (x, y) is small.

Two risks now sit side by side, and the entire subject lives in the gap between them:

Empirical risk (measurable):    R_emp(theta) = (1/n) * sum_i loss( f_theta(x_i), y_i )
True (expected) risk (wanted):  R(theta)     = E over (x,y) drawn from D of loss( f_theta(x), y )
Generalization gap:             R(theta) - R_emp(theta)

We can compute the first exactly. We can never compute the second, because D, the data-generating distribution, is unknown and always will be. What we can do is estimate R by averaging the loss over a held-out sample the model never touched. Because those held-out examples are i.i.d. draws from D, that average is an unbiased estimate of R, and its uncertainty shrinks like 1 / sqrt(m) in the size m of the held-out set. That has a practical consequence people routinely forget. A test set of 100 examples gives an accuracy estimate whose standard error is about sqrt(0.5 * 0.5 / 100) = 0.05, five percentage points, so a two-point gap between two models on such a test set is noise, not evidence. Reporting three decimal places on a 100-example test set is false precision.

The i.i.d. assumption is doing heavy lifting here, and in the wild it is often false. Medical data collected at one hospital and deployed at another, credit models fitted before a recession and used during one, and fraud detectors facing adversaries who deliberately adapt all violate "same fixed distribution". The failure mode has a name, distribution shift, and no amount of clever training repairs it. The honest responses are monitoring live performance, retraining on recent data, and evaluating on data collected the way deployment data will actually arrive.

Worked example: why a perfect training score proves nothing

Six patients, one feature (a lab value x), and a binary label y meaning disease present:

x:  1.0   1.4   2.1   3.6   4.0   4.9
y:   0     0     1     0     1     1

Model A is 1-nearest-neighbor. Model B is the crude threshold rule "predict 1 when x is greater than 3.0". Compare them two ways.

• Step 1, training error of A. Every training point's nearest neighbor is itself, so A reproduces all six labels exactly. Training error = 0 / 6 = 0.00.
• Step 2, training error of B. B predicts 0, 0, 0, 1, 1, 1 against truth 0, 0, 1, 0, 1, 1. It misses the third point (predicted 0, truth 1) and the fourth (predicted 1, truth 0). Training error = 2 / 6 = 0.33.
• Step 3, evaluate on a seventh patient, held out, with x = 2.0 and true label 0. Model A finds the nearest training point, x = 2.1, whose label is 1, and predicts 1: wrong. Model B compares 2.0 with the threshold 3.0 and predicts 0: right.

What we just did: we ranked the two models by two different criteria and got opposite answers. By training error A wins 0.00 to 0.33; on the held-out patient B wins. The third training point (x = 2.1, y = 1) is very likely an unusual patient, and A committed the entire neighborhood around x = 2 to that single label. B, being cruder, could not commit that hard. Only the second comparison, made on data the model never saw, tells you anything about future performance.

Where this sits in the modern field

None of the framework above is repealed by the last decade of progress; what changed is the scale of the hypothesis classes. Deep networks (Module 6) are hypothesis classes with millions to hundreds of billions of parameters, fitted by gradient descent on a differentiable loss. Large language models are trained with a very specific supervised loss, next-token prediction over large text corpora, and are then adapted through further stages such as supervised fine-tuning and reinforcement learning from human feedback (Ouyang et al., 2022). Fluency does not exempt them from the framework: they minimize an empirical risk on a training corpus, and their characteristic failure of producing confident, well-formed statements that are not supported by any source is a generalization failure, extensively catalogued in the research literature (Ji et al., 2023).

Be precise about what any such system does. A model trained on next-token prediction learns a conditional distribution over text; it does not thereby acquire a verified database of facts, and it has no mechanism that guarantees its outputs are true. Keeping that distinction sharp is exactly the habit this lesson is training, and it applies to a logistic regression on ten features just as much as to a frontier model.

Where people get stuck

• "The algorithm is the model." Gradient descent is not a model; it is a search procedure. Two people can use the same optimizer on completely different hypothesis classes and get unrelated systems. Name all three ingredients before you argue about which "algorithm" is better.
• "More data always beats a better model." More data reliably helps with variance, and it does nothing for a hypothesis class that cannot express the pattern. A straight line fitted to a parabola stays wrong with a billion points.
• "The test set told me my model improved." If you consulted the test set to choose between models, you have used it for selection, and it is no longer an unbiased estimate of anything. Use validation data for choices and keep the test set sealed (Module 3).
• "Machine learning finds causes." It finds regularities that support prediction under the training distribution. A model can predict hospital readmission accurately from a feature that merely tracks who gets scheduled for follow-up, and that model will not tell you what happens if you intervene.

Recap

• Mitchell's framing names the three things any learning claim must specify: the task T, the experience E, and the performance measure P.
• Every method here is a hypothesis class, a loss function, and an optimizer; the three choices are independent.
• The hypothesis class carries the inductive bias, without which generalization is impossible.
• Empirical risk is computable; true risk is not. The gap between them is the whole problem.
• The i.i.d. assumption is what makes a held-out estimate meaningful, and distribution shift is what breaks it.
• Zero training error is easy and worthless on its own, as 1-nearest-neighbor demonstrates.

Every algorithm ahead is a specific choice of hypothesis class and loss, plus a way to minimize J. Keeping generalization in view, rather than raw training error, is what separates machine learning from mere curve-fitting, and it is the standard against which every method in the next six modules will be judged.

Sources

1. Mitchell, T. M. (1997). Machine learning. McGraw-Hill. cs.cmu.edu
2. Domingos, P. (2012). A few useful things to know about machine learning. Communications of the ACM, 55(10), 78-87. homes.cs.washington.edu
3. Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134-1142. web.mit.edu
4. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The elements of statistical learning (2nd ed.). Springer. hastie.su.domains
5. James, G., Witten, D., Hastie, T., & Tibshirani, R. (2021). An introduction to statistical learning (2nd ed.). Springer. statlearning.com
6. Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., ... Lowe, R. (2022). Training language models to follow instructions with human feedback. arXiv. arxiv.org
7. Ji, Z., Lee, N., Frieske, R., Yu, T., Su, D., Xu, Y., ... Fung, P. (2023). Survey of hallucination in natural language generation. ACM Computing Surveys, 55(12), 1-38. arxiv.org

Machine learning problems fall into a few broad families, separated mainly by what information the training data carries. The two you will use most are supervised and unsupervised learning.

The big picture

Here is the single question that sorts the field: what does one row of your data look like? If a row is a pair, an input together with the answer you want predicted, you are in supervised territory. If a row is just an input with no answer attached, you are in unsupervised territory. Everything else, the choice of algorithm, the loss function, the way you will measure success, follows from that one observation, which is why it is worth making deliberately and out loud before you write any code.

An analogy. Supervised learning is studying with an answer key: you attempt a problem, check the key, and adjust. Unsupervised learning is being handed an unsorted box of photographs and asked to organize it, with nobody to tell you whether "by decade" beats "by location". Both are legitimate learning; only one has an objective grade at the end, and that asymmetry shapes everything downstream, especially evaluation.

Key idea: the paradigm is a property of your data, not of your ambitions. Wanting to predict churn does not make an unlabeled customer table a supervised problem; you need recorded churn outcomes first.

Supervised learning

In supervised learning, every training example comes with a correct answer, the label y. The algorithm learns a mapping from inputs to labels so it can predict the label of new, unlabeled inputs. It is "supervised" because the labels act like an answer key during training. Supervised tasks split by the type of label:

• Classification: the label is a category from a finite set. Is this tumor benign or malignant? Which of ten digits is in this image? The output is discrete.
• Regression: the label is a continuous number. What will this house sell for? What temperature tomorrow? The output is real-valued.

Most of this course, linear and logistic regression, trees, forests, and SVMs, lives in the supervised world.

Formally, supervised learning assumes the pairs (x, y) are drawn from a joint distribution D over inputs and labels, and it tries to approximate some target functional of that distribution. That last phrase matters more than it sounds, because it tells you what a model is really estimating:

Regression with squared error:   f*(x) = E[ y | x ]        the conditional mean
Regression with absolute error:  f*(x) = median( y | x )   the conditional median
Classification with 0-1 loss:    f*(x) = argmax_c P(y = c | x)   the Bayes classifier

The optimal predictor under squared error is the conditional mean, and under absolute error it is the conditional median. So the loss you pick silently decides which summary of the label distribution you are estimating. If your target is skewed, say household income, least squares chases the mean and gets pulled by the tail, while absolute-error training tracks the typical household. Nobody tells you this at the API; you have to know it.

Supervised labels also come in more shapes than "category" and "number". Multiclass problems have more than two categories (ten handwritten digits). Multilabel problems attach several non-exclusive tags to one input (an article can be both "politics" and "economics"). Ordinal labels are categories with an order (a five-star rating), where treating them as unordered categories throws away information and treating them as plain numbers falsely assumes the gaps are equal. Structured prediction outputs whole objects, such as a sentence or a segmentation mask. The core machinery is the same in each case; only the loss and the output layer change.

Key idea: "supervised" specifies where the training signal comes from, and the shape of the label specifies which loss and which output layer you need.

Unsupervised learning

In unsupervised learning, there are no labels: only the inputs x. The goal is to discover structure hidden in the data itself. Two staple tasks are:

• Clustering: group similar examples together, for instance segmenting customers into behavioral types. k-means, later in the course, does this.
• Dimensionality reduction: re-express high-dimensional data in fewer dimensions while preserving what matters, for visualization or noise removal. Principal component analysis (PCA) does this.

Two more unsupervised tasks round out the picture. Density estimation models the distribution of the inputs themselves, which is what powers anomaly detection: score a new point by how improbable it is under the fitted density, and flag the tail. Generative modeling goes further and learns to draw new samples that resemble the training data. Ghahramani's framing is useful here: unsupervised learning is best understood as building a model of the data distribution P(x), with clustering and dimensionality reduction as two ways of describing that model compactly.

Because there is no answer key, unsupervised results are harder to score objectively; we judge them by usefulness and by proxy measures of structure. Those proxies exist and are worth naming: inertia and the silhouette coefficient for clusterings, explained variance for PCA, held-out log-likelihood for density models. Every one of them measures internal consistency, not correctness. A clustering can have an excellent silhouette score and still carve your customers along an axis nobody in the business cares about. The final arbiter for unsupervised output is almost always an external judgment: does this structure help a downstream task, or help a human decide something?

Key idea: unsupervised metrics score the geometry of a solution, never its truth. Always pair them with a downstream check.

A quick comparison and the middle ground

Aspect	Supervised	Unsupervised
Training data	Inputs with labels	Inputs only
Goal	Predict labels for new inputs	Find structure in the data
Typical tasks	Classification, regression	Clustering, dimensionality reduction
Evaluation	Compare prediction to true label	Proxy measures; usefulness

Other paradigms round out the map. Semi-supervised learning uses a few labels plus many unlabeled points, exploiting the shape of the unlabeled cloud to place a boundary more sensibly than the labels alone could. Reinforcement learning learns from a reward signal earned by taking actions in an environment, rather than from fixed labeled examples; the defining complication is that actions change the future data the agent sees, so the i.i.d. assumption of Lesson 1 no longer holds and the agent must trade exploration against exploitation. Knowing which family a problem belongs to is the first decision you make, because it determines which algorithms are even applicable.

Self-supervised learning: the modern middle

The paradigm that reshaped practice over the last decade is self-supervised learning, and the honest description is precise: it is supervised learning on labels manufactured from the raw data itself, so no human annotation is required. Hide part of the input and train the model to predict the hidden part. Because the "label" is just another piece of the input, an effectively unlimited training set falls out of unlabeled data.

• In language, BERT masks a subset of tokens and trains the model to recover them from both-sided context (Devlin et al., 2019), while GPT-style models predict the next token from the preceding ones. Both are supervised objectives over labels that were never annotated.
• In vision, contrastive methods such as SimCLR create two augmented views of the same image and train the representation to pull matching views together and push non-matching ones apart (Chen et al., 2020).

The usual workflow is two-stage: pretrain on a large unlabeled corpus with a self-supervised objective, then fine-tune on a much smaller labeled dataset for the actual task. This is why a team with only a few thousand labeled examples can now reach accuracy that once required millions. Be careful with the vocabulary, though. Self-supervised pretraining does not remove the need for labels when you want a specific supervised behavior; it reduces how many you need. And it inherits whatever is in the corpus, so a pretrained representation carries the statistical regularities, useful and otherwise, of the text or images it was built from.

Worked classification

Consider three problems. Predicting whether a credit-card transaction is fraudulent is supervised classification (discrete label: fraud or not). Predicting the dollar amount of next month's sales is supervised regression (continuous label). Grouping news articles into topics with no predefined categories is unsupervised clustering (no labels, structure discovered). Naming the paradigm immediately narrows your toolbox to the right methods.

Try it

Sort these four, and say what would have to be true of the data for each answer to hold. (a) An online store wants to place each of 40,000 products into one of 12 existing catalog categories, and 3,000 products are already categorized by hand. (b) A hospital wants to flag unusual lab panels for review, with no record of which past panels were unusual. (c) A utility wants to forecast tomorrow's peak demand in megawatts. (d) A warehouse robot must learn a route policy that minimizes travel time, learning only from how long each attempted route took.

Worked answer. (a) Supervised multiclass classification if you use only the 3,000 labeled products, or semi-supervised learning if you also exploit the 37,000 unlabeled ones. The categories are predefined and some labels exist, so this is not clustering. (b) Unsupervised anomaly detection via density estimation; with no record of past anomalies there is no label to supervise on. If the hospital later records reviewer verdicts, it becomes supervised classification. (c) Supervised regression, because the target is a continuous number and history supplies the labels automatically. (d) Reinforcement learning: the signal is a reward (negative travel time) earned by acting, and the robot's own choices determine which routes it ever observes. What we just did: in each case we asked what a single row of training data contains, and the paradigm followed.

Where people get stuck

• "Clustering will find my classes." Clustering finds groups that are compact in whatever feature space and distance you gave it. There is no guarantee those groups line up with a category you have in mind; if you know the categories and have examples, use classification.
• "Unsupervised means no assumptions." k-means assumes roughly round, similar-sized clusters; PCA assumes the interesting structure is linear and high-variance. Dropping labels does not drop inductive bias, it hides it.
• "Regression means linear regression." Regression names the task (continuous target). Trees, forests, SVMs, and neural networks all do regression.
• "Self-supervised is unsupervised." The training objective is supervised in form; what is absent is the human annotator, not the label. Keeping this straight explains why the same optimization machinery works for both.
• "I can turn a regression into a classification for free." Bucketing a continuous target into "high" and "low" discards ordering and magnitude, and the threshold you pick becomes an untested modeling assumption. Sometimes worth it, never free.

Recap

• Supervised learning has labeled pairs; unsupervised learning has inputs only. Look at one row of data to decide.
• Within supervised learning, classification predicts categories and regression predicts numbers, and the loss determines which summary of the label distribution you estimate.
• Labels also come as multiclass, multilabel, ordinal, and structured outputs, each with its own loss.
• Unsupervised tasks include clustering, dimensionality reduction, density estimation, and generative modeling, all scored by internal proxies rather than correctness.
• Semi-supervised learning mixes a few labels with many unlabeled points; reinforcement learning replaces labels with rewards from acting.
• Self-supervised pretraining manufactures labels from the data itself and is the backbone of modern language and vision systems.

Naming the paradigm immediately narrows your toolbox to the right methods and, just as usefully, sets your expectations about how you will ever know whether the result is any good. The rest of the course works mostly in the supervised setting, returning to the unsupervised side in Module 5.

Sources

1. Ghahramani, Z. (2004). Unsupervised learning. In O. Bousquet, U. von Luxburg, & G. Raetsch (Eds.), Advanced lectures on machine learning (pp. 72-112). Springer. mlg.eng.cam.ac.uk
2. Hastie, T., Tibshirani, R., & Friedman, J. (2009). Unsupervised learning. In The elements of statistical learning (2nd ed., ch. 14). Springer. hastie.su.domains
3. scikit-learn developers. (n.d.). Supervised learning. scikit-learn user guide. scikit-learn.org
4. scikit-learn developers. (n.d.). Unsupervised learning. scikit-learn user guide. scikit-learn.org
5. Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019). BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv. arxiv.org
6. Chen, T., Kornblith, S., Norouzi, M., & Hinton, G. (2020). A simple framework for contrastive learning of visual representations. arXiv. arxiv.org
7. Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction (2nd ed.). MIT Press. incompleteideas.net

To turn "learn a good model" into a solvable problem, we must say precisely what "good" means. That is the job of the loss function: a rule that assigns a nonnegative number to each prediction, larger when the prediction is worse. Once a loss is fixed, learning becomes the concrete optimization of finding parameters that make the average loss small.

The big picture

A loss function is where a value judgment enters the mathematics. It is the one place you get to say "this kind of mistake bothers me twice as much as that kind", and once you have said it, the optimizer will obey without argument. Choose squared error and you have declared that one error of size 10 is as bad as one hundred errors of size 1. Choose absolute error and you have declared they are equally bad only if there are ten of the small ones. Neither statement is more correct in the abstract; they are different statements about the world, and the fitted model differs accordingly.

Think of a loss as a price list. The optimizer is a ruthless shopper who will pay whatever the list says and nothing more. If your price list charges nothing for missing rare cancers and a great deal for false alarms, you will get a model that misses cancers. This is not a failure of the algorithm; it is the algorithm doing exactly what you wrote down. Most disappointing models in practice are models that optimized a loss nobody stopped to inspect.

Key idea: the loss function encodes your priorities, and the optimizer enforces them literally. Write the price list you actually mean.

Regression loss: squared error

For regression, the dominant choice is squared-error loss. For one example with prediction y-hat and true value y, the loss is the squared difference, and averaging over the dataset gives the mean squared error (MSE):

per-example loss:  (y_hat - y)^2
MSE = (1/n) * sum over i of ( f(x_i) - y_i )^2

Squaring makes all errors positive, penalizes big misses far more than small ones, and yields smooth calculus that gradient methods love. Worked example. Suppose predictions are 3, 5, 8 and truths are 2, 5, 6. The errors are 1, 0, 2; their squares are 1, 0, 4; the MSE is (1 + 0 + 4) / 3 = 5 / 3 = 1.67.

Squaring has a cost, though, and it is the same property that makes it useful: a single large error can dominate the entire average, so squared error is sensitive to outliers. Three alternatives are worth having in your toolkit:

MSE   = (1/n) * sum ( y_hat - y )^2                 units are the target squared
RMSE  = sqrt(MSE)                                   back in the target's own units
MAE   = (1/n) * sum | y_hat - y |                   every error weighted equally
Huber_delta(e) = 0.5 * e^2                 if |e| <= delta
                 delta*(|e| - 0.5*delta)   if |e| >  delta

RMSE is just MSE put back into the target's units so you can say "off by about 12,000 dollars" instead of "off by 144 million dollars squared"; it still ranks models exactly as MSE does, because square root is increasing. MAE treats a 10-unit miss as ten 1-unit misses and so shrugs off outliers, at the price of a kink at zero that gradient methods must handle. Huber loss is the compromise, behaving like squared error for small residuals and like absolute error beyond a threshold delta, giving smooth gradients near the optimum and bounded influence in the tails.

Worked comparison. Predictions 3, 5, 8 with truths 2, 5, 6 gave MSE 1.67. Now corrupt one truth so the errors become 1, 0, 12. MSE jumps to (1 + 0 + 144) / 3 = 48.33, a 29-fold increase from one point. MAE moves only from (1 + 0 + 2) / 3 = 1.00 to (1 + 0 + 12) / 3 = 4.33. Huber with delta = 1 charges 0.5 for the first error, 0 for the second, and 1 * (12 - 0.5) = 11.5 for the third, averaging 4.00. The three loss functions rank the same model very differently once an outlier appears, which is exactly why the choice deserves a decision rather than a default.

Key idea: squared error asks "avoid catastrophes"; absolute error asks "be typically close". Pick according to whether one big miss really is worse than several small ones in your setting.

Classification loss: 0-1 loss

For classification, the most natural loss is 0-1 loss: charge 0 for a correct label and 1 for a wrong one. Its average is exactly the misclassification rate, so 1 minus the average is accuracy. Worked example. On 5 examples, if the model is right on 4 and wrong on 1, the 0-1 losses are 0, 0, 0, 0, 1; the average is 1/5 = 0.20, an accuracy of 80%.

The catch is that 0-1 loss is flat almost everywhere and jumps in a step, so its gradient is zero or undefined and it cannot guide gradient descent. Worse, directly minimizing 0-1 loss over even the simple class of linear separators is computationally intractable in general. In practice we optimize a smooth surrogate loss (such as the logistic loss in Module 2) that is easy to minimize and tracks the 0-1 loss well, then report 0-1 error (accuracy) at the end.

The standard surrogates are all functions of the margin, written m = y * z where the label y is coded as +1 or -1 and z is the model's real-valued score. A positive margin means correct with confidence; a negative margin means wrong. Each surrogate is a different penalty curve over that one number:

0-1 loss       :  1 if m <= 0, else 0        the thing we care about, not optimizable
Hinge  (SVM)   :  max(0, 1 - m)              zero once m >= 1; kinked at m = 1
Logistic       :  log(1 + e^(-m))            never exactly zero; smooth everywhere
Exponential    :  e^(-m)                     used by AdaBoost; very harsh on m << 0

All three surrogates are convex upper bounds on the 0-1 loss, which is what makes them useful: minimizing an upper bound pushes the quantity of interest down, and convexity means the optimizer cannot get trapped. They differ in temperament. Hinge loss stops caring once an example is correctly classified past the margin, which is why SVM solutions depend only on a few support vectors. Logistic loss keeps applying gentle pressure forever, which is why it yields calibrated probabilities rather than just a decision. Exponential loss punishes badly misclassified points so severely that a single mislabeled example can distort the fit, which is a known fragility of AdaBoost on noisy data.

Losses can also be made asymmetric on purpose. If a missed fraud costs 500 dollars and a false alarm costs 5, weight the two error types 100 to 1 in the loss rather than post-processing an unweighted model. Most libraries expose this as class weights or sample weights, and it is a cleaner intervention than resampling the data.

Key idea: we optimize a smooth convex surrogate because we must, and we report the metric we actually care about because the surrogate is a means, not the goal.

Empirical risk minimization

The true risk is the expected loss over the whole data distribution, which we cannot compute because the distribution is unknown. Instead we minimize the empirical risk, the average loss over our finite sample. This strategy is empirical risk minimization (ERM), and it underlies nearly every algorithm here.

Write the two quantities side by side, because the whole theory of learning is an argument about their difference:

True risk        R(f)     = E over (x,y) ~ D of  loss( f(x), y )     unknown
Empirical risk   R_emp(f) = (1/n) * sum_i loss( f(x_i), y_i )        computable
ERM: choose f_hat = argmin over f in H of R_emp(f)

Why should this work at all? For a single fixed f, the law of large numbers says R_emp(f) converges to R(f) as n grows, so the empirical average is a good estimate. But ERM does not evaluate one fixed f; it searches a whole class H and returns the winner, and the winner is precisely the function that got the luckiest on this sample. That selection effect biases R_emp(f_hat) downward. What learning theory supplies is a uniform convergence guarantee: a bound holding simultaneously for every f in H, of the form

R(f) <= R_emp(f) + complexity(H, n, confidence)   for all f in H, with high probability

where the complexity term grows with the richness of H (measured by VC dimension or Rademacher complexity) and shrinks roughly like 1 / sqrt(n). Two consequences follow immediately and both are practical. First, a richer hypothesis class needs more data to earn the same guarantee. Second, since the bound is empirical risk plus complexity, the sensible strategy is to minimize the sum, not the first term alone. That strategy has a name, structural risk minimization, and it is the theoretical parent of the regularization you will meet in Module 3.

ERM has one crucial limitation. Driving empirical risk to zero can inflate the true risk, because a flexible model can fit the sample's noise. This gap between empirical and true risk is exactly overfitting, and controlling it, through regularization, validation, and sensible model choice, is a running theme of the course. Choosing the right loss is step one; refusing to trust empirical risk blindly is step two.

Worked example: the same predictions, three verdicts

A binary classifier produces scores z for four examples with true labels y coded as +1 or -1. Threshold at z = 0.

example:   1      2      3      4
y:        +1     +1     -1     -1
z:       +2.0   -0.3   -1.5   +0.4
margin m = y*z:  +2.0  -0.3  +1.5  -0.4

• Step 1, 0-1 loss. Examples 2 and 4 have negative margins, so they are misclassified. Average 0-1 loss = 2 / 4 = 0.50, an accuracy of 50 percent.
• Step 2, hinge loss. max(0, 1 - m) gives max(0, -1.0) = 0, max(0, 1.3) = 1.3, max(0, -0.5) = 0, max(0, 1.4) = 1.4. Average = 2.7 / 4 = 0.675. Note that examples 1 and 3 contribute exactly nothing: they are correct past the margin, so the SVM has no further interest in them.
• Step 3, logistic loss. log(1 + e^(-m)) gives log(1 + e^(-2.0)) = 0.127, log(1 + e^(0.3)) = 0.854, log(1 + e^(-1.5)) = 0.201, and log(1 + e^(0.4)) = 0.913. Average = 2.095 / 4 = 0.524. Every example contributes something, including the two already correct.

What we just did: one set of predictions, three numbers. The 0-1 loss says "half wrong" and stops. Hinge loss reports how far the two mistakes are from the margin and ignores the successes entirely. Logistic loss reports a smooth, always-positive penalty that keeps pushing every point further from the boundary. Now notice the gradients. Under 0-1 loss the derivative is 0 everywhere it exists, so no update is possible. Under logistic loss example 2 has a large derivative and example 1 a tiny one, so training automatically spends its effort where the model is wrong. That is the entire practical argument for surrogates.

Where people get stuck

• "Lower training loss means a better model." Only when comparing the same loss on the same data with the same model class. Comparing a logistic loss of 0.31 to a hinge loss of 0.28 is meaningless; they are different units.
• "Accuracy is the loss." Accuracy is the evaluation metric; cross-entropy is usually the training loss. Confusing them explains why validation loss can rise while validation accuracy holds steady, a model getting more confidently wrong on a few examples while its decisions stay put.
• "MSE is always the safe default." With heavy-tailed targets or a few corrupted labels, one point can dominate. Check the residual distribution before defaulting, and consider MAE or Huber when the tail is real.
• "I will just fix the class imbalance later with a threshold." Threshold tuning is legitimate (Module 7), but if the costs are known up front, encoding them in the loss through class weights lets the optimizer place the whole decision surface accordingly rather than shifting one cut afterwards.

Recap

• A loss function turns "be good" into a number; the optimizer will honor it literally, so it must express your real priorities.
• Squared error penalizes large misses hardest and estimates the conditional mean; MAE and Huber resist outliers.
• RMSE is MSE in the target's own units and ranks models identically.
• 0-1 loss is what we care about in classification but cannot be optimized directly, so we minimize convex surrogates: hinge, logistic, or exponential, all functions of the margin.
• Empirical risk minimization picks the hypothesis with the lowest average training loss.
• Uniform convergence bounds show the true risk is at most empirical risk plus a complexity penalty, motivating structural risk minimization and, in practice, regularization.

Choosing the loss is a modeling decision on the same footing as choosing the hypothesis class. Spend real thought on it, and remember that whatever you write down is what the optimizer will pursue to the exclusion of everything you left out.

Sources

1. Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge University Press. cs.huji.ac.il
2. Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018). Foundations of machine learning (2nd ed.). MIT Press. cs.nyu.edu
3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). Loss functions and robustness. In The elements of statistical learning (2nd ed., ch. 10.6). Springer. hastie.su.domains
4. Goodfellow, I., Bengio, Y., & Courville, A. (2016). Machine learning basics. In Deep learning (ch. 5). MIT Press. deeplearningbook.org
5. Ng, A., & Ma, T. (2023). CS229 lecture notes. Stanford University. cs229.stanford.edu
6. scikit-learn developers. (n.d.). Metrics and scoring: Quantifying the quality of predictions. scikit-learn user guide. scikit-learn.org
7. scikit-learn developers. (n.d.). Stochastic gradient descent. scikit-learn user guide. scikit-learn.org

Linear regression is the simplest and most important supervised model. It assumes the target is, approximately, a weighted sum of the features plus a constant. Despite its simplicity it is fast, interpretable, and the foundation on which logistic regression and neural networks are built.

The big picture

It is fashionable to treat linear regression as the thing you learn before the real methods. That is backwards. In production systems it remains a first choice whenever you need to defend a prediction to a regulator, a clinician, or a skeptical colleague, because the model is a sentence you can say out loud: "each extra square meter is worth about three thousand". It trains in milliseconds, it needs no hyperparameter search, it degrades gracefully with small data, and it gives you a baseline that any fancier model must beat before it earns its complexity. A gradient-boosted forest that wins by half a percent over a linear model on a 400-row dataset has probably won by luck.

There is a deeper reason to study it carefully. Logistic regression is linear regression with a squashing function on the output. A neural network is a stack of linear regressions with nonlinearities between them. Support vector machines find a particular linear function in a transformed space. If you genuinely understand the linear model, its cost surface, its solution, and its failure modes, you have understood the skeleton of most of the course.

Key idea: linear regression is not the simple case you outgrow. It is the atom that the later models are built from, and the baseline they must beat.

The model

With features x1 through xd, linear regression predicts:

y_hat = w_1*x_1 + w_2*x_2 + ... + w_d*x_d + b

The weights w say how much each feature moves the prediction, and the bias (intercept) b is the prediction when all features are zero. Writing a constant feature equal to 1 lets us fold b into the weight vector, so the model is compactly the dot product of a weight vector and the (augmented) input. Geometrically, with one feature this is a straight line; with two, a plane; in general, a hyperplane.

Now the point that surprises people: "linear" means linear in the parameters, not linear in the raw inputs. The model is a weighted sum of whatever columns you put in the matrix, and you may manufacture those columns however you like. Adding a column equal to x squared and another equal to x cubed still gives an ordinary least-squares problem, solved by exactly the same machinery, but the fitted curve is a cubic. This is called basis expansion, and it means the linear model can capture curvature, interactions, and thresholds:

Still linear regression, all of these:
    y_hat = w1*x + w2*x^2 + w3*x^3 + b               polynomial curve
    y_hat = w1*size + w2*rooms + w3*(size*rooms) + b  interaction term
    y_hat = w1*log(income) + b                        transformed feature
NOT linear regression:
    y_hat = w1 * x^(w2) + b        the parameter w2 sits in an exponent

Categorical features enter through one-hot encoding: a colour feature with three levels becomes three 0/1 columns, of which you keep two plus the intercept to avoid perfect collinearity (the three dummies would sum to the constant column). Once you see this, the boundary between "linear model" and "flexible model" is less about the equation and more about how many columns you are willing to invent and how much data you have to support them.

Key idea: linearity is a statement about the weights, not the features. Feature engineering is how a linear model becomes nonlinear in x.

The cost function

We fit the weights by minimizing mean squared error. It is customary to include a factor of one half so the derivative is clean:

J(w, b) = (1 / (2n)) * sum over i of ( y_hat_i - y_i )^2

This cost is a smooth, bowl-shaped (convex) function of the weights, which means it has a single global minimum and no misleading local minima, a very convenient property we exploit when training.

State the assumptions precisely, because different ones are needed for different claims. To use least squares as a predictor you need almost nothing beyond the target being roughly an additive function of the features you supplied. To interpret the coefficients or attach confidence intervals to them you need considerably more:

• Linearity in the parameters and correct specification: the columns you included really do span the systematic part of y. Omitting a variable that affects y and correlates with an included one biases the included coefficient. This is omitted-variable bias, and it is why observational coefficients are not causal effects.
• Independent errors. Residuals must not be correlated with each other. Time series and repeated measurements on the same subject routinely violate this, which shrinks the effective sample size and makes standard errors too small.
• Homoscedasticity. Error variance is constant across the range of the predictions. Spending data often violates this: high-income households vary more in absolute dollars than low-income ones.
• No perfect collinearity. No feature is an exact linear combination of others, or X-transpose-X is singular and no unique solution exists.

Normality of the errors is not required for least squares to be a good estimator; the Gauss-Markov result says that under the assumptions above, least squares has the smallest variance among linear unbiased estimators regardless of the error distribution. Normality is needed only for exact small-sample t and F inference. That distinction saves a lot of pointless worry about histograms of residuals when your goal is prediction.

Deriving the solution

Because J is convex and differentiable, the minimum is where the gradient vanishes. Differentiate the cost with respect to a single weight w_j, using the chain rule on the square:

J(w) = (1 / (2n)) * sum_i ( w . x_i - y_i )^2
dJ/dw_j = (1/n) * sum_i ( w . x_i - y_i ) * x_ij
Set every partial to zero and stack them in matrix form:
    X^T (X w - y) = 0    =>    (X^T X) w = X^T y      the NORMAL EQUATIONS
    w = (X^T X)^(-1) X^T y                            when X^T X is invertible

The name comes from geometry, and the geometry is worth carrying around. The predictions X w live in the column space of X, the set of all vectors you can build from your features. The condition X-transpose times the residual equals zero says the residual vector is orthogonal (normal) to every feature column. In other words, least squares projects y perpendicularly onto the column space of X: it takes the closest achievable point and leaves an error that has no remaining correlation with any feature. Any leftover pattern involving your features would mean you had not reached the closest point.

Interpreting a fitted model

Suppose we predict a house price (in thousands) from size in square meters and age in years and obtain price_hat = 3.0*size - 1.5*age + 50. The weight 3.0 says each additional square meter adds about 3 thousand to the predicted price, holding age fixed. The weight -1.5 says each extra year of age subtracts about 1.5 thousand. The intercept 50 is the baseline. This "holding others fixed" reading is why linear models are prized when you need to explain a prediction, not just make one.

Two cautions on that reading. First, the coefficient is measured in the units of its feature, so comparing raw coefficients across features is meaningless: 3.0 per square meter and -1.5 per year are not on the same scale. If you want to compare importance, standardize the features first (subtract the mean, divide by the standard deviation) and compare the standardized coefficients. Second, "holding age fixed" is a statement about the fitted surface, not about an experiment. If size and age are strongly correlated in your data, the model has little independent evidence about what happens when one moves and the other does not, and the individual coefficients become unstable even while the predictions stay fine. That is multicollinearity, diagnosed with the variance inflation factor and treated by dropping a redundant feature, combining features, or applying ridge regularization (Module 3).

Report fit with two numbers. RMSE gives typical error in the target's units. R-squared gives the fraction of the target's variance the model explains, computed as 1 - SS_res / SS_tot, where SS_res is the sum of squared residuals and SS_tot is the sum of squared deviations from the mean. R-squared never decreases when you add a feature, even a column of random noise, so on training data it is not a model-selection tool; use adjusted R-squared or, better, held-out error.

Worked example: fitting a line by hand

Four houses, with size x in hundreds of square feet and price y in thousands. Fit y_hat = w*x + b by least squares.

x:  1    2    3    4
y: 60   80   90  130

• Step 1, means. x_bar = (1 + 2 + 3 + 4) / 4 = 2.5. y_bar = (60 + 80 + 90 + 130) / 4 = 360 / 4 = 90.
• Step 2, centered products. Deviations in x are -1.5, -0.5, 0.5, 1.5; in y they are -30, -10, 0, 40. Their products are 45, 5, 0, 60, summing to S_xy = 110.
• Step 3, centered squares. Squares of the x deviations are 2.25, 0.25, 0.25, 2.25, summing to S_xx = 5.0.
• Step 4, slope and intercept. w = S_xy / S_xx = 110 / 5 = 22. b = y_bar - w * x_bar = 90 - 22 * 2.5 = 90 - 55 = 35.
• Step 5, check the fit. Predictions are 57, 79, 101, 123. Residuals are 3, 1, -11, 7, which sum to 0 as they must whenever an intercept is included. SS_res = 9 + 1 + 121 + 49 = 180.
• Step 6, R-squared. SS_tot = 900 + 100 + 0 + 1600 = 2600. R-squared = 1 - 180 / 2600 = 1 - 0.069 = 0.931. RMSE = sqrt(180 / 4) = sqrt(45) = 6.7 thousand.

What we just did: the slope formula w = S_xy / S_xx is the one-feature normal equation written out, and the residuals summing to zero is the orthogonality condition applied to the constant column. Both facts are the general theory in miniature, which is why hand-fitting a four-point line is worth the ten minutes.

Two ways to solve it

Because the cost is convex and quadratic, calculus gives a closed-form answer called the normal equations: set the gradient to zero and solve a linear system for the weights in one shot. This is exact and excellent for modest numbers of features. But it requires forming and inverting a d-by-d matrix, which costs on the order of d-cubed operations and becomes slow or numerically unstable when d is large. For big or streaming problems we instead minimize the cost iteratively with gradient descent, the subject of the next lesson. Both target the same convex bowl; they differ only in how they reach the bottom.

# Normal equations (matrix form), X has a column of 1s for the bias:
w = (X^T X)^(-1) X^T y      # one exact solve, cost grows with d^3

One practical note that separates textbook code from library code: no serious implementation actually computes that inverse. Forming X-transpose-X squares the condition number of X, which doubles the number of digits you lose to rounding. Production solvers instead factor X directly, by QR decomposition or by the singular value decomposition, and solve a triangular system. This is why scikit-learn's LinearRegression calls a least-squares routine rather than a matrix inverse, and why it still returns a sensible answer when the features are nearly collinear.

Where people get stuck

• "A high R-squared means a good model." R-squared is scale-free and can be high for a badly misspecified model or low for a genuinely useful one in a noisy domain. Always look at a residual plot: structure in the residuals (a curve, a fan shape) is the model telling you which assumption you broke.
• "The coefficient is the causal effect." It is a partial association within the fitted specification. Add or drop a correlated feature and it will move. Causal claims need a design, not a regression.
• "Linear regression cannot fit curves." It cannot fit curves in the features you gave it. Add x squared and it fits a parabola, still by ordinary least squares.
• "Least squares needs normally distributed data." It does not. The features need not be normal, the target need not be normal, and only exact small-sample inference relies on normal errors.
• "More features are safer." Every added column fits a little more noise. With d approaching n the model can interpolate the training data exactly and predict nothing, which is where regularization becomes mandatory.

Recap

• Linear regression predicts a weighted sum of features plus an intercept, and "linear" refers to the weights, not the features.
• Basis expansion and one-hot encoding let a linear model express curves, interactions, and categories.
• The squared-error cost is convex, so the minimum is unique and found where the gradient is zero.
• Setting the gradient to zero gives the normal equations, whose geometry is orthogonal projection of y onto the column space of X.
• Coefficients read as marginal effects holding other features fixed, subject to correct specification and low collinearity.
• Report RMSE and R-squared, but judge models on held-out data; solvers use QR or SVD rather than an explicit inverse.

Fit a linear model first on any new tabular problem. It costs almost nothing, it tells you the scale of the signal, and it gives every later model something honest to be compared against.

Sources

1. James, G., Witten, D., Hastie, T., & Tibshirani, R. (2021). Linear regression. In An introduction to statistical learning (2nd ed., ch. 3). Springer. statlearning.com
2. Hastie, T., Tibshirani, R., & Friedman, J. (2009). Linear methods for regression. In The elements of statistical learning (2nd ed., ch. 3). Springer. hastie.su.domains
3. scikit-learn developers. (n.d.). Linear models. scikit-learn user guide. scikit-learn.org
4. Zhang, A., Lipton, Z. C., Li, M., & Smola, A. J. (2023). Linear regression. In Dive into deep learning. Cambridge University Press. d2l.ai
5. Ng, A., & Ma, T. (2023). CS229 lecture notes. Stanford University. cs229.stanford.edu
6. Strang, G. (2010). Linear algebra (18.06): Projections and least squares. MIT OpenCourseWare. ocw.mit.edu
7. scikit-learn developers. (n.d.). Preprocessing data. scikit-learn user guide. scikit-learn.org

Gradient descent is the general-purpose engine for minimizing a differentiable cost, and it powers nearly all of modern machine learning. The intuition is simple: to reach the bottom of a valley in fog, feel which way is downhill and take a small step that way, then repeat.

The big picture

The previous lesson ended with a closed-form solution for linear regression, so why bother with an iterative method at all? Three reasons, and they compound. First, almost no other model has a closed form: logistic regression, neural networks, and most everything after Module 3 have no formula you can solve for the optimum. Second, even when a closed form exists it may be unaffordable; inverting a matrix costs on the order of d-cubed, so a hundred thousand features is out of reach while a gradient step over the same data is cheap. Third, gradient descent works when the data does not fit in memory, because it can consume the dataset in pieces.

The fog analogy is worth taking seriously rather than treating as decoration. You are on a hillside in dense fog with an altimeter and a way to feel the slope under your feet. You cannot see the valley floor. You can, however, determine which direction goes down most steeply right here, take a step that way, and repeat. Nothing about that procedure requires you to know the shape of the whole landscape, which is exactly why it scales to models with a hundred billion parameters where no one could possibly picture the surface.

Key idea: gradient descent needs only local information, the slope where you are standing. That is what makes it the universal engine: it never has to understand the whole cost surface, only the piece under its feet.

The gradient and the update rule

The gradient of the cost is the vector of partial derivatives with respect to every parameter. It points in the direction of steepest increase, so its negative points steepest downhill. Gradient descent repeatedly nudges the parameters in the negative-gradient direction:

repeat until convergence:
    theta := theta - alpha * gradient_of_J(theta)

Here alpha is the learning rate, a small positive number setting the step size. For linear regression the gradient has a clean form; the update for a single weight w_j is:

w_j := w_j - alpha * (1/n) * sum over i of ( y_hat_i - y_i ) * x_ij

Each step compares predictions to truth, weights the error by the feature, and shifts the weight to shrink the error. Read the structure of that expression, because it recurs everywhere: error times input. If a feature was large and the prediction was too high, that weight gets pushed down hard. If the feature was zero for an example, that example says nothing about that weight. The same error-times-input form appears in logistic regression and in every layer of a neural network, which is not a coincidence but a consequence of the chain rule.

Worked example: three steps by hand

Take the one-parameter cost J(w) = w^2, whose derivative is dJ/dw = 2w, and start at w = 3 with alpha = 0.2.

step 0:  w = 3.000   J = 9.000   grad = 6.000
step 1:  w = 3.000 - 0.2*6.000 = 1.800   J = 3.240   grad = 3.600
step 2:  w = 1.800 - 0.2*3.600 = 1.080   J = 1.166   grad = 2.160
step 3:  w = 1.080 - 0.2*2.160 = 0.648   J = 0.420

Each step multiplies w by (1 - 2*alpha) = 0.6, so the parameter decays geometrically toward the minimum at w = 0 and never overshoots it. Now repeat with alpha = 1.2. The multiplier becomes 1 - 2*1.2 = -1.4, so w goes 3, then -4.2, then 5.88, then -8.232: the sign flips every step and the magnitude grows. The cost diverges. For this quadratic the exact stability condition is alpha < 1, with the fastest convergence at alpha = 0.5, which lands on the minimum in a single step. That is the whole story of the learning rate in miniature: a threshold set by the curvature of the cost, below which you converge and above which you explode.

What we just did: we watched the same algorithm converge and diverge with nothing changed but one number. Notice also that the gradient shrinks as we approach the minimum, so the steps automatically get smaller near the bottom even at a fixed alpha. Gradient descent decelerates on its own.

The learning rate is delicate

The learning rate controls everything about convergence:

• Too small: progress is correct but painfully slow, taking many iterations.
• Too large: steps overshoot the minimum and the cost can oscillate or diverge to infinity.
• Just right: the cost falls quickly and levels off near the minimum.

A healthy sign is that the cost decreases on (almost) every iteration. If it rises, lower alpha. A workable search is to try alpha in a rough geometric ladder, 0.001, 0.003, 0.01, 0.03, 0.1, 0.3, and plot the cost against iteration for each; the largest value whose curve falls smoothly is usually close to right.

The threshold that decides stability is set by curvature. For a quadratic cost the relevant quantity is the largest eigenvalue L of the Hessian, and gradient descent converges when alpha < 2 / L. Meanwhile the speed of convergence is governed by the condition number kappa = L / mu, the ratio of the largest to the smallest curvature. When kappa is near 1 the cost surface is a round bowl and descent walks straight in. When kappa is large the bowl is a long narrow ravine: the step size is capped by the steep direction while progress along the shallow direction crawls, and the path zigzags across the valley. The number of iterations needed scales roughly with kappa.

This is precisely why feature scaling is not cosmetic. Suppose one feature is house size in square feet (values in the thousands) and another is the number of bedrooms (values 1 to 5). The curvature along the size direction is larger by a factor of roughly a million, giving an enormous condition number and a cost surface shaped like a canyon. Standardizing each feature to mean 0 and standard deviation 1 makes the curvatures comparable and can turn thousands of iterations into dozens. Compute the mean and standard deviation on the training split only, then apply them to validation and test data, or you have leaked information (Lesson 9).

Key idea: the learning rate is bounded by the steepest curvature, while progress is set by the shallowest. Scaling the features improves the ratio, which is the single cheapest speedup available.

Batch, stochastic, and mini-batch

The variants differ in how much data each step uses to estimate the gradient:

Variant	Data per update	Character
Batch	All n examples	Smooth, stable, slow per step
Stochastic (SGD)	One example	Noisy, fast, cheap per step
Mini-batch	A small group (e.g. 32)	The practical compromise

Batch gradient descent uses the whole dataset for each update: accurate but expensive on large data. Stochastic gradient descent (SGD) uses one random example per update: each step is cheap and the noise can even help escape flat regions, though the path jitters. Mini-batch uses a small batch, blending stability with speed, and is the default for training neural networks. All three descend the same cost; they trade accuracy of each step against how many steps you can afford.

The statistics are simple and worth stating. A mini-batch gradient is an unbiased estimate of the full-batch gradient, and its standard deviation falls like 1 / sqrt(B) in the batch size B. Quadrupling the batch halves the noise but quadruples the compute per step, so there is no free accuracy: the reason mini-batches dominate is hardware, since a GPU evaluates 32 or 256 examples in nearly the time it takes to evaluate one. Small batches also inject noise that acts as a mild regularizer, and empirical studies have found small-to-moderate batches often generalize at least as well as very large ones for a fixed epoch budget (Masters & Luschi, 2018). A rule that survives contact with practice: if you increase the batch size, you usually need to increase the learning rate too.

Beyond plain descent: momentum and adaptive methods

Plain gradient descent is rarely what actually trains a modern model. Two families of improvement matter.

Momentum accumulates a running average of past gradients and steps along that, which damps the zigzag in a ravine and accelerates along the consistent direction, in the same way a heavy ball rolling downhill is less deflected by side slopes than a light one:

v := beta * v + grad_J(theta)          # beta is typically 0.9
theta := theta - alpha * v

Adaptive methods give each parameter its own effective step size, scaled by a running estimate of that parameter's gradient magnitudes. AdaGrad introduced the idea; Adam (Kingma & Ba, 2015) combined a momentum term with a per-parameter scale and became the default optimizer for deep learning. Adam maintains running averages of the gradient (first moment) and of the squared gradient (second moment), applies a bias correction for their initialization at zero, and divides the step by the square root of the second moment. A refinement, AdamW (Loshchilov & Hutter, 2019), decouples weight decay from the adaptive scaling, and is the standard choice for training transformers today.

Two honest qualifications. Adaptive optimizers reduce how carefully you must tune alpha; they do not eliminate tuning, and on some problems well-tuned SGD with momentum still generalizes better. And none of these methods changes the fundamental picture: they are all still descending a cost surface using local gradient information. Alongside the optimizer, practitioners schedule the learning rate over training, commonly a short linear warmup followed by cosine or step decay, which lets early steps be cautious and late steps be fine.

Knowing when to stop

Convergence is declared, not detected. Common criteria are that the change in cost falls below a tolerance, that the gradient norm falls below a tolerance, that a fixed iteration budget is exhausted, or, most usefully in practice, that validation error stops improving. That last one is early stopping, and it is genuinely a form of regularization: stopping before the optimizer has fully fitted the training data limits how much noise the model absorbs. For non-convex costs, gradient descent finds a local minimum or a flat region rather than a certified global optimum, which for neural networks turns out to be acceptable in practice.

Where people get stuck

• "The cost is bouncing, so training failed." With SGD or mini-batches the per-step cost is a noisy estimate and will bounce. Plot a running average or the cost per epoch. Only a persistent upward trend means the learning rate is too high.
• "Gradient descent gets stuck in local minima." For convex costs (linear and logistic regression, linear SVMs) there are no bad local minima at all. In high-dimensional non-convex problems the more common obstacles are saddle points and long flat plateaus, not deep bad basins.
• "Normalize everything, including the target and the test set statistics." Scale features using training-split statistics only. Scaling the target is optional and changes the meaning of the loss value.
• "Adam means I can skip the learning rate." Adam has a learning rate too, commonly around 1e-3 for small models and much smaller for large ones, and it still matters.
• "More epochs are always better." Past the point where validation error bottoms out, further epochs fit noise. Watch validation, not training.

Recap

• Gradient descent minimizes a differentiable cost using only local slope information, stepping opposite the gradient.
• The update is theta := theta - alpha * gradient, and for squared error the per-weight gradient has the form error times input.
• Too small an alpha wastes iterations; too large diverges. The stability threshold is set by the largest curvature, alpha < 2 / L.
• The condition number governs speed, which is why standardizing features (using training statistics only) is such a cheap win.
• Batch, stochastic, and mini-batch differ only in how much data estimates each gradient; mini-batch noise falls like 1 / sqrt(B).
• Momentum smooths the path, Adam and AdamW adapt a step size per parameter, and early stopping on validation error is both a stopping rule and a regularizer.

Every model in the rest of this course is trained by some descendant of this loop. When a model will not train, the first three things to check are the learning rate, the feature scaling, and whether the cost curve is falling at all.

Sources

1. Bottou, L. (2012). Stochastic gradient descent tricks. In Neural networks: Tricks of the trade (2nd ed., pp. 421-436). Springer. leon.bottou.org
2. Kingma, D. P., & Ba, J. (2015). Adam: A method for stochastic optimization. arXiv. arxiv.org
3. Loshchilov, I., & Hutter, F. (2019). Decoupled weight decay regularization. arXiv. arxiv.org
4. Ruder, S. (2017). An overview of gradient descent optimization algorithms. arXiv. arxiv.org
5. Goodfellow, I., Bengio, Y., & Courville, A. (2016). Optimization for training deep models. In Deep learning (ch. 8). MIT Press. deeplearningbook.org
6. Goh, G. (2017). Why momentum really works. Distill. distill.pub
7. Masters, D., & Luschi, C. (2018). Revisiting small batch training for deep neural networks. arXiv. arxiv.org

Despite its name, logistic regression is a classification method, the standard first choice for predicting a binary label such as spam or not, disease or not. It adapts the linear model to output a probability between 0 and 1 rather than an unbounded number.

The big picture

Start with the obvious bad idea, because seeing why it fails motivates everything else. Code the labels 0 and 1 and run ordinary linear regression on them. Two problems appear immediately. The fitted line is unbounded, so it will happily predict 1.4 or -0.3 for extreme inputs, and there is no way to read those as probabilities. Worse, a single far-away point drags the whole line and can move the decision boundary even though it was already classified correctly and confidently. Squared error simply is not the right price list for a yes-or-no question.

Logistic regression fixes both problems with one change: keep the linear score, but pass it through a function that compresses the whole real line into the interval (0, 1). The linear part supplies the flexibility and interpretability; the squashing function supplies the probability semantics. That single design pattern, a linear map followed by a nonlinearity, is repeated in every neuron of every neural network you will build in Module 6, which is why this lesson is load-bearing far beyond binary classification.

Key idea: logistic regression is linear regression on the log-odds scale. Everything linear about it lives on that scale, and the sigmoid is just the translation back to probabilities.

From a linear score to a probability

Logistic regression first computes a familiar linear score (also called the logit), then squashes it through the sigmoid (logistic) function into the interval (0, 1):

z = w . x + b                 # linear score
sigmoid(z) = 1 / (1 + e^(-z)) # maps any z to a value in (0, 1)
y_hat = P(y = 1 | x) = sigmoid(z)

The sigmoid is an S-shaped curve: large positive z gives an output near 1, large negative z near 0, and z = 0 gives exactly 0.5. We read the output as the estimated probability of the positive class, then apply a threshold (usually 0.5) to decide the label.

Odds, log-odds, and what a coefficient means

Invert the sigmoid and the model reveals what it is actually linear in. If p = sigmoid(z), then a little algebra gives

p = 1 / (1 + e^(-z))     =>     p / (1 - p) = e^z     =>     log( p / (1 - p) ) = z = w . x + b

The quantity p / (1 - p) is the odds of the positive class, and its logarithm is the log-odds or logit. So the model says: the log-odds of the outcome are a linear function of the features. That gives every coefficient a clean reading. Increasing feature x_j by one unit adds w_j to the log-odds, which multiplies the odds by e^(w_j). The quantity e^(w_j) is the odds ratio, and it is what clinical and social-science papers actually report.

Numbers make this concrete. A coefficient of 0.69 gives an odds ratio of e^0.69 = 2.0, so a one-unit increase doubles the odds. A coefficient of -0.35 gives e^(-0.35) = 0.70, a 30 percent reduction in odds. Note carefully that doubling the odds is not doubling the probability: if p starts at 0.10 the odds are 0.111, doubling them to 0.222 gives p = 0.182, not 0.20. The effect on probability depends on where you start, which is exactly the nonlinearity the sigmoid introduces and the reason the model is linear on the log-odds scale rather than the probability scale.

Key idea: a logistic coefficient is an additive effect on log-odds and a multiplicative effect on odds. Translate to probability only at a specific starting point.

Why not squared error? The log loss

Pairing the sigmoid with squared-error loss produces a non-convex cost riddled with local minima, and it barely punishes confident mistakes. Instead we use cross-entropy, also called log loss, which is convex for logistic regression and penalizes confident wrong answers severely:

loss for one example (label y in {0, 1}):
    -[ y * log(y_hat) + (1 - y) * log(1 - y_hat) ]
J = average of that loss over all n examples

Read it in two halves. If the true label is 1, only -log(y_hat) survives: predicting 0.99 costs almost nothing, predicting 0.01 costs a lot. If the true label is 0, only -log(1 - y_hat) survives, symmetrically. The loss goes to infinity as a confident prediction turns out wrong, which strongly discourages overconfidence. We minimize this cost with the same gradient descent from the previous lesson; remarkably, the gradient has the identical clean form, error times feature.

Cross-entropy is not an arbitrary choice, it is the negative log-likelihood of the model. Treat each label as a Bernoulli draw with success probability y_hat. The likelihood of one observation is y_hat^y * (1 - y_hat)^(1 - y); take logs, sum over the data, and negate, and you have exactly the cost above. Minimizing cross-entropy is therefore maximum likelihood estimation, which is where the method's statistical guarantees come from and why the fitted probabilities mean something rather than being arbitrary scores.

The gradient is worth deriving once, because the cancellation is the reason the formula is so simple. Write z = w . x + b and use the fact that the sigmoid satisfies d(sigmoid)/dz = sigmoid(z) * (1 - sigmoid(z)):

L = -[ y*log(p) + (1-y)*log(1-p) ]        with p = sigmoid(z)
dL/dp  = -y/p + (1-y)/(1-p) = (p - y) / ( p*(1-p) )
dp/dz  = p*(1-p)
dL/dz  = dL/dp * dp/dz = p - y            the p*(1-p) factors cancel exactly
dL/dw_j = (p - y) * x_j                   chain rule through z = w.x + b

The messy denominator vanishes, leaving prediction minus truth times the feature, precisely the linear-regression gradient with p in place of y_hat. One update rule, two models. This cancellation happens only because log loss is paired with the sigmoid; with squared error the p*(1-p) factor survives, and it goes to zero whenever the model is confidently wrong, which is exactly when you most want a large gradient. That is the deeper reason squared error trains badly here, beyond the convexity argument.

Worked example: one training step by hand

A model has weights w = (0.5, -1.0) and bias b = 0.2. A training example has x = (2, 1) with true label y = 1. Use alpha = 0.1.

• Step 1, the score. z = 0.5*2 + (-1.0)*1 + 0.2 = 1.0 - 1.0 + 0.2 = 0.2.
• Step 2, the probability. p = 1 / (1 + e^(-0.2)). Since e^(-0.2) = 0.8187, p = 1 / 1.8187 = 0.550.
• Step 3, the loss. y = 1, so L = -log(0.550) = 0.598. For comparison, a confident correct prediction of 0.95 would cost only -log(0.95) = 0.051, and a confident wrong one of 0.05 would cost 3.00.
• Step 4, the gradient. p - y = 0.550 - 1 = -0.450. So dL/dw_1 = -0.450 * 2 = -0.900, dL/dw_2 = -0.450 * 1 = -0.450, and dL/db = -0.450.
• Step 5, the update. w_1 := 0.5 - 0.1*(-0.900) = 0.590. w_2 := -1.0 - 0.1*(-0.450) = -0.955. b := 0.2 - 0.1*(-0.450) = 0.245.
• Step 6, verify improvement. The new score is 0.590*2 + (-0.955)*1 + 0.245 = 1.180 - 0.955 + 0.245 = 0.470, giving p = 0.615 and loss -log(0.615) = 0.486, down from 0.598.

What we just did: because the model under-predicted a positive example (p - y was negative), every weight moved in the direction that raises the score, and it moved twice as far on the feature whose value was 2 as on the feature whose value was 1. Error times feature, exactly as the formula promised.

The decision boundary

We predict class 1 when y_hat is at least 0.5, which happens exactly when the score z is at least 0. Since z = w . x + b is linear, the boundary w . x + b = 0 is a straight line (or hyperplane): logistic regression is a linear classifier. It draws one flat divider through feature space, class 1 on one side, class 0 on the other.

This makes it interpretable and fast, but unable, on its own, to separate classes that curl around each other; for that we need the nonlinear models later in the course. A useful bonus: because the weights sit inside the sigmoid, a positive weight means that increasing that feature increases the probability of the positive class.

The threshold is a separate decision from the model, and 0.5 is only the default. Lowering it to 0.2 predicts positive more readily, catching more true positives at the cost of more false alarms; Module 7 makes that tradeoff quantitative with precision, recall, and ROC analysis. Nothing about retraining is required to change a threshold, and on imbalanced problems the default 0.5 is usually the wrong operating point.

More than two classes: softmax

For K classes, keep one weight vector per class, compute K scores, and normalize them into a probability distribution with the softmax function:

z_k = w_k . x + b_k                for k = 1..K
P(y = k | x) = e^(z_k) / sum over j of e^(z_j)
loss = -log( P(y = true class | x) )     categorical cross-entropy

Softmax reduces to the sigmoid when K = 2, and the gradient keeps the same shape: predicted probability minus the one-hot label, times the feature. This is the standard output layer of essentially every classification neural network, so the machinery you have just learned is the last layer of a modern image or text classifier.

Two practical hazards

First, complete separation. If some feature (or combination) perfectly splits the classes in your training set, the likelihood keeps improving as the weights grow without bound: the model can always sharpen the sigmoid a little more, so the maximum-likelihood estimate does not exist and the fitted coefficients run off toward infinity. Symptoms are enormous coefficients and enormous standard errors. The cure is regularization; this is one reason scikit-learn applies L2 regularization to LogisticRegression by default, which makes the penalized objective strictly convex and the solution finite and unique.

Second, calibration. Because logistic regression is fitted by maximum likelihood on a proper scoring rule, its probabilities are usually well calibrated: among the cases it assigns 0.7, roughly 70 percent really are positive. This is not true of every classifier. Empirical comparisons have found that boosted trees and support vector machines produce systematically distorted probabilities, correctable after the fact with Platt scaling or isotonic regression (Niculescu-Mizil & Caruana, 2005). If you plan to use the number as a probability and not just to rank cases, check a calibration curve rather than assuming.

Where people get stuck

• "Logistic regression is regression." The name records that it regresses the log-odds on the features. The task is classification.
• "An odds ratio of 2 doubles the risk." It doubles the odds. At a baseline probability of 0.1 that means a rise to 0.18, not to 0.20; at a baseline of 0.5 it means a rise to 0.67.
• "The decision boundary is curved because the sigmoid is curved." The sigmoid is monotone, so the set where p = 0.5 is exactly the set where z = 0, which is a hyperplane. The output surface curves; the boundary does not.
• "Huge coefficients mean strong evidence." They often mean separation or collinearity. Check for a feature that perfectly predicts the label, and regularize.
• "Accuracy is the way to evaluate it." With imbalanced classes, accuracy hides everything. Use log loss for probability quality, and precision, recall, or AUC for decisions.

Recap

• Logistic regression computes a linear score and squashes it with the sigmoid to get P(y = 1 | x).
• It is linear in the log-odds; a coefficient is an additive effect on log-odds and a multiplicative effect e^(w) on odds.
• The training loss is cross-entropy, which is the negative log-likelihood of a Bernoulli model, and it is convex.
• The gradient simplifies to (p - y) * x because the sigmoid derivative cancels, giving the same update form as linear regression.
• The decision boundary where p = 0.5 is the hyperplane z = 0; the threshold itself is a separate, tunable choice.
• Softmax generalizes the model to K classes, and regularization is needed to keep coefficients finite under separation.

Logistic regression is the strongest simple baseline in classification and the direct ancestor of the output layer in modern networks. If a complicated model cannot beat it by a margin larger than your test-set noise, the complicated model has not earned its place.

Sources

1. Cox, D. R. (1958). The regression analysis of binary sequences. Journal of the Royal Statistical Society: Series B, 20(2), 215-242. find source ↗
2. Hastie, T., Tibshirani, R., & Friedman, J. (2009). Linear methods for classification. In The elements of statistical learning (2nd ed., ch. 4). Springer. hastie.su.domains
3. James, G., Witten, D., Hastie, T., & Tibshirani, R. (2021). Classification. In An introduction to statistical learning (2nd ed., ch. 4). Springer. statlearning.com
4. scikit-learn developers. (n.d.). Logistic regression. In Linear models, scikit-learn user guide. scikit-learn.org
5. Ng, A., & Ma, T. (2023). CS229 lecture notes. Stanford University. cs229.stanford.edu
6. Niculescu-Mizil, A., & Caruana, R. (2005). Predicting good probabilities with supervised learning. Proceedings of the 22nd International Conference on Machine Learning, 625-632. cs.cornell.edu
7. scikit-learn developers. (n.d.). Probability calibration. scikit-learn user guide. scikit-learn.org

Why does a more powerful model sometimes predict worse? The answer is the bias-variance tradeoff, the single most useful lens for understanding generalization. It decomposes a model's expected error on new data into pieces that pull in opposite directions as we change model complexity.

The big picture

The dartboard picture is the fastest way in. A thrower whose darts all cluster tightly but land two inches left of the bullseye has low variance and high bias: consistent and consistently wrong. A thrower whose darts scatter all over the board but average out to the bullseye has low bias and high variance: right on average, unreliable in any single throw. You would like both to be small, and the frustrating fact of statistical learning is that the knobs available to you usually trade one against the other.

The crucial move that makes this precise is imagining repeating the whole experiment. You have one training set, but conceptually you could have drawn a different sample of the same size from the same population, fitted the same procedure, and obtained a different model. Bias and variance are statements about that imaginary ensemble of models, not about the single model on your screen. Bias asks: averaged over all those training sets, does the procedure land on the truth? Variance asks: how much do the fitted models differ from one another? Holding this thought experiment in mind is what makes the rest of the lesson click.

Key idea: bias and variance are properties of a learning procedure applied to random data, not of one fitted model. That is why you diagnose them by comparing training and validation error rather than by inspecting coefficients.

Three sources of error

Imagine training your model many times on different random datasets from the same source and averaging its errors on a fresh test point. That expected error splits into three parts:

• Bias: error from wrong assumptions, the gap between the average prediction and the truth. A model too simple to capture the pattern (say, a straight line for a curved trend) has high bias. High bias causes underfitting.
• Variance: error from sensitivity to the particular training set, how much predictions wobble as the data changes. A model too flexible chases noise and has high variance. High variance causes overfitting.
• Irreducible error: noise inherent in the problem that no model can remove.

The decomposition, stated precisely

Assume the world generates data as y = f(x) + eps, where f is the true regression function and eps is noise with mean 0 and variance sigma^2. Let f_hat be the model fitted to a random training set D, and fix a test point x. Averaging over both the training sets and the noise:

E[ ( y - f_hat(x) )^2 ]  =  ( E[f_hat(x)] - f(x) )^2  +  E[ ( f_hat(x) - E[f_hat(x)] )^2 ]  +  sigma^2
                         =        Bias^2               +              Variance                +  Irreducible
where E[.] averages over random training sets D (and, for y, over the noise).

The derivation is one line of algebra once you add and subtract the average prediction. Write the error as (y - E[f_hat]) + (E[f_hat] - f_hat), square it, and take expectations; the cross term vanishes because E[f_hat - E[f_hat]] = 0 by construction. What is left is exactly the three terms above. Two consequences deserve emphasis. First, every term is nonnegative, so sigma^2 is a hard floor: no model, however good, can have expected squared error below the noise variance. Second, bias and variance are the only parts you can influence, and complexity moves them in opposite directions.

Worked example: measuring the three terms

Suppose the truth at a particular test point is f(x) = 10, noise has sigma^2 = 1, and we fit the same procedure to five different training sets, obtaining predictions at that point of 8.6, 9.2, 8.8, 9.0, 8.4.

• Step 1, the average prediction. (8.6 + 9.2 + 8.8 + 9.0 + 8.4) / 5 = 44.0 / 5 = 8.80.
• Step 2, bias. E[f_hat(x)] - f(x) = 8.80 - 10 = -1.20, so Bias^2 = 1.44.
• Step 3, variance. Deviations from 8.80 are -0.20, 0.40, 0.00, 0.20, -0.40. Their squares are 0.04, 0.16, 0.00, 0.04, 0.16, averaging 0.40 / 5 = 0.08.
• Step 4, total. Expected squared error = 1.44 + 0.08 + 1.00 = 2.52, of which 57 percent is bias, 3 percent is variance, and 40 percent is irreducible noise.

What we just did: we diagnosed a clear underfitting problem quantitatively. This procedure is consistent (tiny variance) and consistently too low (large bias), so the right response is a more flexible model or better features, not more data. Now imagine a second procedure whose five predictions were 12.5, 7.1, 11.0, 6.8, 12.6, averaging 10.0. Its bias is exactly zero, but its variance is (6.25 + 8.41 + 1.00 + 10.24 + 6.76) / 5 = 6.53, for a total of 7.53, far worse despite being unbiased. Averaging away that variance is precisely what bagging will do in Module 4.

Key idea: unbiasedness is not the goal. Total expected error is, and a little bias bought cheaply in exchange for a lot of variance is the best trade in applied machine learning.

The tradeoff with complexity

As model complexity rises, bias falls (the model can fit more shapes) but variance rises (it fits each dataset's quirks). A very simple model underfits: high bias, low variance, poor on both training and test data. A very complex model overfits: low bias, high variance, excellent on training data but poor on test data. The total error is a U-shaped curve, minimized at an intermediate sweet spot.

Diagnosing from the numbers

You can read the regime directly off training and validation error:

Symptom	Diagnosis	Remedy
High training AND validation error	Underfitting (high bias)	More complex model, more features
Low training but high validation error	Overfitting (high variance)	Simpler model, regularization, more data
Low training AND validation error	Good fit	Ship it

The large gap between training and validation error is the fingerprint of overfitting. This diagnosis drives every fix in the rest of the module: regularization to curb variance, and cross-validation to measure where the sweet spot lies.

Learning curves: reading the regime off a plot

A single pair of numbers can mislead, so plot training and validation error against training set size. The shapes are diagnostic and they tell you what to do next:

• High bias. Both curves flatten early and converge to a high error, close together. Adding data changes nothing, because the model already extracts everything its class can express. Spend your effort on richer features or a more flexible model.
• High variance. Training error stays low, validation error stays much higher, and the gap narrows slowly as data is added. Here more data genuinely helps, as do regularization and simplification.
• Good fit. The curves converge to a low error with a small gap, and the remaining error is close to your estimate of the irreducible noise.

The practical value is that these two failures call for opposite remedies. Collecting another fifty thousand rows to fix a high-bias model is expensive and useless; simplifying a high-variance model that just needed more data throws away accuracy. Diagnose before you prescribe.

Where the classical picture needs updating

The U-shaped curve above is a genuine and useful description of what happens with classical model families. It is not the whole story for very large models, and a graduate treatment should say so precisely.

Zhang and colleagues (2017) showed that standard deep networks can fit a large image dataset with entirely random labels, achieving zero training error, which means their raw capacity is large enough to memorize. Yet the same architectures, trained on the real labels, generalize well. So parameter count alone cannot be the right measure of effective complexity, and classical bounds phrased purely in terms of capacity do not explain the observed behavior.

Belkin and colleagues (2019) traced what happens as capacity keeps increasing past the point of interpolation, where the model fits the training data exactly. Test error first follows the classical U, rising as the model starts to overfit, peaks near the interpolation threshold, and then falls again as capacity grows further. They named this the double descent curve. Nakkiran and colleagues (2019) reproduced the effect across architectures and showed a matching phenomenon in training time as well as model size.

Read this carefully, because it is easy to overstate. Double descent does not repeal the bias-variance decomposition, which is an algebraic identity and remains true. What it shows is that the mapping from "number of parameters" to "variance" is not monotone: in the heavily overparameterized regime, gradient descent tends to select among the many interpolating solutions one with small norm, and that implicit preference acts like a regularizer. The classical U-shape is one region of a larger picture, and the practical advice is unchanged: measure generalization on held-out data rather than reasoning from parameter counts, in either direction.

Where people get stuck

• "Bias means the model is unfair." Statistical bias here is the gap between the average prediction and the truth. Social bias in ML systems is a different and important topic, and the shared word causes real confusion.
• "Overfitting means the training error is too low." Low training error is not itself a problem. The problem is the gap between training and validation error, which is the visible shadow of variance.
• "More data fixes overfitting, so it fixes everything." More data reduces variance, which is only one of the three terms. It does nothing for bias and nothing for irreducible noise.
• "I can compute the bias of my model." Not from one training set, and not without knowing the truth f. The decomposition is a conceptual tool; what you actually measure is the training-validation gap.
• "Because of double descent, bigger is always better." The second descent is observed in specific overparameterized regimes with particular training procedures. With a few hundred rows of tabular data, the classical U is exactly what you will see.

Recap

• Expected squared error decomposes exactly into bias squared, variance, and irreducible noise.
• Bias and variance describe a learning procedure over random training sets, not a single fitted model.
• Rising complexity lowers bias and raises variance, giving the classical U-shaped test-error curve.
• Underfitting shows as high training and validation error together; overfitting shows as a large gap between them.
• Learning curves distinguish the two regimes and tell you whether more data will help.
• In heavily overparameterized models, test error can descend a second time past the interpolation threshold, so judge by held-out measurement rather than by parameter count.

The bias-variance lens is the most reusable idea in the course. Every technique in the next two lessons, and most of Module 4, is an attempt to buy a large reduction in variance for a small increase in bias.

Sources

1. Geman, S., Bienenstock, E., & Doursat, R. (1992). Neural networks and the bias/variance dilemma. Neural Computation, 4(1), 1-58. find source ↗
2. Hastie, T., Tibshirani, R., & Friedman, J. (2009). Model assessment and selection. In The elements of statistical learning (2nd ed., ch. 7). Springer. hastie.su.domains
3. James, G., Witten, D., Hastie, T., & Tibshirani, R. (2021). Statistical learning. In An introduction to statistical learning (2nd ed., ch. 2). Springer. statlearning.com
4. Belkin, M., Hsu, D., Ma, S., & Mandal, S. (2019). Reconciling modern machine learning practice and the bias-variance trade-off. arXiv. arxiv.org
5. Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B., & Sutskever, I. (2019). Deep double descent: Where bigger models and more data hurt. arXiv. arxiv.org
6. Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. arXiv. arxiv.org
7. scikit-learn developers. (n.d.). Underfitting vs. overfitting. scikit-learn examples. scikit-learn.org

Regularization is the main tool for fighting overfitting. The idea is to discourage the model from becoming too complex by adding a penalty on the size of its weights to the training cost. Large weights let a model make wild, wiggly predictions that chase noise; penalizing them keeps the fit smoother and lowers variance, at the price of a little more bias, moving the model toward the bias-variance sweet spot.

The big picture

Lesson 7 diagnosed the disease: variance, caused by a model flexible enough to chase noise. Regularization is the treatment, and the cleanest way to think about it is as a budget. Instead of letting the optimizer spend as much coefficient magnitude as it likes, you charge for it. A feature now has to earn its weight by reducing the training loss more than the penalty costs. Weak, noisy features cannot pay, so they shrink toward zero, while genuinely informative features survive.

There is an equivalent and often more illuminating picture, the constrained form. Minimizing loss + lambda * penalty is the Lagrangian of the problem "minimize the loss subject to the penalty being at most some budget t". Every lambda corresponds to some budget t, and larger lambda means smaller budget. In this picture the solution is where the elliptical contours of the squared-error loss first touch the boundary of the budget region, and the shape of that region is what distinguishes L2 from L1 in a way that makes their behavior obvious rather than mysterious.

Key idea: regularization deliberately biases the model in exchange for stability. You accept being a little wrong on average in order to stop being wildly different every time the data changes.

The regularized cost

We minimize the usual loss plus a penalty term scaled by a strength lambda:

J(w) = original_loss(w) + lambda * penalty(w)

The two dominant penalties differ in how they measure "size":

• L2 regularization (ridge) penalizes the sum of squared weights: penalty = sum of w_j^2. It shrinks all weights smoothly toward zero without usually making any exactly zero.
• L1 regularization (lasso) penalizes the sum of absolute weights: penalty = sum of |w_j|. It can drive some weights exactly to zero, performing automatic feature selection and yielding a sparse model.

Note that the bias term b is conventionally left unpenalized, since shrinking the intercept has no bearing on model complexity, and penalizing it would make the model's predictions depend on where you happened to put the origin of your target variable.

Why L2 shrinks: the ridge solution in closed form

Ridge regression is one of the few regularized problems with a formula, and the formula explains the behavior:

Ordinary least squares:  w = (X^T X)^(-1) X^T y
Ridge:                   w = (X^T X + lambda*I)^(-1) X^T y

Adding lambda to the diagonal does two things at once. Numerically, it guarantees the matrix is invertible even when the features are collinear or when there are more features than observations, which is exactly the situation where least squares breaks down. Statistically, if you rotate into the coordinate system where X-transpose-X is diagonal with entries d_j (its eigenvalues, the amount of variation in each direction), the ridge estimate shrinks each coordinate of the least-squares solution by a factor

shrink factor for direction j  =  d_j / (d_j + lambda)

Directions where the data varies a lot (large d_j) are barely touched; directions where the data barely varies (small d_j), which are precisely the directions where the least-squares coefficient is least reliable, get shrunk hard. Ridge is not a blunt instrument. It applies the most shrinkage exactly where the evidence is weakest, which is why it works so well against multicollinearity.

Worked example. One standardized feature with sum of squares X^T X = 20 and X^T y = 40, so the unpenalized slope is 40 / 20 = 2.0. With lambda = 5 the ridge slope is 40 / (20 + 5) = 1.60, a shrink factor of 20 / 25 = 0.80. With lambda = 20 it is 40 / 40 = 1.00, half the original. With lambda = 180 it is 40 / 200 = 0.20. Notice the coefficient approaches zero but never reaches it for any finite lambda; that is the defining behavior of L2.

Why L1 zeroes out: corners and soft thresholding

Now the geometry. In two dimensions the L2 budget region is a circle and the L1 budget region is a diamond with corners on the axes. The loss contours are ellipses expanding from the unpenalized solution, and the answer is the first point of contact. A circle has no preferred direction, so contact almost never happens exactly on an axis: both coefficients stay nonzero. A diamond has sharp corners sitting on the axes, and expanding ellipses hit corners disproportionately often. A corner is a point where one coordinate is exactly zero. That is the whole explanation for sparsity, and it generalizes to d dimensions, where the L1 region is a cross-polytope with corners, edges, and faces of every dimension.

The algebra agrees. For a single standardized feature, minimizing (1/2)(w - w_ols)^2 + lambda*|w| gives the soft-thresholding rule:

w_lasso = sign(w_ols) * max( |w_ols| - lambda, 0 )
Compare L2 on the same problem:  w_ridge = w_ols / (1 + lambda)

Worked comparison. With w_ols = 3.0 and lambda = 1, lasso gives sign(3) * max(3 - 1, 0) = 2.0 while ridge gives 3 / 2 = 1.5. With w_ols = 0.6 and the same lambda = 1, lasso gives max(0.6 - 1, 0) = 0 exactly, while ridge gives 0.6 / 2 = 0.30. Lasso subtracts a fixed amount and clips at zero, so any coefficient smaller than lambda is eliminated outright. Ridge multiplies by a fixed factor, so small coefficients get proportionally smaller but never vanish. That single difference is the whole L1-versus-L2 story.

The Bayesian reading

Both penalties have a probabilistic interpretation that makes them feel less arbitrary. Maximizing the posterior of a linear model with a Gaussian prior on the weights, w ~ Normal(0, tau^2), gives exactly ridge regression, with lambda determined by the ratio of noise variance to prior variance. Using a Laplace (double-exponential) prior instead gives exactly lasso. So L2 encodes the belief "coefficients are probably small and none is exactly zero", while L1 encodes "most coefficients are probably exactly zero and a few are large". Choosing a penalty is choosing a prior belief about how the world is structured, and the sparse belief is often right in high-dimensional problems.

L2 versus L1 at a glance

Property	L2 (ridge)	L1 (lasso)
Penalty	Sum of squares of weights	Sum of absolute values
Effect on weights	Shrinks all smoothly	Sets some exactly to zero
Feature selection	No	Yes (sparse solution)
Best when	Many small useful effects	Few features truly matter

A blend of the two, called the elastic net, combines smooth shrinkage with sparsity and is popular when features are correlated.

Choosing the strength lambda

The strength lambda controls the tradeoff and is a hyperparameter, a knob we set rather than learn from the training loss directly:

• lambda = 0: no penalty, back to ordinary (possibly overfitting) fitting.
• lambda too large: weights are crushed toward zero, the model underfits (high bias).
• lambda just right: variance drops with only a small rise in bias, and generalization improves.

Because the best lambda cannot be read off the training error (which always prefers lambda = 0), we choose it with a validation set or cross-validation, trying several values and keeping the one with the lowest validation error. Search on a logarithmic grid, since what matters is the order of magnitude: 1e-4, 1e-3, 1e-2, 1e-1, 1, 10, 100. Plotting every coefficient against lambda gives the regularization path, a genuinely useful diagnostic that shows the order in which features drop out under lasso and how stable each coefficient is under ridge. A common refinement is the "one standard error rule": among lambdas whose cross-validated error is within one standard error of the best, choose the largest, buying extra simplicity for statistically indistinguishable performance.

Scaling is not optional here

A penalty on coefficient magnitude is only meaningful if the magnitudes are comparable. Suppose one feature is measured in meters and another in millimeters. Switching the second to meters multiplies its coefficient by a thousand, which changes the penalty it incurs by a factor of a thousand for L1 or a million for L2, and therefore changes which features get eliminated. Unregularized least squares is invariant to such rescaling; regularized fitting is not. Standardize your features before penalizing them, computing the means and standard deviations on the training split only, and do it inside your cross-validation loop rather than before it.

Regularization beyond the penalty term

The word covers any deliberate constraint that trades a little bias for less variance, and several of the most effective techniques are not penalty terms at all:

• Early stopping. Halting gradient descent when validation error bottoms out limits how far the weights travel from their small initial values, which for linear models is closely related to an L2 penalty.
• Dropout. Randomly zeroing a fraction of a neural network's units during each training step prevents units from co-adapting into fragile combinations, and it approximates averaging over an ensemble of thinned networks (Srivastava et al., 2014).
• Data augmentation. Training on label-preserving transformations (image crops, flips, noise) tells the model which variations it should ignore, which is an assumption about the world expressed as extra data rather than as a penalty.
• Weight decay. In deep learning the L2 penalty is usually implemented as decay applied directly in the update. With adaptive optimizers the two are not equivalent, which is precisely the correction AdamW introduced (Lesson 5).
• Structural limits. Fewer layers, shallower trees, or fewer clusters all constrain the hypothesis class directly.

Where people get stuck

• "Lasso does feature selection, so it identifies the true features." Among a group of correlated features, lasso tends to pick one essentially arbitrarily and zero the rest. Rerun on a resampled dataset and a different member of the group may survive. Elastic net is more stable here, and neither method licenses a causal claim.
• "Bigger lambda is safer." Past the sweet spot you are simply underfitting, converting a variance problem into a bias problem. The validation curve is U-shaped in lambda, and you want its bottom.
• "Regularization fixes bad features." It fixes variance. Features that are wrong, leaky, or missing are not repaired by shrinkage.
• "L1 and L2 mean the same thing everywhere." In scikit-learn's LogisticRegression the strength parameter is C, which is the inverse of lambda, so smaller C means more regularization. Read the documentation before tuning.
• "Penalize the intercept too, for consistency." Do not. It makes the fit depend on an arbitrary shift of the target.

Recap

• Regularization adds a penalty on coefficient size, trading a small increase in bias for a large reduction in variance.
• Ridge has the closed form (X^T X + lambda*I)^(-1) X^T y and shrinks each direction by d_j / (d_j + lambda), hardest where the data is least informative.
• Lasso soft-thresholds, subtracting lambda and clipping at zero, so coefficients smaller than lambda are eliminated exactly.
• The geometry explains it: the L1 budget region has corners on the axes, the L2 region is smooth and round.
• Ridge corresponds to a Gaussian prior on the weights and lasso to a Laplace prior; elastic net blends both.
• Standardize features before penalizing, tune lambda on a log grid by cross-validation, and remember that early stopping, dropout, and augmentation are regularizers too.

Regularization is the mechanism; cross-validation, the next lesson, is how we tune it and how we verify that the trade actually paid off.

Sources

1. Hoerl, A. E., & Kennard, R. W. (1970). Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1), 55-67. find source ↗
2. Tibshirani, R. (2011). Regression shrinkage and selection via the lasso: A retrospective. Journal of the Royal Statistical Society: Series B, 73(3), 273-282. tibshirani.su.domains
3. Zou, H., & Hastie, T. (2005). Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B, 67(2), 301-320. hastie.su.domains
4. Hastie, T., Tibshirani, R., & Wainwright, M. (2015). Statistical learning with sparsity: The lasso and generalizations. CRC Press. hastie.su.domains
5. Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., & Salakhutdinov, R. (2014). Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56), 1929-1958. jmlr.org
6. scikit-learn developers. (n.d.). Ridge regression and classification; Lasso. In Linear models, scikit-learn user guide. scikit-learn.org
7. Goodfellow, I., Bengio, Y., & Courville, A. (2016). Regularization for deep learning. In Deep learning (ch. 7). MIT Press. deeplearningbook.org

We keep saying "use a validation set." This lesson makes that precise. To estimate generalization honestly and to tune hyperparameters like lambda, we must evaluate on data the model did not train on, and we must be disciplined about how that data is used.

The big picture

Here is the trap that catches almost everyone once. You try twenty model configurations, evaluate each on the same held-out set, and report the best one's score. That number is not an honest estimate of future performance, and the reason is not subtle: you ran twenty lotteries and reported the winner. Even if all twenty models were genuinely identical in quality, the best of twenty noisy measurements is systematically above the truth. The more configurations you try, the more optimistic the winner's score becomes, and the effect can easily be several percentage points.

This is the same selection bias that made empirical risk minimization untrustworthy in Lesson 3, reappearing one level up. There it was the model class being searched; here it is the hyperparameter grid. The remedy has the same shape too: keep a portion of the data completely outside the search, so that when the searching is finished you have a measurement that no decision ever touched.

Key idea: data you used to make a choice cannot also measure that choice. Every selection step needs its own untouched holdout downstream of it.

Three roles for data

Data is split by purpose, not just convenience:

• The training set fits the model's parameters (weights).
• The validation set tunes hyperparameters (like lambda or model complexity) and is used to pick between models.
• The test set is touched exactly once, at the very end, to report an unbiased estimate of real-world performance.

The rule is strict: once you make any decision based on the test set, it is no longer an honest test. Guard it. A common allocation is 60/20/20 or 70/15/15, but the right split depends on scale rather than tradition. With a million rows, 1 percent is ten thousand examples, which is plenty for a stable estimate, so 98/1/1 is perfectly reasonable. With three hundred rows, no fixed split is comfortable and cross-validation becomes mandatory rather than optional. The question to ask is not "what fraction" but "how many examples do I need for the standard error of my metric to be small enough to distinguish the models I care about", which for a proportion near 0.5 means roughly 0.5 / sqrt(m).

k-fold cross-validation

A single validation split wastes data and can be lucky or unlucky. k-fold cross-validation uses the data far more efficiently. Split the training data into k equal folds (k = 5 or 10 is typical). Then, for each fold in turn, train on the other k - 1 folds and validate on the held-out fold. Average the k validation scores to get a stable estimate.

k-fold cross-validation (for one hyperparameter setting):
    split data into k folds
    for i = 1 to k:
        train on all folds except fold i
        score_i = evaluate on fold i
    cv_score = average(score_1, ..., score_k)

Worked example. With 5-fold cross-validation on 100 examples, each fold has 20. You train five models, each on 80 examples and validated on the remaining 20, so every example is used for validation exactly once and for training four times.

To tune lambda, run this whole procedure for each candidate lambda and choose the value with the best average score. This is more reliable than a single split, at the cost of k times the computation.

Choosing k, and the variants that matter

The choice of k is itself a bias-variance tradeoff, but about the estimate rather than the model. Small k means each model trains on a smaller fraction of the data (with k = 2, only half), so the estimated performance is pessimistically biased relative to a model trained on everything. Large k means each model trains on nearly all the data, reducing that bias, but the k training sets overlap heavily, so the k scores are highly correlated and their average is not as stable as its count suggests. The extreme case, leave-one-out cross-validation with k = n, is nearly unbiased and often has high variance, besides costing n model fits. Empirical work has long favored k = 5 or k = 10 as the practical sweet spot (Kohavi, 1995), and that recommendation has held up.

• Stratified k-fold preserves the class proportions in every fold. Use it by default for classification; with a 5 percent positive class and plain random folds you can easily draw a fold with almost no positives, making the score meaningless.
• Repeated k-fold reruns the whole procedure with different random partitions and averages, which shrinks the variance caused by one unlucky partition at a linear cost in compute.
• Group k-fold keeps all rows sharing an identifier (the same patient, the same user, the same document) inside a single fold. If the same patient appears in both training and validation, you are measuring memorization of that patient, not generalization to new ones.
• Time-series split always trains on the past and validates on the future, growing the training window forward. Random folds on time-ordered data let the model see the future while predicting the past, which is leakage in its purest form.

Nested cross-validation: measuring after you have chosen

Now return to the trap from the opening. If you run k-fold cross-validation over a grid of hyperparameters and report the best cross-validated score, that number is optimistically biased, because the selection used exactly the folds you are reporting. The fix is nested cross-validation: an inner loop that selects hyperparameters, and an outer loop that measures the whole selection procedure on data the inner loop never saw.

for each outer fold i in 1..K_outer:
    hold out outer fold i
    run k-fold CV on the remaining data over the hyperparameter grid   # INNER loop
    pick the best hyperparameters from the inner CV
    refit on all of the remaining data with those hyperparameters
    score once on outer fold i                                          # untouched
report the average of the K_outer scores

Worked example. With a 5-fold outer loop, a 5-fold inner loop, and a grid of 12 hyperparameter settings, the total number of model fits is 5 * (5 * 12 + 1) = 305: sixty inner fits plus one refit per outer fold. That is the price of an unbiased estimate of the tuned procedure. Note what the outer average estimates. It does not estimate the performance of one specific hyperparameter setting; it estimates the performance of the entire pipeline including its tuning step, which is exactly the thing you would deploy. Different outer folds may well select different hyperparameters, and that is not a bug.

Data leakage: the silent killer

Data leakage is when information from outside the training set sneaks into training, producing scores that look great but collapse in deployment. Classic mistakes include standardizing features using statistics computed over the whole dataset (the mean must come from training data only), selecting features while peeking at test labels, or having duplicate rows split across train and test.

Leakage is worth cataloguing, because each variety looks innocent on its own:

• Preprocessing leakage. Fitting a scaler, imputer, or PCA on the full dataset before splitting. The transformation now encodes information from the validation rows.
• Feature-selection leakage. Ranking features by their correlation with the target on all the data, then cross-validating only the model. This is one of the most damaging and most common errors, and with many noise features it can manufacture apparently excellent accuracy out of nothing.
• Target leakage. Including a feature that is a consequence of the outcome rather than a predictor of it. A column recording "date discharged from ICU" predicts survival superbly and will not exist at prediction time.
• Duplicate leakage. Near-identical rows split across train and test, common in scraped data and in datasets with repeated measurements on the same subject.
• Temporal leakage. Training on data recorded after the prediction moment, including features computed from future aggregates.

The structural cure is to express the entire workflow as a pipeline object, so that scaling, imputation, feature selection, and the estimator are all refitted together inside every training fold. In scikit-learn, wrapping the steps in a Pipeline and passing the whole thing to cross_val_score does this automatically; doing the steps by hand before the split is exactly how leakage gets in.

The discipline that prevents leakage is simple to state: any quantity learned from data, scaling factors, selected features, chosen hyperparameters, must be derived using only the training portion of each split. Combined with a locked-away test set, cross-validation then gives an estimate you can actually trust, which is the whole point of controlling overfitting.

Where people get stuck

• "Cross-validation prevents overfitting." It measures generalization; it does not change the model. What prevents overfitting is a simpler model, regularization, or more data. Cross-validation tells you whether the prevention worked.
• "I got 94 percent in cross-validation, so I will get 94 percent in production." Only if production data is drawn like your data. Cross-validation cannot see distribution shift, and it cannot see leakage that is baked into how the dataset was assembled.
• "Leave-one-out is the most accurate, so use it." It has the smallest bias but often high variance and the highest cost. For most problems 5-fold or 10-fold is both cheaper and more stable.
• "One number is enough." Report the standard deviation across folds alongside the mean. A model averaging 0.85 with a fold spread of 0.02 is a different proposition from one averaging 0.85 with a spread of 0.15.
• "I peeked at the test set only once." Once is enough to contaminate it if you then changed anything. If you must look again, treat it as a validation set and obtain fresh test data.

Recap

• Training data fits parameters, validation data selects hyperparameters and models, and the test set is opened once at the end.
• k-fold cross-validation rotates the validation role through k folds and averages, using the data far more efficiently than a single split.
• k = 5 or 10 balances the bias and variance of the estimate; leave-one-out is nearly unbiased but expensive and often high-variance.
• Use stratified folds for classification, group folds for repeated subjects, and forward-chaining splits for time series.
• Nested cross-validation is required for an unbiased estimate of a procedure that includes hyperparameter tuning.
• Leakage takes many forms; wrapping every learned transformation in a pipeline refitted inside each fold is the structural defence.

A model you cannot honestly evaluate is a model you cannot responsibly deploy. The habits in this lesson, especially the pipeline and the sealed test set, are what separate a result that survives contact with reality from one that does not.

Sources

1. Stone, M. (1974). Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society: Series B, 36(2), 111-147. find source ↗
2. Kohavi, R. (1995). A study of cross-validation and bootstrap for accuracy estimation and model selection. Proceedings of the 14th International Joint Conference on Artificial Intelligence, 1137-1143. ai.stanford.edu
3. Arlot, S., & Celisse, A. (2010). A survey of cross-validation procedures for model selection. Statistics Surveys, 4, 40-79. arxiv.org
4. Hastie, T., Tibshirani, R., & Friedman, J. (2009). Cross-validation. In The elements of statistical learning (2nd ed., ch. 7.10). Springer. hastie.su.domains
5. Raschka, S. (2018). Model evaluation, model selection, and algorithm selection in machine learning. arXiv. arxiv.org
6. scikit-learn developers. (n.d.). Cross-validation: Evaluating estimator performance. scikit-learn user guide. scikit-learn.org
7. scikit-learn developers. (n.d.). Common pitfalls and recommended practices. scikit-learn user guide. scikit-learn.org

A decision tree predicts by asking a sequence of simple yes/no questions about the features, following the answers down a branching structure until it reaches a leaf that gives the prediction. Trees are prized for being human-readable: the path to a decision is a plain chain of rules, and they need no feature scaling.

The big picture

You already know how to run a decision tree, because you have played twenty questions. Each question narrows the possibilities, and a good question is one that splits the remaining candidates into groups that are as different from each other as possible. Asking "is it alive?" early is smart; asking "is it a badger?" early is not, because it almost always yields "no" and eliminates one option out of thousands. The entire training algorithm for a decision tree is a formalization of "ask the most informative question first".

What makes trees genuinely different from everything in Modules 2 and 3 is that they are non-parametric and local. A linear model commits in advance to a fixed number of coefficients and lets every training point vote on all of them, so one distant outlier tugs the whole surface. A tree grows its structure from the data, and each leaf's prediction depends only on the training points that landed in that leaf. Two consequences follow immediately: trees need no feature scaling, since a threshold on a feature is unaffected by its units, and trees capture interactions automatically, since a split on one feature happens inside a region already defined by splits on others.

Key idea: a tree is a nested set of yes/no questions chosen greedily to make the resulting groups as pure as possible. Everything technical in this lesson is a precise version of "as pure as possible".

Anatomy and how splits are chosen

Each internal node tests one feature against a threshold ("is age < 30?"), sending examples left or right; each leaf holds a prediction (a class for classification, an average for regression). Training builds the tree greedily, top down: at each node it searches over features and thresholds for the split that best separates the classes, then recurses on each side.

"Best" is measured by how pure the resulting groups are, meaning how dominated each is by a single class. Two standard purity measures for a node are:

Gini impurity = 1 - sum over classes of p_c^2
Entropy       = - sum over classes of p_c * log2(p_c)

where p_c is the fraction of the node belonging to class c. Both are 0 for a perfectly pure node (all one class) and largest when classes are evenly mixed.

The tree picks the split that most reduces impurity, the information gain. Worked example. A node with 8 positives and 2 negatives has p = 0.8 and 0.2, so its Gini impurity is 1 - (0.8^2 + 0.2^2) = 1 - (0.64 + 0.04) = 0.32. A pure node of all positives would have Gini 1 - 1^2 = 0.

The gain from a split must account for how many examples go each way, so it is a weighted comparison:

Gain = Impurity(parent) - [ (n_left / n) * Impurity(left) + (n_right / n) * Impurity(right) ]

Without the weights, a split that isolates a single pure example would look wonderful. With them, purifying two examples out of a hundred barely moves the number. Gini and entropy almost always choose the same splits in practice; entropy is slightly more expensive because of the logarithm and slightly more inclined to produce balanced splits. Gini is scikit-learn's default for that reason.

Worked example: choosing a split by information gain

Fourteen customers, of whom 9 churned (class C) and 5 stayed (class S). We consider splitting on "contract = monthly".

Parent: 9 C, 5 S   (n = 14)
Split "monthly?":
    yes  -> 6 examples:  6 C, 0 S
    no   -> 8 examples:  3 C, 5 S

• Step 1, parent entropy. p_C = 9/14 = 0.643, p_S = 5/14 = 0.357. H = -(0.643 * log2(0.643) + 0.357 * log2(0.357)) = -(0.643 * -0.637 + 0.357 * -1.485) = 0.410 + 0.530 = 0.940 bits.
• Step 2, left child. All 6 are class C, so p_C = 1 and H_left = 0 bits. A pure node carries no uncertainty.
• Step 3, right child. p_C = 3/8 = 0.375, p_S = 5/8 = 0.625. H = -(0.375 * -1.415 + 0.625 * -0.678) = 0.531 + 0.424 = 0.954 bits.
• Step 4, weighted child entropy. (6/14) * 0 + (8/14) * 0.954 = 0.429 * 0 + 0.571 * 0.954 = 0.545 bits.
• Step 5, information gain. 0.940 - 0.545 = 0.395 bits.
• Step 6, the same split under Gini. Parent Gini = 1 - (0.643^2 + 0.357^2) = 1 - (0.413 + 0.127) = 0.459. Left = 0. Right = 1 - (0.375^2 + 0.625^2) = 1 - (0.141 + 0.391) = 0.469. Weighted = 0.571 * 0.469 = 0.268. Gain = 0.459 - 0.268 = 0.191.

What we just did: we scored one candidate split two ways. The units differ (bits versus a probability-scale quantity) but the ranking logic is identical, and both say the split buys a substantial reduction in disorder. The training algorithm computes this number for every feature and every candidate threshold, keeps the maximum, and then recurses into each child. For a numeric feature with n distinct values there are n - 1 candidate thresholds, usually taken at the midpoints between consecutive sorted values.

Key idea: impurity measures uncertainty inside a node; information gain measures how much of it a proposed question removes, weighted by how many examples that question actually affects.

Greedy, not optimal

The tree chooses the best split at each node without any lookahead, which makes training fast but means the result is not the best possible tree. Finding the smallest tree consistent with a dataset is NP-hard, so every practical algorithm is greedy. The visible consequence is the XOR problem: with two binary features where the label is 1 exactly when the features differ, neither feature alone reduces impurity at all, so a greedy criterion sees no reason to split on either. A tree of depth 2 represents the function perfectly, but a single-step-lookahead search may never find it. This is a genuine limitation, and it is one motivation for the randomized ensembles of the next lesson, which explore different split sequences.

Trees for regression

Nothing structural changes when the target is continuous. Each leaf predicts the mean of its training targets, and the split criterion becomes reduction in sum of squared deviations rather than reduction in Gini or entropy:

Impurity(node) = sum over i in node of ( y_i - mean(y in node) )^2
Choose the split maximizing the weighted reduction in this quantity.

Because each leaf outputs a constant, a regression tree produces a step function. It cannot extrapolate at all: feed it an input beyond the range it was trained on and it returns the value of the nearest boundary leaf, forever flat. For trending time series that is a serious drawback and a reason to prefer a linear model or a hybrid.

Splits carve the feature space into boxes

Because each split is a threshold on one feature, a decision tree partitions feature space into axis-aligned rectangles, one per leaf, and predicts a constant within each. This gives trees a distinctive staircase-shaped boundary and lets them capture nonlinear patterns and feature interactions that a single linear model cannot.

The same property is also a weakness worth naming. A boundary that is genuinely diagonal, such as "approve the loan when income exceeds twice the debt", is a single line that logistic regression captures with two coefficients. A tree must approximate it with a staircase, and getting a smooth diagonal to within a small error can take dozens of splits, each one estimated from fewer examples than the last. If you suspect a linear combination of features matters, either supply that combination as an engineered feature or use a model that can form it directly.

The overfitting problem

A tree grown without limit will keep splitting until every leaf is pure, often ending with one training example per leaf. Such a tree memorizes the training set: near-zero training error but high variance and poor generalization, a textbook case of overfitting. The cures constrain the tree's growth:

• Limit the maximum depth or require a minimum number of samples to split a node.
• Prune the tree after growing it, cutting back branches that do not improve validation performance.

These controls trade a little bias for much less variance. The principled version of pruning is cost-complexity pruning, introduced with CART: grow the tree fully, then for a penalty alpha find the subtree minimizing

R_alpha(T) = training_error(T) + alpha * (number of leaves in T)

As alpha increases from 0, this generates a nested sequence of ever-smaller subtrees, and alpha is chosen by cross-validation exactly as lambda was in Lesson 8. The idea is the same one as regularization: pay for complexity, and let the data decide how much complexity it can support. In scikit-learn this is exposed as the ccp_alpha parameter.

Reading a tree honestly

Trees report a feature importance for each variable, computed as the total impurity reduction contributed by all splits on that feature, weighted by the examples reaching them. It is useful and it is biased in a specific way: impurity-based importance systematically favors continuous and high-cardinality features, because such features offer many candidate thresholds and therefore many chances to reduce impurity by luck. A customer ID column can look important. The robust alternative is permutation importance, which shuffles one feature's values on held-out data and measures how much performance degrades; it is model-agnostic and computed where it counts, on data the tree did not train on.

Trees also handle several practical annoyances gracefully. No feature scaling is needed. Monotone transformations of a feature (log, square root) do not change the tree at all, since they preserve the ordering that thresholds depend on. Categorical features can be split on subsets of levels, and several implementations handle missing values natively by learning a default direction at each node. These conveniences are a large part of why tree ensembles dominate tabular problems in practice.

Even so, a single tuned tree is often mediocre and unstable; small changes in the data can reshape it entirely, because one different split near the root changes every subtree below it. That instability is precisely the weakness that ensembles, in the next lesson, are designed to fix.

Where people get stuck

• "Trees are interpretable, so a tree is always the transparent choice." A depth-3 tree is a readable set of rules. A depth-25 tree with 4,000 leaves is not interpretable in any useful sense, and its rules are unstable under resampling.
• "Feature importance tells me what causes the outcome." It tells you which columns this particular fitted tree found useful for splitting, and impurity-based importance is biased toward high-cardinality features. Use permutation importance on held-out data, and do not read causation into either.
• "I should scale my features first." Harmless but pointless. Thresholds are invariant to any monotone rescaling.
• "Entropy is better than Gini." They agree on the chosen split the overwhelming majority of the time. Spend the tuning budget on depth and pruning instead.
• "A regression tree can extrapolate a trend." It cannot. Beyond the training range it returns a constant, because every leaf is a constant.

Recap

• A decision tree routes an example through threshold tests to a leaf, which supplies the prediction.
• Splits are chosen greedily to maximize weighted impurity reduction, measured by Gini or entropy for classification and by squared-error reduction for regression.
• Information gain is parent impurity minus the example-weighted average impurity of the children.
• Greedy growth is fast but not optimal; XOR-style patterns can defeat single-step lookahead.
• Trees partition the space into axis-aligned boxes, which handles interactions well and diagonal boundaries badly.
• Unpruned trees overfit; depth limits, minimum-samples rules, and cost-complexity pruning with alpha chosen by cross-validation control it.

A single tree is best treated as a building block and a communication device rather than a final model. Its variance is the problem that the next lesson solves by growing many trees and averaging them.

Sources

1. Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and regression trees. Wadsworth. find source ↗
2. Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81-106. link.springer.com
3. Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379-423. people.math.harvard.edu
4. Hastie, T., Tibshirani, R., & Friedman, J. (2009). Tree-based methods. In The elements of statistical learning (2nd ed., ch. 9.2). Springer. hastie.su.domains
5. James, G., Witten, D., Hastie, T., & Tibshirani, R. (2021). Tree-based methods. In An introduction to statistical learning (2nd ed., ch. 8). Springer. statlearning.com
6. scikit-learn developers. (n.d.). Decision trees. scikit-learn user guide. scikit-learn.org
7. scikit-learn developers. (n.d.). Permutation feature importance. scikit-learn user guide. scikit-learn.org

A single decision tree is unstable: change a few training points and it can look completely different. Ensemble methods turn this weakness into a strength by combining many models whose errors partly cancel. The headline example is the random forest, one of the most reliable off-the-shelf classifiers.

The big picture

Ask one expert to estimate the number of jellybeans in a jar and you get a guess with an unknown error. Ask five hundred people and average the answers, and the average is often startlingly close, because individual overestimates and underestimates cancel. The catch, and it is the whole subject of this lesson, is that cancellation only works if the errors are independent. If everyone in the room first heard the same person say "about a thousand", the average will be anchored near a thousand no matter how many people you poll. A crowd of correlated guessers is barely better than one guesser.

That is exactly the situation with bagged decision trees. Trees grown on resampled versions of the same data are similar to each other, because they will all discover the same one or two dominant features and split on them near the root. The genius of the random forest is a second injection of randomness whose only purpose is to break that correlation. Understanding why decorrelation is worth more than accuracy per tree is the point of this lesson.

Key idea: averaging removes the part of the error that differs between models and leaves the part they share. Ensembles are engineered to maximize the first part and minimize the second.

Bagging: averaging away variance

The core idea is bagging (bootstrap aggregating). From the training set of n examples, draw many bootstrap samples, each a random sample of n examples drawn with replacement (so some examples repeat and some are omitted). Train a separate tree on each bootstrap sample, then aggregate: for classification, take a majority vote across trees; for regression, average their predictions.

Why does averaging help? Individual deep trees have low bias but high variance. Averaging many roughly independent high-variance predictions keeps the low bias while sharply cutting the variance, the same reason an average of many noisy measurements is more precise than one. The trees must be somewhat decorrelated for this to work well, which motivates the forest's second trick.

The mathematics of that last sentence is worth writing down, because it is the single most illuminating formula in ensemble learning. Suppose you average B predictors, each with variance sigma^2, and each pair correlated with coefficient rho. The variance of the average is

Var( average of B predictors ) = rho * sigma^2 + ( (1 - rho) / B ) * sigma^2

Read the two terms separately. The second term vanishes as B grows: that is the part averaging can remove, and it is why more trees never hurt. The first term does not depend on B at all: it is a floor set by how correlated the trees are. Adding the ten-thousandth tree cannot help you get below rho * sigma^2. Therefore the only way to improve a large ensemble is to lower rho, and lowering rho is precisely what feature subsampling does.

Worked example. Take sigma^2 = 1. With B = 100 fully independent trees (rho = 0) the variance of the average is 0 + 1/100 = 0.010, a hundredfold reduction. With rho = 0.6, typical of bagged trees on data with a couple of dominant features, it is 0.6 + 0.4/100 = 0.604, barely better than a single tree's 1.0. Now drop the correlation to rho = 0.2 through feature subsampling and it becomes 0.2 + 0.8/100 = 0.208, a threefold improvement over the rho = 0.6 case, purchased entirely by decorrelation rather than by better trees. Note the trade: restricting each split to a random subset of features makes each individual tree worse (higher sigma^2), and the ensemble still wins because rho falls faster than sigma^2 rises.

The bootstrap, and the free validation set it gives you

A bootstrap sample of size n drawn with replacement leaves some examples out. The probability a particular example is missed on one draw is (1 - 1/n), so the probability it is missed by all n draws is (1 - 1/n)^n, which converges to 1/e = 0.368 as n grows. So each tree trains on roughly 63.2 percent of the distinct examples and never sees the other 36.8 percent, called its out-of-bag (OOB) sample.

This is a gift. For each training example, collect the trees that did not see it, average their predictions, and compare to the truth. The resulting OOB error is a nearly unbiased estimate of generalization error obtained without any separate validation split and without refitting anything, which is especially valuable on small datasets. It is not a substitute for a sealed test set when you are tuning aggressively, but as a free running estimate it is excellent.

The extra randomness in a random forest

A random forest is bagging with decision trees plus one more source of randomness: at each split, the tree may only choose from a random subset of the features rather than all of them. This feature subsampling stops every tree from leaning on the same one or two dominant features, so the trees disagree more and their average generalizes better. Two knobs matter most: the number of trees (more is better and never hurts accuracy, only compute) and the number of features considered per split.

Source of randomness	What it does
Bootstrap sampling of rows	Each tree sees a different resampled dataset
Random feature subset per split	Decorrelates trees so averaging helps more

The conventional defaults for the number of features tried per split are sqrt(d) for classification and d/3 for regression, where d is the total number of features, and both are worth treating as starting points rather than laws. Note also that the individual trees in a random forest are usually grown deep and left unpruned. That is deliberate: deep trees have low bias and high variance, and variance is exactly what the averaging removes. Pruning each tree first would raise bias that the ensemble cannot undo.

Random forests are accurate, robust to outliers, need little tuning, and even estimate feature importance. Their main costs are reduced interpretability (a forest of hundreds of trees is not a simple rule) and more computation than a single tree.

Bagging versus boosting

Bagging builds many trees independently and in parallel and averages them, chiefly to reduce variance. Boosting takes a different route: it builds trees sequentially, each new tree focusing on the examples the previous ones got wrong, chiefly to reduce bias. Gradient-boosted trees often edge out random forests in raw accuracy but are more sensitive to their settings and easier to overfit. Both are ensembles; they differ in whether the members are grown together and averaged (bagging) or grown one after another to correct mistakes (boosting).

The boosting family has a clear lineage. AdaBoost (Freund & Schapire, 1997) reweights the training examples after each round, raising the weight of those the current ensemble misclassifies so the next weak learner concentrates on them. Gradient boosting (Friedman, 2001) reframes this as gradient descent in function space: each new tree is fitted to the negative gradient of the loss with respect to the current predictions, which for squared error is simply the residuals. That reframing is what freed boosting from any single loss function and made it applicable to regression, classification, and ranking alike.

Gradient boosting, in outline:
    F_0(x) = a constant (the mean, for squared error)
    for m = 1..M:
        r_i = -dLoss( y_i, F_(m-1)(x_i) ) / dF        # pseudo-residuals
        fit a shallow tree h_m to the pairs (x_i, r_i)
        F_m(x) = F_(m-1)(x) + eta * h_m(x)            # eta is the learning rate

Three knobs matter and they interact. The learning rate eta (often 0.01 to 0.1) shrinks each tree's contribution; smaller eta needs more trees but generalizes better. The number of trees M is chosen by early stopping on a validation set, because unlike a random forest, a boosted model will overfit if you add trees indefinitely. And tree depth is kept small, typically 3 to 8, since each tree only needs to correct a residual, not model the whole function. Modern implementations, notably XGBoost (Chen & Guestrin, 2016) and LightGBM, add explicit regularization on leaf weights, second-order gradient information, histogram-based split finding, and native missing-value handling.

Aspect	Bagging / random forest	Boosting
How members are built	Independently, in parallel	Sequentially, each on the last one's errors
Base learner	Deep, unpruned, low bias	Shallow stumps or small trees, high bias
Primarily reduces	Variance	Bias
More members	Never hurts accuracy	Can overfit; use early stopping
Tuning sensitivity	Low	Higher (eta, depth, M, subsampling)
Free error estimate	Yes, out-of-bag	No, needs a validation set

A third pattern, stacking, trains several different model types and then trains a simple meta-model on their out-of-fold predictions to learn how to combine them. It often squeezes out a final increment of accuracy at a substantial cost in complexity and in the discipline required to avoid leakage in the meta-features.

Where tree ensembles stand today

Despite a decade of deep learning progress, gradient-boosted tree ensembles remain the strongest general default for medium-sized tabular data. A careful benchmark across dozens of datasets found tree-based models still outperforming tuned neural architectures on typical tabular problems, and attributed the gap to specific properties of tabular data: irregular target functions that favor axis-aligned partitions, many uninformative features, and a lack of the rotational invariance that neural networks assume (Grinsztajn et al., 2022). Be careful about how far you take this. It is a claim about tabular data at moderate scale, not about images, audio, or text, where deep networks are decisively better, and not a claim that no neural approach can ever win on a given table.

Where people get stuck

• "More trees can overfit a random forest." They cannot, in the sense that test error converges rather than degrading as B grows; the second variance term simply shrinks toward zero. More trees cost compute. In boosting, by contrast, more trees genuinely can overfit.
• "Bagging and boosting are basically the same." They target different terms. Bagging averages low-bias, high-variance models to cut variance. Boosting adds high-bias, low-variance models sequentially to cut bias. That is why the base learners are deep in one and shallow in the other.
• "Out-of-bag error means I do not need a test set." OOB is an excellent running estimate, but once you tune hyperparameters against it, it inherits the selection bias of Lesson 9. Keep a sealed test set.
• "Random forests handle correlated features fine." Prediction is fine; importance is not. Correlated features split their importance between them, so each can look unimportant while the group matters a great deal.
• "Ensembles are black boxes, so nothing can be said." Partial dependence plots, permutation importance, and SHAP values give real, if partial, insight into what an ensemble has learned.

Recap

• Bagging trains models on bootstrap resamples and aggregates them, reducing variance while preserving low bias.
• The variance of an average is rho*sigma^2 + (1-rho)/B * sigma^2, so correlation between members sets a floor no amount of averaging can beat.
• A random forest adds per-split feature subsampling specifically to lower rho, accepting slightly worse individual trees for a much better average.
• Each bootstrap sample omits about 36.8 percent of examples, giving a free out-of-bag estimate of generalization error.
• Boosting builds shallow trees sequentially on the gradient of the loss, reducing bias, and needs a learning rate, a tree count set by early stopping, and shallow depth.
• Gradient-boosted trees remain the strongest default on medium-sized tabular data, while deep networks dominate images, audio, and text.

If you are given a table and a deadline, fit a random forest first for a robust baseline that needs almost no tuning, then try gradient boosting when you have the time to tune it properly. The difference between them is usually smaller than the difference made by better features.

Sources

1. Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2), 123-140. link.springer.com
2. Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5-32. link.springer.com
3. Breiman, L. (2001). Random forests [Technical report]. University of California, Berkeley. stat.berkeley.edu
4. Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119-139. rob.schapire.net
5. Friedman, J. H. (2001). Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5), 1189-1232. find source ↗
6. Chen, T., & Guestrin, C. (2016). XGBoost: A scalable tree boosting system. arXiv. arxiv.org
7. Grinsztajn, L., Oyallon, E., & Varoquaux, G. (2022). Why do tree-based models still outperform deep learning on tabular data? arXiv. arxiv.org

The support vector machine (SVM) is a powerful classifier built on an elegant geometric idea: among all the hyperplanes that separate two classes, prefer the one that sits as far as possible from the nearest points of either class. That distance is the margin, and maximizing it tends to give boundaries that generalize well.

The big picture

Draw two clouds of points that a straight line can separate, then ask a room of people to draw the line. You will get many different lines, all of them achieving zero training error. Logistic regression will pick one of them (the maximum-likelihood one, which depends on every point including the far-away ones). The SVM asks a different and rather beautiful question: of all the lines that work, which one is most defensible? Its answer is the line that stays as far as possible from the nearest example on either side, on the reasoning that a boundary with a wide buffer will survive small perturbations in the data, and a boundary that skims past a training point will not.

This is a substantive change in the objective, not a cosmetic one. It makes the solution depend on only a handful of points, it gives a crisp geometric quantity to maximize, and it produces an optimization problem whose structure happens to admit the kernel trick. Three consequences from one idea.

Key idea: among all boundaries that separate the classes, the SVM chooses the one maximizing the distance to the nearest point. Robustness, not likelihood, is the criterion.

The maximum-margin hyperplane

Logistic regression finds some separating line; an SVM finds the widest street. Picture the boundary as a road drawn between the two classes: the SVM makes the road as wide as it can, and the boundary runs down its center. The examples that touch the edges of the street, the closest points that "hold it in place", are the support vectors. Remarkably, only these few points determine the boundary; move any other point (without crossing the street) and nothing changes. A wide margin gives a buffer against noise, which is why max-margin classifiers are robust.

Turning "widest street" into an optimization problem

Fix the scale so that the closest points on each side satisfy w . x + b = +1 and w . x + b = -1. This is a normalization, not an assumption: any separating hyperplane can be rescaled to make it true. Under that convention the distance between the two margin lines works out to

margin width = 2 / ||w||           where ||w|| = sqrt( sum_j w_j^2 )
Maximizing 2 / ||w||   is the same as   minimizing (1/2) * ||w||^2
So the hard-margin SVM solves:
    minimize   (1/2) * ||w||^2
    subject to y_i * ( w . x_i + b ) >= 1   for every training example i

Stare at that for a moment, because it is a small surprise. Maximizing a margin turns into minimizing the norm of the weight vector, which is precisely the L2 penalty from Lesson 8. The max-margin principle and ridge-style regularization are the same mathematical impulse wearing different clothes: keep the weights small, keep the function from getting too steep, keep the decision robust.

Worked example. One feature, two points: x = 2 labeled -1 and x = 6 labeled +1. A boundary at x = 4 gives w * 4 + b = 0. Impose the margin conditions w * 6 + b = +1 and w * 2 + b = -1. Subtracting, 4w = 2 so w = 0.5, and then b = 1 - 0.5 * 6 = -2. The margin width is 2 / |0.5| = 4, which is exactly the gap between the two points, as it must be for the boundary sitting halfway. Now add a third point at x = 10 labeled +1. It satisfies 0.5 * 10 - 2 = 3, comfortably beyond the margin, so it is not a support vector and the solution does not change at all. Move it to x = 100 and still nothing changes. That insensitivity to distant points is the SVM's signature, and it contrasts sharply with logistic regression, whose likelihood keeps responding to every point.

The soft margin for messy data

Real data is rarely perfectly separable; a few points sit on the wrong side or inside the street. A soft-margin SVM allows some violations, penalizing each by an amount controlled by a hyperparameter usually called C. Large C insists on few violations (a narrow, hard margin that risks overfitting); small C tolerates more violations for a wider margin (more regularization, more bias). Tuning C is the SVM's version of the bias-variance dial, chosen by cross-validation.

Written out, the soft-margin problem introduces a slack variable xi_i measuring how far example i intrudes into or across the margin:

minimize   (1/2)*||w||^2 + C * sum_i xi_i
subject to y_i * ( w . x_i + b ) >= 1 - xi_i,   xi_i >= 0
Equivalently, with lambda = 1 / (2*C*n), an unconstrained problem:
    minimize  (1/n) * sum_i max(0, 1 - y_i*(w . x_i + b))  +  lambda * ||w||^2
              _____________ hinge loss _______________/     _ L2 penalty _/

That second form connects the whole lesson to Lesson 3 and Lesson 8: a soft-margin SVM is exactly hinge loss plus an L2 penalty, fitted by any convex optimizer. Note the direction of the C parameter, which trips people constantly. C multiplies the error term, so it is inversely related to regularization strength: large C means "violations are expensive", a narrow hard margin, low bias and high variance; small C means "violations are cheap", a wide margin, more regularization and more bias. In scikit-learn C = 1.0 is the default and worth sweeping over several orders of magnitude.

The kernel trick

So far the boundary is linear. The SVM becomes far more powerful through the kernel trick: a kernel function computes similarities between points as if they had been mapped into a much higher-dimensional space, without ever building that space explicitly. A linear boundary in the high-dimensional space corresponds to a curved boundary in the original one, so an SVM with, say, a radial basis function (RBF) kernel can carve out flexible, nonlinear regions.

The trick works because of a structural fact about the optimization. Solving the SVM through its dual formulation gives an objective in which the training inputs appear only inside dot products x_i . x_j, and the prediction rule likewise depends only on dot products between the new point and the support vectors:

Dual objective:  maximize  sum_i a_i - (1/2) * sum_i sum_j a_i a_j y_i y_j ( x_i . x_j )
                 subject to 0 <= a_i <= C  and  sum_i a_i y_i = 0
Prediction:      f(x) = sign( sum over support vectors of a_i y_i ( x_i . x ) + b )
Kernel substitution: replace every ( x_i . x_j ) with K(x_i, x_j)

Since the raw coordinates never appear on their own, you may replace each dot product with a kernel function K that computes the dot product in some transformed space without ever constructing that space. Only the a_i that are nonzero matter, and those correspond exactly to the support vectors, which is why the model is sparse in the training data. The common kernels:

• Linear: K(u, v) = u . v. The original model, best when d is large relative to n, as in text classification.
• Polynomial: K(u, v) = (gamma * (u . v) + r)^p. Represents feature interactions up to degree p explicitly.
• RBF (Gaussian): K(u, v) = exp( -gamma * ||u - v||^2 ). The default workhorse, corresponding to an infinite-dimensional feature space. Small gamma gives a wide, smooth influence per point; large gamma makes each support vector's influence local and the boundary wiggly, which overfits.

C and gamma interact strongly, so tune them jointly on a logarithmic grid, for example C in {0.1, 1, 10, 100, 1000} crossed with gamma in {1e-4, 1e-3, 1e-2, 1e-1, 1}, using cross-validation. And scale your features first: the RBF kernel is a function of Euclidean distance, so a feature measured in thousands will swamp one measured in units and gamma will be meaningless.

Practical notes

The standard SVM is inherently binary; multiclass is handled by fitting one-versus-rest or one-versus-one collections of binary machines. Training cost scales roughly between n^2 and n^3 in the number of examples for kernel SVMs, which puts a practical ceiling somewhere in the tens of thousands of rows; beyond that, a linear SVM trained by stochastic gradient descent, or a tree ensemble, is the pragmatic choice. SVMs also extend to regression as support vector regression, which fits a tube of width epsilon around the data and penalizes only points outside it. One genuine limitation: an SVM outputs a decision score, not a probability, and converting it requires a post-hoc calibration step such as Platt scaling (see Lesson 6).

This lets one clean algorithm handle problems where classes wrap around each other. The tradeoffs: SVMs are memory- and compute-heavy on very large datasets, and the kernel and its parameters need tuning, but on medium-sized problems with clear margins they remain a strong, principled choice. Historically they were the dominant classifier from the late 1990s until deep networks overtook them on perceptual tasks around 2012; today they are a specialist tool that still shines on small-to-medium problems with many features and few samples, such as text and some biological data.

Where people get stuck

• "Large C means more regularization." The opposite. C multiplies the error term, so large C punishes violations harder and gives a narrower, less regularized margin. Small C regularizes more.
• "The kernel maps the data, so I should look at the transformed features." There are none to look at. The whole point is that only inner products are ever computed; for the RBF kernel the implied space is infinite-dimensional.
• "An SVM gives me the probability of the class." It gives a signed distance from the boundary. Probabilities require Platt scaling or isotonic regression fitted on held-out data.
• "Scaling is optional, like with trees." For kernel SVMs it is mandatory. Distances drive the kernel, and unscaled features destroy them.
• "More support vectors means a better model." Usually the reverse: a large fraction of points serving as support vectors signals a small C, a badly chosen gamma, or heavy class overlap, and it also makes prediction slower.

Recap

• An SVM picks the separating hyperplane with the largest margin, which is the most robust of the boundaries that work.
• With the margin lines normalized to +1 and -1, the width is 2 / ||w||, so maximizing margin means minimizing (1/2)*||w||^2, an L2 penalty in disguise.
• Only the support vectors, the points on or inside the margin, determine the solution; distant points have no influence.
• The soft margin adds slack variables penalized by C, and is exactly equivalent to hinge loss plus an L2 penalty. Large C means less regularization.
• The dual objective involves inputs only through dot products, which is what licenses the kernel trick and makes the model sparse in the training data.
• Scale features, tune C and gamma jointly on a log grid, and expect roughly n^2 to n^3 training cost for kernel SVMs.

The margin idea is worth carrying beyond this lesson. Whenever you can express "be right, and be right with room to spare", you get a model that degrades gracefully rather than catastrophically when the data shifts a little.

Sources

1. Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273-297. link.springer.com
2. Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. Proceedings of the Fifth Annual Workshop on Computational Learning Theory, 144-152. find source ↗
3. Hsu, C.-W., Chang, C.-C., & Lin, C.-J. (2016). A practical guide to support vector classification. National Taiwan University. csie.ntu.edu.tw
4. Chang, C.-C., & Lin, C.-J. (2011). LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3), 1-27. csie.ntu.edu.tw
5. Hastie, T., Tibshirani, R., & Friedman, J. (2009). Support vector machines and flexible discriminants. In The elements of statistical learning (2nd ed., ch. 12). Springer. hastie.su.domains
6. scikit-learn developers. (n.d.). Support vector machines. scikit-learn user guide. scikit-learn.org
7. scikit-learn developers. (n.d.). RBF SVM parameters. scikit-learn examples. scikit-learn.org

Clustering is the unsupervised task of grouping similar examples together using only the inputs. The most widely used clustering algorithm is k-means, which partitions data into a chosen number k of clusters, each represented by its center.

The big picture

Imagine you must place k warehouses to serve a country's customers, and your only goal is to minimize the total squared distance from customers to the warehouse serving them. Two subproblems appear immediately, and each is easy on its own. If the warehouses are already placed, every customer obviously goes to the nearest one. If the customer assignments are already fixed, the best position for each warehouse is obviously the average location of its customers. Neither problem is hard; what makes the joint problem hard is that each answer depends on the other.

k-means resolves the circularity by alternating: guess the warehouses, assign customers, move the warehouses to the average of their customers, reassign, and repeat. Each half-step is optimal given the other half fixed, so the total cost can only go down. That is the entire algorithm, and it explains both why it converges quickly and why it can converge to something mediocre: alternating optimization finds a point where neither half can improve alone, which is not necessarily the best configuration overall.

Key idea: k-means is alternating optimization of one cost. Because each step is optimal given the other, the cost decreases monotonically, and because the joint problem is non-convex, where you start determines where you land.

The objective

k-means seeks k cluster centers, called centroids, and an assignment of each point to a centroid, so as to minimize the total squared distance from points to their assigned centroids. This total is the within-cluster sum of squares (also called inertia):

minimize  sum over points x of  || x - centroid(cluster of x) ||^2

Small inertia means tight, compact clusters. "Hard" here is a precise statement: finding the globally optimal k-means partition is NP-hard even for k = 2 in general dimension, so no practical algorithm is guaranteed to find it. What we use instead is a fast heuristic that improves the objective each round and stops at a local optimum.

Notice what the squared-distance objective commits you to. Squared Euclidean distance is minimized by the arithmetic mean, which is why the update step is "move to the mean" and not something else; using a different distance would require a different update, and using medians instead gives a different algorithm (k-medoids) that resists outliers better. The objective also has no term rewarding balanced or well-separated clusters, only compactness, which is the root of several failure modes later in this lesson.

Lloyd's algorithm: two alternating steps

Starting from k initial centroids (often k random data points), repeat two steps until assignments stop changing:

repeat until no assignment changes:
    ASSIGN:  put each point in the cluster of its nearest centroid
    UPDATE:  move each centroid to the mean of the points assigned to it

Each step can only lower (or hold) the inertia, so the algorithm always converges, usually within a handful of iterations.

Why can the inertia only go down? The assignment step moves each point to the centroid that is nearest, which by definition cannot increase that point's contribution. The update step replaces each centroid by the mean of its members, and the mean is exactly the point minimizing the sum of squared distances to a set, so it cannot increase that cluster's contribution either. Since there are finitely many possible assignments and the cost never rises, the algorithm must terminate, usually in ten or twenty iterations regardless of dataset size.

Worked example. With k = 2 on points at 1, 2, 9, 10 (one dimension), suppose centroids start at 1 and 10. Assign: {1, 2} go to centroid 1, {9, 10} go to centroid 10. Update: the centroids move to the means, 1.5 and 9.5. Reassigning gives the same groups, so it has converged to the natural clusters {1, 2} and {9, 10}.

Worked example: two full iterations in two dimensions

Five points and k = 2, with centroids initialized at the first and last points.

Points:  A(1,1)  B(1.5,2)  C(3,4)  D(5,7)  E(3.5,5)
Initial centroids:  m1 = (1,1)   m2 = (3.5,5)

• Step 1, assign. Squared distance from B(1.5,2) to m1 is 0.25 + 1 = 1.25; to m2 it is 4 + 9 = 13. So B joins cluster 1. C(3,4) is 4 + 9 = 13 from m1 and 0.25 + 1 = 1.25 from m2, so it joins cluster 2. D(5,7) is 16 + 36 = 52 from m1 and 2.25 + 4 = 6.25 from m2, joining cluster 2. Result: cluster 1 = {A, B}, cluster 2 = {C, D, E}.
• Step 2, update. m1 = ((1 + 1.5)/2, (1 + 2)/2) = (1.25, 1.5). m2 = ((3 + 5 + 3.5)/3, (4 + 7 + 5)/3) = (11.5/3, 16/3) = (3.83, 5.33).
• Step 3, reassign. Check the point most likely to switch, C(3,4). Distance squared to m1 = (1.75)^2 + (2.5)^2 = 3.06 + 6.25 = 9.31; to m2 = (0.83)^2 + (1.33)^2 = 0.69 + 1.77 = 2.46. C stays in cluster 2. No point changes, so the algorithm has converged.
• Step 4, report the inertia. Cluster 1: A and B are each (0.25)^2 + (0.5)^2 = 0.3125 from m1, totalling 0.625. Cluster 2: C contributes 2.46, D contributes (1.17)^2 + (1.67)^2 = 1.37 + 2.79 = 4.16, E contributes (0.33)^2 + (0.33)^2 = 0.22. Total inertia = 0.625 + 2.46 + 4.16 + 0.22 = 7.47.

What we just did: two passes of assign-and-update on five points, with the inertia value that a library would report. Try the same points with initial centroids at C and E and you will find a different partition with a different inertia, which is the practical face of the non-convexity discussed next.

Two important caveats

• Initialization matters. Because the objective is non-convex, different starting centroids can converge to different, worse solutions (local minima). The standard fix is to run k-means several times with different random starts and keep the result with the lowest inertia; a smarter seeding scheme called k-means++ spreads the initial centroids out to make good outcomes more likely. Its rule is specific: pick the first centroid uniformly at random, then pick each subsequent centroid from the data with probability proportional to its squared distance from the nearest already-chosen centroid. Points far from every existing centroid are therefore likely to be chosen next, which discourages the classic failure of two seeds landing inside one true cluster. Arthur and Vassilvitskii (2007) proved this seeding alone gives an expected inertia within a factor of O(log k) of the optimum, before a single Lloyd iteration runs, and it is the default in scikit-learn.
• You must choose k. The algorithm needs the number of clusters as input.

Choosing k with the elbow method

Inertia always falls as k rises (more centroids fit the data more tightly), reaching zero when k equals the number of points, so we cannot just minimize it. The elbow method plots inertia against k and looks for the "elbow", the point where adding another cluster yields only a small further drop. That kink suggests a natural number of clusters. The elbow is honest but often ambiguous: on real data the curve frequently bends gently with no obvious corner, and different people read different elbows off the same plot.

Two sharper tools are worth knowing. The silhouette coefficient scores each point by comparing how close it is to its own cluster with how close it is to the nearest other cluster:

For point i:  a(i) = mean distance to other points in its OWN cluster
              b(i) = mean distance to points in the NEAREST OTHER cluster
              s(i) = ( b(i) - a(i) ) / max( a(i), b(i) )        ranges from -1 to +1
Average s(i) over all points to score a whole clustering.

A silhouette near +1 means the point sits comfortably inside its cluster; near 0 means it lies on a boundary; negative means it would be better off elsewhere. Averaging over points and comparing across k gives a criterion with an actual maximum rather than a subjective bend. The gap statistic goes further, comparing the observed inertia curve against the curve you would get from uniformly random data with the same bounding box, and choosing the k where the gap is largest; it has the virtue of being able to say "k = 1", that is, no cluster structure at all.

Key idea: inertia alone can never choose k, because it decreases mechanically with k. Any usable criterion must penalize complexity or compare against a null model.

What k-means assumes, and when it fails

k-means is fast and scalable, but the squared-distance-to-a-mean objective quietly assumes a great deal. Knowing the assumptions tells you exactly when to reach for something else:

• Roughly spherical clusters of similar size. Because assignment is by nearest centroid, the boundaries between clusters are always straight (a Voronoi partition). Two elongated, parallel, cigar-shaped groups will be cut across rather than separated.
• Similar densities. A large diffuse cluster next to a small tight one tends to get split, with the tight cluster absorbed into a neighbor.
• Comparable feature scales. Distance is dominated by whichever feature has the largest numeric range, so standardize first, exactly as with kernel SVMs.
• No meaningful outliers. A single extreme point drags its centroid, because the mean is not robust. k-medoids or DBSCAN handle this better.
• k clusters really exist. The algorithm always returns exactly k groups, even on data with no cluster structure at all. It cannot tell you that the answer is "there are no clusters here".

When these fail, the standard alternatives are Gaussian mixture models, which fit a covariance per component and give soft probabilistic memberships rather than hard assignments (k-means is essentially the limiting case with spherical, equal covariances and hard assignment); DBSCAN, which defines clusters by density and can find arbitrary shapes while labelling sparse points as noise, without needing k in advance; and hierarchical clustering, which builds a dendrogram you can cut at any level.

Where people get stuck

• "k-means found the true groups." It found a partition minimizing a specific compactness cost in the feature space and scaling you supplied. Whether the partition corresponds to anything real is an external question requiring domain validation.
• "I ran it once, so I have the answer." Different seeds give different local optima. Run at least ten restarts and keep the lowest inertia; scikit-learn's n_init parameter does this, and k-means++ seeding makes good outcomes far more likely.
• "Lower inertia means a better clustering." Only at a fixed k. Across different k, inertia always falls, so it cannot compare them.
• "Cluster labels are stable." The numbering is arbitrary and changes between runs. Never treat cluster 0 as a persistent identity without matching centroids across runs.
• "Standardizing is optional." It changes which clustering you get. Standardizing is a modeling decision about which features should count equally, so make it deliberately.

Recap

• k-means partitions data into k clusters by minimizing the within-cluster sum of squared distances (inertia).
• Lloyd's algorithm alternates assignment to the nearest centroid and relocation to the cluster mean; each step cannot increase the cost, so it always converges.
• The global optimum is NP-hard, so results depend on initialization; use multiple restarts and k-means++ seeding.
• k-means++ picks each new centroid with probability proportional to squared distance from the nearest existing centroid, spreading seeds apart.
• Inertia cannot choose k; use the elbow as a rough guide and the silhouette coefficient or gap statistic for a criterion with a real optimum.
• The method assumes spherical, similarly sized, similarly dense clusters on comparable scales; Gaussian mixtures, DBSCAN, and hierarchical clustering relax different parts of that.

Clustering is a hypothesis-generating tool. Use it to propose structure, then validate the proposal with something outside the clustering itself: a downstream prediction task, an external label, or an expert's judgment.

Sources

1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129-137. cs.cmu.edu
2. Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 1027-1035. theory.stanford.edu
3. Dasgupta, S. (2013). Algorithms for k-means clustering (CSE 291 lecture notes). University of California, San Diego. cseweb.ucsd.edu
4. Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20, 53-65. find source ↗
5. Hastie, T., Tibshirani, R., & Friedman, J. (2009). Cluster analysis. In The elements of statistical learning (2nd ed., ch. 14.3). Springer. hastie.su.domains
6. scikit-learn developers. (n.d.). Clustering. scikit-learn user guide. scikit-learn.org
7. scikit-learn developers. (n.d.). Demonstration of k-means assumptions. scikit-learn examples. scikit-learn.org

High-dimensional data is hard to visualize, slow to model, and often redundant because features are correlated. Principal component analysis (PCA) is the classic dimensionality reduction method: it re-expresses the data in a new set of axes ordered by how much variation they capture, letting us keep a few axes and discard the rest with minimal loss.

The big picture

Hold a pen at arm's length and shine a light on it, casting a shadow on the wall. Rotate the pen and the shadow changes: end-on it is a dot, telling you almost nothing, while side-on it is a full-length line preserving the pen's most important property. PCA is the systematic search for the shadow that preserves the most. Given a cloud of points in many dimensions, it finds the low-dimensional projection along which the points remain as spread out as possible, on the reasoning that variation is where the information lives.

There is a second, equivalent way to describe the same answer, and having both in mind is useful. Maximizing the variance retained by the projection is exactly the same as minimizing the squared distance between each original point and its projection. So PCA is simultaneously "the most informative view" and "the least lossy compression". The two descriptions coincide because total variance splits cleanly into what the projection keeps and what it discards, so keeping the most is discarding the least.

Key idea: PCA rotates the coordinate axes to align with the data's own directions of spread. It does not change the data at all; it changes the description, and then lets you throw away the least useful parts of the description.

The core idea: directions of maximum variance

PCA finds new directions, the principal components, that are straight-line combinations of the original features. The first principal component is the single direction along which the data varies the most. The second is the direction of greatest remaining variance that is orthogonal (perpendicular) to the first, and so on. Each component is orthogonal to all earlier ones, so the new axes are uncorrelated. Intuitively, PCA rotates the coordinate system to line up with the natural spread of the data.

The mathematics: eigenvectors of the covariance matrix

Center the data (subtract each feature's mean) and form the covariance matrix S, a d-by-d symmetric matrix whose (j, k) entry is the covariance between features j and k. The variance of the data projected onto a unit direction u is u-transpose S u, so PCA is the constrained problem

maximize   u^T S u     subject to   u^T u = 1
Lagrange:  S u = lambda u        (an eigenvalue equation)
Therefore: principal components = eigenvectors of S
           variance along component j = lambda_j, its eigenvalue
Ordering the eigenvalues lambda_1 >= lambda_2 >= ... gives PC1, PC2, ...

Because S is symmetric and positive semi-definite, its eigenvalues are real and nonnegative and its eigenvectors can be chosen mutually orthogonal, which is exactly the structure PCA promises. The sum of the eigenvalues equals the total variance, that is, the trace of S, which is what makes "fraction of variance explained" a meaningful ratio.

In practice no implementation forms S and diagonalizes it. Libraries apply the singular value decomposition directly to the centered data matrix X = U D V-transpose. The columns of V are the principal directions and the squared singular values relate to the eigenvalues by lambda_j = d_j^2 / (n - 1). The reason is the same numerical argument as in Lesson 4: forming X-transpose-X squares the condition number and loses precision, while the SVD works on X itself.

Worked example: PCA on a 2 by 2 covariance matrix

Suppose two standardized features have covariance matrix

S = [ 1.0   0.8 ]
    [ 0.8   1.0 ]

• Step 1, eigenvalues. Solve det(S - lambda*I) = 0, that is (1 - lambda)^2 - 0.64 = 0, so 1 - lambda = +/- 0.8 and lambda_1 = 1.8, lambda_2 = 0.2.
• Step 2, check the total. lambda_1 + lambda_2 = 2.0, which equals the trace of S, the total variance of two standardized features. Good.
• Step 3, eigenvectors. For lambda_1 = 1.8, solve (S - 1.8I)u = 0, giving -0.8u_1 + 0.8u_2 = 0, so u_1 = u_2 and the unit eigenvector is (0.707, 0.707), the 45-degree diagonal. For lambda_2 = 0.2 the eigenvector is (0.707, -0.707), perpendicular to it.
• Step 4, explained variance. PC1 carries 1.8 / 2.0 = 90 percent of the variance, PC2 carries 0.2 / 2.0 = 10 percent.
• Step 5, interpret. Two features correlated at 0.8 are largely redundant: 90 percent of what they jointly say is captured by their sum, and only 10 percent by their difference. Keeping PC1 alone reduces two numbers to one while losing a tenth of the spread.

What we just did: the entire PCA pipeline in miniature. Notice how the correlation drove the result. Had the off-diagonal been 0.0, both eigenvalues would be 1.0, PC1 would explain only 50 percent, and PCA would offer no compression at all. PCA helps exactly to the extent that your features are correlated, which is also why it is nearly useless on already-uncorrelated features.

Explained variance

Each principal component carries a share of the data's total variance, its explained variance. Because the components are ordered from most to least, the first few often account for the bulk of the variation. Reporting the cumulative explained variance tells you how many components you need: if the first two components together explain 90% of the variance, you can replace many original features with just two coordinates and lose only 10% of the spread. This is the payoff, fewer dimensions, most of the information.

Three conventions for choosing how many components to keep, in rough order of usefulness. Set a variance target (keep enough components to reach 90 or 95 percent cumulative). Read a scree plot of eigenvalue against component index and look for the elbow, the same bend-hunting exercise as choosing k in k-means and with the same ambiguity. Or, when PCA feeds a supervised model, treat the number of components as a hyperparameter and select it by cross-validation on the downstream task, which is the only criterion that measures what you actually care about.

Using PCA

The recipe is short: standardize the features (PCA is sensitive to scale, since it chases variance), compute the principal components, then project the data onto the top few. Common uses are:

• Visualization: project to 2 or 3 components to plot high-dimensional data and eyeball its structure.
• Compression and speed: fewer features mean faster, lighter downstream models.
• Noise reduction: discarding low-variance components can drop noise while keeping signal.

Standardizing is more consequential than it sounds. PCA on the raw covariance matrix lets whichever feature has the largest numeric variance dominate the first component: income in dollars will bury age in years for no reason other than units. PCA on the correlation matrix, which is what you get by standardizing first, treats every feature as equally important a priori. Standardize by default, and depart from that only when the features share meaningful units and their relative magnitudes are themselves informative, as with pixel intensities or repeated measurements of the same quantity.

A related option is whitening: after projecting, divide each component by its standard deviation so all retained components have unit variance. This is useful when a downstream algorithm is distance-based and you want each retained direction to count equally, and harmful when the relative magnitudes carried real signal.

PCA also supports reconstruction. Project down to k components, then map back to the original space; the difference is the reconstruction error, whose average equals the sum of the discarded eigenvalues. Because low-variance directions often carry more noise than signal, discarding them can genuinely denoise the data. That said, "low variance" and "unimportant" are not synonyms, which brings us to the limits.

Limitations, and what to reach for instead

PCA is linear: it captures only straight-line structure and can miss curved patterns. Points arranged on a spiral or a curved sheet have their structure smeared by any linear projection. Principal components are also combinations of original features, so a component like "0.4 times income plus 0.3 times education minus 0.2 times debt" is harder to explain than any single column.

The most important caution is the third one: variance is not the same as usefulness. PCA is unsupervised and never looks at the target, so a direction that separates your classes perfectly but happens to have small variance will be discarded without hesitation. If your aim is supervised prediction, PCA is a reasonable preprocessing step but not a substitute for feature selection, and you should verify on held-out data that it helped rather than assuming.

For nonlinear structure, the modern tools are t-SNE (van der Maaten & Hinton, 2008) and UMAP, which build a neighborhood graph and lay it out in two dimensions so nearby points stay nearby. They produce far more legible cluster pictures than PCA, and they come with a serious interpretive warning: in a t-SNE plot the sizes of clusters and the distances between them are largely artifacts of the perplexity setting and the random seed, not properties of the data (Wattenberg et al., 2016). Read them as evidence that groups exist, never as a map with meaningful distances. Both are visualization tools rather than reusable transformations; PCA, by contrast, produces a fitted linear map you can apply unchanged to new data, which is why it remains the default preprocessing step. Autoencoders generalize PCA to nonlinear compression, and a linear autoencoder trained with squared error recovers the PCA subspace exactly.

Where people get stuck

• "PC1 is my most important feature." PC1 is the direction of greatest variance in the inputs. It has no knowledge of your target and may be irrelevant to it.
• "Fit PCA on all the data, then split." That is leakage (Lesson 9). Fit PCA inside the training fold and apply the same transformation to validation and test data.
• "Components are meaningful concepts." Loadings sometimes suggest an interpretation, and sometimes they are numerically convenient mixtures with no interpretation at all. Do not force one.
• "The signs of the loadings matter." Eigenvectors are defined up to sign, so a component and its negation are the same component. Different libraries and different runs may flip it.
• "95 percent variance retained means 95 percent accuracy retained." Those are unrelated quantities. Measure downstream performance rather than inferring it from a variance ratio.

Recap

• PCA finds orthogonal directions of maximum variance, equivalently the projection minimizing squared reconstruction error.
• The components are the eigenvectors of the covariance matrix and the variance along each is its eigenvalue; implementations use the SVD for numerical stability.
• Explained variance ratios sum to 1, and cumulative explained variance tells you how many components to keep.
• Standardize first unless the features share meaningful units, because PCA on raw covariances is dominated by whichever feature has the largest scale.
• PCA compresses only to the extent that features are correlated, and it captures only linear structure.
• Variance is not importance: PCA is unsupervised, so validate on the downstream task, and treat t-SNE and UMAP layouts as evidence of grouping rather than as maps with real distances.

Used with those limits in mind, PCA is an indispensable first step for exploring and compressing high-dimensional data, and the eigen-decomposition at its heart is the same machinery you will meet again in spectral clustering, factor analysis, and the analysis of neural network representations.

Sources

1. Pearson, K. (1901). On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 2(11), 559-572. find source ↗
2. Jolliffe, I. T., & Cadima, J. (2016). Principal component analysis: A review and recent developments. Philosophical Transactions of the Royal Society A, 374(2065), 20150202. pmc.ncbi.nlm.nih.gov
3. Shlens, J. (2014). A tutorial on principal component analysis. arXiv. arxiv.org
4. Hastie, T., Tibshirani, R., & Friedman, J. (2009). Principal components, curves and surfaces. In The elements of statistical learning (2nd ed., ch. 14.5). Springer. hastie.su.domains
5. scikit-learn developers. (n.d.). Decomposing signals in components (matrix factorization problems). scikit-learn user guide. scikit-learn.org
6. van der Maaten, L., & Hinton, G. (2008). Visualizing data using t-SNE. Journal of Machine Learning Research, 9(86), 2579-2605. jmlr.org
7. Wattenberg, M., Viegas, F., & Johnson, I. (2016). How to use t-SNE effectively. Distill. distill.pub

A neural network is a model built by stacking many simple units into layers, so that the whole can represent very complex functions. It generalizes logistic regression: where logistic regression has one linear-then-sigmoid unit, a neural network chains many of them, letting it learn nonlinear patterns automatically.

The big picture

Everything before this module required you to supply the right features. A linear model can only fit a curve if you hand it an x-squared column; a tree can only use a ratio if you compute it. Neural networks change the division of labor: given enough layers and data, the intermediate layers learn useful transformations of the raw input, and the final layer runs an ordinary linear model on top of them. That is why the field's older name for this was representation learning, and it is the honest one-sentence summary of what depth buys you.

Think of a layer as a stage in a factory. Raw pixels arrive; the first stage produces something like edge detectors; the next assembles edges into corners and textures; the next into object parts; the last decides "cat". Nobody wrote down what an edge detector is. The weights that compute one were found by gradient descent on the same loss you have been minimizing since Module 2. Nothing mystical is happening: this is still a hypothesis class, a loss function, and an optimizer, exactly as in Lesson 1. The hypothesis class is just enormously more expressive.

Key idea: a neural network is a composition of simple functions, alternating linear maps with nonlinearities. The composition is what creates expressive power, and the nonlinearity is what makes composition non-trivial.

Neurons and layers

The basic unit, a neuron, does exactly what we have seen: it computes a weighted sum of its inputs plus a bias, then applies a nonlinear activation function. Neurons are organized into layers:

• The input layer holds the features.
• One or more hidden layers transform the data through their neurons; a network with several hidden layers is called deep.
• The output layer produces the prediction (one sigmoid unit for binary classification, several units for multiclass or regression).

Each neuron in a layer connects to every neuron in the next, each connection carrying a learnable weight. A modest network can have thousands of weights, all tuned by training. Counting them is a useful habit: a fully connected layer from m inputs to n outputs holds m*n weights plus n biases. A 784-256-128-10 network for handwritten digits therefore holds 784*256 + 256 + 256*128 + 128 + 128*10 + 10 = 200,704 + 256 + 32,768 + 128 + 1,280 + 10 = 235,146 parameters. Compare that with 60,000 training images and the overfitting risk from Module 3 becomes concrete rather than abstract, which is why regularization is not optional here.

Written in matrix form the whole layer is one operation, which is how it is actually computed:

Layer l:   z^(l) = W^(l) a^(l-1) + b^(l)          W is (n_l by n_(l-1))
           a^(l) = g( z^(l) )                     g applied elementwise
Input:     a^(0) = x
Output:    y_hat = a^(L)
For a batch of B examples, stack them: Z = X W^T + b, one matrix multiply for the whole batch.

That last line is the practical reason GPUs matter. A forward pass is a chain of dense matrix multiplications, precisely the operation graphics hardware performs thousands of times in parallel, which is why hardware built for rendering triangles turned out to be the right hardware for training networks.

Why nonlinearity is the whole point

The activation function must be nonlinear. Here is why: if every neuron were purely linear, then stacking layers would just compose linear maps, and a composition of linear maps is itself a single linear map. The entire deep network would collapse to a plain linear model, no matter how many layers. Nonlinear activations break that collapse, so each layer can bend and fold the representation, and the network as a whole can approximate very complicated functions. Common activations are the sigmoid, the hyperbolic tangent (tanh), and the ReLU (rectified linear unit), which simply outputs max(0, z): cheap to compute and effective in deep networks.

This is also where the universal approximation theorem belongs, and it is routinely overstated, so state it carefully. Cybenko (1989) and Hornik, Stinchcombe and White (1989) proved that a feedforward network with a single hidden layer and a suitable nonlinear activation can approximate any continuous function on a compact set to arbitrary accuracy, given enough hidden units. What the theorem does not say is at least as important. It gives no bound on how many units are needed, which may be astronomically many. It says nothing about whether gradient descent will find those weights. And it says nothing about generalization from finite data. Universal approximation explains why networks are not obviously limited; it does not explain why they work.

Choosing an activation is a real decision. The main options:

Activation	Formula	Notes
Sigmoid	1 / (1 + e^(-z))	Output in (0,1); derivative at most 0.25, so it shrinks gradients. Use only at a binary output.
tanh	(e^z - e^(-z)) / (e^z + e^(-z))	Output in (-1,1) and zero-centered, which helps optimization; still saturates.
ReLU	max(0, z)	Derivative 1 for z > 0, cheap, sparse activations. Units can "die" if they get stuck at z < 0.
Leaky ReLU	max(0.01z, z)	Small negative slope keeps dead units recoverable.
GELU	z * Phi(z)	Smooth, gates by the input's own magnitude; standard in transformer architectures.

ReLU displaced sigmoid and tanh in hidden layers after Glorot, Bordes and Bengio (2011) showed that rectifiers train deep networks faster and better, largely because their gradient does not vanish for positive inputs. Smooth variants such as GELU (Hendrycks & Gimpel, 2016) are now the default inside transformers. The output activation is a separate choice determined by the task: identity for regression, sigmoid for binary classification, softmax for multiclass. Never put a ReLU on a regression output unless the target genuinely cannot be negative.

Key idea: hidden activations exist to break linearity and to keep gradients flowing. Output activations exist to put the prediction in the right range for the loss.

The forward pass

Computing a prediction is the forward pass: feed the inputs into the first layer, apply weights, biases, and activation to get that layer's outputs, feed those into the next layer, and continue to the output.

Worked example. A neuron has inputs x = (2, 3), weights w = (0.5, -1), and bias b = 1. Its pre-activation is z = 0.5(2) + (-1)(3) + 1 = 1 - 3 + 1 = -1. With a ReLU activation the output is max(0, -1) = 0; with a sigmoid it would be about 0.27.

Worked example: a full forward pass

A 2-3-1 network with ReLU hidden units and a sigmoid output. Input x = (1, 2).

Hidden weights W1 (3 rows, one per hidden unit) and biases b1:
    h1: w = ( 1.0, -1.0)   b =  0.5
    h2: w = ( 0.5,  0.5)   b = -2.0
    h3: w = (-1.0,  2.0)   b =  0.0
Output weights W2 = (1.0, -2.0, 0.5),  b2 = -1.0

• Step 1, hidden pre-activations. z1 = 1.0*1 + (-1.0)*2 + 0.5 = 1 - 2 + 0.5 = -0.5. z2 = 0.5*1 + 0.5*2 - 2.0 = 0.5 + 1.0 - 2.0 = -0.5. z3 = -1.0*1 + 2.0*2 + 0.0 = -1 + 4 = 3.0.
• Step 2, hidden activations. ReLU gives a1 = max(0, -0.5) = 0, a2 = max(0, -0.5) = 0, a3 = max(0, 3.0) = 3.0. Two of three units are inactive for this input, which is the sparsity ReLU is known for.
• Step 3, output pre-activation. z_out = 1.0*0 + (-2.0)*0 + 0.5*3.0 - 1.0 = 1.5 - 1.0 = 0.5.
• Step 4, output activation. y_hat = sigmoid(0.5) = 1 / (1 + e^(-0.5)) = 1 / 1.6065 = 0.622.
• Step 5, the loss, if the true label is y = 1. Cross-entropy = -log(0.622) = 0.475.
• Step 6, sanity check the dead units. Because a1 and a2 are exactly 0, the output does not depend on the first two output weights for this input, and the gradient will not update the weights feeding those units either. If that persists for every input, those units are dead and the network has effectively lost capacity.

What we just did: eleven multiplications and one squashing function produced a prediction and a loss. A network with a hundred billion parameters does exactly this, just with much larger matrices. Chaining such calculations layer by layer yields the network's prediction, which we then compare to the true label with a loss, setting up the training in the next lesson.

Depth, width, and modern architectures

Given a fixed parameter budget, depth usually beats width. There are function families a deep network represents with a number of units growing polynomially where a shallow one needs exponentially many, and depth also matches the compositional structure of real signals, where objects are made of parts made of edges. The practical counterweight is that very deep networks are harder to optimize, which is what residual connections (Module 6 and beyond) were designed to fix.

The fully connected network in this lesson is the general case, and modern architectures are mostly the general case plus a structural assumption that reduces parameters and encodes prior knowledge:

• Convolutional networks share a small set of weights across spatial positions, encoding the assumption that a useful pattern is useful anywhere in the image. This cuts parameters enormously and builds in translation equivariance.
• Recurrent networks reuse the same weights across time steps for sequences, carrying a hidden state forward.
• Transformers (Vaswani et al., 2017) replace recurrence with an attention mechanism in which every position computes a weighted combination of all positions, with weights derived from learned query, key, and value projections. Because those weights are computed rather than fixed, the network can route information between arbitrary positions, and because the computation is parallel across positions rather than sequential, it trains far more efficiently on modern hardware. Transformers are now the backbone of large language models and are widely used for images and audio as well.

Every one of these still performs the same forward pass you just computed by hand: linear maps, nonlinearities, a loss at the end.

Where people get stuck

• "Neurons work like brain cells." The analogy inspired the name and stops there. An artificial neuron is a dot product followed by a scalar function; biological neurons are vastly more complex and do not learn by backpropagation.
• "Universal approximation means a network can learn anything." It means a network can represent any continuous function on a compact set given unlimited width. Representing is not learning; the theorem is silent about optimization and about generalization from finite data.
• "More layers are always better." Deeper networks need more data, more careful initialization, and often architectural help such as residual connections and normalization. On a small tabular dataset a two-layer network frequently loses to gradient boosting.
• "ReLU has no downsides." Units whose pre-activation is negative for every input contribute nothing and receive no gradient. Leaky ReLU or GELU, plus a sensible learning rate, mitigates this.
• "Forget feature scaling now that the network learns features." Unscaled inputs still produce a badly conditioned loss surface (Lesson 5). Standardize inputs and use a principled initialization scheme.

Recap

• A neural network stacks layers of neurons, each computing a weighted sum plus bias followed by a nonlinear activation.
• A layer is one matrix multiply plus a bias vector, which is why the whole forward pass maps onto GPU hardware.
• Without nonlinear activations the composition of layers collapses to a single linear map, no matter the depth.
• Universal approximation says one hidden layer suffices in principle, with no guarantee about width, trainability, or generalization.
• ReLU and its smooth variants dominate hidden layers; the output activation is fixed by the task, and the parameter count grows as m*n per dense layer.
• Convolutional, recurrent, and transformer architectures add structural assumptions on top of the same forward-pass machinery.

You can now compute what a network predicts. The next lesson explains how those hundreds of thousands of weights get set in the first place, which is where backpropagation earns its reputation.

Sources

1. Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386-408. ling.upenn.edu
2. Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4), 303-314. link.springer.com
3. Hornik, K., Stinchcombe, M., & White, H. (1989). Multilayer feedforward networks are universal approximators. Neural Networks, 2(5), 359-366. cognitivemedium.com
4. Glorot, X., Bordes, A., & Bengio, Y. (2011). Deep sparse rectifier neural networks. Proceedings of Machine Learning Research, 15, 315-323. proceedings.mlr.press
5. Hendrycks, D., & Gimpel, K. (2016). Gaussian error linear units (GELUs). arXiv. arxiv.org
6. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2017). Attention is all you need. arXiv. arxiv.org
7. Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep feedforward networks. In Deep learning (ch. 6). MIT Press. deeplearningbook.org

A neural network has thousands of weights, and gradient descent needs the gradient of the loss with respect to every one of them. Computing those gradients efficiently is the job of backpropagation, the algorithm that made training deep networks practical. It is nothing more exotic than the calculus chain rule, applied cleverly and reused across the network.

The big picture

Consider how you might compute the gradient without backpropagation. Nudge one weight by a tiny amount, run the whole network forward, see how the loss changed, divide by the nudge. That is a finite-difference derivative, and it is correct. It is also catastrophically expensive: one forward pass per weight, so a network with 235,000 weights needs 235,000 forward passes to take one gradient step. At that cost deep learning would never have happened.

Backpropagation computes every one of those derivatives in a single backward sweep costing roughly as much as one forward pass. The speedup is not a clever approximation; the gradients are exact. It comes from recognizing that the same intermediate quantities appear in the derivative of every weight in a layer, so computing them once and reusing them turns a per-weight cost into a per-layer cost. That single observation, published for neural networks by Rumelhart, Hinton and Williams in 1986 and known more generally as reverse-mode automatic differentiation, is what made training deep models feasible.

Key idea: backpropagation is the chain rule organized so that shared factors are computed once. Exact gradients for every parameter, at the price of about one extra forward pass.

The idea: assign blame backward

Training alternates two passes. The forward pass computes the prediction and the loss, as in the last lesson, caching each layer's intermediate values. The backward pass then works from the loss back toward the inputs, computing how much each weight contributed to the error, its partial derivative. Because a weight in an early layer affects the loss only through the layers that follow it, its influence is a product of the derivatives along that path, exactly what the chain rule multiplies together.

Chain rule intuition for one weight w:
    dLoss/dw = dLoss/d(output) * d(output)/d(hidden) * ... * d(...)/dw
Backprop computes these products once, layer by layer, from output to input,
reusing shared factors instead of recomputing them.

The key efficiency is reuse: the gradient signal arriving at a layer is passed back and combined with that layer's local derivative to produce both the updates for its weights and the signal to send to the previous layer. One backward sweep yields every gradient, at roughly the cost of one forward pass.

Made precise, the whole algorithm is four equations. Write delta^(l) for the gradient of the loss with respect to layer l's pre-activations z^(l), the quantity that carries blame backward:

(1) Output layer:   delta^(L) = dLoss/da^(L)  *  g'( z^(L) )
    (for sigmoid or softmax output with cross-entropy this simplifies to  a^(L) - y)
(2) Propagate back:  delta^(l) = ( W^(l+1) )^T delta^(l+1)  *  g'( z^(l) )
(3) Weight gradient: dLoss/dW^(l) = delta^(l) ( a^(l-1) )^T
(4) Bias gradient:   dLoss/db^(l) = delta^(l)
    ( * denotes elementwise multiplication )

Equation (2) is the heart of it. To get the blame at layer l you take the blame at layer l+1, push it back through the transposed weight matrix (each unit receives blame in proportion to how strongly it fed forward), and multiply by the local derivative of this layer's activation. Equation (3) then says the same thing you saw in linear and logistic regression: the gradient for a weight is the incoming activation times the outgoing blame. Error times input, one more time.

Worked example: backpropagation by hand

A minimal network: one input x, one hidden ReLU unit, one linear output, squared-error loss.

x = 2,  y = 1
w1 = 0.5, b1 = 0      ->  z1 = w1*x + b1
a1 = ReLU(z1)
w2 = -1.0, b2 = 0.5   ->  y_hat = w2*a1 + b2
Loss = 0.5 * ( y_hat - y )^2

• Step 1, forward. z1 = 0.5*2 + 0 = 1.0. a1 = ReLU(1.0) = 1.0. y_hat = -1.0*1.0 + 0.5 = -0.5. Loss = 0.5*(-0.5 - 1)^2 = 0.5*2.25 = 1.125.
• Step 2, output blame. dLoss/dy_hat = y_hat - y = -0.5 - 1 = -1.5. The output is linear, so delta_out = -1.5.
• Step 3, output-layer gradients. dLoss/dw2 = delta_out * a1 = -1.5 * 1.0 = -1.5. dLoss/db2 = delta_out = -1.5.
• Step 4, propagate back. The blame arriving at a1 is delta_out * w2 = -1.5 * (-1.0) = 1.5. ReLU's derivative at z1 = 1.0 is 1 (positive input), so delta_1 = 1.5 * 1 = 1.5.
• Step 5, hidden-layer gradients. dLoss/dw1 = delta_1 * x = 1.5 * 2 = 3.0. dLoss/db1 = delta_1 = 1.5.
• Step 6, update with alpha = 0.1. w2 := -1.0 - 0.1*(-1.5) = -0.85. b2 := 0.5 - 0.1*(-1.5) = 0.65. w1 := 0.5 - 0.1*3.0 = 0.20. b1 := 0 - 0.1*1.5 = -0.15.
• Step 7, verify. New z1 = 0.20*2 - 0.15 = 0.25, a1 = 0.25, y_hat = -0.85*0.25 + 0.65 = 0.4375. New loss = 0.5*(0.4375 - 1)^2 = 0.158, down sharply from 1.125.

What we just did: one complete training step for every parameter, computed with a single forward pass and a single backward pass. Note step 4 in particular. Had z1 been negative, ReLU's derivative would be 0, delta_1 would be 0, and w1 and b1 would receive no update at all on this example. That is the mechanism behind dead units, and, run through many layers, behind vanishing gradients.

Putting it together: the training loop

Backpropagation supplies the gradients; gradient descent (usually mini-batch, from Module 2) uses them to update the weights. The loop is:

repeat for many epochs:
    for each mini-batch:
        forward pass:   compute predictions and loss
        backward pass:  backpropagate to get gradient for every weight
        update:         weight := weight - alpha * gradient

One full sweep through the training data is an epoch; networks typically train for many epochs. All the earlier ideas return here: the learning rate must be tuned, features should be standardized so the loss surface is well-behaved, and regularization (including a neural-network favorite, dropout, which randomly disables neurons during training) fights overfitting.

Two setup decisions matter as much as the loop itself. Initialization cannot be all zeros, because then every unit in a layer computes the same thing, receives the same gradient, and stays identical forever; symmetry must be broken by random values. Nor can it be arbitrary random values, because if the variance is too large the activations saturate and if it is too small the signal dies out over depth. Glorot and Bengio (2010) derived a scale that keeps activation variance roughly constant across layers for tanh-like units, and He et al. (2015) adapted it for ReLU, whose zeroing of half the inputs calls for a factor of 2. These are the defaults in every modern framework and are one of the quiet reasons deep networks became trainable.

Normalization layers are the other. Batch normalization standardizes each unit's pre-activations across the current mini-batch, then rescales them with learned parameters (Ioffe & Szegedy, 2015). Empirically this permits much higher learning rates and speeds up training substantially, though the original explanation in terms of "internal covariate shift" has been contested and the mechanism is still debated. Layer normalization, which standardizes across features within a single example instead of across the batch, is the variant used in transformers because it does not depend on batch composition.

Practical pitfalls

Two issues deserve naming. The vanishing gradient problem: when many small derivatives multiply together through deep networks, the gradient reaching early layers can shrink toward zero, stalling their learning. This is one reason ReLU (whose derivative is 1 for positive inputs) largely replaced the sigmoid in hidden layers. The opposite, exploding gradients, can also occur. And because the loss surface of a neural network is non-convex, training finds a good local minimum rather than a guaranteed global one, which is usually fine in practice; in high dimensions the more common obstacles are saddle points and flat plateaus than genuinely bad basins, and most local minima that gradient descent reaches turn out to have similar loss.

Make the vanishing-gradient arithmetic concrete. Suppose each layer contributes a derivative factor of about 0.25, the maximum for a sigmoid. After 10 layers the gradient reaching the first layer is scaled by 0.25^10, roughly 1e-6, so the early layers barely move while the late ones train normally. Three fixes are standard, and they are complementary rather than competing:

• ReLU-family activations, whose derivative is 1 on the active side, so the product does not decay.
• Residual (skip) connections, which add a layer's input to its output so that the gradient has a path back with derivative 1 regardless of what the layer does. This is what let He et al. (2016) train networks over a hundred layers deep, and it is now standard in transformers as well.
• Normalization layers, which keep activations in a range where derivatives are well behaved.

The opposite problem, exploding gradients, is most common in recurrent networks and is handled by gradient clipping: if the gradient's norm exceeds a threshold, rescale it down to that threshold before the update, preserving direction while capping step size.

Regularizing a network

Everything from Lesson 8 applies, with a few neural-network specifics. Dropout with rate 0.2 to 0.5 on fully connected layers randomly zeroes activations during training and scales appropriately, then uses the full network at test time. Weight decay is the L2 penalty, applied in decoupled form when using Adam. Early stopping on a validation metric is nearly free and almost always worth it. Data augmentation encodes the invariances you want the model to have. And there is an implicit regularizer you do not configure at all: the noise in mini-batch gradients biases the optimizer toward flatter regions of the loss surface, which is part of why SGD-trained networks generalize better than the raw parameter count would suggest (Lesson 7).

Autodiff in practice

You will almost never implement backpropagation. Frameworks such as PyTorch, TensorFlow, and JAX build a computational graph as the forward pass executes and then apply reverse-mode automatic differentiation to it, so any function you can write from differentiable primitives gets exact gradients for free (Baydin et al., 2018). This matters for how you should think about model design: you are free to invent an architecture or a loss and trust the gradients, which is exactly the freedom that produced the last decade of architectural experimentation. It is still worth knowing what the framework is doing, because the failures you will actually debug, exploding losses, dead units, gradients that are silently zero because you detached a tensor, are all failures of the mechanism described in this lesson.

Backpropagation plus gradient descent, run over many epochs with sensible initialization, activations, normalization, and regularization, is the engine behind essentially all modern deep learning, from a two-layer tabular model to a frontier language model. The scale differs by nine orders of magnitude; the algorithm does not.

Where people get stuck

• "Backpropagation is the learning algorithm." It computes gradients. Gradient descent (or Adam) uses them. Keeping the two separate makes optimizer choices much clearer.
• "Backprop gives approximate gradients." They are exact to floating-point precision. Finite differences are the approximation, useful only as a debugging check on small examples.
• "Initialize the weights to zero for a clean start." Then every unit in a layer is identical forever, because they receive identical gradients. Random initialization at a principled scale is essential.
• "The training loss went down, so it is working." Training loss going down while validation loss rises is overfitting. Always plot both.
• "Non-convexity means training is unreliable." In practice different random seeds usually reach solutions of similar quality. The reproducibility risks are elsewhere: data ordering, nondeterministic GPU kernels, and undisciplined hyperparameter search.

Recap

• Backpropagation is the chain rule applied across layers, organized so shared factors are computed once.
• It yields exact gradients for every parameter at about the cost of one extra forward pass, versus one forward pass per weight for finite differences.
• The four equations propagate delta backward through the transposed weight matrices and the local activation derivatives; each weight's gradient is incoming activation times outgoing blame.
• Training loops over mini-batches for many epochs: forward, backward, update.
• Principled random initialization and normalization layers make deep networks trainable; residual connections, ReLU-family activations, and gradient clipping address vanishing and exploding gradients.
• Automatic differentiation frameworks implement all of this, so architecture design is unconstrained by the need to derive gradients by hand.

With the forward pass, the loss, and the gradients in hand, you have the complete training machinery for a neural network. What remains is knowing whether the trained model is any good, which is the subject of the final module.

Sources

1. Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. Nature, 323(6088), 533-536. nature.com
2. Baydin, A. G., Pearlmutter, B. A., Radul, A. A., & Siskind, J. M. (2018). Automatic differentiation in machine learning: A survey. Journal of Machine Learning Research, 18(153), 1-43. jmlr.org
3. Glorot, X., & Bengio, Y. (2010). Understanding the difficulty of training deep feedforward neural networks. Proceedings of Machine Learning Research, 9, 249-256. proceedings.mlr.press
4. He, K., Zhang, X., Ren, S., & Sun, J. (2015). Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification. arXiv. arxiv.org
5. Ioffe, S., & Szegedy, C. (2015). Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv. arxiv.org
6. He, K., Zhang, X., Ren, S., & Sun, J. (2016). Deep residual learning for image recognition. arXiv. arxiv.org
7. Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., ... Chintala, S. (2019). PyTorch: An imperative style, high-performance deep learning library. arXiv. arxiv.org

A single accuracy number rarely tells the whole story of a classifier, especially when one class is rare or when different mistakes carry different costs. Proper evaluation starts with the confusion matrix and the metrics built from it.

The big picture

A smoke detector and a cancer screening test face the same statistical problem and opposite cost structures. Nobody minds a smoke alarm going off over burnt toast, but everybody minds a fire it failed to detect, so the alarm is tuned to almost never miss and to tolerate false alarms. A screening test that flags one healthy person in three sends thousands to unnecessary biopsies, so the tolerance runs the other way. A single accuracy number cannot express either of those preferences, because it treats a miss and a false alarm as the same unit of badness.

That is the whole motivation for this lesson. Evaluation is not a formality performed after modeling; it is where the actual decision problem enters. Two models with identical accuracy can be worlds apart in usefulness, and the confusion matrix is the object that shows you the difference.

Key idea: accuracy collapses two distinct kinds of error into one number. Almost every real application cares about them differently, so almost every real evaluation needs more than accuracy.

The confusion matrix

For binary classification, every prediction falls into one of four cells, comparing the predicted label to the true label:

	Predicted Positive	Predicted Negative
Actually Positive	True Positive (TP)	False Negative (FN)
Actually Negative	False Positive (FP)	True Negative (TN)

A false positive is a false alarm (predicted positive, actually negative); a false negative is a miss (predicted negative, actually positive). Which is worse depends entirely on the application, and that is the point.

The core metrics

From these four counts we build the standard metrics:

Accuracy  = (TP + TN) / (TP + TN + FP + FN)   # fraction correct overall
Precision = TP / (TP + FP)   # of predicted positives, how many are right
Recall    = TP / (TP + FN)   # of actual positives, how many we caught
F1        = 2 * (Precision * Recall) / (Precision + Recall)   # their harmonic mean

Precision answers "when the model says positive, how often is it correct?", it matters when false alarms are costly (for example, flagging a legitimate email as spam).

Recall (sensitivity) answers "of all the real positives, how many did we find?", it matters when misses are costly (for example, failing to detect a disease). The F1 score is their harmonic mean, a single balanced number that is high only when both precision and recall are high. The harmonic mean is the right choice precisely because it refuses to be fooled by an extreme: a model with precision 1.0 and recall 0.01 has arithmetic mean 0.505 but F1 = 2(1.0 * 0.01)/(1.01) = 0.0198, which correctly reports that the model is nearly useless.

The same four counts support several other names, and knowing the synonyms saves confusion when moving between fields:

Name	Formula	Also called	Reads as
Recall	TP / (TP + FN)	Sensitivity, true positive rate, hit rate	Of the actual positives, the share caught
Specificity	TN / (TN + FP)	True negative rate; 1 - specificity is the FPR	Of the actual negatives, the share correctly cleared
Precision	TP / (TP + FP)	Positive predictive value (PPV)	Of the flagged cases, the share truly positive
NPV	TN / (TN + FN)	Negative predictive value	Of the cleared cases, the share truly negative

Recall and specificity are computed within the true classes and are therefore properties of the classifier that do not change with prevalence. Precision and NPV are computed within the predicted classes and do change with prevalence, a point developed below with numbers. Medicine uses sensitivity and specificity for exactly this reason: they transfer between populations, while PPV does not.

When one error genuinely outweighs the other, use the F-beta score, which weights recall beta times as heavily as precision:

F_beta = (1 + beta^2) * Precision * Recall / ( beta^2 * Precision + Recall )
    beta = 1   -> F1, balanced
    beta = 2   -> recall counts four times as much (misses hurt)
    beta = 0.5 -> precision counts four times as much (false alarms hurt)

Worked example

A model is evaluated on 100 cases. It produces TP = 40, FP = 10, FN = 20, TN = 30. Then:

• Accuracy = (40 + 30) / 100 = 0.70.
• Precision = 40 / (40 + 10) = 40 / 50 = 0.80.
• Recall = 40 / (40 + 20) = 40 / 60 = 0.67.
• F1 = 2(0.80 x 0.67) / (0.80 + 0.67) = 1.072 / 1.47 = 0.73.
• Specificity = TN / (TN + FP) = 30 / (30 + 10) = 0.75, so the false positive rate is 0.25.
• Balanced accuracy = (Recall + Specificity) / 2 = (0.67 + 0.75) / 2 = 0.71, which happens to be close to plain accuracy here because the classes are near balanced (60 positives, 40 negatives).

Worked example: why precision collapses on rare events

A screening test has sensitivity 0.99 and specificity 0.95, which sounds excellent. Apply it to 100,000 people where the disease prevalence is 0.5 percent, so 500 are truly sick.

• Step 1, true positives. 0.99 * 500 = 495 sick people correctly flagged. Five are missed.
• Step 2, false positives. There are 99,500 healthy people, and the false positive rate is 1 - 0.95 = 0.05, so 0.05 * 99,500 = 4,975 healthy people are flagged.
• Step 3, precision. PPV = 495 / (495 + 4,975) = 495 / 5,470 = 0.090. Fewer than one in ten flagged people actually has the disease.
• Step 4, accuracy, for contrast. (495 + 94,525) / 100,000 = 0.950. A model that simply declared everyone healthy would score 0.995, higher still, while catching nobody.
• Step 5, change the prevalence to 10 percent and redo it. TP = 0.99 * 10,000 = 9,900; FP = 0.05 * 90,000 = 4,500; PPV = 9,900 / 14,400 = 0.688.

What we just did: we held the classifier completely fixed and changed only the population, and precision moved from 0.09 to 0.69. Sensitivity and specificity did not budge, because they condition on the true class. This is the single most important quantitative fact in classifier evaluation, and it explains why a model validated on a balanced benchmark can be badly disappointing in deployment where positives are rare, and why reported precision figures are meaningless without the prevalence they were measured at.

Key idea: recall and specificity travel between populations; precision does not. Always report the base rate alongside precision.

Beyond two classes, and beyond F1

With K classes the confusion matrix becomes K by K, with correct predictions on the diagonal. Per-class precision and recall are computed one-versus-rest and then combined in one of three ways, and the choice materially changes the story:

• Macro averaging takes the unweighted mean across classes, so a rare class counts as much as a common one. Use it when small classes matter.
• Weighted averaging weights each class by its support, which is closer to overall accuracy and lets big classes dominate.
• Micro averaging pools all the TP, FP, and FN counts before computing, which in single-label multiclass problems equals accuracy exactly.

Two summary statistics deserve more use than they get. Balanced accuracy, the mean of recall across classes, is a simple fix for imbalance. The Matthews correlation coefficient (MCC) uses all four cells of the confusion matrix and produces a value in [-1, 1] that is high only when the model does well on both classes; unlike F1, it is not blind to true negatives and does not depend on which class you happened to call positive. Chicco and Jurman (2020) argue on these grounds that MCC should be preferred to F1 and accuracy as a default single-number summary for binary classification, and the argument is a good one.

MCC = (TP*TN - FP*FN) / sqrt( (TP+FP)(TP+FN)(TN+FP)(TN+FN) )
For TP=40, FP=10, FN=20, TN=30:
    numerator   = 40*30 - 10*20 = 1200 - 200 = 1000
    denominator = sqrt(50 * 60 * 40 * 50) = sqrt(6,000,000) = 2449.5
    MCC = 1000 / 2449.5 = 0.408

Note how much more sober 0.408 is than the F1 of 0.73 on the very same predictions. Both are defensible numbers; they weigh the four cells differently, and MCC's inclusion of the true negatives is why it is harder to impress.

The precision-recall tradeoff and imbalance

Precision and recall usually trade off. Lowering the decision threshold predicts positive more readily, catching more true positives (higher recall) but also raising false alarms (lower precision); raising the threshold does the reverse. You tune the threshold to match which error you fear more. This also exposes why accuracy misleads on imbalanced data: if only 1% of transactions are fraud, a lazy model that predicts "not fraud" for everything scores 99% accuracy while catching zero fraud (recall 0). Precision and recall reveal that failure instantly, which is why they, not raw accuracy, are the right tools for rare-event problems.

When the costs are actually known, you can do better than picking a metric: write down a cost matrix and choose the threshold that minimizes expected cost. If a missed fraud costs 500 and a false alarm costs 5 (in investigator time), then flag a transaction whenever 500 * p > 5 * (1 - p), which rearranges to p > 5/505 = 0.0099. The optimal threshold is 0.01, not 0.5, and no amount of arguing about F1 versus MCC substitutes for that calculation when the numbers are available. This also explains why the default 0.5 threshold is so often wrong: it is optimal only when the two errors cost the same and the model is well calibrated.

Where people get stuck

• "Precision and recall are just two views of the same thing." They have different denominators. Precision divides by what the model predicted positive; recall divides by what actually is positive. Say the denominator out loud and the confusion disappears.
• "Precision measured on a benchmark transfers to production." It does not, if the prevalence differs. Recall and specificity transfer; precision must be recomputed at the deployment base rate.
• "F1 is the neutral choice." F1 ignores true negatives entirely and changes value if you swap which class is called positive. Use MCC or balanced accuracy when you want a genuinely symmetric summary.
• "Improve the model to fix low recall." Often you just need a lower threshold. Check the precision-recall tradeoff at various thresholds before retraining anything.
• "Report one number." Report the confusion matrix. Every metric in this lesson is a lossy summary of those four counts, and different readers need different summaries.

Recap

• The confusion matrix holds TP, FP, FN, and TN, and every classification metric is a function of those four counts.
• Precision is TP/(TP+FP), recall is TP/(TP+FN), specificity is TN/(TN+FP), and F1 is the harmonic mean of precision and recall.
• Recall and specificity condition on the true class and transfer across populations; precision depends on prevalence and does not.
• On rare events a classifier with 99 percent sensitivity and 95 percent specificity can still have precision below 10 percent.
• Multiclass metrics need an averaging choice: macro treats classes equally, weighted favors large classes, micro equals accuracy.
• Balanced accuracy and MCC are more robust single-number summaries than accuracy or F1, and an explicit cost matrix beats all of them when the costs are known.

These metrics all describe a classifier at one chosen threshold. The final lesson steps back and asks how the model behaves across every threshold at once, which is the right question when you are comparing models rather than deploying one.

Sources

1. Powers, D. M. W. (2020). Evaluation: From precision, recall and F-measure to ROC, informedness, markedness and correlation. arXiv. arxiv.org
2. Chicco, D., & Jurman, G. (2020). The advantages of the Matthews correlation coefficient (MCC) over F1 score and accuracy in binary classification evaluation. BMC Genomics, 21(1), 6. bmcgenomics.biomedcentral.com
3. Saito, T., & Rehmsmeier, M. (2015). The precision-recall plot is more informative than the ROC plot when evaluating binary classifiers on imbalanced datasets. PLOS ONE, 10(3), e0118432. journals.plos.org
4. Raschka, S. (2018). Model evaluation, model selection, and algorithm selection in machine learning. arXiv. arxiv.org
5. scikit-learn developers. (n.d.). Metrics and scoring: Quantifying the quality of predictions. scikit-learn user guide. scikit-learn.org
6. scikit-learn developers. (n.d.). Precision-recall. scikit-learn examples. scikit-learn.org
7. Google. (n.d.). Classification: Accuracy, recall, precision, and related metrics. Machine learning crash course. developers.google.com

Precision and recall describe a classifier at one decision threshold. But a probabilistic classifier offers a whole family of behaviors as you slide the threshold from strict to lenient. The ROC curve summarizes that entire family in one picture, and its area under the curve distills it to a single threshold-independent score.

The big picture

Every metric in the last lesson required you to have already committed to a threshold, which creates an awkward ordering problem. You cannot sensibly pick a threshold until you know which model you are deploying, and you cannot compare models on precision and recall until you have picked a threshold for each. The ROC curve resolves the deadlock by evaluating a model at every threshold simultaneously, producing a picture of the entire tradeoff and a single summary number that no longer depends on the choice.

The name is a historical curiosity worth knowing. ROC analysis was developed by radar operators during the Second World War, who faced exactly this problem: turn the receiver's sensitivity up and you detect more incoming aircraft but also more flocks of birds. The framework moved into signal detection theory, then into radiology in the 1970s, and then into machine learning, which is why the vocabulary mixes engineering, medicine, and statistics.

Key idea: a probabilistic classifier is not one classifier but a family, one per threshold. The ROC curve describes the whole family, and AUC scores how well the model ranks, independent of where you cut.

Building the ROC curve

The receiver operating characteristic (ROC) curve plots two rates against each other as the threshold varies:

True Positive Rate  (TPR, = recall) = TP / (TP + FN)   # y-axis
False Positive Rate (FPR)           = FP / (FP + TN)   # x-axis

At a very strict threshold the model predicts positive almost never, so both TPR and FPR are near 0 (bottom-left). At a very lenient threshold it predicts positive almost always, so both approach 1 (top-right). Sweeping the threshold traces a curve between these corners. The ideal is to climb toward high TPR while keeping FPR low, so a curve that bows toward the top-left corner is better.

In practice the curve is not drawn from a continuum of thresholds but from the finitely many that matter: sort the examples by score and step the threshold down through them one at a time. Each positive encountered moves the curve up by 1 / n_pos; each negative moves it right by 1 / n_neg. The ROC curve is therefore a staircase with exactly one step per example, and the whole construction takes one sort.

Worked example: building an ROC and computing AUC two ways

Eight test examples, four positive and four negative, with model scores:

sorted by score, highest first:
  0.95 P   0.80 P   0.70 N   0.55 P   0.45 N   0.35 N   0.30 P   0.10 N
n_pos = 4, so each P raises TPR by 0.25;  n_neg = 4, so each N raises FPR by 0.25

• Step 1, walk the list from the top, starting at (FPR, TPR) = (0, 0). The two P's take us to (0, 0.25) then (0, 0.50). The N at 0.70 moves right to (0.25, 0.50). The P at 0.55 goes up to (0.25, 0.75). The N's at 0.45 and 0.35 move right to (0.50, 0.75) and (0.75, 0.75). The P at 0.30 goes up to (0.75, 1.00), and the last N finishes at (1.00, 1.00).
• Step 2, area by geometry. Only the rightward moves contribute area, each a rectangle of width 0.25 and height equal to the current TPR: 0.25*0.50 + 0.25*0.75 + 0.25*0.75 + 0.25*1.00 = 0.125 + 0.1875 + 0.1875 + 0.25 = 0.75.
• Step 3, area by counting pairs. There are 4 * 4 = 16 positive-negative pairs. The 0.95 and 0.80 positives outrank all four negatives, contributing 8. The 0.55 positive outranks 0.45, 0.35, and 0.10 but loses to 0.70, contributing 3. The 0.30 positive outranks only 0.10, contributing 1. Total 12, and 12 / 16 = 0.75.
• Step 4, note the agreement. The two routes must agree, because the area under the staircase literally counts correctly ordered pairs.

What we just did: we established the identity that makes AUC interpretable. AUC equals the probability that a randomly chosen positive is scored above a randomly chosen negative, which is the Mann-Whitney U statistic in disguise. It follows that AUC depends only on the ranking of the scores, not their values. Squaring every score, or passing them all through any increasing function, leaves AUC completely unchanged. Hold on to that fact; it has a sharp consequence three sections down.

Area under the curve (AUC)

The single most useful summary is the AUC, the area under the ROC curve, ranging from 0 to 1:

• AUC = 1.0: a perfect classifier that ranks every positive above every negative.
• AUC = 0.5: no better than random guessing (the diagonal chance line).
• AUC below 0.5: worse than chance (its predictions are anti-correlated with truth).

AUC has a clean interpretation: it is the probability that the model assigns a higher score to a randomly chosen positive example than to a randomly chosen negative one. In other words, AUC measures how well the classifier ranks positives above negatives, independent of any particular threshold.

A model with AUC below 0.5 is not useless; it is informative and wired backwards, and flipping its sign gives AUC = 1 - original. In credit scoring the same quantity is often reported as the Gini coefficient, defined as 2 * AUC - 1, so an AUC of 0.75 is a Gini of 0.50. And because AUC is estimated from a finite sample it carries sampling error: with a few dozen positives its standard error can easily exceed 0.05, so a difference of 0.01 between two models means nothing without a paired comparison. The DeLong test is the standard way to compare two AUCs computed on the same test set.

The consequence of rank invariance: AUC says nothing about calibration

Since AUC depends only on ordering, a model that outputs 0.90 for every positive and 0.85 for every negative has an AUC of 1.0 despite its probabilities being badly wrong in absolute terms. So does a model outputting 0.05 and 0.02. Perfect discrimination, useless probabilities. If you plan to threshold at an expected-cost cutoff (Lesson 17) or feed the probability into a downstream calculation, you need calibration as well as discrimination, and you must measure it separately: plot a reliability curve, or compute the Brier score, the mean squared error between predicted probabilities and outcomes. Post-hoc correction by Platt scaling or isotonic regression fixes calibration while leaving AUC untouched, precisely because those corrections are monotone.

When to use which

Because AUC is threshold-independent, it is ideal for comparing models overall and for judging ranking quality. Single-threshold metrics like precision and recall are what you report once you have committed to an operating threshold for deployment. One caution: on heavily imbalanced data, ROC curves can look optimistic because a large true-negative count keeps FPR low, so a precision-recall curve often tells a more honest story for rare-positive problems. The disciplined workflow is to compare candidate models by AUC, then choose the threshold that balances precision and recall for your costs, and finally report both on the untouched test set.

The imbalance objection deserves numbers, because it is easy to state and easy to underestimate. Suppose 1,000,000 transactions contain 1,000 frauds. A model flags 900 of the frauds (TPR = 0.90) and also flags 20,000 of the 999,000 legitimate transactions. The false positive rate is 20,000 / 999,000 = 0.020, which plots as a point very close to the top-left corner and contributes to a flattering AUC. But precision at that operating point is 900 / 20,900 = 0.043: an investigator following up on flags is wasting time on 23 clean transactions for every fraud found. The ROC curve did not lie, it simply reported a ratio whose denominator, the 999,000 negatives, is so large that a substantial absolute number of false positives still looks like a small rate.

The precision-recall curve plots precision against recall instead, so the vast pool of true negatives never enters the denominator, and its summary statistic is average precision (the area under it). Its baseline is not 0.5 but the positive class prevalence, 0.001 in the example above, so a model must beat 0.001 rather than 0.5 to be doing anything. Saito and Rehmsmeier (2015) demonstrated across simulated and real datasets that ROC plots can appear nearly identical for models whose PR plots differ dramatically on imbalanced data. The rule of thumb: report ROC-AUC when both classes matter roughly equally, and report average precision when the positive class is rare and the cost of a false alarm is borne per flag.

Choosing an operating point from the curve

The curve is also how you pick the threshold, and there are three defensible ways to do it:

• Youden's J statistic, maximize TPR - FPR, which selects the point farthest above the chance diagonal. This is the right default when the two errors cost about the same.
• Constraint-driven: fix the tolerable false positive rate (or the required recall) from operational limits, such as how many alerts a team can process per day, and read the threshold off the curve.
• Cost-driven: minimize expected cost using an explicit cost matrix, as in Lesson 17. This dominates the others whenever the costs are actually known.

Whichever you use, choose the threshold on validation data, not on the test set, and remember that the optimal threshold depends on prevalence. If deployment prevalence differs from your validation set, the threshold must be revisited.

For multiclass problems, AUC generalizes by one-versus-rest (one curve per class, then macro or weighted averaging) or one-versus-one (a curve per class pair). Macro averaging treats rare classes as equal citizens, weighted averaging lets the common classes dominate, and the choice should follow the same reasoning as for macro versus weighted F1.

Where people get stuck

• "AUC 0.85 means 85 percent accuracy." It means that 85 percent of positive-negative pairs are correctly ordered. Accuracy at any given threshold could be much higher or much lower.
• "High AUC means the probabilities are trustworthy." AUC is rank-invariant and therefore blind to calibration. Check a reliability curve or the Brier score before using a probability as a probability.
• "ROC handles imbalance fine." The FPR denominator is the whole negative pool, so a large absolute number of false positives can still be a small rate. Use a precision-recall curve for rare positives.
• "Model A has AUC 0.842 and model B has 0.838, so A wins." Not without a confidence interval or a paired test. AUC has real sampling variability, especially with few positives.
• "Pick the threshold that maximizes accuracy." That silently assumes the two errors cost the same, which is exactly the assumption Module 7 exists to question.

Recap

• The ROC curve plots true positive rate against false positive rate as the decision threshold sweeps through the scores.
• It is a staircase with one step per test example, built from a single sort, and bowing toward the top-left is better.
• AUC equals the probability that a random positive is ranked above a random negative, so 0.5 is chance and 1.0 is perfect ranking.
• Because AUC depends only on ranking, it is unchanged by any monotone transformation of the scores and therefore says nothing about calibration.
• On heavily imbalanced data ROC curves look optimistic; the precision-recall curve and average precision, whose baseline is the prevalence, are more informative.
• Choose the operating point on validation data using Youden's J, an operational constraint, or an explicit cost matrix, then report threshold metrics on the sealed test set.

This closes the loop that opened in Lesson 1. You formalized a task, chose a hypothesis class and a loss, trained by descending a gradient, controlled variance with regularization and cross-validation, and can now evaluate the result honestly enough to defend it. That last step is not the least important one; it is what makes the rest trustworthy.

Sources

1. Fawcett, T. (2006). An introduction to ROC analysis. Pattern Recognition Letters, 27(8), 861-874. ccrma.stanford.edu
2. Hanley, J. A., & McNeil, B. J. (1982). The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology, 143(1), 29-36. find source ↗
3. Saito, T., & Rehmsmeier, M. (2015). The precision-recall plot is more informative than the ROC plot when evaluating binary classifiers on imbalanced datasets. PLOS ONE, 10(3), e0118432. journals.plos.org
4. Niculescu-Mizil, A., & Caruana, R. (2005). Predicting good probabilities with supervised learning. Proceedings of the 22nd International Conference on Machine Learning, 625-632. cs.cornell.edu
5. scikit-learn developers. (n.d.). Metrics and scoring: Quantifying the quality of predictions. scikit-learn user guide. scikit-learn.org
6. scikit-learn developers. (n.d.). Multiclass receiver operating characteristic (ROC). scikit-learn examples. scikit-learn.org
7. Google. (n.d.). Classification: ROC and AUC. Machine learning crash course. developers.google.com