APM_4AI09/RKHS.md

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.