Brevet FR2879782A1 — publié le 20060623

PROCEDE DE FILTRAGE EN TEMPS REEL DE FLUX DE CONTENUS NUMERIQUES PROVENANT DE TEXTES La présente invention se rapporte à un procédé de filtrage en temps réel de flux de contenus numériques provenant de textes. Lorsque l'on doit extraire rapidement des informations pertinentes parmi une grande masse d'informations reçues de façon continue ou tout au moins à un débit élevé (dépêches d'agences, journaux, documents livrés en vrac,...), les procédés connus de filtrage automatique de ces informations se révèlent inefficaces, soit parce qu'ils n'arrivent pas à suivre la cadence d'arrivée de ces informations en étant très sélectifs, soit parce que le résultat de leur filtrage est insuffisant du fait qu'ils sont peu sélectifs pour pouvoir tenir la cadence d'arrivée des informations. La présente invention a pour objet un procédé de filtrage d'informations en temps réel, quel que soit leur débit d'arrivée, tout en fournissant toutes les informations pouvant être pertinentes, et pouvant classer celles-ci suivant un grand nombre de thèmes sélectionnés. Le procédé conforme à l'invention est caractérisé en ce que l'on constitue un filtre initial comportant plusieurs filtres élémentaires représentés chacun par une grammaire locale et comportant chacun sa propre séquence d'énoncés pertinents des thèmes recherchés, que l'on fait l'apprentissage de ce filtre initial sur un corpus initial de, portion de texte représentatif du domaine exploré, que l'on détermine les poids des différents filtres élémentaires en relevant la fréquence d'apparition de mots et de combinaisons de mots dans le corpus initial, que l'on déterminise et minimise l'ensemble des filtres élémentaires pour en faire l'automate, que l'on applique le flux en temps réel à cet automate et qu'un opérateur effectue la synthèse des résultats de sortie de l'automate, ces résultats étant avantageusement triés par pondération. La présente invention sera mieux comprise à la lecture de la description détaillée d'un mode de réalisation, pris à titre d'exemple non limitatif et illustré par le dessin annexé, sur lequel: - la figure 1 est un bloc-diagramme simplifié d'un procédé de filtrage en temps réel de flux numériques conforme à l'invention, la figure 2 est un bloc-diagramme simplifié d'un exemple de deux filtres, représentés sous forme de graphes, mis en oeuvre par le procédé de l'invention, la figure 3 est un blocdiagramme simplifié d'un exemple de transducteur de plusieurs filtres, mis en oeuvre par le procédé de l'invention, la figure 4 est un blocdiagramme simplifié d'un exemple de transducteur minimal déterministe, mis en oeuvre par le procédé de l'invention, et la figure 5 est un blocdiagramme simplifié d'un exemple de transducteur minimal déterministe pondéré, mis en oeuvre par le procédé de l'invention. La présente invention est relative à un procédé filtrage temps réel de flux de contenus numériques. Elle est fondée sur la technologie des transducteurs linguistiques. Le procédé met en oeuvre un filtre représenté comme un automate linguistique à poids, qui a été préalablement entraîné sur un corpus. Chaque entrée d'un fllux numérique est transformée en automate; le processus de filtrage consiste donc à appliquer l'automate à poids du filtre sur l'automate du document. Si l'automate atteint un état terminal, alors le document est pertinent par rapport au filtre, et recommence ainsi pour chaque document du flux. Filtrage et grammaires locales Le procédé de réduction de flux temps réel est illustré sur le diagramme de la figure 1. Un flux d'informations numériques (ou préalablement numérisées) est filtré par un filtre 2, et réparti en différents ensembles de filtrats, notés 3 dans leur ensemble. Chacun de ces ensembles de filtrats correspond à un thème ou un mot donné. A partir de chacun de ces ensembles de filtrats, un opérateur humain effectue une synthèse correspondante S, l'ensemble des synthèses S étant noté 4, puis fournit pour chacun de ces ensembles un rapport de synthèse R, l'ensemble de ces rapports étant noté 5. Ainsi, la phase de filtrage F est automatisée et la phase de synthèse S est réalisée par un opérateur humain (appelé opérationnel). Un moyen de garantir le filtrage temps réel est d'utiliser une 35 technologie dont la complexité ne dépend pas du nombre de filtres. 10 Idéalement, cette complexité doit être linéaire (en temps) en fonction de la taille des documents à filtrer. Un moyen de garantir une synthèse temps réel est d'utiliser en amont une technologie de filtrage extrêmement précise. Avec une telle technologie, une file d'attente de la phase S (un filtrat) explose (devient beaucoup trop volumineuse), uniquement si: - le filtre est trop large (pas assez sélectif); - le thème concerné par le filtre est extrêmement productif. Dans ces deux cas, l'utilisateur peut corriger directement le problème en affinant son filtre (pour le rendre plus sélectif) pour le premier cas, et en introduisant en aval des technologies bien connues de clustering ou de dédoublonnage pour le deuxième cas. Selon la présente invention, l'utilisation de grammaires locales décrites sous forme d'automates linguistiques garantit les deux contraintes ci-dessus. En effet, une grammaire locale ne reconnaît que ce que la séquence spécifie (à l'inverse des technologies fondées sur des extensions sémantiques, statistiques ou neuronales). Le filtrage par grammaires locales est donc extrêmement précis (aux ambiguïtés vraies du langage près, la précision vaut 1). Par ailleurs, la technologie des automates linguistiques garantit en théorie une complexité linéaire en temps et en espace par rapport à la taille du document. On va décrire maintenant les filtres mis en oeuvre par la présente invention. Un filtre est défini comme un transducteur à poids T1 représenté sous forme de graphe. Les noeuds du graphe correspondent aux transitions du transducteur et les chemins du graphe correspondent aux états du transducteur. Au départ les transitions sont équiprobables, puis, étant donné un corpus initial C, on entraîne Ti sur C et on obtient ainsi un nouvel automate pondéré F1. Cette opération est répétée autant de fois qu'il y a de filtres utilisateurs. On construit ensuite le transducteur, résultant de la réunion de tous les filtres, en introduisant une transition en amont et une transition en aval, chacune générant en sortie des étiquettes contenant un identifiant du filtre. Ce transducteur est déterminisé et minimalisé. Ce transducteur est passé sur le document arrivant du flux d'information. Il génère en sortie le document annoté par les étiquettes des filtres déclenchés par le document. Un exemple simplifié d'un tel processus à deux filtres a été représenté en figure 2, sous forme de graphes. Sur cette figure, on a représenté en entrée le corpus C et deux transducteurs TI et T2. L'entraînement de C sur TI et T2 donne les filtres F1 et F2, respectivement. Dans cet exemple, les filtres TI et T2 retiennent respectivement les thèmes relatifs à marchés publics et services publics . Ces deux filtres TI et T2 sont transformés en transducteurs puis réunis pour faire un transducteur comme montré dans la figure 3. Ensuite, le transducteur est déterminisé et minimalisé comme dans la figure 4. Dans la figure 3, on voit que sont insérées des transitions générant en sortie des étiquettes type SGML identifiant le filtre ( par exemple). Ces étiquettes permettent de faire du surlignage des parties pertinentes du document. Par exemple, si nous avons le document en entrée contenant: [...] leo,9 commissaireo,8 auxo,9 compteso,6 signeo, 9 leso,9 marchéso,7 publicso,9 passéso,5 Paros [...] ; le résultat du passage de ce document donne: [...] leo,9 commissaireo,8 auxo,9 compteso, 6 signeo,9 leso,9 marchéso,7 publicso,9 passéso,5 paro,9 [...] ; qui, dans un navigateur HTML, pourrait donner à l'aide d'une feuille de style: [...] le commissaire aux comptes signe les marchés publics passés par [...]. Dans l'exemple ci-dessus, les noeuds contiennent des mots. Pour simplifier la tâche de l'opérationnel, les noeuds peuvent factoriser les mots recherchés en: É spécifiant une forme canonique (lemme) ; É spécifiant une catégorie grammaticale; É spécifiant un sous-graphe. Pour rendre la déterminisation plus aisée, on crée autant de transitions qu'il y a de formes fléchies, mais pour le cas des catégories grammaticales, le nombre de transitions peut exploser. Selon un autre aspect de l'invention, on peut utiliser la catégorie grammaticale qui reconnaît tout mot simple ou composé du dictionnaire. On peut également utiliser des négations, par exemple qui reconnaît un mot qui n'est pas dans le dictionnaire. Selon encore un autre aspect de l'invention, on peut également utiliser dans certains cas particuliers des noeuds qui contiennent non pas des mots mais des lettres. Les automates sont entraînés sur un corpus représentatif du domaine. La pondération des transitions est fondée sur une combinaison de trois facteurs: Les unigrammes: le poids des mots est fondé sur la fréquence du mot en question et sur un ensemble de traits caractéristiques définis sur les mots. Pour un corpus écrit, les traits prennent en compte le fait qu'un mot commence par une minuscule ou une majuscule, qu'il soit connu ou non du dictionnaire, qu'il soit en début ou en milieu de phrase. Les unigrammes sont performants pour identifier en première approximation des séquences comme les noms de personnes ou les noms de lieux composés de nombreux mots inconnus, commençant éventuellement par des majuscules. Les bigrammes: un bigramme évalue la probabilité d'identification d'un mot étant donné le mot précédent. Le processus est en fait inversé de manière à pouvoir prédire le mot à reconnaître, le mot probable étant un mot donné. - Les trigrammes: les trigrammes fonctionnent de la même manière que les bigrammes, en étendant le contexte pris en compte aux deux mots précédents. On obtient ainsi des séquences souvent pertinentes, mais la couverture des séquences obtenues est bien évidemment moindre que celle des unigrammes ou des bigrammes. Les probabilités sont calculées à partir du corpus d'entraînement. L'apprentissage est généralement fait de manière non supervisée (c'est-àdire sur un corpus non étiqueté) mais ill peut aussi être utile de mettre en avant l'information recherchée sur un corpus étiqueté. L'approche dépendra de l'objectif recherché. On va décrire maintenant les traitements tels qu'effectués selon le procédé de l'invention. Les pondérations précédemment calculées sont ensuite reportées sur les filtres. Pour ce faire, il suffit de prendre en compte les arêtes des graphes et d'y projeter les probabilités telles que calculées à l'étape précédente. On a représenté en figure 5 un transducteur minimal déterministe pondéré pour mettre en oeuvre un tel procédé. Lorsqu'un flux numérique se présente, il est d'abord segmenté en phrases en utilisant le transducteur de phrases. Ce transducteur s'applique sur une séquence de chaînes de caractères qui s'assemblent en suite de mots (simples et/ou composés). Ensuite, chaque mot est étiqueté par des accès au dictionnaire. Puis, le texte étiqueté est passé dans le transducteur des filtres. Enfin, on récupère le résultat trié par pondération. Le procédé de l'invention traite également le cas de filtres 10 imbriqués. Par exemple, si l'on a les filtres suivants: - FI: marchés publics; - F2: nouveaux marchés; et le texte suivant: - Les nouveaux marchés sont florissants. Les marchés publics 15 sont abondants. Les nouveaux marchés publics vont bon train . Lors de l'application du transducteur, on retrouve les expressions pertinentes suivantes: - Les nouveaux marchés sont florissants. 20 Les marchés publics sont abondants. Les nouveaux marchés publics vont bon train. Les nouveaux marchés publics vont bon train. Plusieurs filtres ont été reconnus, mais le filtre F2 obtient le meilleur score (0.12). Le score est calculé de manière classique, en faisant le produit des probabilités de chaque arête! du transducteur correspondant au filtre. Le score 0,12 est donc meilleur que le score 0, 86. La recherche du meilleur chemin peut être effectuée par des algorithmes classiques, notamment l'algorithme dit de Viterbi, qui permet de calculer un chemin optimal dans un graphe complexe pondéré. Des algorithmes récents ont montré comment étendre l'algorithme de Viterbi pour proposer les n meilleurs chemins dans un graphe pondéré. Les avantages du procédé de l'invention sont les suivants: Ce procédé s'applique aussi bien à des flux numériques textuels que audio, étant donné un corpus d'apprentissage du domaine: flux numérique textuel: les transducteurs à poids ainsi obtenus sont appliqués directement sur le document. flux numérique audio: on transforme les transducteurs à poids en un N-gramme (modèle de langage du système) du système de reconnaissance de la parole choisie. Seules les séquences correspondant aux transducteurs seront reconnues en fonction du paramétrage choisi. Le procédé de l'invention garantit le traitement temps réel doublement: d'une part, par la technique utilisée qui ne recourt pas à une pré-indexation des documents issus du flux, et d'autre part par la technique de pondération qui permet d'identifier les séquences les plus probables. Ceci permet d'attribuer un score aux documents filtrés. Ainsi, l'opérationnel, dans son travail de synthèse, peut prendre en compte les priorités en temps réel. En fonction du paramétrage, on peut faire évoluer la qualité et le rappel du filtrage souhaité. En effet, plus le seuil est proche de 0, plus les flux de données tels que des dépêches, sont pertinents. En contrepartie, le rappel sera faible car peu d'éléments seront retenus. Si l'opérationnel décide d'élever ce seuil, la couverture sera meilleure mais la précision sera plus faible (il y aura plus de dépêches non pertinentes reconnues par le système). REVENDICATIONS 1. Procédé de filtrage en temps réel de flux de contenus numériques provenant de textes, caractérisé en ce que l'on constitue un filtre initial (F) comportant plusieurs filtres élémentaires (F1, F2) représentés chacun par une grammaire locale et comportant chacun sa propre séquence d'énoncés pertinents des thèmes recherchés, que l'on fait l'apprentissage de ce filtre initial sur un corpus initial de portion de texte représentatif du domaine exploré, que l'on détermine les poids des différents filtres élémentaires en relevant la fréquence d'apparition de mots et de combinaisons de mots dans le corpus initial, que l'on déterminise et minimise l'ensemble des filtres élémentaires pour en faire un automate, que l'on applique le flux en temps réel à cet automate et qu'un opérateur effectue la synthèse (S) des résultats de sortie de l'automate. 2. Procédé selon la revendication 1, caractérisé en ce que les résultats de sortie de l'automate sont triés par pondération. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que l'on définit un filtre comme un transducteur à poids (T1) représenté sous forme de graphe dont les noeuds correspondent aux transitions du transducteur. 4. Procédé selon l'une des revendications précédentes, 20 caractérisé en ce que l'on utilise la catégorie grammaticale qui se rapporte à des mots simples ou composés d'un dictionnaire. 5. Procédé selon l'une des revendications précédentes, caractérisé en ce que l'on utilise des négations ( !DIC>) qui se rapportent à des mots qui ne sont pas dans un dictionnaire. 6. Procédé selon l'une des revendications précédentes, caractérisé en ce que l'on utilise des noeuds qui contiennent des lettres. 7. Procédé selon l'une des revendications précédentes, caractérisé en ce que l'on entraîne l'automate sur un corpus représentatif du domaine relatif au flux traité. 8. Procédé selon la revendication 7, caractérisé en ce que l'on effectue la pondération des transitions après entraînement du transducteur sur le corpus initial (C), autant de fois qu'il y a de filtres. 9. Procédé selon la revendication 8, caractérisé en ce qu'après avoir passé le transducteur sur le flux d'informations, ce transducteur génère un document annoté par les étiquettes des filtres déclenchés par le document. 10. Procédé selon la revendication 9, caractérisé en ce que l'on utilise les étiquettes pour faire du surlignage des parties pertinentes du 5 document produit.