Bienvenue dans la première partie de cette mini-série dédiée aux SVM.
Quand on pense Machine Learning, on pense généralement à des méthodes récentes, encore mal comprises, et utilisées empiriquement, à la manière d’un apprenti sorcier.
En effet, que ce soit les algorithmes génétiques, les réseaux de neurones, le Boosting… on qualifie souvent ces algorithmes de « boîtes noires ». Autrement dit, même s’il est facile de commenter l’entrée et la sortie de l’algorithme indépendamment, lorsqu’il s’agit de détailler la contribution exacte de chaque entrée au résultat final, c’est une autre paire de manches. La faute à un trop grand nombre de paramètres, à l’utilisation d’événements aléatoires…
Néanmoins, parmi cette myriade d’algorithmes tous plus complexes les uns que les autres, s’en trouve un, dont l’âge avancé dénote avec son efficacité et sa simplicité.
Conceptualisé par Vladimir Vapnik dès le début des années 60, il fait son entrée dans le milieu de l’informatique en 1990. Dès lors, il devient une référence pour tous ceux qui s’intéressent de près ou de loin aux techniques d’apprentissage supervisé. Encore aujourd’hui, il continue d’être enseigné, étudié et massivement utilisé. Vous l’aurez compris, nous allons parler ici des Machines à Vecteurs de Support, aussi appelé SVM pour Support Vector Machine.
Warning : Parler de la simplicité d’un tel algorithme revient à parler de la petitesse de la Lune. On sait qu’elle est petite à côté de ce qui l’entoure, mais on pourrait quand même pas en faire le tour à pied.
Cet article sera divisé en 2 parties. Dans celle-ci, nous allons vous présenter le principe de base des Margin Classifiers, et les limites de ces derniers.
Dans la seconde, nous rentrerons davantage dans le détail des SVM, l’objectif étant de donner une vue d’ensemble sur leur fonctionnement
Maximal Margin Classifiers
Comme souvent en Sciences, avant de s’attaquer au problème en tant que tel, on préfère étudier un cas particulier, plus simple à résoudre. Nous allons donc commencer cette présentation par l’étude d’un cousin des SVM, les Classifieurs à Marge Maximal.
Supposons que nous ayons un jeu de données contenant 2 types d’observations : les « + » et les « -« . Notre objectif est de pouvoir prédire la classe (« + » ou « -« ) d’une nouvelle observation, ici représentée par un « x ».
Instinctivement, on comprend bien que l’observation devrait être classée parmi les « – » ici. Mais il est difficile d’expliquer les raisons qui nous permettent d’affirmer cela.
La méthode que l’on va appliquer est la suivante :
Tracer une droite séparant les 2 classes. Si l’observation se trouve au-dessus de cette droite, on dira qu’il s’agit d’un « + », sinon d’un « -« . Ici par exemple, l’observation « x » se trouve en dessus de la droite, il s’agit donc d’un « -« .
La méthode semble fonctionner correctement. Cependant, dans le cas particulier de notre problème, il existe une infinité de droites séparant parfaitement les 2 ensembles. Chacune d’elle délimite des espaces différents et constitue une réponse différente au problème. La question est alors de savoir comment choisir la meilleure droite parmi toutes les droites possibles.
Sur la figure précédente, il semble logique de dire que la droite centrale sépare mieux les données que les 2 autres. En effet, comme elle est éloignée à la fois des « + » et des « -« , elle ne risque pas de classer une observation dans une classe alors qu’elle se trouve en réalité très proche de l’autre classe.
En mathématiques, la distance qui sépare une droite de l’observation la plus proche est appelée la marge. La droite centrale a une marge plus importante que les deux autres.
Autrement dit, la droite qui sépare le mieux les 2 classes est celle dont la marge est la plus élevée. Vous comprenez désormais d’où vient le terme de « Maximal Margin Classifiers » ?
Dans le cas de notre exemple, la droite continue est la meilleure droite de séparation. La marge, qui est représentée en pointillé, est maximale. Vous aurez remarqué que la même distance sépare la droite des 3 observations les plus proches. C’est une caractéristique que l’on retrouve systématiquement pour la meilleure droite.
Il existe une méthode permettant de la calculer à tous les coups, l’algorithme Maximal Margin Classifier utilise cette méthode pour
Ce qu’il faut retenir de cette introduction, c’est qu’il suffit de trouver la droite avec la marge la plus grande pour pouvoir classer toutes les nouvelles observations.
De plus, lorsqu’elle existe, il est relativement simple de calculer l’équation de la droite de séparation (si le détail des calculs vous intéresse, je vous recommande la vidéo de MIT OpenCourseWare qui traite précisément de ce sujet .
On tient alors une méthode simple et rapide pour répondre au problème posé.
Cependant, la méthode que nous venons de voir a deux gros défauts. En effet, elle est très sensible aux valeurs extrêmes (aussi appelées outliers).
L’arrivée d’un outlier (le « – » le plus haut) perturbe complètement le résultat.
Pire encore, au cas où vous vous seriez posé la question : Non, il n’existe pas toujours de droite séparant parfaitement les 2 classes. C’est par exemple le cas dans l’image qui suit :
Nous nous retrouvons finalement avec un algorithme qui, dans certains cas, ne fonctionne pas du tout.
Dans le prochain article dédié aux SVM, nous verrons comment donner davantage de flexibilité à notre algorithme, en l’autorisant à commettre quelques erreurs de classification, pour améliorer ses performances globales.
Les techniques de Machine Learning vous intéressent ? Vous souhaitez apprendre à les maîtriser ? Nos formations en data science sont faites pour ça !
