Atteindre 78 % de précision sur MNIST avec GZIP en moins de 10 lignes de code

• Expérience montrant qu’il est possible d’atteindre environ 78 % de précision sur la classification des chiffres manuscrits MNIST en utilisant uniquement la compression GZIP et le k-plus proches voisins (k-NN), ce qui suggère qu’on peut utiliser la compression comme outil de classification sans modèle
• La distance de compression normalisée (NCD) est calculée à partir de la différence de longueur lorsqu’on compresse ensemble deux échantillons d’image, puis utilisée comme mesure de similarité entre images
• Chaque échantillon de test est comparé à 100 échantillons d’entraînement, et l’étiquette majoritaire parmi les k=5 voisins les plus proches devient la prédiction
• En raison du coût de calcul, la précision a été mesurée sur une partie des images de test plutôt que sur l’ensemble du jeu de test ; utiliser le jeu complet pourrait rendre l’évaluation plus précise
• L’exemple public contient encore une erreur de refactorisation : un cache des longueurs compressées est créé mais n’est pas utilisé dans le calcul réel de la NCD ; il faut donc soit supprimer le cache, soit l’intégrer dans compute_ncd

---

Classer MNIST avec GZIP + k-NN

• L’expérience classe le jeu de données de chiffres manuscrits MNIST avec la combinaison GZIP + k-NN
• Le court exemple de code utilise la longueur du résultat de gzip.compress(z.tobytes()) comme longueur compressée, calcule la NCD, puis choisit l’étiquette la plus fréquente parmi les 5 voisins les plus proches
• Un exemple exécutable est disponible dans ce Jupyter Notebook
• L’objectif n’est pas d’obtenir la meilleure précision possible, mais de valider simplement l’idée d’utiliser la compression comme outil de classification sans modèle
• Le code en moins de 10 lignes relève moins du cœur de l’expérience que d’un aspect ludique de code golf

Calcul de similarité et procédure de classification

• La NCD mesure la similarité en normalisant à quel point le coût de compression de deux points de données ensemble diffère de leur compression séparée
• La longueur compressée est calculée sous la forme suivante
  • Cx1 = len(gzip.compress(x1.tobytes()))
  • Cx2 = len(gzip.compress(x2.tobytes()))
  • Cx1x2 = len(gzip.compress((x1 + x2).tobytes()))
• La formule de la NCD est de la forme (Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2)
• La classification consiste à calculer la distance entre chaque image de test et les images d’entraînement, à trier par proximité, puis à utiliser le vote majoritaire des 5 plus proches
• Dans l’expérience, la comparaison se fait sur la base de 100 échantillons d’entraînement et, en raison du coût de calcul, seulement sur une partie du jeu de test

Idées de référence et points d’attention dans le code

• Cette approche s’inspire de l’article text generation from data compression et du papier parameter free text classification
• Après la rédaction de l’article, l’auteur a aussi découvert MNIST by ZIP, un billet d’Andreas Kirsch publié en 2019 avec une méthode similaire
• Le code d’exemple crée bien un cache des longueurs compressées des échantillons d’entraînement, mais n’utilise pas réellement ces valeurs dans la boucle principale
  • Dans la version standard comme dans la version obfusquée, compressed_lengths ou cls sont créés, mais les longueurs mises en cache ne sont pas utilisées dans le calcul de la NCD
  • Supprimer le cache et utiliser directement training_set, ou modifier compute_ncd pour exploiter les valeurs en cache, permettrait d’aligner l’intention du code avec son implémentation

[GN⁺]

Avis de Hacker News

