Pourquoi les chiffres de l’article « gzip beats BERT » ne correspondent-ils pas ?

 (kenschutte.com)
1 points par GN⁺ 2023-07-18 | 1 commentaires | Partager sur WhatsApp
  • Les performances du classifieur kNN basé sur gzip mises en avant dans l’article de Jiang et al. sur la classification de texte en low-resource pourraient avoir été calculées non pas avec une précision kNN standard, mais d’une manière proche d’un top-2 avec k=2
  • Dans experiments.py du dépôt officiel, calc_acc considère comme correcte toute prédiction où l’un des labels ex aequo correspond au bon label, de sorte qu’il suffit qu’un seul des deux échantillons d’apprentissage les plus proches soit juste pour compter comme un succès
  • En recalculant la colonne “Full” des quatre premiers jeux de données, plusieurs chiffres changent, et sur KirundiNews, la méthode gzip passe de la meilleure à la moins bonne performance
  • Une réimplémentation séparée montre que la sortie du code officiel était toujours identique à top2, et qu’en résolvant les égalités à k=2 en donnant priorité à l’échantillon le plus proche, on obtient en pratique le même résultat que k=1
  • L’option rand==True casse les égalités via random.choice, mais ne semble pas avoir été utilisée pour les résultats de l’article, tandis que SogouNews n’a pas encore été exécuté à cause de la taille des données

Problème de calcul de la précision révélé lors de la reproduction des résultats de l’article

  • Le sujet est l’article de Jiang et al., “Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors, dont le tableau montrant que la méthode basée sur gzip surpassait plusieurs méthodes neuronales a attiré l’attention sur Twitter
  • Lors de la reproduction du code source officiel, il a été constaté que la méthode de calcul de la précision du classifieur kNN ne se comportait pas comme dans l’approche habituelle
  • En particulier, avec k=2, on se rapproche davantage d’une précision top-2 que d’une précision kNN(k=2) normale, ce qui peut conduire à surestimer les performances de la méthode de l’article

Pourquoi les égalités posent problème avec un kNN à k=2

  • La méthode de l’article utilise un classifieur kNN et, d’après l’Appendix C, k=2 est utilisé dans toutes les expériences
  • Une classification avec k=2 cherche les 2 échantillons d’apprentissage les plus proches pour chaque échantillon de test, ce qui rend la situation des labels très simple
    • Si les deux labels sont identiques, ce label est prédit, ce qui revient au même résultat que k=1
    • Si les deux labels sont différents, on obtient une égalité 1:1, ce qui nécessite une règle supplémentaire pour départager, par exemple donner priorité à l’échantillon le plus proche
  • Si l’égalité est cassée aléatoirement, alors dans la moitié des cas d’égalité 1:1, on choisit l’échantillon le plus éloigné, ce qui rend difficile de faire mieux que k=1

La manière dont calc_acc traite les égalités

  • Le point problématique se situe dans la méthode calc_acc de experiments.py
  • Le flux du code rassemble dans sorted_pred_lab les labels des top-k échantillons ainsi que leurs comptes, puis les regroupe par label avant de les trier selon le nombre d’occurrences
  • Il parcourt ensuite les labels à égalité pour le compte maximal, et si l’un d’eux correspond au label de test, if_right = 1, ce qui le compte comme correct
  • Avec k=2, si deux labels différents reçoivent chacun 1 vote, cela revient simplement à vérifier si l’un des deux candidats est le bon label
  • Le résultat ressemble à la précision top-k au sens d’ImageNet, mais avec une différence importante : ici, la référence n’est pas un ensemble de k labels sélectionnés, mais de k échantillons d’apprentissage
  • Cette méthode accepte un k arbitraire, mais ne calcule pas du top-k pour toutes les valeurs de k ; avec k=2, il se produit simplement une situation particulière où tous les candidats sont regroupés avec un compte maximal de 1
  • calc_acc possède un drapeau rand, et quand rand==True, les égalités sont cassées via random.choice, mais cela ne semble pas avoir été utilisé pour les résultats de l’article

