Introduction aux SVM

Découvrez les SVM, ces outils classiques du Machine Learning !

a marqué ce sujet comme résolu.

Malheureusement, cet article qui était en bêta a été supprimé par son auteur.

Tout le monde se secoue ! :D

J’ai commencé (jeudi 23 juin 2016 à 23h12) la rédaction d’un article au doux nom de « Introduction aux SVM » et j’ai dans l’objectif de proposer en validation un texte aux petits oignons. Je fais donc appel à votre bonté sans limite pour dénicher le moindre pépin, que ce soit à propos du fond ou de la forme. Vous pourrez consulter la bêta à votre guise à l’adresse suivante :

Merci !


Au début, j’avais écrit un rapport sur les SVM pour le boulot, puis je me suis dit que ça ferait un chouette article pour ZdS. Je l’ai donc modifié un peu, et voilà. :)

Si un gentil valido passe par là, est-ce qu’il pourrait insérer le JSFiddle en dernière partie ? Merci !

Avec cet article, j’ai tenté une approche tout public, parce que à mon avis, comprendre le fonctionnement d’un SVM ne nécessite pas de grosses connaissances théoriques. On peut s’en faire une idée simple sans trop mettre les mains dans les maths. Mon problème, c’est que je ne sais pas trop à quel point c’est effectivement accessible à quelqu’un qui n’y connaît quasiment rien en maths. :/

Par ailleurs, j’ai été très rapide sur les SVM multiclasse, est-ce que vous pensez qu’il vaut mieux détailler ou non ?

+3 -0

C'est sympa comme article, j'ai lu rapidement et à 1h30 du matin, j'ai compris l'essentiel, donc ça va c'est bien expliqué :D . c'est relativement accessible, même pour quelqu'un qui connaitrait pas le sujet, je pense. Y'a encore deux/trois phrases un peu compliqués mais rien de bien méchant.

Je repasse dans la semaine pour une relecture.

Ps: juste par curiosité, c'est quoi ton travail ?

+0 -0

Bonjour les agrumes !

J'ai donc été le gentil modo en question. Par contre, je ne sais pas si c'est parce que c'est du hors ligne ou bien parce que la version actuelle du zmarkdown est buggée lorsqu'on n'a pas une url du style https://jsfiddle.com/{id_du_fiddle}/{incrément_version}/ mais pour l'instant ça n'apparait pas.

La bêta a été mise à jour et décante sa pulpe à l'adresse suivante :

Merci d'avance pour vos commentaires.

+2 -0

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l'adresse suivante :

Merci d'avance pour vos commentaires.


Merci à vous pour vos premiers retours, et merci au gentil artragis pour le JSFiddle (d'ailleurs, ça ne marchait effectivement pas parce qu'il manquait un /increment_version, j'en ai profité pour rajouter des crédits à l'intérieur du fiddle et maintenant ça marche).

J'ai changé le titre, je pense que c'est mieux comme ça. Je ne peux de toute façon pas expliquer plus clairement ce qu'est un SVM dans le titre, mais au moins je pense que machine learning, ça parle à tout le monde. J'ai aussi corrigé deux-trois coquilles que j'ai vues.

Hugo : Je suis preneur des phrases que tu trouves nébuleuses !
Pour répondre à ton PS, je fais mon stage de fin d'études dans un labo de recherche en informatique dans une boîte privée. Ce qui fait que des fois, je ne fais pas forcément ce qui m'intéresse, mais bon, c'est sympa quand même. :)

+1 -0

les algorithmes de machine learning, où l'ordinateur est capable d'effectuer un apprentissage à partir de données pré-traitées

C'est pas faux de mettre ça en opposition avec ce que tu appelles les algorithmes classiques ? C'est de l'apprentissage, mais encadré, y a rien de spontané qui se passe, si ?

Je pense que tu devrais considérer (donc indiquer) que les lecteurs connaissent déjà le principe du ML et de la classification. Là, l'introduction au sujet (introduction du tutoriel et première section) n'est à mon avis pas assez développée pour être utile aux personnes n'ayant pas connaissance du domaine.