• En remplaçant la fonction de distance du code par une métrique plus simple, la distance GZIP donne une précision plus faible pour la classification MNIST, avec un coût de calcul bien plus élevé
  Distance Gzip : environ 3 min, 78 % de précision / distance euclidienne : environ 0,5 s, 93 % / distance de Jaccard : environ 0,7 s, 94 % / dissimilarité de Dice : environ 0,8 s, 94 %
  Jaccard et Dice sont mesurées après binarisation des images
  Je ne connais pas très bien l’algorithme GZIP, mais il est intéressant que les résultats soient aussi bas, et je me demande si un algorithme de compression centré sur l’image ferait mieux
  L’article lui-même est créatif, avec du bon code et de bonnes explications, mais je pense que les lignes de base ci-dessus ajoutent du contexte au score de gzip

  • Le meilleur résultat que j’ai trouvé est la normalised mutual information, avec 95 %, et même si c’est un peu plus complexe, elle peut être calculée assez rapidement sur des images binarisées
    NMI skimage : environ 30 s, 95 % de précision / NMI numba : environ 0,6 s, 95 % de précision
    J’ai calculé les comptages conjoints 2x2, l’entropie et l’information mutuelle normalisée avec le code numba fourni par ChatGPT
  • Je savais que MNIST était simple, mais je ne pensais pas que c’était à ce point ; ce serait vraiment utile comme ligne de base si vous pouviez partager le bout de code utilisé
    Personnellement, je m’intéresse à l’entraînement rapide sur CIFAR10, donc ce genre d’approche pourrait aussi être assez utile dans d’autres domaines
  • L’implémentation des méthodes à noyaux de ben recht atteint 98 % en 10 lignes
    https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
  • J’ai aussi essayé la compression PNG, et elle fait en fait un peu mieux : PNG donne environ 83 % de précision en 15,1 s
    J’ai aussi ajouté zstandard : Zstd(level=3) donne environ 88 % de précision en 3,5 s, donc beaucoup plus vite que gzip
    Si, pour calculer Cx1x2, on utilise (x1-x2)*2 au lieu de x1+x2, zstd monte jusqu’à 93 % de précision
    Si on empile les deux tableaux l’un au-dessus de l’autre sans les additionner, les performances s’effondrent complètement à moins de 20 %, alors que cette méthode semble bien marcher pour la classification de chaînes, ce qui est intéressant
  • L’approche gzip est stylée, mais au final elle semble donner de moins bons résultats avec davantage d’étapes

• En comparaison avec d’autres techniques, Linear SVC atteint 92 %, SVC à noyau RBF 96,4 %, SVC à noyau polynomial 94,5 %, la régression logistique 89 % et le naïve Bayes environ 81 %
  Source : https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi...
  À lire des articles en ligne, il semble possible d’obtenir de bien meilleurs résultats avec seulement K-NN, donc l’auteur s’est peut-être compliqué la tâche en utilisant gzip

  • Beaucoup de gens ignorent que la régression logistique peut atteindre environ 90 % de précision sur MNIST
    J’aime commencer par un modèle simple puis ajouter de la complexité ensuite, mais j’ai souvent entendu dire que « la régression logistique ne marche pas », même sur des problèmes où elle fonctionne en réalité très bien
    Quand on demande quelle performance de référence on attendrait sur MNIST, beaucoup de gens estiment 20 à 30 %
    Même les personnes qui font du machine learning sous-estiment souvent à quel point les rendements décroissants arrivent vite quand on augmente fortement la complexité du modèle
    Dans de nombreux cas, si un modèle simple n’obtenait pas de bonnes performances, il était difficile d’obtenir d’excellentes performances avec un modèle plus complexe
  • Ce blog ne montre pas les meilleures performances actuelles ; il compare plutôt des implémentations SVM relativement simples
    L’article original qui a introduit le jeu de données MNIST atteignait déjà environ 98 % de précision, et les réseaux de neurones actuels montent jusqu’à 99,87 %
    https://paperswithcode.com/sota/image-classification-on-mnis...
  • Le point essentiel n’est pas de faire mieux, mais de montrer qu’après compression il reste assez d’information pour obtenir un signal fort
    La compression est justement là pour rendre le problème plus difficile, et c’est bien ce qu’elle continue de faire
  • C’est chouette que ça fonctionne, mais MNIST est devenu tellement facile que j’aimerais qu’on arrête maintenant de l’utiliser comme benchmark
  • Il existe donc un algorithme de compression plus optimal pour la relation entre les entrées et les sorties de MNIST
    Comme les autres modèles ont tendance à ajouter du bruit quelque part, je me demande ce que donnerait de l’ingénierie de caractéristiques avant gzip
    Par exemple, on pourrait commencer par appliquer un flou gaussien et des convolutions, puis utiliser le deep learning pour la sélection de caractéristiques

