Classification de textes grâce à la compression

Introduction:

L'objectif de notre projet est de créer et d'étudier un algorithme de classification de texte grâce à la compression.
Avec la compression, qui est un procédé basé sur des statistiques, on peut théoriquement reconnaître deux textes comportant les mêmes mots et phrases grâce à leurs compressions qui seront similaires.
En se basant sur ce concept, un groupe de chercheurs a créé un algorithme de 12 lignes pouvant faire cette classification.
Notre objectif va donc être de le recréer et de l'étudier pour le comparer à des algorithmes basés sur le Learning.

Les réseaux de neurones profonds :

Pour bien comprendre ce dont nous allons parler ici, il faut comprendre ce que sont les réseaux de neurones profonds ou le Deep learning en anglais. Cette méthode a redessiné les capacités de l’intelligence artificielle en exploitant des architectures profondes inspirées du cerveau humain. Ces modèles apprennent à extraire des représentations depuis des données complexes, et ils alimentent aujourd’hui de nombreux services automatisés. La méthode de classification proposée par les chercheurs a pour but de concurrencer ces réseaux de neurones et étant donné qu'il existe beaucoup de ces modèles, c'est un des plus puissants qui a été choisi, il s'agit de BERT. Il a été créé par Google et a révolutionné l'IA en 2018, le point fort de ce réseau de neurones est qu'il est capable de comprendre le sens des mots en fonction de leur contexte. BERT est un modèle pré entraîné par Google pendant des jours et des jours sur des millions de données, dans les tests qui suivent lorsque l'on parlera de donner, il s'agira pour BERT d'une spécialisation sur les catégories de notre BDD (Base de données).

Fonctionnement général :

Le code des chercheurs

Voici le code proposé par les chercheurs qui ont découvert cette méthode, 11 lignes en Python.


Cet algorithme fusionne 2 grands classiques du numérique : la compression et l’algorithme des k plus proches voisins.






Voici un exemple de classification d’un texte grâce à cette méthode…
Imaginons que l’on possède 20 fichiers et que l’on connaît la catégorie de chaque fichier. J’en ai 10 qui parlent d’astronomie et 10 qui parlent de voitures, on va appeler cela notre BDD. Et on a découvert après coup qu'un 21^ième fichier s’est perdu, on ne sait pas à quelle catégorie il appartient. On va donc l’appeler fichier mystère.
Maintenant que l’on a tout ce qu’il nous faut, on peut commencer. Pour que ce soit plus compréhensible, on va découper cet algorithme en 5 étapes.

• Étape 1 : Tous les textes de notre base de données n’ont pas la même taille, on va donc les compresser et récupérer leur taille. Pour commencer, on compresse astro_1.txt (le premier fichier de notre BDD) et on récupère sa taille que l’on appelle C(x). On récupère également la taille de notre fichier mystère compressé que l’on appelle C(y).
• Étape 2 : Puis on compresse le fichier que l’on cherche à tester avec astro_1.txt et on récupère aussi la taille obtenue. On peut tout de suite remarquer que lors de la compression, si mon fichier mystère est de la catégorie astronomie, il va mieux se compresser avec astro_1.txt plutôt qu’avec voiture_1.txt car il a plus de mots en commun et donc la taille xy sera plus petite.
• Étape 3 : Étant donné que tous les textes n’ont pas le même nombre de mots, on va essayer de normaliser le résultat pour qu’il soit compris entre 0 et 1, peu importe le nombre de mots de chaque fichier. Et pour cela, on effectue un calcul très simple (Normalized Compression Distance), $NCD={\frac {C(xy)-\min\{C(x),C(y)\}}{\max\{C(x),C(y)\}}}$ Et on obtient $0<NCD<1$. Si le résultat est proche de 0, cela veut dire que la compression était très efficace, donc que les fichiers possédaient beaucoup de mots semblables. Et si au contraire le résultat est proche de 1, cela signifie que les textes n’ont que très peu de mots en commun, ce qui a rendu la compression très peu efficace.
• Étape 4 : J’ajoute ce score à un tableau associatif avec pour chaque score la catégorie de mon fichier et j’effectue cette action 20 fois car je vais comparer mon 21^ième fichier avec les 19 autres de ma base de données. J’aurai donc un tableau avec 20 scores.

