Algorithme de représentation des résultats en arbre et comparaison

Algorithme de représentation des résultats en arbre et comparaison

Introduction à l’algorithme en arbre 

Un algorithme de classification des séquences d’information est nécessaire afin d’identifier les facultés d’un individu à travers un vidéo. Un des algorithmes intéressants est l’algorithme en arbre. Cet algorithme a été initialement développé lors de mes cours du baccalauréat pour l’identification du sujet d’un texte, mais n’ont pas été publiés en dehors des travaux de ces cours. Une brève publication de cet algorithme sera alors incluse dans ce mémoire pour l’introduire avant de l’appliquer au sujet de cette recherche. Elle est basée sur la notion des N-Gram utilisés par plusieurs auteurs, donc principalement Pauls, Kleins [23] et Cavnar [18]. Cet algorithme, indépendant de la langue, est alors utilisable dans autre chose que des langues telles que des signaux. Ce sera l’analyse par signaux qui sera utilisée pour l’appliquer à la détection automatique des facultés affaiblies. Un signal généré par un comportement humain, soit le nystagmus et tout mouvements de l’œil devraient se comporter de manière naturelle, soit de manière semblable à une langue écrite.

Dans la littérature, de multiples textes existent et pourraient bénéficier d’une indexation ou d’un classement. Il existe de multiples algorithmes pour identifier le sujet d’un texte, mais ces algorithmes sont basés sur des critères linguistiques et sont difficiles à implémenter. Les méthodes statistiques actuelles ne permettent pas d’obtenir de bons résultats rapidement, car les filtres de mots ne peuvent pas s’appliquer au contexte. Il faut donc penser à un algorithme qui s’appliquera sur les suites de mots et non uniquement aux mots. Cependant les suites de mots dépendent des conjugaisons de verbes. Il faudra alors passer un filtre de prétraitement pour mettre les verbes à l’infinitif et tous les noms et adjectif au masculin singulier. L’uniformité est la seule option pour réussir une bonne détection du sujet d’un texte. Ensuite, nous enlèverons les mots communs (ex: le, la, de, du, …). Ces mots peuvent être identifiés par un humain ou par analyse statistique de texte de multiples sujets, cette étape est optionnelle. Si tout le jeu de donnée provient d’un même sujet, il pourrait être difficile de distinguer les mots communs de la langue de ceux du sujet (ex en santé le mot santé). L’algorithme analyse le texte en créant un arbre des suites de mots avec plusieurs têtes d’écriture. Cet algorithme est basé sur la notion de N-Gram, mais en ayant plusieurs avantages comparés à ceux-ci.

Lors de la recherche en traitement de langue naturelle, personne n’arrive à un consensus sur quelle information cibler pour extraire cette information. Certains avancent que le mot seul est suffisant, mais ces algorithmes ont fait leurs preuves et ne sont pas très précis [21]. D’autres affirment qu’une fenêtre autour du mot doit être utilisée pour identifier sa sémantique, cependant encore une fois les preuves ont été faites que ces algorithmes ne donnaient pas les meilleurs résultats [24]. La dernière option est une phrase complète, qui véhicule beaucoup d’information et qui donne actuellement les meilleurs résultats [24]. Se basant sur le principe des suites de mots, nous allons identifier les suites à l’intérieur d’une phrase pour ne pas à avoir la combinaison de toutes les fenêtres autour de notre mot comme inspiré par [17]. Nous créons un algorithme qui va extraire ces suites et les comparer pour obtenir un taux de similitude. Cet algorithme fonctionne en un passage sur le texte pouvant alors aussi s’appliquer aux textes non reproductibles tel que les informations qui viennent en temps réel et non d’un enregistrement.

Méthodologie (Les étapes) 

Analyse du texte et représentation en arbre
Nous explorerons le texte sous forme d’arbre à racine implicite. D’abord, nous plaçons une tête d’écriture à la racine implicite. À chaque mot lu, nous demandons aux têtes d’écritures d’écrire le mot, ensuite les têtes se déplacent sur le nouveau mot et une nouvelle tête est ajoutée à la racine implicite .

Pour contrer ce phénomène, il faudrait alors insérer des points de coupes qui seront expliqués plus loin dans le texte. Un point de coupe étant le fait d’éliminer toutes têtes pour n’en conserver qu’une nouvelle à la racine.

Ainsi, pour donner suite à la création de l’arbre sous cette méthode, il est possible de s’apercevoir que chaque branche, ou branche partielle représente un N-Gram  . Il a donc été possible en un seul passage et en limitant le nombre de comparaisons aux nœuds seulement plutôt que l’ensemble complet de construire l’ensemble des N-Gram de toutes les longueurs possibles. Il aurait été possible en connaissant une longueur désirée de N-Gram de couper les têtes d’écriture pour toutes les branches trop profondes. Ensuite il aurait été nécessaire de couper les branches trop courtes pour la longueur de N-Gram désirée.

Comparaison avec la version N-Gram brute
Nous avons précédemment vu que notre meilleur des cas a une complexité de l’ordre N et le pire d’ordre N²et que l’exploration brute est d’ordre N³ peu importe la phrase, cependant, nous n’avons pas considéré la différence fondamentale d’une comparaison, dans notre algorithme une comparaison étant faite sur un mot seulement d’une longueur de M lettres. Dans le cas de l’exploration brute, une comparaison se fait sur chaque mot de la suite, soit la longueur d’une phrase L maximale et 1 minimale (L/2) et M lettres par mot donne L/2+M pour chaque comparaison rendant l’algorithme brut beaucoup plus long pour une même comparaison. Un autre avantage de l’approche par arbre est que chaque mot n’est lu qu’une fois plutôt que de resegmenter le texte à chaque itération. Si la segmentation du texte est lourde, l’algorithme en arbre permet de la minimiser.

Apprentissage/Addition
L’apprentissage de sujet se fait un peu sur le même principe que l’exploration, d’abord, il faut explorer le texte et générer l’arbre, ensuite il faut savoir à quel sujet appartient le texte, il peut alors y avoir plusieurs catégories. Dans une base de sujets, on vérifie premièrement que le sujet existe, s’il existe on additionne les arbres pour former un arbre plus grand et on l’ajoute dans la banque de sujets, si le sujet n’existe pas on prend un arbre vide lors de l’addition.

L’addition d’arbres (A+B) se fait de manière B vers A, soit pour chaque nœud de B, s’il existe dans A on augmente un compteur, initialement à zéro étant associé à ce nœud, sinon on ajoute le nœud à A. L’on applique alors cette règle récursivement jusqu’à ce que l’arbre complet soit additionné et donne un résultat C.

Comparaison/Soustraction
La comparaison de sujets se fait par la soustraction d’arbre A vers B, pour chaque nœud de A, on additionne la valeur de son compteur au maximum de poids de l’arbre et on vérifie son existence dans B, si le nœud de A existe dans B, nous attribuons des poids selon la méthode choisie d’attribution de ces poids.  Cette comparaison est effectuée récursivement pour l’obtention du rapport entre le score obtenu et un score maximal. Au moment du calcul il est plus efficace de compter les poids perdus, soit les poids n’ayant pas de comparatif dans B, alors on obtient l’inverse du résultat souhaité à la fin . Soit un score de différence (Poids perdu sur poids maximum), un texte ayant moins de 30% de différence pourrait être considéré comme un même sujet, et un texte de moins de 10% peut être considérés très similaire, donc surement un extrait ou une citation.