Skip to main content

Section 3.4 Régression à Noyau

La méthode la régression a Noyau est la méthode historique pour passer au cas nonlinéaire. Elle a été depuis supplantée par les réseaux de neurones, mais reste efficace pour un certains nombre de problèmes.

Subsection 3.4.1 Fonction de re-description

Lors des sections précédentes on a introduit la régression linéaire qui nous permet de construire un modèle linéaire paramétré à partir de données. Dans de nombreuses applications (notamment celles qui nous occupent) l’hypothèse qu’on cherche à approcher une fonction linéaire ou quasi linéaire est trop restrictive. On a besoin d’approcher des problèmes nonlinéaires. Une première approche a été d’introduire une régression polynomiale. Cependant pour des données en grande dimension (\(d >>1\)) cette approche devient très compliquée à mettre en oeuvre, car le nombre de coefficients explose avec la dimension.
On va donc introduire une autre approche appelée régression à noyau. Dans un premier temps on va introduire la notion de fonction et d’espace de re description. Une idée naturelle pour construire une approximation nonlinéaire est de se ramener à un problème connu. Puisqu’on sait traiter le cas linéaire peut qu’on se ramener un problème linéaire ?

Définition 3.65.

Soit \(f(x):\mathbb{R}^d\rightarrow \mathbb{R}\text{.}\) Soit \(\phi(x):\mathbb{R}^d\rightarrow H\) avec \((H,\langle .\rangle)\) un espace de Hilbert (de dimension finie ou infinie). On dit que \(\phi\) est une une fonction de re-description et \(H\) l’espace de re-description associé si
\begin{equation*} f(x)=\langle\theta,\phi(x)\rangle_{H} \end{equation*}
On voit qu’une fonction de re-description est juste une transformation qui rend notre fonction linéaire. Si on connaît \(\phi\) on voit donc qu’on peut proposer une régression linéaire pour construire une approximation de \(f\text{.}\) Il est important de noter que cette transformation peut changer la dimension des données.
La fonction de re description \(\phi(x)\) peut envoyer \(x\) dans un espace de dimension infini. Par conséquent à chaque \(x\) la fonction peut associer une fonction.

Exemple 3.66.

On considère la fonction
\begin{equation*} f(x_1,x_2)=2x_1^2 +\frac12x_2^2-\sqrt{2}x_1x_2 \end{equation*}
Donner une fonction de re description ?
Solution 1.
On prend \(\phi(x): \mathbb{R}^2 \rightarrow (\mathbb{R}^3,\langle . \rangle_{\mathbb{R}^3}) \) avec
\begin{equation*} \phi(x)=\begin{cases} x_1^2 \\ x_2^2 \\ \sqrt{2}x_1x_2 \end{cases} \end{equation*}
Dans ce cas on peut écrire \(f\) sous la forme:
\begin{equation*} f(x)= \Biggl \langle\begin{pmatrix} 2\\ \frac12 \\ -1 \end{pmatrix}, \begin{pmatrix} x_1^2\\ x_2^2 \\ \sqrt{2}x_1x_2 \end{pmatrix} \Biggr \rangle \end{equation*}
Toujours supposant qu’on connait \(\phi\text{,}\) on peut appliquer la régression linéaire sous sa forme primale Proposition 3.19 ou duale Proposition 3.21 aux données pré-traitées en appliquant \(\phi\text{.}\) On peut récapituler la régression linéaire et l’approche avec fonctions de re-description à l’aide du tableau suivant
Régression linéaire: \(f(x)=\langle w, x\rangle_{\mathbb{R}^{d+1}}\)
Régression non-linéaire: \(f(x)=\langle w, \phi(x)\rangle_{\mathbb{R}^{d+1}}\)
Théorème: Il existe \((\alpha_{1}, ..., \alpha_n)\in\mathbb{R}^n\) tels que
\begin{equation*} \theta=\sum_{i=1}^n \alpha_{i}x_i \end{equation*}
Preuve: formulation duale Proposition 3.21 appliquées aux données \((x_1,... ,x_n)\text{.}\)
Théorème: Il existe \((\alpha_{1}, ..., \alpha_{n})\in\mathbb{R}^n\) tels que
\begin{equation*} \theta=\sum_{i=1}^n \alpha_{i}\phi(x_i) \end{equation*}
Preuve: formulation duale Proposition 3.21 appliquées aux données \((\phi(x_1),... ,\phi(x_n))\text{.}\)
Prédiction:
\begin{equation*} f(x)=\sum_{i=1}^n\alpha_{i}\langle x_i, x\rangle_{\mathbb{R}^{d+1}} \end{equation*}
Prédiction:
\begin{equation*} f(x)=\sum_{i=1}^n\alpha_{i}\langle \phi(x_i), \phi(x)\rangle_{H} \end{equation*}
On voit donc que si on détermine \(\phi\) on peut a priori facilement calculer notre approximation de fonction. Cependant il existe des défauts à l’approche:
  1. il faut calculer le produit scalaire dans l’espace de re description \(H\) ce qui peut être coûteux si \(H\) est de grande dimension. Si on est en dimension infini on n’a pas de solution naturelle.
  2. Il n’y a pas unicité de \(\phi\text{.}\) Comment peut-on le choisir ?

Exemple 3.67.

On considère la fonction
\begin{equation*} f(x_1,x_2)=2x_1^2 +\frac12x_2^2-\sqrt{2}x_1x_2 \end{equation*}
Donner deux fonctions de re description ?
Solution 2.
On prend \(\phi_1(x): \mathbb{R}^2 \rightarrow (\mathbb{R}^3,\langle . \rangle_{\mathbb{R}^3}) \) avec
\begin{equation*} \phi_1(x)=\begin{cases} x_1^2 \\ x_2^2 \\ \sqrt{2}x_1x_2 \end{cases} \end{equation*}
et \(\phi_2(x): \mathbb{R}^2 \rightarrow (\mathbb{R}^4,\langle . \rangle_{\mathbb{R}^4}) \) avec
\begin{equation*} \phi_2(x)=\begin{cases} x_1^2 \\ x_2^2 \\ x_1x_2\\ x_2x_1\\ \end{cases} \end{equation*}

Subsection 3.4.2 Fonctions Noyaux

Un des problèmes principaux de l’approche précédente est le calcul du produit scalaire dans l’espace de re description. En effet on a vu que si on sait calculer ce produit scalaire efficacement il est possible de calculer un problème de régression. On va voir qu’il est possible d’introduire une méthode pour construire des fonctions de re descriptions doit le produit scalaire avec elle même est facilement calculable. On parle de l’astuce des noyaux(kernel tric).

Définition 3.68. Fonction noyau.

Soit un ensemble \(V\) d’éléments de \(\mathbb{R}^d\) (fini ou indénombrable). Une fonction \(k: V \times V \rightarrow \mathbb{R}\) est une un noyau si il existe un espace de Hilbert \((H,\langle ,\rangle_H)\) et une fonction de re-description \(\phi: V\rightarrow H\) tel que:
\begin{equation*} k(x,y)=\langle \phi(x),\phi(y)\rangle_H, \quad \forall x,y\in V \end{equation*}
On remarque immédiatement que si une telle fonction existe on peut rapidement évaluer le produit scalaire \(\langle \phi(x),\phi(y)\rangle_H\) en évaluant \(k(x,y)\text{.}\) On pourrait donc facilement évaluer notre problème de régression. Cette définition nous donne immédiatement un exemple de noyau \(k(x,y)=\langle x, y\rangle\text{.}\)

Preuve.

La preuve est rapide. Par définition
\begin{equation*} \sum_{i=1}^n \sum_{j=1}^n a_i a_j k(x_i,x_j)=\sum_{i=1}^n \sum_{j=1}^n a_i a_j \langle \phi(x_i),\phi(y_i)\rangle_H \end{equation*}
ce qui donne
\begin{equation*} \sum_{i=1}^n \sum_{j=1}^n a_i a_j k(x_i,x_j)= \Biggl \langle \sum_{i=1}^n a_i \phi(x_i),\sum_{i=1}^n a_j \phi(y_j)\Biggr \rangle_H \end{equation*}
et donc par définition d’un produit de scalaire dans un espace de Hilbert
\begin{equation*} \sum_{i=1}^n \sum_{j=1}^n a_i a_j k(x_i,x_j)= \Norm \sum_{i=1}^n a_i \phi(x_i)\Norm_H\ge 0 \end{equation*}
Nous avons introduit une notion celle de noyau qui nous permettrait de calculer rapidement le produit scalaire dans l’espace de re-description. Cependant il reste des questions en suspend.
  1. comment construire un noyau ?
  2. quel sont l’espace et la fonction de re description associés ?
En effet, pour un noyau donné il n’y a pas a priori unicité de \(\phi\) et de \(H\text{.}\)

Exemple 3.70.

