Aller au contenu principal

Classer

Ce que ce chapitre apporte

  • Formuler un problème de classification et dire ce qui le distingue d'une régression.
  • Dérouler l'algorithme du perceptron et énoncer sa garantie, ainsi que sa limite.
  • Montrer sur un exemple qu'aucune droite ne sépare deux classes disposées en damier.
  • Écrire une régression logistique et dire pourquoi elle rend une probabilité.
  • Justifier l'emploi de la perte logarithmique plutôt que des moindres carrés.
  • Régler le nombre de voisins et reconnaître ce qu'il contrôle.
  • Construire un arbre de décision et lire la forme de sa frontière.
Prédire un nombre demandait de mesurer un écart. Prédire une catégorie demande autre chose : tracer une frontière dans l'espace des attributs, et décider de quel côté tombe chaque cas. Ce chapitre présente quatre façons de tracer cette frontière, une droite, un vote de voisins, une suite de questions, et une probabilité. Elles échouent différemment, et c'est en regardant la forme de leurs régions qu'on comprend laquelle convient.

Une frontière, pas un écart

Classification binaire

Étant donné des exemples décrits par des attributs et étiquetés par l'une de deux classes, une classification cherche une règle qui attribue une classe à tout nouveau cas.

Géométriquement, cette règle découpe l'espace des attributs en régions, une par classe. La frontière de décision est la limite entre ces régions.

Regarder la région, pas la formule
Deux classifieurs peuvent se tromper sur le même nombre d'exemples et se comporter de façon entièrement différente ailleurs. Ce qui les distingue n'est pas leur score, c'est la forme de la région qu'ils colorient.
Une droite découpe le plan en deux demi-plans, et rien d'autre ne lui est possible. Un vote de voisins produit un contour qui épouse les données. Un arbre ne sait tracer que des frontières parallèles aux axes, donc des rectangles.
Ces formes sont des hypothèses sur le problème, faites avant d'avoir vu la moindre donnée. Les figures de ce chapitre montrent la région entière plutôt que la seule frontière, parce que c'est là que se lit l'hypothèse.

Dans la figure ci-dessous, le fond montre la classe prédite en chaque point du plan. Les trois curseurs font pivoter et glisser la droite ; onze exemples sont mal rangés au départ.

246246température (°C)charge du processeur
erreurs apprentissage 11 / 28

11 points mal classés sur 28. Faire pivoter et glisser la droite change ce nombre, mais une droite reste une droite.

Deux classes séparables par une droite. En laissant les deux poids à 1 et en descendant le biais jusqu'à −6, les vingt-huit exemples se rangent correctement. Toute valeur entre −6 et −8 convient : quand deux classes sont bien écartées, il n'existe pas une bonne droite mais une infinité.

Le perceptron

La règle, et elle tient en une ligne

Partir de poids nuls. Parcourir les exemples ; à chaque fois qu'un exemple est mal classé, ajouter son vecteur d'attributs aux poids, avec le signe de sa classe :

w←w+yi xisi yi(w⋅xi)≤0w \leftarrow w + y_i\, x_i \qquad \text{si } y_i (w \cdot x_i) \leq 0

Recommencer tant qu'il reste des erreurs.

main.py
Sortie
>_ Prêt à exécuter…
La garantie, et exactement ce qu'elle ne dit pas
Le théorème de convergence du perceptron affirme que si les deux classes sont séparables par une droite, l'algorithme s'arrête après un nombre fini de corrections, et le nombre de corrections est borné par (R/γ)2(R/\gamma)^2 où RR est le rayon du nuage et γ\gamma la marge de la meilleure droite.
C'est une garantie forte, et elle est entièrement conditionnelle. Si les classes ne sont pas séparables, le théorème ne dit rien du tout, et l'algorithme ne s'arrête pas : il corrige indéfiniment, en changeant de droite à chaque passage.
Rien dans le code ne signale cette situation. Une boucle sans limite tournerait pour toujours, et une boucle avec limite rend une droite quelconque parmi celles qu'elle a traversées. C'est pourquoi toute implémentation borne le nombre de passages, et c'est aussi pourquoi le perceptron a été abandonné au profit de méthodes qui minimisent une erreur plutôt que de compter des fautes.

