Méthodes à noyaux

Les méthodes à noyaux (parfois aussi méthodes à noyau) constituent une famille d'algorithmes d'apprentissage automatique et d'analyse de données. Elles peuvent être utilisées à la fois pour l'apprentissage supervisé et non supervisé.

Ces méthodes doivent leur nom au fait qu'elles manipulent les données via une fonction appelée noyau (kernel en anglais) ou fonction de covariance, qui peut s'interpréter comme une mesure de la similarité entre deux points de l'espace des données. Le noyau est un paramètre de l'algorithme, et différentes mesures de similarité peuvent donc être employées afin de s'adapter à la nature des données.

Lorsque le noyau utilisé est défini positif, il induit implicitement un espace de Hilbert à noyau reproduisant ainsi qu'une transformation permettant de plonger les données d'entrée dans cet espace. La plupart des méthodes à noyau peuvent dans ce cas s'interpréter comme l'application d'un algorithme plus simple dans cet espace. Par exemple, une machine à vecteurs de support est un classifieur non-linéaire construit en utilisant un classifieur linéaire sur les données ainsi transformées. Bien que l'espace induit puisse être de dimension élevée voire infinie, les modèles obtenus peuvent s'exprimer simplement grâce à l'astuce du noyau, sans avoir besoin de calculer explicitement la représentation des données dans l'espace induit.

Certaines méthodes, comme les estimateurs de densité par noyau, n'imposent pas que le noyau utilisé soit défini positif.

La plupart des algorithmes à noyau reposent sur des techniques d'optimisation convexe, et la solution de certains problèmes admet une expression analytique. Ces méthodes ont de solides fondements théoriques, et les modèles produits peuvent être analysés dans le cadre de la théorie de l'apprentissage statistique.

Problèmes

Apprentissage supervisé

Parmi les méthodes à noyaux couramment utilisées, on peut citer certaines méthodes de régression non paramétrique comme la régression ridge à noyau et les méthodes d'interpolation à noyau. Les machines à vecteur de support sont un modèle courant pour résoudre certains problèmes de classification.

Régression ridge à noyau

La méthode de régression ridge à noyau est une méthode de régression basée sur l'utilisation d'une fonction objectif quadratique et de la régularisation de Tikhonov. Le problème de minimisation du risque empirique régularisé peut ainsi s'écrire :

$f^{*}\in {\underset {f\in H}{\operatorname {arg\,min} }}{\frac {1}{n}}\sum _{i=1}^{n}(f(x_{i})-y_{i})^{2}+\lambda \lVert f\rVert _{H}^{2}$

où $\lambda >0$ est un paramètre controllant le compromis entre attache aux données et régularisation, et $(H,\lVert \cdot \rVert _{H})$ un espace de Hilbert à noyau reproduisant.

Machines à vecteurs de support à noyau

Les machines à vecteurs de support sont un modèle d'apprentissage automatique utilisé pour résoudre des problèmes de classification automatique à deux classes. Ils peuvent s'interpréter comme un classifieur linéaire, obtenu en maximisant la séparation entre le classifieur et les données d'entraînement de chaque classe. Lorsque les données ne sont pas linéairement classifiables, il est courant d'utiliser des machines à vecteurs de support après plongement des données dans un espace de Hilbert à noyau reproduisant.

Ces modèles peuvent également être généralisés pour résoudre des problèmes de classification multi-classe et des problèmes de régression.

Leurs propriétés statistiques ont été largement étudiées.

Apprentissage non supervisé

Parmi les méthodes d'apprentissage non supervisé à noyaux, on peut citer l'analyse en composantes principales à noyaux et le partitionnement type k-moyennes à noyaux.

Théorie

Espaces de Hilbert à noyau reproduisant

Le fondement mathématique des méthodes à noyau est la théorie des espaces de Hilbert à noyau reproduisant. Le choix d'un noyau défini positif revient implicitement à choisir un espace de fonctions dans lequel est construit l'estimateur.

La régularité du noyau conditionne directement la régularité des fonctions appartenant à cet espace. En particulier, dans le cas d'un noyau invariant par translation défini sur $\mathbb {R} ^{d}$, le produit scalaire de l'espace de Hilbert à noyau reproduisant est directement lié à la transformée de Fourier du noyau.