En outre, il n'est pas très économe de définir le ML et la classification dans chaque tutoriel portant sur un algorithme de ce genre. Autant factoriser les explications dans un contenu, comme l'avait commencé Bermudes quelque part.

+0 -0

Hello,

Merci pour vos retours !

Je pense que tu devrais considérer (donc indiquer) que les lecteurs connaissent déjà le principe du ML et de la classification

Zut, c'est absolument pas ce que j'avais en tête. :/
En fait, pour répondre à spacefox, à mon avis c'est délicat de dire ce qu'est un svm sans parler de machine learning et de classification, et au début, ma première partie etait contenue dans l'introduction, puis je me suis dit que ça ferait une introduction super lourde.
Le problème, c'est que si je veux garder l'article accessible à tous, c'est pas facile de concilier les deux sans rester vague sur ce qu'est un svm au début.

Du coup, je vais re-réfléchir à tout ça cette semaine, et je vais retenter de faire une introduction tout public. Si ça foire aussi, je ferai un article qui ne sera pas tout public. :)

C'est pas faux de mettre ça en opposition avec ce que tu appelles les algorithmes classiques ? C'est de l'apprentissage, mais encadré, y a rien de spontané qui se passe, si ?

J'ai probablement été un peu flou, mais ce qui sépare un algo classique d'un algo de machine learning c'est que l'algo classique ne fait que appliquer des règles de décision écrites en dur dans leur code, tandis que l'algo de machine learning apprend ces règles de décision par lui même, sur des données données dans un format prétraité.

En outre, il n'est pas très économe de définir le ML et la classification dans chaque tutoriel portant sur un algorithme de ce genre. Autant factoriser les explications dans un contenu, comme l'avait commencé Bermudes quelque part.

Tiens, j'avais pas vu son projet de tuto. Ce serait effectivement cool de factoriser, mais je ne peux pas le faire si je persiste à vouloir rendre ça accessible sans prérequis (et je persiste :p ). Qui plus est, le tuto est encore en bêta, ce qui veut dire que le contenu n'est accessible qu'aux membres.

J'ai probablement été un peu flou, mais ce qui sépare un algo classique d'un algo de machine learning c'est que l'algo classique ne fait que appliquer des règles de décision écrites en dur dans leur code, tandis que l'algo de machine learning apprend ces règles de décision par lui même, sur des données données dans un format prétraité.

De ce que j'avais vu ce ne sont que des paramètres qui sont ajustés par apprentissage. Je vois pas bien la différence avec un programme classique où une variable évolue et influe sur le déroulement.

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l'adresse suivante :

Merci d'avance pour vos commentaires.


J'écris rarement, et j'écris lentement, donc ça a pris plus de temps que prévu. Quoi qu'il en soit, voici la nouvelle version. :)

Notamment, grâce à vos commentaires et après réflexion, je me suis aperçu que si je croyais que l'article serait accessible tous publics, je me mettais le doigt dans l'oeil jusqu'au coude. J'ai donc laissé tomber quelques-unes des explications qui ralentissaient le plus la lecture.
J'ai cependant laissé mon introduction aux problèmes de classification, tout en l'étoffant, j'espère qu'à présent elle est plus utile aux personnes qui n'y connaissent rien.

Autre chose, j'ai également ajouté un peu de contenu à la fin, en indiquant des bibliothèques de SVM pour différents langages ; mes modifications sont principalement dans l'introduction, la première et la dernière partie.

De ce que j'avais vu ce ne sont que des paramètres qui sont ajustés par apprentissage. Je vois pas bien la différence avec un programme classique où une variable évolue et influe sur le déroulement.

En fait, dès que ton programme prend en compte les données précédentes pour ajuster ses paramètres, c'est également du machine learning. Ce que j'appelle "algo classique", c'est un algo où toutes les règles sont fixées et immuables (si le diamètre est supérieur à 10 cm, c'est une pomme, sinon et si c'est rouge et tout rond, c'est une groseille, sinon c'est une fraise). Par exemple, la régression linéaire, c'est aussi du machine learning.

