# Reproducing Kernel Hilbert Space (RKHS)

## 1. Définition du Noyau (Kernel)

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).

### Propriété Définie Positive (PDS)
Un noyau $k$ est dit défini positif si :
$$\forall (x_{1}, \dots, x_{n}) \in \mathcal{X}^{n}, \forall c \in \mathbb{R}^{n}, \sum_{i=1}^{n} \sum_{j=1}^{n} c_{i} c_{j} k(x_{i}, x_{j}) \geq 0$$

> **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.

---

## 2. Noyau Reproduisant

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 :

1.  **Appartenance :** $\forall x \in \mathcal{X}, k(\cdot, x) \in H$
2.  **Propriété de reproduction :** $\forall f \in H, \forall x \in \mathcal{X}, f(x) = \langle f, k(\cdot, x) \rangle_{H}$

L'espace $H$ est alors appelé l'**Espace de Hilbert à Noyau Reproduisant (RKHS)** associé à $k$.

> **Remarque :** En appliquant la propriété de reproduction à la fonction $f = k(\cdot, x')$, on obtient :
> $$k(x, x') = \langle k(\cdot, x), k(\cdot, x') \rangle_{H}$$

---

## 3. Exemples de Noyaux PDS

Voici deux exemples classiques de noyaux utilisés en apprentissage automatique :

* **Noyau Gaussien (RBF) :** $k(x, x') = \exp(-\gamma \|x - x'\|^2)$ avec $\gamma > 0$
* **Noyau Polynomial :** $k(x, x') = (1 + \langle x, x' \rangle)^{p}$ avec $p \in \mathbb{N}$

---

## 4. Théorème de Moore-Aronszajn (1943)

Ce théorème fondamental établit la relation entre les noyaux PDS et les espaces de Hilbert.

Soit $k$ un noyau défini positif sur $\mathcal{X}$.

1.  **Existence :** Il existe un espace de Hilbert $H$ et une application (feature map) $\Phi: \mathcal{X} \to H$ tels que :
    $$\forall x, x' \in \mathcal{X}, k(x, x') = \langle \Phi(x), \Phi(x') \rangle_{H}$$
2.  **Unicité :** Il existe un unique espace de Hilbert $H_k$ tel que $k$ soit son noyau reproduisant. Cet espace possède les propriétés :
    * $\forall x \in \mathcal{X}, k(\cdot, x) \in H_k$
    * $\forall f \in H_k, \forall x \in \mathcal{X}, f(x) = \langle f, k(\cdot, x) \rangle_{H_k}$


### Proof (constructive)

**Étape 1 — Pré-espace de Hilbert $H_0$**

On définit l'espace des combinaisons linéaires finies de noyaux :

$$H_0 = \left\{ f : \mathcal{X} \to \mathbb{R} \;\middle|\; \exists\, (\alpha_i)_{i \in I} \in \mathbb{R}^{|I|},\; f(x) = \sum_{i \in I} \alpha_i k(x, x_i),\; x_i \in \mathcal{X},\; |I| < \infty \right\}$$

Pour $f(\cdot) = \sum_{i \in I} \alpha_i k(\cdot, x_i)$ et $g(\cdot) = \sum_{j \in J} \beta_j k(\cdot, z_j)$, on définit le produit scalaire :

$$\langle f, g \rangle_{H_0} := \sum_{i \in I,\, j \in J} \alpha_i \beta_j k(x_i, z_j)$$

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$ :

$$\langle f, k(\cdot, x) \rangle_{H_0} = \left\langle \sum_i \alpha_i k(\cdot, x_i),\, k(\cdot, x) \right\rangle = \sum_i \alpha_i k(x_i, x) = f(x)$$

**Étape 3 — Complétion en espace de Hilbert**

$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 :

$$|f_p(x) - f_q(x)| = |\langle f_p - f_q, k(\cdot, x) \rangle| \leq \|f_p - f_q\| \sqrt{k(x,x)}$$

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 :

$$\langle f, g \rangle_{\mathcal{H}} = \lim_{n \to \infty} \langle f_n, g_n \rangle_{H_0}$$

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 :

| Opération | Feature map associée |
|---|---|
| a) $K_1(x,y) + K_2(x,y)$ | $\Phi(x) = (\Phi_1(x), \Phi_2(x))^T$ |
| b) $\alpha K_1(x,y)$ pour $\alpha > 0$ | $\Phi(x) = \sqrt{\alpha}\Phi_1(x)$ |
| c) $K_1(x,y) K_2(x,y)$ | $\Phi(x)_{ij} = \Phi_1(x)_i \Phi_2(x)_j$ (produit tensoriel) |
| d) $f(x) f(y)$ pour toute $f$ | $\Phi(x) = f(x)$ |
| e) $x^T A y$ pour $A \succeq 0$ | $\Phi(x) = L^T x$ pour $A = LL^T$ (Cholesky) |

