Algorithmique de l'apprentissage : voisins et moyennes

Pour $(3,3)$ : $d^2$ vers A $=8,5,5,2$, vers B $=8,13,13,18$. $k=1$ : voisin $(2,2)$, A. $k=3$ : $(2,2),(1,2),(2,1)$ — A, A, A : A unanime. Pour $(4,5)$ : vers A $=25,18,20,13$, vers B $=1,2,4,5$. $k=1$ : $(5,5)$, B ; $k=3$ : $(5,5),(5,6),(6,5)$ — B unanime. Aucun basculement possible ici : chaque point de test a ses $k$ voisins tous du même côté — les nuages sont bien séparés et les points de test francs. Le $k$ ne compte que près de la frontière, là où les $k$ voisins panachent les deux classes — un point comme $(3,5;3,5)$, équidistant des nuages, changerait d'étiquette selon l'arbitrage. (D'où la géométrie à retenir : $k$-NN découpe le plan en zones d'influence, et $k$ règle la finesse du découpage — loin de la frontière, tous les $k$ se valent.)

def evaluer(entrainement: list, test: list, k: int) -> tuple:
    confusion = {}
    for point, vraie in test:
        predite = knn(entrainement, point, k)
        confusion[(vraie, predite)] = confusion.get((vraie, predite), 0) + 1
    reussite = sum(v for (a, b), v in confusion.items() if a == b)
    return (confusion, reussite / len(test))

test = [([0, 1], "A"), ([3, 2], "A"), ([6, 7], "B"), ([4, 5], "B")]
confusion, taux = evaluer(entrainement, test, 3)
assert taux == 1.0 and confusion == {("A", "A"): 2, ("B", "B"): 2}

Quatre points francs, quatre succès : matrice diagonale, taux $100\%$ — le cas facile, qui valide la mécanique avant d'affronter des données bruitées (exercice 4). (Le dictionnaire à clés-couples (chapitre 17) est le format naturel d'une matrice creuse : seules les cases non nulles existent ; pour l'afficher en tableau, parcourir les classes en ordre fixe — et l'absence d'une clé se lit confusion.get((a, b), 0), le zéro des absents, chapitre 16.)

Tour 1 — affectation : $(1,1)\to c_1$ ; $(1,2)\to c_1$ ($d^2=1$ contre $2$) ; $(2,1)\to c_2$ ; les trois points du nuage droit $\to c_2$ ($(5,4)$ : $25$ contre $18$, etc.). Recentrage : $c_1=(1;1,5)$, $c_2=(\frac{2+5+6+5}{4};\frac{1+4+4+5}{4})=(4,5;3,5)$. Tour 2 — affectation : $(2,1)$ rejoint $c_1$ ($d^2=1,25$ contre $12,5$) ; tout le nuage droit reste à $c_2$. Recentrage : $c_1=(\frac{4}{3};\frac{4}{3})$, $c_2=(\frac{16}{3};\frac{13}{3})$. Tour 3 — plus aucun point ne change : stabilité, les deux nuages sont retrouvés. Le mauvais départ s'est résorbé : le centre $c_2$, d'abord tiré vers la droite par les trois points lointains, a fini par émigrer dans leur nuage, libérant $(2,1)$. (Les $k$-moyennes corrigent beaucoup d'initialisations médiocres — c'est leur robustesse pratique ; mais pas toutes, et c'est l'exercice 7 : la différence entre « souvent » et « toujours » est précisément ce qu'un minimum local ne garantit pas.)

(a) $(45+138)/200=91,5\%$. (b) Spams manqués : $15/60=25\%$ des spams atteignent la boîte ; légitimes bloqués : $2/140\approx 1,4\%$ — partis au panier, peut-être un message important. (c) Non : le légitime bloqué coûte généralement bien plus cher (un contrat manqué) que le spam passé (un agacement) — ce classifieur, prudent sur les faux positifs, est probablement bien réglé. Quant au « tout-normal » : $140/200=70\%$… recalcul : il classerait normal les $200$ messages, réussite $140/200=70\%$ — un score honorable en apparence, pour un filtre qui ne filtre rien. C'est le piège des classes déséquilibrées : le taux global flatte le vote pour la classe majoritaire, et seule la matrice révèle l'inutilité ($0\%$ des spams détectés). (Toujours comparer un classifieur au « prédicteur de la classe majoritaire » : c'est le zéro de l'échelle, comme le hasard pur l'est pour deux classes équilibrées — un taux de réussite ne se lit jamais dans l'absolu.)

import random
random.seed(0)
def nuage(cx, cy, n, etiquette):
    return [([random.gauss(cx, 1.2), random.gauss(cy, 1.2)], etiquette)
            for _ in range(n)]
entrainement = nuage(0, 0, 100, "A") + nuage(2, 2, 100, "B")
test         = nuage(0, 0, 100, "A") + nuage(2, 2, 100, "B")

Allure typique des mesures — entraînement : $100\%$ à $k=1$ (chacun est son propre voisin), décroissant ensuite ; test : médiocre à $k=1$ ($\approx 85\%$ : la frontière épouse le bruit), maximal vers $k=7$–$51$ ($\approx 88$–$90\%$), s'effondrant à $k=151$ (presque tout l'entraînement vote : on tend vers le tout-majoritaire). L'écart entre les deux courbes mesure le surapprentissage : énorme à $k=1$, nul aux grands $k$. Le bon $k$ est au creux du U du test — et le choisir en regardant le test, c'est déjà tricher un peu : en toute rigueur, on réserve un troisième paquet (validation) pour ce réglage, et le test ne sert qu'une fois, à la toute fin. (Deux nuages gaussiens qui se chevauchent ont un taux d'erreur incompressible — le meilleur classifieur du monde ne sépare pas l'inséparable : viser $100\%$ en test sur données bruitées n'est pas un objectif, c'est un symptôme.)