Tableau associatif trié de mes 20 scores



• Étape 5 : Et pour finir, je trie mon tableau par ordre croissant et j'observe la catégorie des k premiers fichiers. Si on choisit un $k=5$, je regarde la catégorie de mes 5 premiers fichiers et on voit ci-contre que l'on a 3 fichiers type astronomie et 2 fichiers voitures, alors j’en déduis que mon 21^ième fichier appartient à la catégorie astronomie.

Note : L'ordre n'est important que pour le choix des k premiers scores, une fois celui-ci fait, l'ordre n'est plus important.

Les résultats des chercheurs :

Pour effectuer les comparaisons, c’est le modèle BERT qui a été choisi.
1^er test : On ne donne aucune donnée à BERT, il est donc laissé en l’état sans spécialisation. Pour cela, on lui demande de classer des textes sur de nouvelles langues. Comme on peut s’en douter, la méthode par compression l’emporte haut la main.
2^ième test : Le point surprenant, aussi appelé “le miracle du Few Shot” par les chercheurs, est le cas où on ne donne que très peu de données. Évidemment, BERT obtient des scores assez faibles, mais la méthode de compression gzip réussit à largement dépasser le 1 chance sur 2 !

Comparaison sur des données standard

3^ième test : Si on effectue une comparaison sur des données standards avec des catégories très éloignées syntaxiquement, c’est le cas arrangeant pour la méthode de compression gzip qui parvient presque à égaler BERT. L’écart de réussite (ci-contre) est minuscule alors que la complexité technologique est radicalement différente.

4^ième test : La méthode gzip a aussi ses limites. On a effectué ce test sur une BDD appelée Yahoo Answers. Cette BDD est un peu particulière car elle regroupe différents argots et contient même des fautes d’orthographe. De plus, elle est constituée de plus d’1,5 million de mots différents et c’est exactement le cas où BERT excelle, il a été créé pour ces conditions. Et il le montre car il obtient un score de 76% et Gzip 63%.

Note : Yahoo Answers est une base de données formée à partir d'anciennes discussions de forums, elle est donc constituée de nombreux argots et surtout de beaucoup de fautes.
Pour ce qui est du temps d’exécution, chacun a ses avantages. BERT prend beaucoup de temps pour s’entraîner et apprendre, et ensuite il nous suffit de le “spécialiser” dans les catégories que l’on veut lui faire classer (un entraînement de 5 ou 6h), alors que Gzip n’a pas besoin d’entraînement. Pour la classification en elle-même, BERT ressort le résultat quasi instantanément car il a tout appris par cœur. Il est comme un traducteur expérimenté, alors que Gzip est comme un apprenti qui doit rechercher dans son dictionnaire : à chaque mot, il prend donc un peu plus de temps. Son temps de classification varie en fonction du nombre de catégories car, je le rappelle, il faut compresser le fichier mystère avec tous les fichiers de toutes les catégories. Donc plus il y en a, plus c’est long, contrairement à BERT pour qui le nombre de catégories n’influence pas du tout son temps de classification.

Temps d'exécution

Ce qu'on a utilisé

Python

Lors de notre projet, nous avons principalement utilisé un algorithme Python, mais nous y avons ajouté plusieurs bibliothèques Python avec une base de données de textes.

Les Bibliothèques Python

Dans notre algorithme, nous utilisons 2 bibliothèques Python qui sont essentielles et une 3ème bibliothèque qui a servi pour des tests spécifiques.

1 : Bibliothèque OS

Nous avons utilisé la bibliothèque OS pour accéder aux textes dans notre base de données, obtenir les chemins d'accès et ainsi rendre possible nos tests.

2 : Bibliothèque zlib

zlib a joué un rôle majeur dans notre algorithme car il s'agit d'une bibliothèque d'outils de compression qui nous a servi à compresser nos textes dans Python au format zlib (un format compressé par l'algorithme de compression deflate) .

3 : Bibliothèque random (Non essentielle)

Random nous avait servi à rendre les tests aléatoires et ainsi vérifier le taux moyen de réussite de notre algorithme. Ce dernier n'était donc pas indispensable pour son fonctionnement mais il était très intéressant lors de la phase de test.

