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é :

I - 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.



II - Un exemple : la reconnaissance optique de caractères

À venir…

III - Les mains dans le cambouis

La suite de cette page indique la démarche mathématique et informatique permettant d'aboutir à la résolution des SVM (et devrait être accessible à un bon niveau L2 si l'on ne rentre pas trop dans les détails mathématiques). En fin de page sont données des références qui en permettent une implémentation complète.

Formulation mathématique du problème : marge dure

On considère des points $\mathbf{x^1}=(x^1_1,\ \cdots\ x^1_n),\ \cdots\ \mathbf{x^p}=(x^p_1,\ \cdots\ x^p_n)\in\mathbb{R}^p$, chacun étant muni d'une étiquette $y^1\cdots y^p\in\{-1,1\}$, correspondant à sa classe. Ces points constituent notre ensemble d'exemples.

On cherche un hyperplanC'est-à-dire un espace affine de dimension $p-1$ : une droite en dimension 2, un plan en dimension 3, etc. séparant les points d'étiquette 1 des points d'étiquette -1.
On suppose dans cette partie qu'un tel hyperplan existe, i.e. que les points de la base d'exemple sont linéairement séparables - ce sont les SVM dits à marge dure (et nous verrons un peu plus loin comment relâcher cette contrainte).
Un tel hyperplan est décrit par une équation affine du type $H_{\textbf{w}}(\textbf{x})=0$, où $H((x_1\cdots x_n))=w_1x_1+\cdots + w_nx_n+w_0$ - les $w_i$ étant des paramètres réels. Il sépare l'espace en deux demi-espaces : $\mathcal{H}_{\textbf{w}}^+=\{\mathbf{x}\in\mathbb{R}^n\ |\ H_{\textbf{w}}(\textbf{x}) > 0\}$ et $\mathcal{H}_{\textbf{w}}^-=\{\mathbf{x}\in\mathbb{R}^n\ |\ H_{\textbf{w}}(\textbf{x}) < 0\}$.