Ce qu'une droite ne peut pas faire

02460246température (°C)charge du processeur
erreurs apprentissage 18 / 28

18 points mal classés sur 28. Faire pivoter et glisser la droite change ce nombre, mais une droite reste une droite.

Les mêmes deux classes, disposées en damier. Aucun réglage des trois curseurs ne descend au-dessous de sept erreurs sur vingt-huit, soit un quart des exemples. Ce n'est pas une question de patience : le balayage complet de la grille des curseurs a été fait, et sept est le minimum.
Le damier, et pourquoi il a arrêté un domaine pendant quinze ans
Une droite sépare le plan en deux morceaux. Ici chaque classe occupe deux coins opposés, et aucune coupure droite ne peut réunir deux coins opposés d'un côté et les deux autres de l'autre.
Le meilleur qu'une droite puisse faire est d'isoler un coin sur quatre, donc de se tromper sur un quart des points. Le balayage de la grille entière des curseurs le confirme : sept erreurs sur vingt-huit, jamais moins.
C'est la fonction « ou exclusif », et Minsky et Papert en firent en 1969 l'argument décisif contre le perceptron. Le domaine s'en est largement détourné pendant une quinzaine d'années.
Deux issues existent, et ce sont les deux mêmes que partout ailleurs. Changer d'espace : en ajoutant l'attribut x×yx \times y, le damier devient séparable par un plan. Ou empiler les couches : deux droites suivies d'une combinaison suffisent, et c'est le sujet du chapitre 10.

Une probabilité plutôt qu'un côté

Régression logistique

Calculer un score z=w⋅x+bz = w \cdot x + b, puis le convertir en probabilité par la fonction logistique

σ(z)=11+e−z\sigma(z) = \frac{1}{1 + e^{-z}}

