• 10 heures
  • Moyenne
Licence

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 02/08/2023

Maximisez la marge de séparation entre vos classes

Cas linéairement séparable

Vous avez déjà vu comment transformer la régression linéaire pour prédire la probabilité de l'appartenance d'un point à la classe positive. Mais puisqu'on parle de modèles linéaires, peut-on essayer de trouver un hyperplan (en deux dimensions, une droite) qui sépare « au mieux » les deux classes ?

Comment définir « au mieux » ? Commençons par considérer le cas linéairement séparable, autrement dit celui dans lequel il existe au moins un hyperplan $\(\mathcal{H}\)$ tel que tous les points d'une classe soient d'un côté de $\(\mathcal{H}\)$ et tous les points de l'autre classe soient de l'autre côté de $\(\mathcal{H}\)$ .

Marge d'un hyperplan séparateur

En fait, si les données sont linéairement séparables, il existe généralement une infinité d'hyperplans séparateurs qui classifient correctement les données. (le schéma ci-dessous, en dimension 2, devrait vous en convaincre). Pour formaliser lequel parmi ces multiples hyperplans nous convient le mieux, nous allons définir la marge d'un hyperplan séparateur $\(\mathcal{H}\)$ comme deux fois la distance de $\(\mathcal{H}\)$ au point du jeu de données qui en est le plus proche. (Il peut y avoir plusieurs points qui sont les plus proches de $\(\mathcal{H}\)$, comme sur le schéma ci-dessous.)

La marge est le double de la distance entre l'hyperplan séparateur et les observations les plus proches.
La marge est le double de la distance entre l'hyperplan séparateur et les observations les plus proches (points cerclés de noir).

Comment utiliser ce concept de marge pour choisir un hyperplan séparateur ? L'idée derrière les SVMs est de chercher un hyperplan de marge maximale. Un hyperplan de marge maximale se situe à mi-distance entre les points positifs et les points négatifs dont il est le plus proche (voir illustration ci-dessous). En effet, si $\(\mathcal{H}\)$ est plus proche des points positifs que des points négatifs, on peut le déplacer vers les points négatifs et augmenter sa marge.

Un hyperplan séparateur $\(\mathcal{H}\)$ de marge maximale $\(\gamma \)$ définit une zone, un « no man's land » en quelque sorte, délimitée par deux hyperplans $\(\mathcal{H}_+ \)$ et $\(\mathcal{H}_- \)$ parallèles à $\(\mathcal{H}\)$ , situés chacun à une distance $\(\frac{\gamma }{2}\)$ de $\(\mathcal{H}\)$ , et entre lesquels il n'y a aucun point du jeu de données. Ce no man's land est souvent appelé la zone d'indécision car on manque d'information pour classifier les points dans cette zone (notre décision de positionner la frontière de décision, c'est-à-dire l'hyperplan séparateur, au milieu de cette zone est basée sur un choix de modélisation et non pas sur les données).

Le(s) point(s) positif(s) le(s) plus proche(s) de $\(\mathcal{H}\)$ sont situés sur $\(\mathcal{H}_+\)$ , et de même, le(s) point(s) négatif(s) le(s) plus proche(s) de $\(\mathcal{H}\)$ sont situés sur $\(\mathcal{H}_-\)$ . Ainsi, ces points  supportent (ou, disons, soutiennent) $\(\mathcal{H}_-\)$ et   $\(\mathcal{H}_+\)$  et s'appellent les vecteurs de support, d'où le nom de machine à vecteurs de support ou Support Vector Machine (SVM) de l'algorithme que nous allons découvrir aujourd'hui.

Séparatrice à marge maximale. Les observations cerclées de noirs sont les vecteurs de support.
Séparatrice à marge maximale. Les observations cerclées de noirs sont les vecteurs de support.

Formulation du SVM

Très bien, mais comment trouver un hyperplan séparateur à marge maximale ?

Considérons nos données : n points en p dimensions, représentés par la matrice  $\(X \in \mathbb{R}^{n×p},\)$ d'étiquettes représentées par un vecteur $\(y \in \{-1,1\}^n.\)$

