Machines à vecteurs de support : marges et noyaux

La plupart des classifieurs s’ajustent en écrivant une perte puis en la minimisant. Les machines à vecteurs de support partent d’un point plus géométrique : parmi toutes les frontières qui séparent deux classes, préférer celle qui est la plus éloignée de chaque observation. Suivre honnêtement cette idée mène à un classifieur qui ignore l’essentiel de ses propres données d’entraînement, puis à une technique pour courber la frontière sans payer l’espace dans lequel elle se courbe.

A. La bande la plus large

En dimension $p$, un hyperplan est l’ensemble où $\beta_0 + \beta_1 x_1 + \cdots + \beta_p x_p = 0$. Il coupe l’espace en deux : en notant $f(x)$ ce membre de gauche, on obtient donc un classifieur - prédire $+1$ quand $f(x) > 0$ et $-1$ sinon. Avec des étiquettes codées $\pm 1$, une observation est correctement classée exactement quand $y_i f(x_i) > 0$.

Si les classes se séparent, elles se séparent généralement d’une infinité de façons ; la question est donc de savoir quel hyperplan retenir. Le classifieur à marge maximale calcule la distance de chaque observation à un hyperplan candidat, appelle marge la plus petite d’entre elles, et choisit l’hyperplan dont la marge est la plus grande. C’est la ligne médiane de la bande la plus large qui tienne entre les classes.

Six points rendent cela concret. La classe $+1$ en $(3,3)$, $(4,4)$, $(3,5)$ et la classe $-1$ en $(1,1)$, $(0,2)$, $(2,0)$. La réponse est $x_1 + x_2 - 4 = 0$, avec des distances $|x_1 + x_2 - 4|/\sqrt{2}$ :

$$\begin{array}{lll} (3,3),\ (1,1),\ (0,2),\ (2,0) & \sqrt{2} \approx 1.414 & \text{support vectors} \\ (4,4),\ (3,5) & 2\sqrt{2} \approx 2.828 & \text{irrelevant} \end{array}$$

Quatre observations touchent le bord de la bande et la maintiennent en place : ce sont les vecteurs de support. Les deux autres peuvent être déplacées n’importe où de leur côté de la bande, tant qu’elles restent hors de celle-ci ($x_1 + x_2 \ge 6$), sans rien changer au classifieur ajusté. Faites-en entrer une dans la bande et celle-ci se rétrécit. Notez que les vecteurs de support ne se répartissent pas également entre les classes.

L’optimisation s’énonce comme la maximisation de $M$ sous les contraintes $\sum_j \beta_j^2 = 1$ et $y_i(\beta_0 + \beta\cdot x_i) \ge M$ pour tout $i$. Cette normalisation a l’air d’une écriture de comptable, mais elle est essentielle : multiplier tous les coefficients par un $k \neq 0$ quelconque décrit le même hyperplan, si bien que sans convention d’échelle les paramètres sont indéterminés. Fixer la norme à un fait en outre de la quantité contrainte la véritable distance perpendiculaire.

B. Pourquoi la perfection est le mauvais objectif

Le classifieur à marge maximale échoue de deux façons. Il n’a aucune solution quand les classes ne sont pas séparables, ce qui est fréquent. Et quand il fonctionne, il est entièrement déterminé par les points les plus proches de la frontière : il hérite donc de leur instabilité. Ajoutez aux six ci-dessus une seule observation $+1$ en $(1.6, 1.6)$ et la meilleure marge atteignable tombe de $1.414$ à $0.424$. Un point, un facteur de plus de trois. Puisqu’une marge étroite est précisément ce qui généralise mal, exiger une séparation parfaite se retourne contre soi.

Le classifieur à vecteurs de support autorise les violations et les facture. Chaque observation reçoit une variable d’écart $\varepsilon_i \ge 0$, la contrainte devient $y_i(\beta_0 + \beta \cdot x_i) \ge M(1 - \varepsilon_i)$, et le total est plafonné par $\sum_i \varepsilon_i \le C$. L’écart dit la gravité de l’inconduite d’un point : zéro pour le bon côté de la marge, jusqu’à un pour l’intérieur de la marge mais encore correctement classé, et au-delà de un pour le mauvais côté de l’hyperplan lui-même.

$C$ est un budget de violation. À $C = 0$, plus rien n’est abordable et le problème redevient le classifieur à marge maximale. Quand $C$ grandit, la marge s’élargit et davantage de points s’y installent. Comme chaque erreur de classement coûte plus d’une unité, $C$ plafonne aussi le nombre d’erreurs d’entraînement. Il n’est pas estimé par le solveur : c’est un hyperparamètre réglé par validation croisée.