qui envoie tout réel dans ]0,1[\left]0, 1\right[, vaut 0,50{,}5 en z=0z = 0, et croît d'autant plus vite que zz est proche de zéro.

La frontière de décision reste une droite, celle où z=0z = 0. Ce qui change est que le modèle annonce désormais à quel point il est sûr.

main.py
Sortie
>_ Prêt à exécuter…
Le gradient est celui du chapitre 5, au mot près
Pour la régression, le gradient de l'erreur valait 2nX⊤(Xβ−y)\frac{2}{n} X^{\top}(X\beta - y), soit la matrice des attributs multipliée par le vecteur des écarts.
Pour la régression logistique, le gradient de la perte logarithmique vaut 1nX⊤(σ(Xw)−y)\frac{1}{n} X^{\top}(\sigma(Xw) - y) : la même chose, avec la probabilité à la place de la prévision.
Cette coïncidence n'en est pas une. Elle vient de ce que la fonction logistique et la perte logarithmique sont faites l'une pour l'autre, et c'est précisément ce qui rend cette perte préférable à toute autre.
La différence est qu'ici aucune formule fermée n'existe. Il faut descendre, ce qui est exactement la situation annoncée au chapitre 6.
main.py
Sortie
>_ Prêt à exécuter…
Pourquoi pas les moindres carrés sur une probabilité
La réponse tient dans la dernière colonne du tableau.
Quand le modèle attribue une probabilité de 0,001 à un exemple qui est en réalité de classe 1, il se trompe autant qu'il est possible. La perte logarithmique produit alors une poussée de 0,999, la plus forte possible : le modèle est violemment corrigé.
La perte carrée produit une poussée de 0,002. Elle s'est évanouie, parce que la dérivée de la sigmoïde s'annule aux extrémités et vient multiplier le terme d'erreur. Le modèle reste bloqué dans sa certitude fausse.
Il y a une seconde raison, plus technique et tout aussi décisive : la perte logarithmique composée avec la sigmoïde est convexe en les poids, donc sans minimum local, alors que la perte carrée ne l'est pas.

Les plus proches voisins

k plus proches voisins

Aucune phase d'apprentissage : les exemples sont simplement conservés.

Pour classer un nouveau cas, chercher les kk exemples les plus proches et prendre la classe majoritaire parmi eux.

02460246température (°C)charge du processeur
erreurs apprentissage 0 / 36erreurs test 4 / 32

Avec un seul voisin, chaque point est son propre voisin le plus proche : aucune erreur d'apprentissage, par construction. Le contour épouse le moindre relevé, y compris ceux qui sont faux.

Quatre relevés ont été mal étiquetés, deux dans chaque camp adverse. À k = 1 le contour se plie pour les englober : zéro erreur d'apprentissage, mais quatre erreurs de test. Dès k = 3 les îlots disparaissent, l'apprentissage compte quatre erreurs, qui sont exactement les quatre relevés faux, et le test n'en compte plus qu'une.
Ce que règle vraiment le nombre de voisins

À k = 1, chaque exemple est son propre voisin le plus proche. L'erreur d'apprentissage vaut donc zéro par construction, sans que cela signifie quoi que ce soit. Le contour se plie autour de chaque relevé, y compris autour des quatre qui sont faux, et l'erreur de test vaut 4 sur 32.

À k = 3, les îlots ont disparu. L'erreur d'apprentissage remonte à 4, et il se trouve que ces quatre exemples mal classés sont exactement les quatre relevés faux. Le modèle a cessé de les croire. L'erreur de test tombe à 1 sur 32.

C'est le même mécanisme que le degré du polynôme au chapitre précédent, et il conduit à la même conclusion : une erreur d'apprentissage nulle est un symptôme, pas un résultat.

Trois pièges propres aux voisins
L'échelle. La méthode repose entièrement sur une distance, donc la variable la plus étalée décide seule, exactement comme au chapitre 4. Standardiser est obligatoire.
Le coût. Il n'y a pas d'apprentissage, mais chaque prédiction exige de parcourir tout le jeu de données. Le coût est reporté sur l'usage, et il grandit avec le nombre d'exemples conservés.
La dimension. Quand les attributs se comptent par dizaines, tous les points deviennent à peu près équidistants les uns des autres et la notion de voisinage perd son sens. La méthode brille en petite dimension et s'effondre en grande.

Les arbres de décision

Construction descendante

Chercher la coupe qui sépare le mieux les classes, sous la forme « attribut jj inférieur ou égal à un seuil ss ». Recommencer séparément de chaque côté, jusqu'à ce qu'un groupe soit pur ou qu'une limite soit atteinte.

La qualité d'une coupe se mesure par l'impureté de Gini, 2p(1−p)2p(1-p) pour deux classes, qui vaut zéro quand un groupe est pur et un demi quand il est parfaitement mélangé. On retient la coupe qui minimise la moyenne pondérée des impuretés des deux côtés.

main.py
Sortie
>_ Prêt à exécuter…
les questions poséesles régions qui en résultentouinonouinontempérature ≤ 4,1A17·2charge ≤ 3,3A1B18·2températurecharge ↑
3 feuilles4 / 36 erreursprofondeur réelle 2

Chaque coupe de l'arbre découpe un rectangle de plus dans le plan. Il y en a 2 ici, pour 3 régions.

L'arbre à gauche, les régions qu'il découpe à droite. Chaque coupe ajoutée est un rectangle de plus. À la profondeur 2 il reste quatre erreurs, qui sont les quatre relevés mal étiquetés ; en poussant jusqu'à 5 il n'en laisse plus qu'une, au prix de neuf régions au lieu de trois. Le bloc Python ci-dessus va jusqu'à la profondeur 10, où l'arbre atteint zéro erreur avec onze feuilles.
Pourquoi les deux moitiés doivent se regarder ensemble
Une coupe de l'arbre à gauche est un trait dans le plan à droite, et rien d'autre. Voir les deux bouger en même temps rend évidente la propriété qu'on énonce partout sans jamais la montrer : un arbre ne compare qu'un attribut à un seuil, donc ses frontières sont parallèles aux axes, toujours.
Le compteur de feuilles dit combien de régions ont été créées, et l'arbre s'arrête parfois de lui-même avant la profondeur demandée : quand aucune coupe ne fait plus baisser l'impureté, ou quand les deux côtés rendraient la même classe, il ne sert à rien de creuser.
Pousser le curseur jusqu'au bout montre enfin à quoi ressemble une erreur d'apprentissage nulle : des lamelles absurdes, tracées autour de quatre relevés faux.
Le même U, pour la troisième fois
L'erreur d'apprentissage descend de 5 à 0 quand la profondeur passe de 1 à 10, sans jamais remonter. L'erreur de test passe par un creux à zéro en profondeur 2, puis remonte à 3.
C'est exactement la forme rencontrée avec le degré du polynôme et avec le nombre de voisins. Trois modèles sans rapport, un seul phénomène : au-delà d'un certain point, la souplesse supplémentaire ne sert plus qu'à apprendre le bruit.
Ce qui change d'un modèle à l'autre est seulement le nom du réglage qui contrôle la souplesse : le degré, le nombre de voisins, la profondeur. Chercher ce réglage est la première chose à faire devant un modèle inconnu.
Ce que les arbres apportent, et ce qu'ils coûtent
Ils se lisent. L'arbre de profondeur 3 s'énonce en quatre phrases, compréhensibles par quelqu'un qui n'a jamais entendu parler de la méthode. Aucun autre modèle de ce module n'a cette propriété.
Ils ne demandent pas de mise à l'échelle, puisqu'ils comparent chaque attribut à un seuil, sans jamais mélanger deux attributs dans un même calcul. C'est le seul modèle du chapitre à s'en dispenser.
Ils traitent les variables qualitatives directement, sans indicatrices.
En regard, ils sont instables : déplacer un seul exemple peut changer la première coupe et donc tout l'arbre. Et leurs frontières sont des escaliers, ce qui approche mal une séparation oblique. Ces deux défauts se corrigent en moyennant des centaines d'arbres, ce qui donne les forêts aléatoires et le gradient boosting, méthodes qui dominent aujourd'hui les données en tableau. Le prix payé est la lisibilité, qui disparaît entièrement.

Quatre frontières sur les mêmes points

main.py
Sortie
>_ Prêt à exécuter…
Le même score, et des hypothèses opposées
La régression logistique, les cinq voisins et l'arbre de profondeur 2 se trompent tous sur quatre exemples sur trente-six. Un tableau de résultats les déclarerait équivalents.
Leurs frontières n'ont rien à voir. L'une est une droite, et le restera quelles que soient les données. L'autre est un contour organique qui suit les exemples. La troisième est faite de rectangles, parce qu'un arbre ne compare jamais qu'un attribut à un seuil.
L'arbre de profondeur 10, lui, atteint zéro erreur en découpant de fines lamelles autour de chaque relevé faux. C'est visuellement absurde, et c'est exactement ce que produit une erreur d'apprentissage nulle.
Le choix entre ces modèles ne se fait donc pas sur le score. Il se fait sur la forme qu'on croit raisonnable pour le problème, sur le besoin d'expliquer la décision, et sur le coût à l'usage.
Ce que ferait scikit-learn
from sklearn.linear_model import LogisticRegression, Perceptron
from sklearn.neighbors import KNeighborsClassifier
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

m = make_pipeline(StandardScaler(), LogisticRegression()).fit(X, y)
v = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5)).fit(X, y)
a = DecisionTreeClassifier(max_depth=3).fit(X, y)     # pas de mise a l'echelle ici
print(export_text(a, feature_names=["temperature", "charge"]))
print(m.predict_proba(X)[:5])