L'équation d'un hyperplan en dimension p est paramétrisée par les coordonnées du vecteur normal à cet hyperplan, $\(w \in \mathbb{R}^p\)$ ainsi que par un scalaire $\(b \in \mathbb{R}\)$ . Nous pouvons ainsi poser que l'équation de notre hyperplan séparateur de marge maximale $\(\mathcal{H}\)$ est $\(\langle w, x \rangle + b = 0\)$ .

Les hyperplans $\(\mathcal{H}_+\)$ et $\(\mathcal{H}_-\)$ sont parallèles à $\(\mathcal{H}\)$ et ont donc le même vecteur normal $\(w\)$ . De plus, ils sont équidistants par rapport à $\(\mathcal{H}\)$ , et leurs équations peuvent donc s'écrire $\(\mathcal{H}_+: \langle w, x \rangle + b = K\)$ et $\(\mathcal{H}_-: \langle w, x \rangle + b = -K\)$ ou $\(K\)$ est une constante. Comme nous pouvons arbitrairement multiplier $\(w\)$ , $\(b\)$ et $\(K\)$ par n'importe quel scalaire pour obtenir les mêmes équations, nous pouvons fixer $\(K=1\)$ , et ainsi avoir $\(\mathcal{H}_+: \langle w, x \rangle + b = 1\)$ et $\(\mathcal{H}_-: \langle w, x \rangle + b = -1.\)$

Équations de l'hyperplan séparateur et des parois de la zone ne contenant aucun point du jeu d'entraînement.

Nous pouvons maintenant utiliser ces équations pour deux choses :

- Calculer la marge $\(\gamma, \)$ autrement dit la distance entre $\(\mathcal{H}_+\)$ et $\(\mathcal{H}_-.\)$ Quelques manipulations vous permettront d'arriver à $\(\gamma = \frac{2}{||w||}.\)$ 

- Garantir que nos données soient correctement classifiées : les points positifs doivent tous être à l'extérieur de $\(\mathcal{H}_+, \)$ et les points négatifs doivent tous être à l'extérieur de $\(\mathcal{H}_-.\)$  Plus précisément, nous cherchons à ce que tous les points d'étiquette $\(y^{(i)} = 1\)$ vérifient $\(\langle w, x^{(i)}\rangle + b \geq 1, \)$ et que tous les points d'étiquette $\(y^{(i)} = -1\)$ vérifient $\(\langle w, x^{(i)}\rangle + b \leq -1. \)$ On peut combiner ces deux conditions en une seule : $\(y^{(i)} \left( \langle w, x^{(i)}\rangle + b \right) \geq 1.\)$ 

Nous avons donc le problème d'optimisation suivant :

$\[\arg \max{w \in \mathbb{R}^p, b \in \mathbb{R}} \frac{2}{||w||_2} \mbox{ avec } y^{(i)} (\langle w, x^{(i)} \rangle + b) \geq 1 \,\, \forall i \in \{1, \dots, n\}.\]$

 Pour simplifier les calculs, nous allons choisir de non pas maximiser $\(\frac{2}{||w||}\)$ , mais de minimiser $\(\frac{1}{2}||w||_2^2\)$ , ce qui est équivalent. Nous obtenons ainsi le problème suivant :

$\[\arg\min_{w \in \mathbb{R}^p, b \in \mathbb{R}} \frac{1}{2}||w||_2^2 \mbox{ avec } y^{(i)} (\langle w, x^{(i)} \rangle + b) \geq 1 \,\, \forall i \in \{1, \dots, n\}.\]$

Il s'agit d'un problème d'optimisation quadratique sous contrainte, qui peut être résolu avec un certain nombre de solveurs numériques. Cependant nous verrons plus bas que l'on peut le reformuler d'une façon qui nous donnera une solution plus facilement interprétable.

Prédire avec une SVM

D'accord, mais avant ça, comment utiliser une SVM pour faire des prédictions ?

