Introduction to Machine Learning

Session 1: Foundations, Nearest Neighbors & Linear Prediction

David Picard

2026-09-21

Welcome

Session 1: Agenda

8:30–11:35 · 185 min

Time Block
8:30–9:10 What is ML? · Formal setting · ERM
9:10–9:15 ⚡ Exercise 1: ERM failure
9:15–9:25 Generalization & PAC bound
9:25–10:00 1-NN & k-NN (incl. Cover–Hart theorem)
10:00–10:10 Model selection (cross-validation, test set)
10:10–10:20 ☕ Break
10:20–10:35 PAC-learnability · Bridge to Chapter 2
10:35–11:05 PCA · Bluebell examples & reconstruction
11:05–11:20 Linear regression (incl. interactive fit)
11:20–11:30 💻 Coding lab: k-NN + cross-validation
11:30–11:35 Wrap-up & next session

What is Machine Learning?

Le savant n’étudie pas la nature parce que cela est utile ; il l’étudie parce qu’il y prend plaisir et il y prend plaisir parce qu’elle est belle.

— Henri Poincaré, Science et Méthode (1908)

It is that the sciences do not try to explain, they hardly even try to interpret, they mainly make models. […] The justification of such a mathematical construct is solely and precisely that it is expected to work.

— John von Neumann, Method in the Physical Sciences (1955)

An informal definition

Machine Learning is the art of automating the creation of models from data such that they make accurate predictions.

  • No requirement to understand or explain, only to predict accurately
  • The model comes from data, not human intuition
  • Tension between data and human intuition (inductive bias) will recur throughout the course

Formal Setting

0:10–0:25 · 15 min

Random variables, predictors, loss

Consider a pair of random variables \((x, y)\) with unknown joint probability \(P(x, y)\). We seek \(f\) such that \(f(x) \approx y\).

0-1 loss. For a prediction \(f(x)\) and target \(y\), \[ \ell(f(x), y) = 0 \text{ iff } f(x) = y, \text{ else } 1. \]

True risk & Bayes error

True risk. \(\displaystyle \mathcal{R}_f = \mathbb{E}[\ell(f(x), y)] = \int \ell(f(x), y)\, dP(x, y)\)

Bayes error. \(\displaystyle \mathcal{R}_{\min} = \mathbb{E}\big[\ell(\arg\max_z P(x, z), y)\big]\), the irreducible error.

  • \(\mathcal{R}_f\) is not computable: \(P(x,y)\) is unknown
  • \(\mathcal{R}_{\min}\) is the best any predictor can do

Determinism proposition

\(\mathcal{R}_{\min} = 0\) if and only if the process \(x \mapsto y\) is deterministic, i.e. \(\forall z \neq y,\ P(x, z) = 0\).

Proof sketch: split the expectation on whether \(\arg\max_z P(x,z) = y\); the non-deterministic case forces a strictly positive integral unless \(P(x,z)=0\) for all \(z \neq y\).

Empirical Risk Minimization

0:25–0:40 · 15 min

From an abstract risk to a computable one

Given a dataset \(\mathcal{A} = \{(x_i, y_i)\}_{i \leq n}\) sampled i.i.d. from \(P(x,y)\):

Empirical risk. \(\displaystyle \hat{\mathcal{R}}_{\mathcal{A}}(f_\theta) = \frac{1}{n}\sum_{(x,y)\in\mathcal{A}} \ell(f_\theta(x), y)\)

The empirical risk is an unbiased and consistent estimator of the true risk: \(\mathbb{E}[\hat{\mathcal{R}}_{\mathcal{A}}(f_\theta)] = \mathcal{R}_f\) and \(\hat{\mathcal{R}}_{\mathcal{A}}(f_\theta) \to \mathcal{R}_f\) as \(n \to \infty\).

The ERM principle

Empirical Risk Minimization (ERM). Given \(\{f_\theta\}_{\theta \in \Theta}\) and \(\mathcal{A}\), return \(f_{\theta^\star}\) with \[ \theta^\star = \arg\min_{\theta \in \Theta} \hat{\mathcal{R}}_{\mathcal{A}}(f_\theta). \]

  • Purely data-driven: only assumes \(P(x,y)\) exists and can be sampled
  • Guaranteed in the limit to match the true risk of the chosen \(f_\theta\)

