APM_4AI09/cheatsheet.md

Cours de Révision — SD-TSIA205

Apprentissage Statistique Non-Paramétrique — Synthèse Examen

Lecture des examens : Les deux examens passés (2024, 2025) portent quasi-exclusivement sur l'estimateur à noyau (densité et CDF), la décomposition biais-variance et l'optimisation du bandwidth. Ces thèmes sont à maîtriser parfaitement. Les autres chapitres (RKHS, régression, réseaux) sont du cours vu mais moins testés directement.

---

0. Panorama des Paradigmes Statistiques

	\theta déterministe	\theta aléatoire
Ensemble discret/fini	Tests d'hypothèses — Neyman-Pearson	Théorie de la décision — MAP
Dimension finie (paramétrique)	Estimation — Cramér-Rao	Bayésien — MMSE = \mathbb{E}[\theta\mid X]
Dimension infinie (non-param.)	Minimax \inf_{\hat f}\sup_{f\in\mathcal{F}}\mathbb{E}[L(\hat f,f)]	—

Compromis Biais-Variance fondamental : pour tout estimateur \hat f,

\mathbb{E}[(\hat f(x) - f(x))^2] = \underbrace{(\mathbb{E}[\hat f(x)] - f(x))^2}_{\text{Biais}^2} + \underbrace{\text{Var}(\hat f(x))}_{\text{Variance}}

---

