Machine Learning from First Principles

Chapter 1 · Part I: Foundations

What Is Machine Learning?

Instead of writing the rules of a program by hand, we write a program that finds the rules from examples. This chapter sets up the vocabulary for everything that follows.

After this chapter you will be able to

  • Define machine learning in terms of a task, experience, and a performance measure.
  • Distinguish supervised, unsupervised, self-supervised, and reinforcement learning.
  • Write down the supervised learning problem: data, model, loss, and empirical risk.
  • Explain why we evaluate on held-out data and what generalization means.
  • Name the four ingredients shared by every method in this book.

1.1Programs That Learn from Data

Suppose you must write a program that decides whether an email is spam. A rule list ("flag messages containing free money") catches some spam, wrongly flags some real mail, and breaks as soon as spammers adapt. Machine learning instead collects thousands of emails that people have already labeled and writes a program that finds a good rule from them. When spammers change tactics, we collect new examples and run the program again.

Definition 1.1 (Machine learning, Mitchell 1997)

A program learns from experience $E$ with respect to tasks $T$ and performance measure $P$ if its performance at $T$, as measured by $P$, improves with $E$.

For the spam filter: $T$ is labeling emails, $E$ is a set of labeled emails, and $P$ is the fraction of new emails labeled correctly. Naming $T$, $E$, and $P$ explicitly is the first step of every project in this book.

Intuition: learning is fitting plus generalizing

A learning program fits: it adjusts internal knobs so its outputs agree with the examples it has seen. And, if it is any good, it generalizes: it also gives sensible outputs on examples it has never seen. Fitting alone is easy (memorize the examples). Generalizing is the hard part.

1.2Kinds of Learning

KindExperienceExample
Supervisedinputs with labelspredict a house price (regression) or whether an email is spam (classification)
Unsupervisedinputs onlygroup customers by purchasing behavior; find a few directions that explain the data
Self-supervisedinputs only; labels made by hiding part of each inputpredict the next word of a sentence, the way language models are trained
Reinforcementactions, observations, rewardslearn to play a game from its score

If a supervised label is a real number the problem is regression; if it is one of finitely many categories it is classification. Chapters 4–9 cover supervised learning, Chapters 10–11 unsupervised learning, and Chapters 15–17 self-supervised and reinforcement learning.

1.3The Supervised Learning Setup

Data. A training set $\Data = \{(\vx^{(i)}, y^{(i)})\}_{i=1}^n$ with inputs $\vx^{(i)}\in\R^d$ (a vector of $d$ features) and labels $y^{(i)}$. We assume the pairs are independent and identically distributed (i.i.d.) draws from an unknown distribution $p(\vx, y)$. That assumption is what lets past examples say something about future ones, and it is the assumption most often violated in practice.

Model. A function $f_{\vtheta}$ with adjustable parameters $\vtheta$. The set of functions reachable by changing $\vtheta$ is the hypothesis class, for example all linear models $f(\vx) = \vw\T\vx + b$.

Loss. A function $\ell(\hat y, y)$ measuring how bad prediction $\hat y$ is when the truth is $y$: squared error $(\hat y - y)^2$ for regression, or the 0–1 loss $\mathbb 1[\hat y\neq y]$ for classification.

Risk. What we care about is the expected loss on new data, the true risk; what we can compute is the average loss on the training data, the empirical risk:

$$R(\vtheta) = \E_{(\vx,y)\sim p}\big[\ell(f_{\vtheta}(\vx), y)\big], \qquad \hat R(\vtheta) = \frac1n\sum_{i=1}^n\ell\big(f_{\vtheta}(\vx^{(i)}), y^{(i)}\big). \tag{1.1, 1.2}$$

Key idea: empirical risk minimization

Choose $\hat\vtheta = \argmin_{\vtheta}\hat R(\vtheta)$ and hope $R(\hat\vtheta)$ is also small. For any fixed $\vtheta$, $\hat R\to R$ as $n\to\infty$ by the law of large numbers. The subtlety, studied in Chapter 5, is that $\hat\vtheta$ was chosen because it does well on the training set.

1.4A First Example: Fitting a Line

With one feature $x$ and the class of lines $f(x) = wx + b$, the empirical risk under squared error is the mean squared error:

$$\mathrm{MSE}(w,b) = \frac1n\sum_{i=1}^n\big(wx^{(i)} + b - y^{(i)}\big)^2. \tag{1.3}$$

Each term squares a residual: the vertical gap between a point and the line. Try minimizing it yourself.

After a minute you will find yourself tilting and shifting the line in whichever direction lowers the error. That strategy is gradient descent (Chapter 3). For this problem we can also set both partial derivatives to zero and solve exactly:

Show derivation
$$\pd{\mathrm{MSE}}{b} = \frac2n\sum_i\big(wx^{(i)} + b - y^{(i)}\big) = 0 \;\Rightarrow\; b = \bar y - w\bar x,$$ $$\pd{\mathrm{MSE}}{w} = \frac2n\sum_i\big(wx^{(i)} + b - y^{(i)}\big)x^{(i)} = 0.$$

