Machine à vecteurs de support

Le cas simple est le cas d'une fonction discriminante linéaire, obtenue par combinaison linéaire du vecteur d'entrée ${\displaystyle x=(\mathbf {x} _{1},...,\mathbf {x} _{N})^{T}}$, avec un vecteur de poids ${\displaystyle w=(\mathbf {w} _{1},...,\mathbf {w} _{N})^{T}}$ :

${\displaystyle h(x)=w^{T}x+w_{0}}$

Il est alors décidé que ${\displaystyle x}$ est de classe 1 si ${\displaystyle h(x)\geq 0}$ et de classe -1 sinon. C'est un classifieur linéaire.

La frontière de décision ${\displaystyle h(x)=0}$ est un hyperplan, appelé hyperplan séparateur, ou séparatrice. Le but d'un algorithme d'apprentissage supervisé est d'apprendre la fonction h(x) par le biais d'un ensemble d'apprentissage :

${\displaystyle \{(x_{1},l_{1}),(x_{2},l_{2}),\ldots ,(x_{k},l_{k}),\ldots ,(x_{p},l_{p})\}\subset \mathbb {R} ^{N}}$×${\displaystyle \{-1,1\}}$

où les ${\displaystyle l_{k}}$ sont les labels, ${\displaystyle p}$ est la taille de l'ensemble d'apprentissage, ${\displaystyle N}$ la dimension des vecteurs d'entrée. Si le problème est linéairement séparable, on doit alors avoir :

${\displaystyle l_{k}h(x_{k})\geq 0\quad 1\leq k\leq p,\quad {\mbox{ autrement dit }}\quad l_{k}(w^{T}x_{k}+w_{0})\geq 0\quad 1\leq k\leq p.}$

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.

Exemple d'un problème de discrimination à deux classes, avec une séparatrice linéaire : la droite d'équation y = x. Le problème est linéairement séparable.

Exemple d'un problème de discrimination à deux classes, avec une séparatrice non-linéaire : le cercle unité. Le problème n'est pas linéairement séparable.

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, dont les performances en apprentissage sont identiques (le risque empirique est le même), mais dont les performances en généralisation peuvent être très différentes. Pour résoudre ce problème, il a été montré[11], qu'il existe un unique hyperplan optimal, défini comme l'hyperplan qui maximise la marge entre les échantillons et l'hyperplan séparateur.

Il existe des raisons théoriques à ce choix. Vapnik a montré[11] que la capacité des classes d'hyperplans séparateurs diminue lorsque leur marge augmente.

Pour un ensemble de points linéairement séparables, il existe une infinité d'hyperplans séparateurs.

L'hyperplan optimal (en rouge) avec la marge maximale. Les échantillons entourés sont des vecteurs supports.

La marge est la distance entre l'hyperplan et les échantillons les plus proches. Ces derniers sont appelés vecteurs supports. L'hyperplan qui maximise la marge est donné par :

${\displaystyle \arg \max _{w,w_{0}}\min _{k}\{||x-x_{k}||:x\in \mathbb {R} ^{N},w^{T}x+w_{0}=0\}}$

Il s'agit donc de trouver w et w₀ remplissant ces conditions, afin de déterminer l'équation de l'hyperplan séparateur :

${\displaystyle h(x)=w^{T}x+w_{0}=0}$

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 ${\displaystyle l_{k}(w^{T}x_{k}+w_{0})\geq 0}$ comme expliqué précédemment). La distance d'un échantillon x_k à l'hyperplan est donnée par sa projection orthogonale sur le vecteur de poids[note 4] :

${\displaystyle {\frac {l_{k}(w^{T}x_{k}+w_{0})}{||w||}}}$.

L'hyperplan séparateur (w,w₀) de marge maximale est donc donné par :

${\displaystyle \arg \max _{w,w_{0}}\left\{{\frac {1}{||w||}}\min _{k}\left[l_{k}(w^{T}x_{k}+w_{0})\right]\right\}}$

Afin de faciliter l'optimisation, on choisit de normaliser w et w₀, de telle manière que les échantillons à la marge ( ${\displaystyle x_{marge}^{+}}$ pour les vecteurs supports sur la frontière positive, et ${\displaystyle x_{marge}^{-}}$ pour ceux situés sur la frontière opposée) satisfassent :

${\displaystyle {\begin{cases}w^{T}x_{marge}^{+}+w_{0}=1\\w^{T}x_{marge}^{-}+w_{0}=-1\end{cases}}}$

D'où pour tous les échantillons, ${\displaystyle k=1,\ldots ,p}$

${\displaystyle l_{k}(w^{T}x_{k}+w_{0})\geq 1}$

