Brevet FR2842923A1 — publié le 20040130

i Générateur d'un corpus spécifique à un domaine. La présente invention appartient au domaine des traitements automatiques du langage naturel. Plus particulièrement, elle adresse le problème de la génération d'un ensemble de textes spécifique d'un domaine d'application ou corpus spécifique. Les corpus spécifiques sont nécessaires, notamment dans les systèmes informatiques de reconnaissance de la parole pour atteindre un taux de reconnaissance acceptable pour l'utilisateur. C'est particulièrement nécessaire pour les systèmes à large vocabulaire (typiquement 20 000 mots) . La génération d'un corpus spécifique est un traitement qui nécessite encore dans l'état de l'art de longues opérations d'apprentissage progressif basées sur une sélection des textes d'un corpus d'un domaine donné à partir des phrases entrées par l'utilisateur. Une méthode de sélection basée sur un modèle probabiliste a été divulguée notamment dans le brevet US 5,444,617. Cette méthode présente l'inconvénient de nécessiter des interactions avec l'utilisateur longues et coteuses. La présente invention surmonte cet inconvénient en permettant à l'utilisateur de formuler une spécification du corpus spécifique sous la forme d'une grammaire, ou ensemble de règles de syntaxe, propre au domaine d'application, la génération du corpus spécifique du domaine étant ensuite automatique. L'invention réduit ainsi de manière importante le temps nécessaire à la collecte du corpus spécifique. A cet effet, l'invention propose un produit/programme et un procédé de collecte d'un ensemble de textes spécifiques d'un domaine d'application à partir d'un ensemble de textes non spécifique, caractérisé en ce qu'il comprend un module de commande par une grammaire du domaine d'application. L'invention sera mieux comprise à l'examen des figures suivantes dont le contenu est explicité dans le corps de la description: Figure 1: Schéma montrant les modules du produit/programme selon l'invention. Figure 2: Schéma montrant un exemple de génération des ngrammes d'une grammaire spécifique d'un domaine d'application. Figure 3: Schéma explicitant un algorithme de calcul des distances entre mots selon l'invention. Figure 4: Exemple de calcul des distances entre mots selon l'invention. Figure 5: Exemple de calcul sémantique. Figure 6: Graphique montrant la répartition des n-grammes en fonction de la distance aux mots du vocabulaire de la grammaire. La figure 1 montre l'enchaînement des modules et des traitements selon l'invention. Les définitions de la figure sont les suivantes: Le corpus général 10 est un ensemble de textes, disponible dans le commerce, non spécifique d'un domaine, qui peut comporter plusieurs millions de textes. n-gram[VcORpusj 13 est un ensemble de suites de mots ordonnés extraites du corpus général ou n-uplets, lesdits mots étant présents dans le vocabulaire. La manière dont ces n-grammes sont constitués est décrite plus loin. Le vocabulaire de ce corpus VCORPUS 11 est l'ensemble des mots les plus fréquemment rencontrés dans ce corpus ou ensemble des unigrammes. On limite généralement le vocabulaire à 20 000 mots. Le générateur AEF 20 est un module qui permet de générer les n-grammes d'une grammaire du domaine A à partir de ladite grammaire, d'une manière également explicitée dans la suite de la description. Un ensemble ngram[VcFG(A)] 33 est généré à partir de la grammaire CFG(A) 30 d'une manière explicitée dans la suite de la description. Le corpus spécifique de A, CORPUS(A) 40 est initialisé avec les n-grammes VCFG(A) 33. On rajoute par récurrence à CORPUS(A) 40 les n-grammes de VCORPUS 13 qui remplissent la condition: 3 n-gram[VcFG(A)]: D (n-gram [VcoRpus], n-gram [VCFG(A)]) Plusieurs fonctions de distance D sont utilisables comme expliqué 30 dans la suite de la description. 6 est le seuil de distance qui doit être réglé de manière à optimiser la constitution de CORPUS(A) 40 pour les applications de reconnaissance spécifiques du domaine A. Typiquement les n-grammes de VCORPUS13 seront des bi-grammes ou des tri-grammes. Un bigramme est un ensemble de deux mots qui appartiennent au vocabulaire VcoRpusl 1 auquel sont associées leurs probabilités d'occurrence dans le corpus général 10. Les tri-grammes sont des ensembles de trois mots dans l'ordre dans lequel ils se présentent dans le corpus général 10 auquel sont associées leurs probabilités d'occurrence dans le corpus général 10. Pour générer n-gram[VcoRpus] on peut utiliser des outils du commerce généralement désignés sous l'appellation générique d'outils de génération de modèle statistique de langage. On peut par exemple utiliser celui développé par l'Université Carnegie Mellon décrit par Philippe Clarkson et Ronald Rosenfeld dans une publication de l'Université [Rosenfeld 95] Rosenfeld R., The CMU Statistical Language Modeling Toolkit and its use, ARPA Spoken Language Technology Workshop, Austin Texas (USA) pp 4550, 1995. Cet article est incorporé par référence à la présente description. La plupart des modèles statistiques de langage, et notamment celui décrit dans l'article sous référence, corrigent les probabilités d'occurrences les plus faibles de manière à supprimer le biais qui est classique dans ce type d'analyse statistique. Les n-grammes les moins observés ont en effet une probabilité d'occurrence biaisée vers le bas et les plus observés une probabilité d'occurrence biaisée vers le haut. La grammaire CFG (A) 30 est une grammaire indépendante du contexte, ce qui veut dire que des variations du contexte ne modifient pas la grammaire elle-même. Cette grammaire est, dans l'état de l'art, constituée manuellement. Les n-gram[VcFG(A)] 33 seront typiquement des tri-grammes ou des quadri-grammes. Ils sont créés par le générateur AEF 20 dont un exemple est décrit à la figure 2. La génération des n-grammes de CFG(A) 30 se déroule comme suit, - création de l'automate déterministe correspondant (on ne tient pas compte des probabilités). (Sommet = état, Transition = symbole terminal); - on sélectionne tous les n-arcs consécutifs appartenant à cet automate, soit la CFG suivante: GRAMMAIRE = unité (alpha OU bravo) (rejoignez OU (allez vers) l'unité (alpha OU bravo) Le vocabulaire est donc VCFG = (unité, alpha, bravo, rejoignez, allez vers, l'unité). On remarque que | I = 6 On obtient l'automate fini déterministe représenté à la figure 2. Les unigrammes sont: unité, alpha, bravo, rejoignez, allez vers, l'unité (on retombe sur VCFG). Les bigrammes sont: unité alpha, unité bravo, alpha rejoingnez, alpha allez vers, bravo rejoignez, bravo allez vers, rejoingnez l'unité, allez vers l'unité, l'unité alpha, l'unité bravo. Il y en a 10, c'est-à-dire beaucoup moins que I VCGF 12 = 36 Les trigrammes sont: unité alpha rejoignez, unité alpha allez vers, unité bravo rejoignez, unité bravo allez vers, alpha rejoignez l'unité, alpha allez vers l'unité, bravo rejoignez l'unité, bravo allez vers l'unité, rejoignez l'unité alpha, rejoignez l'unité bravo, allez vers l'unité alpha, allez vers l'unité bravo. 11 y en a 12, c'est-à-dire beaucoup moins que IVCGF 3= 216 Bien qu'en théorie, le nombre de n-grammes peut atteindre IVCGF n, il est n réalité bien plus petit que cela (quelques milliers de ngrammes pour une grammaire dont le vocabulaire atteint 200 mots). Le vocabulaire VCFG(A) 31 est l'ensemble des uni-grammes. La figure 3 illustre le fonctionnement de l'algorithme de calcul de distance entre deux mots d'un dictionnaire. Dans l'application on utilise les trois dictionnaires 10, 12 et 32 de la figure 1. Les dictionnaires dico-VcoRpus 12 et dico-VCFG( A) 32 sont des dictionnaires extraits d'un dictionnaire général 1 Oa qui est un composant que l'on trouve dans le commerce. Ce dictionnaire général apporte des informations aux formes fléchies des mots, telle que la prononciation, la racine du mot. On peut aussi y ajouter des informations sémantiques qui peuvent être représentées sous forme de graphe ou de vecteurs conceptuels. Cet algorithme comprend trois étapes: - Le calcul de distance lettre à lettre, qui utilise l'algorithme de distance d'édition et les paramètres ins-del-sub; - Le calcul de distance entre deux mots quelconques, qui va pondérer suivant la longueur du mot transformé; - Le calcul de distance entre deux mots du dictionnaire qui va prendre en compte le type et le sens des mots. Les notations sont les suivantes I a I nombre de lettres de a C mot vide Div opérateur de division entière Une des méthodes de calcul des distances entre deux mots est décrite dans les ouvrages accessibles à l'homme de métier sous le nom de distance d'édition (ou de Levenstein ou de Wagner-Fisher) [Wagner & Fisher, 1974] Wagner, R. A. & Fisher, M.J. (1974). The string-to-string correction problem. Journal of the Association for computing Machinery, 21(1), 168-173. [Amengual & Vidai, 1998] Amengual, J.-C. & Vidal, E. Efficient error-correcting viterbi parsing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(10), 1109-1116, 1998. Ces articles sont incorporés par référence dans la présente demande. Etant donnés deux mots a et b, la distance d'édition renvoie le nombre minimal d'opérations d'édition nécessaires pour transformer le mot a en mot b. Ces opérations d'édition sont en général l'insertion d'une lettre, la suppression d'une lettre et la substitution d'une lettre. On peut affecter un poids à chacune de ces opérations. Dans ce cas, la distance d'édition renverra le poids total minimal qui transforme le mot a en mot b. Soit DL (a,b) la fonction qui renvoie la distance d'édition (Levenstein) qui permet de transformer a en b. DL admet pour paramètres les entiers Pins, Pdel, Psub (les distances unitaires pour chaque 25 insertion/suppression/substitution). Les choix de ces paramètres est arbitraire dans un premier temps, c'est en fonction des résultats que l'on pourra les affiner, mais par exemple on peut prendre: Pdel = 2, Pins = 3 et Psub =4. Pour notre application, la distance DQ entre deux mots quelconques doit mettre en évidence la dénaturation du mot d'origine: l'importance de la transformation effectuée peut se mesurer par rapport à la taille du mot d'origine. Etant donné un mot a de longeur n, si k opérations d'édition ont été effectuées, alors la dénaturation du mot d'origine peut s'estimer à k/n. Dans le cas particulier o a est vide (a = E) on effectue le calcul comme si la longueur du mot vide était de 1. Les vocabulaires VCFG et VCORPUS étant finis, la longueur du mot le plus long est donnée par la formule: DQ(a,b) = (K*DL(a,b)) div lai sia! É 0 et Do (a,b) = DL (F,b) sia! = 0 o K = max( {al/a a VCFG},{l bl/b Y VCORPUS}) Il est maintenant souhaitable pour calculer la distance D entre deux mots du dictionnaire de corriger la distance d'édition d'un facteur tenant compte de leur distance étymologique et sémantique. Pour ne pas dégrader la vitesse d'exécution du traitement, on choisit avantageusement un indicateur simplifié de cette proximité constitué comme il est dit cidessous Soit DQmax la distance maxi entre deux mots quelconques Soient a E VCFG (A) et b E VcoRpus les deux mots dont on veut mesurer la distance. D (a,b) = Do + DQ (a,b) Si a et b ont la même racine, DO = 0 Si a et b ont le même sens, Do = DOmax Si a et b appartiennent au vocabulaire de la CFG, Do = 2* DQmax Sinon, Do = 3* DQmax Toute fonction de calcul de distance entre a et b est utilisable. Il est cependant préférable que la fonction D soit continue par morceaux et croissante en fonction de DQ. On donne ci-dessous un exemple d'exécution de l'algorithme de calcul de la distance entre mots. Prenons Pins=Pdel=Psub=l Soit VCFG défini par: VCFG = {g, " unité ", " afficher "} Soit Vcorpus défini par VCORPUS = { ú, " montrer ", " K=8 longueur du mot le plus long: " afficher " Donc l'expression de la distance entre deux mots du dictionnaire devient Do(a,b) = 8*DL(a,b) div I a I 8*DL(E, b) si a!=0 sinon DQmax = 8*1 = 8 D(ú, e)=O D(ú,, DO= 24 DQ(F, " cheval ")= 6 D(ú, " cheval ")= 24+6=30 D(" unité ", ú)= Do=24 Do(" ", F)= (5*8) div 5 = 8 D( > " montré "-> D" " cnité "->> "chité "--> "cheté "-, " chevé "-* " cheva" -> , DO = 24 DQ(" afficher >",)= (8*8) div 8 = 8 D(" afficher ",g) =24+8= 32 D(" afficher ", " montrer ")= Do = Damax = 8 DQ(", afficher ", " montrer ")= (6*8) div 8 = 6 Car(",afficher"-> "mfficher >-> ,--> " montrer> =6) D(" afficher,, " montrer ")= 8 + 6 = 14 D(" afficher ", " cheval ")= DO = 3*DQmax = 24 DQ (" afficher ", "cheval ") = (7*8) div 8 = 7 car (" "fficher ">> "ficher "--> " icher "--> "cher "-@ " chev" --> " cheva "-* " cheval " = 7) D (" figure 4. On remarque que la distance la plus faible (hormis les mots vides) 25 est celui pour le couple (afficher, montrer). Il est en effet plus facile d'insérer que de supprimer: la suppression conduit à la perte d'information, tandis que l'insertion ajoute du bruit dans l'information. Dans une variante de réalisation, Il est possible d'avoir un découpage plus fin au niveau du sens en considérant plusieurs niveaux de sémantiques différentes (par le biais d'une classification). Par exemple: couleur, rouge, et vert sont voisins, mais rouge et vert sont plus proches entre eux qu'avec couleur. Le calcul sémantique est fait à partir de dictionnaires sémantiques. Il existe plusieurs formes de disctionnaires sémantiques dont deux en particulier: ceux à base de graphes, et ceux à base de vecteurs. Sur l'exemple des couleurs, si le dictionnaire sémantique est un graphe, on peut obtenir le schéma de la figure 5; Pour calculer la distance, on peut utiliser la convention suivante - deux frères ont une distance de 1 un père et un fils ont une distance de 2 Par exemple, la distance entre couleurs et rouge est de 2. Celle entre rouge et vert est de 1. Par contre la distance entre rouge et chien est de 5, comme illustré figure 5b. Lorsqu'il s'agit de vecteurs conceptuels, la distance se résume à un produit scalaire. Dans la mesure o ce qui nous intéresse, ce sont les distances très proches entre les mots (à partir d'une certaine distance, on n'est plus intéressé par la valeur). Par conséquent, dans l'invention on considèrera la distance sémantique comme étant binaire (deux mots sont 1 5 proches sémantiquement ou ne le sont pas). Les distances sont des valeurs entières, ce qui permet de constituer plus facilement des tableaux d'analyse qui permettront de choisir le seuil. A l'aide de cet algorithme de calcul des distances entre mots (ou distances unitaires), il est possible de calculer D (a,b) pour tout mot a et tout mot b appartenant respectivement à VCORPUS et à VCFG(A). Il s'agit maintenant de déduire de cette première matrice une deuxième matrice des distances entre les n-grammes (x;)' de VcoRpus et les mgrammes (y,)' de VCFG(A). On utilisera avantageusement pour ce faire un algorithme connu de l'homme du métier décrit dans l'ouvrage [Chodorowski, 2001] Chodorowski, J. Inférence grammaticale pour l'apprentissage de la syntaxe en reconnaissance de la parole et dialogue oral. Thèse, Université de Rennes 1, 2001, page 50 qui est incorporé par référence dans la présente description. On cherche à calculer l'élément M (n, m) de cette deuxième 30 matrice qui est la distance entre le n-gramme (x*);' et le mgramme (yj)rn. L'algorithme décrit dans la référence ci-dessus calcule M (n, m) par une récurrence de programmation dynamique définie de la manière suivante M (0,0)= 0 M (i,0) = Y,'= D (xk, c) pour 1 étaient des simples symboles. Exemple: Distance entre vers ". 1 5 M1=unité M2=alpha M3=allez M4=vers M5=avancez La distance entre ces deux phrases est égale à la distance entre les séquences M1M2M3M4 et M1M2M3M5, étant donnée la matrice de distance unitaire D(Mi,Mj) calculée précédemment. Le nombre de calculs pour chaque élément M (n, m) est donc de l'ordre de n x m, soit de 12 dans le cas d'un mode priviligié de réalisation o n = 3 et m = 4. On notera que les calculs de rang inférieur dans la récurrence permettent de remplir d'autres cases de la matrice des distances entre ngram et m-grams. Cependant bien entendu, d'autres algorithmes de calcul des distances entre n-grammes et m-grammes pourront être choisis. Le seuil ô de distance au-dessous duquel les n-grams du corpus général dont la distance à des m-grams de VCFG(A) sont rajoutés à CORPUS (A), celui-ci étant initialisé au départ par VCFG(A). L'analyse numérique de la matrice des M (n, m) permet de tracer un graphe un graphe des fréquences de n-grammes en fonction de la distance aux mots et VCFG(A) (figure 6). Quelques itérations seront utiles pour régler 8. il La mise en oeuvre de l'invention est possible sur un ordinateur du commerce de type quelconque pourvu des interfaces classiques d'entrée et de restitution de données (clavier, souris,écran, imprimante). L'intégration avec un système de reconnaissance vocale est possible sur une configuration commune. Dans ce cas, le système informatique dispose en outre d'un microphone, de hauts-parleurs, d'une carte spécialisée de traitement de signal et d'un logiciel spécialisé de reconnaissance vocale. REVENDICATIONS 1. Produit/programme de collecte d'un ensemble de textes (40) spécifique d'un domaine d'application (à) à partir d'un ensemble textes non spécifique (10), caractérisé en ce qu'il comprend un module de commande par une grammaire (30) du domaine d'application (à). 2. Produit/programme selon la revendication 1, caractérisé en ce que le module de commande comporte un module de mesure de distance D entre des phrases de l'ensemble de textes non spécifique et des phrases de la grammaire du domaine d'application. 3. Produit/programme selon la revendication 2, caractérisé en ce que le module de commande comporte une valeur ajustable ô de seuil de distance entre phrases. 4. Produit/programme selon l'une des revendications 2 ou 3, caractérisé en ce que le module de mesure de distance calcule la distance D entre une phrase de n mots et une phrase de m mots de manière récurrente à partir d'une mesure de la distance entre les mots. 5. Produit/programme selon la revendication 4, caractérisé en ce que pour i et j' variant respectivement de 1 à n et 1 à m, un élément de rang (i, j) dans la récurrence est le minimum de la somme de l'élément de rang (i 1, j) et de la distance entre le mot de rang i de la première phrase et le mot " espace ", de la somme de l'élément de rang (i, j - 1) et de la distance entre le mot " espace " et le mot de rang j de la deuxième phrase et de la somme de l'élément de rang (i - 1, j - 1) et de la distance entre le mot de rang i de la première phrase et le mot de rang j de la deuxième phrase. 6. Produit/programme selon la revendication 4, caractérisé en ce que, pour i et j variant respectivement de 1 à n et de 1 à m, des éléments de rang (i, o) ou (o, j) dans la récurrence sont chacun la somme pour k variant de 1 à i des distances entre le mot de rang k et le mot " espace >. 7. Produit/programme selon la revendication 4, caractérisé en ce que, l'élément de rang (o, o) dans la récurrence est égal à o. 8. Produit/programme selon l'une des revendications 4 à 7, caractérisé en ce que la distance entre mots est une fonction décroissante de leur proximité étymologique et sémantique et croissante d'une mesure du cot de transformation lettre à lettre d'un des deux mots en l'autre. 9. Produit/programme selon l'une des revendications 1 à 8, caractérisé en ce que les n-grammes de la grammaire spécifique du domaine d'application (33) sont générés par un module (20) o l'utilisateur paramètre un automate à états finis déterministe. 10. Système de reconnaissance de la parole comprenant un produit/programme selon l'une des revendications 1 à 9. 11. Système de traitement de l'information comprenant un module selon l'une des revendications 1 à 10. 12. Procédé de collecte d'un ensemble de textes spécifique d'un domaine d'application A à partir d'un ensemble de textes non spécifique (10), caractérisé en ce que la collecte est commandée par une grammaire du domaine d'application D (30). 13. Procédé selon la revendication 12, caractérisé en ce que la commande comporte une mesure de distance D entre des phrases de l'ensemble de textes non spécifique et des phrases de la grammaire du domaine d'application. 14. Procédé selon la revendication 13, caractérisé en ce que la 20 commande comporte une valeur ajustable 6 du seuil de distance entre phrases. 15. Procédé selon l'une des revendications 13 ou 14, caractérisé en ce que la mesure de distance entre une phrase de n mots et une phrase de m mots se calcule de manière récurrente à partir d'une mesure de la distance entre les mots. 16. Procédé selon la revendication 15, caractérisé en ce que pour i et j' variant respectivement de 1 à n et 1 à m, un élément de rang (i, j) dans la récurrence est le minimum de la somme de l'élément de rang (i - 1, j) et de la distance entre le mot de rang i de la première phrase et le mot " espace ", de la somme de l'élément de rang (i, j - 1) et de la distance entre le mot " espace " et le mot de rang j de la deuxième phrase et de la somme de l'élément de rang (i - 1, j - 1) et de la distance entre le mot de rang i de la première phrase et le mot de rang j de la deuxième phrase. 17. Procédé selon la revendication 15, caractérisé en ce que, pour i et j variant respectivement de 1 à n et de 1 à m des éléments de rang (i, o) ou (o, j) dans la récurrence sont chacun la somme pour k variant de 1 à i des distances entre le mot de rang k et le mot " espace ". 18. Procédé selon la revendication 15, caractérisé en ce que, l'élément de rang (o, o) dans la récurrence est égal à o. 19. Procédé selon l'une des revendications 15 à 18, caractérisé en ce que la distance entre mots est une fonction décroissante de leur proximité étymologique et sémantique et croissante d'une mesure du cot de transformation lettre à lettre d'un des deux mots en l'autre. 20. Procédé selon l'une des revendications 12 à 19, caractérisé en ce que les n-grammes de la grammaire spécifique du domaine d'application (33) sont générés par un module (20) o l'utilisateur paramètre un automate à états finis déterministe. 21. Procédé de reconnaissance de la parole mettant en oeuvre un procédé selon l'une des revendications 12 à 20. 1 5 22. Procédé de traitement de l'information mettant en oeuvre un procédé selon l'une des revendications 12 à 21.