Substitute $b$ into the second equation: $\sum_i\big(w(x^{(i)}-\bar x) - (y^{(i)}-\bar y)\big)x^{(i)} = 0$. Because $\sum_i (x^{(i)}-\bar x)\bar x = 0$, we can replace $x^{(i)}$ by $x^{(i)}-\bar x$ and solve for $w$.

$$\hat w = \frac{\sum_i (x^{(i)}-\bar x)(y^{(i)}-\bar y)}{\sum_i (x^{(i)}-\bar x)^2}, \qquad \hat b = \bar y - \hat w\bar x. \tag{1.4}$$

The slope is the sample covariance of $x$ and $y$ divided by the sample variance of $x$, and the line passes through $(\bar x, \bar y)$.

import numpy as np

rng = np.random.default_rng(0)
x = rng.uniform(0, 10, size=30)
y = 1.2 + 0.6 * x + rng.normal(0, 0.9, size=30)   # true line plus noise

w = np.sum((x - x.mean()) * (y - y.mean())) / np.sum((x - x.mean())**2)
b = y.mean() - w * x.mean()
mse = np.mean((w * x + b - y)**2)
print(f"w = {w:.3f}, b = {b:.3f}, MSE = {mse:.3f}")   # close to 0.6 and 1.2

1.5Generalization and the Test Set

A polynomial of degree $n-1$ passes exactly through $n$ training points, so its training error is zero, but between the points it swings wildly and predicts new data terribly. This is overfitting. The only honest estimate of performance on new data comes from data the model has never seen:

  1. Before anything else, randomly split the data into a training set (often 60–80%) and a test set.
  2. Fit the model on the training set only.
  3. Report the loss on the test set.

Choices such as the polynomial degree or the learning rate are made on a separate validation set carved out of the training data. The test set is used once, at the end.

Pitfall: peeking at the test set

Every time you look at test performance and change something in response, information about the test set leaks into the model. If you tried twenty variants and report the best test score, that score is optimistic. Make all decisions on validation data.

The difference between test and training error is the generalization gap. Regularization (Chapter 5) and data augmentation (Chapter 16) are tools for keeping it small.

1.6The Ingredients of Every ML Method

IngredientQuestion it answers
DataWhat examples do we learn from, and how were they collected?
ModelWhich family of functions do we search over?
LossHow do we measure a bad prediction?
OptimizerHow do we search the family for a low-loss member?

Linear regression: input–output pairs, a linear model, squared error, and a closed-form solution. A large language model: trillions of words, a Transformer, next-word cross-entropy, and a variant of Adam. Same ingredients, different scale.

1.7A Short History

Least squares was published by Legendre in 1805 and used by Gauss to track the asteroid Ceres. Rosenblatt built the perceptron in 1958. Backpropagation for multilayer networks was popularized in 1986. Support vector machines, tree ensembles, and probabilistic models dominated the 1990s and 2000s. Around 2012 a deep convolutional network trained on GPUs sharply cut the error on the ImageNet benchmark, and since then larger data sets, faster hardware, and architectures that keep improving with scale have reinforced each other. The Transformer (2017) led to today's large language models, and diffusion models did the same for image generation.

The four ingredients have not changed. If you understand least squares, gradient descent, and maximum likelihood, you already understand the core of a modern language model.

1.8Summary

  • A program learns if its performance $P$ on task $T$ improves with experience $E$.
  • Supervised, unsupervised, self-supervised, and reinforcement learning differ in the experience they use.
  • Supervised learning minimizes the empirical risk in the hope of a low true risk.
  • The least-squares line has slope $\widehat{\Cov}(x,y)/\widehat{\Var}(x)$ and passes through $(\bar x,\bar y)$.
  • Evaluate on a test set never used for decisions; decide on a validation set.
  • Every method combines data, a model, a loss, and an optimizer.

1.9Exercises

  1. ConceptualIdentify $T$, $E$, $P$, and the kind of learning for: (a) recommending movies; (b) detecting credit-card fraud; (c) a chess program that learns by playing itself; (d) grouping news articles by topic.
  2. ConceptualModel A has training MSE 0.02 and test MSE 3.1. Model B has 0.9 and 1.0. Which would you deploy, and what does each pair suggest?
  3. MathComplete the derivation of Equation (1.4).
  4. MathShow that the residuals of the least-squares line sum to exactly zero.
  5. MathFor the constant model $f(x)=c$ under absolute error $|\hat y-y|$, show that any median of the labels minimizes the empirical risk. What minimizes it under squared error?
  6. CodingGenerate 20 points from $y=\sin x+\varepsilon$, $x\in[0,6]$, $\varepsilon\sim\Normal(0,0.1^2)$. Fit polynomials of degree 1, 3, and 15 with np.polyfit and compare training MSE with MSE on 1000 fresh points.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.