Classer par ressemblance
En une phraseClasser un nouveau cas en regardant les exemples qui lui ressemblent le plus, et comprendre que les mesures, le nombre de voisins et les étiquettes sont des choix humains.
Savoir professeur
Dix minutes de lecture, pour préparer la séance sans connaissance préalable.
L’idée : on ressemble à ses voisins
La méthode des plus proches voisins est l’une des plus anciennes et des plus simples de l’apprentissage automatique. Elle a été décrite en 1951 par deux statisticiens américains, Evelyn Fix et Joseph Hodges, puis étudiée en 1967 par Thomas Cover et Peter Hart.
Son principe tient en une phrase : pour classer un nouveau cas, on cherche, parmi des exemples déjà classés, ceux qui lui ressemblent le plus, et on lui donne la classe de la majorité d’entre eux. Le nombre de voisins consultés se note souvent k. Avec k égal à un, on copie la classe du voisin le plus proche ; avec k égal à trois, les trois plus proches votent.
Il n’y a ni règle écrite ni calcul compliqué. La machine garde simplement tous ses exemples en mémoire, et tout le travail se fait au moment de répondre. On parle parfois d’apprentissage « paresseux ».
Ce que montre la feuille
Chaque message est décrit par deux mesures : son nombre de liens et son nombre de mots écrits en capitales. On peut donc le placer comme un point dans un repère. Les dix-huit points de la feuille ont été classés par un humain : ce sont les exemples étiquetés. Les messages indésirables se regroupent en haut à droite, les messages normaux en bas à gauche.
La ressemblance devient une distance : deux messages se ressemblent si leurs points sont proches. Sur la feuille, on la mesure à la règle. Le quadrillage a la même unité sur les deux axes, sinon la distance n’aurait pas de sens. C’est un vrai problème dans les applications : si une mesure s’exprime en grammes et une autre en kilogrammes, la première écrase la seconde. On ramène alors toutes les mesures à la même échelle.
Les quatre nouveaux messages ont été choisis pour faire apparaître quatre situations.
- A, de la vie scolaire, est entouré de messages normaux : un ou trois voisins, la réponse est la même, et elle est juste.
- B, au milieu des messages indésirables, est classé indésirable dans les deux cas, à raison.
- C, la lettre d’information du club de football, a pour plus proche voisin la lettre d’information de la médiathèque, classée normale malgré ses huit liens. Avec un voisin, la réponse est juste. Avec trois, deux messages indésirables l’emportent, et la réponse devient fausse. Consulter plus de voisins rend la méthode moins sensible aux exceptions, mais l’empêche aussi de reconnaître les cas particuliers.
- D, le message du grand-père, est loin de tous les exemples. La machine le classe pourtant, indésirable, car ses voisins les moins éloignés le sont. Elle ne dit jamais « je ne sais pas », à moins qu’on ne lui fixe une distance maximale.
Trois choix humains
La séance doit faire nommer clairement ces trois choix, car ils reviendront toute l’année.
- Les mesures. Le nombre de liens et de capitales ne disent rien du sens d’un message. Mesurer autre chose, l’expéditeur connu ou non par exemple, aurait sauvé le message du grand-père. Choisir les mesures, c’est décider de ce que la machine peut voir.
- Le nombre de voisins. Il n’existe pas de bon nombre universel. On en essaie plusieurs sur des exemples gardés de côté, ce que la séance 7 approfondira. On préfère un nombre impair pour éviter les égalités entre deux classes.
- Les étiquettes. Quelqu’un a décidé que la lettre de la médiathèque était normale. Une erreur d’étiquette se propage à tous les messages qui lui ressemblent. La séance 4 a montré que deux personnes n’étiquettent pas toujours de la même façon.
De la feuille aux vraies applications
La démonstration des dessins utilise exactement la même méthode, avec trois voisins. Mais un dessin y est décrit par deux cent cinquante-six mesures, une par case d’une grille de seize cases sur seize, et non par deux. On ne peut plus dessiner le repère, mais la distance se calcule de la même façon : on élève au carré l’écart sur chaque mesure, on additionne et on prend la racine carrée. Les élèves qui connaissent la formule de la distance entre deux points dans un repère peuvent le faire remarquer.
L’exemple du courrier est volontairement simplifié. Les vrais filtres combinent des centaines d’indices et d’autres méthodes. La recherche des plus proches voisins reste pourtant partout : recommandation de films ou de musiques à partir des goûts de personnes qui vous ressemblent, recherche d’images semblables, ou recherche des passages de documents les plus proches d’une question pour aider un assistant conversationnel à répondre. La séance 13 montrera comment des mots peuvent devenir des points dans un repère.
Vocabulaire et erreurs fréquentes
Employer : exemple étiqueté, classe, mesure, distance, plus proches voisins, vote majoritaire. Le mot caractéristique est souvent employé à la place de mesure dans les textes spécialisés.
Trois erreurs reviennent. Croire que la machine « lit » le message : elle ne voit que deux nombres. Croire que plus de voisins donne toujours une meilleure réponse : le message C montre le contraire. Croire qu’une réponse calculée est forcément fiable : le calcul du message D est exact, mais il repose sur des mesures qui ne suffisent pas.
Déroulé
- 5 min
Accroche
Projeter deux objets de messages : « Réunion parents-professeurs jeudi » et « FÉLICITATIONS !!! VOUS AVEZ GAGNÉ, CLIQUEZ ICI ». Demander lequel est indésirable et à quoi on le voit. Relever au tableau les indices cités, puis annoncer qu’on va en garder deux, qui se comptent : le nombre de liens et le nombre de mots écrits en capitales.
- 15 min
Le plus proche voisin
Distribuer la feuille, une par binôme. Expliquer le graphique : chaque point est un message déjà classé par un humain, placé selon ses deux mesures. Les binômes placent les quatre nouveaux messages, puis cherchent pour chacun le point le plus proche, à la règle, et notent sa classe. Rôles : l’un place et mesure, l’autre vérifie et écrit ; on échange au message suivant.
- 10 min
Les trois plus proches voisins
Même travail avec les trois points les plus proches : la classe majoritaire l’emporte. Les binômes comparent les deux colonnes et entourent les messages dont la réponse change.
- 10 min
Mise en commun
Projeter le corrigé. Faire raconter le message C : son plus proche voisin est une lettre d’information pleine de liens, classée normale ; avec trois voisins, les messages indésirables l’emportent, à tort. Puis le message D, du grand-père : loin de tout, il est quand même classé, et mal. Faire nommer les trois choix humains : les mesures, le nombre de voisins, les étiquettes.
- 5 min
La même méthode, en plus grand
Projeter la démonstration de la séance 2 et montrer les trois dessins les plus proches qu’elle affiche. C’est la même méthode, avec deux cent cinquante-six mesures par dessin, une par case de la grille, au lieu de deux.
- 5 min
Trace écrite
Projeter la trace écrite, la faire recopier ou distribuer la version imprimée.
- 5 min
Vérification
Lire les quatre questions ; réponses écrites, lettre par lettre, puis correction immédiate.
Version avec ordinateurs
- La feuille reste sur papier : placer les points et mesurer à la règle est le cœur de la séance.
- Pour la dernière étape, les binômes ouvrent ia.edulatex.xyz/demonstrations, deuxième démonstration (« Apprendre par l’exemple »), au lieu de la projection.
- Dessiner une forme et regarder les trois exemples les plus proches que la machine affiche sous sa réponse.
- Chercher un dessin pour lequel les trois voisins ne sont pas d’accord, deux contre un.
- Compter les mesures que la machine compare : une par case de sa grille de seize cases sur seize.
Apprendre par l’exemple
Cette machine a vu 8 ronds et 8 croix dessinés à la main. Dessinez une forme dans le cadre : elle cherche, parmi ses exemples, les trois qui ressemblent le plus à votre dessin.
Votre dessin
Ce que voit la machine
Une grille de 16 × 16 cases plus ou moins noircies. Elle ne voit ni lignes ni formes.
Sa réponse
Dessinez une forme : sa réponse s’affiche ici.
Tout ce qu’elle a vu : 16 exemples
Version sans ordinateur
Toute la séance se fait sans ordinateur. Seule l’avant-dernière étape change : au lieu de la démonstration, on revient aux grilles de la séance 2.
Matériel
- La feuille des élèves, une par binôme.
- Une règle graduée par binôme ; un compas aide pour les trois plus proches voisins.
- Le corrigé, à reproduire au tableau sur un quadrillage.
Consignes
- Mener l’accroche, les deux étapes de la feuille et la mise en commun comme dans le déroulé.
- Rappeler la machine de la séance 2 : chaque case de la grille de cinq sur cinq était une mesure, noircie ou non. Un dessin y était donc décrit par vingt-cinq mesures, et non deux.
- Faire remarquer que compter les cases noircies en commun était déjà une façon de mesurer la ressemblance, et que la machine choisissait l’exemple le plus ressemblant : c’était déjà la méthode du plus proche voisin.
- Conclure : on ne peut pas dessiner un graphique à vingt-cinq axes, mais la machine calcule une distance de la même façon, quelle que soit la quantité de mesures.
Corrigé de la feuille
Les pointillés relient chaque nouveau message à ses trois plus proches voisins.
| Message | Un voisin | Trois voisins | En réalité |
|---|---|---|---|
| A (2 ; 2) | Normal | Normal | Normal |
| B (8 ; 7) | Indésirable | Indésirable | Indésirable |
| C (7 ; 1) | Normal | Indésirable, erreur | Normal |
| D (1 ; 9) | Indésirable, erreur | Indésirable, erreur | Normal |
« Erreur » signale une réponse de la machine qui diffère de la réalité.
Trace écrite
Pour classer un nouveau cas, la méthode des plus proches voisins cherche, parmi des exemples déjà classés, ceux qui lui ressemblent le plus. Le nouveau cas reçoit la classe de la majorité de ces voisins.
La ressemblance se mesure par une distance entre des mesures choisies à l’avance, comme le nombre de liens et de mots en capitales d’un message.
Trois choix humains décident du résultat : les mesures retenues, le nombre de voisins consultés et les étiquettes des exemples. La machine répond toujours, même pour un cas qui ne ressemble à aucun exemple.
Vérification
À projeter ou à lire en fin de séance. Les réponses sont repliées.
-
Comment la méthode des plus proches voisins classe-t-elle un nouveau message ?
- AElle applique des règles écrites par un humain.
- BElle lui donne la classe de la majorité des exemples qui lui ressemblent le plus.
- CElle lit le message et en comprend le sens.
Réponse
B. Elle ne lit rien et n’applique aucune règle : elle compare des mesures, trouve les exemples les plus proches et fait voter leurs classes.
-
Pourquoi le message C change-t-il de classe entre un voisin et trois voisins ?
- AParce que la règle graduée n’est pas assez précise.
- BParce que la machine apprend entre les deux calculs.
- CParce que son plus proche voisin est une exception, et que deux messages indésirables l’emportent quand on en consulte trois.
Réponse
C. Le plus proche voisin de C est une lettre d’information normale, malgré ses nombreux liens. Avec trois voisins, les deux messages indésirables qui suivent font la majorité. Plus de voisins n’est donc pas toujours mieux.
-
Pourquoi le message du grand-père est-il classé indésirable ?
- AParce que les deux mesures choisies ne disent rien du sens du message, et que la machine répond même loin de tout exemple.
- BParce que les messages des grands-parents sont souvent indésirables.
- CParce que la machine s’est trompée dans son calcul.
Réponse
A. Le calcul est juste. Mais beaucoup de capitales et un lien, c’est tout ce que voit la machine, et aucun exemple ne ressemble vraiment à ce message. Elle répond quand même.
-
Qui a décidé de mesurer le nombre de liens et les mots en capitales ?
- ALa machine, au cours de l’apprentissage.
- BDes humains, avant tout calcul.
- CPersonne : ce sont les seules mesures possibles.
Réponse
B. On aurait pu mesurer la longueur du message, connaître ou non l’expéditeur, l’heure d’envoi. Ce choix humain décide de ce que la machine peut voir, et donc de ses erreurs.
Questions difficiles
Les questions d’élèves qui déstabilisent, et une réponse possible.
Alors il vaut mieux prendre un voisin ou trois ?
Ça dépend des données. Un seul voisin suit aveuglément les exceptions ; beaucoup de voisins noient les petits groupes. On essaie plusieurs valeurs sur des exemples gardés de côté et on garde la meilleure, ce que montre la séance 7. On choisit un nombre impair pour éviter les égalités entre deux classes.
Et s’il y a deux points exactement à la même distance ?
Il faut une règle fixée à l’avance : prendre un voisin de plus, tirer au sort, ou préférer la classe la plus fréquente. Sur la feuille, les égalités ne concernent que des voisins de même classe, elles ne changent donc rien.
Pourquoi ne pas ajouter une mesure « l’expéditeur est connu » ?
Excellente idée : c’est exactement le travail de ceux qui conçoivent ces systèmes. Bien choisir les mesures compte souvent plus que la méthode. Les vrais filtres combinent des centaines d’indices, dont l’expéditeur.
La machine sait-elle ce qu’est un courrier indésirable ?
Non. Elle connaît des points et des étiquettes. Le mot « indésirable » n’a pour elle pas plus de sens que « classe 1 ». Ce sont les humains qui ont étiqueté les exemples.
Avec deux cent cinquante-six mesures, comment mesurer une distance qu’on ne peut pas dessiner ?
Par le calcul. Dans un repère, la distance entre deux points se calcule avec les écarts sur chaque axe : on élève chaque écart au carré, on les additionne, on prend la racine carrée. Avec deux cent cinquante-six mesures, la somme a simplement deux cent cinquante-six termes.