Machine Learning

Contents

• Introduction and overview
• 0. Review: optimization, concentration and information tools
• 1. The statistical framework of learning
• 2. Linear regression and regularization
• 3. Classification: logistic regression and SVM
• 4. Evaluation, big data and pipelines
• 5. Kernels and RKHS
• 6. Trees, forests, boosting
• 7. Unsupervised: k-means, EM, PCA
• 8. Generalization theory
• 9. Research at CMAP and LIX (Le Pennec, Read)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: engineer who already fitted a sklearn model / MNIST-like MLP and wants to understand why it generalizes (or not) — without opening on VC dimension. Empirical first: visible overfitting on a train/test split, ridge that “calibrates” coefficients, a forest that works when linear fails.

Mandatory module: methodological foundation — learning from data, and under what conditions it works. Supervised (least squares → boosting), unsupervised, generalization theory. This is what separates understanding models from calling a library. Downstream LLGA (DL, NLP, Graph ML, RL) reuses this vocabulary.

What you will be able to do

• Frame a learning problem: risk, empirical risk, hypotheses, bias-variance trade-off.
• Implement and tune linear regression, ridge/Lasso regularization, logistic regression and SVMs, justifying every choice.
• Use kernels to move to the nonlinear setting and understand what a “reproducing kernel Hilbert space” brings in practice.
• Choose between trees, random forests and boosting (gradient boosting) according to the nature of the data and the interpretability constraint, and explain a tree ensemble with Shapley values and permutation importance.
• Conduct a complete unsupervised analysis: k-means, Gaussian mixture and EM, PCA and dimensionality reduction.
• State and exploit generalization bounds to argue for a model’s performance on new data.
• Build a rigorous evaluation pipeline: splits, cross-validation, adapted metrics, per-group metrics and fairness criteria, honest comparison of two models, scaling up.
• Read an academic or industrial ML paper and identify the underlying statistical framework.

Official objectives and syllabus (2026-2027 catalog)

Official objectives (paraphrased from the description published on SynapseS): machine learning is the discipline that designs algorithms allowing computers to learn from data, automatically extract complex patterns from them and derive intelligent decisions from them. The course focuses on the methodology underlying supervised and unsupervised learning, with a particular emphasis on the mathematical formulation of the algorithms and on how they can be implemented and used in practice; to this end it presents the necessary tools from optimization theory.

Proofs are not done in lecture: some are done in labs, others are given in a document; each lab ends with a numerical exercise in Python. Official assessment: a final exam.

No session-by-session programme is displayed (the “Descriptif & programme” tab of the sheet is empty); the following table maps every element of the official description to our chapters.

Our materials deliberately go beyond this official description, which remains generic: ch. 8 (generalization theory) pushes the theoretical analysis further than the official statement, ch. 5 (kernels and RKHS) and ch. 6 (trees, forests, boosting) detail model families that the sheet does not name, and ch. 4 (evaluation, big data, pipelines) and ch. 9 (research at CMAP and LIX (Le Pennec, Read)) are deepenings specific to the LLGA track. No theme explicitly listed in the catalog is missing.

Where this course fits in the program

This mandatory module of Year 1 · Period 1 (36 h, 4.5 ECTS) is the hinge of the program: it assumes the two refresher modules are completed, Refresher in Statistics (probability, basic inequalities, estimation, tests, linear regression) and Refresher in Computer Science (Python, NumPy, complexity). The refreshers do not teach optimization: the opening chapter “Review” supplies it (gradient descent, convexity, duality), together with Hoeffding’s inequality and the entropy and KL divergence used throughout.

The official 2026-2027 sheet displays no prerequisites (its tab is empty), but the emphasis on mathematical formulation and Python labs presupposes precisely these two foundations. The course unit is moreover shared with the engineering cycle (X), the MJH, MPRI and CCSN master’s programs and the other MScT tracks ViCAI and TRAI — hence a course tailored to advanced scientific profiles.

Downstream, it feeds everything else in the program. Deep Learning immediately follows by revisiting the perceptron and gradient descent; Emerging Subjects in ML reuses SGD and generalization theory for distributed learning. The Statistical Learning Theory notes deepen chapter 8 up to VC bounds and Rademacher complexity; that course is not in the LLGA 1 – S1 list (it is still offered in other tracks), and its notes are kept on this site for reference. The chapter on evaluation, big data and pipelines directly prepares the projects and applied modules of Period 2, from NLP to Graph ML.

The chapter “Research at CMAP and LIX (Le Pennec, Read)” presents the research of Erwan Le Pennec (CMAP) and Jesse Read (LIX): it is a gateway to internships and possible PhD topics from the end of M1.

Course outline

• Review: optimization, concentration and information: gradient, convexity, concentration inequalities, entropy and KL divergence, Lagrangian duality — L3 tools, immediately mobilized.
• The statistical framework of learning: risk, empirical minimization, bias-variance — the constitution of the problem.
• Linear regression and regularization: the reference model and the first answer to overfitting.
• Classification: logistic, SVM and naive Bayes: margins, losses, decision boundaries, generative versus discriminative modelling.
• Evaluation, big data and pipelines: operational rigor — metrics, validation, scaling up.
• Kernels and RKHS: linearizing the nonlinear via the kernel embedding.
• Trees, forests, boosting: the still-essential family on tabular data, in companies as in competitions.
• Unsupervised: k-means, EM, PCA: segmenting and compressing without labels.
• Generalization theory: why (and when) the empirical error announces the true error.
• Research at CMAP and LIX (Le Pennec, Read): research at CMAP and LIX, from forests to ensembles, and possible internship topics.

Session plan

36 h in class = 12 sessions of 3 h. The volume is the one of the SynapseS 2026–2027 sheet (36 h in person); the sheet publishes no session-by-session programme, so the split below is our proposal for covering these notes in that time. Level 1 = foundations (reviews, definitions, first worked examples), 2 = core methods, 3 = advanced theory; the level never goes down from one session to the next.

Self-study, outside the 36 h (about 5 h in total): ch. 0.4 Lagrangian, KKT and LP duality (≈ 1 h, read before session 3; Ex. 2 in session 3 and Ex. 9 in session 6 use it) · ch. 4.9 Comparing two models honestly (≈ 1 h, after session 7, with Ex. 7) · ch. 9 Research at CMAP and LIX — multi-label learning and aggregation of estimators (≈ 3 h, with Ex. 13 and 17).

How to study this module

• First secure the review: the opening chapter gathers the L3 optimization and concentration tools, which the Refresher in Statistics does not cover, and the entropy and KL divergence met in its section 9.3. The refresher’s probability and estimation chapters are assumed: if an exercise there resists you, handle it before moving on.
• Follow the chapter order: every model family (linear, kernels, trees) is taken up again by generalization theory, which only makes sense after them.
• Reimplement at least once each familiar model (ridge regression, k-means, a tree) in NumPy before using scikit-learn.
• Do the paper exercises on bounds and bias-variance: these are the most discriminating questions in the assessments.
• Build a complete end-to-end mini-pipeline on a real dataset as soon as chapter 4 is done: this is what recruiters expect, and every later model family plugs into it.
• Keep the chapter “Research at CMAP and LIX (Le Pennec, Read)” as an orientation signal: it announces internship topics. For more theory after chapter 8, the Statistical Learning Theory notes are kept on this site for reference (that course is not in the LLGA list).

Notation

Deviations from the site-wide conventions (notation page). Chapter 2 writes p for the number of features, as regression textbooks do. Chapter 9 writes L for the number of labels, as the multi-label literature does. The Lagrangian of sections 0.4 and 3.2 is written \mathcal{L}; it is minimized over the primal variables.

Everywhere else the page follows the site-wide conventions:

