Chapitre 3
Outils

3.1 Introduction

Deux points importants sont à retenir des chapitres précédents :

1. tout d’abord que le processus de compréhension se base sur la transcription du module RAP pour extraire le sens de l’énoncé utilisateur ;
2. deuxièmement, la compréhension se base dans la plupart des cas dans les systèmes de dialogue sur des unités conceptuelles élémentaires correspondant à des portions de phrases ayant un sens unitaire pour le système.

Nous proposons dans les travaux de cette thèse une architecture de décodage conceptuel, i.e. une méthode permettant de tenir compte de ces concepts dans la génération de la transcription. La détection des concepts dans une intervention utilisateur se fait généralement par une analyse à base de grammaire. Nous utiliserons ce formalisme et en particulier le formalisme des grammaires régulières encodées sous la forme d’automate à états fini pour effectuer cette opération. Le chapitre 3.2 introduit cette notion de modélisation formelle du langage. Le chapitre 3.4 présente les outils qui seront utilisés pour implémenter cette modélisation, à savoir les automates à états fini.

Plusieurs articles ont montré, [Schapire et Singer, 2000, Haffner et al., 2003, Karahan et al., 2003, Tur et al., 2004], que les outils de classification de texte (les classifieurs à large-marge comme les machines à support vectoriels (SVM) ou les implémentations de l’algorithme de boosting peuvent être un moyen efficace pour détecter des concepts notamment dans les systèmes de routage d’appel, par exemple [Gorin et al., 1997]. Les arbres de décisions sémantiques (SCT-Semantic Classification Tree) décrits dans [Kuhn et De Mori, 1995] ont également été utilisés dans des systèmes de dialogue similaires à ceux présentés dans ces travaux (application ATIS). Cette approche de détection de concepts a 2 principaux avantages :

• premièrement, l’intervention humaine est limitée dans le sens où aucun mot-clef ni aucune grammaire ne doivent être défini afin de caractériser un concept. Néanmoins, un corpus d’entraînement doit nécessairement être annoté ;
• deuxièmement, les classifieurs sont plus robustes au bruit généré par les erreurs du système de transcription automatique de la parole et aux effets dus à la parole spontanée parce qu’ils reposent sur des conditions suffisantes. Ils peuvent être directement entraînés sur les sorties du module RAP et donc modéliser ce bruit, alors que les grammaires génèrent habituellement des phrases correctes du language.

Nous proposons d’effectuer la détection de concepts au travers de ces méthodes. Le chapitre 3.5 introduit alors les notions de classification que nous utiliserons.

3.2 Les langages formels

3.2.1 Introduction

Bien que les applications de reconnaissance de la parole fonctionnent généralement au moyen de modèles de langage statistiques, plusieurs travaux présentent de nouvelles voies intermédiaires dans le but de combiner l’approche formelle et l’approche statistique afin de tirer parti du meilleur de ces 2 approches. [Estève, 2002] propose par exemple des modèles de langages hybrides s’appuyant sur l’intégration de connaissances linguistiques a priori (grammaires locales) dans un modèle statistique. Cette section présente l’approche formelle de modélisation du langage.

3.2.2 Définition

Soit un alphabet V , un ensemble fini de symboles ou de caractères, une chaîne w = (v₁,v₂,…,v_n) un n-uplet d’éléments appartenant à V , l’opération de base sur les chaînes, la concaténation :

Sur V ^∗ la concaténation notée || est une opération

Un langage formel L construit à l’aide d’un vocabulaire V est un sous-ensemble du monoïde libre V ^∗. Un langage L sur V ^∗ : L ⊆ V ^∗.

3.2.3 Les langages réguliers

L’ensemble des langages réguliers sur un vocabulaire V peut-être défini récursivement par les règles suivantes :

• le langage vide ϕ est un langage régulier ;
• le langage {𝜖} est un langage régulier ;
• pour tout x de V , {x} est un langage régulier ;
• si R₁ et R₂ sont des langages réguliers alors : R₁ ∪ R₂, R₁.R₂ et R₁^∗ sont des langages réguliers.

Notons que certains langages ne sont pas réguliers, comme par exemple le langage {aⁿ.bⁿ|n > 0} défini sur le vocabulaire {a,b}.

3.2.4 Expressions régulières

Les expressions régulières fournissent une autre méthode de description des langages réguliers. Les expressions régulières (E.R.) sur un alphabet V et les langages qu’elles décrivent sont définis récursivement de la manière suivante :

• 𝜖 est une E.R. qui décrit le langage {𝜖} ;
• si a ∈ V , alors a est une E.R. qui décrit {a} ;
• si r et s sont des E.R. qui décrivent respectivement les langages R et S :
  • alors (r)|(s) est une E.R. décrivant R⋃ S ;
  • alors (r)(s) est une E.R. dénotant RS ;
  • alors (r)^∗ est une E.R. décrivant R^∗ ;
  • alors (r)⁺ est une E.R. décrivant R⁺ ;
• il n’y a pas d’autres expressions régulières.

Remarques : pour économiser des parenthèses, par convention, on établit les priorités décroissantes suivantes : ∗, concaténation, |.

Exemple : considérons le vocabulaire suivant V _fin = {f,i,n}, le langage L_fin = {(f|i|n)^∗fin} = {fin,ffin,niffin,iiiifin,…} sur V _fin^∗ est un langage régulier où toutes les chaînes appartenant au langage sont composées de n’importe quelle chaîne composée des symboles du vocabulaire {f,i,n}, mais se terminant par la chaîne « fin ».

3.3 Grammaires formelles

3.3.1 Définition

Si un langage est fini, on peut le définir en listant l’ensemble des chaînes le composant : définition en extension. Si le langage est infini, la définition extensive est impossible, il est nécessaire d’avoir recours à une définition en compréhension. Le but est de trouver un moyen de spécifier un langage. Une grammaire formelle permet avec un nombre fini de règles de générer un langage donné.

[Chomsky, 1957, Chomsky, 1965] définit une grammaire G comme un quadruplet G = (V _T,V _N,R,A), avec :

• V _T est un ensemble fini de symboles terminaux : l’alphabet sur lequel le langage généré est défini.
• V _N est l’ensemble des symboles non-terminaux
• R ⊆ (V ⁺ × V ^∗) où V = V _T ⋃ V _N est un ensemble fini de règles de productions (ou règles de réécriture). Les règles sont donc de la forme α → β où α ∈ V ⁺ et β ∈ V ^∗.
• A ∈ V _N appelé l’Axiome, est le symbole de départ

3.3.2 Classification de Chomsky

Chomsky a effectué une classification des grammaires formelles (appelée « hiérarchie de Chomsky ») en différents types selon leur capacité descriptive, c’est à dire selon la complexité des langages qu’elles engendrent. Les grammaires sont habituellement divisées en 4 types selon les contraintes posées sur les règles de productions :

• Aucune restriction sur les règles.
• Grammaires sensibles au contexte. Les règles doivent satisfaire la condition |α| ≤ |β|. Cela signifie intuitivement que le membre de droite doit contenir au moins autant de symboles que le membre de gauche.
• Grammaires hors-contexte. Toutes les règles doivent avoir la forme A → β où A ∈ V _N. Intuitivement, cela signifie donc qu’une grammaire est hors-contexte si le membre de gauche de chaque règle est constitué d’un seul symbole non-terminal.
• Grammaires régulières. Toutes les règles doivent avoir une des deux formes suivantes : A → μB ou A → μ dans le cas des grammaires « régulières à gauche », A → Bμ ou A → μ dans le cas des grammaires « régulières à droite » avec A,B ∈ V _N et μ ∈ V _T.

La relation entre ces 4 types de grammaire est bien sûr la suivante :

Les grammaires hors contexte sont les plus utilisées pour le traitement du langage naturel, bien qu’il ait été prouvé que celui-ci n’est pas engendré par une grammaire de ce type [Pullum et Gazdar, 1982]. Cette utilisation répandue vient du bon compromis existant entre la capacité de description des grammaires hors-contexte et les restrictions qu’elles induisent au niveau de l’analyse grammaticale : ces restrictions permettent une analyse efficace, et la puissance de description des grammaires hors-contexte permet de décrire une grande partie de la structure d’un langage. Pour des applications restreintes concernant le traitement du langage naturel, les grammaires régulières sont préférées aux grammaires hors-contexte : puisque la partie visée du langage est déterminée, la capacité de description des grammaires régulières s’avère suffisante. Notamment dans le contexte de dialogue où nous avons à faire à des phrases courtes, il est aisément possible d’obtenir une grammaire régulière à partir d’une hors-contexte. De plus, leur analyse grammaticale est plus efficace, en terme de rapidité, que celle des grammaires hors-contexte.

Dans la pratique, les langages réguliers ne sont donc pas utilisables pour décrire des phénomènes trop complexes, mais ils se prêtent facilement à la modélisation de phénomènes de portée réduite et localisée. Tout langage régulier peut être engendré par une grammaire régulière. Un exemple de grammaire régulière engendrant le langage de l’exemple 3.2.4 est la suivante :

À chacune des grammaires présentées, peut être associé un type d’automate qui accepte le langage engendré par cette grammaire. Ces automates sont des machines virtuelles qui permettent de signifier l’appartenance ou non d’une phrase à un langage. Le tableau 3.1 établit la correspondance entre les quatre grands types de grammaires présentées précédemment et quatre sortes d’automates.

Les grammaires utilisées dans le traitement effectué par les systèmes de dialogue sont généralement des grammaires régulières et hors-contexte. Dans un contexte de dialogue oral où les phrases sont finies et de taille limitée, il est possible d’obtenir une approximation d’une grammaire hors-contexte par une grammaire régulière [Mohri et Nederhof, 2001]. Les automates à états fini sont alors appropriés pour représenter les connaissances linguistiques dans les systèmes de dialogue et sont présentés dans la section suivante.

3.4 Automates À États Fini

3.4.1 Définition

Les automates sont des machines qui prennent en entrée une chaîne de symboles et qui effectuent un algorithme de reconnaissance de la chaîne. La chaîne est reconnue par l’automate si et seulement si celui-ci part d’un état initial, lit tous les symboles de la chaîne, puis s’arrête dans un état final. Le langage accepté par un automate à états fini est l’ensemble des chaînes dont les symboles font passer de l’état initial de l’automate jusqu’à un de ses états terminaux par une succession de transition utilisant tous ces symboles dans l’ordre.

Plus formellement, un automate à états fini est un quintuplet A = (Q,V,δ,s,F) où :

• Q est un ensemble fini d’états ;
• V est un ensemble fini de symboles (l’alphabet (d’entrée) ;
• δ : Q × (V ∪{𝜖}) → Q est la fonction (totale) de transition ;
• s ∈ Q est l’état initial (ou de départ) ;
• F ⊆ Q est un sous-ensemble de Q, les états accepteurs (ou terminaux).

δ est la fonction de transition de l’automate. δ(e,a) = e^′ indique que si l’automate est dans l’état e et qu’il rencontre le symbole a, il passe dans l’état e^′. De plus, pour tout e de Q, δ(e,𝜖) = e.

Un automate à états fini possède les propriétés suivantes :

• le langage accepté par un automate à état fini est un langage régulier ;
• à partir de toute expression régulière r décrivant un langage (régulier) R il est possible de construire un automate à état fini acceptant ce même langage ;
• à partir de tout automate à état fini acceptant un langage (régulier) R il est possible de construire un automate à état fini déterministe acceptant le même langage.

Un automate associé à l’expression régulière 3.2.4 est visible dans la figure 3.1. Cet automate à état fini est non-déterministe. C’est à dire qu’il existe au moins un couple, formé d’un état et d’un symbole, qui admette plus d’une image par la fonction de transition (δ(1,f) = 1 et δ(1,f) = 2 dans l’exemple de la figure 3.1). Dans ce cas l’automate doit faire des choix pour progresser. Un automate non-déterministe reconnaît une phrase si parmi tous les choix possibles pour l’analyser, il en existe au moins un qui le laisse dans un état final. L’inconvénient d’un automate non-déterministe est d’analyser les chaînes plus lentement que les automates déterministes. En effet, si un mauvais choix est pris dans une transition, il faut revenir en arrière jusqu’à ce choix pour parvenir à la reconnaissance de la chaîne. Par exemple la chaîne « ffin », à la lecture du premier symbole deux possibilités sont offertes, passage à l’état 1, ou rester en l’état 0. Si l’on passe à l’état 1, nous sommes dans un état ou il est alors impossible d’effectuer de transition, or la chaîne n’est pas encore entièrement lue, dans ce cas il faut donc revenir à l’état 0 et choisir de rester. La complexité de la reconnaissance d’une chaîne par un automate non-déterministe est dite exponentielle. Si, à chaque état et pour chaque symbole, existent n transitions possibles, la reconnaissance d’une chaîne de longueur p demandera jusqu’a n^p transitions. Un algorithme permet de déterminiser tout automate à états fini, c’est à dire de faire en sorte que sa fonction de transition n’admette pour tout état et tout symbole, qu’au plus un état dans lequel l’automate peut transiter. La version déterministe de l’automate de la figure 3.1 est visible dans la figure 3.2.

3.4.2 Définition d’un FSM et algorithmes associés

Toutes les opérations présentées sur les FSMs sont faites avec la suite d’outils d’AT&T ([Mohri et al., 1997]). Suivant les définitions utilisées dans [Mohri et al., 2002], les accepteurs et transducteurs utilisés dans cette étude sont définis en accord avec la notion générale algébrique du semi-anneau (semiring). Un semi-anneau K est un ensemble 𝕂 avec une opération associative et commutative ⊕, une opération associative ⊗, ainsi que deux éléments neutres 0 et 1 : K = (𝕂,⊕,⊗,0,1). Les poids associés aux hypothèses générées par le module de reconnaissance automatique de la parole (RAP) représentent les probabilités codées en −log. Le semi-anneau correspondant est appelé le log semiring : (ℝ,+,.,0,1). Lorsque sont utilisées les probabilités en −log pour une approximation du meilleur chemin, un semi-anneau tropical (tropical semiring) est utilisé : (ℝ₊ ∪∞,min,+,∞,0).

Les accepteurs et transducteurs sont définis comme suit :

Soient Σ un alphabet de symboles d’entrées ; Δ un alphabet de symboles de sorties ; 𝜖 un symbole vide ; Q un ensemble d’états (avec I=état initial et F=états terminaux) ; 𝕂 un semi-anneau ; E un ensemble de transitions défini comme : E ⊆ Q × (Σ ∪{𝜖}) × (Δ ∪{𝜖}) × 𝕂 × Q ; w une fonction de pondération : w : Q → 𝕂.

Si Path(R₁,x,R₂) est un ensemble de chemins de R₁ ⊆ Q à R₂ ⊆ Q avec un symbole d’entrée x et Path(R₁,x,y,R₂) un ensemble de chemins dans Path(R₁,x,R₂) avec un symbole de sortie y, alors :

• Accepteur  A = (Σ,Q,I,F,E) avec pour tout x ∈ Σ :
  

  (3.1)

• Transducteur  T = (Σ,Δ,Q,I,F,E) avec pour tout x ∈ Σ^∗,y ∈ Δ^∗ :
  

  (3.2)

et w[π] = w[t₁] ⊗ w[t₂] ⊗… ⊗ w[t_n] pour un chemin π fait des transitions suivantes t₁,t₂,…,t_n.

Différentes opérations fondamentales sur les FSMs utilisées dans ce document sont présentées :

L’union

Soit l’automate A₁ acceptant un langage L₁ ⊆ V ^∗ (exemple figure 3.3) et un automate A₂ acceptant un langage L₂ ⊆ V ^∗ (exemple figure 3.4), l’automate A_1∪2 (exemple figure 3.5) résultant de l’union des deux automates A₁ et A₂ au moyen de l’opération :

L’intersection

Soit l’automate A₁ acceptant un langage L₁ ⊆ V ^∗ (exemple figure 3.3) et un automate A₂ acceptant un langage L₂ ⊆ V ^∗ (exemple figure 3.4), l’automate A_1∩2 (exemple figure 3.7) résultant de l’intersection des deux automates A₁ et A₂ au moyen de l’opération suivante :

La différence

Soit l’automate A₁ acceptant un langage L₁ ⊆ V ^∗ (exemple figure 3.3) et un automate A₂ acceptant un langage L₂ ⊆ V ^∗ (exemple figure 3.4), l’automate A_1∩2 (exemple figure 3.8) résultant de la différence des deux automates A₁ et A₂ au moyen de l’opération suivante :

La projection

L’opération de projection à partir d’un transducteur permet d’obtenir un accepteur de même topologie, avec les transitions étiquetées comme les entrées du transducteur si cette projection se fait sur les entrées, où comme les sorties si cette projection se fait sur les sorties :

La composition

La composition est une opération entre deux transducteurs. Elle permet d’aligner les symboles de sortie du premier transducteur (exemple figure 3.9) avec les symboles d’entrée du second (exemple figure 3.10) et de produire un transducteur dont les entrées sont celles du premier transducteur et les sorties celles du second (exemple figure 3.11).

[T₁ ∘ T₂](x,y) = ⊕ _z[T₁](x,z) ⊗ [T₂](z,y)

3.5 Méthodes de classification

3.5.1 Les arbres de décision sémantique

L’application des arbres de décisions sémantiques au langage naturel a été introduite dans [Kuhn et De Mori, 1995]. La nouveauté des algorithmes de SCT réside dans la construction des questions pour l’apprentissage de l’arbre de décision. Cette construction se fait à partir d’un ensemble d’expressions régulières Π₀ associé à la racine de l’arbre :
soient V , l’ensemble des mots du vocabulaire du corpus d’entraînement C₀, w ∈ V n’importe quel mot du vocabulaire, le symbole « + » indiquant la présence de n’importe quelle séquence de mots non vide dans l’expression régulière, Π₀ contient les quatre éléments suivants :

L’ensemble des questions appliquées à la racine, N₀, est obtenu en considérant toutes les expressions régulières Π₀ possibles appliquées sur tous les w du vocabulaire V selon les quatre éléments de Π₀. Il y a donc 4 ×|V | possibilités où |V | représente la taille du vocabulaire. Chaque expression régulière est alors testée à la racine de l’arbre. Le critère d’impureté de Gini est utilisé pour choisir la meilleure question à chaque nœud N_i. Soient les k classes c₁,c₂,...,c_k dont les probabilités de répartition sont p₁,p₂,...,p_k alors le critère de Gini du nœud N_i s’exprime par :

La meilleure question pour N_i est celle qui apporte la plus grande variation d’impureté entre N_i et ses fils. Si les deux enfants de N_i sont notés N_i+1^oui et N_i+1^non, la variation d’impureté Δ_i est alors définie par :

Par exemple, si +W est l’expression régulière qui maximise Δi, la phrase qui est acceptée par cette expression régulière fait partie d’un corpus C₁^oui associé au fils de la branche du corpus nommé OUI. Les autres font partie du corpus C₁^non associées au fils nommé NON. L’ensemble des questions associé à C₁^oui est obtenu par la substitution suivante : + → Π₀ nous menant à Π₀W. En général, étant donnée une expression régulière : +W₁ + W₂ + … + W_i + … où W_i est déjà déterminé par une série de mots, les questions sont générées en remplaçant chaque + par Π₀, c’est à dire :

Soit | + | le nombre de symboles + dans l’expression régulière originale, le nombre de cas est alors : 4 ×| + |×|V |.

Lorsque le SCT est construit, il prend des décisions sur la base de règles de classification statistique apprises sur ces expressions régulières. Les règles apprises par le SCT sont donc résistantes aux diverses formulations du locuteur car elles ne dépendent que d’un petit nombre de mots. En revanche, si un seul des mots composants de la règle est mal reconnu, elle ne s’applique pas.

La figure 3.12 est un exemple d’arbre.

3.5.2 Les algorithmes de Boosting

Le Boosting est une méthode générale pour améliorer les performances de n’importe quel algorithme d’apprentissage. Par définition, un algorithme de Boosting peut théoriquement transformer un algorithme d’apprentissage basique (appelé « weak learner ») avec des performances juste un peu meilleures que le hasard en un algorithme très performant. Le principe de ces algorithmes de Boosting est re-pondérer à plusieurs reprises les exemples d’apprentissage et de refaire tourner l’algorithme d’apprentissage sur ces exemples re-pondérés. Les exemples mal classés sont re-pondérés à la hausse tandis que les biens classés sont re-pondérés à la baisse. Ainsi, le boosting force cet algorithme à concentrer ses efforts d’apprentissage sur les exemples les plus difficiles. L’hypothèse finale est un vote pondéré des différentes hypothèses obtenues à chaque instance de l’algorithme d’apprentissage. L’algorithme AdaBoost [Freund et Schapire, 1996] est présenté dans la figure 3.13.

3.5.3 Les Machines à Vecteur de Support, SVMs

Les SVMs, proposés par Vapnik ([Vapnik, 1982, Vapnik, 1995]), sont une classe d’algorithmes d’apprentissage qui ont été utilisés avec succès dans plusieurs tâches d’apprentissage. Ils permettent de construire un classifieur à valeurs réelles qui découpent le problème de classification en 2 sous-problèmes : transformation non-linéaire des entrées et choix d’une séparation linéaire optimale. Ils offrent en particulier une bonne approximation du principe de minimisation du risque structurel. L’idée de la minimisation du risque structurel est de trouver une hypothèse h pour laquelle l’erreur vraie minimale est garantie. L’erreur vraie de h est la probabilité que h fasse une erreur sur un exemple non-vu et extrait aléatoirement du corpus de test.
Le premier sous-problème à traiter est donc celui de travailler dans un espace où les données soient linéairement séparables. Les données sont alors projetées dans un espace de grande dimension par une transformation basée sur un noyau (voir figure 3.14). Le noyau est une fonction qui retourne la valeur du produit scalaire des images des 2 arguments K(x₁,x₂) = . Il peut être linéaire, polynomial ou gaussien .

Le deuxième sous-problème est traité dans cet espace transformé. Les classes y sont séparées par des classifieurs linéaires qui déterminent un hyper-plan optimal. L’hyper-plan optimal est celui qui sépare correctement toutes les données et qui maximise la marge, la distance du point le plus proche à l’hyper-plan (représentée par d dans la figure 3.15). Les hyperplans peuvent être déterminés au moyen d’un nombre de points limité qui seront appelés les « vecteurs supports ».

Pour appliquer les SVMs sur du texte, la technique la plus simple employée est celle du sac de mots où tous les mots sont représentés par des chiffres. Le lexique complet représente alors un vecteur et chaque phrase sera codée par ce vecteur.
L’utilisation des SVMs dans ce cas est alors pleinement justifiée [Joachims, 1998].

• Ils ont le potentiel pour gérer ce grand nombre de données.
• Le vecteur représentant chaque phrase contient peu de données qui ne sont pas des 0. Les SVMs sont adaptés aux problèmes de ce type (vecteurs creux).
• La plupart des problèmes de catégorisation de textes sont linéairement séparables.