On se donne le noyau
\begin{equation*} k(x,y)=\langle x,y\rangle \end{equation*}
Donner deux fonctions de re-description ?
Solution.
On prend \(\phi_1(x): \mathbb{R}^2 \rightarrow (\mathbb{R}^3,\langle . \rangle_{\mathbb{R}^3})\) avec
\begin{equation*} \phi_1(x)=\begin{cases} x_1^2 \\ x_2^2 \\ \sqrt{2}x_1x_2 \end{cases} \end{equation*}
et \(\phi_2(x): \mathbb{R}^2 \rightarrow (\mathbb{R}^4,\langle . \rangle_{\mathbb{R}^4})\) avec
\begin{equation*} \phi_2(x)=\begin{cases} x_1^2 \\ x_2^2 \\ x_1x_2\\ x_2x_1\\ \end{cases} \end{equation*}
L’enjeu maintenant va être de caractériser les noyaux et les espace de re description associés.

Subsection 3.4.3 Espace de Hilbert a noyau reproduisant

On va commencer par caractériser les fonctions noyaux. Pour cela on va introduit différents théorèmes pour obtenir cette caractérisation. Tous ces théorèmes vont avoir pour objectif de prouver la contraposée de la proposition Proposition 3.69 qui va constituer le théorème suivant:
Ce théorème nous permet de construire automatiquement des noyaux et donc de pouvoir établir une régression non linéaire (qu’on détaillera dans la section suivante). On ne va pas démontrer ce théorème général directement. On va le démonter dans trois cas
  1. \(V\) est un ensemble fini
  2. \(V\) est un espace métrique compact
  3. \(V\) est un espace métrique général
Les deux derniers cas vont nous obliger d’introduire un certain nombre d’outils.

Subsubsection 3.4.3.1 Cas de \(V\) fini

On commence par le cas le plus simple. Celui ou notre ensemble de départ est fini. On pose \(V=\left\{x_1,....,x_n\right\}\text{.}\)
Preuve.
On considère la matrice symétrique \(K\) tel que \(K_{ij}=k(x_i,x_j)\text{.}\) Puisque la fonction \(k\) est définie positive alors on a
\begin{equation*} \sum_{i=1}^n \sum_{j=1}^n a_i a_j K_{ij}\ge 0, \quad \forall (a_1,...,a_n)\in \mathbb{R}^n \end{equation*}
cela revient à
\begin{equation*} \langle K\bs{a},\bs{a}\rangle \ge 0, \quad \forall \bs{a}\in \mathbb{R}^n \end{equation*}
On a donc une matrice diagonalisable dans une base orthonormée à valeurs propres positives. On a donc
\begin{equation*} K= P^{-1}DP \end{equation*}
Puisque la base est orthonormée on a \(P^{-1}=P^t\) et donc \(K=P^t D P\) On a donc
\begin{equation*} K_{ij}=k(x_i,x_j)=\sum_{k=1}\lambda_k P_{ik}P_{jk}=\langle \phi(x_i),\phi(x_j) \rangle_{\mathbb{R}^n} \end{equation*}
avec
\begin{equation*} \phi(x_i)=\begin{pmatrix} \sqrt{\lambda_1}p_{i1} \\ \vdots \\\sqrt{\lambda_n}p_{in} \end{pmatrix} \end{equation*}

Subsubsection 3.4.3.2 Cas \(V\) compact

On va maintenant considérer que \(V\) est un espace compact de \(\mathbb{R}^d\text{.}\) Il s’agit donc d’un intervalle fermé borné. On va maintenant considérer des fonctions continue
\begin{equation*} k: V \times V \rightarrow \mathbb{R} \end{equation*}
Dans le cas de \(V \) on a opérateur \(k\) qui est une matrice et on a démontré que semi-définie positif impliquait que ce soit un noyau en utilisant une diagonalision de la matrice. Dans le cadre d’un espace compact, on va procéder de façon similaire en construisant un opérateur continue et en le "diagonalisant" à l’aide du théorème de décomposition spectral des opérateurs auto adjoints. On appellera les noyaux de ce type des noyaux de Mercer.
Définition 3.73.
Soit \(H\) un espace de Hilbert. \(L\) est un opérateur linéaire si c’est une application linéaire continue de \(H\) dans \(H\text{.}\) Ce type d’opérateur est dit
  1. compact si pour toute suite bornée \(\left\{f_n\right\}_{n=1}^{\infty}\) de \(H\) alors la suite \(\left\{L f_n\right\}_{n=1}^{\infty}\) possède une sous suite converge,
  2. auto-adjoint si \(\forall f,g\in H\)
    \begin{equation*} \langle Lf ,g \rangle_H = \langle f ,L g \rangle_H \end{equation*}
  3. positif si \(\forall f\in H\)
    \begin{equation*} \langle Lf ,f \rangle_H \ge 0 \end{equation*}
Preuve.
  1. Continuité:
    Le caractère linéaire est immédiat. On va donc ensuite montrer la continuité de \(L_k\text{.}\) On commence par
    \begin{equation*} \Biggl|(L_k f)(x) \Biggr| = \Biggl| \int_V k(x,y)f(y)d\mu(y) \Biggr| \end{equation*}
    La on utilise l’inégalité de Cauchy-Schwarz ce qui donne
    \begin{equation*} \Biggl|(L_k f)(x) \Biggr| \le \Norm k(x,.)\Norm_{L^2_{\mu}} \Norm f\Norm_{L^2_{\mu}} \end{equation*}
    Puisque \(k\) est continue sur \(V\) un compact elle appartient à l’espace de Banach \(C^0\) muni de la norme max et est bornée pour cette norme. On a donc
    \begin{equation*} \Norm k(x,.)\Norm_{L^2_{\mu}} = \left(\int_V k(x,y)^2d\mu(y)\right)^\frac12 \leq \left(\int_V \underset{y\in V}{max}\mid k(x,y)\mid^2d\mu(y)\right)^\frac12 \end{equation*}
    et
    \begin{equation*} \Norm k(x,.)\Norm_{L^2_{\mu}} = \left(\int_V k(x,y)^2d\mu(y)\right)^\frac12 \leq \sqrt{\mu(V)} \underset{y\in V}{max}\mid k(x,y)\mid \end{equation*}
    On a donc
    \begin{equation*} \Biggl|(L_k f)(x) \Biggr| \le \sqrt{\mu(V)} \underbrace{\underset{y\in V}{max}\mid k(x,y)\mid}_{M} \Norm f\Norm_{L^2_{\mu}} \end{equation*}
    Ensuite on regarde la norme \((L_k f)(x)\)
    \begin{equation*} \Norm L_k f \Norm_{L^2_{\mu}} =\left( \int_V(L_k f)(x)^2\right)^{\frac12}\leq \left( \int_V( \sqrt{\mu(V)} M \Norm f\Norm_{L^2_{\mu}})^2 \right)^{\frac12} \end{equation*}
    ce qui donne
    \begin{equation*} \Norm L_k f \Norm_{L^2_{\mu}} \leq \sqrt{\mu(V)} M \Norm f\Norm_{L^2_{\mu}}\left( \int_V 1\right)^{\frac12} = \mu(V) M \Norm f\Norm_{L^2_{\mu}} \end{equation*}
    Cela nous permet de conclure sur la continuité de l’opérateur de \(L^2_{\mu}(V)\) dans lui-même.
  2. Compacité:
    Pour la compacité on va utiliser le théorème d’Arzela-Ascoli qui dit qu’une partie de \(W\in C^0(V,V)\) avec \(V\) un espace metrique est relativement compacte si elle est uniformément bornée et continue. Puisque \(W\) est relativement compacte alors toutes suites de \(W\) admet une sous suite convergente. Donc si on démontre que pour tout ensemble borné de \(L^2_{\mu}\) l’image par \(L_k\) est relativement compact on aura conclu. Il faut donc montrer que \(\forall (f_n)_{n\ge 0}\)est bornée (\(\Norm L_k f_n \Norm_{L^2_{\mu}} \leq M\)) l’image par \(L_k\) est uniformément bornée et equicontinue.
    On se donne \((f_n)_{n\ge 0}\) avec \(\Norm L_k f_n \Norm_{L^2_{\mu}} \leq C\text{.}\) En utilisant les mêmes calculs que précédemment on obtient pour tous les éléments de la suite
    \begin{equation*} \Biggl|(L_k f_n)(x) \Biggr| \le \sqrt{\mu(V)} \underbrace{\underset{y\in V}{max}\mid k(x,y)\mid}_{M} \Norm f_n\Norm_{L^2_{\mu}} \end{equation*}
    En utilisant la définition de la norme infinie et le fait que les suites sont bornées on obtient
    \begin{equation*} \Norm L_k f_n \Norm_{\infty} \le \sqrt{\mu(V)} M C. \end{equation*}
    Maintenant on va établir le côté équicontinue. \(\forall f\in L_2^{\mu}(V)\text{,}\) \(\forall x_1,x_2 \in V\times V\) on a
    \begin{equation*} \Biggl|(L_k f_n)(x_1) - (L_k f_n)(x_2)\Biggr| = \Biggl| \int_V (k(x_1,y) -k(x_2,y))f_n(y)d\mu(y) \Biggr| \end{equation*}
    Comme précédemment on utilise Cauchy-Schwarz afin d’obtenir
    \begin{equation*} \Biggl|(L_k f_n)(x_1) - (L_k f_n)(x_2)\Biggr| \leq \sqrt{\mu(V)}\underset{y\in V}{max}\mid (k(x_1,y) -k(x_2,y)) \mid \Norm f_n\Norm_{L^2_{\mu}} \end{equation*}
    Puisque \(k\) est continue et \(V\) un compact alors \((L_k f)\) est continue et donc une partie de \(C^0(V)\text{.}\) En utilisant que la suite est borné on obtient
    \begin{equation*} \Biggl|(L_k f_n)(x_1) - (L_k f_n)(x_2)\Biggr| \leq \sqrt{\mu(V)}\underset{y\in V}{max}\mid (k(x_1,y) -k(x_2,y)) \mid C \end{equation*}
    On a donc l’équicontinuité et on peut conclure que l’image de notre opérateur est relativement compact dans \(C^0(V)\text{.}\) Il faut maintenant passer à \(L_{\mu}^2(V)\text{.}\) On a donc que l’image d’un borné de \(L_{\mu}^2(V)\) est compact dans \(C^0(V)\text{.}\) C’est donc aussi vrai pour la boule unité de \(L_{\mu}^2(V)\) dont l’image est relativement compact dans \(C^0(V)\text{.}\) Par conséquent ca peut être recouvert par une ensemble fini de boule de C0 de rayon \(\epsilon\text{.}\) Par l’inclusion de \(C^0(V)\) dans \(L_{\mu}^2(V)\) on peut recouvrir par les même boules mais en norme \(L_{\mu}^2(V)\) de rayon de type \(\epsilon \sqrt( \mu(V))\text{.}\) Puisque ceci est vrai \(\forall \epsilon\) l’image de la boule unité de \(L_{\mu}^2(V)\) est relativement compact dans \(L_{\mu}^2(V)\text{.}\)
  3. Auto-ajoint:
    On part de
    \begin{equation*} \langle Lf ,g \rangle_H = \int_V (Lf)(x) g(x)d\mu(x)= \int_V \int_V k(x,y)f(y) g(x)d\mu(y)d\mu(x)=\langle f ,Lg \rangle_H \end{equation*}
    Le côté symétrique et le théorème de Fubini permet de conclure
  4. Positivité:
    Pour la positivité on passe la définition de l’intégrale utilisant les sommes de Riemann. On a
    \begin{equation*} \langle Lf, f\rangle = \int_V f(x)f(y)k(x,y)d\mu(x)d\mu(y) \end{equation*}
    ceci est égal à
    \begin{equation*} \langle Lf, f\rangle = \underset{k\rightarrow\infty}{lim} \frac{\mu(V)}{k^2} \sum_{i,j=1}^k f(_i)f(x_j)k(x_i,x_j) \ge 0 \end{equation*}
    par définition de \(k\text{.}\)
