Machine à vecteurs de support - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Historique - Principe général - Résumé intuitif - Extensions

Résumé intuitif

Les séparateurs à vastes marges sont des classifieurs qui reposent sur deux idées clés, qui permettent de traiter des problèmes de discrimination non-linéaire, et de reformuler le problème de classement comme un problème d'optimisation quadratique.

La première idée clé est la notion de marge maximale. La marge est la distance entre la frontière de séparation et les échantillons les plus proches. Ces derniers sont appelés vecteurs supports. Dans les SVM, la frontière de séparation est choisie comme celle qui maximise la marge. Ce choix est justifié par la théorie de Vapnik-Chervonenkis (ou théorie statistique de l'apprentissage), qui montre que la frontière de séparation de marge maximale possède la plus petite capacité. Le problème est de trouver cette frontière séparatrice optimale, à partir d'un ensemble d'apprentissage. Ceci est fait en formulant le problème comme un problème d'optimisation quadratique, pour lequel il existe des algorithmes connus.

Afin de pouvoir traiter des cas où les données ne sont pas linéairement séparables, la deuxième idée clé des SVM est de transformer l'espace de représentation des données d'entrées en un espace de plus grande dimension (possiblement de dimension infinie), dans lequel il est probable qu'il existe une séparatrice linéaire. Ceci est réalisé grâce à une fonction noyau, qui doit respecter certaines conditions, et qui a l'avantage de ne pas nécessiter la connaissance explicite de la transformation à appliquer pour le changement d'espace. Les fonctions noyau permettent de transformer un produit scalaire dans un espace de grande dimension, ce qui est coûteux, en une simple évaluation ponctuelle d'une fonction. Cette technique est connue sous le nom de kernel trick.

Extensions

Marge souple

En général, il n'est pas non plus possible de trouver une séparatrice linéaire dans l'espace de redescription. Il se peut aussi que des échantillons soient mal étiquetés, et que l'hyperplan séparateur ne soit pas la meilleure solution au problème de classement.

En 1995, Corinna Cortes et Vladimir Vapnik proposent une technique dite de marge souple, qui tolère les mauvais classements. La technique cherche un hyperplan séparateur qui minimise le nombre d'erreurs grâce à l'introduction de variables ressort $ξ k$ (slack variables en anglais), qui permettent de relacher les contraintes sur les vecteurs d'apprentissage:

Avec les contraintes précédentes, le problème d'optimisation est modifié par un terme de pénalité, qui pénalise les variables ressort élevées:

$\mbox{Minimiser } \frac{1}{2} ||w||^2+C \sum_{k=1}^p \xi_k \quad, \quad C>0$

où $C$ est une constante qui permet de contrôler le compromis entre nombre d'erreurs de classement, et la largeur de la marge. Elle doit être choisie par l'utilisateur, en général par une recherche exhaustive dans l'espace des paramètres, en utilisant par exemple la validation croisée sur l'ensemble d'apprentissage. Le choix automatique de ce paramètre de régularisation est un problème statistique majeur.

Cas multi-classe

Plusieurs méthodes ont été proposées pour étendre le schéma ci-dessus au cas où plus de deux classes sont à séparer. Ces schémas sont applicables à tout classifieur binaire, et ne sont donc pas spécifiques aux SVM. Les deux plus connues sont appelées one versus all et one versus one. Formellement, les échantillons d'apprentissage et de test peuvent ici être classés dans $M$ classes ${C 1, C 2,..., C M}$ .

La méthode one-versus-all (appelée parfois one-versus-the-rest) consiste à construire $M$ classifieurs binaires en attribuant le label 1 aux échantillons de l'une des classes et le label -1 à toutes les autres. En phase de test, le classifieur donnant la valeur de confiance (e.g la marge) la plus élevée remporte le vote.

La méthode one-versus-one consiste à construire $M (M - 1) / 2$ classifieurs binaires en confrontant chacune des $M$ classes. En phase de test, l'échantillon à classer est analysé par chaque classifieur et un vote majoritaire permet de déterminer sa classe. Si l'on note $x t$ l'échantillon à classer et $h i j (.)$ le classifieur SVM séparant la classe $C i$ et la classe $C j$ et renvoyant le label attribué à l'échantillon à classer, alors le label attribué à $x t$ peut formellement se noter $Card(\{h_{i,j}(x_t)\} \cap \{k\};i,j,k \in [1,M], i<j)$ . C'est la classe qui sera le plus souvent attribuée à $x t$ quand il aura été analysé par tous les $h i j$ . Il peut exister une ambiguité dans le résultat du comptage, s'il n'existe pas de vote majoritaire

Une généralisation de ces méthodes a été proposée en 1995 sous le nom d'ECOC, consistant à représenter les ensembles de classifieurs binaires comme des codes sur lesquels peuvent être appliqués les techniques de correction d'erreur.

Ces méthodes souffrent toutes de deux défauts. Dans la version one-versus-all, rien n'indique que les valeurs du résultat de classification des $M$ classifieurs soient comparables (pas de normalisation, donc possibles problèmes d'échelle). De plus le problème n'est plus équilibré, par exemple avec M=10, on utilise seulement 10% d'exemples positifs pour 90% d'exemples négatifs.

Les SVM pour la régression

Vladimir Vapnik, Harris Drucker, Chris Burges, Linda Kaufman et Alex Smola ont proposé en 1996 une méthode pour utiliser des SVM afin de résoudre des problèmes de régression.