Donc, dans un algo classique, les variables peuvent évoluer, mais les exemples vus par le passé n'influent pas les nouveaux exemples.

+0 -0

Salut, je pense qu'il n'y a pas que moi que ca dérange de voir un acronyme (SVM) partout sans que sa signification ne soit donnée une seule fois, si ?
C'est comme faire un cours sur les espaces vectoriels en les appelant EV tout du long (je n'ai rien trouvé de mieux sur le coup).

Je pense que c'était (en partie) le sens de la remarque de SpaceFox.

Ok, je vois. Je n'en ai effectivement pas parlé dans l'introduction, parce que SVM signifie Support Vector Machines, soit machines à vecteurs support. Et je me voyais mal expliquer ce qu'est un vecteur support dans l'intro. C'est pour ça que je ne donne pas le sens de l'acronyme avant la partie 3, mais effectivement je rajouterai l'acronyme dans l'intro sans rentrer dans les détails pour la prochaine version.

Je l'ai dévoré ! Ce serrait cool qu'il sorte un jour.

Bon par-contre je reste sur ma faim sur le multiclasse. Je veux dire pour le one-vs-all, ça voudrait dire que sûrement on devrait avoir recourt à l'astuce du noyau, ou alors j'ai pas compris. Pour le one-vs-one, j'ai simplement pas compris, mais il est vraiment tard, ça viens très certainement du fait que je sois pas réactif mais peut-être qu'avec plus d'explications je comprendrais.

Dans tous les cas, je me renseignerais sur la page Wikipédia.

+0 -0

Je n'ai pas oublié cet article ! En fait je me suis aperçu qu'il serait pas mal de changer l'ordre des parties (donner des vagues intuitions en premier), et depuis juillet je n'ai pas eu une minute à moi. Je m'en occupe quand je serai revenu de vacances (dans un mois :soleil: )

Pour répondre à tes questions, le one-vs-all, tu sais que plus tu es proche de la frontière, plus tu es incertain de ton résultat. Si je reprends l'exemple de l'article, tu sauras si l'insecte est abeille ou pas abeille, guêpe ou pas guêpe, et frelon ou pas frelon. Si tes résultats sont, dans l'ordre, pas abeille/guêpe/pas frelon, tu sais que c'est un frelon. Si tu as plusieurs résultats positifs, alors tu regarde celui pour lequel tu as le plus de certitude, et on dit que c'est le résultat de ta classification.

Le one-vs-one, c'est plus un système de voteurs : est-ce que l'insecte est plus une guêpe ou une abeille ? Une guêpe ou un frelon ? Une abeille ou un frelon ? L'espèce qui aura remporté le plus de "duels" sera jugée comme étant l'espèce la plus probable, et sera le résultat retourné par le SVM. Je rajouterai des schémas pour mieux expliquer le concept. :)

+0 -0

Merci !

C'est carrément claire comme ça x')

Reste plus qu'à implémenter ! Je fais ça dès que j'ai le temps en Python et pourquoi pas en C ou même JS si je veux le présenter.

+0 -0

A mon sens, il y a quelques confusions sur les definitions donnees en intro. Pour etre sur de ne pas trop dire de betises, je me base sur The Elements ofStatistical Learning (gratuit en ligne) et Artificial Intelligence: A Modern Approach.

Le machine learning permet de trouver une solution a un problème à partir des données. On distingue :

  • l'apprentissage supervisé, qui consiste à analyser dans un premier temps des données contenant le classement attendu, puis a appliquer sur d'autres donnees dont le classement n'est pas connue
  • l'apprentissage non supervisé, qui consiste à classer des données sans connaissances préalable

Pour reprendre l'exemple de Russel et Iving, si on prend comme exemple la detection de spams :

  • une approche classique serait d'écrire des règles du type "si le mail contient plus de 50% de majuscules, c'est probablement un spam".
  • une approche supervisée consiste à donner une liste de mails a l'algorithme, en indiquant les spams et non spams. L'algo en déduit des règles permettant de classer au mieux les spams et non spams. Puis on applique ces regles sur des emails sont l'algo ne sait pas si ce sont des spams ou non.
  • une approche non-supervisée consiste à donner directement les mails à l'algo et celui-ci essaie de regrouper les mails les plus semblables ensembles et de séparer les emails les plus dissemblables. L'algo est dans ce cas incapable de séparer en spam/non spam, mais si on lui donne un mail, il pourra dire qu'il est plus proche de tel groupe de mails ou de tel autre groupe.