• Le code peut être élégant et court, mais 78 % de précision sur MNIST, c’est très mauvais
  Même un modèle factice fait avec TensorFlow atteint facilement 90 % de précision, et les meilleurs modèles sont à 99,87 %
  Benchmark : https://paperswithcode.com/sota/image-classification-on-mnis...

  • Je pense que l’article met l’accent au mauvais endroit
    Ce qui est intéressant, c’est qu’on peut utiliser la compression pour classifier sans entraîner de modèle
    Cela amène donc à se demander si d’autres mesures informationnelles, moins coûteuses et avec perte, pourraient aussi être utilisées
    To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review
    [https://arxiv.org/abs/2304.09355\)" class="ud link">https://arxiv.org/abs/2304.09355\](https://arxiv.org/abs/2304.09355\)*
  • L’objectif n’est pas de produire du code « élégant et court », mais de montrer une curiosité intéressante ; le faire en 10 lignes est plutôt un défi supplémentaire
    Ce qui est intéressant, ce n’est pas de savoir si GZip atteint l’état de l’art, mais le fait qu’il parvienne à classifier à peu près correctement
    C’est un peu comme un ours qui jouerait du piano : ce qui est étonnant, ce n’est pas qu’il reproduise Mozart à la perfection, mais qu’il soit capable d’en jouer
  • Ce n’est pas une tentative de battre un record, mais un exemple qui montre un aspect intéressant de la compression
    Cela dit, c’est tout de même 8 fois meilleur que la ligne de base, et cela montre que la compression peut apprendre une représentation

• Si l’on remplace compute_ncd par une distance euclidienne, la précision de test augmente de 15 points de pourcentage et le volume de calcul baisse fortement.
  Il suffit de changer en quelque chose comme distances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths].

• Parmi les livres qui traitent des liens profonds entre théorie de l’information, compression et algorithmes d’apprentissage, MacKay est celui que j’ai trouvé le meilleur.
  Pour des personnes correctement formées, c’est peut-être évident, mais en tant qu’autodidacte ayant fait du machine learning très orienté pratique, j’ai eu un puissant moment « ah, d’accord ! » en voyant ce sujet se prolonger jusque dans des domaines comme la physique des particules et la cosmologie.
  Je laisse ça ici en espérant qu’au moins une personne aura la même prise de conscience.

  • J’ai ajouté MacKay à ma liste de choses à faire.
    J’ai trouvé assez marquant d’apprendre que la compression Lempel-Ziv originale, l’une des bases de gzip, venait moins d’une simple tentative de réduire la taille que de recherches sur la « complexité des suites finies ».
    https://ieeexplore.ieee.org/document/1055501

• Pour être juste, MNIST est presque parfaitement séparé dès qu’on le passe dans UMAP.
  À mon avis, de nos jours, il faut vraiment faire des efforts pour obtenir de mauvaises performances sur MNIST.
  https://github.com/lmcinnes/umap_paper_notebooks/blob/master...
  Il vaudrait mieux mettre ce jeu de données à la retraite ; des jeux comme QuickDraw ont beaucoup plus de sens, je pense.

  • En tant qu’auteur, je suis totalement d’accord.
    Ce n’est pas vraiment une grande réussite en soi, mais c’est tout de même intéressant de voir que ça fonctionne.
    Quand je rentrerai chez moi, j’ajouterai dans l’article que résoudre MNIST est relativement facile.
  • Du point de vue de la recherche, MNIST est en pratique un problème résolu, et les performances actuelles sont probablement meilleures que celles des humains.
    Cela dit, comme la plupart des algorithmes simples et raisonnables atteignent 97 % de précision, il garde de la valeur comme outil pédagogique ou comme jeu de données Hello world.
    Même en construisant ses outils soi-même depuis zéro, cela reste à l’échelle d’un devoir, et c’est une tâche utile que tout le monde comprend, comme la « reconnaissance de chiffres sur du courrier ».
  • gzip n’est pas un « truc moderne » : c’est une technologie bien plus ancienne qu’UMAP, et même que MNIST lui-même.
    Si l’on comprend la compression, cette approche est aussi une idée très simple ; elle aurait pu être écrite dès le premier jour de publication de MNIST et aurait tout de même obtenu 78 % de précision.
    C’est ce point que je trouve assez surprenant.
  • Cela suffit presque à donner raison à la personne impolie qui se plaignait des acronymes.
    Le dépôt ne définit pas non plus UMAP, mais si l’on en croit ChatGPT, UMAP signifie Uniform Manifold Approximation and Projection ; c’est une technique de réduction de dimension et de visualisation utilisée en machine learning et en analyse de données.