Ce résultat va nous permettre d’utiliser le théorème spectral qu’on va rapidement rappeler.
Preuve.
Admis
Maintenant on va pouvoir énoncer le théorème de Mercer et son corollaire qui vont permettre d’obtenir une version "constructive" des noyaux pour \(v\) un espace compact.
Preuve.
Admis
Preuve.
On doit juste montrer que l’application est continue et que \(\phi(x)\) appartient à \(l^2\text{.}\) Pour cela on remarque:
\begin{equation*} \langle \phi(x), \phi(x)\rangle_{l^2}=k(x,x) \lt \infty \end{equation*}
car (3.36) converge. On a donc \(\phi(x) \in l^2\text{.}\) Pour la continuité il suffit de regarder:
\begin{equation*} \Norm \phi(x)- \phi(y)\Norm_{l^2}^2 = \sum_{n=1}^{\infty}\lambda_i(\psi_n(x)-\psi_n(y))^2 \end{equation*}
En utilisant la définition des noyaux
\begin{equation*} \Norm \phi(x)- \phi(y)\Norm_{l^2}^2 = k(x,x)+k(y,y)-2 k(x,y) \end{equation*}
On peut conclure en utilisant la continuité du noyau.
On a donc obtenu qu’une fonction \(k: V \times V \rightarrow \mathbb{R}\) semi définie positive et continue et \(V\) compact était un noyau et donc pouvait représenter le produit scalaire un espace de Hilbert potentiellement en grande dimension. On n’avait pas unicité de la fonction et de l’espace de re description associés. Dans le cas \(V\) fini ou compact la méthode la construction de \(H\) et de \(\phi\) basé sur la diagonalisation nous donne un choix "canonique" de la fonction de re description et donc de l’espace de Hilbert associé.

Subsubsection 3.4.3.3 Espace De Hilbert a noyau reproduisant

On va maintenant proposé dans le cas général (\(V\) un espace métrique) proposer une construction canonique de \(H\) et \(\phi\)
Définition 3.78. Espace de Hilbert à noyau reproduisant (RKHS).
Soit \(V\) Un espace métrique. Soit \(H\) un espace de Hilbert de fonctions réelles définies sur \(V\text{.}\) Une fonction \(k: V\times V\rightarrow \mathbb{R}\) est appelé un noyau reproduisant si
  1. \(H\) contient toutes les fonctions de la forme:
    \begin{equation*} \forall x\in H, \quad k_x(y)\rightarrow k(x,y) \end{equation*}
  2. \(\forall x\in V, f\in H\) on a:
    \begin{equation*} f(x)=\langle f, k_x\rangle_H \end{equation*}
Si il existe un noyau reproduisant \(k\) alors H est appelé espace de Hilbert a noyau reproduisant.
On va introduite un théorème qui nous permet à partir des noyaux reproduisant permet de démontrer le théorème Théorème 3.71 dans le cas général.
Définition 3.79.
On se donne un noyau \(k: V \times V \rightarrow \mathbb{R}\) semi-définie positif continue. On se donne \((x_1,...x_n)\) avec \(x_i\in V, \forall i \lt n\text{.}\) On introduit l’espace fonctionnel engendré \(H_{k}^0\) donné par
\begin{equation*} H_{k}^0=\left\{ f(x),\quad \mbox{tel que}\quad f(x)=\sum_{i=1}^n\alpha_i k(x,x_i)\right\} \end{equation*}
Cet espace (comme on le verra rapidement après) est un espace vectoriel euclidien qui engendre des fonctions à partir de combinaisons linéaires de fonctions issues du noyau. Il sera important dans la preuve qui va suivre.
Définition 3.80.
Soit \((H_0; \langle .,.\rangle_{H_0})\) un espace pré-hilbertien de fonctions définies sur \(V\) et à valeurs réelles. On dit qu’il existe une unique complétion fonctionnelle de \(H_0\) si il existe:
  1. un espace vectoriel de fonctions \(H\) défini sur \(V\) et à valeurs réelles tel que \(H_0 \subset H\text{.}\)
  2. un produit scalaire \(\langle .,.\rangle_H\)