On cherche un tel hyperplan de sorte que tous les points d'étiquette $-1$ soient dans $\mathcal{H}_{\textbf{w}}^-$, et tous ceux d'étiquette $+1$ dans $\mathcal{H}_{\textbf{w}}^+$. Cela peut se traduire par la propriété suivante  $$\forall i\in\{ 1\cdots p\},\ y_iH_{\textbf{w}}(\mathbf{x^i})>0$$ Remarquons que les différents paramètres $w_i$ et $\alpha$ peuvent tous être multipliés par une constante strictement positive sans changer l'hyperplan et les demi-espaces correspondants. Il est donc possible de renormaliser ces paramètres de sorte que les inéquations ci-dessus s'écrivent $$\forall i\in\{ 1\cdots p\},\ y_iH_{\textbf{w}}(\mathbf{x^i})\geq 1\ \ (\text{avec égalité pour au moins l'un des points})\ \ (1)$$ La distance d'un point $\mathbf{x}$ à l'hyperplan est donnée par $\frac{|H_{\textbf{w}}(\mathbf{x})|}{\sqrt{w_1^2+\cdots +w_n^2}}=\frac{|H_{\textbf{w}}(\mathbf{x})|}{\|\mathbf{w}\|}$. D'après $(1)$, la marge de l'hyperplan - c'est-à-dire sa distance au(x) point(s) le(s) plus proche(s) de la base d'exemple est donc égale à $\frac{1}{\|\mathbf{w}\|}$. Ces points les plus proches sont appelés vecteurs de support.

On cherche comme expliqué ci-dessus à maximiser cette marge, i.e. à minimiser $\frac{1}{2}\|\mathbf{w}\|^2$ sous les contraintes $(1)$, ce qui donne la première formulation des SVM.
Problème primal des SVM (marge dure)

Minimiser $$\frac{1}{2}\|\mathbf{w}\|^2$$
sous les contraintes $$\forall i\in\{ 1\cdots p\},\ y_iH_{\textbf{w}}(\mathbf{x^i})\geq 1$$

Marge souple

Si les points de la base d'exemple ne sont pas linéairement séparables, le problème précédent n'admettra pas de solution. On peut alors le relâcher de la façon suivante : les contraintes $(1)$ sont remplacées par $$\forall i\in\{ 1\cdots p\},\ y_iH_{\textbf{w}}(\mathbf{x^i})\geq 1-\xi_i\ \ (\text{avec égalité pour au moins l'un des points})\ \ (2)$$ où les $\xi_i\geq 0$ - appelées variables ressorts - donnent une certaine souplesse : dans la mesure où, si $\xi_i\geq 1$, le membre de droite devient négatif, le $\mathbf{x^i}$ correspondant peut passer de l'autre côté de l'hyperplan, i.e. à être «mal classé».

À la fonction à minimiser on ajoute alors un terme $C\sum_{i=1}^p\xi_i$, qui pénalise le recours à ces ressorts. $C>0$ est un paramètre qui gère cette pénalité. Lorsque $C\longrightarrow\infty$, on se rapproche d'une marge dure.
Problème primal des SVM (marge souple)

Minimiser $$\frac{1}{2}\|\mathbf{w}\|^2+C\sum_{i=1}^p\xi_i$$
sous les contraintes $$\forall i\in\{ 1\cdots p\},\ y_iH_{\textbf{w}}(\mathbf{x^i})\geq 1-\xi_i$$ $$\forall i\in\{ 1\cdots p\},\ \xi_i\geq 0$$

Problème dual

Notre problème primal est un problème d'optimisation : Ces problèmes - et en fait des problèmes beaucoup plus généraux - sont étudiés dans le cadre de l'optimisation convexe. Il s'agit d'une branche des mathématiques intéressante, et abordable avec un bon bagage de CPGE. Je ne vais pas donner de résultats généraux ici, mais me contenter dans la suite d'appliquer ces résultats au cas particulier qui nous intéresse ici.

Le problème primal est équivalent à un problème dit dual :
Problème dual des SVM

Maximiser (pour les variables $\alpha_i\in\mathbb{R}$) $$\sum_{i=1}^p\alpha_i-\sum_{i=1}^p\sum_{j=1}^py_iy_j\alpha_i\alpha_j<\mathbf{x^i},\mathbf{x^j}>$$
sous les contraintes $$\forall i\in\{ 1\cdots p\},\ 0\leq \alpha_i\leq C$$ et $$\sum_{i=1}^py_i\alpha_i=0$$
Le passage du problème primal au dual se fait par l'intermédiaire d'un Lagrangien - dont le principe sera expliqué dans une autre page.
Une fois ce problème dual résolu, on peut retrouver la solution optimale du primal - i.e. les paramètres de l'hyperplan - à l'aide des formules $\forall j\in\{1,\cdots n\}\ \ w_j=\sum_{i=1}^py_i\alpha_ix^i_j$ et $w_0=\left(\sum_{j=1}^nw_jx^i_j\right)-y_i$ pour un $i$ tel que $\alpha_i>0$.
Noter que dans le problème dual, les exemples $\mathbf{x^i}$ apparaissent comme paramètres et uniquement à l'intérieur de produits scalaires - ce qui va permettre
le coup du noyau dont il a été question ci-dessus.

Résolution du problème dual

Un peu de théorie d'optimisation convexe en plus donne des conditions nécessaires et suffisantes - appelées conditions de Karush-Kuhn-Tucker (KKT) pour qu'un vecteur $(\alpha_1,\cdots \alpha_p)$ satisfaisant les contraintes soit l'optimum du problème dual :
Pour tout $i\in\{1,\cdots p\}$ Ces conditions sont en particulier suffisantes pour avoir l'optimum. On peut donc directement chercher un vecteur $(\alpha_1,\cdots \alpha_p)$ vérifiant les conditions KKT.

L'idée globale de l'algorithme SMO (Sequential Minimal Optimization - qui est utilisé sur cette page) est la suivante :
Schéma général de l'algorithme SMP
Quelques remarques : Les références données ci-dessous ont permis l'implémentation de SMO pour les applications ci-dessus. Si vous souhaitez également l'implémenter de A à Z, je conseille de commencer par la version simplifiée du cours de Stanford…

Références