Le problème à marge souple possède une propriété qu’il vaut la peine d’isoler : une observation strictement du bon côté de la marge n’a aucun effet sur le classifieur. Déplacez-la, rien ne change. Seuls les points situés sur la marge ou qui la violent - les vecteurs de support - entrent dans la solution avec des coefficients non nuls. C’est le sens précis dans lequel la méthode est robuste aux points lointains, et ce qui la distingue de l’analyse discriminante linéaire, qui utilise chaque observation à travers les moyennes de classe et la covariance.

$C$ est donc le cadran biais-variance sous un autre costume. Un $C$ petit donne une marge étroite soutenue par peu de points : biais faible, variance élevée. Un $C$ grand donne une marge large reposant sur beaucoup : plus de biais, moins de variance.

C. Courber la frontière gratuitement

Certaines données ne sont séparées par rien de plat - une classe en anneau autour d’une autre, par exemple. Le remède standard consiste à élargir l’espace des variables : ajustez une frontière linéaire dans $x_1, x_2, x_1^2, x_2^2, x_1x_2$ et elle redescend dans le plan sous la forme d’une conique. L’obstacle est le coût. Les monômes de degré au plus 2 sur $p$ prédicteurs, constante incluse, sont au nombre de $(p+1)(p+2)/2$ :

$$\begin{array}{ll} p = 2 & 6 \\ p = 10 & 66 \\ p = 100 & 5{,}151 \\ p = 1{,}000 & 501{,}501 \end{array}$$

Ce qui sauve la situation, c’est que la solution peut s’écrire $f(x) = \beta_0 + \sum_i \alpha_i \langle x, x_i\rangle$, et qu’ajuster les $\alpha_i$ ne demande que les produits scalaires entre paires d’observations d’entraînement. Aucune des deux étapes ne touche jamais aux coordonnées. Remplacez donc chaque produit scalaire par un noyau $K(x_i, x_{i'})$, une fonction de similarité, et l’algorithme fonctionne encore - désormais implicitement dans l’espace auquel ce noyau correspond. Comme $\alpha_i$ s’annule hors des vecteurs de support, la somme est en prime courte.

Le noyau polynomial $K(x_i,x_{i'}) = (1 + \sum_j x_{ij}x_{i'j})^d$ change le classifieur à vecteurs de support en machine à vecteurs de support. Ce n’est pas un tour de passe-passe, et cela vaut la peine d’être vérifié une fois. Pour $p = 2$, $d = 2$ :

$$(1 + x_1z_1 + x_2z_2)^2 = \langle \varphi(x), \varphi(z)\rangle, \qquad \varphi(x) = \big(1, \sqrt{2}x_1, \sqrt{2}x_2, x_1^2, x_2^2, \sqrt{2}x_1x_2\big) .$$

Le noyau renvoie un produit scalaire à six dimensions à partir de deux dimensions d’entrée. À $p = 1{,}000$, l’application explicite réclame un demi-million de coordonnées quand le noyau coûte encore mille multiplications.

L’autre choix courant est le noyau radial $\exp(-\gamma \sum_j (x_{ij} - x_{i'j})^2)$, qui ne dépend que de la distance et décroît exponentiellement en son carré. Avec $\gamma = 1$, une distance au carré de $2$ donne $0.135$ et une distance au carré de $8$ donne $0.000335$. Il est local : une prédiction est gouvernée par les points d’entraînement proches, les points lointains entrant avec des poids indiscernables de zéro. Cette localité est la source de sa souplesse, et elle correspond à un espace de variables de dimension infinie que vous ne pourriez écrire à aucun prix - ce qui est le meilleur argument en faveur d’un travail par noyaux plutôt que par coordonnées.

Vérifiez-le vous-même ci-dessous plutôt que sur trois paires figées. Déplacez le second point où vous voulez : le noyau, calculé à partir de deux coordonnées, et le produit scalaire des deux images à six dimensions restent le même nombre, et les six coordonnées que le membre de droite a dû construire sont imprimées en dessous. Passez ensuite au noyau radial et écartez les points : deux unités suffisent déjà pour qu’une observation d’entraînement n’apporte plus rien.

Où cela vous laisse

Une marge est une raison défendable de préférer une frontière à une autre, et les vecteurs de support sont les seules données qui comptent pour elle. Exiger une séparation parfaite est fragile, un budget de violations rachète donc de la stabilité, et ce budget est le familier cadran biais-variance. Les noyaux courbent ensuite la frontière en changeant ce que « similarité » veut dire, plutôt qu’en construisant un espace plus grand. Le parcours de formation Machines à vecteurs de support travaille chacun de ces points à la main et en code.