Inductive bias

Inductive bias. The set of assumptions, prior knowledge, or preferences that a learning algorithm uses in addition to data.

  • Restricting \(\Theta\) (the search space) is already an inductive bias
  • Strictly speaking: no ML algorithm is bias-free (choosing \(x, y\) already assumes something), but we reserve the term for strong constraints
  • This trade-off (data vs. bias) returns in every chapter

Exercise 1

0:40–0:45 · 5 min

⚡ ERM failure example

Construct a toy hypothesis class and dataset where the empirical risk is zero but the true risk is large. Make the overfitting gap explicit and explain which assumption of ERM it violates.

Format: 4 min work + 1 min share-out.

Generalization & the PAC Bound

0:45–0:55 · 10 min

The generalization gap

Generalization gap. \(\displaystyle \Gamma_f = \mathcal{R}_f - \hat{\mathcal{R}}_{\mathcal{A}}(f)\).

  • Abstract (uses the incomputable \(\mathcal{R}_f\)) but central theoretically
  • Goal: bound \(\Gamma_f\) using only the size of \(\mathcal{A}\) (and maybe the algorithm’s properties)

A first PAC bound

Under the realizability assumption (\(\exists h^\star \in \mathcal{H},\ \mathcal{R}_{h^\star} = 0\)):

PAC generalization bound. For finite \(\mathcal{H}\), \(\delta, \varepsilon > 0\), and \(m \geq \frac{\ln(|\mathcal{H}|/\delta)}{\varepsilon}\), ERM on \(m\) samples yields \(h_{\mathcal{A}}\) with \[ P[\Gamma_{h_{\mathcal{A}}} > \varepsilon] \leq \delta. \]

  • Union bound over “misleading” datasets (proof in the book)
  • Numeric reality check: \(64\times64\) RGB template predictor \(\Rightarrow |\mathcal{H}| = 2^{64\times64\times24}\), needs \(m \approx 6.8\)M samples for \(1\%\) error at \(99\%\) confidence, already impractical

1-Nearest Neighbor

0:55–1:15 · 20 min

The nearest neighbor rule