Tout simplement qu'au début, un algorithme de machine learning ne sait rien faire ; puis, au fur et à mesure qu'il s'entraîne sur des données, il est capable de répondre de plus en plus efficacement à la tâche qu'on lui demande de faire.

les algorithmes de machine learning classique, où l'ordinateur est capable d'effectuer un apprentissage à partir de données pré-traitées ;

Donc ca, c'est pas le machine learning, mais l'apprentissage supervisé.

et enfin le deep learning, où l'algorithme apprend lui-même à faire le pré-traitement, avant de passer à l'étape d'apprentissage.

Et ca, c'est du non supervisee.

Le deep learning, c'est autre chose. C'est l'application du learning pour des problématiques complexes, sur des grosses bases de donnees.

Mais avant toute chose, un SVM, c'est quoi ? C'est tout simplement un algorithme qui, étant donné une entrée, est capable d'assigner une catégorie à cette entrée. Par exemple, on peut entraîner un SVM de telle sorte que, quand on lui présente les caraactéristiques d'un fruit (taille, poids, diamètre…), il soit capable de dire si c'est une pêche, une poire, une fraise… Sans que l'on ait jamais dit au SVM ce qu'est une fraise ! Comme tous les algorithmes de machine learning, le SVM l'aura appris tout seul, à partir d'exemples d'entraînement.

Donc non. Lors de l'apprentissage, on presente un certain nombre de fruits à l'algo, en lui disant si c'est une fraise ou non. Et l'algo "apprend" quels sont les caractéristiques qui permettent de faire la différence entre une fraise ou non.

D'ailleurs, dans tes exemples ensuite, tu dis bien que l'on donne au SVM les labels des points lors de l'apprentissage.

plus particulièrement des SVM, qui sont un des outils de machine learning particulièrement efficaces pour la classification.

"efficace" est peut être trop subjectif. Il est populaire, assez ancien et bien connu, pas trop complexe à comprendre, mais c'est peut être gênant de parler d'efficacité en dehors de tout contexte.

+0 -0
  • une approche supervisée consiste à donner une liste de mails a l'algorithme, en indiquant les spams et non spams. L'algo en déduit des règles permettant de classer au mieux les spams et non spams. Puis on applique ces regles sur des emails sont l'algo ne sait pas si ce sont des spams ou non.

Tu as peut-être juste oublié de le mentionner, mais c'est un peu plus compliqué que ça. On ne se contente pas de lui balancer des exemples, on lui indique également des caractéristiques (features) à étudier (nombre de majuscules, de signes de ponctuation, présence ou non de tels mots…). Ce que l'algorithme fait, c'est "simplement" déterminer la valeur 50% que tu donnes en exemple.

+0 -0

