- Proposition d’une méthode non paramétrique de classification de texte combinant un compresseur simple comme gzip et un classificateur des k plus proches voisins (kNN)
- Sans aucun paramètre d’entraînement, tout en restant légère et généraliste, avec un coût de calcul inférieur à celui des DNN
- Par rapport aux méthodes de deep learning sans préentraînement, obtient des résultats compétitifs sur 6 jeux de données in-distribution
- Sur l’ensemble des 5 jeux de données OOD (out-of-distribution), dont 4 en langues à faibles ressources, surpasse BERT
- Affiche aussi d’excellentes performances dans des contextes few-shot, où le manque de données annotées rend l’entraînement des DNN difficile
Contexte et problématique
- Les DNN sont largement utilisés pour la classification de texte grâce à leur forte précision
- Mais ils nécessitent des millions de paramètres et de grandes quantités de données annotées, ce qui entraîne un coût de calcul élevé
- En conséquence, leur utilisation, leur optimisation et leur transfert vers des situations OOD (out-of-distribution) deviennent des tâches coûteuses en pratique
Méthode proposée
- Présentation d’une méthode non paramétrique simple, légère et généraliste comme alternative aux DNN
- Architecture combinant un compresseur simple comme gzip et un classificateur des k plus proches voisins
- Sa caractéristique essentielle est de ne comporter aucun paramètre d’entraînement
Résultats expérimentaux
- Sur 6 jeux de données in-distribution, performances à un niveau compétitif face aux méthodes de deep learning sans préentraînement
- Sur l’ensemble des 5 jeux de données OOD, dont 4 en langues à faibles ressources, surpasse BERT
- Montre aussi des atouts en contexte few-shot, lorsque les données annotées sont trop rares pour entraîner efficacement un DNN
1 commentaires
Avis sur Hacker News
Lien direct vers l’article : https://aclanthology.org/2023.findings-acl.426.pdf
Intuitivement, l’idée centrale est que, étant donnés les documents x1, x2 et un nouveau document x, si les régularités statistiques de x sont plus proches de celles de x1 que de celles de x2, alors on obtient
len(compress(cat(x1,x))) - len(compress(x)) < len(compress(cat(x2,x))) - len(compress(x)). Ici,catsignifie concaténation, etcompressest un compresseur comme gzipLittéralement,
len(compress(cat(x1,x))) - len(compress(x))est le nombre d’octets supplémentaires nécessaires pour compresser les régularités statistiques de x1 étant données celles de x. Plus x1 et x se ressemblent, moins il faut d’octets supplémentaires pour compressercat(x1,x)par rapport à la compression de x seulLes auteurs appliquent k plus proches voisins (kNN) aux documents compressés à l’aide d’une fonction de distance fondée sur cette idée, appelée distance de compression normalisée (NCD). Ils abordent aussi les liens entre NCD et information, entropie de Shannon et complexité de Kolmogorov
Étonnamment, cette méthode simple et intuitive surpasse BERT dans plusieurs tâches de classification zero-shot. Cela ne signifie toutefois pas forcément qu’elle batte des Transformers plus grands et plus récents
L’idée serait de comparer la taille compressée selon que le document est utilisé ou non comme dictionnaire de compression. zstd offre un taux de compression bien supérieur à gzip, au moins aux niveaux 20+, donc si ce qui marche avec gzip vient d’une approximation de la complexité de Kolmogorov, cela pourrait fonctionner encore mieux
Si x1 est en anglais et que x est une traduction en hébreu du même document, j’imagine qu’un LLM ferait mieux
J’ai récemment travaillé avec des images et généré des sorties JPEG ; même à partir des mêmes pixels de base, on peut obtenir des images très variées. C’est intéressant de voir que plus une image est bruitée et proche de l’aléatoire, plus le fichier JPG est gros, tandis que plus elle ressemble à une photo, plus le JPG est petit
Si l’équivalence entre IA et compression vous intéresse, regardez le Hutter Prize :) http://prize.hutter1.net/
Le Large Text Compression Benchmark vaut aussi le détour http://mattmahoney.net/dc/text.html — le meilleur compresseur actuel au monde est un réseau neuronal de Fabrice Bellard, célèbre créateur de ffmpeg et QEMU
J’aime aussi beaucoup le style texte uniquement approprié de ces pages
Comme ils ajustent le codage arithmétique (https://en.wikipedia.org/wiki/Arithmetic_coding) en fonction du contexte de l’octet/bit à prédire, plus la suite est prédite précisément, plus l’encodage devient efficace. La tâche elle-même ressemble beaucoup à celle d’un Transformer comme GPT
Une prédiction parfaite ne réduit pas l’intervalle arithmétique, donc le coût de stockage supplémentaire est presque nul et, par conséquent, aucun bit n’est stocké. Mais pour un benchmark équitable, il faut aussi comptabiliser la taille du décompresseur
C’est une idée assez ancienne ; voir [1,2]. Elle est ancienne, mais reste très utile, comme le perceptron
[1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications
[2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
Une théorie ressemble à une histoire qui explique beaucoup de choses avec les mêmes « personnages ». Ici, les personnages sont plutôt des concepts ; les atomes, par exemple, correspondent bien à cela
Je voudrais souligner que cette méthode n’est plus forte que pour les actualités
Sur Yahoo Questions, elle n’atteint pas les meilleures performances. Les articles d’actualité sont écrits de manière similaire et il arrive que certaines parties soient copiées, il n’est donc pas déraisonnable de penser qu’ils partagent beaucoup de mots
Yahoo Questions est un forum, donc la variation lexicale y est plus importante, mais il existe des similarités sémantiques entre les mots
Autrement dit, gzip est puissant quand beaucoup de mots se recoupent (la taille augmente peu lors de la compression gzip), tandis que quand la similarité sémantique compte, les DNN gagnent toujours
Les résultats sont intéressants, mais à mon avis pas autant qu’ils en ont l’air
Il faut vraiment considérer comme très important le fait que ce résultat vienne de données hors distribution. Par exemple, des actualités dans des langues comme le « kinyarwanda, le kirundi, le pinyin »
Dans un cadre plus général, BERT gagne toujours très largement
C’est intéressant qu’une méthode aussi simple puisse être très efficace, mais il ne faut pas la survendre
Mais quand on regarde les conditions citées, c’est au contraire assez intuitif. Que signifie classer des textes dans une langue que l’on ne connaît absolument pas ? Si on me demande de classer un texte en kirundi, je n’en comprends pas du tout le sens ; le mieux que je puisse faire est de chercher les fréquences de mots ou de séquences de caractères et de regrouper les textes qui ont des empreintes de fréquence similaires
On ne comprend toujours pas le sens réel, mais on peut faire mieux que le hasard, et c’est effectivement ce qui se passe. La bonne nouvelle, c’est que c’est exactement ce que fait gzip+kNN : c’est son métier, sa raison d’être
Il n’y a pas grand-chose à gagner à essayer de lire et comprendre ce texte, ou à prédire le caractère suivant. Une personne normale, ne connaissant pas la langue, n’essaierait même pas. Malheureusement, c’est précisément ce que fait BERT. Parce que c’est la seule chose qu’il sache faire. Cela dit, il faut reconnaître qu’il en tire plus d’utilité qu’un humain ordinaire, et probablement même qu’un humain non ordinaire
En fait, c’est très malin et intuitif
Si l’on concatène deux morceaux de texte similaires, ils se compresseront mieux que si l’on concatène deux morceaux de texte différents
Cela ressemble moins à une victoire de cette méthode qu’à un signal négatif pour la similarité fondée sur le deep learning
Avec l’engouement autour des LLM, ils sont certes impressionnants, mais beaucoup de gens semblent supposer qu’il y a eu des progrès comparables aussi dans les couches d’embedding destinées à la simple similarité textuelle
D’où toute la frénésie autour des bases de données d’embeddings, mais à mes yeux il y a très peu de preuves pour l’étayer
Le lien devrait pointer vers le PDF de l’article : https://aclanthology.org/2023.findings-acl.426.pdf
Un algorithme de compression, c’est une économie/compression d’espace, c’est-à-dire de bits et d’octets. Les modèles de machine learning, en particulier les modèles génératifs, économisent/compressent les représentations et la pensée humaines
La classification de texte est une forme de compression au-dessus des représentations humaines. Existe-t-il une propriété fondamentale du langage humain et des données qui expliquerait ce qui réussit le mieux dans une tâche de machine learning donnée ?
Si un jour une telle théorie prend forme, il ne serait peut-être pas surprenant que l’encodage de bits/octets compressés et les représentations humaines compressées soient étroitement liés dans un certain espace, et donc connectés d’une manière ou d’une autre. En pratique, une telle théorie — par exemple fondée sur l’entropie ou sur la physique — pourrait aider à choisir entre un algorithme de compression et un modèle de machine learning pour certains types de compression de représentations humaines
Du point de vue des données, quels seraient les exemples négatifs difficiles qui rendent ce genre d’algorithme mauvais ? Pour l’instant, on ne peut peut-être qu’approcher cette théorie sous l’angle des différents types de données textuelles humaines. Par exemple, prédire des mélanges avec un modèle thématique statistique fonctionne bien sur des textes académiques, mais rencontre des difficultés avec les textes d’Internet
Y a-t-il des gens qui travaillent sur ce genre de théorie, en dehors de Wolfram Physics ?
https://www.newyorker.com/tech/annals-of-technology/chatgpt-...
C’est tout à fait logique. La compression relève de la « compréhension », c’est-à-dire de la représentation de l’entrée d’une manière qui permette de la reconnaître et de l’étiqueter
Si les bits reconnus deviennent plus grands que l’étiquette, tada, on a de la compression. Il n’est pas surprenant que gzip puisse faire mieux qu’un DNN sur cette tâche
Je dis sous-ensemble parce que la compréhension est plus générale. Un algorithme de compression donné peut très bien fonctionner sur des nombres à virgule flottante. À l’inverse, le cerveau et les réseaux de neurones artificiels peuvent peut-être compresser n’importe quel motif d’entrée, même si leurs performances sont moins bonnes
Je ne vois pas comment gzip peut gérer un mot comme “not”, qui inverse le sens de toute une phrase
Quelqu’un comprend ?