> De ces propriétés, on déduit que tout polynôme de noyaux est encore un noyau, et que la limite ponctuelle de noyaux est aussi un noyau.

---

## 6. Inégalité de Cauchy-Schwartz pour les noyaux

Soit $k$ un noyau PDS. Alors $\forall (x, z) \in \mathcal{X}^2$ :

$$k(x, z)^2 \leq k(x, x)\, k(z, z)$$

**Preuve :** La matrice de Gram $K = \begin{pmatrix} k(x,x) & k(x,z) \\ k(z,x) & k(z,z) \end{pmatrix}$ est SDP, donc $\det(K) = k(x,x)k(z,z) - k(x,z)^2 \geq 0$.

---

## 7. Espace des features et feature map

Tout espace de Hilbert $\mathcal{H}$ pour lequel il existe $\varphi : \mathcal{X} \to \mathcal{H}$ avec :
$$\forall (x, x') \in \mathcal{X} \times \mathcal{X},\quad k(x, x') = \langle \varphi(x), \varphi(x') \rangle_{\mathcal{H}}$$
est appelé **espace des features** associé à $k$, et $\varphi$ est appelée **feature map**.

Le RKHS $\mathcal{H}_k$ est le plus petit espace des features associé à $k$, avec $\varphi(x) = k(\cdot, x)$.

$$\mathcal{H}_k = \overline{\text{Span}\{\varphi(x) = k(\cdot, x) : x \in \mathcal{X}\}} \subset \mathcal{F}(\mathcal{X}, \mathbb{R})$$

---

# Apprentissage avec les noyaux

## 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 :

$$\min_{f \in \mathcal{H}} \mathbb{E}_\mu[\ell(Y, f(X))]$$

En pratique, on ne peut pas minimiser le risque vrai $R(f) := \mathbb{E}[\ell(Y, f(X))]$. On le remplace par le **risque empirique** :

$$R_n(f) := \frac{1}{n} \sum_{i=1}^n \ell(y_i, f(x_i))$$

Pour contrôler la complexité du modèle et éviter le sur-apprentissage, on résout un problème de **minimisation du risque empirique régularisé** :

$$\arg\min_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n \ell(y_i, h(x_i)) + \lambda \Omega(h)$$

où $\Omega : \mathcal{H} \to \mathbb{R}^+$ est une fonction de régularisation et $\lambda > 0$ un hyperparamètre. La variante contrainte s'écrit :

$$\arg\min_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n \ell(y_i, h(x_i)) \quad \text{s.t. } \Omega(h) \leq C$$

**Exemples de pertes :**
- Classification binaire : $\ell(y, f(x)) = \mathbf{1}_{y \neq f(x)}$
- Régression : $\ell(y, f(x)) = (y - f(x))^2$

---

## 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 :

$$J(f) = c(x_1, \dots, x_n, f(x_1), \dots, f(x_n)) + \lambda g(\|f\|_{\mathcal{H}_k})$$

admet une solution de la forme :

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

### Preuve

Soit $\mathcal{H}_1 = \text{span}\{k(x_i, \cdot),\, i = 1, \dots, n\}$. Tout $f \in \mathcal{H}$ s'écrit $f = f_1 + f_1^\perp$ avec $f_1 \in \mathcal{H}_1$ et $f_1^\perp \in \mathcal{H}_1^\perp$.

Par la propriété de reproduction : $f(x_i) = \langle f(\cdot), k(x_i, \cdot) \rangle = \langle f_1(\cdot), k(x_i, \cdot) \rangle = f_1(x_i)$

Donc $c(f(x_1), \dots, f(x_n)) = c(f_1(x_1), \dots, f_1(x_n))$.

Par orthogonalité : $\|f\|^2 = \|f_1\|^2 + \|f_1^\perp\|^2 \geq \|f_1\|^2$

Comme $g$ est strictement croissante : $g(\|f\|) \geq g(\|f_1\|)$, avec égalité si et seulement si $f_1^\perp = 0$.

Ainsi $J(f_1) \leq J(f)$, et tout minimiseur de $J$ vérifie $f_1^\perp = 0$, i.e. $f = f_1 = \sum_i \alpha_i k(\cdot, x_i)$.

---

# Régression Ridge à Noyau (Kernel Ridge Regression)

## 1. Régression ridge linéaire

La régression ridge linéaire dans $\mathbb{R}^d$ avec régularisation $\ell_2$ :

$$\arg\min_{\beta \in \mathbb{R}^d} L(\beta) := \frac{1}{n} \sum_{i=1}^n (y_i - \beta^T x_i)^2 + \lambda \|\beta\|^2$$

soit encore (en notant $\mathbf{y}$ le vecteur des $y_i$) :

$$\arg\min_{\beta \in \mathbb{R}^d} \frac{1}{n}(\mathbf{y} - X\beta)^T(\mathbf{y} - X\beta) + \lambda \beta^T \beta$$

La condition du premier ordre donne :

$$\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$ :

$$\arg\min_{f \in \mathcal{H}_k} L(f) := \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=1}^n \alpha_i k(x, x_i)$.

