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é :
«apprentissage» car l'entrée des SVM est un ensemble d'exemples, à partir desquels les SVM vont s'«entraîner» à classer les objets. Noter les importants guillemets : les SVM sont une méthode mathématico-informatique, qui n'est absolument pas capable d'apprentissage ou d'intelligence au sens où un humain peut apprendre ou faire preuve d'intelligence. L'appellation «Intelligence» Artifielle - domaine auquel appartiennent les SVM - entretient également ce type de malentendu.
«supervisé» car la base d'exemples doit être étiquetée : il faut savoir à quelle classe appartient chaque exemple.
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
La droite calculée ne dépend que des vecteurs de support - qui sont dans le cas général au nombre de trois. C'est un avantage de la méthode, qui n'est pas sensible aux points éloignés de la frontière.
En déplaçant des points, vous avez du tomber sur des situations où les points bleus et rouge ne sont pas linéairement séparables. On peut adapter les SVM pour tout de même calculer une séparation linéaire - en considérant certains points comme des données aberrantes (une traduction peu satisfaisante du terme anglais généralement utilisé : outlier). Cliquer sur cette phrase pour faire apparaitre une telle situation.
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.
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 :
convexe : la fonction objectif à minimiser est une fonction convexe;
sous contraintes affines.
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\}$
Si $\alpha_i=0$, $y_iH_{\mathbf{w}}(\mathbf{x^i})\geq 1$ (et $\mathbf{x^i}$ est alors un vecteur de support).
Si $\alpha_i=C$, $y_iH_{\mathbf{w}}(\mathbf{x^i})\leq 1$.
Si $0 < \alpha_i < C$, $y_iH_{\mathbf{w}}(\mathbf{x^i}) = 1$
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
On se donne $i\neq j$ tels que les conditions KKT ne soient pas vérifiées en $i$ ou en $j$.
Quelques calculs donnent alors des formules
explicites permettant de modifier $\alpha_i$ et
$\alpha_j$ de façon à ce que les conditions KKT soient
maintenant satisfaites en $i$ et en $j$.
On recommence avec d'autres $i$ et $j$ jusqu'à ce
que toutes les conditions KKT soient satisfaites.
Quelques remarques :
Forcer les conditions KKT pour deux indices $i$ et $j$ risque de les faire perdre pour d'autres indices. Cependant on peut prouver la convergence de l'algorithme pour de bons choix des indices.
Le choix des indices $i$ et $j$ influe également sur la vitesse d'exécution de l'algorithme. La méthode complète propose des heuristiques pour essayer d'effectuer les meilleurs choix possibles à chaque étape.
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
Apprentissage machine, de la théorie à la pratique (Massih-Reza Amini) pour une introduction au problème.
The Simplified SMO Algorithm, extrait du cours CS229: Machine Learning de l'université de Stanford. Une version simplifiée (mais fonctionnelle) de l'algorithme complet détaillé dans l'article suivant :
Sequential Minimal Optimization : A Fast Algorithm for Training SVM (John C.Platt)