APM_4AI09/ch2.md

Cours 2 : Théorie de la Régression

Fondamentaux, Non-paramétrique et Régularisation

---

1. Introduction et Cadre Probabiliste

L'objectif de la régression est de prédire une variable de sortie Y \in \mathbb{R} à partir d'un vecteur d'entrée X \in \mathcal{X} \subset \mathbb{R}^d.

Soit (X, Y) un couple de v.a. suivant une loi jointe inconnue de densité f_{X,Y}(x,y). On dispose d'un échantillon i.i.d. :

\mathcal{D}_N = \{(x_n, y_n)\}_{n=1}^N

On cherche une fonction de décision f : \mathcal{X} \to \mathbb{R} telle que f(X) soit une "bonne" approximation de Y.

---

2. L'approche Naïve et ses Limites

Une approche intuitive consiste à minimiser le risque empirique :

f^* = \arg\min_{f \in \mathcal{F}} \frac{1}{N} \sum_{n=1}^N |y_n - f(x_n)|^2

Le problème du sur-apprentissage (Overfitting)

Si \mathcal{F} est trop vaste (ex : toutes les fonctions continues), il existe une infinité de solutions annulant parfaitement l'erreur empirique.

• Polynôme de Lagrange : On peut construire un polynôme de degré N-1 passant par tous les points (x_n, y_n).
• Conséquence : L'erreur d'entraînement est nulle, mais la généralisation sur de nouvelles données est médiocre. C'est le phénomène de sur-apprentissage.

---

3. Caractérisation de la Solution Optimale

Définition — Fonction de régression

La solution du problème de minimisation théorique :

f^* = \arg\min_{f \in L^2(P_X)} \mathbb{E}_{X,Y}\!\left[|Y - f(X)|^2\right]

est donnée par l'espérance conditionnelle :

m(x) = \mathbb{E}[Y \mid X = x]

Preuve (approche bayésienne) : Par désintégration de la mesure :

\mathbb{E}[(Y-f(X))^2] = \mathbb{E}_X\!\left[\mathbb{E}_Y[(Y-f(X))^2 \mid X=x]\right]

Pour chaque x, le minimum de \mathbb{E}[(Y-c)^2 \mid X=x] en c est atteint pour c = \mathbb{E}[Y \mid X=x].

Modèle de bruit additif : On suppose souvent :

Y = f(X) + \varepsilon, \quad \mathbb{E}[\varepsilon \mid X] = 0, \quad \text{Var}(\varepsilon \mid X) = \sigma^2

La fonction cible est bien f(x) = \mathbb{E}[Y \mid X=x].

---

4. Méthodes d'Estimation Non-Paramétriques

4.1 Approche Heuristique : $k$-plus proches voisins ($k$-NN)

L'idée est de moyenner les réponses y_i des observations dont les x_i sont les plus proches de x. Soit \sigma_x une permutation telle que \|x - x_{\sigma_x(1)}\| \leq \dots \leq \|x - x_{\sigma_x(N)}\|.

• Si k=1 : \hat{f}(x) = y_{\sigma_x(1)} — interpolation (risque de sur-apprentissage).
• Si k=N : \hat{f}(x) = \frac{1}{N}\sum y_n = \bar{Y} — modèle constant (risque de sous-apprentissage).

4.2 Lissage par Noyau : Estimateur de Nadaraya-Watson

On cherche à estimer m(x) = \int y\, \frac{f_{X,Y}(x,y)}{f_X(x)}\, dy. En remplaçant les densités par leurs estimateurs de noyau (Parzen-Rosenblatt) :

• \hat{f}_X(x) = \frac{1}{N}\sum_{n=1}^N K_h(x - x_n)
• \hat{f}_{X,Y}(x,y) = \frac{1}{N}\sum_{n=1}^N K_h(x-x_n)\,K_h(y-y_n)

L'estimateur de Nadaraya-Watson est :

\hat{f}(x) = \sum_{n=1}^N w_n(x)\, y_n, \quad \text{où } w_n(x) = \frac{K_h(x - x_n)}{\sum_{i=1}^N K_h(x - x_i)}

Les poids w_n(x) somment à 1 et représentent l'influence relative du point n sur la prédiction en x.

---

5. Régularisation et Splines de Lissage

Pour éviter le sur-apprentissage tout en restant flexible, on restreint l'espace des solutions en ajoutant une pénalité de régularisation.

5.1 Principe de Pénalisation

\hat{f} = \arg\min_{f} \sum_{n=1}^N |y_n - f(x_n)|^2 + \lambda\, \text{Pen}(f)

• Régression Ridge : \text{Pen}(f) = \|f\|^2_{L^2} (favorise les petites normes)
• Lasso : \text{Pen}(f) = \|f\|_{L^1} (favorise la parcimonie)

5.2 Splines de Lissage

On minimise sur l'espace des fonctions deux fois dérivables sur [a, b] :

J(f) = \frac{1}{N} \sum_{n=1}^N (y_n - f(x_n))^2 + \lambda \int_a^b |f''(t)|^2\, dt

Le terme \int |f''(t)|^2\, dt pénalise la courbure de la fonction (sa "rugosité").

Définition — Spline Cubique

Une fonction S est une spline cubique sur une partition a = t_0 < t_1 < \dots < t_p = b si :

1. S est un polynôme de degré \leq 3 sur chaque intervalle [t_n, t_{n+1}].
2. S est de classe C^2 sur [a, b].

Résultat fondamental : La solution du problème J(f) est unique et est une spline cubique naturelle dont les nœuds sont situés aux points d'observation x_1, \dots, x_N. Bien que l'espace C^2 soit de dimension infinie, la solution appartient à un espace de dimension finie N, ce qui rend le calcul possible par algèbre linéaire.