• Data: a sample D_n = \{(x_i, y_i)\}_{i=1}^n drawn iid from \mathbb{P}, with n examples and d features, and X \in \mathbb{R}^{n \times d}.
• Losses and risks: a loss \ell(\hat y, y) is written prediction first; \mathcal{R}(f) is the risk, \hat{\mathcal{R}}_n(f) the empirical risk, and F(\theta) an objective minimized over parameters.
• Reserved letters: \eta is a learning rate, or the inverse temperature of exponential weights; L is a smoothness (Lipschitz) constant, or the graph Laplacian L = D - A in graph examples; the bound maximized by EM is written \mathrm{ELBO}.

0. Review: optimization, concentration and information tools

0.1. Why concentration inequalities in an ML course?

All of generalization theory (chapter 8) rests on one simple question: is the empirical risk \hat{\mathcal{R}}_n(f), computed on n examples, close to the true risk \mathcal{R}(f)? The answer is given by concentration inequalities — results of probability analysis that we use here as a black box, proved once and for all.

Chebyshev gives a 1/(nt^2) decay for a mean of n variables: usable but slow, and with no exponential control. The extra ingredient — independence — provides the exponential magic.

0.2. Gradient descent and stochastic gradient descent

The official description of the course announces “tools from optimization theory, and how to use them for machine learning”. Almost every estimator of this module is the minimizer of an empirical risk F(\theta) = \frac1n\sum_{i=1}^n \ell_i(\theta), where \ell_i is the loss on example i. When no closed form exists (logistic regression, the lasso, boosting, neural networks), the minimizer is computed iteratively. Two numbers of the problem govern how fast this works: the smoothness constant and the curvature.

Stochastic gradient descent (SGD). One full gradient costs \mathcal{O}(nd), which is prohibitive when n reaches millions. SGD replaces it by the gradient of one example drawn uniformly at random, or of a mini-batch B_t of size b: \theta_{t+1} = \theta_t - \eta_t\,\frac1b\sum_{i \in B_t}\nabla \ell_i(\theta_t). Because \mathbb{E}_i[\nabla \ell_i(\theta)] = \nabla F(\theta), the step is right on average; its variance decreases like 1/b when the mini-batch is drawn with replacement.

Two regimes follow. With a constant step, SGD reaches a neighbourhood of the minimizer whose size is proportional to \eta times the gradient noise, and then oscillates there. With decreasing steps such that \sum_t \eta_t = \infty and \sum_t \eta_t^2 < \infty (for example \eta_t \propto 1/t), the iterates converge (Robbins–Monro conditions).

For a convex loss, if \|\theta_0 - \theta^\star\| \leq R and the stochastic gradients satisfy \mathbb{E}\|\nabla \ell_i(\theta_t)\|^2 \leq G^2 along the iterates, the averaged iterate \bar\theta_T obtained with \eta = R/(G\sqrt T) satisfies \mathbb{E}[F(\bar\theta_T)] - F(\theta^\star) \leq RG/\sqrt T. This rate is slower per iteration than theorem 0.5, but each iteration is n/b times cheaper — the trade-off behind partial_fit in section 4.6 and behind the training of every neural network in the Deep Learning module.

import numpy as np
rng = np.random.default_rng(0)
n, d = 10_000, 5
X = rng.normal(size=(n, d)); theta_star = rng.normal(size=d)
y = X @ theta_star + 0.1 * rng.normal(size=n)

L = np.linalg.eigvalsh(X.T @ X / n).max()          # smoothness constant
theta = np.zeros(d)
for t in range(100):                                 # full gradient descent, step 1/L
    theta -= (1 / L) * X.T @ (X @ theta - y) / n

theta_sgd = np.zeros(d)
for t in range(1, 2001):                             # mini-batch SGD, b = 32, decreasing step
    idx = rng.integers(0, n, size=32)
    grad = X[idx].T @ (X[idx] @ theta_sgd - y[idx]) / 32
    theta_sgd -= 0.5 / np.sqrt(t) * grad
print(np.linalg.norm(theta - theta_star), np.linalg.norm(theta_sgd - theta_star))

0.3. Entropy, cross-entropy and KL divergence

Classification losses, the EM algorithm of chapter 7 and the training objective of every language model compare two probability distributions. Three quantities do this job. We define them on a finite set; for densities, integrals replace the sums.

The logistic loss of proposition 3.2 is (iii) for the Bernoulli model of the label given x, and the softmax loss of language models is (iii) for the next token. The Refresher in Statistics, section 9.3 derives (iii) for conditional models.

Mutual information. The dependence between two variables is the divergence between their joint law and the product of their marginals: I(X; Y) = \mathrm{KL}\big(p_{XY} \,\|\, p_X \otimes p_Y\big) = H(Y) - H(Y \mid X) \geq 0, where H(Y \mid X) is the average entropy of Y once X is known. By (i), it is zero if and only if X and Y are independent. It is the information gain of the trees of section 6.1 and one of the filter scores of section 4.7.

0.4. Lagrangian duality and KKT conditions (self-study)

Read this section alone before session 3, where Exercise 2 first needs it. Many estimators minimize a function under constraints: the SVM of section 3.2 is solved through its dual, and Exercises 2 and 9 minimize under constraints. Duality turns each constraint into a price, and the KKT conditions characterize the optimum.

Linear programs. When the objective and the constraints are affine, the dual is again a linear program: \min_{x \geq 0} \ c^\top x \ \ \text{s.t.} \ \ Ax \geq b \qquad \text{has the dual} \qquad \max_{y \geq 0} \ b^\top y \ \ \text{s.t.} \ \ A^\top y \leq c. For linear programs, strong duality holds as soon as the primal has a finite optimum, with no Slater condition. Linear-programming duality comes back in reinforcement learning (the linear program of a Markov decision process) and in optimal transport.

1. The statistical framework of learning

Concrete scene: you fit a classifier on 60,000 digits (MNIST-like), train accuracy 99.8%, test 91%. The model “works”… and memorizes. Conversely, an under-regularized linear model may stall at 85% everywhere. This chapter names those gaps: risk vs empirical risk, bias-variance, validation. Theory comes after the symptom.

The excess risk decomposes into two contributions of different natures:

The first depends only on the choice of \mathcal{F} (modeling bias), the second on the sample and the size of \mathcal{F} (variance, chapter 8). Enlarging \mathcal{F} decreases the first and increases the second: the whole dilemma is there.

1.1. Bias-variance

A class \mathcal{F} that is too small ⇒ high bias; too large ⇒ high variance. This decomposition is diagnostic: high training and test errors ⇒ underfitting (enlarge the model); low training and high test ⇒ overfitting (regularize, more data, chapters 2 and 8). No algorithm is universally better (the “no free lunch” theorem): prior knowledge about the data matters as much as the algorithm.

1.2. Cross-validation

The risk \mathcal{R} is unobservable: it is estimated by setting data aside. k-fold: split into k blocks, train k times while rotating the test block, average.

Leave-one-out (k = n) has low bias but high estimation variance and costs n trainings; k = 5 or 10 is the standard compromise.

Program rules: never fit preprocessing on the test set; a final test set that is looked at only once; validation serves to choose hyperparameters and models (chapter 4 for the nested version).

from sklearn.model_selection import cross_val_score
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import Ridge

pipe = make_pipeline(StandardScaler(), Ridge(alpha=1.0))
scores = cross_val_score(pipe, X, y, cv=5, scoring="neg_root_mean_squared_error")
print(-scores.mean(), scores.std())

2. Linear regression and regularization

2.1. Ordinary least squares

2.2. Regularization: ridge and lasso

from sklearn.linear_model import Ridge, Lasso, lasso_path
for lam in [1e-4, 1e-2, 1.0, 10.0]:
    l = Lasso(alpha=lam).fit(X, y)
    print(f"lambda={lam:8.3f}  nonzero coeffs = {(l.coef_ != 0).sum()}")

# lasso regularization path (piecewise linear, cf. LARS)
alphas, coefs, _ = lasso_path(X, y, alphas=np.logspace(-3, 1, 100))

3. Classification: logistic regression and SVM

3.1. Logistic regression