La base de données

Pour obtenir une grande quantité de textes, nous avons utilisé la base de données 20news qui est structurée de la manière suivante :

- Un répertoire 20News avec à l'intérieur un répertoire data (dont le contenu sera utilisé comme des textes déjà classifiés) et un répertoire test (dont le contenu sera utilisé comme des textes à classifier).

- Dans les deux répertoires, nous trouvons les 20 mêmes répertoires qui sont des catégories de textes (par exemple le répertoire alt.atheism contenait uniquement des textes sur l'athéisme).

- Chaque répertoire de catégorie contenait plusieurs centaines de textes différents, sachant que les textes dans data et test étaient tous différents."

Paramètre fonction

Dans notre code, tout est contrôlé par la fonction classification qui va appeler les 5 fonctions auxiliaires. Elle prend 7 paramètres en entrée :

Ses 7 paramètres

Paramètre dossiers

Ce paramètre est une liste de chaînes de caractères qui sont des chemins d'accès vers les catégories de la partie "data" (les textes d'entraînement) dans 20News.

Paramètre test_folders

Ce paramètre est également une liste de chaînes de caractères qui sont des chemins d'accès, mais vers les catégories de test (les textes à évaluer) dans 20News.

Paramètre k

Il s'agit d'un entier qui va fixer le nombre de "k plus proches voisins" qu'on va étudier pour prendre la décision de classification.

Paramètre nbr_fich_training

Il s'agit d'un entier qui va fixer le nombre de textes déjà classifiés qui vont être utilisés comme base de référence.

Paramètre nbr_fich_test

Il s'agit également d'un entier, mais qui va fixer le nombre de textes à classifier qui vont être étudiés lors du test.

Paramètre coupe_entete

Initialisé à False par défaut, il s'agit d'un booléen qui va indiquer aux fonctions si l'en-tête des textes doit être retiré (True) ou non (False).

Paramètre aléatoire

Initialisé à False par défaut, il s'agit d'un booléen qui va indiquer aux fonctions si les textes doivent être sélectionnés dans un ordre aléatoire (True) ou non (False).

Le résultat renvoyé

Cette fonction va renvoyer le résultat de la fonction auxiliaire evaluer_classification, qui renvoie le taux de réussite global des classifications effectuées."

Structure du code

Nous avons utilisé 5 fonctions auxiliaires appelées par la fonction principale classification dans notre code Python, chacune réalisant une étape précise du procédé :

La fonction NCD

Cette fonction est le cœur du choix de classification.

Principe

Cette fonction calcule le NCD (Normalized Compression Distance), qui correspond à la ressemblance entre deux textes compressés. Elle prend 2 paramètres qui sont 2 chaînes de caractères (un texte X et un texte Y) non compressées. Elle va d'abord effectuer une compression de chacun des textes (pour obtenir une taille Cx1 et une taille Cx2), puis elle va concaténer les deux textes (X+Y) et compresser ce nouveau texte (pour obtenir une taille Cx). La fonction renverra ensuite le NCD : la taille de Cx moins la taille du plus petit fichier entre Cx1 et Cx2, le tout divisé par la taille du plus grand fichier entre Cx1 et Cx2.

Résultat renvoyé

Le résultat sera un flottant compris entre 0 (compressions et textes presque identiques) et 1 (compressions et textes très différentes).

La fonction preparer_training_data

Cette fonction est l'outil d'accès aux textes déjà classifiés dans 20News. Elle prend 4 paramètres :

Paramètre dossiers

C'est une liste qui contient les chemins d'accès vers les répertoires des catégories qu'on souhaite extraire dans 20News.

Paramètre nbr_fich_training

C'est un nombre entier qui représente le nombre de fichiers qu'on souhaite récupérer par catégorie.

Paramètre coupe_entete

Il s'agit d'un booléen qui va dire à la fonction de retirer les en-têtes des textes (s'il vaut True) ou de les conserver (s'il vaut False).

Paramètre aléatoire

C'est également un booléen qui va dire à la fonction de sélectionner les textes au hasard ou non. S'il vaut True, la sélection sera mélangée ; s'il vaut False, les premiers fichiers seront pris dans l'ordre.