Supposons notre problème d'optimisation résolu. Nous avons donc trouvé $\(w^*\)$ et $\(b^*\)$ qui minimisent la fonction objective (correspondant à l'inverse de la marge) sous contrainte que tous les points du jeu de données soient du bon côté de la zone d'indécision.

Nous allons maintenant étiqueter comme positif  un point qui est du même côté de $\(\mathcal{H}\)$ que les points positifs du jeu d'entraînement, autrement dit $\(x\)$ pour lequel $\(\langle w^*, x \rangle + b^* \geq 0.\)$ À l'inverse, nous prédisons comme négatif un point $\(x\)$ situé de l'autre côté de l'hyperplan séparateur, autrement dit pour lequel $\(\langle w^*, x \rangle + b^* \lt 0\)$

Nous utilisons donc directement l'hyperplan séparateur comme fonction de décision : 

$\[f(x) = \langle w^*, x \rangle + b^*.\]$

  Si cette fonction est positive, le point est étiqueté positif, et inversement, si elle est négative, le point est étiqueté négatif.

Formulation duale et interprétation géométrique

Selon le vocabulaire en vigueur dans le domaine de l'optimisation sous contraintes, le problème d'optimisation que nous avons posé plus haut s'appelle un problème primal. Par une technique connue sous le nom des multiplicateurs de Lagrange, ce problème primal peut être reformulé en introduisant un scalaire $\(\alpha_i\)$ (appelé, sans surprise, un multiplicateur de Lagrange) pour chacune de nos  \(n\) contraintes ; il est équivalent à

$\[\arg\max_{\alpha \in \mathbb{R}^n} \min_{w \in \mathbb{R}^p, b \in \mathbb{R}} \frac{1}{2}||w||_2^2 - \sum_{i=1}^n \alpha_i \left( y^{(i)} (\langle w, x^{(i)} \rangle + b) - 1 \right), \mbox{ avec } \alpha_i \geq 0 \, \, \forall i \in \{1, \dots, n\}.\]$

La fonction suivante s'appelle le lagrangien du problème.

De plus les coefficients $\(\alpha_i\)$ vérifient les conditions, dites de Karush-Kuhn-Tucker (ou KKT), que pour tout $\(i \in \{1, \dots, n\},\)$

 - soit  $\(\alpha_i = 0\)$ et  $\(y^{(i)} \left( \langle w, x^{(i)} \rangle + b \right) - 1 > 0\)$ — dans ce cas, la contrainte est vérifiée strictement :  $\(y^{(i)} \left( \langle w, x^{(i)} \rangle + b \right) > 1. \)$ En d'autres termes,  $\(x^{(i)}\)$ est situé à l'extérieur de la frontière de la zone d'indécision ;

- soit  $\(\alpha_i > 0\)$ et $\(y^{(i)} \left( \langle w, x^{(i)} \rangle + b \right) - 1 = 0\)$ — dans ce cas, la contrainte est vérifiée à l'égalité : $\(y^{(i)} \left( \langle w, x^{(i)} \rangle + b \right) = 1.\)$ En d'autres termes,  $\(x^{(i)}\)$ est situé sur la frontière de la  zone d'indécision.

Cela signifie que les points $\(x^{(i)}\)$ pour lesquels $\(\alpha_i \gt 0\)$ sont les vecteurs de support, et ceux pour lesquels $\(\alpha_i = 0\)$ sont ceux situés loin de $\(\mathcal{H}_+\)$ et $\(\mathcal{H}_-\)$ .

Les vecteurs de support sont ceux pour lesquels \(\alpha\) est non nul.
Les vecteurs de support sont ceux pour lesquels  \(\alpha\) est non nul.

 Appelons $\((w^*, b^*)\)$ une solution de la minimisation du lagrangien. Celle-ci peut s'obtenir en annulant le gradient du lagrangien

- en $\(w: \nabla_w L_p = w - \sum_{i=1}^n \alpha_i y^{(i)} x^{(i)}\)$ et donc $\(w^* = \sum_{i=1}^n \alpha_i y^{(i)} x^{(i)} ;\)$ 