3.2. Margin SVM

3.3. Generative versus discriminative classifiers: naive Bayes

Logistic regression models \mathbb{P}(Y \mid X) directly, and the SVM only a decision boundary: both are discriminative. A generative classifier takes the opposite route: it models how each class produces its inputs, p(x \mid y), together with the class proportions \pi_y = \mathbb{P}(Y = y), and classifies with Bayes’ formula.

The model family is the same as in section 3.1; only the fitting differs. Naive Bayes fits \theta through the joint likelihood of (x, y), which is efficient when its assumptions hold; logistic regression fits \mathbb{P}(Y \mid x) only and remains consistent for that family when they fail.

Ng and Jordan (2002) made the trade-off precise: the generative classifier approaches its asymptotic error with a number of examples of order \log d, the discriminative one with order d, but the discriminative asymptotic error is never worse. Naive Bayes is therefore a strong baseline for small samples and high-dimensional text, and logistic regression usually wins once data are plentiful.

4. Evaluation, big data and pipelines

4.1. Choosing your metric

4.2. Nested cross-validation

Selecting a model and estimating its risk on the same folds is a well-documented optimism bias: the retained score is that of a “champion” chosen among the candidates on those same data — the exact mechanism of selection overfitting (chapter 8!). Nested cross-validation separates the two roles: the inner loop (on k-1 folds) chooses the hyperparameters, the outer loop (the remaining fold) evaluates the model thus chosen. Cost: k_{\text{int}} \times k_{\text{ext}} trainings — the price of statistical honesty.

from sklearn.model_selection import GridSearchCV, cross_val_score
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression

pipe = make_pipeline(StandardScaler(), LogisticRegression(max_iter=1000))
grid = GridSearchCV(pipe, {"logisticregression__C": [0.01, 0.1, 1, 10]}, cv=5)
outer_scores = cross_val_score(grid, X, y, cv=10)   # outer loop: honest estimation
print(outer_scores.mean(), outer_scores.std())

4.3. Data leakage

from sklearn.compose import ColumnTransformer
from sklearn.impute import SimpleImputer
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import OneHotEncoder, StandardScaler
from sklearn.ensemble import HistGradientBoostingClassifier

prep = ColumnTransformer([
    ("num", Pipeline([("imp", SimpleImputer(strategy="median")),
                      ("sc",  StandardScaler())]), num_cols),
    ("cat", OneHotEncoder(handle_unknown="ignore"), cat_cols),
])
model = Pipeline([("prep", prep), ("clf", HistGradientBoostingClassifier())])
# model.fit on the train only; nothing is learned outside fit().

4.4. Imbalanced classes

With 0.5% of fraud, the trivial classifier “everything is normal” reaches 99.5% accuracy. Three levers:

• (i) the loss — weight the classes via class_weight="balanced": the \propto 1/n_k weighting restores the balance in ERM;
• (ii) resampling — oversampling the minority (SMOTE: interpolate between minority neighbors) or undersampling the majority, always inside the training pipeline only (otherwise: leakage);
• (iii) evaluation — precision/recall, PR-AUC; and the decision threshold chosen after calibration (4.5), not at 0.5 by default.

4.5. Probability calibration

Two standard post-processings, learned on a separate calibration set: Platt scaling — fit a logistic regression (chapter 3) on the noisy score: \hat p = \sigma(a\,s(x) + b); isotonic regression — the nonparametric monotone function closest to the reliability bins (more flexible, more data needed).

Caution: discrimination and calibration are two distinct properties — a model may excellently order examples (high AUC) while announcing systematically overconfident probabilities. SVM scores are not probabilities: going through calibration is indispensable as soon as one wants probabilities (cost/benefit decisions, stacking).

from sklearn.calibration import CalibratedClassifierCV
cal = CalibratedClassifierCV(estimator=svc, method="isotonic", cv=5).fit(X_train, y_train)
# check: sklearn.calibration.calibration_curve + Brier score

4.6. Big data: what does size change?

When n explodes, theory plays for you (bounds in \sqrt{d/n}, chapter 8) but computation costs become the limiting factor. Switch to incremental methods (partial_fit/SGD: the stochastic gradient descent of section 0.2, one pass at a time), to hashing for sparse text features, to histogram implementations (HistGradientBoosting), and to the stream methods of chapter 9 (River) when the data do not fit in memory.

Golden rule of the program: a complete reference pipeline — train/val/test split → preprocessing learned on train only → nested selection → single evaluation on test → error inspection (confusion matrix, residuals of chapter 2, subgroups) — to be replicated in all the labs and the running project. The Year 1 end-of-year projects use this pipeline as their shared evaluation kit, completed by subgroup metrics (4.8), honest model comparison (4.9) and the paired, group-level comparison of the Refresher in Statistics exit checkpoint.

4.7. Feature selection

Removing useless features reduces variance, cost and the effort of interpretation. Three families of methods exist, and all three are learning steps: they must be fitted on training data only.

import numpy as np
from sklearn.pipeline import make_pipeline
from sklearn.feature_selection import SelectKBest, f_classif
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import cross_val_score

rng = np.random.default_rng(0)
X = rng.normal(size=(50, 5000)); y = rng.permutation(np.repeat([0, 1], 25))  # pure noise
top = SelectKBest(f_classif, k=20).fit(X, y).get_support()       # WRONG: selection on all data
print(cross_val_score(LogisticRegression(), X[:, top], y, cv=5).mean())   # optimistic
pipe = make_pipeline(SelectKBest(f_classif, k=20), LogisticRegression())  # RIGHT: inside the folds
print(cross_val_score(pipe, X, y, cv=5).mean())                            # close to 0.5

4.8. Subgroup evaluation and group fairness

An average score can hide a group on which the model fails. Before deployment, the error inspection of the reference pipeline (4.6) is repeated per group: by sex, age band, region, device, or any attribute on which errors would be costly or unfair.

The per-group metrics are computed on the held-out predictions of the pipeline, never on the training data. Each comes with its group size: a 20-point gap on a group of 30 people is mostly noise (section 4.9 gives the intervals).

These criteria cannot all hold at once. The identity below, a simple count, shows why.

There are three places to act on a disparity: before training (reweighting the groups), during training (a constraint in the loss), and after training (one threshold per group, the post-processing of Hardt and coauthors). Deleting the attribute A from the features is not enough when other features are correlated with it.

import pandas as pd
res = pd.DataFrame({"y": y_test, "yhat": model.predict(X_test), "group": X_test["sex"]})
for g, d in res.groupby("group"):                       # held-out predictions only
    pos, neg = d.y == 1, d.y == 0
    print(g, len(d), "positive rate", d.yhat.mean(),
          "TPR", d.yhat[pos].mean(), "FPR", d.yhat[neg].mean(), "PPV", d.y[d.yhat == 1].mean())

4.9. Comparing two models honestly (self-study)

“Model B beats model A by 0.8 points” is a claim about risks, made from noisy estimates. This section, read after session 7, gives the tools to check such a claim before writing it.

Paired comparisons over folds or seeds. Evaluate both models on the same folds, or with the same seeds, and work with the differences \delta_j = s_j(B) - s_j(A) for j = 1, \dots, k. With \bar\delta their mean and s_\delta their standard deviation, the paired statistic t = \frac{\bar\delta}{s_\delta/\sqrt{k}} is compared with a Student distribution with k - 1 degrees of freedom. Pairing removes the variation that both models share: an easy fold is easy for both. Two caveats:

• cross-validation folds share training data, so the differences are correlated and the plain test is too optimistic. Nadeau and Bengio (2003) correct it by replacing 1/k with 1/k + n_{\text{test}}/n_{\text{train}} in the variance;
• with few folds or skewed differences, the Wilcoxon signed-rank test, which uses only the signed ranks of the differences, makes no normality assumption.