Résultat renvoyé

Une liste de dictionnaires (tableaux associatifs) où chaque élément contient le texte du fichier (nommé content) et sa catégorie d'origine (nommée label).

La fonction preparer_test_files

Cette fonction a le même principe que preparer_training_data, mais elle va agir sur les textes non classifiés (la partie test de 20News). Elle prend 3 paramètres :

Paramètre test_folders

Ce paramètre est une liste contenant les chemins d'accès vers les répertoires de test dans 20News.

Paramètre nbr_fich_test

Il s'agit d'un nombre entier qui définit le nombre de textes désirés par dossier pour faire nos tests.

Paramètre aléatoire

C'est un booléen qui permet de sélectionner les fichiers de test de manière aléatoire (True) ou non (False).

Résultat renvoyé

Une liste (tableau) qui contient les chemins d'accès des fichiers de test.

La fonction ouvre_fich

Cette fonction va lire le contenu des fichiers de test. Elle prend 2 paramètres :

Paramètre fich1

C'est le chemin d'accès d'un fichier texte. La fonction va l'ouvrir et le transformer en chaîne de caractères.

Paramètre coupe_entete

C'est un booléen (initialisé à False par défaut) qui va enlever les en-têtes s'il vaut True et les garder s'il vaut False.

Résultat renvoyé

Une chaîne de caractères qui représente le contenu texte du fichier.

La fonction evaluer_classification

Cette fonction va calculer le taux de réussite de la classification en utilisant un compteur de fichiers testés et un compteur de réussites. Elle prend 4 paramètres :

Paramètre test_files_paths

C'est la liste des chemins des fichiers de test créée par preparer_test_files.

Paramètre training_data

C'est la liste de dictionnaires de textes déjà classifiés créée par preparer_training_data.

Paramètre k

C'est un entier qui va servir à déterminer le nombre de "k plus proches voisins" qu'on va étudier pour prendre la décision finale.

Paramètre coupe_entete

C'est le booléen gérant les en-têtes, qui sera passé en paramètre à la fonction ouvre_fich.

Résultat renvoyé

Un nombre flottant représentant le pourcentage de réussite, calculé en divisant le compteur de réussites par le nombre total de tests, le tout multiplié par 100."

Nos tests

Après avoir fait plusieurs tests avec notre algorithme, nous avons pu observer et analyser des résultats.

Taux de réussite

Grâce à nos tests, nous avons pu observer un taux de réussite intéressant.

Un taux meilleur que le hasard

Nos tests ont montré des résultats atteignant jusqu'à 96% de réussite sur 100 textes de test, 300 textes déjà classifiés par catégorie (donc 600 pour une classification à 2 catégories) et un k = 13. Il était très rare que le taux de réussite soit inférieur à 50% (cela a dû arriver entre 5 et 10 fois sur 190 tests. En considérant un succès quand le taux de réussite est supérieur ou égal à 50%, on obtient un succès global entre 94,74% et 97,37%). L'algorithme a donc un bon potentiel de classification en bonnes conditions.

Un taux très variable

Comme dit précédemment, notre algorithme a pu classifier 100 textes avec un taux de réussite de 96%, mais il a également été parfois en échec avec un taux de réussite inférieur à 50%. Lors de nos tests, nous utilisions des textes basés sur plusieurs catégories et nous avons étudié ce taux de réussite sur ces différentes catégories. On a pu observer que sur des catégories avec un thème semblable, on obtenait des taux de classification moins bons (environ 45% de réussite pour la catégorie religion musulmane quand elle est classifiée avec la catégorie athéisme). À l'inverse, deux catégories très différentes permettent une classification bien meilleure (par exemple 96% de réussite avec athéisme face à la catégorie électronique). Donc, selon les catégories utilisées, le taux de réussite va beaucoup varier ; il s'agit d'une limite de notre algorithme.

Faits intéressants

Nous avons pu également découvrir plusieurs faits intéressants sur notre algorithme.

Une mauvaise classification sur les petits textes