1. Estimation de Densité par Noyau ⭐ (Cœur de l'examen)

1.1 Définition de l'estimateur

Soit X_1,\dots,X_N \overset{\text{iid}}{\sim} f. L'estimateur de Parzen-Rosenblatt est :

\boxed{\hat{f}_h(x) = \frac{1}{Nh}\sum_{n=1}^N K\!\left(\frac{x - X_n}{h}\right)}

avec K : \mathbb{R}\to\mathbb{R} un noyau vérifiant \int K(u)\,du = 1, et h > 0 la fenêtre (bandwidth).

Intuition : On "lisse" la mesure empirique \hat p = \frac{1}{N}\sum \delta_{X_n} par le noyau K_h(u) = \frac{1}{h}K(u/h) : \hat f_h = K_h * \hat p.

1.2 Calcul du Biais — Technique Taylor

L'espérance de l'estimateur est la convolution :

\mathbb{E}[\hat f_h(x)] = (K_h * f)(x) = \int K_h(x - t)\,f(t)\,dt = \int K(u)\,f(x - hu)\,du

Le biais est donc :

\text{Biais}(\hat f_h(x)) = \mathbb{E}[\hat f_h(x)] - f(x) = \int K(u)\,[f(x-hu) - f(x)]\,du

Développement de Taylor à l'ordre k de f(x-hu) en x :

f(x - hu) - f(x) = \sum_{l=1}^k \frac{(-hu)^l}{l!} f^{(l)}(x) + R_k(x, hu)

Si le noyau est d'ordre $k$ (i.e. \int u^l K(u)\,du = 0 pour l = 1,\dots,k), tous les termes en h^l disparaissent après intégration. Il reste :

\text{Biais}(\hat f_h(x)) = \int K(u)\, R_k(x, hu)\,du

Cas de l'examen 2025 (k = 2, f'' est $L$-lipschitzienne) :

Les hypothèses sont K paire (donc \int uK = 0), \int u^2 K(u)\,du = 0, \int |u^3 K(u)|\,du = C_1.

Le reste de Taylor d'ordre 2 vérifie (avec |f''(x-\theta hu) - f''(x)| \le L|\theta hu|) :

|R_2(x, hu)| = \left|\int_0^{-hu} f''(x+t)\,(-hu - t)\,dt - \frac{(hu)^2}{2}f''(x)\right| \le \frac{L}{6}|hu|^3

Donc :

\boxed{|\text{Biais}(\hat f_h(x))| \le \frac{L\,C_1}{6}\,h^3 =: \gamma_1 h^3}

Cas général (f est $s$-höldérienne, noyau d'ordre k = \lfloor s\rfloor) : |\text{Biais}| = O(h^s).

1.3 Calcul de la Variance

Par indépendance des X_n :

\text{Var}(\hat f_h(x)) = \frac{1}{N}\,\text{Var}\!\left(K_h(x - X_1)\right) \le \frac{1}{N}\,\mathbb{E}\!\left[K_h(x-X_1)^2\right]

Par changement de variable u = (x - t)/h :

\mathbb{E}[K_h(x-X_1)^2] = \int \frac{1}{h^2}K\!\left(\frac{x-t}{h}\right)^2 f(t)\,dt = \frac{1}{h}\int K(u)^2\,f(x-hu)\,du \le \frac{\|f\|_\infty}{h}\int K(u)^2\,du

Cas de l'examen 2025 (\|f\|_\infty \le f_{\max}, \int K^2 = C_2) :

\boxed{\text{Var}(\hat f_h(x)) \le \frac{f_{\max}\,C_2}{Nh} =: \frac{\gamma_2}{Nh}}

1.4 Borne sur le MSE

\text{MSE}(\hat f_h(x)) = \text{Biais}^2 + \text{Variance} \le \underbrace{\gamma_1^2\,h^{2k+2}}_{\text{Biais}^2} + \underbrace{\frac{\gamma_2}{Nh}}_{\text{Variance}} =: g(h)

Pour l'examen 2025 (k=2) :

g(h) = \gamma_1^2\, h^6 + \frac{\gamma_2}{Nh}

1.5 Fenêtre Optimale h^*

On minimise g(h) par rapport à h > 0 :

g'(h) = 0 \iff 6\,\gamma_1^2\,h^5 - \frac{\gamma_2}{Nh^2} = 0 \iff h^7 = \frac{\gamma_2}{6N\gamma_1^2}

\boxed{h^* = \left(\frac{\gamma_2}{6N\gamma_1^2}\right)^{1/7}}

Cas général (biais en h^{2s}, variance en \frac{1}{Nh}) :

h^* \asymp N^{-\frac{1}{2s+1}}

1.6 Vitesse de Convergence

En substituant h^* dans g(h^*) :

g(h^*) = \gamma_1^2\left(\frac{\gamma_2}{6N\gamma_1^2}\right)^{6/7} + \frac{\gamma_2}{N}\left(\frac{\gamma_2}{6N\gamma_1^2}\right)^{-1/7} \sim N^{-6/7}

Examen 2025 : vitesse N^{-6/7} car s=3 → \frac{2s}{2s+1} = \frac{6}{7}.

Cas général : vitesse minimax N^{-\frac{2s}{2s+1}}.

Régularité s	Vitesse	Commentaire
s = 1	N^{-2/3}	Hölder 1, biais en h^2
s = 2	N^{-4/5}	biais en h^4 (noyau ordre 2)
s = 3	N^{-6/7}	biais en h^6 (examen 2025)
s \to \infty	\to N^{-1}	vitesse paramétrique

Interprétation : Plus f est régulière (grand s), plus on approche la vitesse paramétrique 1/N. La fenêtre optimale h^* décroît avec N (on "zoome" en affinant avec plus de données).

1.7 Résumé : Propriétés des Noyaux

Un noyau K d'ordre $k$ vérifie :

1. \int K(u)\,du = 1
2. \int u^l K(u)\,du = 0 pour l = 1,\dots,k
3. \int |u^{k+1} K(u)|\,du < +\infty

Astuce : Si K est pair, la condition \int u^l K = 0 pour l impair est automatique. Il suffit d'annuler les moments pairs.

Exemples :

• Noyau rectangulaire : K(u) = \frac{1}{2}\mathbf{1}_{[-1,1]}(u) — ordre 0
• Noyau gaussien : K(u) = \frac{1}{\sqrt{2\pi}}e^{-u^2/2} — ordre 1 (pair, mais \int u^2 K \ne 0)
• Noyau d'Epanechnikov : K(u) = \frac{3}{4}(1-u^2)\mathbf{1}_{[-1,1]}(u) — ordre 1

---

2. Estimation de la CDF par Noyau ⭐ (Examen 2024)

2.1 L'estimateur

Soit k un noyau de densité et K(x) = \int_{-\infty}^x k(t)\,dt sa primitive (une CDF). L'estimateur de F est :

\hat{F}_N(x) = \frac{1}{N}\sum_{n=1}^N K\!\left(\frac{x - x_n}{h}\right)

Attention : Ici K est la primitive du noyau k, pas le noyau lui-même.

2.2 Biais comme convolution

Théorème :

\mathbb{E}[\hat F_N(x)] = (k_h * F)(x) = \int k_h(x-u)\,F(u)\,du

Preuve : Par intégration par parties (IBP) :

\int \frac{1}{h}k\!\left(\frac{x-u}{h}\right)F(u)\,du \overset{\text{IBP}}{=} \underbrace{\left[-K\!\left(\frac{x-u}{h}\right)F(u)\right]_{-\infty}^{+\infty}}_{=0} + \int K\!\left(\frac{x-u}{h}\right)f(u)\,du = \mathbb{E}[K((x-X)/h)]

Les termes au bord sont nuls car : K(-\infty)F(+\infty) = 0\cdot 1 = 0 et K(+\infty)F(-\infty) = 1\cdot 0 = 0.

2.3 Décomposition MSE

\mathbb{E}\!\left[(F(x) - \hat F_N(x))^2\right] = \text{Var}(\hat F_N(x)) + \underbrace{((k_h * F)(x) - F(x))^2}_{\text{Biais}^2}

2.4 Borne sur la Variance

Comme 0 \le K(t) \le 1, on a K(t)^2 \le K(t), donc :

\mathbb{E}[K((x-X_1)/h)^2] \le \mathbb{E}[K((x-X_1)/h)] \le 1

Par indépendance : \text{Var}(\hat F_N(x)) \le \frac{1}{N}.

2.5 Borne sur le Biais

(k_h * F)(x) - F(x) = \int k(t)\,(F(x - th) - F(x))\,dt

Preuve : Changement de variable u = th dans \int k_h(x-u)F(u)du, puis soustraction de F(x)\int k = F(x).

Par le théorème des accroissements finis |F(x-th) - F(x)| \le |f|_\infty\cdot|th| :

|(k_h * F)(x) - F(x)| \le \sup_t f(t)\cdot h \int |t|\,k(t)\,dt

2.6 MSE optimal en O(1/N)

\text{MSE} \le \frac{1}{N} + C^2 h^2 où C = \|f\|_\infty \int |t|k(t)\,dt.

En choisissant h = N^{-1/2} : \text{MSE} \le \frac{1}{N} + \frac{C^2}{N} = \frac{1+C^2}{N} = O(1/N).

Remarque clé : La vitesse 1/N pour la CDF est meilleure que pour la densité (N^{-2s/(2s+1)} < 1/N pour tout s fini). Estimer la CDF est un problème "plus facile" que d'estimer la densité.

---

3. Espaces de Régularité

3.1 Espace de Hölder \Lambda(s, L)

Pour s = k + \beta avec k \in \mathbb{N}, \beta \in (0, 1] :

\Lambda(s, L) = \left\{f : f \text{ est } k \text{ fois dérivable et } |f^{(k)}(x) - f^{(k)}(y)| \le L|x-y|^\beta\right\}

Cas importants :

• s = 1 (k=0, \beta=1) : f est $L$-lipschitzienne
• s = 2 (k=1, \beta=1) : f' est $L$-lipschitzienne
• s = 3 (k=2, \beta=1) : f'' est $L$-lipschitzienne ← examen 2025

3.2 Espace de Sobolev W^s([0,1])

W^s([0,1]) = \left\{f \in L^2([0,1]) : \sum_{k \in \mathbb{Z}} |\alpha_k|^2(1+|k|)^{2s} < +\infty\right\}

où \alpha_k = \langle f, e_k\rangle sont les coefficients de Fourier.

Ellipsoïde de Sobolev : B(s, R) = \{f \in W^s : \|f\|_{W^s} \le R\}.

Le biais de l'estimateur par projection tronqué à l'ordre M vérifie :

\text{Biais}^2 = \sum_{|k| > M}|\alpha_k|^2 \le \frac{R^2}{M^{2s}}

---

4. Estimation par Projection (Fourier)

4.1 Estimateur

Dans la base de Fourier e_k(x) = e^{2\pi ikx} :

\hat f(x) = \sum_{|k| \le M} \hat\alpha_k\, e_k(x), \qquad \hat\alpha_k = \frac{1}{N}\sum_{n=1}^N e_k(X_n)

4.2 Analyse MISE

\text{MISE} = \underbrace{\sum_{|k|>M}|\alpha_k|^2}_{\text{Biais}^2 = O(M^{-2s})} + \underbrace{\sum_{|k|\le M}\frac{\text{Var}(e_k(X))}{N}}_{\text{Variance} = O(M/N)}

Ordre optimal : M^* \asymp N^{1/(2s+1)} → MISE \asymp N^{-2s/(2s+1)} (même vitesse que le noyau).

Méthode	Paramètre	Rôle du paramètre
Projection	M (nb de modes)	\uparrow M → moins de biais, plus de variance
Noyau	h (bandwidth)	\downarrow h → moins de biais, plus de variance

---

5. Régression Non-Paramétrique

5.1 Solution de Bayes

Problème : minimiser R(f) = \mathbb{E}[(Y - f(X))^2]. La solution est :

m(x) = \mathbb{E}[Y \mid X = x] \quad \text{(espérance conditionnelle)}

Preuve : \mathbb{E}[(Y-f(X))^2] = \mathbb{E}_X[\mathbb{E}_Y[(Y-f(X))^2\mid X]]. Pour tout x fixé, le minimum en c de \mathbb{E}[(Y-c)^2\mid X=x] est c = \mathbb{E}[Y\mid X=x].

5.2 Estimateur de Nadaraya-Watson

\hat m(x) = \frac{\displaystyle\sum_{n=1}^N Y_n\, K_h(x - X_n)}{\displaystyle\sum_{n=1}^N K_h(x - X_n)} = \sum_{n=1}^N w_n(x)\, Y_n

Les poids w_n(x) = K_h(x-X_n)/\sum_i K_h(x-X_i) sont positifs et somment à 1.

Cas limites :

• h \to 0 : interpolation exacte (overfitting)
• h \to \infty : \hat m(x) = \bar Y (underfitting)

5.3 Splines de Lissage

Minimisation dans C^2([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

Résultat fondamental : la solution est une spline cubique naturelle avec nœuds en X_1,\dots,X_N. Malgré l'espace infini-dimensionnel, la solution vit dans un espace de dimension N → problème matriciel.

---

6. RKHS et Méthodes à Noyau

6.1 Noyau Défini Positif (PDS)

k : \mathcal{X}\times\mathcal{X} \to \mathbb{R} est symétrique défini positif si :

\forall (x_i)_{i=1}^n,\; \forall c \in \mathbb{R}^n,\quad \sum_{i,j} c_i c_j k(x_i, x_j) \ge 0

⟺ la matrice de Gram K_{ij} = k(x_i, x_j) est semi-définie positive (SDP).

Exemples :

• Gaussien (RBF) : k(x,x') = e^{-\gamma\|x-x'\|^2}
• Polynomial : k(x,x') = (1 + \langle x,x'\rangle)^p
• Linéaire : k(x,x') = x^T x'

Inégalité de Cauchy-Schwartz : k(x,z)^2 \le k(x,x)\cdot k(z,z).

6.2 RKHS et Propriété de Reproduction

Un espace de Hilbert \mathcal{H} est un RKHS de noyau k si :

1. k(\cdot, x) \in \mathcal{H} pour tout x
2. f(x) = \langle f, k(\cdot, x)\rangle_{\mathcal{H}} pour tout f \in \mathcal{H} (propriété de reproduction)

La feature map naturelle est \varphi(x) = k(\cdot, x), de sorte que k(x,x') = \langle\varphi(x), \varphi(x')\rangle_{\mathcal{H}}.

6.3 Théorème de Moore-Aronszajn

Pour tout noyau PDS k, il existe un unique RKHS \mathcal{H}_k dont k est le noyau reproduisant.

Construction : H_0 = \text{span}\{k(\cdot, x_i)\}, produit scalaire \langle \sum_i \alpha_i k(\cdot,x_i), \sum_j \beta_j k(\cdot,z_j)\rangle = \sum_{i,j}\alpha_i\beta_j k(x_i,z_j), puis complétion.

6.4 Théorème du Représentant (Wahba 1978)

Soit g : [0,\infty)\to\mathbb{R} strictement croissante. Toute solution de :

\min_{f\in\mathcal{H}_k} c(f(x_1),\dots,f(x_n)) + \lambda\,g(\|f\|_{\mathcal{H}_k})

admet une représentation finie :

\boxed{f_n(\cdot) = \sum_{i=1}^n \alpha_i\, k(\cdot, x_i)}

Preuve (esquisse) : Décomposer f = f_1 + f_1^\perp avec f_1 \in \text{span}\{k(\cdot,x_i)\}. Par reproduction, f(x_i) = f_1(x_i). Par Pythagore, \|f\| \ge \|f_1\|. Donc J(f_1) \le J(f) → le terme f_1^\perp est nul à l'optimum.

6.5 Kernel Ridge Regression (KRR)

Problème :

\min_{f\in\mathcal{H}_k} \frac{1}{n}\sum_i (y_i - f(x_i))^2 + \lambda\|f\|^2_{\mathcal{H}_k}

Par le théorème du représentant f(x) = \sum_i \alpha_i k(x,x_i). En notant K la matrice de Gram n\times n :

\boxed{\boldsymbol\alpha = (K + n\lambda I)^{-1} Y}

Dérivation : La loss s'écrit \frac{1}{n}\|Y - K\boldsymbol\alpha\|^2 + \lambda\boldsymbol\alpha^T K\boldsymbol\alpha. La dérivée par rapport à \boldsymbol\alpha donne K(K + n\lambda I)\boldsymbol\alpha = KY.

Cas linéaire k(x,x')=x^Tx' → K = XX^T → régression Ridge classique.

6.6 SVM à Noyau

Perte hinge : \ell(y, h(x)) = \max(1 - yh(x), 0)

Problème : \min_{h\in\mathcal{H}} \frac{1}{n}\sum_i \max(1-y_i h(x_i),0) + \lambda\|h\|^2_{\mathcal{H}}

Par le théorème du représentant : h(x) = \sum_i \alpha_i k(x,x_i). Le problème se réécrit en QP dans \mathbb{R}^n via variables d'écart \xi_i \ge 0.

Avec biais : théorème du représentant semi-paramétrique → h(x) = \sum_i \alpha_i k(x,x_i) + b.

6.7 Propriétés de Clôture

Les noyaux PDS sont stables par : somme, produit scalaire positif, produit, composition par une fonction positive, limite ponctuelle.

---

7. Fléau de la Dimension et Réseaux de Neurones

7.1 La Classe \mathcal{F}_C

\mathcal{F}_C = \left\{f \;\middle|\; \int_{\mathbb{R}^d}\|\vec\omega\|_1|F(\vec\omega)|\,d\vec\omega \le C\right\}

où F est la transformée de Fourier de f.

7.2 Écart de Kolmogorov

w_N(\mathcal{F}_C) = \inf_{\substack{H_N \text{ s.e.v.} \\ \dim H_N \le N}} \sup_{f\in\mathcal{F}_C} \|f - \text{proj}_{H_N}f\|_{L^2}

C'est l'erreur minimale d'approximation par tout sous-espace linéaire de dimension N.

7.3 Théorème (Fléau de la Dimension)

\exists\,\kappa > 0,\quad w_N(\mathcal{F}_C) \ge \kappa\,\frac{C}{d}\,N^{-1/d}

Conséquence : Pour toute méthode linéaire (polynômes, Fourier tronqué, ondelettes...), l'erreur en dimension d décroît comme N^{-1/d}. Pour d = 100, il faudrait N = 10^{100} échantillons pour atteindre une erreur de 10^{-2}.

Preuve (idée) : On construit 2N fonctions de test h_j^* = \cos(2\pi \vec k_j \cdot \vec x) normalisées pour appartenir à \mathcal{F}_C. Tout sous-espace H_N ne peut être orthogonal à toutes, donc l'une d'elles a une grande composante hors de H_N. L'argument combinatoire montre que \|\vec k_{2N}\|_1 \ge d(2N)^{1/d}.

7.4 Pourquoi les Réseaux de Neurones ?

Un réseau avec N neurones est une somme de fonctions non-linéaires :

f(x) = \sum_{j=1}^N c_j\,\sigma\!\left(\vec w_j^T \vec x + b_j\right)

Ce n'est pas un sous-espace linéaire fixé : les \vec w_j, b_j s'adaptent aux données. Les réseaux peuvent briser le fléau de la dimension pour certaines classes de régularité.

---

8. Récapitulatif Formules Clés à Retenir

Quantité	Formule	Ordre
Estimateur noyau densité	\hat f_h(x) = \frac{1}{Nh}\sum K\!\left(\frac{x-X_i}{h}\right)	—
Espérance de \hat f_h	\mathbb{E}[\hat f_h(x)] = (K_h * f)(x)	—
Biais (noyau ordre k, f \in \Lambda(s,L))	$	\text{Biais}
Variance	\text{Var}(\hat f_h(x)) \le \frac{\gamma_2}{Nh}	O(1/(Nh))
MSE = Biais² + Var	\le \gamma_1^2 h^{2s} + \frac{\gamma_2}{Nh}	—
Bandwidth optimal	h^* \asymp N^{-1/(2s+1)}	—
Vitesse minimax densité	\text{MSE}(h^*) \asymp N^{-2s/(2s+1)}	—
Vitesse estimateur CDF	\text{MSE} = O(1/N) avec h = N^{-1/2}	—
KRR	\boldsymbol\alpha = (K + n\lambda I)^{-1}Y	—

---

9. Méthodologie pour l'Examen

Étapes systématiques pour un problème d'estimateur à noyau :

1. Écrire l'estimateur — vérifier les hypothèses sur le noyau (parité, moments)
2. Calculer le biais :
   • Écrire \mathbb{E}[\hat f(x)] - f(x) = \int K(u)[f(x-hu) - f(x)]du
   • Faire le développement de Taylor jusqu'à l'ordre où les moments de K annulent les termes
   • Borner le reste par la condition de Hölder/Lipschitz
3. Calculer la variance :
   • Utiliser \text{Var}(\hat f) = \frac{1}{N}\text{Var}(K_h(x-X_1)) \le \frac{1}{N}\mathbb{E}[K_h^2(x-X_1)]
   • Changement de variable u=(x-t)/h, puis borner f par f_{\max}
4. MSE = Biais² + Variance
5. Optimiser en $h$ : dériver et annuler \frac{d}{dh}(\text{Biais}^2 + \text{Variance}) = 0
6. Analyser g(h^*) en fonction de N (vitesse de convergence)

Piège fréquent : ne pas oublier le facteur \frac{1}{N} devant la variance (indépendance des X_i).