One test set: McNemar’s test. When both models are evaluated once on the same test examples, only their disagreements matter. Let n_{01} count the examples that A gets right and B gets wrong, and n_{10} the reverse. If both models have the same accuracy, each disagreement goes either way with probability 1/2, and \chi^2 = \frac{(|n_{01} - n_{10}| - 1)^2}{n_{01} + n_{10}} approximately follows a \chi^2 law with one degree of freedom: reject equality at 5 % above 3.84. With few disagreements, use the exact binomial test instead (Dietterich, 1998).

An interval for one accuracy: Clopper–Pearson. If k of n test examples are classified correctly, the exact 95 % interval for the accuracy is \big[\,B_{0.025}(k,\ n - k + 1),\ \ B_{0.975}(k + 1,\ n - k)\,\big], where B_q(a, b) is the q-quantile of the Beta distribution with parameters a and b. For 870 correct answers out of 1000, it gives [0.848, 0.890]. The interval is 4 points wide, so a 1-point difference between two models needs the paired tests above, not two overlapping intervals.

Many comparisons: Bonferroni. Testing m hypotheses (ten datasets, five baselines) at level \alpha each produces false discoveries. Testing each at level \alpha/m keeps the probability of any false discovery below \alpha, by the union bound.

5. Kernels and RKHS

5.1. The Moore-Aronszajn theorem

5.2. The representer theorem and kernel regression

6. Trees, forests, boosting

6.1. Decision trees (CART)

Recursive partition of \mathcal{X} by axis-aligned cuts (binary questions “x_j \leq t?”). At each leaf, one predicts the mean (regression) or the majority class (classification). Growth: at each node, choose (j, t) maximizing the impurity gain; then pruning to avoid overfitting. The exact impurity criteria, for a node D containing the classes in proportions p_1, \dots, p_K:

6.2. Random forests (bagging)

6.3. Boosting: gradient descent in function space

from sklearn.ensemble import RandomForestClassifier, HistGradientBoostingClassifier
from sklearn.model_selection import cross_val_score
rf  = RandomForestClassifier(n_estimators=300, min_samples_leaf=2, oob_score=True)
gbt = HistGradientBoostingClassifier(max_iter=300, learning_rate=0.06)
print(cross_val_score(rf, X, y, cv=5).mean(), cross_val_score(gbt, X, y, cv=5).mean())
print("forest OOB error:", 1 - rf.fit(X, y).oob_score_)  # free validation

6.4. Explaining tree ensembles

A forest of 300 trees cannot be read like one tree. When a decision must be justified (credit, health, the interpretability constraint of the course objectives), two questions come up: which features matter overall, and why this prediction for this example?

Global importance: impurity versus permutation. Forests report by default the mean decrease in impurity: the gains of definition 6.1, summed over the splits that use each feature. It is computed on the training data and favours features with many possible split points, such as continuous variables or identifiers, even when they are pure noise (Strobl and coauthors, 2007).

The permutation importance (Breiman, 2001) avoids this bias. On held-out data, shuffle one column, which breaks its link with the label, and measure the drop of the score. Two caveats remain: correlated features share their importance, since the model can use one in place of the other, and an importance describes the model, not a causal effect in the world.

For a linear model with independent features, the Shapley value is the familiar “coefficient times deviation”, \phi_j = \theta_j\,(x_j - \mathbb{E}[X_j]) (Exercise 15).

TreeSHAP. The sum of definition 6.5 has 2^{d-1} terms. For trees, however, the values v(S) can be estimated by walking down the tree with the training counts stored in its nodes. TreeSHAP (Lundberg and coauthors, 2020) computes the resulting Shapley values exactly, in time \mathcal{O}(T\,N_{\text{leaf}}\,D^2) for T trees with at most N_{\text{leaf}} leaves and depth D; additivity then sums them over the ensemble.

import shap                                     # pip install shap
explainer = shap.TreeExplainer(gbt.fit(X_train, y_train))
phi = explainer.shap_values(X_test)             # one row of attributions per test example
shap.summary_plot(phi, X_test)                  # global view: the spread of each feature's values

Attribution methods for neural networks and LLMs (LIME, KernelSHAP, integrated gradients) are taught in Explainability, Security and Privacy of LLMs, ch. 4.

7. Unsupervised: k-means, EM, PCA

7.1. k-means

Beyond k-means: hierarchical and density-based clustering. k-means looks for K compact clusters of similar spread. Single-linkage clustering starts from n singletons and repeatedly merges the two clusters whose closest points are closest. The merge heights form a dendrogram, and cutting it at a height gives a partition at that scale.

Its merges are the edges of a minimum spanning tree, which makes it fast but prone to chaining through a few intermediate points. It is also the 0-dimensional persistence of the Topological Data Analysis module.

DBSCAN (Ester, Kriegel, Sander and Xu, 1996) needs a radius \varepsilon and a count m. A point with at least m neighbours within \varepsilon is a core point; clusters are the connected groups of core points with their neighbours, and the remaining points are labelled noise. DBSCAN finds clusters of any shape and chooses their number itself, but a single \varepsilon fits poorly when the densities differ.

7.2. Gaussian mixtures and EM

7.3. Principal component analysis

import numpy as np
Xc = X - X.mean(0)
U, S, Vt = np.linalg.svd(Xc, full_matrices=False)
Z = Xc @ Vt[:2].T                  # 2D projection
var_explained = (S**2 / (S**2).sum())[:10]   # variance explained per component

8. Generalization theory

This chapter justifies mathematically what precedes: when and why does empirical risk minimization generalize? It is also the starting point of the Statistical Learning Theory notes, kept for reference (that course is not in the LLGA list), and the reading grid for all the hyperparameters of the course (regularization, margin, tree depth, number of boosting iterations).

8.1. Why uniform convergence is necessary

8.2. Vapnik-Chervonenkis dimension

8.3. The VC bound by double sampling (sketch)

8.4. Rademacher complexity

Rademacher versus VC: the Rademacher complexity is data-dependent (it is computed on the sample, by simulating the \sigma_i), without a logarithmic factor, and applies to continuous classes of real-valued functions (scores, margins). It is the standard tool of modern bounds — including the SVM margin bounds (theorem 3.6) and the aggregation bounds of chapter 9.

8.5. Regularizing = controlling capacity

9. Research at CMAP and LIX (Le Pennec, Read)

At École Polytechnique, two research lines extend this module directly: multi-label classification (Jesse Read, LIX) and estimator aggregation (Erwan Le Pennec, CMAP). Two topics where the previous chapters reappear — and gateways to internships / PhD topics.

9.1. Jesse Read: learning sets of labels (multi-label, streams, extreme)

The taxonomy popularized by Jesse Read’s thesis (Scalable Multi-label Classification, Waikato, 2010) and by the classifier chains paper separates methods into two families: problem transformation (bring multi-label back to standard binary/multiclass problems) and algorithm adaptation (modify kNN, trees, SVMs… to directly ingest label vectors). Three canonical transformations:

9.2. Erwan Le Pennec: aggregating estimators rather than choosing one

Facing a family f_1, \dots, f_M of candidate estimators (different kernels, different wavelet bases, different values of \lambda…), the classical statistician selects one. The alternative carried by Erwan Le Pennec and his co-authors is to aggregate them: predict with a weighted combination f_{\hat\pi} = \sum_m \hat\pi_m f_m, the weights being learned from data — typically exponential weights (Gibbs measure):

Here \eta > 0 is an inverse temperature. The risk of the aggregate is then controlled by an oracle inequality: pay the price of the best candidate up to a \log M term, with no assumption on which one is best.

Exercises

1. ★ Closed-form ridge. Show that \hat\theta_{\text{ridge}} is indeed given by (X^\top X + n\lambda I)^{-1}X^\top y by setting the gradient to zero, then that the problem is always strictly convex as soon as \lambda > 0.

   Proof. Solution Gradient: \nabla_\theta\big(\tfrac1n\|y - X\theta\|^2 + \lambda\|\theta\|_2^2\big) = \tfrac2n X^\top(X\theta - y) + 2\lambda\theta; setting it to zero gives (X^\top X + n\lambda I)\theta = X^\top y.

   The Hessian \tfrac2n(X^\top X + n\lambda I) \succeq 2\lambda I \succ 0 is positive definite for \lambda > 0, even if X^\top X is singular: unique global minimum — this is the first practical benefit of regularization (cf. proposition 2.5 for the spectral reading).∎