Cette normalisation est parfois appelée la forme canonique de l'hyperplan, ou hyperplan canonique[12].

Avec cette mise à l'échelle, la marge vaut désormais ${\displaystyle {\frac {1}{||w||}}}$, il s'agit donc de maximiser ${\displaystyle ||w||^{-1}}$. La formulation dite primale des SVM s'exprime alors sous la forme suivante[note 5] :

${\displaystyle {\mbox{Minimiser}}\quad {\frac {1}{2}}||w||^{2}\quad {\mbox{sous les contraintes}}\quad l_{k}(w^{T}x_{k}+w_{0})\geq 1}$

Ceci peut se résoudre par la méthode classique des multiplicateurs de Lagrange, où le lagrangien est donné par :

${\displaystyle L(w,w_{0},\alpha )={\frac {1}{2}}||w||^{2}-\sum _{k=1}^{p}\alpha _{k}\left\{l_{k}(w^{T}x_{k}+w_{0})-1\right\}\qquad \qquad (1)}$

Le lagrangien doit être minimisé par rapport à w et w₀, et maximisé par rapport à α.

En annulant les dérivées partielles du lagrangien, selon les conditions de Kuhn-Tucker, on obtient :

${\displaystyle {\begin{cases}\sum _{k=1}^{p}\alpha _{k}l_{k}x_{k}&=w^{*}\\\sum _{k=1}^{p}\alpha _{k}l_{k}&=0\end{cases}}}$

En réinjectant ces valeurs dans l'équation ${\displaystyle (1)}$, on obtient la formulation duale :

${\displaystyle {\mbox{Maximiser }}{\tilde {L}}(\alpha )=\sum _{k=1}^{p}\alpha _{k}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}l_{i}l_{j}x_{i}^{T}x_{j}\qquad \qquad (2)}$ ${\displaystyle {\mbox{sous les contraintes }}\alpha _{k}\geq 0{\mbox{ , et }}\sum _{k=1}^{p}\alpha _{k}l_{k}=0}$

Ce qui donne les multiplicateurs de Lagrange optimaux ${\displaystyle \alpha _{k}^{*}}$.

Afin d'obtenir l'hyperplan solution, on remplace w par sa valeur optimale w^*, dans l'équation de l'hyperplan ${\displaystyle h(x)}$ , ce qui donne :

${\displaystyle h(x)=\sum _{k=1}^{p}\alpha _{k}^{*}l_{k}(x\cdot x_{k})+w_{0}}$

• Il y a trois remarques intéressantes à faire à propos de ce résultat. La première découle de l'une des conditions de Kuhn-Tucker, qui donne :

${\displaystyle \alpha _{k}[l_{k}h(x_{k})-1]=0\quad 1\leq k\leq p.}$

d'où

${\displaystyle {\begin{cases}\alpha _{k}&=0\\l_{k}h(x_{k})&=1\end{cases}}}$.

Les seuls points pour lesquels les contraintes du lagrangien sont actives sont donc les points tels que ${\displaystyle l_{k}h(x_{k})=1}$, 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.

• La deuxième remarque découle de la première. Seul un sous-ensemble restreint de points est nécessaire pour le calcul de la solution, les autres échantillons ne participant pas du tout à sa définition. Ceci est donc efficace au niveau de la complexité. D'autre part, le changement ou l'agrandissement de l'ensemble d'apprentissage a moins d'influence que dans un modèle de mélanges gaussiens par exemple, où tous les points participent à la solution. En particulier, le fait d'ajouter des échantillons à l'ensemble d'apprentissage qui ne sont pas des vecteurs supports n'a aucune influence sur la solution finale.

• La dernière remarque est que l'hyperplan solution ne dépend que du produit scalaire entre le vecteur d'entrée et les vecteurs supports. Cette remarque est l'origine de la deuxième innovation majeure des SVM : le passage par un espace de redescription grâce à une fonction noyau.

Exemple simple de transformation : le problème n'est pas linéairement séparable en coordonnées cartésiennes, par contre en coordonnées polaires, le problème devient linéaire. Il s'agit ici d'un exemple très simple, l'espace de redescription étant de même dimension que l'espace d'entrée.

La notion de marge maximale et la procédure de recherche de l'hyperplan séparateur telles que présentées pour l'instant ne permettent de résoudre que des problèmes de discrimination linéairement séparables. C'est une limitation sévère qui condamne à ne pouvoir résoudre que des problèmes jouets, ou très particuliers. Afin de remédier au problème de l'absence de séparateur linéaire, l'idée de l'astuce du noyau (en anglais kernel trick) est de reconsidérer le problème dans un espace de dimension supérieure, éventuellement de dimension infinie. Dans ce nouvel espace, il est alors probable qu'il existe une séparation linéaire.

