Vous savez tous que les algorithmes de machine learning sont classés en deux catégories : apprentissage non-supervisé et apprentissage supervisé. Aujourd’hui, nous allons nous focaliser sur ce deuxième mode, et plus précisément sur les machines à vecteurs de support ou SVM (pour Support Vector Machines en anglais).
En français on parle de séparateurs à vastes marges, pour garder l’acronyme.
Pour tous ceux qui ne connaissent pas les problèmes de classification et séparation, je vous conseille la lecture de cet article avant de continuer la lecture.
Les Support Vectors Machines dans la théorie
Les SVM sont des classificateurs qui permettent de traiter des problèmes non linéaires en les reformulant en problèmes d’optimisation quadratique. Qui sont beaucoup plus faciles à résoudre.
Ces méthodes reposent sur deux idées clés : la notion de marge maximale et la notion de fonction noyau.
Sans trop rentrer dans les détails théoriques, la marge maximale est la frontière de séparation des données qui maximise la distance entre la frontière de séparation et les données les plus proches (i.e. qui maximise la marge).
En quelques mots également, une fonction noyau est une sorte d’alternative à un produit scalaire (qui est coûteux) dans un espace à très grande dimension.
À tout couple d’éléments, un noyau associe une mesure de leur »influence réciproque ». Elle est calculée à travers leur distance ou leur corrélation. Ces dernières lignes semblent compliquer à comprendre, mais nous en verrons l’utilité dans les prochaines paragraphes.
Concrètement, qu’est ce qu’un SVM ?
Et sinon, concrètement, c’est quoi les SVM ?
Pour rester synthétique, les SVM sont un ensemble de techniques d’apprentissage supervisé qui ont pour objectif de trouver, dans un espace de dimension N>1, l’hyperplan qui divise au mieux un jeu de donnée en deux. Les SVM sont des séparateurs linéaires, c’est-à-dire que la frontière séparant les classes est une droite.
Nous avons ci-dessus un exemple d’hyperplan séparateur pour N=2. H1 ne sépare pas correctement le jeu de donnée; H2 le sépare bien mais pas de façon optimale; H3 sépare le jeu de donnée avec la marge maximale.
Comment fonctionne un SVM ?
Afin de trouver cette fameuse frontière séparatrice, il faut donner au SVM des données d’entrainement. On donne à l’algorithme un jeu de données dont on connait déjà les deux classes.
On entre alors dans la phase d’entrainement. Le SVM va déterminer la frontière la plus plausible. Mais comment choisir la frontière alors qu’il y en a une infinité ?
C’est là qu’intervient la première idée clé : la marge maximale.
La frontière choisie doit maximiser sa distance avec les points les plus proches de la frontière. Les points d’entraînement les plus proches de la frontière sont d’ailleurs appelés vecteurs support. Ils sont appelés comme cela car la frontière donnée par un SVM ne dépend que des vecteurs support (on peut le prouver mathématiquement). Ils sont donc le support que le SVM utilise pour construire la frontière. On comprend mieux d’où vient le nom Support Vector Machines maintenant…
Après la phase d’entrainement, le SVM a « appris » (une IA apprend elle vraiment ? petite digression sur ce que l’IA n’est pas[https://larevueia.fr/ce-que-lia-nest-pas/]) où est l’emplacement de la frontière à partir des données d’entrainement. Ainsi, après plusieurs phases d’entrainement, le SVM sait où placer la frontière pour de nouvelles données.
Dans le cas de la figure ci-dessus, la tâche est relativement facile puisque le problème est linéairement séparable, c’est-à-dire que l’on peut trouver une droite linéaire séparant les données en deux.
Ces problèmes là étant très simples et peu rencontrés en pratique, l’intérêt s’en trouve limité. Dans la majorité des cas, les données sont « mélangés » et le problème non linéairement séparable. Il n’est alors pas possible de les séparer seulement avec une droite. Mais on avait dit que les Support vector machines sont des séparateurs linéaire, ils ne fonctionnent donc que dans les cas simples ? Un peu de patience, nous y venons…
Comment les SVM interviennent dans les non linéairement séparable
La quasi totalité des cas que nous rencontrons en pratique sont non-linéairement séparable. Et c’est la qu’entre en jeu la fonction noyau dont nous avons parlé quelque paragraphes plus haut.
Afin de contourner le problème non linéairement séparable, on plonge dans un espace de dimension supérieur (éventuellement infini) et on reconsidère le problème dans cet espace là.
Cette manœuvre permet de passer d’un problème non linéairement séparable à un problème linéairement séparable. La fonction noyau joue un rôle primordiale. En effet, en passant d’un espace de dimension inférieur à un espace de dimension supérieur, les calculs deviennent également plus complexes et plus coûteux.
La fonction noyau permet alors d’effectuer les calculs dans l’espace d’origine en lieu et place de l’espace de dimension supérieur. Le gain en coût et en facilité est colossal. Cette méthode est appelé kernel trick (astuce du noyau en français).
La méthode ne porte par ce nom par hasard. Nous avons besoin de très peu d’informations concernant l’espace de dimension supérieur pour arriver à nos fins. Cependant, cette méthode n’est pas garanti de marcher. En effet, rien ne prouve qu’il est possible de trouver un espace de dimension supérieure où le problème devient linéairement séparable. C’est au cas par cas…
Et si on a plus de deux classes ?
Tous les problèmes que nous avons vu plus haut considéraient seulement deux ensembles distincts à séparer. C’est normal : les Support Vector Machines ont initialement été construit pour séparer seulement deux catégories.
En reprenant la définition des SVM, on rencontre un cul-de-sac : un hyperplan qui sépare l’espace en trois ou plus ça n’existe pas…
Fort heureusement, des chercheurs se sont penchés sur la question et on trouver des solutions. Je vais vous présenter l’une d’entre elles : one vs all.
Cette approche consister à créer autant de SVM que de catégories présentes. Prenons un exemple. Supposons que nous avons des pions rouges, des pions bleues et des pions verts. On souhaite séparer les pions en fonction de leurs couleurs.
Avec l’approche one vs all, on utilise un SVM pour trouver une frontière entre les groupes {pions rouges} et {pions bleues, pions verts}; puis un autre SVM pour trouver une frontière entre {pions bleus} et {pions rouges, pions verts}; et enfin une troisième SVM pour une frontière entre {pions verts} et {pions bleus, pions rouges}. On extrait alors une frontière (non linéaire) de ces trois frontières.
Le mot de la fin sur les support vector machines
Les SVM sont des outils parmi tant d’autres pour faire de la classification (et même de la régression, mais ce sera pour un prochain article…).
Ils sont particulièrement efficace lorsque le nombre de données d’entrainement est faible. Par conséquent, dans ce type de cas on les privilégiera aux réseau de neurones qu’on utilise classiquement. Ces derniers sont très performant mais ont besoin d’une très grande quantité de données d’entrainement.
Les SVM sont utilisés dans une très grande variétés de domaines, allant de la médecine, à la recherche d’information en passant par la finance…
Restez connecté, très bientôt nous vous présenterons un tutoriel pour vous familiarisez de manière pratique avec les SVM !
merci pour votre commision