Kernel trick

Un article de Wikipédia, l'encyclopédie libre.

En apprentissage automatique, le kernel trick (l'astuce du noyau) est une méthode qui consiste à utiliser un classifieur linéaire pour résoudre un problème non-linéaire, en transformant l'espace de représentation des données d'entrées en un espace de plus grande dimension, où le classifieur linéaire est alors utilisé. La discrimination linéaire dans l'espace de grande dimension (appelé aussi espace de redescription) est équivalente à une discrimination non-linéaire dans l'espace d'origine. Le kernel trick a été publié en 1964 par Aizerman et al.^[1]

L'astuce du noyau s'utilise dans un algorithme qui ne dépend que du produit scalaire entre 2 vecteurs d'entrée x et y. Après passage à un espace de redescription par une transformation $\varphi$ , l'algorithme n'est plus dépendant que du produit scalaire:

$\varphi(x)\cdot\varphi(y)$

Le problème de ce produit scalaire est qu'il est effectué dans un espace de grande dimension, ce qui conduit à des calculs impraticables. L'idée est donc de remplacer ce calcul par une fonction noyau telle que:

$K(x,y) = \varphi(x)\cdot\varphi(y)$

Pour réaliser cela, on utilise le théorème de Mercer, qui montre qu'étant donné une fonction noyau continue, symétrique, semi-définie positive K(x, y), elle peut s'exprimer comme un produit scalaire dans un espace de grande dimension.

Plus précisément, si les arguments de la fonction noyau sont à valeurs dans un espace mesurable X, et si le noyau est semi-défini positif, i.e.

$\sum_{i,j} K(x_i,x_j) c_i c_j \ge 0$

alors pour tout sous-ensemble {x₁, ..., x_n} de X, et sous-ensemble {c₁, ..., c_n} d'objets (en général des réels) — il existe une fonction φ(x) dont l'image correspond à un espace préhilbertien possiblement de plus grande dimension tel que:

$K(x,y) = \varphi(x)\cdot\varphi(y).$

L'astuce du noyau consiste donc à remplacer un produit scalaire dans un espace de grande dimension par une fonction noyau, facile à calculer. De cette manière, un classifieur linéaire peut facilement être transformé en un classifieur non linéaire. Un autre avantage des fonctions noyau est qu'il n'est pas nécessaire d'expliciter la transformation $\varphi$ . Celle-ci peut même transformer l'espace d'entrée en un espace de redescription infini, comme le noyau gaussien:

$K(\mathbf{x},\mathbf{y})=\exp\left(- \frac{\|\mathbf{x} - \mathbf{y}\|^2}{2 \sigma^2}\right)$

Après avoir été longuement négligé après la publication d'Aizerman de 1964, l'astuce du noyau a été popularisée par Boser at al. dans leur papier fondateur sur les Machine à vecteurs de support^[2]. L'idée a depuis été appliquée à plusieurs types d'algorithmes en apprentissage automatique et en statistiques:

[modifier] Bibliographie

(en) Bernhard Schölkopf, Alexander J. Smola, Learning With Kernels: Support Vector Machines, Regularization, Optimization and Beyond, 2002, MIT Press.

[modifier] Références

↑ M. Aizerman, E. Braverman, and L. Rozonoer, « Theoretical foundations of the potential function method in pattern recognition learning », dans Automation and Remote Control, 25, p. 821-837
↑ (en) Bernhard E. Boser, Isabelle M. Guyon, Vladimir N. Vapnik, A Training Algorithm for Optimal Margin Classifiers In Fifth Annual Workshop on Computational Learning Theory, pages 144--152, Pittsburgh, ACM. 1992