- et en $\(b: \nabla_b L_p(w, b) = \sum_{i=1}^n \alpha_i y^{(i)} \)$ et donc $\(\sum_{i=1}^n \alpha_i y^{(i)} = 0.\)$ 

Et donc

 Le problème d'optimisation devient donc

$\[\arg\max_{\alpha \in \mathbb{R}^n} -\frac{1}{2} \sum_{i=1}^n \sum_{l=1}^n \alpha_i \alpha_l y^{(i)} y^{(l)} \langle x^{(i)}, x^{(l)} \rangle + \sum_{i=1}^n \alpha_i\]$

 avec  $\(\alpha_i \geq 0\)$ et $\(\sum_{i=1}^n \alpha_i y^{(i)} = 0.\)$ 

Cette nouvelle formulation s'appelle la forme duale du SVM. On peut donc trouver les coefficients du SVM en résolvant ce problème d'optimisation plutôt que le primal.

Mais on aurait pu résoudre le primal directement, non ? Quel est l'intérêt d'avoir fait tous ces calculs ?

Une fois que nous avons trouvé la solution $\(\alpha^*\)$ du problème dual, nous pouvons réécrire notre fonction de décision en remplaçant $\(w^*\)$ par sa valeur  $\(\sum_{i=1}^n \alpha_i^* y^{(i)} x^{(i)}\)$ :

$\(f(x) = \sum_{i=1}^n \alpha_i^* y^{(i)} \langle x^{(i)}, x \rangle + b.\)$

Nous avons donc écrit notre fonction de décision en termes de produits scalaires entre le point à étiqueter et les points du jeu d'entraînement. Cela jouera un rôle important dans le fait de pouvoir étendre les SVM à des problèmes de classification non linéaire, comme nous le verrons dans un autre cours.

Par ailleurs, souvenez-vous de notre interprétation géométrique plus haut : seuls certains points auront un coefficient $\(\alpha_i^* \neq 0\)$ et ces points sont les vecteurs de support. La solution ne dépend donc pas des points qui ne sont pas vecteurs de supports, pour lesquels $\(\alpha_i^* = 0\)$ Et c'est logique, car si l'on déplace un peu ces points, ils restent loin de la zone d'indécision. et l'hyperplan séparateur ne changera pas. Par contre, si l'on déplace un vecteur de support, il pourra entraîner avec lui $\(\mathcal{H}_+\)$ (ou $\(\mathcal{H}_-\)$ s'il s'agit d'un point négatif), ce qui déplacera $\(\mathcal{H}.\)$

Déplacer le point orange, qui n'est pas un vecteur de support, ne change pas la solution. Déplacer le point bleu, qui est vecteur de support, modifie l'hyperplan séparateur.
Déplacer le point orange, qui n'est pas un vecteur de support, ne change pas la solution. Déplacer le point bleu, qui est vecteur de support, modifie l'hyperplan séparateur.

Ainsi, notre fonction de décision peut être calculée sur la base du produit scalaire entre le point à étiqueter et  les vecteurs de support uniquement.

Remarquons que le primal est un problème d'optimisation en p dimensions, alors que le dual est un problème d'optimisation en n dimensions. Si $\(p \ll n\)$ , alors résoudre le primal sera plus efficace. À l'inverse, si l'on a peu d'échantillons et beaucoup de variables  $\((n \ll p),\)$ résoudre le dual sera plus efficace.

Cas non-linéairement séparable

Malheureusement, dans la plupart des cas, les données ne sont pas linéairement séparables. Il va donc falloir que nous acceptions de faire des erreurs, autrement dit que certains points de notre jeu d'entraînement se retrouvent du mauvais côté de la frontière de la zone d'indécision.

Le point orange cerclé de noir est du bon côté de l'hyperplan séparateur, mais du mauvais côté de $\mathcal{H}_+$ (la ligne orange en pointillés). Le point bleu cerclé de noir est du mauvais côté de l'hyperplan séparateur.
Le point orange cerclé de noir est du bon côté de l'hyperplan séparateur, mais du mauvais côté de H- (la ligne orange en pointillés). Le point bleu cerclé de noir est du mauvais côté de l'hyperplan séparateur.