Évolution des précisions après recalcul

  • Dans la colonne “Full” des quatre premiers jeux de données, les chiffres de l’article et les valeurs corrigées knn2d sont les suivants
Catégorie KinyarwandaNews KirundiNews DengueFilipino SwahiliNews
Article 0.891 0.905 0.998 0.927
knn2d corrigé 0.835 0.858 0.999 0.850
  • Le cinquième jeu de données, SogouNews, n’a pas encore été exécuté en raison de sa taille
  • Cette différence change fortement l’interprétation des expériences, et sur KirundiNews, la méthode gzip passe de la meilleure à la moins bonne performance

Résultats confirmés par une implémentation séparée

  • L’implémentation séparée utilise deux stratégies de résolution des égalités
    • r : choix aléatoire
    • d : réduction de k jusqu’à disparition de l’égalité
  • Les résultats de la réimplémentation sont les suivants
Méthode kinnews kirnews filipino swahili Description
table5 0.891 0.905 0.998 0.927 Valeurs du tableau de l’article
code 0.891 0.906 1.000 0.927 Utilisation du dépôt npc_gzip
top2 0.891 0.906 1.000 0.927 top-2
knn1r 0.835 0.858 0.999 0.850 kNN, k=1, égalité aléatoire
knn1d 0.835 0.858 0.999 0.850 kNN, k=1, réduction de k en cas d’égalité
knn2r 0.828 0.807 0.851 0.842 kNN, k=2, égalité aléatoire
knn3r 0.838 0.791 0.851 0.881 kNN, k=3, égalité aléatoire
knn2d 0.835 0.858 0.999 0.850 kNN, k=2, réduction de k en cas d’égalité
knn3d 0.843 0.794 0.904 0.883 kNN, k=3, réduction de k en cas d’égalité
  • La vérification met en évidence ce que calculait réellement le code officiel
    • table5 est proche de code à 0.001 ou 0.002 près, ce qui permet de reproduire les chiffres de l’article
    • code est toujours identique à top2, ce qui montre que les résultats du code officiel correspondent aux résultats top-2 de la réimplémentation
    • knn1r == knn1d, et avec k=1, il n’y a pas d’égalité
    • knn2d == knn1d, et avec k=2, si l’égalité est résolue en prenant le premier échantillon, on revient au même résultat que k=1
    • knn2r < knn2d, et dans les égalités 1:1 à k=2, le choix aléatoire conduit une fois sur deux à prendre l’échantillon le plus éloigné

Points restant à vérifier

  • Une nouvelle réimplémentation incluant davantage de valeurs de k est disponible dans gzip-knn
  • La raison pour laquelle DengueFilipino atteint des scores très élevés, parfois proches de 1.0, sera traitée dans un billet de suivi Part 2
  • La raison de la légère différence entre table5 et code dans deux cas reste encore à confirmer

À lire aussi