(a) En (g, cm), la masse écrase tout : $d^2$ à $(120,6)=1600+12,25$, à $(20,3)=3600+0,25$ — plus proche voisin la pomme de $120$ g : pomme. (b) En (g, mm), le diamètre pèse soudain : $d^2$ à $(120,60)=1600+1225=2825$, à $(20,30)=3600+25=3625$, à $(15,20)=4225+25$… la pomme gagne encore, mais de peu — et un point à $(70,2)$ basculerait : la prédiction dépend de l'unité de mesure, ce qui est scientifiquement indéfendable (le fruit ne change pas avec la règle qui le mesure). (c) Min-max sur l'entraînement : masse sur $[15,150]$, diamètre sur $[2,7]$ — le point devient $(0,48;0,1)$, les fraises $(0,0)$ et $(0,04;0,2)$, les pommes $(1,1)$ et $(0,78;0,8)$. $d^2$ à la fraise $(0,04;0,2)$ : $\approx 0,20$ ; à la pomme $(0,78;0,8)$ : $\approx 0,58$ — fraise, et la réponse est désormais invariante par changement d'unités. (La normalisation n'est pas un raffinement : sans elle, le classifieur encode arbitrairement « un gramme vaut un centimètre » — une hypothèse que personne n'a posée ; tout algorithme à distances — $k$-NN, $k$-moyennes — y est soumis, et l'oubli de normalisation est l'erreur n°1 des débutants en apprentissage.)

(a) Gauche/droite : centres $(0;0,5)$ et $(10;0,5)$, chaque point à $d^2=0,25$ — inertie $1$. Bas/haut : centres $(5,0)$ et $(5,1)$, chaque point à $d^2=25$ — inertie $100$ : cent fois pire. (b) Depuis $c_1=(5,0)$, $c_2=(5,1)$ : le point $(0,0)$ est à $d^2=25$ de $c_1$ et $26$ de $c_2$ — il choisit $c_1$ ; de même chaque point choisit le centre de sa hauteur. Recentrage : les moyennes redonnent exactement $(5,0)$ et $(5,1)$ — rien ne bouge, l'algorithme déclare la convergence sur l'inertie $100$. Aucun geste local ne peut le sauver : il faudrait échanger deux points à la fois, et l'algorithme ne fait que des réaffectations individuellement avantageuses — c'est la définition vécue d'un minimum local. (c) En initialisant sur deux points tirés au hasard parmi les quatre : les $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ paires sont équiprobables — les $4$ paires « mixtes » (un point de chaque côté) convergent vers gauche/droite, et les $2$ paires d'un même côté convergent toujours vers le mauvais partage bas/haut (l'affectation initiale sépare déjà les deux hauteurs, et plus rien ne bouge) : la probabilité exacte d'un bon départ est $4/6\approx 67\%$ — la simulation le confirme, et surtout : sur $10$ départs indépendants, la probabilité de tous les rater devient négligeable — garder la meilleure inertie des dix est la police d'assurance standard. (L'inertie joue ici le rôle du certificat relatif : elle ne dit pas « c'est l'optimum », elle permet de comparer les candidats — et c'est assez pour que la stratégie multi-départs fonctionne ; on retrouvera ce schéma partout où l'optimisation est non convexe, c'est-à-dire partout en intelligence artificielle moderne.)

import matplotlib.pyplot as plt
xs, ys, couleurs = [], [], []
pas = 0.2
for i in range(-20, 31):
    for j in range(-20, 31):
        x, y = i * pas, j * pas
        xs.append(x); ys.append(y)
        couleurs.append("tab:blue" if knn(entrainement, [x, y], 25) == "A"
                        else "tab:orange")
plt.scatter(xs, ys, c=couleurs, s=8)         # la carte des décisions

À $k=1$ : une frontière déchiquetée, constellée d'îlots — chaque point d'entraînement isolé en territoire adverse possède sa petite enclave (il est le plus proche voisin de son voisinage immédiat) : le surapprentissage se voit, ce sont les îlots du bruit. À $k=25$ : une frontière lisse, quasi rectiligne entre les deux nuages, les îlots engloutis par le vote — et au-delà ($k\to n$), la frontière sortirait du cadre : tout deviendrait majoritaire. La courbe en U de l'exercice 5 est la traduction chiffrée de cette géométrie : les îlots de $k=1$ sont autant de zones où le test se trompe, la rigidité des très grands $k$ aussi. (La carte de décision est l'outil de diagnostic visuel de tout classifieur 2D — l'analogue apprentissage du tracé de fonctions du chapitre 4 : quand les nombres se disputent, dessiner ; au-delà de deux dimensions, on perd ce luxe, et c'est précisément pourquoi les matrices de confusion existent.)

