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é par les chercheurs à 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 à été choisi, il s'agit de BERT. Il à été crée par Google et à révolutionné l'IA en 2018, le point fort de ce réseau de neurone est qu'il est capable de comprendre le sens des mots en fonction de leur contexte. BERT est un modèle pré entrainer par Google pendant des jours et des jours sur des millions de données, dans les tests qui suivent lorsque l'on parlera de données 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.


Cette algorithme fusionne 2 grands classique 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 connait la catégorie de chaque fichier, j’en ai 10 qui parle d’astronomie et 10 qui parle des voitures, on vas appeler cela notre BDD. Et on a découvert après coup un 21^ième fichier s’est perdu on ne sait pas à quelle catégorie il appartient. On vas donc l’appeler fichier mystère.
Maintenant que l’on a tous ce qu’il nous faut on peut commencer, pour que ce soit plus compréhensible on vas découper cette algorithme en 5 étapes.

• Etape 1: Tous les textes de notre base de données n’ont pas la même tailles on vas 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ée que l’on appelle C(y).
• Etape 2: Puis on compresse le fichier que l’on cherche a tester avec astro_1.txt et on récupère aussi la taille obtenu . On peut tout de suite remarquer que lors de la compression si mon fichier mystère est de la catégorie astronomie il vas mieux se compresser avec astro_1.txt plutôt qu’avec voiture_1.txt car il a plus de mot en commun et donc la taille xy sera plus petite.
• Etape 3: Etant donné que tous les textes n’ont pas le même nombre mot, on vas essayer de normaliser le résultat pour qu’il soit compris entre 0 et 1 peu importe le nombre de mot 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édait beaucoup de mot semblable. Et si au contraire le résultat est proche de 1 cela signifie que les textes n’ont que très peu de mot en commun ce qui a rendu la compression très peu efficace.
• Etape 4: J’ajoute ce score a 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’aurais donc un tableau avec 20 scores.

Tableau associatif trié de mes 20 scores



• Etape 5: Et pour finir je trie mon tableau par ordre croissant et observe la catégorie des k premiers fichiers. Si on choisit un $k=5$ je regarde la catégorie de mes 5 premiers fichier et et on voit ci-contre que l'on a 3 fichiers type astronomie et 2 fichiers voiture 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 comparaison c’est le modèle BERT qui à été choisi.
1^er test: On ne donne aucune donnée a BERT il est donc laissé en l’état sans spécialisation, pour cela on leur demande de classer des textes sur des nouvelles langue, comme on peut s’en douter la méthode par compression l’emporte haut la main.
2^ième test: Le point surprenant et aussi appelé “le miracle du Few Shot” par les chercheurs est le cas ou on ne donne que très peu de donnée, évidemment BERT obtient des scores assez faible mais la méthode de compression gzip réussit a 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é syntaxiquement, c’est donc 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 ces limites, on a effectué ce test sur une BDD appelé Yahoo Answers, cette BDD est un peu particulière car elle regroupe différents Argos et contient même des fautes d’orthographes, de plus elle est constituée de plus d’1,5 millions de mot différents et c’est exactement le cas où BERT excelle, il à été crée pour ces conditions. Et il le montre car il obtient un score de 76% et Gzip 63%.

• • • • • • • • YAHOO ANSWERS EXPLIQUÉ

Note: Yahoo Answers est une Base de données formée à partir d'ancienne discussion de forum elle est donc constitué de nombreux Argos et surtout beaucoup de fautes.
Pour ce qui est du temps d’exécution chacun à ces avantages, BERT prends beaucoup de temps pour s’entrainer et apprendre, et ensuite il nous suffit de le “spécialiser” dans les catégories que l’on veut lui faire classer, un entrainement de 5 ou 6h, alors que Gzip n’a pas besoin d’entrainement. Pour la classification en elle-même Bert ressort le résultat quasi instantanément car il a toute appris par cœur il est comme un traducteur expérimenté alors que Gzip est comme un apprenti qui doit rechercher dans son dictionnaire, a chaque mot il prends donc un peu plus de temps. Son temps de classification varie en fonction du nombre de catégorie car je le rappelle, il faut compresser le fichier mystère avec tous les fichier de toutes les catégorie donc plus il y en a plus c’est long contrairement à Bert pour qui le nombre de catégorie n’influence pas du tout sont 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 presque identiques) et 1 (compressions 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."

Notre test

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.

Comparaison avec les test des chercheurs :

Ilan ...

Conclusion :

Ilan ...

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