Deux détails valent d'être notés. LogisticRegression applique par défaut une pénalité sur les coefficients, comme au chapitre 7 : ce n'est donc pas exactement le modèle écrit plus haut. Et predict_proba rend la probabilité, alors que predict rend déjà la classe en tranchant à 0,5 ; le chapitre suivant montre pourquoi ce seuil ne doit presque jamais rester à 0,5.

Exercices type

Le perceptron tourne depuis dix mille passages sans s'arrêter. Que faut-il en conclure ?

Que les données ne sont pas séparables par une droite.

Le théorème de convergence garantit un arrêt en un nombre fini de corrections si et seulement si une droite sépare parfaitement les deux classes. En l'absence de cette condition, il ne dit rien, et l'algorithme corrige indéfiniment en changeant de droite à chaque passage.

Ce n'est ni un défaut de réglage ni un problème de patience, et augmenter la limite ne servira à rien.

Trois suites possibles : ajouter des attributs qui rendent le problème séparable, par exemple un produit de deux attributs existants ; passer à un modèle qui minimise une erreur au lieu de compter des fautes, comme la régression logistique, qui s'arrête toujours ; ou empiler des couches, ce qui est le sujet du chapitre 10.

Pourquoi une droite ne peut-elle pas séparer un damier ?

Parce qu'une droite coupe le plan en deux morceaux, et que chaque classe occupe ici deux coins opposés.

