retour

Séparateurs à vaste marge

On s'intéresse à des objets - chacun étant décrit par un vecteur (ou point) de $\mathbb{R}^n$ correspondant à $n$ caractéristiques de cet objet. Un objet peut appartenir à des classes différentes $C_1$, $C_2$… On cherche à construire un classifieur, c'est-à-dire une méthode automatisée permettant de décider, pour un objet donné, à quelle classe il appartient.

Exemple typique : la reconnaissance de caractères. Étant donné une image représentant un chiffre (qui peut être codée comme un élément de $\mathbb{R}^n$ - par exemple la liste de ses pixels), on voudrait pouvoir automatiquement savoir s'il s'agit d'un «0», d'un «1», etc.

Les séparateurs à vaste marge sont une méthode permettant de construire un tel classifieur. Il s'agit d'une méthode d'apprentissage supervisé :

L'idée, et quelques exemples interactifs.

Dans la suite, je me placerai en dimension 2 (les objets à classer sont représentés par un vecteur de $\mathbb{R}^2$ - que nous verrons comme un point par commodité), et dans le cadre d'un problème à deux classes seulement : les points rouges et les points bleus.

Avant de rentrer dans les détails mathématiques et algorithmiques - qui ne sont pas évidents - je vais expliquer les idées principales qui sont à l'origine des SVM.

Séparation linéaire, «vaste marge»

La figure ci-dessous montre ce que nous voulons faire : étant donné des exemples appartenant à nos deux classes (les points rouges et bleus), nous voulons séparer le plan en deux parties - l'une contenant les points rouges, et l'autre les points bleus. De sorte que, si un nouvel objet arrive, il suffise de regarder quelle partie du plan il est situé pour savoir à quelle classe il appartient.
Une idée assez naturelle consiste à essayer de séparer les points rouges et bleus par une droite. À noter qu'il existe en général une infinité de droites possibles. L'idée des SVM est de choisir celle qui a la marge maximale - la marge désignant la distance entre la droite et le ou les points qui en sont le plus proche. Ce choix va permettre aux SVM de bien généraliser le classement de nouvelles données. Les points pour lesquels la marge est atteinte sont appelés vecteurs de support - auxquels la méthode doit son nom en anglais (Support Vector Machine). Dans notre exemple, il y a deux vecteurs de support bleus, et un rouge.

Sur la figure ci-dessous, vous pouvez déplacer les points, supprimer ou créer un nouveau point en cliquant (click gauche pour un point bleu, droit pour un rouge).


Linéairement séparable

Séparation non linéaire

Problème : certaines données ne sont pas correctement modélisées par une séparation linéaire - indépendamment des outliers : cliquer sur cette phrase pour voir un exemple.
La deuxième bonne idée des SVM (après la marge maximale) est de plonger les données dans un espace de dimension plus grande. Les figures ci-dessous illustrent cette idée : les données non linéairement séparables de l'image de gauche (qui est également interactive) se voient attribuer une troisième dimension (que l'on peut voir comme une altitude), de sorte que les points sont maintenant sur un cône dans $\mathbb{R}^3$ (cf figure de droite, que vous pouvez faire tourner pour mieux la visualiser). Dans ce nouvel espace (appelé espace de redescription), les points deviennent linéairement séparables (par un plan - l'extension naturelle de notre droite dans $\mathbb{R}^2$). On projette l'intersection du cône avec le plan séparateur dans $\mathbb{R}^2$, et on obtient alors la séparation elliptique de la figure de gauche. Cette méthode permet donc de séparer nos points par une courbe choisie parmi un ensemble plus riche que les droitesEn l'occurrence des branches de coniques. Autre exemple : cliquer sur cette phrase pour faire apparaitre une configuration où les points sont séparés par une branche d'hyperbole.

Le kernel trick (le «coup du noyau»)

Le choix de la dimension 3 et du cône est un peu arbitraire : en particulier, choisir un espace de redescription de dimension plus grande pourrait permettre de séparer les points avec des familles de courbes encore plus riches. En pratique, on ne transporte pas explicitement les points dans ce nouvel espace, mais on utilise le kernel trick (que l'on pourrait traduire par «le coup du noyau»).
Considérons des vecteurs de $\mathbb{R}^n$, de couleur soit rouge soit bleue, pour lesquels nous souhaitons calculer le séparateur de plus grand margeUne droite en dimension 2, un plan en dimension 3, un sous-espace vectoriel de dimension $n-1$ en dimension $n$. On parle d'hyperplan dans tous les cas.. Comme nous le verrons plus loin, l'algorithme standard pour résoudre ce problème est indépendant de la dimension de l'espace auquel appartiennent les vecteurs, et n'utilise que les produits scalaires de ces vecteurs entre eux.
Reprenons l'exemple de la rediscription sur le cône dans $\mathbb{R}^3$ ci-dessus. Les vecteurs ont été transformés de la façon suivante :
$(x_1,y_1)\ \longrightarrow (x_1,y_1,\sqrt{x_1^2+y_1^2})$
$(x_2,y_2)\ \longrightarrow (x_2,y_2,\sqrt{x_2^2+y_2^2})$
$\ \ \ \ \ \vdots$
L'algorithme dans $\mathbb{R}^3$ va calculer des produits scalaires du type $<(x_1,y_1,\sqrt{x_1^2+y_1^2}),(x_2,y_2,\sqrt{x_2^2+y_2^2})>=x_1x_2+y_1y_2+\sqrt{x_1^2+y_1^2}\sqrt{x_2^2+y_2^2}$.
Tout se passe donc comme si on appliquait l'algorithme aux points $(x_1,y_1),\ (x_2,y_2),\dots$ dans $\mathbb{R}^2$, mais en remplaçant le produit scalaire usuel par la fonction $K:((x_1,y_1), (x_2,y_2)) \longrightarrow x_1x_2+y_1y_2+\sqrt{x_1^2+y_1^2}\sqrt{x_2^2+y_2^2}$ - qui est appelé noyau. Plutôt que de transporter explicitement les points dans un espace de redescription, on va donc se donner un tel noyau. On n'a même plus besoin de connaître explicitement l'espace de redescription !

Les noyaux les plus utilisés sont des noyaux gaussiens, du type $K:(x,y)\mapsto e^{\frac{-\|x-y\|^2}{2\sigma^2}}$.
L'application ci-dessous (où vous pouvez à nouveau manipuler les points) montre des résultats obtenus par cette méthode. Les zones rouge et bleue correspondent aux classes attribuées à une nouvelle donnée qui tomberait dans l'une ou l'autre de ces zones.



Les mains dans le cambouis

À venir…