2. ★ Gauss-Markov in dimension 1. Model y_i = \theta + \varepsilon_i, \varepsilon_i centered, independent, with variance \sigma^2. Show that among the linear unbiased estimators a^\top y of \theta, the empirical mean has minimal variance.

   Proof. Solution Unbiasedness: \mathbb{E}[a^\top y] = \theta\,\textstyle\sum_i a_i = \theta for every \theta, hence \sum_i a_i = 1. Variance: \mathrm{Var}(a^\top y) = \sigma^2\|a\|^2.

   Minimizing \|a\|^2 under the constraint \mathbf{1}^\top a = 1 (Lagrange multipliers, example 0.12 of section 0.4) gives the uniform a_i = 1/n. This is the case X = \mathbf 1 of theorem 2.3; the estimator \frac1n\sum y_i is its geometric projection.∎

3. ★ Cross-entropy. Verify that minimizing the logistic cross-entropy amounts to maximizing the Bernoulli likelihood \prod_i \sigma(\theta^\top x_i)^{y_i}(1-\sigma)^{1-y_i}, and compute \nabla_\theta \hat{\mathcal{R}}_n = \frac1n X^\top(\sigma(X\theta) - y). (All the steps are in theorem 3.3: redo them without notes.)

4. ★ Bagging and correlation. Derive again the formula \mathrm{Var}(A_B) = \rho\sigma^2 + \tfrac{1-\rho}{B}\sigma^2 of theorem 6.2, then comment: what happens if the B trees are identical (\rho = 1)? Why does a small m_{\text{try}} decrease \rho — and at what price?

   Proof. Solution Expand the variance of the sum with equicorrelated covariances \tfrac1{B^2}[B\sigma^2 + B(B-1)\rho\sigma^2]. If \rho = 1, all the trees are identical: the variance remains \sigma^2, bagging is useless. Reducing m_{\text{try}} randomizes the candidate splits and decorrelates the trees; in exchange, each tree, seeing fewer variables, may miss the “right” split — its individual bias increases slightly. The optimal trade-off is found by validation (chapter 4).∎

5. ★ Entropy and the two KL divergences. Write B_p for the Bernoulli distribution of parameter p. Compute in nats the entropy H(B_{0.9}) and the two divergences \mathrm{KL}(B_{0.5} \,\|\, B_{0.9}) and \mathrm{KL}(B_{0.9} \,\|\, B_{0.5}). Then check proposition 0.8(ii) on the pair (B_{0.9}, B_{0.5}).

   Proof. Solution The entropy is H(B_{0.9}) = -0.9\ln 0.9 - 0.1\ln 0.1 \approx 0.095 + 0.230 = 0.325. The two divergences differ, since KL is not symmetric: \mathrm{KL}(B_{0.5} \,\|\, B_{0.9}) = 0.5\ln\tfrac{0.5}{0.9} + 0.5\ln\tfrac{0.5}{0.1} \approx 0.511, \qquad \mathrm{KL}(B_{0.9} \,\|\, B_{0.5}) = 0.9\ln 1.8 + 0.1\ln 0.2 \approx 0.368. Check: H(B_{0.9}, B_{0.5}) = -\ln 0.5 = \ln 2 \approx 0.693, and indeed 0.325 + 0.368 = 0.693.∎

6. ★ PCA by hand. Centred data in \mathbb{R}^2 have the empirical covariance \hat\Sigma = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}. Find the principal components, the share of variance explained by the first one, and the mean squared reconstruction error of the projection on it (theorem 7.6).

   Proof. Solution The characteristic polynomial (2 - \lambda)^2 - 1 has the roots 3 and 1, with eigenvectors v_1 = (1, 1)/\sqrt2 and v_2 = (1, -1)/\sqrt2.

   The first component explains 3/(3 + 1) = 75\% of the variance. By the identity in the proof of theorem 7.6, the mean squared reconstruction error is the total variance \mathrm{tr}\,\hat\Sigma = 4 minus the explained part 3, that is 1 = \lambda_2.∎

7. ★ Is the new model better? Two classifiers are evaluated on the same 1000 test examples. A is right on 870 of them; where they disagree, A alone is right 15 times and B alone 30 times. (i) Give the Clopper–Pearson 95 % interval for the accuracy of A. (ii) Apply McNemar’s test at 5 %. (iii) This comparison was the best of ten datasets that were tried: what changes? (section 4.9)

   Proof. Solution (i) The Beta quantiles (scipy.stats.beta.ppf) give [0.848, 0.890]. B is right on 870 - 15 + 30 = 885 examples.

   (ii) With n_{01} = 15 and n_{10} = 30, \chi^2 = \frac{(|15 - 30| - 1)^2}{45} = \frac{196}{45} \approx 4.36 > 3.84, so B is significantly better at 5 % (p \approx 0.037; the exact binomial test gives 0.036).

   (iii) With ten comparisons, Bonferroni asks for p < 0.005: the gain is no longer significant. Reporting only the best dataset is a selection effect, the trap of Example 4.3.∎

