Soit $\mathcal{X}$ un ensemble non vide. Un noyau est une fonction $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ qui doit être **symétrique** et **définie positive** (PDS).
> **Matrice de Gram :** Pour un ensemble de points donnés, on définit la matrice $K$ par ses éléments $K_{i, j} = k(x_{i}, x_{j})$. La condition ci-dessus revient à dire que la matrice $K$ est semi-définie positive.
Soit $H$ un espace de Hilbert composé de fonctions à valeurs réelles $f: \mathcal{X} \to \mathbb{R}$, doté du produit scalaire $\langle \cdot, \cdot \rangle_{H}$. La fonction $k$ est un **noyau reproduisant** si elle vérifie les deux conditions suivantes :
On remarque que $\langle f, g \rangle_{H_0} = \sum_{j \in J} \beta_j f(z_j) = \sum_{i \in I} \alpha_i g(x_i)$, ce qui montre que ce produit ne dépend pas du choix de développement de $f$ ou $g$. De plus, $\langle f, f \rangle_{H_0} \geq 0$ (la matrice de Gram est SDP) et $\langle f, f \rangle_{H_0} = 0 \Leftrightarrow f = 0$.
**Étape 2 — Norme et propriété de reproduction**
On définit $\|f\|^2_{H_0} := \langle f, f \rangle_{H_0} = \sum_{i,j \in I} \alpha_i K_{ij} \alpha_j = \boldsymbol{\alpha}^T K \boldsymbol{\alpha}$, où $K$ est la matrice de Gram.
La propriété de reproduction est vérifiée dans $H_0$ :
$H_0$ est un pré-espace de Hilbert. On le complète par les limites de suites de Cauchy. Pour une suite de Cauchy $(f_n)_n$ dans $H_0$, la convergence ponctuelle est assurée car :
donc $f(x) := \lim_{n \to \infty} f_n(x)$ existe pour tout $x \in \mathcal{X}$.
**Étape 4 — Construction de $\mathcal{H}$**
On pose $\mathcal{H} = \{\text{limites ponctuelles de suites de Cauchy de } H_0\}$, avec $H_0 \subset \mathcal{H}$. Pour deux fonctions $f, g \in \mathcal{H}$ limites ponctuelles de $(f_n) \in H_0$ et $(g_n) \in H_0$, on définit :
Cette limite existe et ne dépend que de $f$ et $g$ (par Cauchy-Schwartz). La propriété de reproduction s'étend à $\mathcal{H}$ : $\lim_{n \to \infty} \langle f_n, k(\cdot, x) \rangle = \lim_{n \to \infty} f_n(x) = f(x)$.
**Unicité :** Si $\mathcal{H}'$ est un autre RKHS de noyau reproduisant $k$, alors $H_0 \subset \mathcal{H}'$ et par densité et complétude, $\mathcal{H}' = \mathcal{H}$.
> **Résultat intermédiaire :** Toute suite de Cauchy $(f_n)_n \in H_0$ qui converge ponctuellement vers $0$ vérifie $\lim_{n \to \infty} \|f_n\|_{\mathcal{H}} = 0$.
---
## 5. Propriétés de clôture des noyaux
Les noyaux PDS sont stables par les opérations suivantes :
## 1. Cadre statistique de l'apprentissage supervisé
Soit $\mathcal{S} = \{(x_i, y_i)\}_{i=1}^n$ un échantillon i.i.d. issu d'une distribution jointe $\mu$ sur $(X, Y)$, avec $X \in \mathbb{R}^d$ et $Y \in \mathbb{R}$.
**Problème d'apprentissage supervisé :** Étant donnée une fonction de perte $\ell : \mathbb{R} \times \mathbb{R} \to \mathbb{R}^+$, on cherche :
## 2. Théorème du Représentant (Representer Theorem)
**Théorème (Wahba, 1978 ; Schoelkopf et al., 2001)**
Soit $\{x_1, \dots, x_n\}$ un ensemble de points de $\mathcal{X}$, $\lambda > 0$, $k$ un noyau PDS symétrique et $\mathcal{H}_k$ le RKHS associé. Pour $g : [0, \infty[ \to \mathbb{R}$ strictement croissante et $c : (\mathcal{X} \times \mathbb{R})^n \to \mathbb{R} \cup \{+\infty\}$ toute fonction de coût, toute fonction $f \in \mathcal{H}_k$ minimisant :
$$\frac{\partial L(\beta)}{\partial \beta} = 0 \iff \beta_{\text{ridge}} = (X^T X + \lambda n I)^{-1} X^T \mathbf{y}$$
On remarque que $\beta_{\text{ridge}} = X^T (XX^T + \lambda n I_n)^{-1} \mathbf{y} =: X^T \boldsymbol{\alpha}_{\text{ridge}}$ avec $\boldsymbol{\alpha}_{\text{ridge}} := (XX^T + \lambda n I_n)^{-1} \mathbf{y}$.
## 2. Application au noyau : Kernel Ridge Regression
On cherche à résoudre le problème de régression ridge dans $\mathcal{H}_k$ :
$(K + \lambda I)$ est inversible dès que $\lambda > 0$ (car $K \succeq 0$).
**Unicité :** Si $\boldsymbol{\alpha}' = \boldsymbol{\alpha} + \epsilon$ avec $K\epsilon = 0$, alors $\|f_{\alpha'} - f_\alpha\|^2 = \epsilon^T K \epsilon = 0$, donc la solution est unique.
> **Remarque :** En pratique, on évite l'inversion d'une matrice $n \times n$ en utilisant une **approximation de faible rang** ou la **descente de gradient stochastique**.
### Cas linéaire
Si $k(x, x') = x^T x'$ (noyau linéaire), alors $K = XX^T$ et :
Cet estimateur est uniformément consistant (voir Misiakiewicz et Saaed, 2024).
---
# SVM revisité
## 1. Classification binaire avec noyau
Soit $\mathcal{S} = \{(x_i, y_i)\}_{i=1}^n$ avec $y_i \in \mathcal{Y} = \{-1, +1\}$. On choisit un noyau PDS $k$ sur $\mathcal{X}$ et on définit $\mathcal{H}_k$ le RKHS associé. On considère des modèles binaires de la forme :
$$f(x) = \text{sign}(h(x)), \quad h \in \mathcal{H}_k$$
Par le théorème du représentant, $h(x) = \sum_{i=1}^n \alpha_i k(x, x_i) = \sum_{i=1}^n \alpha_i \varphi(x_i)$. Le problème se réécrit dans $\mathbb{R}^n$ :
sous les contraintes $\xi_i \geq 1 - y_i (K\boldsymbol{\alpha})_i$ et $\xi_i \geq 0$.
Il s'agit d'un **problème d'optimisation quadratique avec contraintes affines**, résolu via :
- Définition du Lagrangien et des coefficients lagrangiens
- Conditions d'optimalité du premier ordre (KKT)
- Réécriture du Lagrangien en fonction des multiplicateurs
- Résolution par un solveur convexe
> **Remarque :** En pratique, on prend $f(x) = \text{sign}(h(x) + b)$ avec $b \in \mathbb{R}$, ce qui nécessite un **théorème du représentant semi-paramétrique**.
## 4. Théorème du représentant semi-paramétrique
**Théorème 5 (Schoelkopf et al., 2001)**
Supposons qu'en plus des conditions du théorème du représentant général, on dispose d'un ensemble de $M$ fonctions réelles $\{\psi_p\}_{p=1}^M$ sur $\mathcal{X}$, telles que la matrice $n \times M$ $(\psi_p(x_i))_{ip}$ soit de rang $M$. Alors toute $\tilde{f} := f + h$, avec $f \in \mathcal{H}_k$ et $h \in \text{span}(\psi_p)$, minimisant le risque régularisé :