1 commentaires

 
GN⁺ 2023-07-18
Avis sur Hacker News

  • C’est sans doute décevant pour les auteurs, mais je trouve que c’est une excellente réfutation
    En machine learning, il est vraiment facile de commettre ce genre d’erreur ; pire encore, une erreur méthodologique subtile ne se manifeste généralement pas, comme dans d’autres domaines de l’ingénierie ou des sciences, par un échec fatal, mais par une légère variation des performances
    Même si de mauvaises données se glissent dans le jeu d’entraînement, ou que des informations sur la valeur cible fuient, le système continue plus ou moins de fonctionner, et seuls les résultats sont légèrement contaminés
    Appliquer des algorithmes de compression existants au machine learning donne trop l’impression d’un repas gratuit, contrairement à ce qu’on espérait. S’il y avait une magie particulière dans les algorithmes de compression, on les aurait utilisés comme encodeurs plutôt que d’utiliser des transformers comme compresseurs

    • Il faut absolument garder cela à l’esprit. Les erreurs sont faciles à faire, donc courantes, et la science est un processus bruité, mais il y a aussi du signal dedans ; ce que l’on voit ici, c’est précisément l’essence de la revue par les pairs
      C’est pourquoi je soutiens souvent que la publication ouverte est une meilleure forme de revue par les pairs que les conférences et les revues. La revue par les pairs, c’est quand mes pairs examinent mon travail ; l’essentiel n’est pas dans les critères arbitraires et bruités mis en avant par une conférence ou une revue
      Pendant la majeure partie de l’histoire, cela fonctionnait ainsi, et la revue par les pairs au sens moderne est un concept assez récent, datant du milieu des années 1970. Les anciennes revues avaient plutôt pour mission de diffuser la recherche, comme le fait aujourd’hui arxiv
      https://mitcommlab.mit.edu/broad/commkit/peer-review-a-histo...
      Une autre raison de plaider pour la suppression des conférences et des revues, c’est que cela permettrait d’encourager activement des travaux importants comme les articles de reproduction ou les articles d’échec. On ne serait plus lié au critère de « nouveauté », et en réalité presque toute la recherche est incrémentale
      « Publier », c’est transmettre mon travail à mes pairs et leur permettre de vérifier ou de réfuter les résultats
      Cela dit, le fait que les conférences rassemblent les gens et favorisent la collaboration est une bonne chose. Ce que je critique ici, c’est l’usage des conférences et des revues comme moyen de juger la validité de la recherche
      Si le système des conférences n’était qu’un lieu invitant la recherche et la communauté, il n’y aurait aucun problème. Les revues sont aussi, en théorie, intéressantes parce qu’il existe un dialogue entre auteurs et reviewers, mais je pense que cela peut facilement se faire avec arxiv + github ou OpenReview
    • Cette approche est déjà utilisée. Il suffit de chercher le principe de longueur de description minimale et les classifieurs fondés sur l’entropie
      Les performances sont mauvaises, mais cela existe bel et bien et c’est très facile à déployer. Les textes similaires ont tendance à mieux se compresser, et j’ai déjà vu gzip utilisé pour détecter le plagiat
      On peut aussi utiliser le taux de compression comme poids dans un modèle à ressorts pour la visualisation, et l’appliquer aux métadonnées de communications réseau
    • C’est vrai pour beaucoup d’expériences. Le désir d’obtenir le résultat souhaité l’emporte facilement sur la nécessité de vérifier ce qu’on a réellement obtenu
      C’est particulièrement le cas lorsque les résultats confirment ce que l’on pensait déjà
    • J’étudie beaucoup le machine learning ces derniers temps, et je vois souvent ce genre de schéma. C’est un autre point qui me semble être l’exact opposé de presque tout ce que j’ai fait comme ingénieur logiciel
      Oublier un seul point-virgule provoque immédiatement une erreur
      Mais si l’on se trompe dans le calcul du gradient d’une couche sur trois, cela peut parfois quand même tourner. Simplement, les résultats deviennent étranges
    • Le code de recherche académique est généralement un tas de code brouillon écrit aussi vite que possible par des amateurs, avec très peu de tests, et son principal produit est d’accumuler des citations d’articles
      Un monde avec deux fois moins d’articles scientifiques et deux fois plus d’attention créerait beaucoup plus de valeur, mais tout le système est désespérément gamifié

  • Je suis la personne qui a écrit ce billet de blog. Je suis assez sûr de ce que j’y ai écrit, mais s’il y a quelque chose qui m’a échappé, il faudra peut-être que les auteurs l’expliquent eux-mêmes
    Je viens d’ouvrir une issue sur GitHub : https://github.com/bazingagin/npc_gzip/issues/3

    • Il pourrait être utile d’envisager d’ajouter une note en haut de l’article. Beaucoup de gens semblent se contenter de survoler le titre et comprendre « l’article sur gzip est bidon et l’approche gzip n’est pas terrible », alors qu’en réalité cela ressemble plutôt à « l’approche gzip ne fait pas mieux que les modèles de réseaux neuronaux profonds, mais elle est globalement compétitive et coûte beaucoup moins cher à exécuter »
      L’article lui-même reste solide
    • Je suis le premier auteur de l’article et j’ai lu le billet de blog. La raison pour laquelle nous avons choisi k=2 est que l’usage de n^{1/2} était recommandé, et que nous voulions choisir un k compatible avec le réglage 5-shot
      Mais vous avez raison de dire que ce choix est un peu étrange. Comme nous l’avons dit dans l’article et sur Twitter, les résultats changent quand la valeur de k change, et ce que nous avons rapporté était le meilleur résultat possible, ce qui correspond à une situation idéale où la prédiction est toujours correcte
      Nous avons appliqué la même stratégie à W2V et SentBERT. Cela ne signifie toutefois pas qu’il s’agit d’une précision top-2. À ma connaissance, la précision top-2 donne un point si l’une des deux classes les mieux prédites est correcte
      Or, comme vous l’avez signalé, avec kNN et k=2, il existe des cas où les deux plus proches voisins indiquent la même classe ; dans ce cas, si l’on rapportait la précision top-2, on manquerait une autre classe candidate
      Quand j’aurai le temps de mettre en ligne une nouvelle version sur arxiv, j’aimerais ajouter des résultats avec d’autres stratégies et d’autres valeurs de k. La stratégie de décrémentation mentionnée dans le blog est vraiment bonne, et si vous le souhaitez, j’aimerais l’ajouter au dépôt
      Désolé pour cette réponse courte et tardive. Je n’ai pas encore pu vérifier le dépôt. Je prépare demain une évaluation d’article ; une fois terminée, je répondrai à l’issue et la résoudrai
    • Merci pour la reproduction, c’est un travail important
      Je me demande si vous avez aussi reproduit l’autre tableau de résultats, le Table 3
      Si je comprends bien, lorsque deux classes seulement existent, la précision top-2 vaut 1, mais à mesure que le nombre de classes augmente, l’écart avec la précision « normale » diminue en moyenne. Donc si le dataset comporte beaucoup de classes, les résultats du Table 3 ne devraient pas changer tant que cela
      Quoi qu’il en soit, une précision top-2 de 0,685 sur le dataset 20-newsgroups est assez impressionnante pour une méthode qui ne voit même pas les caractères comme des caractères[1]. Sans parler des bons outils dans lesquels les chercheurs en traitement automatique des langues ont investi des années, comme les tokens, les n-grammes ou les embeddings
      [1] D’après ce que je comprends, gzip ne manipule que des suites de bits, qui ne sont pas nécessairement alignées sur les mots, c’est-à-dire sur les frontières d’octets
    • Je me demande si vous avez d’abord contacté les auteurs avant de publier

  • Quand nous faisions des expériences de pertinence de recherche chez Shopify, nous avons aussi commis beaucoup d’erreurs, et je comprends les auteurs. J’ai moi-même fait pas mal d’erreurs publiquement embarrassantes
    Vers la fin de mon passage chez Shopify, j’ai appris qu’une bonne science exige une bonne ingénierie logicielle. Parce qu’il est facile de se tromper à trop d’endroits de la stack
    Nous avons donc passé beaucoup de temps à construire des logiciels d’expérimentation rigoureux, très testés et de haute qualité, afin de pouvoir faire confiance aux chiffres et reproduire les expériences les uns des autres
    Nous essayions d’éviter les méthodes d’évaluation ponctuelles ; quand nous créions une nouvelle méthode, nous l’ajoutions à la suite d’outils d’évaluation, puis nous la testions pour comprendre ce que signifiait cette métrique
    Cela paraît évident, mais d’après mon expérience avec ce type d’expériences, ce n’est malheureusement pas aussi courant qu’on le souhaiterait. Les entreprises veulent aller vite, et réfléchir en profondeur aux statistiques ou construire des outils internes ne s’aligne généralement pas très bien avec les intérêts de la hiérarchie

    • Dire qu’« une bonne science exige une bonne ingénierie logicielle » est un aspect positif de la recherche industrielle
      D’abord, on peut mobiliser davantage d’expertise en ingénierie logicielle ; ensuite, il y a une incitation à moins exagérer les affirmations. Car si l’on dit que ça marche, on s’attend à ce que ce soit mis en production réelle

  • Je suis content que ce billet de blog ait été publié
    Je fais moi aussi énormément de petits projets de ce genre, et même ce type de travail qui met en évidence un problème dans un article ne voit souvent jamais le jour. En général, ça fait un peu de bruit un instant, puis ça finit enterré sur un disque dur
    Donc merci de l’avoir rendu public

    • Ces temps-ci, j’ai commencé à utiliser Twitter comme un blog à faible coût
      Après avoir passé une journée sur ce genre de travail, je n’ai généralement plus l’énergie d’écrire réellement un billet de blog, et c’est frustrant. En revanche, rédiger un court fil Twitter reste le plus souvent faisable

  • Je suis vraiment ravi de voir ce résultat. kNN + tâche de classification + classification fondée sur une similarité purement textuelle est une combinaison où les résultats peuvent facilement s’empiler dans le bon sens
    Les réactions qui se réjouissent aux dépens de cet article comprennent mal à quel point l’élément de langage naturel est central dans les embeddings. Les expressions qui partagent des mots se classent bien et se compressent bien avec GZIP ; on peut donc utiliser GZIP comme classificateur de substitution
    Le miracle de BERT ou des embeddings, c’est qu’ils n’ont pas besoin de partager les mêmes mots. Par exemple, « what is my safe passcode? » correspond fortement à « my lockbox pin is 1234 », mais pas à « my jewelry is stored safely in the safe »
    C’est aussi important avec les LLM. Beaucoup de gens utilisent des embeddings pour la similarité textuelle, alors qu’en réalité il faut utiliser des modèles SBERT entraînés pour que les questions soient corrélées avec les documents qui contiennent leurs réponses
    Tout le terrier du lapin est ici : https://www.sbert.net/
    Article précédent : Should you use OpenAI's embeddings? Probably not, and here's why. https://iamnotarobot.substack.com/p/should-you-use-openais-e...
    Discussion HN : https://news.ycombinator.com/item?id=35377935

    • Pour être juste, la tâche d’origine avait été choisie délibérément là où une approche comme kNN + compression avait des chances de bien fonctionner, c’est-à-dire dans un contexte hors domaine + faibles ressources
      Dans ces conditions, les entrées d’apprentissage sont si rares qu’un modèle avec beaucoup de paramètres peut avoir du mal à apprendre de bons embeddings
      Dans un cadre classique de classification sur de grands volumes de données dans le domaine, une méthode non paramétrique comme la compression n’a aucune chance de battre des représentations apprises

  • Il n’était pas clair pourquoi les auteurs avaient choisi kNN comme classificateur. S’ils avaient construit une matrice de distances, ils auraient pu transformer la matrice en facteurs avec un positionnement multidimensionnel, puis utiliser un algorithme à base d’arbres comme xgboost ; cela aurait probablement exploité davantage d’information que kNN et donné de bien meilleurs résultats
    Ils auraient aussi pu utiliser l’algorithme de compression PAQ, bien meilleur que les compresseurs de la famille LZ. Ces choix auraient pu améliorer fortement les résultats et mener à la conclusion initiale
    Ce que j’ai apprécié dans cet article, c’est l’abstraction faite de l’algorithme de compression, qui pousse à réfléchir à ce que l’on peut faire d’autre avec la compression à partir de la relation p(x) ~ K^(-|x|). Ici, K est la taille de l’alphabet, |x| la longueur de la chaîne x, en supposant un codage optimal
    Par exemple, cela m’a fait penser qu’on pourrait faire de la classification traditionnelle en regroupant les facteurs de chaque réponse dans des documents séparés, puis en déterminant la classe en trouvant, comme dans l’article, le document qui compresse le mieux l’échantillon suivant. Une forme de classification supervisée utilisant un algorithme de compression
    Plus le compresseur se rapproche du code optimal pour ce jeu de données, mieux cela devrait fonctionner
    Une approche de prédiction de séquences serait tout aussi simple à implémenter
    C’était une agréable surprise

  • Pouvez-vous expliquer comment un algorithme de compression peut battre un LLM ? On dirait qu’on compare un cheval à un graffiti pour dire que le cheval est meilleur
    J’imagine que la réponse se trouve quelque part, mais je ne suis pas familier avec l’IA et je n’arrive pas du tout à comprendre

    • En général, compression = modèle + codage entropique
      Le rôle du modèle est de prédire ce qui vient ensuite, et celui du codeur entropique est d’encoder l’écart entre la prédiction et la valeur suivante réelle, en faisant en sorte que les résultats les plus probables utilisent le moins de bits possible
      Plus le modèle est précis, plus l’écart entre la réalité et la prédiction est faible, et moins le codeur entropique a besoin de bits, ce qui améliore la compression
      Un algorithme de compression simple possède un modèle simple, du type « si j’ai vu le même octet 10 fois, il y a de fortes chances que le 11e soit identique ». Mais un LLM peut aussi servir de modèle, puisque compléter un texte avec les mots les plus plausibles est précisément ce que fait un LLM
      Ici, ils ont fait l’inverse. Au lieu d’utiliser un modèle pour la compression, ils ont utilisé, avec quelques astuces, un algorithme de compression comme s’il s’agissait d’un modèle. L’idée est de considérer comme résultat le plus probable celui que l’algorithme de compression encode avec le moins de bits
      Les auteurs de l’article original ont montré que, sur certaines tâches, le modèle simple qu’on peut extraire de gzip bat un LLM bien plus complexe
    • Un modèle de langage estime la probabilité P(w_1, ..., w_n) d’une suite de mots, ou de façon équivalente P(mot | contexte)
      En compression, il faut attribuer des codes plus courts aux suites de mots les plus probables, il existe donc un lien direct. Une méthode bien connue pour construire ces codes à partir des probabilités est le codage de Huffman
      Cela vaut aussi bien pour un modèle de langage statistique fondé sur les fréquences des mots que pour un LLM utilisé afin d’estimer les probabilités. Plus le modèle de langage est bon, c’est-à-dire plus sa perplexité est faible, plus le résultat compressé est court
      Inversement, on peut aussi dire qu’un algorithme de compression définit implicitement un modèle de langage via la longueur des codes. Par exemple, il suppose en quelque sorte que les chaînes de caractères répétées sont plus probables que du bruit aléatoire
    • L’intuition derrière gzip est la suivante
      Si l’on compresse ABC, on obtient X octets. Si l’on compresse ensuite ABCABC, on n’obtient pas 2X octets. Plus les deux chaînes concaténées se ressemblent, moins il faut d’octets
      ABCABD sera plus gros que ABCABC, mais probablement plus petit que ABCXYZ
      BERT est un très petit LLM selon les standards actuels, et on sait aussi qu’il est moins performant que les modèles à plusieurs milliards de paramètres que l’on rencontre souvent aujourd’hui
    • La compression est équivalente à l’intelligence
      https://mattmahoney.net/dc/rationale.html
    • C’est une tâche très limitée. On prend un document et on le classe, par exemple, dans l’une d’une dizaine de catégories
      Des méthodes consistant à détecter certains mots peuvent aussi assez bien fonctionner selon les cas. Dans ce qui se compresse bien, on trouve souvent des sous-chaînes communes

  • Si c’est vrai, j’aimerais voir comment les gens qui ont tenu de grands discours à propos de cet article vont maintenant effacer discrètement leurs traces
    Je pense en particulier aux influenceurs LinkedIn et Twitter
    Si ce n’est pas vrai, j’aurai l’air idiot, mais je n’ai fait que parcourir l’article en diagonale

  • Gzip comme classifieur est étonnamment bon, et devrait servir de baseline pour les réseaux de neurones

  • Au passage, le blog semble être resté bloqué en 2022
    La date de l’article est indiquée comme étant le 17 juillet 2022

    • Merci. Ce sera bientôt corrigé. Voilà ce qui arrive quand on écrit les dates à la main...