(a) Chaque pixel est un point de ${\mathbb{R}}^1$ (sa valeur $0$–$255$) ; chercher les $4$ niveaux qui représentent au mieux l'image, c'est minimiser la somme des carrés des écarts pixel-niveau : la définition exacte de l'inertie des $k$-moyennes — la « quantification » est un partitionnement déguisé. (b)

def quantifier(image: list, k: int) -> list:
    valeurs = [[float(v)] for ligne in image for v in ligne]
    centres, _ = k_moyennes(valeurs, valeurs[::len(valeurs) // k][:k])
    def niveau(v):
        return round(min(centres, key=lambda c: abs(c[0] - v))[0])
    return [[niveau(v) for v in ligne] for ligne in image]

(c) Sur un dégradé uniforme $0$–$255$, les centres convergent vers les quarts d'étendue ($\approx 32,96,160,224$) : l'image quantifiée est un escalier de quatre paliers — le posterize des logiciels de retouche. Compression : $4$ niveaux $=2$ bits par pixel au lieu de $8$, facteur $4$ (plus la table des centres, négligeable). Sur une photo, les centres ne sont pas équirépartis : ils se densifient là où l'histogramme s'accumule (les zones de peau, le ciel) — c'est la force des $k$-moyennes sur la quantification uniforme : adapter les niveaux aux données. (En couleurs, même algorithme en dimension $3$ — les pixels $(R,V,B)$, les centres devenant la palette : la quantification chromatique des vieux formats d'image, c'est mot pour mot l'algorithme de ce chapitre, et le voir opérer referme la boucle ouverte au chapitre 8.)

Le pipeline, dans l'ordre et avec ses interdits : (1) Séparer d'abord — avant toute statistique : mélanger (random.shuffle), couper $180/60/60$. Faute évitée : normaliser puis séparer — les min/max auraient « vu » le test, fuite d'information (modeste ici, fatale en général). (2) Normaliser : min/max calculés sur les $180$ points d'entraînement, appliqués tels quels aux $120$ autres — quitte à ce qu'un point de test sorte de $[0,1]$ : c'est normal, et c'est le réel. (3) Choisir $k$ : pour $k\in \{1,3,5,\dots ,31\}$, entraîner sur les $180$, mesurer sur la validation — courbe en U, maximum typique vers $k=7$–$15$ ($\approx 90\%$ : trois gaussiennes qui se touchent). Faute évitée : choisir $k$ sur le test — le test devient une validation déguisée et son chiffre final ment. (4) Évaluer une fois : le $k$ élu, prédire les $60$ points de test, publier la matrice $3\times 3$ — typiquement forte diagonale et confusions concentrées entre les deux classes géométriquement voisines : la matrice localise la difficulté (quelles classes se ressemblent), ce que le taux global ne dira jamais. (5) Geler : tout réglage ultérieur (changer $k$, re-normaliser) au vu du test impose un nouveau jeu de test. (Ce protocole en cinq temps est le squelette de tout projet d'apprentissage, du TP au laboratoire ; les algorithmes changeront — réseaux de neurones compris — le protocole, non : c'est lui, bien plus que l'algorithme, qui sépare une mesure honnête d'une illusion d'optique, et c'est la leçon que ce chapitre voulait laisser.)