gbdivers : attention, il y a d'un côté la distinction machine learning "classique"/deep learning, et de l'autre apprentissage supervisé/apprentissage non supervisé. Il existe du ML classique supervisé (SVM, perceptrons…), non supervisé (K-means, notamment), et du DL supervisé (réseaux de neurones profonds), et non supervisé (j'ai du regarder sur Google, mais apparemment ça existe, disclaimer je n'ai pas lu l'article).

Le deep learning est principalement utilisé sur les gros ensembles de données… parce qu'il est bien trop inefficace sur les dataset trop petits (sur-apprentissage). Si tu prends un réseau de neurones profond, tu montes très rapidement à des dizaines, des centaines de milliers de paramètres libres. Si tu n'as que 1 000 données d'entraînement, tu n'iras pas bien loin. Mais sinon, tu peux très bien lancer un SVM sur un dataset de plusieurs milliers/millions de données, même si ça va commencer à devenir lent, il n'y a pas de limite théorique aux nombres de données d'entraînement au ML classique, sauf erreur de ma part.

De façon étonnante, je n'ai jamais vu de définition formelle du deep learning. Si on regarde la vidéo d'intro des conférences de Yann Le Cun au Collège de France, il dit (32-33 minutes) que le deep learning, c'est dès qu'on a plus d'une transformation non-linéaire dans notre algorithme, mais juste sur un bout de slide, je ne sais pas si c'est un consensus. Et puis, c'est pas une notion très parlante.

Pour reprendre ton exemple des spam, on a selon moi trois cas :

  • J'écris un ensemble de règles qui disent si un mail est un spam ou non -> algo classique
  • J'essaie, à partir d'indicateurs sur le mail (nombre de majuscules, langue, nombre de mots sur "liste noire" …) de faire apprendre à l'ordi quels sont les spams, ou simplement de les lui faire classifier de façon non supervisée -> machine learning classique
  • Je donne les mails en brut à la machine, et je la laisse extraire les caractéristiques d'un spam pour pouvoir les détecter ou les classifier de manière non supervisée -> deep learning.

évidemment, cette distinction n'a rien de formel non plus, mais de ma maigre expérience en machine learning, en deep learning l'extraction des caractéristiques est laissée à la machine, ce qui n'est pas le cas en ML classique. Après, je peux me tromper là-dessus, mais honnêtement je pense ne pas trop me tromper.

Edit: c'est vrai que je ne parle pas du tout de l'apprentissage supervisé/non supervisé dans mon article. Mais ce n'est absolument pas le but de cet article d'en parler, donc je pense que je peux faire l'omission. :)

+0 -0

gbdivers : attention, il y a d'un côté la distinction machine learning "classique"/deep learning, et de l'autre apprentissage supervisé/apprentissage non supervisé. Il existe du ML classique supervisé (SVM, perceptrons…), non supervisé (K-means, notamment), et du DL supervisé (réseaux de neurones profonds), et non supervisé (j'ai du regarder sur Google, mais apparemment ça existe, disclaimer je n'ai pas lu l'article).

melepe

Ok, donc on est donc d'accord sur les principes, ce sont 2 notions transverses.

A la lecture de l'intro, je pense qu'un lecteur peut penser que tu assimiles machine learning = apprentissage supervise et deep learning = apprentissage non supervisee.

Quand tu lis par exemple la phrase "un algorithme de machine learning ne sait rien faire ; puis, au fur et à mesure qu'il s'entraîne sur des données, il est capable de répondre de plus en plus efficacement à la tâche qu'on lui demande de faire", si on prend le k-mean que tu cites (donc learning classique non supervise), on n'y a pas de notion d'apprentissage et d'amélioration progressive des résultats retournés par l'algo. Au mieux, on utilisera les résultats retournés par une première passe de l'algo pour supprimer ou regrouper des donnees et relancer l'algo, mais ca ne sera plus les mêmes donnees. Et ca ne sera pas un apprentissage, mais un traitement des donnees fait par une personne.

Edit: c'est vrai que je ne parle pas du tout de l'apprentissage supervisé/non supervisé dans mon article. Mais ce n'est absolument pas le but de cet article d'en parler, donc je pense que je peux faire l'omission.

Oui, je ne disais pas de forcément parler de supervisé et non-supervisé, ce n'est pas nécessaire. Plutôt être sur que le lecteur ne fera cette confusion en lisant l'intro.

en deep learning l'extraction des caractéristiques est laissée à la machine, ce qui n'est pas le cas en ML classique. Après, je peux me tromper là-dessus, mais honnêtement je pense ne pas trop me tromper.

A mon sens, ce n'est pas aussi stricte, on peut balancer des donnees brutes directement en ML aussi (je pense par exemple aux donnees des puces génomiques, qui peuvent être traitées directement par ML). Cela étant dit, je ne suis pas un expert en ML, mais juste un utilisateur. Je ne prendrais pas le risque de m'avancer plus sur ce point ou sur une definition formelle du deep learning.

+0 -0
Ce sujet est verrouillé.