Plus formellement, on applique aux vecteurs d'entrée x une transformation non-linéaire ${\displaystyle \phi }$. L'espace d'arrivée ${\displaystyle \phi (X)}$ est appelé espace de redescription. Dans cet espace, on cherche alors l'hyperplan

${\displaystyle h(x)=w^{T}\phi (x)+w_{0}}$

qui vérifie

${\displaystyle l_{k}h(x_{k})>0}$ , pour tous les points ${\displaystyle x_{k}}$ de l'ensemble d'apprentissage, c'est-à-dire l'hyperplan séparateur dans l'espace de redescription.

En utilisant la même procédure que dans le cas sans transformation, on aboutit au problème d'optimisation suivant :

${\displaystyle {\mbox{Maximiser }}{\tilde {L}}(\alpha )=\sum _{k=1}^{p}\alpha _{k}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}l_{i}l_{j}\phi (x_{i})^{T}\phi (x_{j})\qquad \qquad (3)}$

${\displaystyle {\mbox{Sous les contraintes }}\alpha _{i}\geq 0{\mbox{ , et }}\sum _{k=1}^{p}\alpha _{k}l_{k}=0}$

Le problème de cette formulation est qu'elle implique un produit scalaire entre vecteurs dans l'espace de redescription, de dimension élevée, ce qui est couteux en termes de calculs. Pour résoudre ce problème, on utilise une astuce connue sous le nom de Kernel trick, qui consiste à utiliser une fonction noyau, qui vérifie :

${\displaystyle K(x_{i},x_{j})=\phi (x_{i})^{T}\cdot \phi (x_{j})}$

d'où l'expression de l'hyperplan séparateur en fonction de la fonction noyau :

${\displaystyle h(x)=\sum _{k=1}^{p}\alpha _{k}^{*}l_{k}K(x_{k},x)+w_{0}}$

L'intérêt de la fonction noyau est double :

• Le calcul se fait dans l'espace d'origine, ceci est beaucoup moins coûteux qu'un produit scalaire en grande dimension.
• La transformation ${\displaystyle \phi }$ n'a pas besoin d'être connue explicitement, seule la fonction noyau intervient dans les calculs. On peut donc envisager des transformations complexes, et même des espaces de redescription de dimension infinie.

En pratique, on ne connaît pas la transformation ${\displaystyle \phi }$, on construit plutôt directement une fonction noyau. Celle-ci doit respecter certaines conditions, elle doit correspondre à un produit scalaire dans un espace de grande dimension. Le théorème de Mercer explicite les conditions que ${\displaystyle K}$ doit satisfaire pour être une fonction noyau : elle doit être symétrique, semi-définie positive.

L'exemple le plus simple de fonction noyau est le noyau linéaire :

${\displaystyle K(x_{i},x_{j})=x_{i}^{T}\cdot x_{j}}$

On se ramène donc au cas d'un classifieur linéaire, sans changement d'espace. L'approche par Kernel trick généralise ainsi l'approche linéaire. Le noyau linéaire est parfois employé pour évaluer la difficulté d'un problème.

Des noyaux usuels employés avec les SVM sont :

• le noyau polynomial ${\displaystyle K(x_{i},x_{j})=(x_{i}^{T}\cdot x_{j}+1)^{d}}$ ;
• le noyau gaussien ${\displaystyle K(\mathbf {x} ,\mathbf {y} )=\exp \left(-{\frac {\|\mathbf {x} -\mathbf {y} \|^{2}}{2\sigma ^{2}}}\right)}$.

En général, il n'est pas non plus possible de trouver une séparatrice linéaire dans l'espace de redescription. Il se peut aussi que des échantillons soient mal étiquetés, et que l'hyperplan séparateur ne soit pas la meilleure solution au problème de classement.

En 1995, Corinna Cortes et Vladimir Vapnik proposent une technique dite de marge souple[13], qui tolère les mauvais classements. La technique cherche un hyperplan séparateur qui minimise le nombre d'erreurs grâce à l'introduction de variables ressort ${\displaystyle \xi _{k}}$ (slack variables en anglais), qui permettent de relâcher les contraintes sur les vecteurs d'apprentissage :

${\displaystyle l_{k}(w^{T}x_{k}+w_{0})\geq 1-\xi _{k}\quad \xi _{k}\geq 0,\quad 1\leq k\leq p}$

Avec les contraintes précédentes, le problème d'optimisation est modifié par un terme de pénalité, qui pénalise les variables ressort élevées :

${\displaystyle {\mbox{Minimiser }}{\frac {1}{2}}||w||^{2}+C\sum _{k=1}^{p}\xi _{k}\quad ,\quad C>0}$