Lors de nos tests, nous avons découvert des résultats qui s'inversaient selon l'ordre de classification. Par exemple, si notre tableau de textes déjà classifiés contenait deux catégories A et B, et que le tableau contenait d'abord la catégorie A puis la B, alors l'algorithme classifiait souvent le texte de test en catégorie A (et cela s'inversait si on inversait le tableau). Cela arrivait car les petits textes se compressaient de la même manière et créaient beaucoup d'égalités au niveau du NCD. Comme le tri de Python est stable (il conserve l'ordre initial en cas d'égalité), les NCD égaux étaient triés par ordre d'apparition. Avec un k=13, si les 13 premiers textes égaux étaient de la catégorie A, l'algorithme choisissait A. La solution à ce problème a été de supprimer les petits textes de 20News pour rendre nos statistiques plus fiables.

Une classification limitée par la qualité du texte

Un de nos tests a été réalisé sur une autre base de données avec le même nombre de textes donnés en paramètre. Nous avons vu que notre algorithme a baissé en performance, descendant à un taux de réussite moyen de 63%, là où des algorithmes de Machine Learning (qui avaient avant un taux presque similaire) atteignaient maintenant 76% de réussite. La raison était la suivante : les textes étaient mal écrits avec des fautes d'orthographe notamment. Comme notre algorithme se base sur la ressemblance (les caractères) entre deux textes, il perdait en efficacité (par exemple, le mot bateau et bato ne vont pas se compresser de la même manière, ce qui va influencer les résultats). On a donc un algorithme efficace en condition optimale mais qui va être beaucoup influencé par l'orthographe.

Conclusion sur nos tests

Notre algorithme a donc un bon potentiel avec un taux de réussite très correct, mais il est facilement influençable avec des résultats très variables selon son utilisation.

Les grands avantages de cette compression :

Le principal objectif de cette classification est d’offrir une alternative à la classification “classique”, celle qui utilise des réseaux de neurones profonds. La classification par compression possède 4 grands avantages :

• Le premier est qu’elle permet de remplacer les puissants processeurs graphiques qui sont utilisés par les méthodes classiques par de simples algorithmes de compression, ce qui est beaucoup moins coûteux en ressources.
• De plus cette classification permet non pas de réduire les phases d’entraînement mais de complètement les supprimer. Ce qui rend ce système beaucoup plus rapide, surtout lorsque l’on doit changer des catégories.
• Puisque l’apprentissage n’est plus un impératif cette classification peut s’adapter sans problème à toutes les langues, même celles qui nous sont inconnues si bien entendu on possède un minimum de données dessus.
• Et donc le dernier avantage est son besoin très faible de données, en effet cette classification peut rester très efficace même si l’on ne possède qu’une dizaine de textes de seulement une ligne chacun !!
Au final le but est de prouver qu’avec un simple algorithme mathématique on peut égaler voire surpasser une complexité technologique telle que les réseaux de neurones profonds.

Conclusion :

Pour conclure, selon les chercheurs, la méthode de classification par compression reste une excellente solution, surtout si l’on veut privilégier le temps d’exécution (pas d’attente pour l’entraînement) ou lorsque l’on possède très peu de données. C’est une méthode idéale pour un utilisateur particulier ou un petit projet qui ne possède pas de grandes ressources, car je le rappelle : elle ne nécessite que 15 lignes de code Python et un simple ordinateur.
Cependant, il faut être réaliste : si l’on est dans une grande entreprise qui traite des millions de données identiques chaque jour, les réseaux de neurones profonds (comme BERT) seront plus performants et plus rapides sur le long terme car ils connaissent leur sujet « par cœur ».


Notre avis

Nous sommes un peu plus critiques que les chercheurs. Comme nous l’avons vu, les résultats n’atteignent pas toujours les 90 % de réussite. En réalité, ces scores impressionnants ne s'obtiennent que lorsque l’on choisit les « bonnes catégories » : celles qui ne se ressemblent pas du tout et qui n’ont presque aucun mot en commun (comme les composants d’un ordinateur et les outils de jardin). Dès que le vocabulaire devient trop varié ou « bruyant » (comme sur Yahoo Answers), la compression montre ses limites face à l’IA classique.

Notre algorithme

Voici notre algorithme que nous avons utilisé lors de ce projet :


Notre Algorithme

Le lien mène vers un fichier avec des soucis d'encodage sur le web mais téléchargé en local l'encodage redevient normal