tels que \((H; \langle .,.\rangle_{H})\) soit un espace de Hilbert et , pour tout \(x\in V\text{,}\) la forme linéaire \(\delta_x(f) = f(x)\) est continue.
Preuve.
Admis.
Remarque 3.82.
On voit donc que si on se donne un espace \(H\text{.}\) En général pour démontrer qu’il s’agit d’un RKHS si on a un espace de Hilbert (espace pre-Hilbertien + complétion Lemme 3.81) + les propriétés de Définition 3.79.
Preuve.
  1. Propriété 1: Soit \(k_1,k_2\) deux noyaux reproduisant associés au même espace \(H\text{.}\)
    \begin{equation*} \Norm k_1(x,.)-k_2(x,.)\Norm_2=\langle k_1(x,.)-k_2(x,.), k_1(x,.)-k_2(x,.) \rangle_H \end{equation*}
    \begin{equation*} \Norm k_1(x,.)-k_2(x,.)\Norm_2 = \langle k_1(x,.)-k_2(x,.), k_1(x,.)\rangle_H- \langle k_1(x,.)-k_2(x,.), k_2(x,.) \rangle_H \end{equation*}
    donc
    \begin{equation*} \Norm k_1(x,.)-k_2(x,.)\Norm_2= k_1(x,x) - k_2(x,x) -k_1(x,x)+k_2(x,x)=0 \end{equation*}
    puisque \(\langle f(.),k(x,.)\rangle=f(x)\text{.}\) Il a donc unicité.
  2. Propriété 2
    1. \(\Rightarrow\text{:}\) Si \(H_k\) est un RKHS alors
      \begin{equation*} |\delta_xf|=|f(x)|=|\langle f, k(x,\cdot)\rangle_{H_k} \end{equation*}
      par la propriété reproduisante. Par le théorème de Cauchy-Schwarz, on a
      \begin{equation*} |\delta_xf|\leq \|k(x,\cdot)\|_{H_k}\|f\|_{H_k} =\sqrt{\langle k(x,\cdot), k(x,\cdot)\rangle_{H_k}}\|f\|_{H_k} = \sqrt{k(x,x)}\|f\|_{H_k} \end{equation*}
      par définition du produit scalaire dans \(H_k\text{.}\) Donc \(\lambda_x=\sqrt{k(x,x)}\) et l’opérateur d’évaluation est bien borné.
    2. \(\Leftarrow\text{:}\) Si \(\delta_x : H_k\rightarrow\mathbb{R}\) est borné, par le théorème de représentation de Riesz il existe \(g_{\delta_x}\in H_k\) tel que \(\delta_x f =\langle f, g_{\delta_x}\rangle_{H_k}\) pour tout \(f\in H_k\text{.}\) On définit \(k(x,\cdot)=g_{\delta_x}(\cdot)\text{.}\) On a donc bien \(k(x,\cdot) \in H_k\) pour tout \(x\in\mathcal{X}\) et \(\langle f(\cdot),k(x,\cdot)\rangle_{H_k}=\delta_x f =f(x)\text{.}\) Donc \(k\) est bien un noyau reproduisant.
  3. Propriété 3 et 4: Ici l’idée va être de construire explicitement l’espace de Hilbert associé à un noyau semi-défini positif. On considère l’espace \(H_{k}^0\) définit par Définition 3.79. Soit des fonctions de \(H_{k}^0\text{:}\)
    \begin{equation*} f(x)=\sum_{i=1}^n \alpha_i k(x,x_i), \quad g(x)=\sum_{i=1}^n \beta_i k(x,x_i) \end{equation*}
    On introduit l’opérateur suivant
    \begin{equation*} \langle f,g \rangle_{H_{k}^0}= \sum_{i,j=1}^n\alpha_i\beta_i k(x_i,x_j) \end{equation*}
    On va montrer qu’il s’agit d’un produit scalaire pour \(H_{k}^0\text{.}\) On remarque d’abord que
    \begin{equation} \langle f,g \rangle_{H_{k}^0}= \sum_{i=1}^n\alpha_i g(x_i)= \sum_{j=1}^n\beta_j f(x_j)\tag{3.37} \end{equation}
    cela permet de voir que l’opérateur est symétrique et bilinéaire. Puisque \(k\) est semi-définie positif. On a
    \begin{equation*} \Norm f\Norm_2^2= \sum_{i,j}^n a_i a_j k(x_i,x_j) \ge 0 \end{equation*}
    Il nous reste a montré que caractère non dégénéré et au passage la propriété reproduisante. On utilise les mêmes arguments que dans la preuve de la propriété 2. On obtient
    \begin{equation} \mid f(x)\mid \le \sqrt{k(x,x)}\|f\|_{H_k}\tag{3.38} \end{equation}
    On a donc bien que \(\Norm f\Norm_{H_k}=0\) implique que \(f=0\text{.}\) Pour la propriété reproduisante on utilise (3.37) avec \(g=k(x,.)\text{.}\) On a donc la représentation de Riesz
    \begin{equation} \langle f,k(x,.)\rangle_{H_{k}^0}= \sum_{i=1}^n\alpha_i k(x,x_i)= f(x)\tag{3.39} \end{equation}
    Pour avoir la propriété reproduisante il suffit de choisir \(f(y)=k(y,.)\text{.}\) On a donc montré que \(H_k^0\) est un espace pre-Hilbertien. Si on peut compléter cet espace pour obtenir un espace de Hilbert \(H_k\) ce qui conclura la preuve. Pour cela on va utiliser le lemme Lemme 3.81. La continuité de \(\delta_x\) est obtenu par (3.38). Soit maintenant une suite de Cauchy \(\left\{ f_n \right\}_{n\ge 0}\) d’éléments de \(H_k^0\) telle que \(\underset{n\rightarrow\infty }{lim f_n(x)} = 0, \quad \forall x \in V\text{.}\) Pour Cela on utilise que
    \begin{equation*} \Norm f_m\Norm_{H_{k}^0}^2\le \Norm f_m -f_n\Norm_{H_{k}^0}^2+ \mid \langle f_n, f_m \rangle_{H_{k}^0}\mid \end{equation*}
    On passe une première fois à la limite.
    \begin{equation*} \Norm f_m\Norm_{H_{k}^0}^2\le \underset{n\rightarrow\infty }{lim} \Norm f_m -f_n\Norm_{H_{k}^0}^2+ \underset{n\rightarrow\infty }{lim} \mid \langle f_n, f_m \rangle_{H_{k}^0}\mid \end{equation*}
    On utilise la propriété (3.37) ce qui donne
    \begin{equation*} \underset{n\rightarrow\infty }{lim} \mid \langle f_n, f_m \rangle_{H_{k}^0}\mid = \underset{n\rightarrow\infty }{lim} \sum_{i,j=1}^n\alpha_{i,n}\alpha_{j,n} k(x_i,x_j) = \underset{n\rightarrow\infty }{lim} \sum_{i=1}^n\alpha_{i,n} f_n(x_i) \end{equation*}
    La convergence ponctuelle nous donne donc \(\underset{n\rightarrow\infty }{lim} \mid \langle f_n, f_m \rangle_{H_{k}^0}\mid =0\) donc
    \begin{equation*} \Norm f_m\Norm_2^2\le \underset{n\rightarrow\infty }{lim} \Norm f_m -f_n\Norm_{H_{k}^0}^2 \end{equation*}
    On repasse à la limite et en utilisant le fait qu’on a une suite de Cauchy qui satisfait \(\underset{n,m\rightarrow\infty }{lim} \Norm f_m -f_n\Norm_{H_{k}^0}^2=0\) on a donc
    \begin{equation*} \underset{m\rightarrow\infty }{lim}\Norm f_m\Norm_{H_{k}^0}^2=0 \end{equation*}
    On peut donc appliquer le théorème de complétion et donc on obtient un espace de Hilbert associé à notre produit scalaire.
  4. Propriété 5 On va utiliser la propriété précédente. On commence par démontrer la symétrie:
    \begin{equation*} k(x,y)=\langle k_x,k_y \rangle_{H_k} = \langle k_y,k_x \rangle_{H_k}= k(y,x) \quad \forall (x,y)\in V^2 \end{equation*}
    Pour le coté défini positif on choisit \(\forall n \in \mathbb{N}\text{,}\) \((x_1,...,x_n)\in V^n\) et \((a_1,...,a_n)\in V^n\text{.}\) On a grace a la propriété reproduisante:
    \begin{equation*} \sum_{i,j}^n a_i a_j k(x_i,x_j)= \sum_{i,j}^n a_i a_j \langle k_{x_i},k_{x_j} \rangle_{H_k}= \langle \sum_{i}^n a_i k_{x_i}, \sum_{j}^n a_j k_{x_j} \rangle_{H_k} \end{equation*}
    ce qui donne
    \begin{equation*} \sum_{i,j}^n a_i a_j k(x_i,x_j)= \Norm \sum_{i}^n a_i k_{x_i} \Norm_{H_k} \ge 0 \end{equation*}