Réunir deux coins opposés d'un même côté d'une droite est géométriquement impossible : la droite qui les sépare des deux autres devrait passer entre eux, donc les séparer aussi.

Le mieux qu'une droite puisse faire est d'isoler un coin sur quatre, d'où un quart des points mal classés. Le chapitre l'a vérifié par balayage complet de la grille des curseurs : sept erreurs sur vingt-huit, jamais moins.

C'est l'argument avec lequel Minsky et Papert ont arrêté les recherches sur le perceptron en 1969, et les deux issues connues sont de changer d'espace d'attributs ou d'empiler des couches.

Pourquoi ne pas entraîner un classifieur avec les moindres carrés sur sa probabilité ?

Parce que le gradient s'évanouit là où il faudrait qu'il pousse le plus fort.

Un exemple de classe 1 auquel le modèle attribue la probabilité 0,001 est une erreur maximale. La perte logarithmique produit alors une poussée de 0,999, la plus forte possible. La perte carrée produit une poussée de 0,002, parce que la dérivée de la sigmoïde s'annule aux extrémités et vient multiplier le terme d'erreur.

Le modèle reste donc bloqué dans une certitude fausse, sans qu'aucun message d'erreur ne le signale.

Une seconde raison suffirait à elle seule : la perte logarithmique composée avec la sigmoïde est convexe en les poids, donc sans minimum local, alors que la perte carrée ne l'est pas.

Un classifieur k plus proches voisins avec k = 1 obtient 100 % de réussite sur ses données. Est-ce bon signe ?

Non, c'est mécanique et cela ne signifie rien.

Avec k = 1, chaque exemple d'apprentissage est son propre voisin le plus proche. Sa classe prédite est donc toujours la sienne, quelles que soient les données. Le score est de 100 % même si toutes les étiquettes sont fausses.

Le chapitre le mesure : à k = 1, zéro erreur d'apprentissage mais quatre erreurs de test. À k = 3, quatre erreurs d'apprentissage, qui sont exactement les quatre relevés mal étiquetés, et une seule erreur de test.

C'est le pendant exact du polynôme de degré 11 du chapitre précédent, et la conclusion est la même : il faut mesurer sur des données que le modèle n'a pas vues.

Quel est le seul modèle du chapitre qui n'exige pas de mise à l'échelle ?

L'arbre de décision.

Il ne compare jamais qu'un attribut à un seuil, et ne mélange donc jamais deux attributs dans un même calcul. Multiplier une colonne par mille déplace ses seuils d'autant et ne change rien à l'arbre obtenu.