Assumption: \(\mathcal{X}\) is endowed with a distance \(\|x - x'\|\) and nearby \(x\) share the same \(y\).

1-NN prediction. Given \(\mathcal{A} = \{(x_i,y_i)\}\) and query \(x\): compute \(\mathbf{d} = [\|x-x_1\|, \dots, \|x-x_n\|]\), find \(i = \arg\min_j \mathbf{d}_j\), return \(\hat{y} = y_i\).

  • “Learning” = memorizing \(\mathcal{A}\), the model is the training set
  • Decision regions are the Voronoi cells of \(\mathcal{A}\), colored by class

Voronoi decision regions

1-NN on the 2D toy example of the book

Cover–Hart generalization theorem

Nearest-neighbor convergence. Under mild continuity conditions on \(p\), the nearest neighbor \(x_n'\) of \(x\) among \(n\) i.i.d. samples converges to \(x\) almost surely as \(n \to \infty\).

1-NN generalization (Cover & Hart, 1967). As \(n \to \infty\), \[ \mathcal{R}^\star \leq \mathcal{R} \leq 2\mathcal{R}^\star(1 - \mathcal{R}^\star), \] with \(\mathcal{R}^\star\) the Bayes error.

Cover–Hart, proof sketch

  • Pointwise error \(r(x, x_n') \to r(x) = 2p_1(x)(1-p_1(x))\) a.s. (using the convergence lemma + continuity)
  • Lower bound: \(r^\star(x) \le 1/2 \Rightarrow \mathcal{R} \geq \mathbb{E}[r^\star(x)] \geq \mathcal{R}^\star\)
  • Upper bound: expand \(\mathcal{R} = 2\mathcal{R}^\star - 2\mathbb{E}[r^\star(x)^2]\), use \(\mathrm{Var}(r^\star(x)) \geq 0\)
  • Takeaway: if the process is deterministic (\(\mathcal{R}^\star = 0\)), 1-NN is asymptotically perfect, “learning = memorizing” in this limit (link to representer theorems, later in the course)

k-Nearest Neighbor

1:15–1:30 · 15 min

From 1 to k neighbors

\(k\)-NN prediction. Rank samples by distance to \(x\), take the \(k\) nearest \(\mathcal{N}\), return the majority class \(\arg\max_j \sum_{(x_i,y_i)\in\mathcal{N}} \delta_{y_i,j}\).

  • More neighbors \(\Rightarrow\) smoother, more robust decision boundary
  • Isolated / mislabeled points contribute less as \(k\) grows
  • Can have strange non-local effect

Effect of k

\(k\)-NN on the same 2D toy dataset, for variable \(k\)

Choosing k

  • Not an ERM problem: it compares across families, and \(k=1\) always has \(\hat{\mathcal{R}}_{\mathcal{A}} = 0\), it always “wins” trivially
  • \(\Rightarrow\) use cross-validation to pick \(k\) (= another dataset)
  • Ties (e.g. \(k=1\) vs \(k=21\)) broken by simplicity / robustness to outliers
  • Using another dataset to select a model biases its evaluation

Model Selection

1:30–1:40 · 10 min

Cross-validation

How do we select the right model?

  • ERM \(\Rightarrow\) consumes data to optimize a model
  • Selecting a model (hyper parameters) also consumes data
  • Data used for one cannot be used for the other

\(K\)-fold CV. Split \(\mathcal{A}\) into \(K\) folds; for each fold, train on the rest, validate on it; average the \(K\) errors.

Random-split CV. Repeat \(K\) times: random train/validation split with ratio \(r\); average the errors. (Controls training-set size, reuses samples.)

Leave-one-out & the test set

What about the performances of the model?

  • Leave-one-out (LOO): \(K = |\mathcal{A}|\), costly but informative, has a dedicated generalization bound (uniform stability, Bousquet & Elisseeff 2002)
  • Using validation data for model selection contaminates that estimate
  • \(\Rightarrow\) three disjoint sets: train (ERM) / validation (model selection, hyper-parameters) / test (final estimate)
  • Reusing data across roles \(\Rightarrow\) overfitting

Break

1:40–1:50 · 10 min

☕ 10-minute break

Back at 10:20 for PAC-learnability and Chapter 2.

PAC-Learnability

1:50–2:00 · 10 min

Definition

PAC-learnability. \(\mathcal{H}\) is PAC-learnable if for every \(\varepsilon, \delta > 0\) and every distribution \(\mathcal{D}\), there exists an algorithm \(A\) and sample complexity \(m(\varepsilon,\delta,\mathcal{D})\) such that running \(A\) on \(m\) samples returns \(h\) with \(\mathcal{R}_h \leq \mathcal{R}_{h^\star} + \varepsilon\) with probability \(1-\delta\).

  • Two questions: what is learnable, and how efficiently (sample complexity vs. rates)

Fundamental theorem of PAC learning

(Simplified.) For \(\mathcal{H} \subseteq \{\mathcal{X}\to\{0,1\}\}\) under the 0-1 loss, the following are equivalent:

  1. \(\mathcal{H}\) has the uniform convergence property
  2. \(\mathcal{H}\) is PAC learnable
  3. Any ERM rule is a successful PAC learner for \(\mathcal{H}\)
  4. \(\mathcal{H}\) has finite VC dimension
  • VC dimension is formally introduced in Chapter 4, for now, learnability, ERM success, and a finite “capacity” measure all coincide
  • No proof today (needs VC dimension + uniform convergence machinery)

Chapter 2 - Preview

2:00–2:05 · 5 min

From abstract risk to concrete models

  • So far: any \(f_\theta\), abstract risk, generic guarantees
  • Now: a first real family, linear predictors \(h(x) = \langle w, x\rangle\)
  • Running task for the rest of the course: the Bluebell dataset, 1800 64² px images, classified into 12 flower classes

Principal Component Analysis

2:05–2:35 · 30 min

Motivation: compression & reconstruction

Is there a low-dimensional subspace of \(\mathcal{X}\) that captures almost all the information in \(x \in \mathcal{X}\)?

Given \(\mathcal{A} = \{x_i \in \mathbb{R}^d\}\), find \(w \in \mathbb{R}^{d}\), \(\|w\|^2=1\), minimizing the empirical reconstruction risk \[ \mathcal{L}(w) = \frac{1}{n}\sum_i \|x_i - ww^\top x_i\|^2. \]

From reconstruction to an eigenproblem

Equivalent to \(\max_w w^\top \Sigma w\) s.t. \(\|w\|^2=1\), with \(\Sigma = \frac1n\sum_i x_i x_i^\top\).

The solution is the eigenvector of \(\Sigma\) with the largest eigenvalue (Lagrangian \(\Rightarrow \Sigma w = \lambda w\); or Rayleigh quotient argument).

  • Subtract the mean first \(\Rightarrow \Sigma\) becomes the empirical covariance \(\Rightarrow\) this is PCA: the direction of maximal variance
  • Higher target dimension: iterate on the residuals

PCA in action

The Bluebell dataset

One example from each of the 12 Bluebell classes

Principal components of Bluebell

Mean and the first 7 principal directions of the (pixel-space) Bluebell dataset. Percentages: fraction of total variance explained.

PC1 alone already carries ~15% of the variance (roughly the “green background vs. flower blob” contrast)

Bluebell reconstruction

Each reconstruction is \(\hat{x} = \mu + \sum_{i \leq k} \text{coeff}_i \cdot \text{component}_i\), up to 64 principal directions

Linear Regression

2:35–2:50 · 15 min

Setup & loss

Supervised version: \(\mathcal{A} = \{(x_i, y_i)\}\), \(x_i \in \mathbb{R}^d\), \(y_i \in \mathbb{R}\). \[ \mathcal{L}(w) = \frac1n \sum_i \|y_i - w^\top x_i\|^2 \]

Empirical risk: reconstruction of \(y\) from linear projection of \(x\)

Closed-form solution

Matrix form: \(\mathcal{L}(w) = \|Y - Xw\|^2\). Setting \(\partial \mathcal{L}/\partial w = 0\):

Moore–Penrose solution. If \(X^\top X\) is invertible, \[ w = (X^\top X)^{-1} X^\top Y. \]

  • Two practical issues: (1) \(X^\top X\) must be full rank, PCA can help by compressing first; (2) inverting is expensive at scale (\(64\times64\times3\) Bluebell images \(\approx 12\)k dims, inversion has \(d^3\) complexity)
  • \(\Rightarrow\) SGD as a fallback

Linear regression as a classifier

Same synthetic dataset as the 1-NN/\(k\)-NN slides. Regress the label mapped to \(t=\pm1\) on \((x_1,x_2)\) with a bias column, color the background by \(\mathrm{sign}(w^\top x + b)\), and draw that zero level set (solid bordeaux)

Coding Lab

2:50–3:00 · 10 min

💻 k-NN + cross-validation

  1. Implement predict(A, x, k) for \(k\)-NN (vectorized distances, knearestneighbor.py as a reference/starting point).
  2. On the provided 2D synthetic dataset, run 5-fold CV for \(k \in \{1, 3, 5, 7, 11, 15, 21\}\).
  3. Plot mean \(\pm\) std CV error vs. \(k\). Pick a \(k\) and justify your choice without looking at the held-out test set.
  4. Compare to the \(1\)-NN / \(21\)-NN tie discussed earlier

Format: individual or pairs, work at own pace; walk the room for questions.

Wrap-up

3:00–3:05 · 5 min

Recap

  • ML \(=\) ERM on data, but ERM alone doesn’t tell us how well we’ll generalize \(\Rightarrow\) generalization bounds, cross-validation, test sets
  • 1-NN / \(k\)-NN: the simplest non-parametric learners, with real generalization guarantees (Cover–Hart)
  • PCA and linear regression: first linear models

Next session

  • Finish Chapter 2: linear classification, generalized linear models (polynomial & periodic maps), regularization (LASSO, Ridge)
  • All of Chapter 3 Kernels and representer theorems, SVMs.