# Que sont les machines à vecteurs de support, et pourquoi ont-elles tant compté?

Date: 2020-07-14 · Author: Robert Scales · https://guidetoartificialintelligence.com/fr/apprendre/machines-a-vecteurs-de-support/

**Answer:** Une machine à vecteurs de support classe des exemples en deux groupes en trouvant la frontière qui laisse l’écart le plus large possible entre eux, une frontière définie par seulement quelques exemples clés appelés vecteurs de support. L’article de 1995 de Corinna Cortes et Vladimir Vapnik, « Support-Vector Networks », a permis à cette frontière de tolérer quelques erreurs et de se courber selon des formes complexes, ce qui a donné un classificateur fiable, solidement fondé sur les mathématiques, devenu l’un des outils les plus utilisés en apprentissage automatique.

Imaginez une table couverte de billes rouges et bleues, surtout rouges d’un côté et bleues de l’autre, et une règle que vous devez poser pour les séparer. Bien des positions conviendraient. Une machine à vecteurs de support (*support vector machine*, ou SVM) choisit celle qui reste le plus loin possible des billes les plus proches des deux côtés, pour qu’une nouvelle bille qui tombe près de la ligne ait encore de bonnes chances d’être bien classée.

Cette image simple se trouve derrière l’une des méthodes les plus influentes de l’apprentissage automatique. Sa forme la plus connue a été publiée en 1995 par Corinna Cortes et Vladimir Vapnik, des AT&T Bell Laboratories à Holmdel, au New Jersey, dans un article intitulé « Support-Vector Networks » paru dans la revue *Machine Learning*. La revue l’avait reçu en mai 1993.

## D’où vient l’idée?

Vapnik travaillait sur la théorie de l’apprentissage depuis les années 1960. Avec Alexeï Tchervonenkis, il a élaboré ce qu’on appelle aujourd’hui la théorie VC, qui pose une question pratique : quand un modèle s’ajuste à ses exemples d’entraînement, à quel point peut-on être sûr qu’il fonctionnera sur de nouveaux exemples? Une des réponses est l’« hyperplan optimal », la frontière plane qui laisse la plus large marge entre deux classes. Un hyperplan, c’est simplement une ligne en deux dimensions, une feuille plane en trois, et la même idée en plus de dimensions.

Deux morceaux manquaient encore au début des années 1990. D’abord, les données réelles ne peuvent souvent pas être séparées du tout par une ligne droite. En 1992, Bernhard Boser, Isabelle Guyon et Vapnik ont montré un raccourci, appelé aujourd’hui l’astuce du noyau (*kernel trick*), pour obtenir des frontières courbes à peu de frais. Ensuite, les données réelles sont bruitées : quelques billes se trouvent toujours du mauvais côté. L’article de 1995 a réglé ce problème.

## Comment fonctionne une machine à vecteurs de support?

La méthode de l’article repose sur trois idées.

**La marge la plus large.** Parmi toutes les frontières qui séparent les classes, on choisit celle qui laisse le plus grand écart avec les exemples les plus proches. Ces exemples les plus proches sont les vecteurs de support. Eux seuls décident de l’emplacement de la frontière; le reste des données pourrait bouger sans que la frontière change. L’article relie une faible proportion de vecteurs de support à une bonne performance sur de nouvelles données.

**La marge souple.** L’apport de Cortes et Vapnik a été de permettre à la machine d’accepter quelques erreurs d’entraînement quand une séparation parfaite est impossible. Un réglage contrôle le compromis entre une marge large et peu d’erreurs. Cette version à « marge souple » est celle qu’utilisent encore aujourd’hui les logiciels.

**Les noyaux.** Pour tracer des frontières courbes, on peut imaginer soulever les données dans un espace qui compte beaucoup plus de dimensions, où une frontière plane fait l’affaire. Calculer directement dans cet espace serait sans espoir; l’article note que cela pourrait vouloir dire un milliard de dimensions. L’astuce du noyau l’évite en comparant des paires d’exemples dans l’espace d’origine et en transformant le résultat, ce qui donne la même réponse que si l’on travaillait dans l’immense espace.

Voici l’image des billes sous forme d’exemple concret :