Tous les autres en dépendent. Les k plus proches voisins reposent entièrement sur une distance, où la variable la plus étalée écrase les autres. La régression logistique et le perceptron restent corrects sans mise à l'échelle mais convergent bien plus lentement, pour la raison de conditionnement vue au chapitre 6.

En pratique, standardiser par défaut et faire de l'arbre l'exception explicite, plutôt que l'inverse.

Trois modèles obtiennent le même nombre d'erreurs. Comment choisir ?

Pas sur le score, puisqu'il ne les distingue pas.

Sur la forme de la frontière. Une droite suppose que les classes se séparent linéairement ; un arbre, que les découpages utiles sont parallèles aux axes ; les voisins, que des cas proches ont le même sort. Laquelle de ces hypothèses est raisonnable pour le problème ?

Sur le besoin d'expliquer. Un arbre de profondeur 3 s'énonce en quatre phrases. Aucun autre modèle du chapitre ne s'explique aussi simplement, et il y a des contextes où cela décide seul.

Sur le coût à l'usage. Les voisins n'apprennent rien mais parcourent tout le jeu à chaque prédiction. Les autres apprennent une fois et prédisent instantanément.

Sur la stabilité. Un arbre change entièrement si l'on déplace un exemple ; une régression logistique bouge à peine.

Vérification rapideon peut se reprendre

1.Quelle forme a nécessairement la frontière d'un arbre de décision ?

2.Le perceptron ne s'arrête pas après des milliers de passages. Cela signifie…

3.Combien d'erreurs, au minimum, une droite commet-elle sur un damier équilibré ?

4.Pourquoi la perte logarithmique plutôt que la perte carrée sur une probabilité ?

5.Avec k = 1, l'erreur d'apprentissage des plus proches voisins vaut…

6.Quel modèle du chapitre se dispense de mise à l'échelle ?

La méthode

  1. Standardiser les attributs, sauf pour un arbre, où c'est inutile.
  2. Commencer par un modèle linéaire, qui donne une référence en quelques secondes.
  3. Regarder la frontière, pas seulement le score, quand le problème est en deux ou trois dimensions.
  4. Chercher le réglage qui contrôle la souplesse : degré, nombre de voisins, profondeur.
  5. Le choisir par validation croisée, jamais sur le jeu de test.
  6. Se méfier d'une erreur d'apprentissage nulle, qui est mécanique pour k = 1 et pour un arbre profond.
  7. Préférer un arbre court quand la décision doit s'expliquer, une forêt quand seule la performance compte.
  8. Retenir la probabilité, et non la classe, tant que le seuil n'a pas été choisi.

Synthèse

  • Une classification découpe l'espace des attributs en régions ; c'est leur forme qui distingue les modèles.
  • Le perceptron corrige quand il se trompe, et s'arrête en temps fini si les classes sont séparables.
  • Sur un damier, aucune droite ne descend au-dessous d'un quart d'erreurs. C'est une impossibilité géométrique.
  • La régression logistique rend une probabilité ; sa frontière reste une droite.
  • Son gradient est celui du chapitre 5 avec la probabilité à la place de la prévision, et aucune formule fermée n'existe.
  • La perte carrée sur une sigmoïde sature : elle cesse de corriger quand le modèle se trompe avec aplomb.
  • Les k plus proches voisins n'apprennent rien ; à k = 1 l'erreur d'apprentissage est nulle par construction.
  • Ils exigent une mise à l'échelle, coûtent à chaque prédiction, et s'effondrent en grande dimension.
  • Un arbre trace des rectangles, se lit en toutes lettres, et se dispense de mise à l'échelle.
  • Degré, nombre de voisins, profondeur : trois noms pour un seul réglage, celui de la souplesse, et le même U à chaque fois.
  • Un même score peut recouvrir des hypothèses opposées ; le choix ne se fait pas sur le score.

Mettre en pratique

De quel côté de la frontière, la probabilité logistique, et le k qui change la réponse.

Tous les exercices sur classer