où ${\displaystyle C}$ est une constante qui permet de contrôler le compromis entre nombre d'erreurs de classement, et la largeur de la marge. Elle doit être choisie par l'utilisateur, en général par une recherche exhaustive dans l'espace des paramètres, en utilisant par exemple la validation croisée sur l'ensemble d'apprentissage. Le choix automatique de ce paramètre de régularisation est un problème statistique majeur.

Plusieurs méthodes ont été proposées pour étendre le schéma ci-dessus au cas où plus de deux classes sont à séparer. Ces schémas sont applicables à tout classifieur binaire, et ne sont donc pas spécifiques aux SVM[14]. Les deux plus connues sont appelées one versus all et one versus one. Formellement, les échantillons d'apprentissage et de test peuvent ici être classés dans ${\displaystyle M}$ classes ${\displaystyle \{C_{1},C_{2},...,C_{M}\}}$.

La méthode one-versus-all (appelée parfois one-versus-the-rest) consiste à construire ${\displaystyle M}$ classifieurs binaires en attribuant le label 1 aux échantillons de l'une des classes et le label -1 à toutes les autres. En phase de test, le classifieur donnant la valeur de confiance (e.g la marge) la plus élevée remporte le vote.

La méthode one-versus-one consiste à construire ${\displaystyle M(M-1)/2}$ classifieurs binaires en confrontant chacune des ${\displaystyle M}$ classes. En phase de test, l'échantillon à classer est analysé par chaque classifieur et un vote majoritaire permet de déterminer sa classe. Si l'on note ${\displaystyle x_{t}}$ l'échantillon à classer et ${\displaystyle h_{ij}(.)}$ le classifieur SVM séparant la classe ${\displaystyle C_{i}}$ et la classe ${\displaystyle C_{j}}$ et renvoyant le label attribué à l'échantillon à classer, alors le label attribué à ${\displaystyle x_{t}}$ peut formellement se noter ${\displaystyle Card(\{h_{i,j}(x_{t})\}\cap \{k\};i,j,k\in [1,M],i<j)}$. C'est la classe qui sera le plus souvent attribuée à ${\displaystyle x_{t}}$ quand il aura été analysé par tous les ${\displaystyle h_{ij}}$. Il peut exister une ambigüité dans le résultat du comptage, s'il n'existe pas de vote majoritaire[15]

Une généralisation de ces méthodes a été proposée en 1995[16] sous le nom d'ECOC, consistant à représenter les ensembles de classifieurs binaires comme des codes sur lesquels peuvent être appliqués les techniques de correction d'erreur.

Ces méthodes souffrent toutes de deux défauts. Dans la version one-versus-all, rien n'indique que les valeurs du résultat de classification des ${\displaystyle M}$ classifieurs soient comparables (pas de normalisation, donc possibles problèmes d'échelle)[15]. De plus le problème n'est plus équilibré, par exemple avec M=10, on utilise seulement 10 % d'exemples positifs pour 90 % d'exemples négatifs.

Vladimir Vapnik, Harris Drucker, Chris Burges, Linda Kaufman et Alex Smola ont proposé en 1996 une méthode pour utiliser des SVM afin de résoudre des problèmes de régression[17].

• (en) Vapnik, V. Statistical Learning Theory. Wiley-Interscience, New York, (1998)
• (en) Bernhard Schölkopf, Alexander J. Smola, Learning With Kernels: Support Vector Machines, Regularization, Optimization and Beyond, 2002, MIT Press.
• (en) John Shawe-Taylor, Nello Cristianini, Support Vector Machines and other kernel-based learning methods, Cambridge University Press, 2000.
• (en) Christopher J.C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 2, 121–167 (1998)
• (en) Christopher M. Bishop, Pattern Recognition And Machine Learning, Springer, 2006 (ISBN 0-387-31073-8) [détail des éditions]

On trouve une présentation en français de la classification par les machines à vecteurs de support dans :

• Jean Beney, Classification supervisée de documents : théorie et pratique, Hermes Science, février 2008, 184p.
• Vincent Barra, Antoine Cornuéjols, Laurent Miclet, Apprentissage Artificiel : Concepts et algorithmes, Eyrolles, 2021 (ISBN 978-2-416-001-04-8) [détail des éditions]

• Apprentissage automatique
• Apprentissage supervisé
• Réseau de neurones
• Modèle de mélanges gaussiens
• Théorie de Vapnik-Chervonenkis
• Machine à vecteurs de pertinence (en)
• Noyau polynomial

• (en) Introduction aux SVM
• (en) SVM-Light - Implémentation en langage C de Joachims Thorsten