8. ★★ Kernel duel. (i) Show that k(x, x') = (\langle x, x'\rangle + 1)^2 on \mathcal{X} = \mathbb{R}^2 is a kernel by exhibiting an explicit feature map. (ii) Is the function k(x,x') = \cos(x - x') on \mathbb{R} a positive definite kernel?

   Proof. Solution (i) Expand: (x_1x'_1 + x_2x'_2 + 1)^2 = x_1^2x_1'^2 + 2x_1x_1'x_2x_2' + x_2^2x_2'^2 + 2x_1x'_1 + 2x_2x'_2 + 1 = \langle \phi(x), \phi(x')\rangle with \phi(x) = (x_1^2,\ \sqrt2\,x_1x_2,\ x_2^2,\ \sqrt2\,x_1,\ \sqrt2\,x_2,\ 1) — dimension 6 versus 2: the kernel trick saves the explicit passage.

   (ii) Yes, by the addition formula: \cos(x - x') = \cos x\cos x' + \sin x \sin x' = \langle(\cos x, \sin x),\,(\cos x', \sin x')\rangle. A dimension-2 feature map, unit norm.∎

9. ★★ Dual derivation of the SVM. Take up the primal of theorem 3.5: write the Lagrangian (section 0.4) with multipliers (\alpha_i, \mu_i), set the gradients in (\theta, b, \xi) to zero, and recover (a) the dual function, (b) the three families of points of the table in section 3.2 via the complementarity conditions.

10. ★★ EM for a mixture of two 1D Gaussians. Write the two steps, implement (NumPy), and check on a mixture 0.4\,\mathcal{N}(-2, 1) + 0.6\,\mathcal{N}(3, 1) that the log-likelihood is increasing over 50 iterations (theorem 7.5: plot \log p_{\theta_t} and check the increase, strict away from a stationary point).

11. ★★ VC by hand. (i) Show that the intervals [a,b] of \mathbb{R} do not shatter 3 aligned points (example 8.4(ii)). (ii) Compute the VC bound (theorem 8.6) for d = 10, n = 1000, \delta = 5\% and comment (“how much data per dimension?”).

    Proof. Solution (i) For x_1 < x_2 < x_3, the label (1,0,1) is unrealizable: an interval containing x_1 and x_3 contains the whole interval [x_1, x_3], hence x_2.

    (ii) The bound is \sqrt{8(10\log(2e \cdot 1000/10) + \log 80)/1000} \approx \sqrt{8 \times (63.0 + 4.4)/1000} \approx 0.73: a theoretical error margin of 73 points! The bound is (very) conservative — it guarantees the consistency of the ERM principle (error \to 0 as n/d \to \infty), not actual performance; this is why one also evaluates by cross-validation (4.2).∎

12. ★★ k-means++. (i) Show that uniform random seeding has no bounded approximation ratio. Take k = 2 and the four corners of a w \times h rectangle with w \gg h. Compute the probability that Lloyd’s algorithm, started from two distinct corners drawn uniformly, stops at the partition into top and bottom pairs, and the ratio W_{\text{final}}/W^\star there. (ii) Compute the same probability for k-means++. (iii) Simulate both initializations on anisotropic blobs and measure W_{\text{final}}/W^\star (proposition 7.3 guarantees 8(\ln k + 2) in expectation for k-means++).

    Proof. Solution (i) The optimum pairs the corners of each short side: each pair costs 2(h/2)^2, so W^\star = h^2. If the two seeds lie on the same short side, the two far corners join the seed on their own long side; the centres move to the middles of the long sides, every corner is closest to its own centre, and Lloyd stops with W = 2 \cdot 2(w/2)^2 = w^2.

    This happens with probability 2/6 = 1/3, and then W_{\text{final}}/W^\star = (w/h)^2, as large as one wants.

    (ii) After a first corner, k-means++ picks the other corner of the same short side with probability h^2/(2w^2 + 2h^2), which tends to 0.∎

13. ★★ Multi-label: Hamming versus subset accuracy. On example 9.2 (labels S, P, s), one tests on 10 documents of which 6 follow the pattern “S=1, P=0 \Rightarrow s=1” and 4 are “all zero”. BR learns h_s \equiv 0 (it sees only x), CC learns h_s(x, S=1, P=0) = 1. Compute the Hamming and subset accuracy losses of the two methods, and explain when BR becomes competitive again.

    Proof. Solution CC is perfect on the learned patterns: Hamming 0, accuracy 1.

    BR errs on the label s of the 6 “pure science” documents: Hamming = \frac{6}{10 \times 3} = 0.2, accuracy = \frac4{10} = 0.4.

    If the S \to s dependency did not exist (labels conditionally independent given x), BR would be optimal for Hamming — the chain would only add noise; it is the targeted loss (Hamming vs fine dependencies) that dictates the method (table in section 9.1).∎

14. ★★ Group fairness on Adult. On the Adult census data (Kohavi, 1996; OpenML dataset 1590), predict whether the income exceeds 50,000 dollars, with the pipeline of 4.3 and a gradient-boosted model.

    • (i) Report accuracy, positive rate, true- and false-positive rates and precision for women and for men, each with its group size (4.8).
    • (ii) Check the identity of proposition 4.5 on your numbers.
    • (iii) Choose one threshold per group so that the true-positive rates are equal, and report what happens to the precision of each group and to the overall accuracy.
    • (iv) Remove the attribute sex from the features: does the gap in positive rates disappear?

    Proof. Solution Outline. (ii) The identity holds exactly, since it is a count. (iii) The group with the lower true-positive rate gets a lower threshold: its true- and false-positive rates rise, its precision usually falls, and the overall accuracy typically drops a little.

    (iv) No. Features correlated with sex, such as relationship (husband or wife) and marital-status, still carry it: removing the attribute (“fairness through unawareness”) does not remove the disparity.∎

15. ★★ Shapley values by hand. Two independent features have mean zero, and the model is f(x) = x_1 + x_1x_2.

    • (i) For the example x = (1, 2), compute v(S) for the four sets S (definition 6.5), then \phi_1 and \phi_2, and check efficiency.
    • (ii) How is the interaction term x_1x_2 shared between the two features?
    • (iii) Show that for a linear model f(x) = \theta_0 + \theta^\top x with independent features, \phi_j = \theta_j(x_j - \mathbb{E}[X_j]).

    Proof. Solution (i) v(\varnothing) = \mathbb{E}[X_1 + X_1X_2] = 0, v(\{1\}) = 1 + \mathbb{E}[X_2] = 1, v(\{2\}) = 3\,\mathbb{E}[X_1] = 0 and v(\{1, 2\}) = f(1, 2) = 3. With two features, each order of arrival has weight 1/2: \phi_1 = \tfrac12(1 - 0) + \tfrac12(3 - 0) = 2, \qquad \phi_2 = \tfrac12(0 - 0) + \tfrac12(3 - 1) = 1, and \phi_1 + \phi_2 = 3 = f(x) - \mathbb{E}[f(X)].

    (ii) The main term gives 1 to feature 1; the interaction x_1x_2 = 2 is split equally, 1 to each.

    (iii) Here v(S) = \theta_0 + \sum_{k \in S}\theta_k x_k + \sum_{k \notin S}\theta_k\mathbb{E}[X_k]. Adding j to any S adds \theta_j(x_j - \mathbb{E}[X_j]), and the weights of definition 6.5 sum to 1.∎

16. ★★ A margin bound in numbers.

    • (i) The ramp loss \varphi_\gamma(u) = \min(1, \max(0, 1 - u/\gamma)), applied to the margin u = y f(x), lies between the 0–1 loss \mathbf{1}\{u \leq 0\} and the margin loss \mathbf{1}\{u < \gamma\}. Show that it is 1/\gamma-Lipschitz, and use lemma 8.9 to explain the term 2R/(\gamma\sqrt n) of theorem 3.6.
    • (ii) With R = 1, \gamma = 0.1, n = 10{,}000, \delta = 0.05 and an empirical margin error of 0.05, evaluate the bound of theorem 3.6.
    • (iii) How many examples make the complexity term equal to 0.05? Why does the dimension of x not appear, unlike in theorem 8.6?

    Proof. Solution (i) \varphi_\gamma is constant outside [0, \gamma] and has slope -1/\gamma on it, so it is 1/\gamma-Lipschitz. Contraction multiplies the complexity R/\sqrt n by 1/\gamma, and symmetrization brings the factor 2.

    (ii) The bound is 0.05 + \frac{2}{0.1 \times 100} + \sqrt{\frac{\ln 40}{20{,}000}} \approx 0.05 + 0.2 + 0.014 \approx 0.26.

    (iii) 2/(0.1\sqrt n) = 0.05 gives \sqrt n = 400, that is n = 160{,}000. The class is controlled by the norm R and the margin \gamma, not by the number of parameters.∎

17. ★★★ Exponential weights. Three estimators with empirical risks 0.30, 0.32, 0.50, n = 100.

    Compute the weights \hat\pi for \eta \in \{0.1\,;\ 1\,;\ 10\} (definition in chapter 9) and plot \max_m \hat\pi_m as a function of \eta. What link with the softmax of chapter 3, and what role does \eta play when one doubts the validity of the empirical risks (small n)?

    Proof. Solution Weights \propto \exp(-100\eta \hat R_m):

    • for \eta = 0.1, ratios e^{-0.2} \approx 0.82 and e^{-2} \approx 0.14 (soft mixture);
    • for \eta = 1, e^{-2} \approx 0.14 and e^{-20} \approx 2\cdot10^{-9};
    • for \eta = 10, quasi-hard selection.

    This is a softmax on the scores -n\eta\hat R_m — \eta plays the role of the inverse temperature. At small n, the \hat R_m are noisy (chapter 0): taking \eta small keeps a mixture, robust to estimation error — precisely the logic of the oracle inequalities of chapter 9.∎

18. ★★★ Running project. On the 20 Newsgroups dataset (count vectorizer → TF-IDF → logistic/forest), build the complete pipeline with nested cross-validation (4.2), report the confusion matrix and macro F1, and calibrate the probabilities (4.5) before choosing the decision threshold. This text preprocessing will be redone “in a modern neural version” in the NLP module.

Projects and assessment

The official assessment is “a final exam” (SynapseS 2026–2027 sheet, “Validation” in the description); the LLGA section of the sheet displays no weights, no resit rule and no ECTS. Everything below is a proposal: the written exam is a mock of that final exam, and the projects are practice that an instructor may adopt as continuous assessment. They exercise objective O1 (machine-learning foundations) in every subject, O7 (hands-on practice: leak-free pipelines, calibration, reproducible code) and O8 (trustworthy AI: the fairness criteria of 4.8 and the explanations of 6.4).

Solo projects

1. [Solo · ≈ 20 h] Honest-evaluation audit. Question: on real data, how optimistic are the evaluation shortcuts that chapter 4 warns against?
   • Reproduce the selection-bias trap of Example 4.3. Then inject each of the four leaks of section 4.3 in a controlled way into a pipeline on the Adult census data (Kohavi, 1996; OpenML dataset 1590): scaling before the split, target encoding on the full set, duplicated individuals across folds, a feature computed from the label.
   • Compare flat and nested cross-validation (4.2) over a grid of at least 20 configurations, repeated over 10 seeds, with a held-out test set (ch. 1, 4).
   • Deliverables: code, a 4–6 page audit report ending with a checklist of fixes, a 10-minute talk. Success: the optimism of each shortcut is measured with an interval over seeds (4.9), and the pipelined estimate agrees with the held-out test set within that interval.
2. [Solo · ≈ 20 h] Guided paper study: generative versus discriminative classifiers (Ng and Jordan, 2002). Question: does naive Bayes reach its asymptotic error with fewer examples than logistic regression, and are its probabilities usable?
   • Read the paper with a one-page sheet: its statistical framework (definition 1.1), its claims, what is proved and what is only measured, its limits (ch. 1, 3).
   • Extend Exercise 18: learning curves of multinomial naive Bayes and logistic regression on 20 Newsgroups (Lang, 1995; fetch_20newsgroups in scikit-learn), from 50 examples to the full training set, over 5 seeds.
   • Calibrate both models with Platt scaling and isotonic regression (4.5); report macro-F1, the Brier score and reliability diagrams, and set the decision thresholds after calibration (ch. 4).
   • Deliverables: code, the reading sheet, a 4–6 page report, a 10-minute talk. Success: the crossing of the learning curves is reproduced, or its absence explained; calibration lowers the Brier score of naive Bayes, and the report says whether it changes that of logistic regression.
3. [Solo · ≈ 20 h] Generalization bounds against observed gaps. Question: how far are the bounds of chapters 3 and 8 from the gaps that one actually measures?
   • For the norm-bounded linear class, the supremum of definition 8.7 has the closed form (R/n)\,\|\sum_i \sigma_i x_i\|; for the ball of radius R of an RKHS, it is (R/n)\sqrt{\sigma^\top K \sigma} (ch. 5). Estimate both complexities by Monte Carlo over the signs.
   • Train linear and RBF support vector machines on two classes of Fashion-MNIST (Xiao, Rasul and Vollgraf, 2017), inputs scaled to unit norm, for several n and C. Plot the measured train–test gap against the margin bound (theorem 3.6) and the VC bound (theorem 8.6) (ch. 3, 8).
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Success: the estimates stay below R\sqrt{\mathrm{tr}\,K}/n, and the report identifies which terms make each bound loose.

Group projects

1. [Group of 3 · ≈ 30 h each] Paper study: why do tree-based models still outperform deep learning on typical tabular data? (Grinsztajn, Oyallon and Varoquaux, 2022). Question: do the paper’s findings also hold against kernel methods, under an honest protocol?
   • Member 1: kernel methods — an RBF support vector machine and kernel ridge regression with the Nyström approximation (ch. 5).
   • Member 2: random forests and HistGradientBoosting with early stopping; the effect of the number of candidate features per split and of the learning rate (ch. 6).
   • Member 3: the shared nested cross-validation pipeline on about ten datasets of the paper’s public benchmark, paired comparisons over 3 seeds (4.9), and the paper’s experiment that adds uninformative features (ch. 4).
   • Deliverables: code, a 6–8 page report, a 15-minute talk. Success: a ranking backed by paired tests, and at least one of the paper’s explanations (sensitivity to uninformative features, irregular target functions) confirmed or refuted for kernels.
2. [Group of 3 · ≈ 30 h each] A fair and explained income model across US states. Use the ACSIncome task of folktables (Ding, Hardt, Miller and Schmidt, 2021), built from US census microdata to replace the Adult data. The subject prepares Explainability, Security and Privacy of LLMs.
   • Member 1: models and calibration — logistic regression and gradient boosting in a leak-free pipeline, with calibration curves per group (ch. 3, 4, 6).
   • Member 2: fairness audit (4.8) — positive rates, error rates and precision by sex and by race, with intervals (4.9); one threshold per group for equal opportunity, and its price in accuracy; a numerical check of proposition 4.5.
   • Member 3: explanations (6.4) — TreeSHAP against permutation importance, and their stability when the model is trained on one state and tested on another.
   • Deliverables: code, a 6–8 page report with a one-page model card, a 15-minute talk. Success: the fairness–accuracy trade-off is plotted with intervals, and the report recommends one criterion and justifies it.
3. [Group of 3 · ≈ 30 h each] Classical baselines for text and graphs. Question: how much of a neural model’s gain survives a well-tuned classical baseline run under the same protocol? Best done in Period 2, alongside Text Mining & NLP and Graph ML.
   • Member 1: text — TF-IDF with logistic regression on AG News (Zhang, Zhao and LeCun, 2015), against a small fine-tuned encoder (NLP ch. 7).
   • Member 2: graphs — the Weisfeiler–Lehman subtree kernel (Shervashidze and coauthors, 2011) with a support vector machine (ch. 5) on MUTAG and PROTEINS from TUDataset (Morris and coauthors, 2020), against a graph neural network (Graph ML ch. 2, 5).
   • Member 3: the shared protocol — same splits and tuning budget, 3 seeds, paired tests and calibration (ch. 4), and the contamination checks of LLM ch. 9 for the pretrained encoder.
   • Deliverables: code, a 6–8 page report, a 15-minute talk. Success: each gap between the neural model and its classical baseline is reported with a paired interval, and the baselines become the reference rows of the Year 1 end-of-year projects.

Written exam (proposal)

Format: 2 hours, one handwritten A4 sheet allowed, no electronic device, four questions. The sheet announces a final exam but displays no format.

1. Question (4 points). Define the risk, the empirical risk and empirical risk minimization. State the decomposition of the excess risk into approximation and estimation errors, and say how enlarging the class moves each term. Why is a cross-validated score optimistic when the same folds also chose the hyperparameters, and how does nested cross-validation fix it?

   Expected: definitions 1.1–1.2, with the loss written \ell(\hat y, y), and the key result of chapter 1. A larger class lowers the approximation error and raises the estimation error, which proposition 8.1 bounds by a supremum over the class. The retained score is the maximum of noisy estimates, a selection bias (4.2, Example 4.3); nested cross-validation chooses in the inner loop and evaluates on an outer fold never used for the choice.

2. Question (5 points). (a) With X^\top X = nI_3, z = X^\top y/n = (0.9, -0.2, 0.4) and \lambda = 0.6, compute the lasso of definition 2.4. (b) Two groups have prevalences 0.5 and 0.2; a classifier has precision 0.8 and false-negative rate 0.2 in both. Compute the two false-positive rates. (c) On 1000 shared test examples, model A alone is right 15 times and model B alone 30 times. Apply McNemar’s test at 5 %.

   Expected: (a) soft thresholding at \lambda/2 = 0.3 gives (0.6, 0, 0.1) (proposition 2.6). (b) By proposition 4.5, 0.2 and 0.05. (c) \chi^2 = 14^2/45 \approx 4.36 > 3.84: B is significantly better at 5 % (section 4.9).

3. Question (5 points). For two distributions on a finite set, prove that \mathrm{KL}(p \,\|\, q) \geq 0, with equality if and only if p = q. Deduce that H(p, q) \geq H(p), and show that maximizing the likelihood of a model q_\theta on a sample minimizes the cross-entropy H(\hat p_n, q_\theta).

   Expected: Jensen’s inequality for the concave logarithm under p, with its two equality cases (proposition 0.8(i)); the split H(p, q) = H(p) + \mathrm{KL}(p \,\|\, q); grouping equal values, the average log-likelihood is -H(\hat p_n, q_\theta), and H(\hat p_n) does not depend on \theta.

4. Question (6 points). For logistic regression with p_i = \sigma(\theta^\top x_i) and labels y'_i \in \{-1, +1\}, F(\theta) = \frac1n\sum_{i=1}^n \log\big(1 + e^{-y'_i\theta^\top x_i}\big). (a) Compute \nabla F and \nabla^2 F. (b) Prove that F is convex, and strictly convex when X has full column rank. (c) Write one Newton step and show that it solves a weighted least-squares problem.

   Expected: (a) by theorem 3.3, \nabla F = \frac1n X^\top(p - y) and \nabla^2 F = \frac1n X^\top W X with W = \mathrm{diag}(p_i(1 - p_i)). (b) For every v, v^\top \nabla^2 F\, v = \frac1n\sum_i w_i (x_i^\top v)^2 \geq 0, zero only if Xv = 0. (c) \theta^+ = \theta + (X^\top W X)^{-1}X^\top(y - p): the weighted least-squares fit, with weights w_i, of the working response X\theta + W^{-1}(y - p) (IRLS).