• Je ne connais ce domaine qu’en amateur, mais des données fortement compressées n’ont-elles pas une entropie élevée, comme des données chiffrées ?
  Si l’on trouve dans des données compressées des motifs permettant d’identifier le chiffre d’origine, ne devrait-on pas pouvoir utiliser ces motifs pour une meilleure compression ?

  • Cette démonstration ne classe pas les données en regardant les données compressées, mais selon la qualité avec laquelle les données se compressent.
    L’idée est que « 7 7 » devrait mieux se compresser que « 7 3 », et que, dans des images raster, « 7 7 » se compressera aussi mieux que « 7 3 ».
  • Des données chiffrées idéales devraient être incompressibles.
    L’incompressibilité est une caractéristique des opérations cryptographiques efficaces.
    Voir la section sur la compression de l’article sur la complexité de Kolmogorov : https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress...
    L’un des concepts que j’aime en compression est le principe des tiroirs, qui dit que pour tout algorithme de compression, il existe nécessairement des sorties plus grandes que leurs entrées.
    On peut tenter de compresser une charge utile chiffrée bien conçue, mais en moyenne la sortie sera plus grande que l’entrée, ce qui rend la compression inutile ; c’est pourquoi on dit qu’elle est « incompressible ».
    https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...

• Il me semble qu’il y a quelques années, quelqu’un avait utilisé la taille des images MNIST comme « méta-caractéristique », mais je n’arrive pas à retrouver ça rapidement.
  De mémoire, sans même regarder les images, cette seule caractéristique donnait une précision d’environ 90 %.

  • Il y a quelques années, j’ai travaillé sur un projet de fingerprinting de captures d’écran de pages web, et la seule taille de l’image compressée fonctionnait aussi bien qu’une certaine méthode d’empreinte destinée à comparer la similarité entre captures d’écran.
  • Je me demande ce que signifie ici « taille ».
    La taille après compression avec gzip ? Si l’on regarde simplement à quel point une image MNIST est sombre, c’est-à-dire la proportion de pixels sombres, on obtient environ 20 % de précision : deux fois mieux qu’un tirage aléatoire, mais très loin de 90 %.

• Je soupçonne que les auteurs de cet article se sont trompés, ce qui a fait bondir leurs résultats en haut du benchmark.
  Depuis cet incident, je considère que la théorie n’est pas cohérente, mais 78 % de précision avec GZIP seul reste impressionnant.

  • Tu penses probablement à cet article : https://kenschutte.com/gzip-knn-paper/
  • Ici, il s’agit de 78 % de précision avec une distance de compression basée sur Gzip et KNN ; cela semble donc pire qu’à peu près n’importe quelle autre métrique de distance imaginable combinée à KNN.

• Indépendamment du fait que ce problème soit ou non un bon cas d’usage pour une astuce de compression, les personnes qui expérimentent devraient arrêter d’utiliser gzip et utiliser zlib.
  En remplaçant simplement la première ligne, de gzip.compress à zlib.compress, on devrait obtenir les mêmes performances de classification avec une vitesse multipliée par 3.