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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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 compression l’emporte haut la main.
2^ième test: Le point surprenant et aussi appelé “le miracle du Few Shot” par les chercheurs et 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 !
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 est minuscule alors que la complexité technologique est radicalement différente.

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.

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 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. 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

Martin ...

Comparaison avec les test des chercheurs :

Ilan ...

Conclusion :

Ilan ...