Exemple : Un noyau de Matérn de paramètre de régularité $\nu$ sur $\mathbb {R} ^{d}$ induit un espace de Hilbert à noyau reproduisant qui est équivalent à un espace de Sobolev d'ordre $\nu +d/2$.

Opérateurs intégraux

Les capacités d'apprentissage des méthodes à noyau sont intrinsèquement liées aux propriétés de l'opérateur intégral associé au noyau choisi ainsi qu'à la distribution de probabilité des données. Cet opérateur peut s'interpréter comme un équivalent continu de la matrice à noyau, qui est elle calculée à partir d'un nombre fini d'échantillons.

En particulier, la vitesse de décroissance des valeurs propres de cet opérateur conditionne, via la notion de dimension effective qui est directement liée, la vitesse de convergence du modèle en fonction du nomble d'échantillons.

Implémentation: l'astuce du noyau

La plupart des algorithmes à noyau cherchent à résoudre un problème d'optimisation sur l'espace de Hilbert à noyau reproduisant induit par le noyau considéré, qui peut être de dimension infinie. Toutefois, les estimateurs obtenus en minimisant un risque empirique appartiennent, en vertu de théorèmes de représentation, à un sous-espace de dimension finie.

Les algorithmes peuvent de fait le plus souvent s'écrire en fonction de la matrice à noyau des données, qui contient les évaluations du noyau entre toutes les paires de points du jeu de données.

Choix du noyau

Parmi les noyaux couramment utilisés pour des données appartenant à $\mathbb {R} ^{d}$, on peut citer notamment les noyaux gaussiens, laplaciens, de Matérn, polynomiaux.

Espaces structurés

Un avantage des méthodes à noyaux est qu'elles peuvent être utilisées facilement sur d'autres espaces par la définition de noyaux adaptés, mais sans avoir besoin de définir explicitement un plongement des données dans un espace euclidien. Des noyaux ont ainsi été définis pour de nombreux types de données comme du texte, des images, des données temporelles, des graphes. Toutefois, chaque noyau est spécifique au cas d'usage et au type de données pour lequel il a été prévu.

Apprentissage de noyau

Depuis les années 2010, dans le cadre de l'apprentissage profond, des noyaux sont appris au moyen de réseaux de neurones. L'architecture d'un tel réseau définit une famille de fonction paramétriques. L'apprentissage du réseau consiste à déterminer les paramètres, ce qui détermine une fonction particulière. L'ensemble des couche cachées du réseau constituent donc un noyau particulier, qui transforme des données brutes (image, texte, son, parole...) en une nouvelle représentation. Ces données transformées peuvent être séparée par la couche de sortie du réseau, faisant par exemple office de classifieur.

Approximation

La plupart des méthodes à noyaux nécessitent pour être implémentées de calculer de larges matrices à noyaux. Cela pouvant être coûteux pour de grands jeux de données, de nombreuses approximations de ces modèles ont été proposées. Parmi les approximations utilisées de manière courante, on peut citer l'approximation de rang faible de matrices à noyau, qui peut être effectuée notamment par sélection de colonnes comme dans le cas de l'approximation de Nyström, ou dans le domaine fréquentiel via le calcul de descripteurs aléatoires.

Applications

Les méthodes à noyaux et leur variantes (krigeage, processus gaussiens) sont utilisées dans de nombreux domaines d'applications, notamment en géostatistiques, en astronomie, en sciences de la terre, en biologie, ou encore en optimisation bayésienne.

Voir aussi

• Estimation par noyau
• Processus gaussien
• Krigeage

Notes et références

Bibliographie

• (en) Ian Goodfellow, Yoshua Bengio et Aaron Courville, Deep Learning, MIT Press, 2016 (ISBN 0262035618, lire en ligne) [détail des éditions]
• H. Wendland, Scattered Data Approximation, Cambridge University Press, coll. « Cambridge Monographs on Applied and Computational Mathematics », 2004 (ISBN 0-521-84335-9)