Le théorème de Aronszjan nous dit que lorsqu’on se muni d’un noyau semi-défini positif on peut lui associé un unique espace de Hilbert reproduisant \(H\) avec ce noyau comme noyau reproduisant associé. La preuve nous donne même une construction de cet espace de Hilbert. On a donc bien une preuve du théorème Théorème 3.71 dans le cas général et donc une caractérisation des fonctions noyaux et des espaces de Hilbert associés. En utilisant la propriété reproduisante on obtient que \(k\) est un noyau et satisfait:
\begin{equation*} k(x,y)=\langle k(.,x),k(.,y) \rangle_H= \langle \phi(x),\phi(y)\rangle _H \end{equation*}
avec \(\phi(.)=k(x,.)\) une fonction de re-description. Ce choix de \(\phi\) n’est pas uniquement, mais il est naturel.
On a enfin complètement caractérisé un noyau. Il suffit de prendre une fonction \(k: V\times V\rightarrow \mathbb{R}\) semi-définie positive et continue. À partir de la on obtient un espace et une fonction de re description à l’aide de RKHS associé. Pour montrer que cette théorie est générale, on va montrer que le noyau de Mercer génère un RKHS.
Preuve.
  1. On montre que \(H_k\) est un espace de Hilbert inclut dans les fonctions continues: Par le théorème spectral la famille des \((\psi_1,\psi_2,....)\) forment une base Hilbertienne de \(L_{\mu}^2(V)\) par conséquent on peut donc écrire tout élément \(f(x)\) de \(L^2\) sous la forme \(f(x)= \sum_{i=1}^{\infty} a_i \psi_i(x)\text{.}\) On prend maintenant une transformation \(I_k: L_{\mu}^2 \rightarrow H_k\) qui associe:
    \begin{equation*} \sum_{i=1}^{\infty} a_i \psi_i(x) \rightarrow \sum_{i=1}^{\infty} \underbrace{a_i\sqrt{\lambda_i}}_{b_i} \psi_i(x) \end{equation*}
    On voit bien en effet que la fonction obtenue est dans \(H_k\text{,}\) car
    \begin{equation*} \sum_{i=1}^{\infty} \frac{b_i^2}{\lambda_i}= \sum_{i=1}^{\infty} a_i^2 \lt \infty \end{equation*}
    L’application \(I_k\) est isomorphisme entre les deux espaces donc on obtient que \(H_k\) est un espace de Hilbert. Maintenant il faut montrer qu’il est inclus dans l’espace des fonctions continues afin d’obtenir l’existence du noyau reproduisant par la 3ème prorpriété de Théorème 3.83. On a
    \begin{equation*} \mid f(x)\mid = \mid \sum_{i=1}^{\infty} a_i \psi_i(x) \mid = \mid \sum_{i=1}^{\infty} \frac{a_i}{\sqrt{\lambda_i }} \sqrt{\lambda_i }\psi_i(x) \mid \end{equation*}
    On utilise Cauchy-Schwarz pour obtenir
    \begin{equation*} \mid f(x)\mid \le \Biggl(\sum_{i=1}^{\infty} \frac{a_i^2}{\lambda_i }\Biggr)^\frac12 \Biggl(\sum_{i=1}^{\infty} \lambda_i \psi_i^2(x) \Biggr)^\frac12 \end{equation*}
    Par définition du noyau et du produit scalaire on obtient
    \begin{equation*} \mid f(x)\mid \le \Norm f\Norm_{H_k} k(x,x)^\frac12 \end{equation*}
    On a donc la convergence dans \(H_k\) qui implique la convergence uniforme. Soit \(f=\sum_{i=1}^{\infty} a_i \psi_i(x)\in H_k\) on introduit la suite obtenu par troncature de \(f\text{:}\)
    \begin{equation*} f_n=\sum_{i=1}^{n} a_i \psi_i(x) \in H_k \end{equation*}
    On va maintenant montrer que \(f \in H_k\) est en pratique continue. L’opérateur \(L_k\) étant continu et puisque \(\psi_i =\frac{1}{\lambda_i}L_k \psi_i\) on a que les vecteurs propres sont des fonctions continues donc c’est aussi le cas pour \(f_n\text{.}\) On va maintenant utiliser que la convergence \(H_k\) implique la convergence uniforme (espace des fonctions connues). On considère
    \begin{equation*} \mid f_n -f_m\mid \le C \Norm f_n -f_m\Norm_{H_k} \end{equation*}
    donc
    \begin{equation*} \underset{n,m\rightarrow \infty}{lim}\mid f_n -f_m\mid \le C \underset{n,m\rightarrow \infty}{lim}\Norm f_n -f_m\Norm_{H_k} \end{equation*}
    Puisqu’on sait que \(f_n\) converge dans \(H_k\) on a \(\underset{n,m\rightarrow \infty}{lim}\Norm f_n -f_m\Norm_{H_k} =0\) donc on a
    \begin{equation*} \underset{n,m\rightarrow \infty}{lim}\mid f_n -f_m\mid =0 \end{equation*}
    Puisque \(f_n\) est continue on a donc une suite de cauchy dans l’espace des fonctions continue et par complétude elle convergence vers une fonction continue. On nomme la limite continue \(f_c\text{.}\) Cette fonction appartient à \(L_{\mu}^2(V)\) car les fonctions continues sur un compact sont bornés et donc sont de carré intégrable si la mesure est finie. Maintenant on souhaite montrer que \(f_c\) coindice avec \(f\text{.}\) Donc
    \begin{equation*} \Norm f_n -f_c \Norm_{L_{\mu}^2} \underset{n\rightarrow \infty }{\rightarrow \infty 0} \end{equation*}
    On remarque ensuite que pour une fonction \(f\in H_k\)
    \begin{equation*} \Norm f\Norm_{{L_{\mu}^2}}^2=\sum_{i=1}a_i^2 \leq \lambda_1 \sum_{i=1}\frac{a_i^2}{\lambda_i} = \Norm f\Norm_{H_k}^2 \end{equation*}
    car \(\frac{\lambda_1}{\lambda_i}\ge 1, \forall i\text{.}\) On a donc pour \(f=\sum_{i=1}^{\infty} a_i \psi_i(x)\)
    \begin{equation*} \Norm f_n -f \Norm_{{L_{\mu}^2}} \le \lambda_1\Norm f_n -f \Norm_{H_k} \underset{n\rightarrow \infty }{\rightarrow 0} \end{equation*}
    et par unicité de la limite dans \(L_{\mu}^2\) on a \(f=f_c\) donc les fonctions de \(H_k\) sont bien continues. Ensuite il va suffire de vérifier les deux propriétés de la Définition 3.78.
  2. On montre que \(k(x,.) \in H_k\): On pose
    \begin{equation*} \phi_x=\sum_{i=1}^{\infty}a_i\psi_i \end{equation*}
    avec \(a_i=\lambda_i\phi_(x)\text{.}\) On va maintenant regarder la série des coefficients:
    \begin{equation*} \sum_{i=1}^{\infty} \frac{a_i^2}{\lambda_i}=\sum_{i=1}^{\infty} \lambda_i\psi_i^2(x) = k(x,x)\lt \infty \end{equation*}
    Cette fonction \(\phi_x \in H_k\text{.}\) On sait que la convergence dans \(H_k\) implique la convergence ponctuelle de la série. On a donc
    \begin{equation*} \phi_x(y)=\sum_{i=1}^{\infty}a_i\psi_i(y) = \sum_{i=1}^{\infty} \lambda_i\psi_i(x)\psi_i(y)=k(x,y) \end{equation*}
    donc \(\phi_x(.)=k(x,.)\) et donc \(k(x,.)\in H_k\text{.}\)
  3. On montre que \(\forall x\in V, f\in H_k \langle f,k(x,.)\rangle_{H_k}\): Soit une fonction de \(H_k\)
    \begin{equation*} f=\sum_{i=1}^{\infty}a_i\psi_i \end{equation*}
    et on a vu que
    \begin{equation*} k(x,.)=\sum_{i=1}^{\infty}\lambda_i \psi_i(x)\psi_i \end{equation*}
    on applique la définition du produit scalaire
    \begin{equation*} \langle f, k(x,.)\rangle_{H_k} =\sum_{i=1}^{\infty}\frac{\lambda_i \psi_i(x)a _i}{\lambda_i}=\sum_{i=1}^{\infty}a_i\psi_i=f \end{equation*}
Maintenant nous allons donner le théorème qui va justifier la construction de ses espaces a noyau reproduisant. Il s’agit d’un théorème d’approximation.
Preuve.
Puisque \(H_k\) est un espace de Hilbert le "Théorème du supplémentaire orthogonale d’un fermé dans un espace de Hilbert" nous dit qu’il existe \(H_{k}^{0,\perp}\) tel que
\begin{equation*} H_k= H_{k}^{0} \oplus H_{k}^{0,\perp} \end{equation*}
car \(H_{k}^{0}\) est un sous-espace vectoriel fermé des fonctions continues. On a donc \(\forall f\in H_k \)
\begin{equation*} f= f_0+ f^{\perp} \end{equation*}
et donc en utilisant les proriété reproduisante de \(H_k\) on a
\begin{equation*} f(x_i)=\langle f(x_i), k(x_i,.)\rangle_{H_k}= \langle f_0(x_i), k(x_i,.)\rangle_{H_k} + \underbrace{\langle f^{\perp}(x_i), k(x_i,.)\rangle_{H_k}}_{=0} \end{equation*}
car \(k(x_i,.)\in H_k^{0}\text{.}\) Par conséquent lorsqu’on se restreint à \(H_k^{0}\) la fonction coût que ne dépend que \(f(x_i)\) ne change pas. Pour le terme de pénalisation on a
\begin{equation*} \Norm f_0\Norm_{H_k} \le \Norm f\Norm_{H_k} \end{equation*}
Donc la solution optimale du problème de minimisation se trouve dans \(H_{k}^{0}\text{.}\)
On remarque qu’en prenant \(L(x,y)=\Norm y - x\Norm_2^2\) on retrouve notre problème aux moindres carrés d’origine.
Le dernier théorème montre que si on veut trouver une fonction de \(H_k\) (RKHS associé au noyau reproduisant \(k\)) qui minimise l’erreur d’approximation sur un nuage de point alors cette fonction sera dans \(H_{k}^0\text{.}\) Si nos points sont générés ou proche d’être généré par une fonction de \(H_k\) la candidate naturelle pour la régression est une une fonction de l’espace \(H_{k}^{0}\) associé à \(k\).

Subsection 3.4.4 Régression à Noyau

Définition 3.86. Modèle nonlinéaire.