Grading rubric (proposal)

References

Textbooks

• T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, 2nd ed., Springer, 2009 — free PDF: the reference textbook of the course.
• G. James, D. Witten, T. Hastie, R. Tibshirani, An Introduction to Statistical Learning, 2nd ed., Springer, 2021 — the applied (Python) version of the same foundation.
• C. Bishop, Pattern Recognition and Machine Learning, Springer, 2006 — for the generative viewpoint (EM, kernels) taken up again in Deep Learning.
• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning, Cambridge, 2014 — ch. 6 (VC dimension and Sauer’s lemma), ch. 26 (Rademacher complexity), ch. 13 (margin bounds, SVM).
• K. Murphy, Probabilistic Machine Learning: An Introduction, MIT Press, 2022 — a modern panorama, free online.
• S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, 2013 — ch. 1-2: Markov, Hoeffding, Chernoff, and beyond (chapter 0).
• G. Garrigos, R. M. Gower, Handbook of Convergence Theorems for (Stochastic) Gradient Methods, arXiv:2301.11235, 2023 — rates of gradient descent and SGD (section 0.2).
• scikit-learn User Guide — the labs follow its conventions (pipelines, calibration, imblearn for imbalance).

Foundational papers cited in the course

• J. H. Friedman, Greedy Function Approximation: A Gradient Boosting Machine, Annals of Statistics 29(5), 2001 — Project Euclid: boosting as functional gradient descent (chapter 6).
• D. Arthur, S. Vassilvitskii, k-means++: The Advantages of Careful Seeding, SODA 2007 — PDF (Stanford): the 8(\ln k + 2) guarantee (chapter 7).
• M. E. Tipping, C. M. Bishop, Probabilistic Principal Component Analysis, JRSS-B 61(3), 1999 — Oxford Academic: PCA as a generative model (chapter 7).
• A. Y. Ng, M. I. Jordan, On Discriminative vs. Generative Classifiers: A Comparison of Logistic Regression and Naive Bayes, NeurIPS 2001 (published 2002): the sample-size trade-off of section 3.3.

