2026-07-01 14:24:01lugonthier:
Refactor section headings for consistency and clarity across multiple documents in the Machine Learning module. Updated headings to include numerical prefixes for better organization and navigation. Adjusted content formatting and improved terminology in French translations for decision trees, ensemble methods, and other foundational concepts.
en/Machine Learning/01 Introduction.md ..
@@ 1,14 1,14 @@
-
# Introduction
+
# 1. Introduction
Machine learning builds models that learn patterns from data instead of being explicitly programmed with rules. This module fixes the notation used throughout the course and maps the landscape of problems and models, so later modules can stay terse and formula-first.
-
## Types of learning
+
## 1.1 Types of learning
- **Supervised**: learn from labelled examples (regression, classification).
- **Unsupervised**: find structure in unlabelled data (clustering, dimensionality reduction).
- **Reinforcement**: learn from feedback by interacting with an environment.
-
## The workflow
+
## 1.2 The workflow
1. Define the problem and gather data.
2. Explore and preprocess the data.
@@ 23,9 23,9 @@
- Classify a supervised problem by the type of its output.
- Distinguish discriminative from generative models.
-
## Notation and setup
+
## 1.3 Notation and setup
-
### Training set
+
### 1.3.1 Training set
The training set is defined as a collection of $m$ labelled examples:
@@ 46,7 46,7 @@
*Remark:* the intercept lets a single dot product $\theta^T x$ carry the bias term, so no separate constant has to be written.
-
### Hypothesis
+
### 1.3.2 Hypothesis
A hypothesis is defined as a function chosen from a model family that maps an input to a prediction:
@@ 54,7 54,7 @@
Learning is the search, over the parameters $\theta$, for the hypothesis that best fits the training set.
-
### Design matrix
+
### 1.3.3 Design matrix
The design matrix stacks the $m$ transposed inputs row by row, and the target vector collects the labels:
@@ 64,9 64,9 @@
*Remark:* with this layout many models reduce to compact matrix expressions, for example a linear prediction over all examples is $X\theta$.
-
## Types of problems and models
+
## 1.4 Types of problems and models
-
### Type of prediction
+
### 1.4.1 Type of prediction
A supervised problem is named by the nature of its target $y$.
@@ 81,7 81,7 @@
*Left: regression fits a continuous output. Right: classification separates the input space into classes.*
-
### Type of model
+
### 1.4.2 Type of model
A model is discriminative if it learns the conditional $p(y \mid x)$ directly, and generative if it models how the data are generated, $p(x \mid y)$ and $p(y)$, then inverts via Bayes' rule:
@@ 95,7 95,7 @@
*Remark:* $p(x)$ is the same for every class, so for classification it can be dropped and the most probable class taken via $\arg\max_y\, p(x \mid y)\, p(y)$.
-
### Putting it together
+
### 1.4.3 Putting it together
The output type fixes regression vs classification, and the modelling choice fixes discriminative vs generative. Together they select a model family.
en/Machine Learning/02 General concepts.md ..
@@ 1,4 1,4 @@
-
# General concepts
+
# 2. General concepts
The building blocks shared by every supervised model: how a loss measures a single prediction and aggregates into a cost, how iterative optimization minimizes that cost, and how the probabilistic view (likelihood) recovers the same objectives. We close with Newton's method, a second-order alternative to gradient descent.
@@ 8,9 8,9 @@
- Define the likelihood and the MLE objective, and link it to minimizing a cost.
- State Newton's update in one and several dimensions and compare it with gradient descent.
-
## Loss functions and cost
+
## 2.1 Loss functions and cost
-
### Loss function
+
### 2.1.1 Loss function
A loss function $L(z, y)$ is defined as a scalar penalty comparing a raw model score $z$ (or a predicted probability $\phi$) against the target $y$. Smaller is better. Each family of models is characterized by its loss.
@@ 23,7 23,7 @@
*Remark:* $z$ denotes a raw score such as $\theta^T x$, whereas $\phi \in (0,1)$ denotes a predicted probability. The cross-entropy row takes a probability $\phi$, not a raw score.
-
### Cost function
+
### 2.1.2 Cost function
The cost $J(\theta)$ is defined as the sum of the per-example losses over the whole training set of $m$ examples:
@@ 37,9 37,9 @@
*Margin-based losses, each a convex surrogate for the 0-1 loss that penalizes small or negative margins.*
-
## Gradient descent
+
## 2.2 Gradient descent
-
### Update rule
+
### 2.2.1 Update rule
Gradient descent iteratively moves the parameters $\theta$ against the gradient of the cost, scaled by a learning rate $\alpha > 0$:
@@ 49,7 49,7 @@
*Remark:* if $\alpha$ is too large the iterates can diverge, if too small convergence is slow.
-
### Batch versus stochastic
+
### 2.2.2 Batch versus stochastic
The two variants differ in how many examples contribute to one update.
@@ 60,7 60,7 @@
Batch gives a smooth descent but reads the whole set per step. SGD updates after each example, so it is cheap per step and noisy.
-
### LMS (Widrow-Hoff) update
+
### 2.2.3 LMS (Widrow-Hoff) update
For the least squared error, the per-coordinate stochastic update is defined as:
@@ 74,15 74,15 @@
*Gradient descent steps downhill toward the minimum (star).*
-
## Likelihood and maximum likelihood estimation
+
## 2.3 Likelihood and maximum likelihood estimation
-
### Likelihood
+
### 2.3.1 Likelihood
The likelihood $L(\theta)$ is defined as the probability of the observed targets under the model, viewed as a function of the parameters $\theta$. Assuming examples are independent, it factorizes:
Products are awkward to optimize, so we take the logarithm. The log-likelihood $\ell(\theta)$ is defined as:
@@ 90,7 90,7 @@
The $\log$ is monotone, so it has the same maximizer as $L(\theta)$ while turning the product into a sum.
-
### Maximum likelihood estimation
+
### 2.3.3 Maximum likelihood estimation
The MLE is defined as the parameter value that makes the data most probable:
@@ 98,9 98,9 @@
*Remark:* maximizing the log-likelihood is equivalent to minimizing the cost $J(\theta) = -\ell(\theta)$. This is exactly the cost-minimization view of the previous lessons, so likelihood and cost are two faces of one objective.
-
## Newton's algorithm
+
## 2.4 Newton's algorithm
-
### One-dimensional update
+
### 2.4.1 One-dimensional update
To find a stationary point of the log-likelihood, Newton's method follows the local quadratic approximation. The scalar update is defined as:
@@ 108,7 108,7 @@
It divides the first derivative by the second, so the step automatically adapts to the curvature.
-
### Multivariate update
+
### 2.4.2 Multivariate update
With a parameter vector $\theta \in \mathbb{R}^{n+1}$, the second derivative becomes the Hessian matrix $H$, with $H_{jk}=\dfrac{\partial^2 \ell}{\partial\theta_j\,\partial\theta_k}$. The update is defined as:
@@ 116,7 116,7 @@
*Remark:* each step solves a linear system in $H$, an $O(n^3)$ operation, so Newton's method is costly when the number of features $n$ is large.
Linear models predict from a linear score $\theta^T x$. This module covers linear regression (continuous targets), logistic regression (binary classification), and the generalized linear model framework that unifies both through the exponential family. Each model is fit by maximum likelihood and shares the same gradient-based update.
@@ 10,21 10,21 @@
- Recognize the exponential-family form and build a GLM from its three assumptions.
- Recover linear, logistic, and softmax regression as special cases.
-
## Linear regression
+
## 3.1 Linear regression
-
### Hypothesis
+
### 3.1.1 Hypothesis
The hypothesis is linear in the augmented input $x \in \mathbb{R}^{n+1}$ with $x_0 = 1$ and parameters $\theta \in \mathbb{R}^{n+1}$:
$$\boxed{ h_\theta(x) = \theta^T x }$$
-
### Cost function
+
### 3.1.2 Cost function
The cost is defined as half the sum of squared residuals over the $m$ examples:
Gradient descent on $J$ gives the least-mean-squares (Widrow-Hoff) update, applied per example $(x^{(i)}, y^{(i)})$:
@@ 37,7 37,7 @@
| Batch GD | sum over all $m$ examples | $O(mn)$ | $m$ small to moderate |
| Stochastic GD (SGD) | one example at a time | $O(n)$ | $m$ large, streaming |
-
### Normal equation
+
### 3.1.4 Normal equation
Setting $\nabla_\theta J(\theta) = 0$ gives a closed-form solution from the design matrix $X$ and target vector $y$:
@@ 45,7 45,7 @@
*Remark:* the normal equation needs no learning rate and no iteration, but inverting $X^T X$ costs $O(n^3)$, so for large $n$ the iterative LMS update is preferred.
-
### Probabilistic interpretation
+
### 3.1.5 Probabilistic interpretation
Assume $y^{(i)} = \theta^T x^{(i)} + \varepsilon^{(i)}$ with i.i.d. Gaussian noise $\varepsilon^{(i)} \sim \mathcal{N}(0, \sigma^2)$. Maximizing the log-likelihood then coincides with minimizing the least-squares cost:
@@ 57,9 57,9 @@
*Least squares fits the line that minimizes the squared residuals (grey segments).*
-
## Logistic regression
+
## 3.2 Logistic regression
-
### Sigmoid
+
### 3.2.1 Sigmoid
The sigmoid (logistic) function squashes a raw score $z \in \mathbb{R}$ into a probability:
@@ 67,7 67,7 @@
Its derivative has the convenient form $g'(z) = g(z)\left(1 - g(z)\right)$.
-
### Model
+
### 3.2.2 Model
The hypothesis outputs the probability of the positive class, with $\phi$ the predicted probability:
Over $m$ i.i.d. examples the log-likelihood is the negative cross-entropy summed over the data:
@@ 85,7 85,7 @@
with $\phi^{(i)} = h_\theta(x^{(i)})$.
-
### Gradient ascent
+
### 3.2.4 Gradient ascent
Maximizing $\ell$ by gradient ascent gives the same form as the LMS update:
@@ 93,7 93,7 @@
*Remark:* the update matches linear regression in form, even though $h_\theta$ is now the sigmoid. This is no coincidence, both are generalized linear models.
-
### Newton's method
+
### 3.2.5 Newton's method
Newton's method converges faster near the optimum. In one dimension:
@@ 109,11 109,11 @@
*Left: the sigmoid maps scores into the interval (0,1). Right: the decision boundary and predicted probability.*
-
## Perceptron
+
## 3.3 Perceptron
The perceptron is the original linear classifier. It keeps the linear score $\theta^T x$ of logistic regression but replaces the sigmoid with a hard threshold, so the output is a class label rather than a probability. Labels are $y \in \{0, 1\}$.
-
### Activation and hypothesis
+
### 3.3.1 Activation and hypothesis
The activation is the step function:
@@ 123,7 123,7 @@
$$\boxed{ h_\theta(x) = g(\theta^T x) }$$
-
### Learning rule
+
### 3.3.2 Learning rule
The perceptron is trained online, one example at a time, and corrects $\theta$ only on a misclassified point:
@@ 135,7 135,7 @@
*The perceptron finds one separating hyperplane. It is not necessarily the maximum-margin one the SVM will choose.*
-
### Convergence
+
### 3.3.3 Convergence
| data | behaviour |
| --- | --- |
@@ 144,15 144,15 @@
*Remark:* the perceptron stops at the first hyperplane that separates the data, usually not the one with the widest margin. This gap motivates the support vector machine (which maximizes the margin) and, stacked into layers, the neural network (a perceptron is a single unit).
-
## Generalized linear models
+
## 3.4 Generalized linear models
-
### Exponential family
+
### 3.4.1 Exponential family
A distribution is in the exponential family if its density can be written with natural parameter $\eta$, sufficient statistic $T(y)$, log-partition $a(\eta)$, and base measure $b(y)$:
A GLM rests on three choices. The response is in the exponential family, the natural parameter is linear in the input, and the prediction is the expected sufficient statistic:
*Remark:* for the Bernoulli, $\eta$ is the log-odds and its inverse is the sigmoid, $\phi = g(\eta)$. This is why logistic regression has the form it does.
-
### Softmax regression
+
### 3.4.4 Softmax regression
For multiclass labels $y \in \{1, \dots, k\}$ the GLM gives softmax regression, with one parameter vector $\theta_k$ per class:
The inner products are exactly where a kernel $K$ is substituted (see [Kernels](/en/Machine%20Learning/04%20Support%20Vector%20Machines#kernels)).
+
The inner products are exactly where a kernel $K$ is substituted (see [Kernels](/en/Machine%20Learning/04%20Support%20Vector%20Machines#43-kernels)).
-
### KKT and support vectors
+
### 4.4.3 KKT and support vectors
At the optimum, complementary slackness ties each multiplier to its constraint:
@@ 183,7 183,7 @@
These are the points exactly on the margin. All others have $\beta_i = 0$ and do not affect $w$.
-
### Kernelized decision
+
### 4.4.4 Kernelized decision
Replacing the inner product by a kernel gives a decision rule expressed only through support vectors:
@@ 192,7 192,7 @@
*Remark:* only support vectors ($\beta_i > 0$) contribute, so prediction cost scales with their
count, not with $m$.
-
### From primal to decision
+
### 4.4.5 From primal to decision
```mermaid
flowchart TD
en/Machine Learning/05 Decision trees and ensemble methods.md ..
@@ 1,4 1,4 @@
-
# Decision trees and ensemble methods
+
# 5. Decision trees and ensemble methods
Tree models partition the input space into axis-aligned regions and fit a constant per region, giving interpretable but high-variance predictors. Ensemble methods combine many trees: bagging and random forests average independently grown trees to cut variance, while boosting grows trees sequentially to cut bias.
@@ 9,9 9,9 @@
- Estimate generalization error for free with out-of-bag samples.
- Build a strong predictor as an additive sum of weak learners (AdaBoost, gradient boosting).
-
## CART decision trees
+
## 5.1 CART decision trees
-
### Tree as a partition
+
### 5.1.1 Tree as a partition
A CART tree partitions the input space into $M$ disjoint regions $R_1,\dots,R_M$ (the leaves) and predicts a constant $c_m$ on each. The prediction is defined as
@@ 21,7 21,7 @@
*Remark:* the regions are axis-aligned boxes, so the decision boundary is a staircase. A single tree has low bias but high variance.
-
### Impurity and split selection
+
### 5.1.2 Impurity and split selection
For a region with class proportions $\hat p_k$, impurity measures how mixed the labels are. The Gini index is defined as
@@ 44,7 44,7 @@
*Remark:* the two criteria almost always pick the same split. Gini is the default in most implementations because it avoids the logarithm.
-
### Regression trees
+
### 5.1.3 Regression trees
For regression the leaf value is the mean of the targets in the region, defined as
@@ 52,7 52,7 @@
and splits minimize the within-region squared error instead of a classification impurity.
-
### Pruning
+
### 5.1.4 Pruning
An unpruned tree fits the training set exactly and overfits. Cost-complexity pruning trades fit against tree size $|T|$ (the number of leaves) through a penalty $\alpha\ge0$:
@@ 72,9 72,9 @@
*A tree carves the input space into axis-aligned regions, each with a constant prediction.*
-
## Random forests
+
## 5.2 Random forests
-
### Bagging
+
### 5.2.1 Bagging
Bagging (bootstrap aggregating) trains $B$ trees on $B$ bootstrap resamples of the data and averages them. The bagged predictor is defined as
@@ 84,7 84,7 @@
A bootstrap sample draws $N$ examples with replacement from $N$ examples. The probability that a given example is never drawn is $(1-\tfrac1N)^N\to e^{-1}\approx0.37$, so about 37% of the data is left out of each tree. These are its out-of-bag (OOB) examples.
-
### Variance of an average
+
### 5.2.2 Variance of an average
If the $B$ trees each have variance $\sigma^2$ and pairwise correlation $\rho$, the variance of their average is
@@ 92,7 92,7 @@
The second term vanishes as $B$ grows, but the first, $\rho\sigma^2$, does not. Reducing the correlation $\rho$ between trees is therefore the key lever, and that is what random forests target.
-
### Random forests
+
### 5.2.3 Random forests
A random forest is bagging plus feature subsampling: at each split only a random subset of $m_{\text{try}}$ features is considered as split candidates. The usual choices are
@@ 126,9 126,9 @@
*(a) A single deep tree overfits with a jagged boundary. (b) A random forest averages many trees for a smoother boundary.*
-
## Boosting
+
## 5.3 Boosting
-
### Additive model
+
### 5.3.1 Additive model
Boosting builds a predictor as a weighted sum of $T$ weak learners $h_t$ (typically shallow trees), fitted one at a time. The additive model is defined as
@@ 136,7 136,7 @@
Each stage corrects the errors of the running sum, so the ensemble is built sequentially and reduces bias rather than variance.
-
### AdaBoost
+
### 5.3.2 AdaBoost
With labels $y\in\{-1,+1\}$, AdaBoost keeps example weights $w^{(i)}$ that concentrate on the currently misclassified points. At round $t$ the weak learner has weighted error $\varepsilon_t$, and its coefficient is defined as
@@ 148,7 148,7 @@
and renormalized. Misclassified examples ($y^{(i)}h_t(x^{(i)})<0$) gain weight, so the next learner focuses on them.
-
### Gradient boosting
+
### 5.3.3 Gradient boosting
Gradient boosting generalizes the idea to any differentiable loss $L$. At stage $t$ it fits the next learner to the negative gradient of the loss evaluated at the current model, the pseudo-residual defined as
fr/Machine Learning/01 Introduction.md ..
@@ 1,14 1,14 @@
-
# Introduction
+
# 1. Introduction
Le machine learning construit des modèles qui apprennent des motifs à partir de données, au lieu d'être programmés explicitement avec des règles. Ce module fixe la notation utilisée tout au long du cours et cartographie l'éventail des problèmes et des modèles, afin que les modules suivants restent concis et centrés sur les formules.
-
## Types d'apprentissage
+
## 1.1 Types d'apprentissage
- **Supervisé** : apprendre à partir d'exemples étiquetés (régression, classification).
- **Non supervisé** : trouver une structure dans des données non étiquetées (clustering, réduction de dimension).
- **Par renforcement** : apprendre via des retours en interagissant avec un environnement.
-
## Le déroulé
+
## 1.2 Le déroulé
1. Définir le problème et rassembler les données.
2. Explorer et préparer les données.
@@ 23,9 23,9 @@
- Classer un problème supervisé selon le type de sa sortie.
- Distinguer les modèles discriminatifs des modèles génératifs.
-
## Notation et mise en place
+
## 1.3 Notation et mise en place
-
### Ensemble d'entraînement
+
### 1.3.1 Ensemble d'entraînement
L'ensemble d'entraînement est défini comme une collection de $m$ exemples étiquetés :
@@ 46,7 46,7 @@
*Remarque :* l'ordonnée à l'origine permet à un seul produit scalaire $\theta^T x$ de porter le terme de biais, de sorte qu'aucune constante séparée n'a besoin d'être écrite.
-
### Hypothèse
+
### 1.3.2 Hypothèse
Une hypothèse est définie comme une fonction choisie dans une famille de modèles qui associe une entrée à une prédiction :
@@ 54,7 54,7 @@
L'apprentissage est la recherche, sur les paramètres $\theta$, de l'hypothèse qui s'ajuste le mieux à l'ensemble d'entraînement.
-
### Matrice de conception
+
### 1.3.3 Matrice de conception
La matrice de conception empile les $m$ entrées transposées ligne par ligne, et le vecteur cible rassemble les étiquettes :
@@ 64,9 64,9 @@
*Remarque :* avec cette disposition de nombreux modèles se réduisent à des expressions matricielles compactes, par exemple une prédiction linéaire sur tous les exemples vaut $X\theta$.
-
## Types de problèmes et de modèles
+
## 1.4 Types de problèmes et de modèles
-
### Type de prédiction
+
### 1.4.1 Type de prédiction
Un problème supervisé est nommé selon la nature de sa cible $y$.
@@ 81,7 81,7 @@
*À gauche : la régression ajuste une sortie continue. À droite : la classification sépare l'espace en classes.*
-
### Type de modèle
+
### 1.4.2 Type de modèle
Un modèle est discriminatif s'il apprend directement la conditionnelle $p(y \mid x)$, et génératif s'il modélise la façon dont les données sont générées, $p(x \mid y)$ et $p(y)$, puis inverse via la règle de Bayes :
@@ 95,7 95,7 @@
*Remarque :* $p(x)$ est identique pour toutes les classes, donc en classification on peut l'ignorer et retenir la classe la plus probable via $\arg\max_y\, p(x \mid y)\, p(y)$.
-
### Mise en relation
+
### 1.4.3 Mise en relation
Le type de sortie fixe régression vs classification, et le choix de modélisation fixe discriminatif vs génératif. Ensemble ils sélectionnent une famille de modèles.
fr/Machine Learning/02 General concepts.md ..
@@ 1,4 1,4 @@
-
# Concepts généraux
+
# 2. Concepts généraux
Les briques communes à tout modèle supervisé : comment une perte mesure une prédiction isolée puis s'agrège en un coût, comment l'optimisation itérative minimise ce coût, et comment le point de vue probabiliste (la vraisemblance) retrouve les mêmes objectifs. On termine par l'algorithme de Newton, une alternative du second ordre à la descente de gradient.
@@ 8,9 8,9 @@
- Définir la vraisemblance et l'objectif du maximum de vraisemblance, et le relier à la minimisation d'un coût.
- Énoncer la mise à jour de Newton en une et plusieurs dimensions et la comparer à la descente de gradient.
-
## Fonctions de perte et coût
+
## 2.1 Fonctions de perte et coût
-
### Fonction de perte
+
### 2.1.1 Fonction de perte
Une fonction de perte $L(z, y)$ est définie comme une pénalité scalaire comparant un score brut $z$ du modèle (ou une probabilité prédite $\phi$) à la cible $y$. Plus elle est petite, mieux c'est. Chaque famille de modèles se caractérise par sa perte.
@@ 23,7 23,7 @@
*Remarque :* $z$ désigne un score brut tel que $\theta^T x$, tandis que $\phi \in (0,1)$ désigne une probabilité prédite. La ligne d'entropie croisée prend une probabilité $\phi$, non un score brut.
-
### Fonction de coût
+
### 2.1.2 Fonction de coût
Le coût $J(\theta)$ est défini comme la somme des pertes par exemple sur tout l'ensemble d'entraînement de $m$ exemples :
@@ 37,9 37,9 @@
*Pertes basées sur la marge, chacune un substitut convexe de la perte 0-1 qui pénalise les marges faibles ou négatives.*
-
## Descente de gradient
+
## 2.2 Descente de gradient
-
### Règle de mise à jour
+
### 2.2.1 Règle de mise à jour
La descente de gradient déplace itérativement les paramètres $\theta$ à l'opposé du gradient du coût, mis à l'échelle par un taux d'apprentissage $\alpha > 0$ :
@@ 49,7 49,7 @@
*Remarque :* si $\alpha$ est trop grand les itérés peuvent diverger, s'il est trop petit la convergence est lente.
-
### Par lots ou stochastique
+
### 2.2.2 Par lots ou stochastique
Les deux variantes diffèrent par le nombre d'exemples contribuant à une mise à jour.
@@ 60,7 60,7 @@
Le mode par lots donne une descente lisse mais lit tout l'ensemble à chaque pas. SGD met à jour après chaque exemple, donc peu coûteux par pas et bruité.
-
### Mise à jour LMS (Widrow-Hoff)
+
### 2.2.3 Mise à jour LMS (Widrow-Hoff)
Pour l'erreur quadratique, la mise à jour stochastique par coordonnée est définie comme :
@@ 74,15 74,15 @@
*La descente de gradient descend la pente vers le minimum (étoile).*
-
## Vraisemblance et estimation du maximum de vraisemblance
+
## 2.3 Vraisemblance et estimation du maximum de vraisemblance
-
### Vraisemblance
+
### 2.3.1 Vraisemblance
La vraisemblance $L(\theta)$ est définie comme la probabilité des cibles observées sous le modèle, vue comme une fonction des paramètres $\theta$. En supposant les exemples indépendants, elle se factorise :
Les produits sont malcommodes à optimiser, on prend donc le logarithme. La log-vraisemblance $\ell(\theta)$ est définie comme :
@@ 90,7 90,7 @@
Le $\log$ est monotone, il a donc le même maximiseur que $L(\theta)$ tout en transformant le produit en somme.
-
### Estimation du maximum de vraisemblance
+
### 2.3.3 Estimation du maximum de vraisemblance
Le maximum de vraisemblance est défini comme la valeur des paramètres qui rend les données les plus probables :
@@ 98,9 98,9 @@
*Remarque :* maximiser la log-vraisemblance équivaut à minimiser le coût $J(\theta) = -\ell(\theta)$. C'est exactement la vue par minimisation du coût des leçons précédentes, vraisemblance et coût sont donc deux faces d'un même objectif.
-
## Algorithme de Newton
+
## 2.4 Algorithme de Newton
-
### Mise à jour unidimensionnelle
+
### 2.4.1 Mise à jour unidimensionnelle
Pour trouver un point stationnaire de la log-vraisemblance, l'algorithme de Newton suit l'approximation quadratique locale. La mise à jour scalaire est définie comme :
@@ 108,7 108,7 @@
Elle divise la dérivée première par la dérivée seconde, donc le pas s'adapte automatiquement à la courbure.
-
### Mise à jour multivariée
+
### 2.4.2 Mise à jour multivariée
Avec un vecteur de paramètres $\theta \in \mathbb{R}^{n+1}$, la dérivée seconde devient la matrice hessienne $H$, avec $H_{jk}=\dfrac{\partial^2 \ell}{\partial\theta_j\,\partial\theta_k}$. La mise à jour est définie comme :
@@ 116,7 116,7 @@
*Remarque :* chaque pas résout un système linéaire en $H$, une opération en $O(n^3)$, donc l'algorithme de Newton est coûteux quand le nombre de variables $n$ est grand.
-
### Newton ou descente de gradient
+
### 2.4.3 Newton ou descente de gradient
| Propriété | Algorithme de Newton | Descente de gradient |
| --- | --- | --- |
fr/Machine Learning/03 Linear models.md ..
@@ 1,4 1,4 @@
-
# Modèles linéaires
+
# 3. Modèles linéaires
Les modèles linéaires prédisent à partir d'un score linéaire $\theta^T x$. Ce module couvre la régression linéaire (cibles continues), la régression logistique (classification binaire) et le cadre des modèles linéaires généralisés qui unifie les deux via la famille exponentielle. Chaque modèle est ajusté par maximum de vraisemblance et partage la même mise à jour par gradient.
@@ 10,21 10,21 @@
- Reconnaître la forme de la famille exponentielle et construire un MLG à partir de ses trois hypothèses.
- Retrouver les régressions linéaire, logistique et softmax comme cas particuliers.
-
## Régression linéaire
+
## 3.1 Régression linéaire
-
### Hypothèse
+
### 3.1.1 Hypothèse
L'hypothèse est linéaire en l'entrée augmentée $x \in \mathbb{R}^{n+1}$ avec $x_0 = 1$ et les paramètres $\theta \in \mathbb{R}^{n+1}$ :
$$\boxed{ h_\theta(x) = \theta^T x }$$
-
### Fonction de coût
+
### 3.1.2 Fonction de coût
Le coût est défini comme la demi-somme des carrés des résidus sur les $m$ exemples :
La descente de gradient sur $J$ donne la mise à jour des moindres carrés moyens (Widrow-Hoff), appliquée par exemple $(x^{(i)}, y^{(i)})$ :
@@ 37,7 37,7 @@
| GD par lots | somme sur les $m$ exemples | $O(mn)$ | $m$ petit à modéré |
| GD stochastique (SGD) | un exemple à la fois | $O(n)$ | $m$ grand, flux de données |
-
### Équation normale
+
### 3.1.4 Équation normale
Annuler $\nabla_\theta J(\theta) = 0$ donne une solution en forme close à partir de la matrice de conception $X$ et du vecteur cible $y$ :
@@ 45,7 45,7 @@
*Remarque :* l'équation normale ne demande ni taux d'apprentissage ni itération, mais inverser $X^T X$ coûte $O(n^3)$, donc pour $n$ grand la mise à jour itérative LMS est préférée.
-
### Interprétation probabiliste
+
### 3.1.5 Interprétation probabiliste
Supposons $y^{(i)} = \theta^T x^{(i)} + \varepsilon^{(i)}$ avec un bruit gaussien i.i.d. $\varepsilon^{(i)} \sim \mathcal{N}(0, \sigma^2)$. Maximiser la log-vraisemblance revient alors à minimiser le coût des moindres carrés :
@@ 57,9 57,9 @@
*Les moindres carrés ajustent la droite qui minimise les résidus au carré (segments gris).*
-
## Régression logistique
+
## 3.2 Régression logistique
-
### Sigmoïde
+
### 3.2.1 Sigmoïde
La fonction sigmoïde (logistique) comprime un score brut $z \in \mathbb{R}$ en une probabilité :
@@ 67,7 67,7 @@
Sa dérivée a la forme commode $g'(z) = g(z)\left(1 - g(z)\right)$.
-
### Modèle
+
### 3.2.2 Modèle
L'hypothèse renvoie la probabilité de la classe positive, $\phi$ étant la probabilité prédite :
Sur $m$ exemples i.i.d. la log-vraisemblance est l'opposé de l'entropie croisée sommée sur les données :
@@ 85,7 85,7 @@
avec $\phi^{(i)} = h_\theta(x^{(i)})$.
-
### Montée de gradient
+
### 3.2.4 Montée de gradient
Maximiser $\ell$ par montée de gradient donne la même forme que la mise à jour LMS :
@@ 93,7 93,7 @@
*Remarque :* la mise à jour a la même forme que la régression linéaire, bien que $h_\theta$ soit maintenant la sigmoïde. Ce n'est pas un hasard, les deux sont des modèles linéaires généralisés.
-
### Méthode de Newton
+
### 3.2.5 Méthode de Newton
La méthode de Newton converge plus vite près de l'optimum. En une dimension :
@@ 109,11 109,11 @@
*À gauche : la sigmoïde envoie les scores dans l'intervalle (0,1). À droite : la frontière de décision et la probabilité prédite.*
-
## Perceptron
+
## 3.3 Perceptron
Le perceptron est le premier classifieur linéaire. Il conserve le score linéaire $\theta^T x$ de la régression logistique mais remplace la sigmoïde par un seuil dur, donc la sortie est une étiquette de classe et non une probabilité. Les étiquettes valent $y \in \{0, 1\}$.
-
### Activation et hypothèse
+
### 3.3.1 Activation et hypothèse
L'activation est la fonction échelon :
@@ 123,7 123,7 @@
$$\boxed{ h_\theta(x) = g(\theta^T x) }$$
-
### Règle d'apprentissage
+
### 3.3.2 Règle d'apprentissage
Le perceptron est entraîné en ligne, un exemple à la fois, et ne corrige $\theta$ que sur un point mal classé :
@@ 135,7 135,7 @@
*Le perceptron trouve un hyperplan séparateur. Ce n'est pas nécessairement celui à marge maximale que choisira le SVM.*
-
### Convergence
+
### 3.3.3 Convergence
| données | comportement |
| --- | --- |
@@ 144,15 144,15 @@
*Remarque :* le perceptron s'arrête au premier hyperplan qui sépare les données, généralement pas celui à la marge la plus large. Cet écart motive la machine à vecteurs de support (qui maximise la marge) et, empilé en couches, le réseau de neurones (un perceptron est une unité).
-
## Modèles linéaires généralisés
+
## 3.4 Modèles linéaires généralisés
-
### Famille exponentielle
+
### 3.4.1 Famille exponentielle
Une distribution appartient à la famille exponentielle si sa densité s'écrit avec le paramètre naturel $\eta$, la statistique suffisante $T(y)$, la log-partition $a(\eta)$ et la mesure de base $b(y)$ :
Un MLG repose sur trois choix. La réponse appartient à la famille exponentielle, le paramètre naturel est linéaire en l'entrée, et la prédiction est la statistique suffisante espérée :
*Remarque :* pour la Bernoulli, $\eta$ est le log-rapport de cotes et son inverse est la sigmoïde, $\phi = g(\eta)$. C'est pourquoi la régression logistique a cette forme.
-
### Régression softmax
+
### 3.4.4 Régression softmax
Pour des étiquettes multiclasses $y \in \{1, \dots, k\}$ le MLG donne la régression softmax, avec un vecteur de paramètres $\theta_k$ par classe :
Les produits scalaires sont exactement l'endroit où l'on substitue un noyau $K$ (voir [Noyaux](/fr/Machine%20Learning/04%20Support%20Vector%20Machines#noyaux)).
+
Les produits scalaires sont exactement l'endroit où l'on substitue un noyau $K$ (voir [Noyaux](/fr/Machine%20Learning/04%20Support%20Vector%20Machines#43-noyaux)).
-
### KKT et vecteurs de support
+
### 4.4.3 KKT et vecteurs de support
À l'optimum, l'écart complémentaire lie chaque multiplicateur à sa contrainte :
@@ 189,7 189,7 @@
Ce sont les points exactement sur la marge. Tous les autres ont $\beta_i = 0$ et n'influencent pas
$w$.
-
### Décision à noyau
+
### 4.4.4 Décision à noyau
Remplacer le produit scalaire par un noyau donne une règle de décision exprimée uniquement à
travers les vecteurs de support :
@@ 199,7 199,7 @@
*Remarque :* seuls les vecteurs de support ($\beta_i > 0$) contribuent, donc le coût de prédiction
croît avec leur nombre, pas avec $m$.
-
### Du primal à la décision
+
### 4.4.5 Du primal à la décision
```mermaid
flowchart TD
fr/Machine Learning/05 Decision trees and ensemble methods.md ..
@@ 1,4 1,4 @@
-
# Arbres de décision et méthodes d'ensemble
+
# 5. Arbres de décision et méthodes d'ensemble
Les modèles d'arbre partitionnent l'espace d'entrée en régions alignées sur les axes et ajustent une constante par région, ce qui donne des prédicteurs interprétables mais à forte variance. Les méthodes d'ensemble combinent plusieurs arbres : le bagging et les forêts aléatoires moyennent des arbres construits indépendamment pour réduire la variance, tandis que le boosting construit les arbres de façon séquentielle pour réduire le biais.
@@ 9,9 9,9 @@
- Estimer gratuitement l'erreur de généralisation avec les échantillons hors-sac.
- Construire un prédicteur fort comme somme additive d'apprenants faibles (AdaBoost, gradient boosting).
-
## Arbres de décision CART
+
## 5.1 Arbres de décision CART
-
### L'arbre comme partition
+
### 5.1.1 L'arbre comme partition
Un arbre CART partitionne l'espace d'entrée en $M$ régions disjointes $R_1,\dots,R_M$ (les feuilles) et prédit une constante $c_m$ sur chacune. La prédiction est définie par
@@ 21,7 21,7 @@
*Remarque :* les régions sont des boîtes alignées sur les axes, donc la frontière de décision est en escalier. Un arbre seul a un faible biais mais une forte variance.
-
### Impureté et choix de la coupure
+
### 5.1.2 Impureté et choix de la coupure
Pour une région de proportions de classes $\hat p_k$, l'impureté mesure le mélange des étiquettes. L'indice de Gini est défini par
@@ 44,7 44,7 @@
*Remarque :* les deux critères choisissent presque toujours la même coupure. Gini est le défaut de la plupart des implémentations car il évite le logarithme.
-
### Arbres de régression
+
### 5.1.3 Arbres de régression
En régression, la valeur de la feuille est la moyenne des cibles dans la région, définie par
@@ 52,7 52,7 @@
et les coupures minimisent l'erreur quadratique intra-région plutôt qu'une impureté de classification.
-
### Élagage
+
### 5.1.4 Élagage
Un arbre non élagué ajuste exactement l'ensemble d'entraînement et surapprend. L'élagage à complexité coûteuse arbitre entre l'ajustement et la taille de l'arbre $|T|$ (le nombre de feuilles) via une pénalité $\alpha\ge0$ :
@@ 72,9 72,9 @@
*Un arbre découpe l'espace en régions alignées sur les axes, chacune à prédiction constante.*
-
## Forêts aléatoires
+
## 5.2 Forêts aléatoires
-
### Bagging
+
### 5.2.1 Bagging
Le bagging (bootstrap aggregating) entraîne $B$ arbres sur $B$ rééchantillons bootstrap des données et les moyenne. Le prédicteur agrégé est défini par
@@ 84,7 84,7 @@
Un échantillon bootstrap tire $N$ exemples avec remise parmi $N$ exemples. La probabilité qu'un exemple donné ne soit jamais tiré vaut $(1-\tfrac1N)^N\to e^{-1}\approx0{,}37$, donc environ 37 % des données restent hors de chaque arbre. Ce sont ses exemples hors-sac (OOB).
-
### Variance d'une moyenne
+
### 5.2.2 Variance d'une moyenne
Si les $B$ arbres ont chacun une variance $\sigma^2$ et une corrélation deux à deux $\rho$, la variance de leur moyenne vaut
@@ 92,7 92,7 @@
Le second terme s'annule quand $B$ croît, mais le premier, $\rho\sigma^2$, persiste. Réduire la corrélation $\rho$ entre les arbres est donc le levier clé, et c'est précisément ce que visent les forêts aléatoires.
-
### Forêts aléatoires
+
### 5.2.3 Forêts aléatoires
Une forêt aléatoire est du bagging avec sous-échantillonnage des variables : à chaque coupure, seul un sous-ensemble aléatoire de $m_{\text{try}}$ variables est considéré comme candidat. Les choix usuels sont
@@ 126,9 126,9 @@
*(a) Un arbre profond seul surajuste avec une frontière en escalier. (b) Une forêt aléatoire moyenne de nombreux arbres pour une frontière plus lisse.*
-
## Boosting
+
## 5.3 Boosting
-
### Modèle additif
+
### 5.3.1 Modèle additif
Le boosting construit un prédicteur comme une somme pondérée de $T$ apprenants faibles $h_t$ (typiquement des arbres peu profonds), ajustés un à un. Le modèle additif est défini par
@@ 136,7 136,7 @@
Chaque étape corrige les erreurs de la somme courante, donc l'ensemble est construit de façon séquentielle et réduit le biais plutôt que la variance.
-
### AdaBoost
+
### 5.3.2 AdaBoost
Avec des étiquettes $y\in\{-1,+1\}$, AdaBoost conserve des poids d'exemples $w^{(i)}$ qui se concentrent sur les points actuellement mal classés. Au tour $t$, l'apprenant faible a une erreur pondérée $\varepsilon_t$, et son coefficient est défini par
@@ 148,7 148,7 @@
puis renormalisés. Les exemples mal classés ($y^{(i)}h_t(x^{(i)})<0$) gagnent du poids, donc l'apprenant suivant se concentre sur eux.
-
### Gradient boosting
+
### 5.3.3 Gradient boosting
Le gradient boosting généralise l'idée à toute perte différentiable $L$. À l'étape $t$, il ajuste l'apprenant suivant sur l'opposé du gradient de la perte évalué au modèle courant, le pseudo-résidu défini par