Le modèle nonlinéaire consiste à se donner une loi de probabilité paramétrée pour le problème de régression Définition 3.17 de la forme:
\begin{equation} p_{\theta}(y \mid x)=\mathcal{N}(y \mid f_{\theta}(x),\sigma^2)\tag{3.44} \end{equation}
avec les paramètres \(\theta\in \mathbb{R}^m\) et \(\mathcal{N}\) une loi Gaussienne. \(\sigma \in \mathbb{R}\) est fixé et modélise l’incertitude sur les données.
Si on applique le même principe (MAP) de construction que dans le cas linéaire et qu’on cherche donc a maximiser la fonction log-vraisemblance avec un a priori gaussien (3.29). On se retrouve à devoir résoudre le problème suivant:
\begin{equation} \operatorname{argmin}_{\theta} \sum_{i=1}^n \Norm y_i - f_{\theta}(x_i)\Norm_2^2 +\lambda \Norm \theta\Norm_2^2\tag{3.45} \end{equation}
On va donc choisir comme représentation \(f_{\theta}\) la fonction
\begin{equation} f_{\theta}(x)=\langle \theta,\phi(x)\rangle_H\tag{3.46} \end{equation}
avec \(\theta\) un élement de \(H\) (potentiellement de dimension infini) l’espace de re-description. En utilisant les même calculs (très formels) que dans la section Subsubsection 3.2.2.1 on peut montrer que
\begin{equation*} \theta=\sum_{i=1}^n\alpha_i\phi(x_i) \end{equation*}
En injectant cela dans notre représentation (3.46) au dessus on obtient:
\begin{equation*} f_{\theta}(x)=\sum_{i=1}^n\alpha_i \langle \phi(x_i),\phi(x)\rangle_H \end{equation*}
Si on prend comme fonction de re-description la fonction de re-description canonique associé un noyau reproduisant \(k\) et un espace on obtient la représentation suivante:
\begin{equation} f_{\theta}(x)=\sum_{i=1}^n\alpha_i k(x_i,x)\tag{3.47} \end{equation}
A partir de la, en intégrant cette représentation dans notre régression (3.45) on obtient la formulation finale de la régression à noyau.

Preuve.

Pour obtenir le premier terme de on remplace juste \(f_{\theta}\) dans (3.45) par sa forme (3.47). Pour obtenir le terme de régularisation il suffit développer le terme Ridge:
\begin{equation*} \parallel f\parallel_2^2 =\langle\sum_{i=1}^n\alpha_i k(x,x_i),\sum_{j=1}^n\theta_j k(x,x_j)\rangle_H \end{equation*}
\begin{equation*} \parallel f\parallel_2^2 = \sum_{i,j=1}^n\alpha_i\alpha_j \langle k(x,x_i), k(x,x_j)\rangle_H \end{equation*}
\begin{equation*} \parallel f\parallel_2^2 = \sum_{i,j=1}^n\alpha_i\alpha_j k(x_i,x_j) \end{equation*}
par la propriété réproduisante du théorème de Aronszjan.
Le problème de régression peut être écrit sous fore matricielle. Pour cela on introduit la matrice \(K\) tel que \(K_{ij}=k(x_i,x_j)\text{,}\) le vecteur \(b\) tel que \(b_{i}=y_i\) et on obtient donc la réécriture de la fonction coût:
\begin{equation} \mathcal{J}(\alpha)= \parallel b - K \alpha\parallel_2^2 + \lambda \langle \alpha,K\alpha\rangle_{\mathbb{R}^n}\tag{3.48} \end{equation}
On retrouve un problème aux moindres carrés ou matrice est symétrique définie positive et carré. On sait résoudre ce problème.

Preuve.

On fera une preuve rapide puisqu’elle reprend des arguments déjà introduits. La matrice \(K\) est symétrique positive puisque associée à un noyau reproduisant. Si \(\lambda\) est strictement positif, On aura une fonctionnelle coercive strictement convexe donc avec un unique minimiseur donné par:
\begin{equation*} \nabla_{\alpha} \mathcal{J}(\alpha)=0 \end{equation*}
On peut calculer le gradient comment dans les section 1 et 2 du chapite. On obtient
\begin{equation*} \nabla_{\alpha}\mathcal{J}(\alpha) = - K b + K^2b \alpha+ \lambda K\alpha \end{equation*}
Cela permet de conclure.
On a obtenu à l’aide des noyaux reproduisant un algorithme de régression nonlineaire simple (problème de moindre carré de taille \(n\) le nombre d’échantillons). On sait que ceci est équivalent à envoyer nos données dans espace de Hilbert \(H_k\) (associé au noyau \(k\)) potentiellement de grandes dimensions et a faire une régression linéaire. On a montré à travers les différents théorèmes que cette méthode permettait de trouver la fonction de \(H_k\) qui minimisait l’erreur d’approximation les points de l’échantillon. Si ces points sont issus d’une fonction de \(H_k\) on peut espère une bonne approximation. Il nous reste donc a déterminer \(k\) et \(H_k\) explicitement.

Subsection 3.4.5 Exemples de noyaux et RKHS

A traves les sections précédentes on va vu que les noyaux permettaient de de construire des fonctions de re descriptions capables de plonger nos données en dimension grande voir infini avec une évaluation facile de produit scalaire dans l’espace de re description par le noyau. On a ensuite vu qu’ à chaque noyau semi-défini positif pouvait se voir associer un espace de Hilbert RKHS (qui sera l’espace de re description). On a aussi vu lorsqu’on cherche a faire une régression dans l’espace de re description la solution (pas forcement unique) peut s’écrire comme une combinaison linéaire d’évaluation du noyau reproduisant. Maintenant il ne nous reste qu’a déterminer des noyaux possibles et leurs espaces RKHS associés. En effet si on veut attaquer une large gamme de problèmes il est important d’avoir des RKHS de grandes tailles et variés. Avant de commencer on va donner quelques réglées sur la construction des noyaux ensuite on les classifiera.

Preuve.

  1. Propriété 1: \(\forall (x_1,y_1)\in V_1^2, (x_2,y_2)\in V_2^2\) on a
    \begin{equation*} k_1(x_1,y_1)+k_2(x_2,y_2)= \alpha\langle \phi_1(x_1),\phi_1(y_1)\rangle_{H_1}+\beta\langle \phi_2(x_2),\phi_2(y_2)\rangle_{H_2} \end{equation*}
    par définition d’un noyau. Cela se réécrit
    \begin{equation*} k_1(x_1,y_1)+k_2(x_2,y_2)= \langle \sqrt{\alpha}\phi_1(x_1),\sqrt{\alpha}\phi_1(y_1)\rangle_{H_1}+ \langle\sqrt{\beta} \phi_2(x_2),\sqrt{\beta}\phi_2(y_2)\rangle_{H_2} \end{equation*}
    cela nous donne
    \begin{equation*} k_1(x_1,y_1)+k_2(x_2,y_2)= \langle \phi((x_1,x_2)),\phi((y_1,y_2))\rangle_{H} \end{equation*}
    avec \(\phi((x_1,x_2))=(\sqrt{\alpha}\phi_1(x_1),\sqrt{\beta}\phi_2(x_2))\) et \(H=H_1\oplus H_2\text{.}\)
  2. Propriété 2: \(\forall (x_1,y_1)\in V_1^2, (x_2,y_2)\in V_2^2\) on a
    \begin{equation*} k_1(x_1,y_1) k_2(x_2,y_2)= \langle \phi_1(x_1),\phi_1(y_1)\rangle_{H_1} \langle \phi_2(x_2),\phi_2(y_2)\rangle_{H_2} \end{equation*}
    cela peut se réécrire
    \begin{equation*} k_1(x_1,y_1) k_2(x_2,y_2)= \langle \phi_1(x_1)\otimes \phi_2(x_2),\phi_1(y_1) \otimes \phi_2(y_2)\rangle_{H} \end{equation*}
    avec \(H=H_1\otimes H_2\) il suffit donc de posé \(\phi(x_1,x_2)=\phi_1(x_1)\otimes \phi_2(x_2)\text{.}\)
Maintenant nous allons donc introduire différents noyaux (ainsi parfois que leurs méthodes de construction) et surtout on va montrer quels sont leurs RKHS associé. En effet lors d’une régression a noyau on sait qu’on cherche un représentant dans l’espace de Hilbert. Si il est très restreint nos capacités à approcher, une large gamme de problèmes sera faible.
On va séparer les noyaux en trois catégories classiques

Subsubsection 3.4.5.1 Noyaux zonaux

On commencer par les noyaux les plus simples.
Définition 3.90.
Soit \(V\in \mathbb{R}^d\text{.}\) Un noyau \(k: V \times V \rightarrow \mathbb{R}\) est dit zonal si il est de la forme:
\begin{equation*} k(x,y)=K(\langle x,y\rangle_{\mathbb{R}^d}) \end{equation*}
avec \(K(x):\mathbb{R}\rightarrow \mathbb{R}\)
  1. Le premier cas est le noyau \(k(x,y)= \langle x,y\rangle_{\mathbb{R}^d} \text{.}\) Dans ce l’espace RKHS \(H_k\) associé est l’espace des fonctions linéaires de la forme \(f(x)=\langle \theta, x\rangle_{\mathbb{R}^d}\) (formes linéaires) munit du produit scalaire:
    \begin{equation*} \langle \theta_1, \theta_2\rangle_{\mathbb{R}^d}, \quad \mbox{pour } f(x)=\langle \theta_1, x\rangle_{\mathbb{R}^d}, \quad g(x)=\langle \theta_2, x\rangle_{\mathbb{R}^d} \end{equation*}
  2. Le second cas est le noyau \(k(x,y)= (\alpha + \langle x,y\rangle_{\mathbb{R}^d})^m \text{.}\) Afin de voir les polynômes obtenus, on peut faire un développement en utilisant la formule multinomiale. On peut montrer (on l’admet ici) qu’on obtient un espace de polynômes de \(\mathbb{R}^d\) de dimension \(\left(\begin{pmatrix} d+m\\ m \end{pmatrix}\right)\text{.}\) On voit donc que la dimension de l’espace monte très rapidement avec \(m\) et \(d\) on aurait avec une formulation classique (primal) de la régression polynomiale un nombre de coefficients et donc une taille du problème qui exploserait. L’avantage de cette formulation (duale) ce que la taille du problème reste lié aux nombres de points \(n\text{.}\)
  3. On peut citer aussi le noyau binomial \(k(x,y)= (1 - \langle x,y\rangle_{\mathbb{R}^d})^{-m} \) ou le Sigmoid \(k(x,y)= \operatorname{tanh}( \langle x,y\rangle_{\mathbb{R}^d}) \)