En notant $K$ la matrice de Gram $n \times n$ (avec $K_{ij} = k(x_i, x_j)$), le problème se réécrit :

$$L(\boldsymbol{\alpha}) = \frac{1}{n}\|Y - K\boldsymbol{\alpha}\|^2 + \lambda \boldsymbol{\alpha}^T K \boldsymbol{\alpha} = \frac{1}{n}(Y - K\boldsymbol{\alpha})^T(Y - K\boldsymbol{\alpha}) + \lambda \boldsymbol{\alpha}^T K \boldsymbol{\alpha}$$

### Condition du premier ordre

$$\frac{\partial L}{\partial \boldsymbol{\alpha}} = -\frac{1}{n}K(Y - K\boldsymbol{\alpha}) + \lambda K\boldsymbol{\alpha} = -\frac{1}{n}KY + \frac{1}{n}K^2\boldsymbol{\alpha} + \lambda K\boldsymbol{\alpha} = 0$$

ce qui donne $K(K + n\lambda I)\boldsymbol{\alpha} = KY$, donc :

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

$(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 :

$$\boldsymbol{\alpha}_{\text{ridge}} = (XX^T + n\lambda I)^{-1} Y$$

ce qui correspond bien à la formule duale de la régression ridge linéaire.

## 3. Sélection des hyperparamètres

Les hyperparamètres sont $\lambda$ (et $\sigma$ si le noyau gaussien est utilisé). Les méthodes de sélection sont :

- **Validation croisée** (cross-validation)
- **Leave-One-Out (LOO)** — cas particulier de la validation croisée

L'estimateur de **Validation Croisée Généralisée (GCV)**, introduit par Grace Wahba (1978), est une approximation de l'estimateur LOO :

$$GCV_\lambda(K, y) = n \cdot \frac{y^T(K + \lambda I)^{-2} y}{\text{Tr}((K + \lambda I)^{-1})^2}$$

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$$

## 2. Perte hinge

On utilise la **perte hinge** :

$$\ell_{\text{hinge}}(y, h(x)) = \max(1 - yh(x), 0)$$

qui est une borne supérieure convexe de la perte 0-1 non continue.

## 3. Formulation dans le RKHS

On résout le problème de minimisation du risque empirique régularisé avec perte hinge :

$$\arg\min_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n \max(1 - y_i h(x_i), 0) + \lambda \|h\|^2_{\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$ :

$$\arg\min_{\boldsymbol{\alpha} \in \mathbb{R}^n} \frac{1}{n} \sum_{i=1}^n \max(1 - y_i (K\boldsymbol{\alpha})_i, 0) + \lambda \boldsymbol{\alpha}^T K \boldsymbol{\alpha}$$

On introduit des **variables d'écart** $\xi_1, \dots, \xi_n \in \mathbb{R}$ pour reformuler le problème :

$$\min_{\boldsymbol{\alpha} \in \mathbb{R}^n,\, \boldsymbol{\xi} \in \mathbb{R}^n} \frac{1}{n} \sum_{i=1}^n \xi_i + \lambda \boldsymbol{\alpha}^T K \boldsymbol{\alpha}$$

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é :

$$c(x_1, \dots, x_n, \tilde{f}(x_1), \dots, \tilde{f}(x_n)) + g(\|f\|_{\mathcal{H}_k})$$

admet une représentation de la forme :

$$\tilde{f}_n(\cdot) = \sum_{i=1}^n \alpha_i k(\cdot, x_i) + \sum_{p=1}^M \beta_p \psi_p(\cdot)$$

avec des coefficients $\beta_p$ uniques.

Dans le cas du SVM avec biais, on pose $M = 1$ et $\psi_1 \equiv 1$ (fonction constante), ce qui donne bien $f(x) = \sum_i \alpha_i k(x, x_i) + b$.
