Brevet FR2801716A1 — publié le 20010601

Les systèmes d'information ou de contrôle utilisent de plus en plus souvent une interface vocale pour rendre l'interaction avec l'utilisateur rapide et intuitive. Ces systèmes devenant plus complexes, les styles de dialogue supportés sont de plus en plus riches, et l'on rentre dans le domaine de la reconnaissance vocale continue à très large vocabulaire. On sait que la conception d'un système de reconnaissance vocale continue à large vocabulaire suppose de produire un Modèle de Langage qui définit la probabilité pour qu'un mot donné du vocabulaire de l'application, suive un autre mot ou groupe de mot, dans l'ordre chronologique de la phrase. Ce modèle de langage doit reproduire le style d'élocution ordinairement employé par un utilisateur du système. La qualité du modèle de langage utilisé influe de manière forte sur la fiabilité de la reconnaissance vocale. Cette qualité est le plus souvent mesurée par un indice appelé perplexité du modèle de langage, et qui représente schématiquement le nombre de choix que le système doit réalisé pour chaque mot décodé. Plus cette perplexité est basse, plus la qualité est bonne. Le modèle de langage est nécessaire pour traduire le signal vocal en une suite textuelle de mots, étape souvent utilisée par les systèmes de dialogue. Il faut alors construire une logique de compréhension qui permette de comprendre la requête pour y répondre. Il existe deux méthodes standards pour produire des modèles de langage à large vocabulaire: (1) La méthode statistique dite en N-gram, le plus souvent en bigram ou trigram, consiste à supposer que la probabilité d'occurrence d'un mot dans la phrase dépend uniquement des N mots qui le précède, indépendamment de son contexte dans la phrase. Si l'on prend l'exemple du trigram pour un vocabulaire de 1000 mots, il faudrait définir 10003 probabilités pour définir le modèle de langage, ce qui est peu pratique. Pour résoudre ce problème, les mots sont groupés en ensembles qui sont soit définis explicitement par le concepteur du modèle, soit déduits par des méthodes auto-organisatrices. Ce modèle de langage est construit a partir d'un corpus de texte de façon automatique. (2) La seconde méthode consiste à décrire la syntaxe au moyen d'une grammaire probabiliste, typiquement une grammaire non contextuelle définie grâce à un ensemble de règles décrites sous la forme dite Backus Naur Form ou BNF. Les règles décrivant les grammaires sont le plus souvent écrites à la main, mais peuvent également être déduites de manière automatique. A ce titre, on peut se référer au document suivant: "Basic methods of probabilistic context free grammars" par F. Jelinek J.D. Lafferty et R.L. Mercer NATO ASI Series Vol. 75 pp. 345-359, 1992. Les modèles précédemment décrits posent des problèmes spécifiques lorsqu'ils sont appliqués à des interfaces de systèmes en langage naturel: Les modèles de langages de type N-grams (1) ne modélisent pas correctement les dépendances entre plusieurs sous-structures grammaticales distantes dans la phrase. Pour une phrase prononcée syntaxiquement correcte, rien ne garantit que ces sous-structures seront respectées au cours de la reconnaissance, ce qui fait qu'il est difficile de déterminer si tel ou tel sens, habituellement porté par une ou plusieurs structures syntaxiques précises, est véhiculé par la phrase. Ces modèles sont adaptés à la dictée continue, mais leur application dans les systèmes de dialogue souffre des défauts mentionnés. Les modèles fondés sur des grammaires (2) permettent de modéliser correctement les dépendances à distance dans une phrase, et également de respecter des sous-structures syntaxiques précises. La perplexité du langage obtenu est souvent plus faible, pour une application donnée, que les modèles de type N-gram. Par contre, pour des langues très infléchies comme le Français ou l'italien, dans lesquelles la place des groupes syntaxiques dans la phrase est assez libre, les grammaires de type BNF posent des problèmes pour la définition des permutations des groupes syntaxiques en question. Pour des langues moins infléchies comme l'Anglais, ces permutations sont également nécessaires pour décrire les hésitations et les faux départs du langage parlé ordinaire, et rendent mal adapté le modèle de langage basé sur les BNF. L'invention a pour objet un dispositif de reconnaissance vocale comportant un processeur audio pour l'acquisition d'un signal audio et un io décodeur linguistique pour déterminer une séquence de mots correspondant au signal audio, caractérise en ce que le décodeur linguistique comporte un modèle de langage défini à l'aide d'une grammaire comprenant une règle syntaxique de permutation sans répétition de symboles. Le modèle de langage proposé par les inventeurs étend le formalisme des grammaires BNF pour supporter les permutations syntaxiques du langage ordinaire et des langues fortement infléchies. Il permet de réduire la mémoire nécessaire pour le traitement de la reconnaissance vocale et est particulièrement adapté à des utilisations dans des produits grand public. Selon un mode de réalisation préférentiel, la règle syntaxique de permutation de symboles comporte une liste de symboles et le cas échéant des expressions de contraintes d'ordre des symboles. Selon un mode de réalisation préférentiel, le décodeur linguistique comporte un moteur de reconnaissance qui, lors de l'affectation de symboles d'une permutation à une suite de termes d'une phrase, choisit un symbole à affecter à un terme donné uniquement parmi les symboles de la permutation n'ayant pas été affectés précédemment. Selon un mode de réalisation particulier, le moteur de reconnaissance met en oeuvre un algorithme de type 'Beam Search ou 'nbest'. D'autres algorithmes peuvent également être mis en oeuvre. D'autres caractéristiques et avantages de l'invention apparaîtront à travers la description d'un mode de réalisation particulier non limitatif, explicité à l'aide des dessins joints parmi lesquels: - la figure 1 est un diagramme d'un système de reconnaissance vocale, - la figure 2 est un diagramme d'un automate à pile de l'art antérieur, - la figure 3 est un diagramme d'un automate à pile selon l'invention, - la figure 4 est un schéma illustrant les alternatives de symboles au o0 début de l'analyse d'un exemple de permutation, conformément à l'invention, - la figure 5 est un schéma illustrant les alternatives de symboles de l'exemple de la figure 4 à une étape ultérieure, conformément à l'invention, - la figure 6 est un schéma illustrant les alternatives de symboles dans le cas de l'expression d'une permutation à l'aide de règles de l'art antérieur, - la figure 7a est un arbre illustrant l'ensemble des alternatives aux noeuds résultant de l'exemple de permutation, conformément à l'invention, et - la figure 7b est un arbre illustrant l'ensemble des alternatives aux noeuds résultant de l'exemple de permutation, selon l'art antérieur. La figure 1 est un diagramme bloc d'un exemple de dispositif 1 de reconnaissance de la parole. Ce dispositif comporte un processeur 2 du signal audio réalisant la numérisation d'un signal audio provenant d'un microphone 3 par l'intermédiaire d'un circuit 4 d'acquisition du signal. Le processeur traduit également les échantillons numériques en symboles acoustiques choisis dans un alphabet prédéterminé. Il comporte à cet effet un décodeur acoustico- phonétique 5. Un décodeur linguistique 6 traite ces symboles dans le but de déterminer, pour une séquence A de symboles, la séquence W de mots la plus probable, étant donné la séquence A. Le décodeur linguistique utilise un modèle acoustique 7 et un modèle de langage 8 mis en oeuvre par un algorithme de recherche par hypothèse 9. Le modèle acoustique est par exemple un modèle dit 'Markov caché ('Hidden Markov model' ou HMM). Le modèle de langage mis en oeuvre dans le présent exemple de réalisation est basé sur une grammaire décrite à l'aide de règles de syntaxe de forme Backus Naur. Le modèle de langage est utilisé pour soumettre des hypothèses à l'algorithme de recherche. Ce dernier, qui est le moteur de reconnaissance proprement dit, est pour ce qui du présent exemple un algorithme de recherche de basé sur un algorithme de type Viterbi et appelé n-best'. L'algorithme de type n-best détermine à chaque étape de l'analyse d'une phrase les n séquences de mots les plus probables. En fin de phrase, la solution la plus probable est choisie parmi les n candidats. Les notions du paragraphe ci-dessus sont en soi bien connues de l'Homme du Métier, mais des informations concernant en particulier l'algorithme nbest sont donnés dans l'ouvrage: "Statistical methods for speech recognition" par F. Jelinek, MIT Press 1999 ISBN 0-262-10066-5 pp. 79-84. D'autres algorithmes peuvent également i0 être mis en oeuvre. Notamment, d'autres algorithmes de type 'Beam Search' (Recherche par faisceau), dont l'algorithme 'n-best' est un exemple. Le décodeur acoustico-phonétique et le décodeur linguistique peuvent être réalisés par l'intermédiaire d'un logiciel approprié exécuté par un microprocesseur ayant accès à une mémoire comportant l'algorithme du moteur de reconnaissance et les modèles acoustique et de langage. L'invention concerne essentiellement le modèle de langage, ainsi que son utilisation par le moteur de reconnaissance. On utilise habituellement les quatre règles syntaxiques suivantes pour définir une grammaire probabiliste de modèle de langage. Ces quatre règles sont: (a) Symbole 'ou' = i (b) Symbole 'et'( Concaténation) = (c) Elément Facultatif = ? (indice facultatif) (d) Affectation Lexicale = "mot lexical" Il est à noter que seules les règles (a), (b) et (d) sont réellement obligatoires. La règle (c) peut être reproduite à l'aide des trois autres, quoiqu'au détriment de la compacité du modèle de langage. Le modèle de langage conforme au présent exemple de réalisation io utilise une règle syntaxique supplémentaire pour définir la grammaire probabiliste du modèle de langage: (e) Symbole 'permutation' s5 = Permut { , ,..., } ( > > ) Ceci signifie que le symbole A est l'une quelconque des permutations sans répétition des n symboles Ai,.. .An, ces symboles étant assemblés par la règle "et" pour chaque permutation. De plus, selon le présent exemple de réalisation, seules les permutations qui vérifient les contraintes exprimées entre parenthèses et qui se lisent: "le symbole Ai apparaît dans la permutation avant le symbole Aj, le symbole Ak apparaît avant le symbole AI", sont valides syntaxiquement. L'indice facultatif présent dans la définition de la règle (c) fonctionne de la manière suivante: Un indice facultatif est un couple formé d'un entier et d'un booléen, qui peut être vrai ou faux. Lorsqu'une règle de récriture du type: = ? (indice facultatif est rencontrée, alors: e Si le même entier que celui du présent indice facultatif n'a jamais été rencontré dans les indices facultatifs d'autres règles qui ont produit l'état actuel dans la grammaire du modèle de langage, pour l'hypothèse actuellement étudiée, alors le symbole A peut: être dérivé en le symbole B et l'indice facultatif activé; * être dérivé dans la règle vide et l'indice facultatif non activé. a Si le même indice a été activé par application d'une règle de même type selon le protocole décrit ci-dessus, alors la seule expression valide de la règle est * de dériver le symbole A en le symbole B si l'indice booléen est vrai; * de dériver le symbole A en le symbole vide si l'indice booléen est faux. Les permutations pourraient être exprimées dans un langage de type BNF indépendant du contexte, en étendant simplement l'arbre syntaxique que représente la cinquième règle, cette extension se faisant uniquement par l'emploi des quatre premières. Pour des raisons combinatoires, I'arbre syntaxique obtenu sera de grande taille, dès que le nombre de symboles permutés augmente. Le traitement des permutations se fait grâce à un automate à pile, donc dépendant du contexte, et qui marque si, au cours de la recherche syntaxique, une occurrence du groupe participant à la permutation a déjà été rencontrée, de façon correcte vis-à-vis des contraintes d'ordre. Le traitement standard d'une grammaire BNF se fait grâce aux objets illustrés par la figure 2. L'exemple de réalisation est par contre basé sur un automate à pile qui utilise les nouveaux objets illustrés par la figure 3. Pour décrire la mise en oeuvre de la règle de syntaxe (e), on prendra l'exemple d'une phrase simple, composée d'une seule permutation de trois termes syntaxiques, sans contraintes: = Permut { , , } Les termes A, B et C peuvent eux-mêmes être des termes complexes, définis avec un ou plusieurs symboles de permutation et/ou d'autres symboles. Un système de reconnaissance vocale basé sur les principes classiques de description des grammaires, c'est-à-dire utilisant la syntaxe BNF simple, traduira cette forme de phrase de la manière suivante: = I j | . Il y a 3! combinaisons, reliées par le symbole "ou" (I). L'arbre syntaxique est totalement déplié, et l'information que cet arbre est en fait la représentation d'une permutation est perdue. L'arbre décrit est entièrement stocké en mémoire pour représenter le modèle de langage nécessaire à la reconnaissance vocale. Cette structure est utilisée pour proposer des termes candidats à analyser au cours de l'algorithme 'n-best search' du moteur de reconnaissance, termes qui seront concaténés pour former des phrases conformes à la syntaxe et parmi lesquelles le moteur retiendra les n meilleures, c'est-à-dire celles qui présentent les scores de vraisemblance les plus élevés connaissant le signal sonore enregistré. L'algorithme 'n-best search' est couplé à une stratégie d'élagage de branches de l'arbre syntaxique qui ne retient, au cours de l'analyse de gauche à droite de la phrase, que les n meilleurs segments candidats jusqu'au point d'analyse actuel. On voit que pour l'étude de la phrase en question, au démarrage de l'analyse, six alternatives seront présentées au moteur de décodage acoustique, une pour chacune des combinaisons des trois termes , et . Le fait que l'on puisse distinguer de gauche à droite trois sousgroupes de deux combinaisons (l'un commençant par le symbole , le second par le symbole , et le dernier par le symbole ) est perdue et le moteur analysera de manière indifférenciée chacune des six structures. S'il s'avère que les structures syntaxiques , et sont suffisamment complexes pour qu'un élagage se produise au cours de l'analyse de ces structures, alors les n meilleurs segments analysés seront en fait composés de paires de structures parfaitement identiques, et donc seulement n-best/2 alternatives auront effectivement été prises en compte. Le traitement nouveau proposé par l'invention ne souffre pas de cette réduction de l'espace de recherche: I'information qu'une permutation existe dans la grammaire est indiquée de façon explicite et la permutation est traitée comme telle. On décrira dans ce qui suit en premier lieu en détail le comportement du moteur de reconnaissance dans le cas de la mise en oeuvre de la règle (e) pour décrire une permutation, puis on s'attachera à décrire le comportement du moteur de reconnaissance dans le cas o les permutations sont exprimées à l'aide des règles (a) à (d). De la comparaison des deux comportements ressortiront les avantages apportés par l'invention mentionnés ci-dessus. Les figures 4 et 5 sont des diagrammes illustrant le comportement du moteur de reconnaissance lorsqu'on lui présente une permutation conformément à l'invention. Au démarrage de l'analyse de la permutation, étape illustrée par la figure 3, trois possibilités sont présentées au moteur de reconnaissance pour le choix du premier terme de la phrase: le symbole , le symbole et le symbole . Une analyse 'n-best' avec élagage est appliquée sur ces structures. Le moteur considère en premier lieu le symbole . Le chemin qui explore la voie se poursuit dans l'analyse gauche-droite de la manière suivante: Comme c'est le chemin débutant par qui est analysé, un symbole logique en mémoire conserve cette information en positionnant une variable affectée à la permutation en question et à l'alternative actuellement étudiée. Cette variable, gérée par le moteur, précise que ce symbole n'est plus actif pour la suite de l'analyse du présent chemin, c'est à dire qu'il ne sera plus disponible en tant que symbole candidat pour un terme situé plus loin le long du même chemin.. Plus précisément, la situation au début de l'analyse est celle illustrée par la figure 4: Les trois symboles , , sont actifs et candidats pour io l'algorithme n-best de reconnaissance. Au cours de la recherche, chacune des alternatives est explorée. Par exemple, pour la première, le symbole est envisagé. Au cours de cette exploration, il faudra explorer les suites de symboles possibles commençant par :Se plaçant au niveau de l'analyse du second terme de la phrase, on aura la situation illustrée par la figure 5: Le symbole n'est plus disponible pour l'analyse de la suite de la phrase, pour l'alternative actuellement envisagée parce qu'il a été consommé précédemment dans l'analyse gauche-droite du flux du signal enregistré. Il reste donc deux symboles candidats, et . De manière analogue, la voie de recherche qui analysera par exemple marquera ce symbole comme inactif et il ne restera que le symbole disponible pour la suite du décodage. En d'autres termes, le moteur de reconnaissance selon l'invention traite une permutation telle que définie par la règle (e) de la manière illustrée par la figure 7a. On considère que le moteur considère le terme de rang i de la phrase à analyser. Le moteur détermine l'ensemble des alternatives de symboles possibles: dans le cas de l'exemple de permutation à trois symboles, il y a trois alternatives possibles au niveau i: , , . Au rang i+1, il n'y a plus que deux alternatives, le symbole précédemment choisi au rang i n'étant plus considéré par le moteur. Au rang i+2, aucun choix n'est plus possible. Du point de vue de la prise en considération des n meilleurs chemins, il apparaît que la réduction du nombre d'alternatives possibles au niveau de certains noeuds de l'arbre de la figure 7a évite la prise en considération de chemins partiellement redondants. On peut de même représenter le fonctionnement d'un algorithme classique de reconnaissance vocale, n'utilisant pas le mécanisme de notre invention. Au démarrage du décodage, la situation est celle de la figure 6: On voit qu'au démarrage de l'analyse de la phrase, le moteur de reconnaissance pense être en présence de six possibilités. Les deux premières commencent toutes deux par le symbole , et leur traitement sera exactement identique, jusqu'à apparition de l'alternative réelle portant sur le second terme. Ainsi, jusqu'à ce point, l'espace de stockage utilisé dans l'algorithme nbest pour conserver les pistes les plus prometteuses comportera en double chaque hypothèse de recherche. Si par ailleurs, le groupe est assez complexe et qu'un élagage intervient avant apparition des termes différenciateurs qui suivent , alors l'algorithme 'n-best-search' ne sera en fait plus que 'n/2 bestsearch', chaque voie analysée étant dupliquée. L'exemple donné porte sur une permutation à trois termes. Pour une permutation à quatre termes ou plus, les mêmes remarques s'appliquent avec des effets encore plus néfastes sur l'algorithme de reconnaissance. La perplexité vue par le moteur de reconnaissance est bien supérieure à la perplexité réelle du modèle de langage. La figure 7b illustre le traitement de l'art antérieur: six alternatives existent au rang i, au lieu de trois. Cet exemple montre que notre invention apporte par rapport à la méthode traditionnelle deux avantages importants, même si elle n'augmente pas l'expressivité du modèle de langage: Au lieu de stocker des arbres syntaxiques décrivant une permutation, qui peuvent être très consommateurs de mémoire, on ne stocke que les termes apparaissant dans la permutation, plus des variables de type simple qui marquent l'activation éventuelle du groupe syntaxique au cours de l'analyse n- best du moteur de reconnaissance. Le traitement syntaxique par grammaire BNF des permutations n'est pas adapté à l'algorithme n-best search imposé par la partie acoustique du traitement de reconnaissance vocale: une même hypothèse d'analyse est considérée plusieurs fois, et le n-best n'est le plus souvent qu'un n/mbest, m dépendant du nombre de termes impliqués dans la permutation. Le nouveau modèle de langage présenté est destiné aux applications de dialogue vocal homme machine à large vocabulaire, pour les langages fortement infléchis ou pour la reconnaissance de la parole spontanée. Le langage basé sur les règles ci-dessus n'est pas plus expressif ou plus puissant qu'un langage de type BNF exprimé à l'aide des règles classiques, lorsque l'ensemble des phrases grammaticales est fini. L'intérêt de l'invention ne porte donc pas sur l'expressivité du nouveau langage, mais sur les avantages au niveau du traitement, par l'algorithme du moteur de reconnaissance vocale, des règles syntaxiques. Moins de mémoire est requise pour le traitement. Par ailleurs, la nouvelle règle syntaxique permet une plus grande facilité d'écriture de la grammaire. Le procédé étant basé sur un automate à pile, il est particulièrement adapté, à la différence des solutions actuelles, aux applications embarquées et à faible coût, telles que les applications dans des appareils d'électronique grand public. Revendications 1. Dispositif de reconnaissance vocale comportant un processeur audio (2) pour l'acquisition d'un signal audio et un décodeur linguistique (6) pour déterminer une séquence de mots correspondant au signal audio, caractérisé en ce que le décodeur linguistique comporte un modèle de langage (8) défini à l'aide d'une grammaire comprenant une règle syntaxique de permutation sans o répétition de symboles. 2. Dispositif selon la revendication 1, caractérisé en ce que la règle syntaxique de permutation de symboles comporte une liste de symboles et le cas échéant des expressions de contraintes d'ordre des symboles. 3. Dispositif selon l'une des revendications 1 ou 2, caractérisé en ce que le décodeur linguistique comporte un moteur de reconnaissance (9) qui, lors de l'affectation de symboles d'une permutation à une suite de termes d'une phrase, choisit un symbole à affecter à un terme donné uniquement parmi les symboles de la permutation n'ayant pas été affectés précédemment. 4. Dispositif selon la revendication 3, caractérisé en ce que le moteur de reconnaissance met en oeuvre un algorithme de type 'Beam Search ou 'n- best'.