Les deux premiers cas nous donnent des espaces de fonctions de dimension finie.

Subsubsection 3.4.5.2 Noyaux invariant par translation

On va maintenant introduire une famille de noyaux qui particulièrement utilisé en pratique. Ici on se place plutôt dans le cas ou \(V=\mathbb{R}^d\text{.}\) On ne peut pas donc appliquer le théorème de Mercer. On va essayer de construire des noyaux préservant une certaine propriété: l’invariance par translation
Définition 3.91.
Soit \(V=\mathbb{R}^d\text{.}\) Un noyau \(k: V \times V \rightarrow \mathbb{R}\) est dit invariant par translation si il est de la forme:
\begin{equation*} k(x,y)=K(x-y) \end{equation*}
avec \(K(x):\mathbb{R}\rightarrow \mathbb{R}\)
On va maintenant essayer d’étudier et construire ce type de noyau. On suppose pour cela que \(K\in L^1(\mathbb{R}^d)\) Pour cela on va appliquer la transformé de Fourier:
\begin{equation*} K(x-y)=\frac{1}{(2\pi)^d}\int_{\mathbb{R}^d}e^{i\langle (x-y),\omega\rangle}\hat{K}(\omega)d\omega \end{equation*}
En le réécrivant
\begin{equation*} K(x-y)=\frac{1}{(2\pi)^d}\int_{\mathbb{R}^d}e^{i\langle x,\omega\rangle}e^{-i\langle y,\omega\rangle}\hat{K}(\omega)d\omega \end{equation*}
On voit qu’on reconnait une forme de la décomposition spectrale des noyaux de Mercer dans le cas indenombrable. Maintenant on va introduire deux théorèmes permettant de proposer des noyaux et de caractériser leurs espace RKHS associés.
Preuve.
Comme dans le cas de Mercer on doit démontrer trois propriétés.
  1. On montre que la fonctionnelle d’évaluation est continue et qu’on a un espace de Hilbert:
    \begin{equation*} \mid f(x)\mid = \frac{1}{(2\pi)^d}\mid\int_{\mathbb{R}^d} e^{i\langle x,\omega\rangle} \hat{f}(\omega)d\omega\mid \end{equation*}
    \begin{equation*} \mid f(x)\mid = \frac{1}{(2\pi)^d}\int_{\mathbb{R}^d} e^{i\langle x,\omega\rangle}\sqrt{\hat{K}(\omega)} \frac{\hat{f}(\omega)}{\sqrt{\hat{K}(\omega)}}d\omega \end{equation*}
    Par Cauchy-Schwarz on a
    \begin{equation*} \mid f(x)\mid \le \left(\int_{\mathbb{R}^d} \left(e^{i\langle x,\omega\rangle}\sqrt{\hat{K}(\omega)}\right)^2 d\omega\right)^{\frac12} \Norm f \Norm_{H_k} \end{equation*}
    donc
    \begin{equation*} \mid f(x)\mid \le \left(\int_{\mathbb{R}^d} e^{2i\langle x,\omega\rangle}\hat{K} dx\right)^{\frac12} \Norm f \Norm_{H_k} \end{equation*}
    \begin{equation*} \mid f(x)\mid \le K(2x) \Norm f \Norm_{H_k} \end{equation*}
    Puisque \(K(2x) \) est borné on a gagné. Par conséquent si \(\Norm f \Norm_{H_k}=0\) alors \(f(x)=0\) on a donc bien un produit scalaire (le reste des est évident) et donc un espace pré-Hilbertien. On peut montrer ensuite qu’il s’agit d’un espace de Hilbert en utilisant la démonstration du point 4 de la preuve de Théorème 3.83.
  2. On montre que \(k(x,.) \in H_k\):
    On considère la fonction \(k_x(y)=k(x,y)=K(x-y)\text{.}\) On a
    \begin{equation} \hat{k}_x(\omega)= \frac{1}{(2\pi)^d}\mid\int_{\mathbb{R}^d} e^{-i\langle y,\omega\rangle}K(y-x)dy= e^{-i\langle u,\omega\rangle}\hat{K}(\omega)\tag{3.49} \end{equation}
    On regarde la norme maintenant de \(k_x(y)\) qui est donné par
    \begin{equation*} \Norm k_x(y)\Norm_{H_k}=\int_{\mathbb{R}^d} \frac{\mid^2\hat{k}_x(\omega)\mid^2}{2} \end{equation*}
    En utilisant le calcul (3.49) sur \(\hat{k}_x(\omega)\) on obtient que
    \begin{equation*} \Norm k_x(y)\Norm_{H_k}=\int_{\mathbb{R}^d} \mid\hat{K}(\omega)\mid \lt \infty \end{equation*}
    Puisque le noyau est \(L^1\) donc \(k_x(y) \in H_k\text{.}\)
  3. On montre que \(\forall x\in V, f\in H_k,\quad \langle f,k(x,.)\rangle_{H_k}=f(x)\):
    \begin{equation*} \langle f,k(x,.)\rangle_{H_k} =\frac{1}{(2\pi)^d}\int_{\mathbb{R}^d}\frac{\hat{k}_x(\omega)\hat{f^*}(\omega)}{\hat{K}(\omega)}d\omega \end{equation*}
    on utilise (3.49) pour obtenit
    \begin{equation*} \langle f,k(x,.)\rangle_{H_k} =\frac{1}{(2\pi)^d}\int_{\mathbb{R}^d}\hat{f^*}(\omega)e^{-i\langle x,\omega\rangle} d\omega=f(x) \end{equation*}
Preuve.
Admis
A Partir de la on peut proposer plusieurs noyaux.
Définition 3.94. Noyau Gaussien.
Soit un noyau invariant par translation \(k(x,y)=K(x-y)\) avec \((x,y)\in \mathbb{R}^d\) et
\begin{equation*} K(x-y)=e^{\frac{\Norm x-y\Norm_2^2}{2\sigma^2}} \end{equation*}
La transformé de Fourier du noyau est
\begin{equation*} \hat{K}(\omega)=e^{-\frac{\sigma^2\omega}{2}} \end{equation*}
et le RKHS associé est
\begin{equation*} H_k=\left\{f\in L^2(\mathbb{R}^d), \quad \mbox{tel que } \quad \int \mid \hat{f}(\omega)\mid^2e^{\frac{\sigma^2\omega}{2}}\le \infty\right\} \end{equation*}
Cela correspond aux fonctions \(C^{\infty}(\mathbb{R}^d)\)
En effet il s’agit de fonction dont le spectre décroît exponentiellement avec la fréquence. Cela revient donc au fait que les fonctions sont le plus régulières possible.
Définition 3.95. Noyau de Laplace.
Soit un noyau invariant par translation \(k(x,y)=K(x-y)\) avec \((x,y)\in \mathbb{R}\) et
\begin{equation*} K(x-y)=\frac12e^{\gamma\Norm x-y\Norm_1} \end{equation*}
La transformé de Fourier du noyau est
\begin{equation*} \hat{K}(\omega)=\frac{\gamma}{\gamma+\omega^2} \end{equation*}
et le RKHS associé est
\begin{equation*} H_k=\left\{f\in L^2(\mathbb{R}), \quad \mbox{tel que } \quad \int \mid \hat{f}(\omega)\mid^2 \frac{\gamma+\omega^2}{\gamma} \le \infty\right\} \end{equation*}
Cela correspond aux fonctions de l’espace de Sobolev \(H^1(\mathbb{R})\text{.}\)
On voit ici que le noyau de Laplace permet de générer des solutions nettement moins régulières (continue quand même par les injections de Sobolev). Ce noyau existe en dimension \(d\text{,}\) mais son espace associé ne semble pas être le même.
Définition 3.96. Noyau de Matern.
Soit un noyau invariant par translation \(k(x,y)=K(x-y)\) avec \((x,y)\in \mathbb{R}^d\) et
pour tout \(\alpha,h>0\)
\begin{equation*} K_{\alpha,h}(x-y)=\frac{1}{2^{\alpha-1}\Gamma(\alpha)}\left( \frac{\sqrt{2\alpha}\Norm x-y\Norm_2 }{h}\right)^{\alpha} B_{\alpha}\left( \frac{\sqrt{2\alpha}\Norm x-y\Norm_2 }{h}\right) \end{equation*}
avec \(B_{\alpha}\) de seconde espèce d’ordre \(\alpha\text{.}\)
La transformé de Fourier du noyau est
\begin{equation*} \hat{K}(\omega)=C_{\alpha,h,d}\left(\frac{2\alpha}{h^2}+4\pi^2\Norm \omega\Norm_2^2\right)^{-\alpha-d/2} \end{equation*}
et le RKHS associé est
\begin{equation*} H_k=\left\{f\in L^2(\mathbb{R}), \quad \mbox{tel que } \quad \int \mid \hat{f}(\omega)\mid^2 \left(\frac{2\alpha}{h^2}+4\pi^2\Norm \omega\Norm_2^2\right)^{\alpha+d/2} \le \infty\right\} \end{equation*}
Cela correspond aux fonctions de l’espace de Sobolev \(H^{\alpha+\frac{d}{2}}(\mathbb{R}^d)\text{.}\) On voit donc qu’on obtient des fonctions avec ue régularité croissante en fonction de la dimension. Les fonctions des RKHS sont continues on pouvait donc s’attendre a ce genre de régularité par les injections de Sobolev.
Définition 3.97. Noyau passe-bande.
Soit un noyau invariant par translation \(k(x,y)=K(x-y)\) avec \((x,y)\in \mathbb{R}\) et
\(\forall \alpha>0\)
\begin{equation*} K_{\alpha,h}(x-y)=\operatorname{sin_c(\alpha(x-y))} \end{equation*}
La transformé de Fourier du noyau est
\begin{equation*} \hat{K}(\omega)=U(\omega+\alpha)-U(\omega-\alpha) \end{equation*}
avec \(U(??)\) et le RKHS associé est
\begin{equation*} H_k=\left\{f\in L^2(\mathbb{R}), \quad \mbox{tel que } \quad \int_{\mid \omega\mid \gt \alpha} \mid \hat{f}(\omega)\mid^2 =0\right\} \end{equation*}
Cela correspond aux fonctions ou le spectre est localisé dans \([-\alpha,\alpha]\text{,}\) on parle des espaces de Paley–Wiener.
On va maintenant comparer l’efficacité des différents noyaux.
Figure 3.98. On approche une fonction \(C^{\infty}([0,2])\) (en haut) et \(C^0([0,2])\) (en bas) par une regression a noyau avec un noyau RBF et un noyau de Mattern qui coincide avec un noyau exponential.
Sur la figure Figure 3.98 on compare différents noyaux. On voit que selon la régularité de la fonction le bon choix de noyau semble être celui qui génère un espace de Hilbert de régularité similaire.