| Situation | Ce que fait la machine |
|---|---|
| Les rouges et les bleues se séparent nettement | Place la frontière au milieu de l’écart le plus large |
| Quelques billes se trouvent du mauvais côté | Accepte ces erreurs (marge souple) plutôt que de tordre la frontière |
| Les billes rouges forment un anneau autour d’un groupe de bleues | Utilise un noyau, qui agit comme une frontière courbe tracée autour du groupe de bleues |
| Une nouvelle bille arrive | Vérifie de quel côté de la frontière elle tombe |

> **À essayer :** éparpillez dix pièces de monnaie et dix boutons sur une table, de sorte que les groupes se chevauchent un peu. Posez un crayon pour les séparer, puis faites-le glisser et pivoter pour rendre l’écart avec la pièce la plus proche et le bouton le plus proche aussi large que possible. Comptez combien d’objets touchent réellement les bords de votre écart : ce sont vos vecteurs de support.

## Les tests sur les chiffres

L’article a testé la méthode sur des chiffres manuscrits, un problème brûlant aux Bell Labs. Avec un ensemble du service postal des États-Unis comptant 7 300 chiffres d’entraînement et 2 000 chiffres de test, des machines à vecteurs de support utilisant des noyaux polynomiaux faisaient environ 4,2 à 4,7 % d’erreurs. C’était mieux que LeNet1, un réseau de neurones conçu spécialement pour cette tâche, à 5,1 %, alors que la performance humaine sur cet ensemble était de 2,5 %. Sur un banc d’essai plus grand de 60 000 chiffres d’entraînement tirés de données du NIST, un seul type de machine à vecteurs de support a atteint 1,1 % d’erreurs, sans aucune conception particulière pour les images.

Dix classificateurs ont été entraînés pour les dix chiffres, chacun séparant un chiffre de tous les autres; le score le plus élevé l’emportait.

## Pourquoi ont-elles compté?

Les machines à vecteurs de support sont arrivées avec trois forces qui manquaient aux réseaux de neurones des années 1990. Elles s’accompagnaient d’une théorie qui expliquait pourquoi elles devaient fonctionner sur de nouvelles données. Leur entraînement est un problème convexe : il n’y a qu’une seule meilleure réponse, sans risque de rester coincé dans une mauvaise. Et elles fonctionnaient bien avec des quantités de données modestes et peu de réglages.

Elles sont vite devenues un choix standard pour la classification : classer des textes par catégorie, reconnaître des images et de l’écriture manuscrite, et classer des protéines en biologie. Bien des équipes se tournaient vers une SVM avant d’essayer quoi que ce soit d’autre. Les réseaux de neurones profonds, nourris de jeux de données beaucoup plus grands et de matériel plus rapide, les ont depuis dépassées pour les images, la parole et le langage.

## Les machines à vecteurs de support valent-elles encore la peine d’être apprises maintenant que l’apprentissage profond domine?

Oui, pour deux raisons. D’abord, elles restent pratiques. Pour des jeux de données petits ou moyens, surtout avec des caractéristiques numériques claires, une SVM s’entraîne souvent en quelques secondes, demande peu de réglages et fait aussi bien que des modèles beaucoup plus gros. Les bibliothèques courantes d’apprentissage automatique en proposent, et elles constituent une solide base de comparaison avant d’essayer un réseau de neurones.

Ensuite, les idées voyagent. La marge est une façon nette de réfléchir à la raison pour laquelle un modèle généralise. Les noyaux vous apprennent à penser les données en matière de similarité entre exemples, une idée qu’on retrouve dans bien d’autres méthodes. Et l’idée des vecteurs de support, selon laquelle quelques exemples critiques définissent la décision, est une lentille utile pour comprendre n’importe quel classificateur.

Si vous débutez, essayez d’abord une SVM sur un petit jeu de données. Voir un modèle simple et bien compris faire étonnamment bien est une bonne façon de comprendre ce qu’ajoutent les modèles plus grands.

## Sources

- Support-Vector Networks: https://doi.org/10.1007/BF00994018
- Support vector machine: https://en.wikipedia.org/wiki/Support_vector_machine