Plus la marge est grande, plus nous somme susceptibles d'avoir d'erreurs. Nous allons donc formuler un nouveau problème : minimiser la marge et l'erreur simultanément :

$\[\arg\min_{w \in \mathbb{R}^p, b \in \mathbb{R}} \frac{1}{2}||w||_2^2 + C \mbox{ erreur}.\]$

L'hyperparamètre C sert à quantifier l'importance relative du terme d'erreur et du terme de marge.

Perte hinge

Comment mesurer l'erreur de notre classifieur ? Rappelez-vous, nous souhaitons que $\(x^{(i)}\)$ soit du bon côte de la frontière de la zone d'indécision, autrement dit, que $\(y^{(i)} f(x^{(i)}) \geq 1\)$ Si c'est le cas, nous voulons que notre fonction d'erreur vaille 0. Sinon, nous allons définir une erreur qui est d'autant plus grande que $\(y^{(i)} f(x^{(i)})\)$ s'éloigne de la valeur 1, autrement dit, que $\(x^{(i)}\)$ s'éloigne de la frontière ( $\(\mathcal{H}_+\)$ s'il est positif ou $\(\mathcal{H}_-\)$ s'il est négatif).

Cette erreur s'appelle la perte hinge, ou « hinge loss » en anglais. « Hinge » signifie « charnière » en anglais, et correspond à la forme « en coude » de la perte hinge.

Perte hinge.

La perte hinge peut s'écrire de manière analytique de la fonction suivante :

  $\(l_{hinge}(y,f(y)) = max(0, 1-yf(x))\)$  

SVM à marge souple

Nous pouvons maintenant formuler notre problème d'optimisation :

