Les machines à vecteurs de support ou séparateurs à vaste marge (en anglais , SVM) sont un ensemble de techniques d'apprentissage supervisé destinées à résoudre des problèmes de discriminationLe terme anglais pour discrimination est , qui a un sens différent en français (se rapporte au ). On utilise aussi le terme classement à la place de discrimination, plus proche du terme anglais, et plus compréhensible. et de régression. Les SVM sont une généralisation des classifieurs linéaires, et appartiennent à la famille des méthodes à noyaux.
Les séparateurs à vaste marge ont été développés dans les années 1990 à partir des considérations théoriques de Vladimir Vapnik sur le développement d'une théorie statistique de l'apprentissage : la théorie de Vapnik-Tchervonenkis. Ils ont rapidement été adoptés pour leur capacité à travailler avec des données de grandes dimensions, le faible nombre d'hyperparamètres, leurs garanties théoriques, et leurs bons résultats en pratique.
Les SVM ont été appliqués à de nombreux domaines (bio-informatique, recherche d'information, vision par ordinateur, finance Bernhard Schölkopf, Alexander J. Smola, , 2002, MIT Press.…). Selon les données, la performance des machines à vecteurs de support est de même ordre, ou même supérieure, à celle d'un réseau de neurones ou d'un modèle de mélanges gaussiens.
Historique Les séparateurs à vastes marges reposent sur deux idées clés : la notion de marge maximale et la notion de fonction noyau. Ces deux notions existaient depuis plusieurs années avant qu'elles ne soient mises en commun pour construire les SVM.
L'idée des hyperplans à marge maximale a été explorée dès 1963 par Vladimir Vapnik et A. Lerner Vladimir Vapnik et A. Lerner, Pattern Recognition using Generalized Portrait Method, Automation and Remote Control, 1963., et en 1973 par Richard Duda et Peter Hart dans leur livre Pattern Classification.. Les fondations théoriques des SVM ont été explorées par Vapnik et ses collègues dans les années 70 avec le développement de la théorie de Vapnik-Tchervonenkis, et par Valiant et la théorie de l'apprentissage PAC L.G. Valiant. , , 27(11), , novembre 1984..
L'idée des fonctions noyaux n'est pas non plus nouvelle : le théorème de Mercer date de 1909 J. Mercer, . Philos. Trans. Roy. Soc. London, A 209:415--446, 1909., et l'utilité des fonctions noyaux dans le contexte de l'apprentissage artificiel a été montré dès 1964 par Aizermann, Bravermann et RozoenerM. Aizerman, E. Braverman, and L. Rozonoer, , Automation and Remote Control 25:821--837, 1964..
Ce n'est toutefois qu'en 1992 que ces idées seront bien comprises et rassemblées par Boser, Guyon et Vapnik dans un article fondateur des séparateurs à vaste marge 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. L'idée des variables ressorts, qui permet de résoudre certaines limitations pratiques importantes, ne sera introduite qu'en 1995. À partir de cette date, qui correspond à la publication du livre de VapnikV. Vapnik, , N-Y, Springer-Verlag, 1995., les SVM gagnent en popularité et sont utilisés dans de nombreuses applications.
Un brevet américain sur les SVM est déposé en 1997 par les inventeurs originels . B. Boser, I. Guyon, and V. Vapnik, US Patent 5,649,068 1997..
Résumé intuitif Les séparateurs à vastes marges sont des classificateurs 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 margeCe choix est justifié par la théorie de Vapnik-Tchervonenkis (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é. Marti A. Hearst, Support Vector Machines, IEEE Intelligent Systems, vol. 13, no. 4, , Jul/Aug, 1998. 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éparation linéaire. Ceci est réalisé grâce à une fonction noyauLa fonction noyau doit respecter les conditions du théorème de Mercer., 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 (ou astuce du noyau).
Principe général Les SVM peuvent être utilisés pour résoudre des problèmes de discrimination, c'est-à-dire décider à quelle classe appartient un échantillon, ou de régression, c'est-à-dire prédire la valeur numérique d'une variable. La résolution de ces deux problèmes passe par la construction d'une fonction qui à un vecteur d'entrée fait correspondre une sortie :
On se limite pour l'instant à un problème de discrimination à deux classes (discrimination binaire), c'est-à-dire , le vecteur d'entrée étant dans un espace X muni d'un produit scalaire. On peut prendre par exemple .
Discrimination linéaire et hyperplan séparateur Le cas simple est le cas d'une fonction discriminante linéaire, obtenue par combinaison linéaire du vecteur d'entrée , avec un vecteur de poids :
La frontière de décision est un hyperplan, appelé hyperplan séparateur, ou séparatrice. Le signe de , qui donne le côté de l'hyperplan dans lequel est localisé, permet alors de décider la classe de . Il est alors décidé que est de classe 1 si et de classe -1 sinon. C'est un classifieur linéaire.
Le but d'un algorithme d'apprentissage supervisé est d'apprendre la fonction h(x) par le biais d'un ensemble d'apprentissage : × où les sont les points dans un espace de dimension , les sont les labels qui valent , est la taille de l'ensemble d'apprentissage, et la dimension des vecteurs d'entrée. Si le problème est linéairement séparable, alors le signe de est égal à pour tout . Dit autrement :
Exemple Imaginons un plan (espace à deux dimensions) dans lequel sont répartis deux groupes de points. Ces points sont associés à un groupe : les points (+) pour y > x et les points (-) pour y < x. On peut trouver un séparateur linéaire évident dans cet exemple, la droite d'équation y = x. Le problème est dit linéairement séparable.
Pour des problèmes plus compliqués, il n'existe en général pas de séparatrice linéaire. Imaginons par exemple un plan dans lequel les points (-) sont regroupés à l'intérieur d'un cercle, avec des points (+) tout autour : aucun séparateur linéaire ne peut correctement séparer les groupes : le problème n'est pas linéairement séparable. Il n'existe pas d'hyperplan séparateur.
Marge maximale On se place désormais dans le cas où le problème est linéairement séparable. Même dans ce cas simple, le choix de l'hyperplan séparateur n'est pas évident. Il existe en effet une infinité d'hyperplans séparateurs. On le voit bien en deux dimensions comme montré dans la figure ci-dessous : on continue à séparer les points positifs des points négatifs si on bouge et tourne un peu une droite qui les séparait déjà. Toutes ces hyperplans séparateurs ont des performances en apprentissage identiques (le risque empirique est le même), mais les performances en généralisation peuvent être très différentes.Pour résoudre ce problème, il a été montré par Vapnik et Kotz en 1982V. Vapnik, et S. Kotz, Estimation of Dependences Based on Empirical Data, Springer Series in Statistics, 1982, ., qu'il existe un unique hyperplan optimal. Il est défini comme l'hyperplan qui maximise la marge entre les échantillons et l'hyperplan séparateur. On veut que l'hyperplan choisi (par exemple la droite en deux dimensions) soit la plus loin des points. Il existe des raisons théoriques à ce choix. Vapnik et Kotz ont montré que la capacité des classes d'hyperplans séparateurs diminue lorsque leur marge augmente.
La marge est la distance entre l'hyperplan et les échantillons les plus proches. Ces derniers sont appelés vecteurs supports. On rappelle que l'hyperplan à trouver est paramétré par les poids w et w0 et que son équation . Le but est de trouver les poids w et w0 afin de maximiser la marge. Etant donné un tel hyperplan, la marge est définie par . Le minimum sur k permet de trouver l'échantillon le plus proche de l'hyperplan. Ainsi, l'hyperplan qui maximise la marge est donné par : .
Recherche de l'hyperplan optimal Formulation primale La marge est la plus petite distance entre les échantillons d'apprentissage et l'hyperplan séparateur qui satisfasse la condition de séparabilité (à savoir comme expliqué précédemment). La distance d'un échantillon xk à l'hyperplan est donnée par sa projection orthogonale sur le vecteur de poidsPour un hyperplan d'équation , la distance de tout point a de l'espace à l'hyperplan est : .
L'hyperplan séparateur (w,w0) de marge maximale est donc donné par :
Afin de faciliter l'optimisation, on choisit de normaliser w et w0, de telle manière que les échantillons à la marge ( pour les vecteurs supports sur la frontière positive, et pour ceux situés sur la frontière opposée) satisfassent :
D'où pour tous les échantillons,
Cette normalisation est parfois appelée la forme canonique de l'hyperplan, ou hyperplan canonique Bernhard Schölkopf, Alexander J. Smola, Learning With Kernels: Support Vector Machines, Regularization, Optimization and Beyond, 2002, MIT Press, .
Avec cette mise à l'échelle, la marge vaut désormais , il s'agit donc de maximiser . La formulation dite primale des SVM s'exprime alors sous la forme suivanteMaximiser est équivalent à minimiser . Le carré est pris pour se débarrasser de la racine carrée incluse dans la norme. Le 1/2 n'est présent que pour faciliter la lisibilité des calculs et du résultat de l'optimisation. :
Ceci peut se résoudre par la méthode des multiplicateurs de Lagrange, où le lagrangien est donné par :
Le lagrangien doit être minimisé par rapport à w et w0, et maximisé par rapport à α.
Formulation duale En annulant les dérivées partielles du lagrangien, selon les conditions de Kuhn-Tucker, on obtient :
En réinjectant ces valeurs dans l'équation , on obtient la formulation duale :
Ce qui donne les multiplicateurs de Lagrange optimaux .
Afin d'obtenir l'hyperplan solution, on remplace w par sa valeur optimale w*, dans l'équation de l'hyperplan , ce qui donne :
Conséquences Il y a trois remarques intéressantes à faire à propos de ce résultat. La première découle de l'une des conditions de Karush-Kuhn-Tucker, qui donne :
d'où . Les seuls points pour lesquels les contraintes du lagrangien sont actives sont donc les points tels que , qui sont les points situés sur les hyperplans de marges maximales. En d'autres termes, seuls les vecteurs supports participent à la définition de l'hyperplan optimal.