Subsubsection 3.4.5.3 Noyaux et Splines

On va maintenant approcher certains noyaux avec des fonctions très utilisées comme Les Splines de lissages. On va se placer sur \(V=[0,1]\text{.}\)
Preuve.
Comme dans le cas de Mercer on doit démontrer trois propriétés.
  1. On montre que la fonctionnelle d’évaluation est continue et qu’on a un espace de Hilbert:
    \begin{equation*} \mid f(x)\mid = \mid f(x)-f(0)\mid = \int_0^1 f^{'}(x)dx \end{equation*}
    On applique Cauchy-Schwarz entre la fonction \(f^{'}\) et la fonction \(1\text{.}\) On obtient donc que
    \begin{equation*} \mid f(x)\mid \le \sqrt{x}\parallel f\parallel_{H^1} \end{equation*}
    Cela montre que si la norme \(\parallel f\parallel_{H^1}\) engendré par le produit scalaire est nulle alors la fonction est nulle. Cela nombre que le produit scalaire est bien un produit scalaire et la norme associée une norme. On a donc un espace-pré-Hilbertien. Le côté Hilbertien s’obtient de la même façon que dans la preuve du point 4 du théorème Théorème d’Aronszajn .
  2. On montre que \(k(x,.) \in H_1\):
    La fonction \(k(x,y)\) est continue, dérivable par morceau donc \(f^{'}\in L^2\) et est égal à zéro en zéro.
  3. On montre que \(\forall x\in V, f\in H_1,\quad \langle f,k(x,.)\rangle_{H}=f(x)\):
    \(\forall x \in [0,1], \quad f\in H\) on a
    \begin{equation*} \langle f,k(x,.)\rangle_h=\int_0^1 f^{'}(y)k^{'}(x,y)dy=\int_0^x f^{'}(y)dy=f(x) \end{equation*}
Ce type de noyau est utilisé pour construire des splines de lissages qui sont solution d’un problème de régression ou on régulalise par la norme \(H_1\) pour obtenir une approximation régulière. On peut aussi faire la même chose avec \(H_m\text{.}\)
\begin{equation*} H^m=\left\{ f\in C^{m-1}([0,1]), \mbox{ tel que }\quad f^{m}\in L^2([0,1]), f^k(0)=0, \forall k\in \left\{0,m-1\right\}\right\} \end{equation*}
et le noyau
\begin{equation*} k_m(x,y)=\int_0^1\frac{(x-z)^{+}(y-z)^{+}}{(m-1)!(m-1)!}dz \end{equation*}
Ce noyau permet de régulariser une régression polynomiale de façon à obtenir les polynômes les plus lisses possibles. Pour cela on utilise une régression à noyau avec le noyau
\begin{equation*} k(x,y)= \underbrace{\sum_{k=1}^{m-1}\frac{x^ky^k}{k!k!}}_{k_0}+\lambda k_m(x,y) \end{equation*}
avec \(k_0\) un noyau engendrant les polynômes de degré \(m-1\text{.}\)

Subsubsection 3.4.5.4 Noyaux et opérateur différentiel

Définition 3.100.
Soit \(H\) un espace de fonction et un opérateur différentiel \(D\) tel que
\begin{equation} Du =f , \quad u\in H\tag{3.50} \end{equation}
avec \(u\) une fonction inconnue. On appelle une fonction de green d’ l’opérateur D une fonction \(k: V\times V \rightarrow \mathbb{R}\) si \(k\) satisfait
\begin{equation*} f(x)=Du(x)=\langle D k(x,.), f\rangle_{L^2} \end{equation*}
Dans ce cas la solution du problème (3.50) s’écrit:
\begin{equation*} u(x)=\int_V k(x,y)f(y) dy \end{equation*}
Preuve.
On note \(k\) la fonction de green de l’opérateur \(D D^*\text{.}\) Ici on n’a pas besoin de démontrer que l’espace est un espace de Hilbert, car c’est par hypothèse. Il suffit donc de montrer les deux dernières propriétés pour avoir un RKHS
On montre que \(k(x,.) \in H\):
\begin{equation*} \langle k(x,.), k(x,.) \rangle_{H}= \langle D k(x,.), D k(x,.) \rangle_{L^2}= \langle D^*D k(x,.), k(x,.) \rangle_{L^2}=k(x,x) \end{equation*}
Puisque k(x,x) est borné le produit scalaire \langle k(x,.), k(x,.) \rangle_{H} aussi donc k(x,.) \in H.
On montre que \(\forall x\in V, f\in H_1 ,\quad \langle f,k(x,.)\rangle_{H}=f(x)\):
Puisque D^*D admet comme noyau k, en utilisant les propriétés on a
\begin{equation*} f(x)= \langle D^* D k(x,.),f \rangle_{L^2(V)}= \langle D k(x,.),D f \rangle_{L^2(V)}=\langle k(x,.),f \rangle_{H} \end{equation*}
ce qui conlut la preuve.

Subsubsection 3.4.5.5 Comment ajouter des a priori ?

Parfois on sait à l’avance que la fonction satisfait certaines propriétés comme la périodicité ou des symétries. Il est possible, en utilisant les règles de construction des noyaux, de construire des nouveaux noyaux et donc des RKHS qui préserveront ses propriétés par construction. On va donner rapidement quelques exemples:
  1. Périodicité
    Il suffit de construire un noyau périodique. D. Mackay a proposé un noyau basé sur le noyau Gaussien:
    \begin{equation*} k(x,y)=e^{-2 \frac{\operatorname{sin}^2(\frac{\pi}{p}\mid x- y \mid))}{l^2} } \end{equation*}
    le paramètre \(p\) décrit la période. Cet hyper paramètre peut aussi être optimisé.
  2. Symétrie par rapport à l’origine
    on peut vouloir considérer des fonctions qui admettent certaines symétries. Par exemple: \(f(x)=f(-x)\text{.}\) Pour cela il suffit de construire le noyau suivant
    \begin{equation*} k_{sym}(x,y)=k(x,y)+k(-x,y) \end{equation*}
  3. Invariance par permutation
    Il peut arriver qu’on souhaite encoder l’invariance par permutation. Par exemple la fonction d’écrit l’énergie de deux particules en interaction est une fonction qui ne dépend pas de l’ordre dans lequel on donne les particules on a donc \(f(x_1,x_2)=f(x_2,x_1)\text{.}\) Pour obtenir cette propriété on peut utiliser le noyau suivant
    \begin{equation*} k_{inv}(x_1,x_2,y_1,y_2)=k(x_1,x_2,y_1,y_2)+k(x_2,x_1,y_1,y_2) \end{equation*}