SVM : Machines à Vecteurs de Support ou Séparateurs à Vastes Marges

SVM principe de fonctionnement général

Notions de base : Hyperplan, marge et support vecteur

Pour deux classes d’exemples donnés, le but de SVM est de trouver un classificateur qui va séparer les données et maximiser la distance entre ces deux classes. Avec SVM, ce classificateur est un classificateur linéaire appelé hyperplan. Dans le schéma qui suit, on détermine un hyperplan qui sépare les deux ensembles de points. Les points les plus proches, qui seuls sont utilisés pour la détermination de l’hyperplan, sont appelés vecteurs de support. Il est évident qu’il existe une multitude d’hyperplan valide mais la propriété remarquable des SVM est que cet hyperplan doit être optimal. Nous allons donc en plus chercher parmi les hyperplans valides, celui qui passe « au milieu » des points des deux classes d’exemples. Intuitivement, cela revient à chercher l’hyperplan le « plus sûr ». En effet, supposons qu’un exemple n’ait pas été décrit parfaitement, une petite variation ne modifiera pas sa classification si sa distance à l’hyperplan est grande. Formellement, cela revient à chercher un hyperplan dont la distance minimale aux exemples d’apprentissage est maximale. On appelle cette distance « marge » entre l’hyperplan et les exemples. L’hyperplan séparateur optimal est celui qui maximise la marge. Comme on cherche à maximiser cette marge, on parlera de séparateurs à vaste marge.

Pourquoi maximiser la marge ?

Intuitivement, le fait d’avoir une marge plus large procure plus de sécurité lorsque l’on classe un nouvel exemple. De plus, si l’on trouve le classificateur qui se comporte le mieux vis-à-vis des données d’apprentissage, il est clair qu’il sera aussi celui qui permettra au mieux de classer les nouveaux exemples. Dans le schéma qui suit, la partie droite nous montre qu’avec un hyperplan optimal, un nouvel exemple reste bien classé alors qu’il tombe dans la marge. On constate sur la partie gauche qu’avec une plus petite marge, l’exemple se voit mal classé. En général, la classification d’un nouvel exemple inconnu est donnée par sa position par rapport à l’hyperplan optimal. Dans le schéma suivant, le nouvel élément sera classé dans la catégorie des « + ».

 Linéarité et non-linéarité

Parmi les modèles des SVM, on constate les cas linéairement séparable et les cas non linéairement séparable. Les premiers sont les plus simple de SVM car ils permettent de trouver facilement le classificateur linéaire. Dans la plupart des problèmes réels il n’y a pas de séparation linéaire possible entre les données, le classificateur de marge maximale ne peut pas être utilisé car il fonctionne seulement si les classes de données d’apprentissage sont linéairement séparables.

Cas non linéaire

Pour surmonter les inconvénients des cas non linéairement séparable, l’idée des SVM est de changer l’espace des données. La transformation non linéaire des données peut permettre une séparation linéaire des exemples dans un nouvel espace. On va donc avoir un changement de dimension. Cette nouvelle dimension est appelé « espace de re-description ». En effet, intuitivement, plus la dimension de l’espace de re-description est grande, plus la probabilité de pouvoir trouver un hyperplan séparateur entre les exemples est élevée. On a donc une transformation d’un problème de séparation non linéaire dans l’espace de représentation en un problème de séparation linéaire dans un espace de re-description de plus grande dimension. Cette transformation non linéaire est réalisée via une fonction noyau. En pratique, quelques familles de fonctions noyau paramétrables sont connues et il revient à l’utilisateur de SVM d’effectuer des test pour déterminer celle qui convient le mieux pour son application. On peut citer les exemples de noyaux suivants : polynomiale, gaussien, sigmoïde et la placien.