$\[\arg\min_{w \in \mathbb{R}^p, b \in \mathbb{R}} \frac{1}{2}||w||_2^2 + C \sum_{i=1}^n l_{\mbox{hinge}}(y^{(i)}, (\langle w, x^{(i)} \rangle + b).\]$

Malheureusement cette nouvelle fonction objective ne peut pas être minimisée analytiquement. Nous allons donc introduire n variables d'ajustement $\(\xi_i,\)$ appelées slack variables en anglais, qui vont mesurer la distance entre $\(y^{(i)} f(x^{(i)})\)$ et 1. Pour chaque point du jeu de données, la perte hinge vaut donc $\(\xi_i\)$ et l'on souhaite

- soit que $\(x^{(i)}\)$ soit correctement classifié : $\(\xi_i = 0\)$ et $\(y^{(i)} f(x^{(i)}) \geq 1\)$ ;

- soit que $\(\xi_i \gt 0\)$ et $\(y^{(i)} f(x^{(i)}) + \xi_i = 1\)$

On peut reformuler ces deux possibilités en deux contraintes :  $\(y^{(i)} f(x^{(i)}) + \xi_i \geq 1\)$ et $\(\xi_i \geq 0\)$

La variable d'ajustement \xi_i est la distance entre yf(x) et sa valeur souhaitée de 1.

La variable d'ajustement $\(\xi_i\)$ est la distance entre $\(yf(x)\)$ et sa valeur souhaitée de 1.

Nous aboutissons donc à la formulation suivante : $\(\arg\min{w \in \mathbb{R}^p, b \in \mathbb{R}, \xi \in \mathbb{R}^n} \frac{1}{2}||w||_2^2 + C \sum_{i=1}^n \xi_i\)$

avec pour tout $\(i \in \{1, \dots, n\}, y^{(i)} f(x^{(i)}) \geq 1 - \xi_i\)$  et $\(\xi_i \geq 0\)$

C'est la forme primale de ce qu'on appelle le SVM à marge souple, ou soft-margin SVM en anglais.

Formulation duale

Avec les mêmes outils d'optimisation sous contrainte que pour le cas linéairement séparable, nous pouvons dériver la formulation duale du SVM à marge souple et les conditions KKT correspondantes.

Nous introduisons ainsi deux multiplicateurs de Lagrange par observation : $\(\alpha_i\)$ pour la première contrainte, et $\(\beta_i\)$ pour la deuxième. Le primal devient équivalent à

$\[\arg\max_{\alpha, \beta \in \mathbb{R}^n} \min_{w \in \mathbb{R}^p, b \in \mathbb{R}, \xi \in \mathbb{R}^n} L_p(w, b) \mbox{ avec } \alpha_i, \beta_i \geq 0 \, \, \forall i \in \{1, \dots, n\}.\]$

Le lagrangien vaut ici

 Les conditions de Karush-Kuhn-Tucker sont les suivantes :

- soit $\( \alpha_i = 0\)$ et $\( y^{(i)} (\langle w, x^{(i)} \rangle + b) - 1 + \xi_i > 0\)$

- soit $\(\alpha_i \gt 0\)$ et  $\(y^{(i)} (\langle w, x^{(i)} \rangle + b) - 1 + \xi_i = 0\)$

- soit $\(\beta_i = 0\)$ et $\(\xi_i \gt 0\)$

- soit $\(\beta_i \gt 0\)$ et $\(\xi_i = 0\)$

La minimisation du lagrangien se fait en minimisant son gradient :

- en w, ce qui donne comme précédemment $\(w = \sum_{i=1}^n \alpha_i y^{(i)} x^{(i)}\)$ ;

- en b, ce qui donne comme précédemment $\(\sum_{i=1}^n \alpha_i y^{(i)} = 0\)$ ;

 - en $\(\xi\)$ , ce qui donne $\(\beta_i = C - \alpha_i\)$

Cette dernière équation nous permet de lier $\(\beta\)$ à $\(\alpha\)$ , et le problème de maximisation en $\(\alpha\)$ et $\(\beta\)$ devient un problème de maximisation en $\(\alpha\)$ seulement. De plus, la contrainte $\(\beta_i \geq 0\)$ nous donne $\(\alpha_i \leq C\)$

La forme duale du SVM à marge souple est donc :

$\[\arg\max_{\alpha \in \mathbb{R}^n} -\frac{1}{2} \sum_{i=1}^n \sum_{l=1}^n \alpha_i \alpha_l y^{(i)} y^{(l)} \langle x^{(i)}, x^{(l)} \rangle + \sum_{i=1}^n \alpha_i\]$

 avec  $\(0 \leq \alpha_i \leq C \, \, \forall i \in \{1, \dots, n\}\)$   et  $\(\sum_{i=1}^n \alpha_i y^{(i)} = 0.\)$ 

La seule différence avec le cas linéairement séparable est la contrainte $\(\alpha_i \leq C\)$ !

Interprétation géométrique

Revenons aux conditions de KKT. Les deux dernières d'entre elles peuvent se réécrire

-  $\(\alpha_i = C\)$ et $\(\xi_i \gt 0\)$

 - $\(\alpha_i \lt C\)$ et $\(\xi_i = 0\)$

En prenant toutes les conditions de KKT en considération, on arrive donc à 3 cas possibles pour $\(\alpha_i\)$ :

 - $\(\alpha_i = 0\)$ . Dans ce cas, $\(xi_i = 0\)$ (car $\(\beta_i = C \gt 0\)$ ) et $\(y^{(i)} (\langle w, x^{(i)} \rangle + b) - 1 \gt 0\)$ Comme précédemment pour le cas linéairement séparable, $\(x^{(i)}\)$ est à l'extérieur de la zone d'indécision  (frontière exclue) ;

 - $\(0 \lt \alpha_i \lt C\)$ . Dans ce cas, $\(\xi_i = 0\)$ (le point est correctement classifié) et $\(y^{(i)} (\langle w, x^{(i)} \rangle + b) - 1 = 0\)$ . $\(x^{(i)}\)$ est donc un vecteur de support ;

- $\(\alpha_i = C\)$ , auquel cas $\(\xi_i \gt 0\)$ et $\(x^{(i)}\)$ est du mauvais côté  de la frontière de la zone d'indécision.

Les points qui vérifient alpha=C sont ceux pour lesquels on a fait une erreur.

Les points qui vérifient $\(\alpha=C\)$ sont ceux pour lesquels on a fait une erreur.

La SVM, aussi appelée SVC pour « Support Vector Classification », est implémentée dans scikit-learn : sklearn.svm.LinearSVC.

Et la régression dans tout ça ?

Les SVM peuvent aussi être utilisées pour des problèmes de régression. On cherche toujours à minimiser $\(||w||_2^2\)$ , mais les contraintes sont maintenant données par une fonction de perte différente : étant donné un hyperparamètre $\(\epsilon \in \mathbb{R}_+\)$ , nous souhaitons que la différence entre l'étiquette $\(y^{(i)}\)$ et sa valeur prédite $\(\langle w x(i) \rangle + b\)$ soit, en valeur absolue, inférieure à $\(\epsilon\)$ . Nous séparons cette condition en deux :

Si la différence est positive, nous souhaitons que $\(y^{(i)} - \langle w, x^{(i)} \rangle - b \leq \epsilon\)$ . Si elle est négative, cette condition sera naturellement vérifiée puisque $\(\epsilon \gt 0\)$ .

Si la différence est négative, nous souhaitons que $\(\langle w, x^{(i)} \rangle + b - y^{(i)} \leq \epsilon\)$ . 

Comme cela ne pourra pas toujours être le cas, nous introduisons deux variables d'ajustement par observation dans nos données : $\(xi_i\)$ pour ajuster la première condition, et $\(xi_i^*\)$ pour ajuster la deuxième. Le primal s'écrit donc :

$\[\arg \min_{w \in \mathbb{R}^p, b \in \mathbb{R}, \xi \in \mathbb{R}_+^n, \xi^* \in \mathbb{R}_+^n} \frac{1}{2} ||w||_2^2 + C \sum_{i=1}^n (\xi_i + \xi_i^*)\]$

 sous les conditions que  $\(y^{(i)} - \langle w, x^{(i)} \rangle - b \leq \epsilon + \xi_i\)$ et $\(\langle w, x^{(i)} \rangle + b - y^{(i)} \leq \epsilon + \xi_i^*.\)$ 

Le dual s'écrit

$\[\arg \min_{\alpha \in \mathbb{R}^n, \alpha^* \in \mathbb{R}^n} -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n (\alpha_i-\alpha_i^*) (\alpha_j - \alpha_j^*) \langle x^{(i)}, x^{(j)} \rangle - \sum_{i=1}^n y^{(i)} (\alpha_i-\alpha_i^*) + \epsilon \sum_{i=1}^n (\alpha_i + \alpha_i^*)\]$

 avec $\(\alpha_i, \alpha^*_i \geq 0 \,\, \forall i \in \{1, \dots, n\}\)$ et $\(\sum_{i=1}^n (\alpha_i - \alpha^*_i) = 0.\)$ 

La régression SVM, aussi appelée SVR pour Support Vector Regression, est implémentée dans scikit-learn : sklearn.svm.LinearSVR. Encore une fois, une implémentation duale et une implémentation primale sont disponibles via l'option 'dual' et il vaut généralement mieux choisir 'dual=False' quand on a beaucoup de données et 'dual=True' quand on a beaucoup de variables.

Conclusion

  • Les SVM (Support Vector Machines), aussi appelées en français Machines à Vecteurs de Support et parfois Séparatrices à Vaste Marge, cherchent à séparer linéairement les données.

  • La version primale résout un problème d'optimisation à p variables et est donc préférable si on a moins de variables que d'échantillons.

  • À l'inverse, la version duale résout un problème d'optimisation à n variables et est donc préférable si on a moins d'échantillons que de variables.

  • Les vecteurs de support sont les points du jeu de données qui sont les plus proches de l'hyperplan séparateur.

  • La fonction de décision peut s'exprimer uniquement en fonction du produit scalaire du point à étiqueter avec les vecteurs de support.

Exemple de certificat de réussite
Exemple de certificat de réussite