Duality, theory, clustering, evaluation and explanation

• S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004 — free PDF: Lagrangian duality, Slater and KKT (section 0.4).
• C. J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery 2(2), 1998 — the sinusoid class and its unshatterable four points (Example 8.2).
• M. Ledoux, M. Talagrand, Probability in Banach Spaces, Springer, 1991 — the contraction principle (lemma 8.9).
• M. Mohri, A. Rostamizadeh, A. Talwalkar, Foundations of Machine Learning, 2nd ed., MIT Press, 2018 — Rademacher bounds, Talagrand’s lemma and margin bounds (chapter 8).
• M. Ester, H.-P. Kriegel, J. Sander, X. Xu, A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise, KDD 1996 — DBSCAN (section 7.1).
• L. van der Maaten, G. Hinton, Visualizing Data using t-SNE, JMLR 9, 2008; L. McInnes, J. Healy, J. Melville, UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction, arXiv:1802.03426, 2018 — section 7.3.
• M. Hardt, E. Price, N. Srebro, Equality of Opportunity in Supervised Learning, NeurIPS 2016 — equalized odds and per-group thresholds (section 4.8).
• A. Chouldechova, Fair Prediction with Disparate Impact: A Study of Bias in Recidivism Prediction Instruments, Big Data 5(2), 2017 — the identity of proposition 4.5.
• J. Kleinberg, S. Mullainathan, M. Raghavan, Inherent Trade-Offs in the Fair Determination of Risk Scores, ITCS 2017 — calibration against balanced error rates (section 4.8).
• T. G. Dietterich, Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms, Neural Computation 10(7), 1998 — McNemar’s test for classifiers (section 4.9).
• C. Nadeau, Y. Bengio, Inference for the Generalization Error, Machine Learning 52(3), 2003 — the corrected resampled t test (section 4.9).
• L. Breiman, Random Forests, Machine Learning 45(1), 2001 — permutation importance (section 6.4).
• C. Strobl, A.-L. Boulesteix, A. Zeileis, T. Hothorn, Bias in Random Forest Variable Importance Measures: Illustrations, Sources and a Solution, BMC Bioinformatics 8, 2007 — the bias of impurity importance (section 6.4).
• L. S. Shapley, A Value for n-Person Games, in Contributions to the Theory of Games II, Princeton University Press, 1953 — the Shapley axioms (section 6.4).
• S. M. Lundberg, G. Erion, H. Chen, et al., From Local Explanations to Global Understanding with Explainable AI for Trees, Nature Machine Intelligence 2, 2020 — TreeSHAP (section 6.4).

Research at CMAP and LIX (Le Pennec, Read)

• J. Read, B. Pfahringer, G. Holmes, E. Frank, Classifier Chains for Multi-label Classification, ECML PKDD 2009 — PDF: the classifier chains paper (chapter 9).
• J. Read, Scalable Multi-label Classification, PhD thesis, University of Waikato, 2010 — full text: the transformation/adaptation taxonomy of multi-label.
• J. Read, A. Bifet, B. Pfahringer, G. Holmes, Scalable and Efficient Multi-label Classification for Evolving Data Streams, Machine Learning 88, 2012 — multi-label on streams (iSOUP-Tree).
• J. Read, Concept-drifting Data Streams are Time Series, 2018 — arXiv:1810.02266.
• J. Read et al., Deep Learning for Multi-label Classification, 2014 — arXiv:1502.05988: a multi-label and deep learning panorama.
• J. Montiel, M. Halford, D. Salles, S. Vrysis, et al. (incl. J. Read), River: machine learning for streaming data in Python, JMLR 22(110), 2021 — JMLR: the tooling of the “streaming” labs.
• L. Montuelle, E. Le Pennec, PAC-Bayesian Aggregation of Affine Estimators, 2014 — arXiv:1410.0661; long version: PAC-Bayesian aggregation of linear estimators, Nonparametric Statistics 33, 2019.
• J. Salmon, E. Le Pennec, An Aggregator Point of View on NL-Means, SPIE Wavelets and Sparsity XIV, 2009 — patch-based denoising reread as aggregation of estimators.
• F. Autin, E. Le Pennec, K. Tribouley, Thresholding Methods to Estimate Copula Density, Journal of Multivariate Analysis 101(1), 2010 — thresholding and automatic selection in nonparametrics.
• É. Gautier, E. Le Pennec, Adaptive Estimation in the Nonparametric Random Coefficients Binary Choice Model by Needlet Thresholding — HAL (inria-00601274): needlets and scale selection, link with logistic regression.