Université du Québec
Institut National de la Recherche Scientifique
Centre Énergie Matériaux Télécommunications

# ANALYSE SÉMANTIQUE POUR SYSTÈMES DE DIALOGUE VERBAUX

Par

Yacine Benahmed

Thèse présentée pour l'obtention du grade de
Philosophiæ Doctor (Ph. D.) en télécommunications

## Jury d'évaluation

Président du jury et
examinateur interne

Prof. Falk, Tiago
Institut National de la Recherche
Scientifique

Examinateur externe

Prof. Cardinal, Patrick
École de technologie supérieure

Examinateur externe

Prof. Tadj, Chakib
École de technologie supérieure

Directeur de recherche

Prof. O'Shaughnessy, Douglas
Institut National de la Recherche
Scientifique

Codirecteur de recherche

Prof. Selouani, Sid-Ahmed
Université de Moncton

© Droits réservés de Yacine Benahmed 2018
<figure><img src="image_1.png" /></figure>
DECLARATION

I hereby declare that except where specific reference is made to the work of others, the contents of
this dissertation are original and have not been submitted in whole or in part for consideration for
any other degree or qualification in this, or any other University. This dissertation is the result of
my own work and includes nothing which is the outcome of work done in collaboration, except
where specifically indicated in the text.

Yacine Benahmed
<figure><img src="image_2.png" /></figure>
# REMERCIEMENTS

J’aimerais remercier mon directeur de thèse Prof. Douglas D. O’Shaughnessy ainsi que mon codirecteur de thèse Prof. Sid Ahmed Selouani pour leurs conseils et leur support tout au long de cette thèse.

J’aimerais aussi remercier les membres du comité d’évaluation Prof. Tiago Falk, Prof. Patrick Cardinal et Prof. Chakib Tadj d’avoir accepté de donner de leur temps malgré leur horaire chargé afin d’évaluer ce travail doctoral ainsi que pour leurs conseils et suggestions.

J’aimerais aussi remercier ma famille et ma belle-famille pour leurs encouragements et leur soutien tout au long de ce processus et de m’avoir encouragé à perséverer malgré les nombreuses difficultés rencontrées.

J’aimerais de plus remercier Emmanuelle d’avoir pris le temps de faire un véritable travail d’édition pour cette thèse, ce qui a permis de la rendre beaucoup plus lisible étant donné mes tendances aux phrases longues et aux tournures de phrases non conventionnelles...

Je voudrais aussi remercier mes amis pour m’avoir tenu dans le droit chemin et de m’avoir constamment demandé « pis, quand-est-ce tu finis ? », ce à quoi je peux maintenant répondre « là ».

Finalement, j’aimerais remercier ma conjointe, Anne Fauré, que j’ai rencontrée durant mon parcours et qui se retrouvait dans le même bateau que moi. Merci de m’avoir prêté ton oreille et pour toutes tes lectures et relectures de mon texte. Finalement, merci pour le plus beau cadeau que tu pouvais nous faire, notre fils Michel-Ange.
<figure><img src="image_3.png" /></figure>
# LISTE DES PUBLICATIONS

## Contributions principales à la these

1. Y. Benahmed, S.-A. Selouani, D. O'Shaughnessy, et A. H. Abolhassani, « Real-Life Speech-Enabled System to Enhance Interaction with RFID Networks in Noisy Environments », dans *International Conference on Acoustics, Speech and Signal Processing*, Prague, Czech Republic, 2011, p. 17811784.

2. Y. Benahmed, S.-A. Selouani, et D. O'Shaughnessy, « Ontology-based pattern generator and root semantic analyser for spoken dialogue systems », dans *Electrical & Computer Engineering (CCECE), 2012 25th IEEE Canadian Conference on*, 2012, p. 14.

3. Y. Benahmed, S.-A. Selouani, et D. O'Shaughnessy, « A Bin-Based Ontological Framework for Low-Resource N-Gram Smoothing in Language Modelling », dans *Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference on*, 2014, p. 49184922.

4. Y. Benahmed, S.-A. Selouani, et D. O'Shaughnessy, « Evaluation of Graph Metrics for Optimizing Bin-Based Ontologically Smoothed Language Models », dans *European Signal Processing Conference*, Budapest, Hongrie, 2016.

## Contributions secondaires

5. S. A. Selouani, T.-H. Lê, Y. Benahmed, et D. O'Shaughnessy, « Enhanced Speech-Enabled Tools for Intelligent and Mobile E-Learning Applications », *Technologies Shaping Instruction and Distance Education: New Studies and Utilizations: New Studies and Utilizations*, p. 147165, 2010.

6. Ayed, S.-A. Selouani, M. Kardouchi, et Y. Benahmed, « Radiological image classification using HMMs and Shape contexts », dans *Information Science, Signal Processing and their Applications (ISSPA), 2012 11th International Conference on*, 2012, p. 87-91.
7. Y. Benahmed, S.-A. Selouani, et D. O’Shaughnessy, « Effects of discriminative training on the RACAD corpus of the French language spoken in the Canadian province of New-Brunswick », dans *Information Science, Signal Processing and their Applications (ISSPA), 2012 11th International Conference on*, 2012, p. 695699.

8. S. Gharsellaoui, A. O. Dahmane, Y. Alotaibi, S. A. Selouani, A. B. Ayed, et Y. Benahmed, « A Rhythm-Based Analysis of Arabic Native and Non-Native Speaking Styles », *International Journal of Signal Processing Systems*, vol. 1, n° 2, p. 202207, 2013.
# RÉSUMÉ

Les modèles de langages statistiques font partie intégrante de nombreuses applications telles que la reconnaissance automatique de la parole, la reconnaissance automatique de l'écriture, la saisie prédictive, la traduction automatique du langage, etc. Malgré les développements récents dans le domaine des réseaux de neurones profonds, les N-grammes demeurent tout de même pertinentes dans des domaines où les ressource linguistiques ou computationnelles sont limitées. L'objectif de cette thèse est de présenter un nouvel algorithme de lissage des N-grammes utilisant l'information sémantique lattente aux ontologies. Comme le langage offre une très grande flexibilité dans sa façon d'exprimer une idée, nous utiliserons les relations sémantiques entre les N-grammes observées et les N-grammes non-observées afin d'estimer les probabilités d'observation de ces dernières dans de nouvelles conditions. Nos résultats démontrent qu'il est possible d'obtenir une réduction de 0,93 bit de l'entropie du modèle de langage. Par ailleurs, afin d'optimiser ces modèles de langages, nous proposons d'évaluer la performance de divers algorithmes évolutionnaires. Nos résultats montrent que l'optimisation par algorithmes génétiques permet de couvrir une plus grande partie de l'espace de recherche, au coût d'une plus grande variance dans la solution obtenue. Pour sa part, l'optimisation par essais particulaires fait preuve d'une moins grande variance dans les solutions obtenues, tout en demeurant aussi performante que l'optimisation par algorithme génétique.

**Mots clés** : Modèles de langage, ontologies, n-grammes, reconnaissance automatique de la parole, algorithmes évolutionnaires.
ABSTRACT

Statistical language models are an integral part of many applications such as automatic speech
recognition, automatic recognition of writing, predictive input, automatic translation of the
language, and so on. Despite recent developments in the field of deep neural networks, N-grams
remain relevant in areas where linguistic or computational resources are limited. The objective of
this thesis is to present a new algorithm of smoothing N-grams using the semantic information
latent to the ontologies. Since language offers a very high degree of flexibility in the way it
expresses an idea, we will use the semantic relations between the observed N-grams and the non-
observed N-grams in order to estimate the observation probabilities of the observed N-grams in
new conditions. Our results show that it is possible to obtain a 0.93 bit reduction of the entropy of
the language model. Moreover, in order to optimize these language models, we propose to evaluate
the performance of various evolutionary algorithms. Our results show that optimization by genetic
algorithms makes it possible to cover a larger part of the research space at the cost of a greater
variance in the solution obtained. For its part, the optimization by particulate swarms shows less
variance in the solutions obtained, while remaining as efficient as the optimization by genetic
algorithm.

**Keywords:** Language models, ontologies, n-grams, automatic speech recognition, evolutionary algorithms.
TABLE DES MATIÈRES

<table><tr><td>DECLARATION</td><td>III</td></tr><tr><td>REMERCIEMENTS</td><td>V</td></tr><tr><td>LISTE DES PUBLICATIONS</td><td>VII</td></tr><tr><td>CONTRIBUTIONS PRINCIPALES À LA THESE</td><td>VII</td></tr><tr><td>CONTRIBUTIONS SECONDAIRES</td><td>VII</td></tr><tr><td>RÉSUMÉ</td><td>IX</td></tr><tr><td>ABSTRACT</td><td>X</td></tr><tr><td>TABLE DES MATIÈRES</td><td>XI</td></tr><tr><td>LISTE DES TABLEAUX</td><td>XVII</td></tr><tr><td>LISTE DES FIGURES</td><td>XIX</td></tr><tr><td>LISTE DES ACCRONYMES</td><td>XXIII</td></tr><tr><td>ANALYSE SÉMANTIQUE POUR SYSTÈMES DE DIALOGUE VERBAUX SYNTHÈSE</td><td>1</td></tr><tr><td>1 INTRODUCTION</td><td>2</td></tr><tr><td>1.1 LA MODÉLISATION DU LANGAGE</td><td>2</td></tr><tr><td>1.2 MOTIVATION</td><td>4</td></tr><tr><td>1.3 MISE EN CONTEXTE DES ARTICLES</td><td>9</td></tr><tr><td>1.3.1 Au-delà des articles</td><td>11</td></tr><tr><td>1.4 CONTRIBUTIONS DE LA THÈSE</td><td>12</td></tr><tr><td>1.5 ORGANISATION DU MANUSCRIT</td><td>13</td></tr><tr><td>2 MODÉLISATION DU LANGAGE</td><td>16</td></tr><tr><td>2.1 INTRODUCTION</td><td>16</td></tr><tr><td>2.2 MODÉLISATION DU LANGAGE POUR LA RECONNAISSANCE AUTOMATIQUE DE LA PAROLE</td><td>19</td></tr><tr><td>2.3 LES N-GRAMMES</td><td>22</td></tr><tr><td>2.4 LE LISSAGE STATISTIQUE</td><td>25</td></tr><tr><td>2.4.1 Lissage additif</td><td>25</td></tr><tr><td>2.4.2 Décompte de Good-Turing</td><td>28</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>2.4.3</td>
      <td>Lissage par interpolation (Jelinek et Mercer)</td>
      <td>31</td>
    </tr>
    <tr>
      <td>2.4.4</td>
      <td>Lissage par repli « backoff »</td>
      <td>34</td>
    </tr>
    <tr>
      <td>2.4.5</td>
      <td>Witten-Bell</td>
      <td>35</td>
    </tr>
    <tr>
      <td>2.4.6</td>
      <td>Décompte absolu (Absolute discounting)</td>
      <td>37</td>
    </tr>
    <tr>
      <td>2.4.7</td>
      <td>Kneser-Ney</td>
      <td>37</td>
    </tr>
    <tr>
      <td>2.4.8</td>
      <td>Kneser-Ney modifié (Modified Kneser-Ney)</td>
      <td>39</td>
    </tr>
    <tr>
      <td>2.4.9</td>
      <td>Basé sur les classes</td>
      <td>40</td>
    </tr>
    <tr>
      <td>2.5</td>
      <td>UN RÉSUMÉ D'AUTRES TECHNIQUES RÉCENTES DE LISSAGE</td>
      <td>41</td>
    </tr>
    <tr>
      <td>2.5.1</td>
      <td>Lissage bayésien</td>
      <td>41</td>
    </tr>
    <tr>
      <td>2.5.2</td>
      <td>Modèle de langage basé sur les réseaux de neurones</td>
      <td>44</td>
    </tr>
    <tr>
      <td>2.6</td>
      <td>ÉVALUATION DE LA PERFORMANCE DES MODÈLES DE LANGAGE</td>
      <td>48</td>
    </tr>
    <tr>
      <td>2.6.1</td>
      <td>Perplexité</td>
      <td>48</td>
    </tr>
    <tr>
      <td>2.6.2</td>
      <td>Taux d'erreur des mots (Word Error Rate)</td>
      <td>49</td>
    </tr>
    <tr>
      <td>3</td>
      <td>LISSAGE DES N-GRAMMES BASÉ SUR LES ONTOLOGIES</td>
      <td>52</td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>MISE EN CONTEXTE</td>
      <td>52</td>
    </tr>
    <tr>
      <td>3.1.1</td>
      <td>Générateur de motif et analyseur sémantique pour systèmes de dialogue verbaux</td>
      <td>53</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>LISSAGE ONTOLOGIQUE</td>
      <td>54</td>
    </tr>
    <tr>
      <td>3.2.1</td>
      <td>Les ontologies</td>
      <td>55</td>
    </tr>
    <tr>
      <td>3.2.2</td>
      <td>Bin-Based Ontological Smoothing</td>
      <td>57</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>MÉTHODOLOGIE EXPÉRIMENTALE</td>
      <td>58</td>
    </tr>
    <tr>
      <td>3.3.1</td>
      <td>Résultats expérimentaux</td>
      <td>59</td>
    </tr>
    <tr>
      <td>3.4</td>
      <td>THÉORIE DES RÉSEAUX</td>
      <td>60</td>
    </tr>
    <tr>
      <td>3.4.1</td>
      <td>Degré</td>
      <td>61</td>
    </tr>
    <tr>
      <td>3.4.2</td>
      <td>Hyperlink-Induced Topic Search</td>
      <td>62</td>
    </tr>
    <tr>
      <td>3.4.3</td>
      <td>PageRank</td>
      <td>63</td>
    </tr>
    <tr>
      <td>3.4.4</td>
      <td>Modularité</td>
      <td>64</td>
    </tr>
    <tr>
      <td>3.4.5</td>
      <td>Méthodologie expérimentale</td>
      <td>64</td>
    </tr>
    <tr>
      <td>3.4.6</td>
      <td>Résultats expérimentaux</td>
      <td>65</td>
    </tr>
    <tr>
      <td>4</td>
      <td>OPTIMISATION DE LA MODÉLISATION DU LANGAGE PAR LES ALGORITHMES ÉVOLUTIONNAIRES</td>
      <td>68</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>INTRODUCTION</td>
      <td>68</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>ALGORITHMES GÉNÉTIQUES</td>
      <td>70</td>
    </tr>
    <tr>
      <td>4.2.1</td>
      <td>Individus</td>
      <td>70</td>
    </tr>
    <tr>
      <td>4.2.2</td>
      <td>Génération</td>
      <td>70</td>
    </tr>
    <tr>
      <td>4.2.3</td>
      <td>Sélection</td>
      <td>71</td>
    </tr>
    <tr>
      <td>4.2.4</td>
      <td>Croisement</td>
      <td>74</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>4.2.5 Mutation</td>
      <td>76</td>
    </tr>
    <tr>
      <td>4.2.6 Critère d'arrêt</td>
      <td>78</td>
    </tr>
    <tr>
      <td>4.2.7 Algorithme général de l'optimisation par algorithme génétique</td>
      <td>78</td>
    </tr>
    <tr>
      <td>4.3 OPTIMISATION PAR ESSAIMS PARTICULAIRES</td>
      <td>80</td>
    </tr>
    <tr>
      <td>4.3.1 Inertie</td>
      <td>80</td>
    </tr>
    <tr>
      <td>4.3.2 Apprentissage individuel</td>
      <td>81</td>
    </tr>
    <tr>
      <td>4.3.3 Influence par le groupe</td>
      <td>81</td>
    </tr>
    <tr>
      <td>4.3.4 Influence de la société</td>
      <td>82</td>
    </tr>
    <tr>
      <td>4.3.5 Voisinage</td>
      <td>82</td>
    </tr>
    <tr>
      <td>4.3.6 Taux d'apprentissage</td>
      <td>82</td>
    </tr>
    <tr>
      <td>4.3.7 Algorithme général de l'optimisation par essais particuliers</td>
      <td>83</td>
    </tr>
    <tr>
      <td>4.4 ÉVALUATION ET COMPARAISON DE LA PERFORMANCE D'ALGORITHMES ÉVOLUTIONNAIRES POUR L'OPTIMISATION DES POIDS D'INTERPOLATION</td>
      <td>85</td>
    </tr>
    <tr>
      <td>4.4.1 L'analogie entre paramètres évolutionnaires et ceux du modèle de langage</td>
      <td>86</td>
    </tr>
    <tr>
      <td>4.4.2 Initialisation et paramètres de la population</td>
      <td>87</td>
    </tr>
    <tr>
      <td>4.4.3 Évaluation de la mutation, de la sélection et du taux de croisement</td>
      <td>88</td>
    </tr>
    <tr>
      <td>4.4.4 Paramètres de l'optimisation par algorithmes génétiques</td>
      <td>103</td>
    </tr>
    <tr>
      <td>4.4.5 Paramètres de l'optimisation par essais particuliers</td>
      <td>104</td>
    </tr>
    <tr>
      <td>4.4.6 Fonction objective</td>
      <td>105</td>
    </tr>
    <tr>
      <td>4.4.7 Résultats</td>
      <td>105</td>
    </tr>
    <tr>
      <td>4.5 ÉVALUATION DU TAUX D'ERREUR DES MOTS</td>
      <td>119</td>
    </tr>
    <tr>
      <td>4.6 DISCUSSION</td>
      <td>126</td>
    </tr>
    <tr>
      <td>ANALYSE SÉMANTIQUE POUR SYSTÈMES DE DIALOGUE VERBAUX ARTICLES</td>
      <td>129</td>
    </tr>
    <tr>
      <td>5 REAL-LIFE SPEECH-ENABLED SYSTEM TO ENHANCE INTERACTION WITH RFID NETWORKS IN NOISY ENVIRONMENTS</td>
      <td>130</td>
    </tr>
    <tr>
      <td>5.1 CONTRIBUTION DES AUTEURS</td>
      <td>130</td>
    </tr>
    <tr>
      <td>5.2 COMMENTAIRES DES ÉVALUATEURS</td>
      <td>131</td>
    </tr>
    <tr>
      <td>5.2.1 Évaluateur no 1</td>
      <td>131</td>
    </tr>
    <tr>
      <td>5.2.2 Évaluateur no 2</td>
      <td>131</td>
    </tr>
    <tr>
      <td>5.2.3 Évaluateur no 3</td>
      <td>131</td>
    </tr>
    <tr>
      <td>5.3 RÉSUMÉ</td>
      <td>132</td>
    </tr>
    <tr>
      <td>5.4 ABSTRACT</td>
      <td>133</td>
    </tr>
    <tr>
      <td>5.5 INTRODUCTION</td>
      <td>133</td>
    </tr>
    <tr>
      <td>5.6 SPEECH-ENABLED RFID SYSTEM</td>
      <td>134</td>
    </tr>
    <tr>
      <td>5.6.1 System details</td>
      <td>135</td>
    </tr>
    <tr>
      <td>5.6.2 Dialog interpreter</td>
      <td>136</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>5.7</td>
      <td>VRE SPEECH ENHANCEMENT TECHNIQUE</td>
      <td>136</td>
    </tr>
    <tr>
      <td>5.7.1</td>
      <td>Online VRE-KLT speech enhancement</td>
      <td>137</td>
    </tr>
    <tr>
      <td>5.8</td>
      <td>EXPERIMENTS AND RESULTS</td>
      <td>141</td>
    </tr>
    <tr>
      <td>5.8.1</td>
      <td>Evaluation of the dialog framework</td>
      <td>141</td>
    </tr>
    <tr>
      <td>5.8.2</td>
      <td>Evaluation of the KLT-VRE enhancement method</td>
      <td>141</td>
    </tr>
    <tr>
      <td>5.9</td>
      <td>CONCLUSION AND FUTURE WORK</td>
      <td>142</td>
    </tr>
    <tr>
      <td>6</td>
      <td>ONTOLOGY-BASED PATTERN GENERATOR AND ROOT SEMANTIC ANALYSER FOR SPOKEN DIALOGUE SYSTEMS</td>
      <td>145</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>CONTRIBUTION DES AUTEURS</td>
      <td>145</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>COMMENTAIRES DES ÉVALUATEURS</td>
      <td>146</td>
    </tr>
    <tr>
      <td>6.2.1</td>
      <td>Évaluateur no 1</td>
      <td>146</td>
    </tr>
    <tr>
      <td>6.2.2</td>
      <td>Évaluateur no 2</td>
      <td>146</td>
    </tr>
    <tr>
      <td>6.2.3</td>
      <td>Évaluateur no 3</td>
      <td>146</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>RÉSUMÉ</td>
      <td>147</td>
    </tr>
    <tr>
      <td>6.4</td>
      <td>ABSTRACT</td>
      <td>148</td>
    </tr>
    <tr>
      <td>6.5</td>
      <td>INTRODUCTION</td>
      <td>148</td>
    </tr>
    <tr>
      <td>6.6</td>
      <td>SPEECH-ENABLED RFID SYSTEM</td>
      <td>150</td>
    </tr>
    <tr>
      <td>6.6.1</td>
      <td>System details</td>
      <td>150</td>
    </tr>
    <tr>
      <td>6.6.2</td>
      <td>AIML-based dialog interpreter</td>
      <td>151</td>
    </tr>
    <tr>
      <td>6.7</td>
      <td>ONTOLOGIES IN NATURAL LANGUAGE PROCESSING</td>
      <td>153</td>
    </tr>
    <tr>
      <td>6.8</td>
      <td>ONTOLOGY-BASED SPEECH PATTERN GENERATOR</td>
      <td>154</td>
    </tr>
    <tr>
      <td>6.8.1</td>
      <td>Ontology</td>
      <td>154</td>
    </tr>
    <tr>
      <td>6.8.2</td>
      <td>Pattern generation and root semantic analysis algorithms</td>
      <td>154</td>
    </tr>
    <tr>
      <td>6.9</td>
      <td>EXPERIMENTS AND RESULTS</td>
      <td>156</td>
    </tr>
    <tr>
      <td>6.9.1</td>
      <td>Evaluation of the pattern generator</td>
      <td>156</td>
    </tr>
    <tr>
      <td>6.10</td>
      <td>CONCLUSION AND FUTURE WORK</td>
      <td>157</td>
    </tr>
    <tr>
      <td>7</td>
      <td>A BIN-BASED ONTOLOGICAL FRAMEWORK FOR LOW-RESOURCE N-GRAM SMOOTHING IN LANGUAGE MODELLING</td>
      <td>159</td>
    </tr>
    <tr>
      <td>7.1</td>
      <td>CONTRIBUTION DES AUTEURS</td>
      <td>159</td>
    </tr>
    <tr>
      <td>7.2</td>
      <td>COMMENTAIRES DES ÉVALUATEURS</td>
      <td>160</td>
    </tr>
    <tr>
      <td>7.2.1</td>
      <td>Meta évaluation no 1</td>
      <td>160</td>
    </tr>
    <tr>
      <td>7.2.2</td>
      <td>Évaluateur régulier no 2</td>
      <td>160</td>
    </tr>
    <tr>
      <td>7.2.3</td>
      <td>Évaluateur régulier no 3</td>
      <td>160</td>
    </tr>
    <tr>
      <td>7.3</td>
      <td>RÉSUMÉ</td>
      <td>163</td>
    </tr>
    <tr>
      <td>7.4</td>
      <td>ABSTRACT</td>
      <td>165</td>
    </tr>
    <tr>
      <td>7.5</td>
      <td>INTRODUCTION</td>
      <td>165</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>7.6 ONTOLOGIES</td>
      <td>167</td>
    </tr>
    <tr>
      <td>7.6.1 The WordNet ontology</td>
      <td>167</td>
    </tr>
    <tr>
      <td>7.7 ONTOLOGY-BASED N-GRAM SMOOTHING</td>
      <td>167</td>
    </tr>
    <tr>
      <td>7.7.1 Bin-Based Ontological Smoothing</td>
      <td>169</td>
    </tr>
    <tr>
      <td>7.7.2 Ontological smoothing algorithm</td>
      <td>170</td>
    </tr>
    <tr>
      <td>7.7.3 Ontology search algorithm for R related terms</td>
      <td>170</td>
    </tr>
    <tr>
      <td>7.8 EXPERIMENTS AND RESULTS</td>
      <td>171</td>
    </tr>
    <tr>
      <td>7.8.1 Limited resources experimental setup</td>
      <td>171</td>
    </tr>
    <tr>
      <td>7.8.2 Perplexity evaluation</td>
      <td>172</td>
    </tr>
    <tr>
      <td>7.8.3 Automatic speech recognition experiments</td>
      <td>174</td>
    </tr>
    <tr>
      <td>7.9 CONCLUSION AND DISCUSSION</td>
      <td>176</td>
    </tr>
    <tr>
      <td><b>8 EVALUATION OF GRAPH METRICS FOR OPTIMIZING BIN-BASED ONTOLOGICALLY SMOOTHED LANGUAGE MODELS</b></td>
      <td><b>177</b></td>
    </tr>
    <tr>
      <td>8.1 CONTRIBUTION DES AUTEURS</td>
      <td>177</td>
    </tr>
    <tr>
      <td>8.2 COMMENTAIRES DES ÉVALUATEURS</td>
      <td>178</td>
    </tr>
    <tr>
      <td>8.2.1 Évaluateur no 1</td>
      <td>178</td>
    </tr>
    <tr>
      <td>8.2.2 Évaluateur no 2</td>
      <td>178</td>
    </tr>
    <tr>
      <td>8.2.3 Évaluateur no 3</td>
      <td>179</td>
    </tr>
    <tr>
      <td>8.2.4 Évaluateur no 4</td>
      <td>179</td>
    </tr>
    <tr>
      <td>8.3 RÉSUMÉ</td>
      <td>180</td>
    </tr>
    <tr>
      <td>8.4 ABSTRACT</td>
      <td>181</td>
    </tr>
    <tr>
      <td>8.5 INTRODUCTION</td>
      <td>181</td>
    </tr>
    <tr>
      <td>8.5.1 Motivation</td>
      <td>182</td>
    </tr>
    <tr>
      <td>8.5.2 Contribution</td>
      <td>182</td>
    </tr>
    <tr>
      <td>8.6 BIN-BASED ONTOLOGICAL SMOOTHING</td>
      <td>183</td>
    </tr>
    <tr>
      <td>8.6.1 Ontological smoothing algorithm</td>
      <td>184</td>
    </tr>
    <tr>
      <td>8.6.2 Network Analysis</td>
      <td>185</td>
    </tr>
    <tr>
      <td>8.6.3 The WordNet ontology</td>
      <td>187</td>
    </tr>
    <tr>
      <td>8.6.4 Weighting adjustments</td>
      <td>187</td>
    </tr>
    <tr>
      <td>8.7 EXPERIMENTS AND RESULTS</td>
      <td>188</td>
    </tr>
    <tr>
      <td>8.7.1 Experimental Setup</td>
      <td>188</td>
    </tr>
    <tr>
      <td>8.7.2 Perplexity evaluation</td>
      <td>189</td>
    </tr>
    <tr>
      <td>8.7.3 Automatic speech recognition experiments</td>
      <td>190</td>
    </tr>
    <tr>
      <td>8.8 CONCLUSION AND DISCUSSION</td>
      <td>191</td>
    </tr>
    <tr>
      <td><b>9 CONCLUSION</b></td>
      <td><b>194</b></td>
    </tr>
    <tr>
      <td>9.1 CONCLUSIONS PRINCIPALES</td>
      <td>194</td>
    </tr>
  </tbody>
</table>
<table><tr><td>9.2 CONTRIBUTIONS PRINCIPALES</td><td>196</td></tr><tr><td>9.3 TRAVAUX FUTURS</td><td>196</td></tr><tr><td>RÉFÉRENCES</td><td>198</td></tr></table>
LISTE DES TABLEAUX

TABLEAU 2.1 : RÉSUMÉ DES COMPTES ORIGINAUX $C(wi)$, DES COMPTES AJUSTÉS $C + 1(wi)$, DES PROBABILITÉS ORIGINALES $P(wi)$, DES PROBABILITÉS AJUSTÉES $P + 1(wi)$ ET DES COMPTES RECONSTITUÉS, $C'wi$, À PARTIR DE CES DERNIÈRES. 26

TABLEAU 2.2 : TABLEAU DES COMPTES DU BIGRAMME. 26

TABLEAU 2.3 : PROBABILITÉS POUR TOUS LES BIGRAMMES POSSIBLES. 26

TABLEAU 2.4 : COMPTES LAPLACE AJUSTÉS POUR $\delta = 1$, LES COMPTES QUI ÉTAIENT ÉGAUX À 0 APPARAISSENT EN GRIS. 27

TABLEAU 2.5 : NOUVELLES PROBABILITÉS LISSÉES POUR $\delta = 1$. LES PROBABILITÉS POUR LES BIGRAMMES PRÉEXISTANTES SONT EN GRAS. 27

TABLEAU 2.6 : COMPTES RECONSTITUÉS DES BIGRAMMES. LES COMPTES QUI ÉTAIENT ÉGAUX À 0 APPARAISSENT EN GRIS. 27

TABLEAU 2.7 : FRÉQUENCE DES FRÉQUENCES DES COMPTES AJUSTÉS GOOD-TURING ET DES COMPTES AJUSTÉS KATZ POUR $k = 5$ DES UNIGRAMMES DU TEXTE LE PETIT PRINCE. 30

TABLEAU 2.8 : COMPTES ET PROBABILITÉS D'UN ÉCHANTILLON D'UNIGRAMMES AJUSTÉS SELON LE LISSAGE GOOD-TURING ET LE LISSAGE KATZ POUR $k = 5$ DU TEXTE LE PETIT PRINCE. 30

TABLEAU 2.9 : FRÉQUENCE DES FRÉQUENCES DES COMPTES AJUSTÉS SELON LE LISSAGE GOOD-TURING ET DES COMPTES AJUSTÉS LE LISSAGE KATZ POUR $k=5$ DES UNIGRAMMES DU TEXTE LE PETIT PRINCE. LES COMPTES ORIGINAUX SONT LISSÉS SELON UNE RÉGRESSION LINÉAIRE TELLE QUE DÉFINIE À L'ÉQUATION (2.17). 31

TABLEAU 2.10 : COMPTES ET PROBABILITÉS D'UN ÉCHANTILLON D'UNIGRAMMES AJUSTÉS GOOD-TURING ET KATZ POUR $k = 5$ DU TEXTE LE PETIT PRINCE. LES COMPTES ORIGINAUX SONT LISSÉS SELON UNE RÉGRESSION LINÉAIRE TELLE QUE DÉFINIE À L'ÉQUATION (2.17). 31

TABLEAU 4.1 : PARAMÈTRES FIXES UTILISÉS POUR L'ÉVALUATION DU NOMBRE D'INDIVIDUS CHOISIS POUR LA FONCTION DE SÉLECTION PAR TOURNOI. 90

TABLEAU 4.2 : RÉSUMÉ DES RÉSULTATS OBTENUS DANS LE CADRE DE L'ÉVALUATION DE L'INFLUENCE DE LA TAILLE DES TOURNOIS SUR LA PERPLEXITÉ POUR OPTIMISATION AVEC ET SANS AMORÇAGE. 92

TABLEAU 4.3 : PARAMÈTRES FIXES UTILISÉS POUR L'ÉVALUATION DE L'EFFET DU TAUX DE CROISEMENT SUR LA PERFORMANCE FINALE DU MODÈLE DE LANGAGE. 94

TABLEAU 4.4 : SOMMAIRE DES RÉSULTATS OBTENUS POUR L'ÉVALUATION DE L'EFFET DU TAUX DE CROISEMENT POUR LA FONCTION DE CROISEMENT ARITHMÉTIQUE AVEC ET SANS AMORÇAGE. 98

TABLEAU 4.5 : PARAMÈTRES STATIQUES POUR L'ÉVALUATION DE LA MUTATION. 99

TABLEAU 4.6 : SOMMAIRE DES RÉSULTATS OBTENUS POUR L'ÉVALUATION DE L'EFFET DU TAUX DE MUTATION POUR LA FONCTION DE MUTATION ADAPTATIVE AVEC ET SANS AMORÇAGE. 103

TABLEAU 4.7 : PARAMÈTRES SIGNIFICATIFS UTILISÉS POUR L'OPTIMISATION PAR ALGORITHME GÉNÉTIQUE. 104
LISTE DES FIGURES

<table>
  <tbody>
    <tr>
      <td>FIGURE 2.1 : ARCHITECTURE GÉNÉRALE D'UN SYSTÈME DE DIALOGUE VERBAL</td>
      <td>18</td>
    </tr>
    <tr>
      <td>FIGURE 2.2 : DÉCOMPOSITION DES COMPOSANTES DE RECONNAISSANCE AUTOMATIQUE DE LA PAROLE ET COMPRÉHENSION DE LA PAROLE DANS LE CONTEXTE D'UN SYSTÈME DE DIALOGUE VERBAL</td>
      <td>18</td>
    </tr>
    <tr>
      <td>FIGURE 2.3 : DÉCOMPOSITION DE LA COMPOSANTE GESTIONNAIRE DE DIALOGUE DANS LE CONTEXTE D'UN SYSTÈME DE DIALOGUE VERBAL</td>
      <td>18</td>
    </tr>
    <tr>
      <td>FIGURE 2.4 : DÉCOMPOSITION DE LA COMPOSANTE GÉNÉRATRICE DE RÉPONSES DANS LE CONTEXTE D'UN SYSTÈME DE DIALOGUE VERBAL</td>
      <td>19</td>
    </tr>
    <tr>
      <td>FIGURE 2.5 : ARCHITECTURE D'UN ML BASÉ SUR LES RÉSEAUX DE NEURONES RÉCURRENTS AVEC LSTM</td>
      <td>46</td>
    </tr>
    <tr>
      <td>FIGURE 3.1 : ÉCHANTILLON DE L'ONTOLOGIE COMPLÈTE AYANT COMME NŒUD CENTRAL LE TERME CHAT. LA TAILLE DES NŒUDS REPRÉSENTE LEUR DEGRÉ DE CONNECTIVITÉ ET LEUR COULEUR LEUR CATÉGORIE GRAMMATICALE : ADJECTIFS (NOIR), ADVERBES (NON REPRÉSENTÉS, BLANC), NOMS (GRIS CLAIR) ET DES VERBES (GRIS). LES COULEURS DES ARÊTES REPRÉSENTENT LE TYPE DE RELATION ENTRE LES NŒUDS. ON NOTERA QUE LA LONGUEUR DES LIGNES N'A AUCUNE SIGNIFICATION AUTRE QUE L'AMÉLIORATION DE LA CLARTÉ DE L'ILLUSTRATION.</td>
      <td>55</td>
    </tr>
    <tr>
      <td>FIGURE 4.1 : ILLUSTRATION DU CONCEPT DE LA ROULETTE DANS LE CONTEXTE D'UN ALGORITHMÈRE GÉNÉTIQUE. CHAQUE SECTEUR DU GRAPHIQUE EN SECTEURS REPRÉSENTE LES PROBABILITÉS, RELATIVES À LEUR PERFORMANCE, D'ÊTRE CHOISI COMME PARENT POUR CHAQUE INDIVIDU DE LA POPULATION</td>
      <td>72</td>
    </tr>
    <tr>
      <td>FIGURE 4.2 : ILLUSTRATION DES PROBABILITÉS RELATIVES RESTANTES AJUSTÉES APRÈS LE TIRAGE AU PREMIER TOUR DE L'INDIVIDU 5</td>
      <td>73</td>
    </tr>
    <tr>
      <td>FIGURE 4.3 : ILLUSTRATION DU PROCESSUS DE CROISEMENT, À PARTIR DU QUATRIÈME ALLÈLE, POUR UN ALGORITHMÈRE GÉNÉTIQUE BINAIRE. LE POINT DE CROISEMENT EST GÉNÉRALEMENT CHOISI DE FAÇON ALÉATOIRE</td>
      <td>74</td>
    </tr>
    <tr>
      <td>FIGURE 4.4 : ILLUSTRATION DU PROCESSUS DE CROISEMENT MULTIPOINTS, POUR UN ALGORITHMÈRE GÉNÉTIQUE BINAIRE. LE POINT DE CROISEMENT EST GÉNÉRALEMENT CHOISI DE FAÇON ALÉATOIRE</td>
      <td>75</td>
    </tr>
    <tr>
      <td>FIGURE 4.5 : ILLUSTRATION DU RÉSULTAT DE LA MUTATION D'UN ALLÈLE SUR UN CHROMOSOME DANS LE CAS D'UN AG BINAIRE</td>
      <td>77</td>
    </tr>
    <tr>
      <td>FIGURE 4.6 : ALGORITHMÈRE GÉNÉRAL DE L'OPTIMISATION PAR ALGORITHMÈRE GÉNÉTIQUE</td>
      <td>79</td>
    </tr>
    <tr>
      <td>FIGURE 4.7 : EXEMPLE DE CONVERGENCE D'UN ESSAIMS PARTICULAIRES CHERCHANT UN MINIMUM GLOBAL D'UNE FONCTION</td>
      <td>80</td>
    </tr>
    <tr>
      <td>FIGURE 4.8 : EXEMPLE DE TOPOLOGIES DE VOISINAGE</td>
      <td>82</td>
    </tr>
    <tr>
      <td>FIGURE 4.9 : ALGORITHMÈRE GÉNÉRAL DE L'OPTIMISATION PAR ESSAIM PARTICULAIRE</td>
      <td>84</td>
    </tr>
    <tr>
      <td>FIGURE 4.10 : CONVERGENCE MOYENNE SUITE À 25 SIMULATIONS MONTE-CARLO DE L'OPTIMISATION PAR AG : (A) REPRÉSENTE LA CONVERGENCE MOYENNE POUR UN TOURNOI DE 2 À 15 INDIVIDUS SANS AMORÇAGE ; (B) REPRÉSENTE LA CONVERGENCE MOYENNE POUR UN TOURNOI DE 2 À 15 INDIVIDUS AVEC AMORÇAGE</td>
      <td>91</td>
    </tr>
  </tbody>
</table>
<figure><img src="image_4.png" /></figure>
LISTE DES ACCRONYMES

**ADL** Allocation de Dirichlet latente

**AE** Algorithmes évolutionnaires

**AG** Algorithme génétique

**AIML** *Artificial Intelligence Markup Language*

**API** Alphabet phonétique international

**ASR** *Automatic Speech Recognition*

**BBOSLM** *Bin Based Ontologically Smoothed Language Model*

**C&C** *Command and Control*

**DCT** *Discrete Cosine Transform*

**DFT** *Discrete Fourier Transform*

**EA** *Evolutionary Algorithms*

**EM** Expectation-Maximisation

**EMV** Estimation du maximum de vraisemblance

**EVD** *EigenValue Decomposition*

**GA** *Genetic Algorithm*

**GT** Good-Turing

**HITS** *Hyperlink Induced Topic Search*

**HMM** *Hidden Markov Models*

**IVR** *Interactive Voice Response*

**JM** Jelienek Mercer

**KLT** *Karhunen-Loève Transform*

**KN** Kneser Ney

**LM** *Language Model*

**LSTM** *Long Short Term Memory*

**MDL** *Minimum Description Length*
<table>
   <tr>
    <td>MHV</td>
    <td>Mots hors vocabulaire</td>
   </tr>
   <tr>
    <td>MKN</td>
    <td>Modified Kneser Ney</td>
   </tr>
   <tr>
    <td>ML</td>
    <td>Modèle de langage</td>
   </tr>
   <tr>
    <td>MLE</td>
    <td>Maximul Likelyhood Estimation</td>
   </tr>
   <tr>
    <td>OEP</td>
    <td>Optimisation par essais particulaires</td>
   </tr>
   <tr>
    <td>OOV</td>
    <td>Out Of Vocabulary</td>
   </tr>
   <tr>
    <td>OWL</td>
    <td>Web Ontology Language</td>
   </tr>
   <tr>
    <td>PCA</td>
    <td>Principal Component Analysis</td>
   </tr>
   <tr>
    <td>PCs</td>
    <td>Principal Components</td>
   </tr>
   <tr>
    <td>PESQ</td>
    <td>Perceptual Evaluation of Speech Quality</td>
   </tr>
   <tr>
    <td>POS</td>
    <td>Part Of Speech</td>
   </tr>
   <tr>
    <td>PP</td>
    <td>Perplexité</td>
   </tr>
   <tr>
    <td>PPL</td>
    <td>Perplexity</td>
   </tr>
   <tr>
    <td>PR</td>
    <td>Page Rank</td>
   </tr>
   <tr>
    <td>PSO</td>
    <td>Particle Swarm Optimisation</td>
   </tr>
   <tr>
    <td>PY</td>
    <td>Pitman-Yor</td>
   </tr>
   <tr>
    <td>PYH</td>
    <td>Pitman-Yor hiérarchique</td>
   </tr>
   <tr>
    <td>RAP</td>
    <td>Reconnaissance automatique de la parole</td>
   </tr>
   <tr>
    <td>RNN</td>
    <td>Reccurent Neural Network</td>
   </tr>
   <tr>
    <td>RNP</td>
    <td>Réseau de neurones profond</td>
   </tr>
   <tr>
    <td>RNR</td>
    <td>Réseau de neurones récurrents</td>
   </tr>
   <tr>
    <td>RFID</td>
    <td>Radio Frequency IDentification</td>
   </tr>
   <tr>
    <td>SS</td>
    <td>Spectral Slope</td>
   </tr>
   <tr>
    <td>SUO-KIF</td>
    <td>Standard Upper Ontology Knowledge Interchange Format</td>
   </tr>
   <tr>
    <td>TALN</td>
    <td>Traitement automatique du langage naturel</td>
   </tr>
   <tr>
    <td>TEM</td>
    <td>Taux d'erreur des mots</td>
   </tr>
   <tr>
    <td>TF-IDF</td>
    <td>Term Frequency Inverse Document Frequency</td>
   </tr>
   <tr>
    <td>VER-KLT</td>
    <td>Variance de l'erreur de reconstruction de la Karhunen-Loève Transform</td>
   </tr>
  </table>
**VRE** *Variance of the Reconstruction Error*

**VRE-KLT** *Variance of the Reconstruction Error of Karhunen-Loève Transform*

**WB** Witten Bell

**WD** *Weighed Degree*

**WER** *Word Error Rate*

**WRR** *Word Recognition Rate*

**WSS** *Weighted Spectral Slope*

**WWW** *World Wide Web*

**XML** *eXtended Markup Language*
*Analyse sémantique pour systèmes de
dialogue verbaux*
*Synthèse*
Felix qui potuit rerum cognoscere causas

Virgile

Sum ergo cogito. Cogito ergo dubito

# 1 INTRODUCTION

## 1.1 La modélisation du langage

De façon générale lorsque nous modélisons un langage naturel<fnref n="1" />, nous tentons de capturer, de décrire et d'exploiter les régularités et les structures intrinsèques à ce langage. En effet, si le langage était sans règles, sans objectifs, il nous serait très difficile de communiquer efficacement. À son plus simple, un modèle de langage peut être constitué d'une liste des mots et des phrases permises par ledit langage. En effet, dans le contexte de la reconnaissance automatique de la parole, à ses tous débuts, la modélisation du langage consistait en listes de mots (des chiffres) permis [1]. Ce n'est que plus tard, alors que les capacités calculatoires le rendirent possible, que les modèles de langage commencèrent à se complexifier.

D'un point de vue philosophique, les premiers modèles de langage formels auxquels nous sommes initiés sont les dictionnaires ainsi que les manuels de syntaxe et de grammaire. Ceux-ci édictent les constructions du langage, les mots qui sont permis selon un ensemble de règles strictes, formelles et laissant peu de place à l'interprétation. C'est pourquoi les premiers modèles de langage informatisés étaient principalement basés sur la grammaire et étaient majoritairement l'affaire des linguistes. Cependant, on le sait bien, le langage parlé n'est pas, dans la majorité des cas, assujetti à autant de règles et restrictions qu'une rédaction écrite : il laisse beaucoup plus de place à l'improvisation, à la spontanéité, l'immédiateté, voir même l'invention (pensons, par exemple, aux néologismes). Cela dit, il est clair que, même avec les meilleures intentions du

<footnote n="1">¹ Pour fin de simplification, nous utiliserons le terme plus général « langage » tout au long de cette thèse. Notons que les techniques décrites ici peuvent d'ailleurs tout aussi s'appliquer (avec modifications au besoin) aux langages dits artificiels.</footnote>
monde, et des ressources temporelles infinies, un modèle de langage conçu à la main ne pourra jamais prétendre répondre à une tâche universelle<fnref n="2" />.

Voilà donc pourquoi la grande majorité de la recherche actuelle dans le domaine se base sur une approche probabiliste et où on s'appuiera sur d'énormes corpora<fnref n="3" /> pour en déduire la structure probabiliste et, ainsi, être en mesure de « minimiser » l'incertitude par rapport à ce qui a été dit.

Outre la reconnaissance automatique de la parole, les modèles de langage sont utilisés autant en traduction automatique, qu'en récapitulation de texte, reconnaissance de l'écriture, traitement du langage, recherche d'information, etc.

L'application principale visée par cette thèse relève du domaine de la reconnaissance automatique de la parole (RAP). La reconnaissance automatique de la parole s'appuie d'une part d'un modèle acoustique et, d'autre part, d'un modèle de langage et où on cherche à résoudre l'équation suivante :

$$ \hat{W} = \underset{W \in \mathcal{L}}{\operatorname{argmax}} P(W|O). \qquad (1.1) $$

Celle-ci se lit comme suit : la phrase reconnue est la phrase ayant la plus haute probabilité étant donné les sons « entendus ».

Il a été démontré à plusieurs occasions que les progrès réalisés en modélisation du langage aboutissent généralement à des améliorations de performance en RAP (diminution du taux d'erreur de reconnaissance des mots, insertions [mots en trop], substitutions, suppressions). Cela se traduit par la suite à des améliorations dans le domaine de la compréhension de la parole (pensez par exemple à Siri [2], mais qui comprend ce que vous dites). En gros, le modèle de langage sert à aider le modèle acoustique en excluant les mots qui sont très peu probables (et, par conséquent, les séquences phonémiques peu probables). Par exemple, sans connaissance du contexte, ou de ces probabilités, il nous serait impossible de savoir si la séquence (observée) suivante de phonèmes (en format API) : e.tɔ.na.mã.mɔ.nɔ.tɔn.e.las, une phrase homophonique, désigne :

<footnote n="2">² Ce qui nous fait forcément penser à la fameuse citation de Jelinek (1985 : traduction libre) « À chaque fois que je vire un linguiste, les performances de la reconnaissance automatique de la parole augmentent ».</footnote>

<footnote n="3">³ Essentiellement des recueils de texte.</footnote>
*Étonnamment monotone et lasse*

ou

*Est ton âme en mon automne hélas* [3].

Un autre exemple qui illustre bien l'importance et le pouvoir prédictif du modèle de langage est justement lorsque l'on a une conversation avec quelqu'un que l'on connaît bien et où nous sommes en mesure de compléter les phrases de notre interlocuteur. On peut donc considérer notre connaissance de l'interlocuteur (son contexte, son vocabulaire habituel, sa façon de présenter/construire ses énoncés) comme un modèle de langage. Ce même modèle de langage nous sert bien aussi lorsque nous ne sommes pas sûr d'avoir bien entendu (signal acoustique déformé ou incomplet), mais nous pouvons exclure certains mots avec un bon degré de certitude (réduction de l'espace de recherche acoustique, détection/correction d'erreur). Pour continuer notre analogie précédente, nous arrivons à prédire ce que notre interlocuteur va dire, car nous l'avons plus souvent entendu dire quelque chose d'une manière, plutôt que d'une autre (probabilité plus élevée, basée sur un nombre d'observations). Un autre exemple serait l'usage d'un patois où les interlocuteurs ont l'habitude d'utiliser des mots et expressions (souvent dites, compte élevé) et donc très probables et, par conséquent, faciles à deviner.

Toutefois, malgré notre maîtrise de la parole et du langage, nous ne sommes toujours pas en mesure, en tant qu'être humain, de tout prédire avec exactitude, et tout comme nous, les ordinateurs ont eux aussi de la difficulté, ce qui nous arrange (les chercheurs), puisqu'on peut toujours faire mieux.

## 1.2 Motivation

La parole est notre moyen privilégié de communication interpersonnelle et nous permet de décrire le monde ainsi que d'en prendre possession [4]. Le langage nous permet quant à lui de comprendre, de **nous** comprendre [5], [6] et de comprendre non seulement les autres, mais aussi leur vision du monde. Le langage participe donc à la construction de chaque individu en fonction de sa culture, de son identité. Ces mécanismes se mettent en place dès notre jeune âge d'abord avec les membres de notre famille puis pour socialiser à l'extérieur de la cellule familiale et ce processus se poursuit toute la vie pour échanger notre sagesse, nos connaissances, des informations et des données.
Cette facilité d'interaction permet d'expliquer pourquoi de nombreux efforts dans le domaine de l'**interaction automatique par la parole**<fnref n="4" /> sont mis en place afin de rendre le plus naturel possible nos interactions avec les divers systèmes informatisés qui sont à notre disposition. Pour preuve, ces systèmes font de plus en plus partie de nos vies, elles-mêmes de plus en plus connectées, ne serait-ce que par l'utilisation de nos téléphones, dits, intelligents, qui proposent des « assistants » virtuels de plus en plus ambitieux et sophistiqués [2], [7], [8]. Nous retrouvons aussi ces capacités d'interaction vocale dans la majorité des voitures (un fort argument de vente de nos jours), qui permettent, en principe, de réduire la distraction des chauffeurs. De plus en plus de centres d'appels nous redirigent vers des agents conversationnels en ligne de premier front. La domotique quant à elle, qui se démocratise de plus en plus, en voit ses fonctionnalités augmentées. À titre d'exemple, à partir du moment où un utilisateur peut interroger le système de façon naturelle, celui-ci pourrait poser la question suivante à « son domicile » :

« Est-ce que la porte est barrée ? »

En supposant que l'individu soit couché, cela est, *ipso facto*, à la fois beaucoup plus facile, rapide et pratique que de se lever et d'aller vérifier si la porte est bel et bien verrouillée.

D'autres applications se prêtent bien à l'interaction par la parole ; lorsque nous avons les mains pleines ou encore lorsque le clavier et la souris ne sont pas des modalités idéales. D'ailleurs, dans nos travaux de maîtrise [9] nous montrons comment une modalité vocale peut être équivalente au clavier et à la souris pour certaines tâches et [10] démontre que pour certains cas qu'une interface vocale est plus efficace que le clavier et la souris.

Évidemment, si nous portons notre regard vers le futur nous ne pouvons éviter de penser à la robotique, un rêve presque aussi ancien que la civilisation moderne [11], [12] elle-même. Aujourd'hui, nous avons nos aspirateurs robotisés, ou encore des « compagnons » robotiques tel que Zenbo [13], Pepper [14] ou encore Anybot [15], demain nous aurons, du moins, *nous* le

<footnote n="4">⁴ Nous préférons ici parler d'interaction automatique par la parole plutôt que de reconnaissance automatique de la parole, comme il était courant par le passé, puisque cette première expression est maintenant l'objectif principal de tous les efforts investis dans ce vaste champ de recherche qu'est la réplication de l'intelligence humaine.</footnote>

<footnote n="5">⁵ Synonyme de l'adjectif verrouillé en acadien/français canadien. Cet exemple illustre bien une des difficultés inhérentes à l'interaction par la parole, à savoir, comment traiter et détecter les dialectes en temps réel et à résoudre les ambiguïtés (de quelle porte parlons-nous ?).</footnote>
souhaitons, des robots de service sophistiqués à la Data dans Star Trek, Marvin dans *Le Guide du Voyageur Galactique* ou encore C3-P0 de Star Wars<fnref n="6" />. Il est évident que la parole est le moyen privilégié d'interaction avec de tels agents (en complément aux interfaces neuronales directes qui ont connu un intérêt grandissant durant les dernières années dû, entre autres, aux développements en électro-encéphalographie [16]. On peut difficilement imaginer devoir utiliser un clavier de quelque sorte pour les commander, voire discuter avec eux.

C'est dans le contexte de cette problématique que nous devons continuer à chercher des moyens de mieux simuler notre capacité à reconnaître et comprendre la parole. Cela dit, de grands progrès ont été réalisés dans les dernières années. Il faut dire que le « *Big Data* » (mégadonnées), jargonnerie du moment, est à la source de bien des développements (p. ex. : traitement de la parole, traitement de l'image, traitement de dossiers médicaux, analyse d'habitude des consommateurs, prévisions boursières, etc.). En effet, la (relative) facilité avec laquelle nous avons dorénavant accès à de vastes quantités de données (sans oublier les ressources computationnelles) ont créé une sorte de ruée vers l'or où les « *data scientist* » (prospecteur des temps modernes) comme on aime bien les appeler, mettent à l'œuvre une panoplie d'algorithmes, autant anciens que nouveaux, dans l'espoir de (re)découvrir des liens jusqu'à présent inconnus (ou oubliés), ou encore d'améliorer les capacités des systèmes en termes de classification. N'oublions pas non plus les célèbres images réimaginées par Google Deep Dream [17] rendues possibles à la fois aux avancées dans l'apprentissage profond qu'au traitement des mégadonnées. Cependant, comme Mikolov [18] l'explique, ce n'est pas nécessairement en « lisant » l'intégralité de l'*Encyclopædia Britannica* qu'un francophone apprendra l'anglais. Comme quoi, on a beau avoir toutes les données du monde, encore faut-il savoir s'en servir pour en extraire l'essentiel<fnref n="7" />. Voilà justement pourquoi nous nous devons de poursuivre nos efforts afin d'améliorer ceux-ci.

Comme vous pouvez l'imaginer, reconnaître, et surtout, comprendre, la parole humaine n'est pas une tâche aisée. De multiples étapes interviennent tout au long du processus, on pense par exemple au :

1. Rehaussement du signal,

<footnote n="6">⁶ Tentons cependant d'éviter HK-47...</footnote>

<footnote n="7">⁷ Un pessimiste vous dira qu'on a encore du chemin à faire, un optimiste vous dira que c'est une époque parfaite pour débuter un doctorat en sciences de l'information.</footnote>
2. Segmentation et analyse du signal de parole (traitement du signal et paramétrage),

3. Modélisation du langage (pour essayer de deviner ou, idéalement, « savoir » ce qui a été dit,

4. Analyse sémantique (assurer un maximum de sens),

5. Analyse pragmatique<fnref n="8" />/compréhension du langage (le comprendre).

Malgré tous ces défis, nous ne cessons de construire un futur où les machines seront en mesure de traiter la parole comme nous le pouvons. Il faut reconnaître que nous avons fait d'énormes progrès en termes de reconnaissance automatique de la parole depuis ses débuts en 1952⁹ où Davis et al. [1] proposèrent un système (circuit analogique), basé sur des filtres, permettant de reconnaître automatiquement une séquence de chiffres. Déjà, 20 ans plus tard, nous étions en mesure d'effectuer de la reconnaissance automatique de la parole en continu (sans marquer de pause après chaque mot) sur un vocabulaire d'environ 100 à 1000 mots. Dès le milieu des années 70 aux années 80 nous passions de modèles principalement par motifs à des modèles stochastiques supportant des milliers de mots [20]. Aujourd'hui, nous disposons de systèmes de reconnaissance automatique de la parole supportant des dizaines, voire des centaines de milliers de mots et où le langage est représenté par un ensemble de modèles statistiques nous permettant de distinguer entre les mots similaires, mais qui ont peu de probabilité de suivre un historique donné.

C'est dans ce contexte que nous nous sommes intéressé à ce domaine et que nous en sommes arrivé à nous questionner sur les manières d'améliorer la prise en compte du sens et de l'importance des liens sémantiques entre les mots. Un élément souvent occulté par les techniques traditionnelles de modélisation du langage est l'objectif du langage en soit : le langage permet aux êtres humains de communiquer ou exprimer des idées, des pensées **qui ont un sens par rapport à un sujet particulier**, donc qui sont sémantiquement et contextuellement liées. De plus, il est possible de dire la même chose de façon plus ou moins précise (généralisation du discours versus spécialisation) et plusieurs sujets similaires peuvent être abordés de façons similaires. Par exemple, on peut avoir un discours similaire à propos d'un chien et d'un chat, par exemple : le chien aboie, le chat miaule, qui peut se résumer à « l'animal de compagnie vocalise ». La question se pose alors

<footnote n="8">⁸ Nous entendons ici par pragmatique le sens de « [la] branche de la linguistique qui s'intéresse aux éléments du langage dont la signification ne peut être comprise qu'en connaissant le contexte de leur emploi » [19]</footnote>

<footnote n="9">⁹ Ou, du moins, le premier article savant répertorié portant sur le sujet.</footnote>
à savoir où peut-on trouver ces ressources sémantiques ? Bien qu'il existe plusieurs moyens de déduire des relations sémantiques à l'aide de divers algorithmes, nous privilégierons l'utilisation de ressources plus formelles, soit les ontologies.

L'ontologie est « ... l'étude de l'être en tant qu'être... » (Aristote [21]). De ce fait, les ontologies sont utilisées pour structurer les termes et les concepts propres à un (ou plusieurs) domaine de connaissance de façon hiérarchique et relationnelle afin d'ultimement décrire leur sens et ainsi nous permettre de raisonner à propos de ces objets. Les entités logiques et philosophiques peuvent elles-mêmes être regroupées de façon contextuelle à l'aide d'opérateurs de relation (relations sémantiques, relations de subsomption) nommée, p. ex. : Terme:chat Relation:manger Terme:souris.

Puisque les ontologies (informatiques) contiennent une quantité importante d'information et qu'on peut en résumer le rôle comme, étant les « ontologies sont aux données ce que la grammaire est au langage » [22], il devient apparent qu'elles doivent être en mesure de nous permettre d'aider nos modèles de langage à mieux prendre en compte les relations entre les mots et nous donner des modèles qui reflètent notre compréhension du langage.

Cela nous amène ainsi à formuler notre question de recherche principale : comment peut-on utiliser l'information sémantique contenue dans les ontologies pour lisser les modèles de langage ?

L'objectif principal est donc d'exploiter ces ontologies pour introduire une notion de savoir dans les modèles de langage, c'est-à-dire, d'être en mesure d'attribuer des probabilités plus élevées à des N-grammes inédits, mais qui sont sémantiquement liées à des N-grammes vus ou qui fonctionnent de façon similaire. En d'autres mots nous tenterons à la fois de paraphraser<fnref n="10" /> les N graves déjà vus et de générer des N-grammes décrivant des sujets similaires. Nous désirons ainsi à la fois réduire la perplexité (une mesure basée sur l'entropie croisée qui nous permet de mesurer la capacité d'un modèle de langage à prédire un corpus de test donné) des modèles de langage et augmenter la performance de la reconnaissance de la parole grâce à nos algorithmes de lissages ontologiques.

<footnote n="10">¹⁰ paraphrase (n.f.) (grec *paraphrasis*) : Formulation différente d'un énoncé sans altération de son contenu [23].</footnote>
## 1.3 Mise en contexte des articles

Le tout a débuté lors de nos travaux de maîtrise où nous avons conçu un navigateur Web pour dispositifs mobiles. Celui-ci utilisait des motifs pour alimenter un système hybride entre le Commande et contrôle et la parole spontanée. C'est en se basant sur ces travaux que nous avons proposé, dans notre premier article « Application d'un système basé sur la parole facilitant l'interaction avec des réseaux RFID dans des environnements bruités », un système qui permet à l'utilisateur travaillant dans un environnement très bruyant d'interagir par la parole avec un réseau d'identification par radiofréquence (RFID). Un des problèmes les plus courants attribués aux interfaces opérant sur le modèle de « commande et contrôle » est leur manque de flexibilité par rapport aux énoncés reconnaissables. C'est pourquoi, afin de rendre notre système plus flexible, nous avons proposé un nouveau cadre de dialogue qui donne aux opérateurs humains la capacité de communiquer avec le système d'une façon plus naturelle. Le gestionnaire de dialogue proposé est basé sur le langage AIML (« *Artificial Intelligence Markup Language* ») qui, à la base, a été conçu pour le développement d'agents conversationnels (visant le clavardage). Ce langage permet au système de répondre à des requêtes formulées en langage naturel par l'intermédiaire de détection de motifs (« *pattern matching* »). Cela a aussi comme avantage de rendre le système beaucoup plus robuste par rapport aux erreurs de reconnaissance automatique de la parole, ce qui est particulièrement problématique dans des environnements très bruyants. De plus, afin de faire face à des environnements très bruyants et changeants, une technique en ligne d'amélioration du sous-espace vectoriel du signal basée sur la variance de l'erreur de reconstruction de Karhunen-Loève Transform (ERV-KLT) est proposée.

Finalement, le caractère naturel du dialogue, ainsi que l'efficacité de l'amélioration du signal de la parole sont évalués dans des situations de la vie réelle sous la plateforme Microsoft Windows. Nos résultats démontrent à la fois que l'algorithme ERV-KLT apporte une amélioration de l'évaluation perceptuelle de la qualité de la parole pour les signaux très bruités par rapport aux algorithmes de références et que le système devient effectivement plus robuste face aux erreurs de reconnaissance de la parole par rapport à une grammaire statique.

Bien que le système proposé dans le premier article permette une interaction plus naturelle avec le système, il demeure que l'une des difficultés principales rencontrées dans l'élaboration de
systèmes basés sur les commandes est la conception des commandes. Le concepteur doit essayer
de couvrir le plus de cas possibles ce qui est à la fois fastidieux et chronophage. Par exemple, une
simple requête de recherche d'inventaire nécessite une multitude de motifs pour couvrir tous les
lemmes, les conjugaisons et toutes autres variations sémantiques possibles. Ce travail de
conception requiert beaucoup de temps et est sujet aux oublis et à l'erreur humaine. C'est pourquoi
nous proposons, dans notre deuxième article, un système facilitant la conception de ce type de
vocabulaire. Comme les ontologies sont utilisées en informatique, pour représenter des sens, des
concepts nous sommes intéressé à leur utilisation pour rendre le processus de création de
commandes le plus semi-supervisé possible. Nous y avons repris la « recette » initiale de dialogue
du premier article. Le système proposé dans le deuxième article devant se charger de
complémenter les commandes de base en créant de nouvelles règles par l'exploration d'une
ontologie pour trouver d'autres façons de dire la même chose. Nous obtenons alors une plus grande
robustesse aux variations de commandes possibles tout en permettant de réduire la charge
cognitive des utilisateurs. Finalement, nos résultats démontrent que le système est en mesure de
générer de nouveaux motifs à partir des motifs de base tout en minimisant l'impact au niveau de
la perplexité du modèle de langage généré.

Bien que le *premier article* et le *deuxième article* proposent un système permettant une interaction plus naturelle avec un système industriel, un problème persiste. Si les modèles de langage ne sont pas en mesure de tenir compte des nouvelles commandes, le système ne sera pas capable de les reconnaître. Nous nous sommes donc tourné vers les modèles de langage qui permettront justement la reconnaissance de telles phrases nouvelles.

Dans notre troisième *article*, nous introduisons une nouvelle méthode de lissage des modèles de
langage basée sur les informations sémantiques trouvées dans les ontologies et qui est spécialement
adaptée pour la modélisation du langage dans un contexte de ressources limitées. Nous exploitons
la connaissance latente de la langue qui est profondément codée dans des ontologies. En tant que
tel, cet article examine la possibilité d'utiliser les relations sémantiques et syntaxiques entre les
« synsets » (mot+sens) couvertes par l'ontologie WordNet (anglais). Ces propriétés seront alors
exploitées afin de générer de nouveaux contextes plausibles pour les événements non vus dans le
corpus d'entrainement dans le but de « simuler » un corpus plus vaste. Ces « nouveaux »
N-grammes sont ensuite interpolés avec un modèle de langue de base lissé à l'aide de l'algorithme
de Witten-Bell [24]. Cela, dans le but de réduire, à la fois, la perplexité du modèle de langage et le taux d'erreur de mots dans une tâche de reconnaissance automatique de la parole. Nos résultats expérimentaux démontrent qu'il est possible d'obtenir une réduction significative de la perplexité du modèle (jusqu'à 9,85 % par rapport au modèle de base). Ces résultats montrent également qu'il est possible de réduire le taux d'erreur de mots du modèle de langage original d'une manière statistiquement significative par rapport au modèle de base lissé à l'aide de l'algorithme de Kneser-Ney entrainé sur le corpus « Wall Street Journal-Based Continuous Speech Recognition Phase II ».

Pour donner suite à ces résultats encourageants, nous nous sommes posé la question à savoir si la théorie des graphes, telle qu'appliquée dans le domaine de la théorie de l'information et des réseaux (sociaux), pouvait apporter de l'information supplémentaire à nos modèles de langage. C'est pourquoi nous avons examiné, dans le *quatrième article*, l'apport des mesures tirées de la théorie des graphes à la généralisation de notre algorithme de lissage de modèle de langage proposé dans le *troisième article*. Plus spécifiquement, nous avons exploré l'effet des mesures HITS, PageRank, Modularité et degré pondéré sur la performance de la reconnaissance automatique de la parole, de même que par rapport à la perplexité des modèles de langage. Comme les ontologies peuvent être représentées sous forme de graphes, nous étudions l'utilisation de paramètres des graphes comme facteur de lissage supplémentaire afin de saisir l'information sémantique ou relationnelle intrinsèque aux ontologies. Plus précisément, nous étudions l'effet des mesures *Hyperlink-Induced Topic Search* (HITS), PageRank, Modularité et degré pondéré à la fois sur la performance de la reconnaissance automatique de la parole, de même que sur la perplexité des modèles de langage. Nos résultats montrent que l'interpolation des bacs originaux à des distances 1, 3 et 5 a donné lieu à une amélioration du taux d'erreur des mots de 0,71 % par rapport à l'interpolation des bacs 1 à 5 proposés ultérieurement dans le *troisième article*. Finalement, nous avons observé que la modularité, le PageRank et l'HITS sont prometteurs et méritent une étude plus approfondie dans le futur.

### 1.3.1 Au-delà des articles

Les algorithmes d'optimisation par espérance-maximisation ou de Powell sont majoritairement utilisés dans le domaine de la reconnaissance automatique de la parole, notamment pour l'optimisation des paramètres des modèles de langage. Bien qu'assez rapide, nous pouvons
constater empiriquement que les résultats obtenus représentent souvent des solutions très
localement optimales.

Ces choix étaient justifiables dans un contexte de ressources computationnelles limitées (ou d'exécution en temps réel). Cependant, comme la plupart des modèles de langage utilisés dans les systèmes commerciaux sont généralement optimisés hors-ligne, la contrainte du temps s'en voit grandement diminuée.

Il nous est donc apparu judicieux d'explorer d'autres algorithmes d'optimisation qui offrent un potentiel accru de trouver une solution globalement satisfaisante. Par conséquent, nous avons choisi d'étudier l'optimisation des poids d'interpolation des modèles de langage par algorithmes évolutionnaires. Plus spécifiquement, nous comparons les algorithmes génétiques et l'algorithme collaboratif d'optimisation par essais particulaires aux approches traditionnelles. Nos résultats montrent qu'il nous est possible d'obtenir une diminution significative de perplexité pour nos modèles de langage, particulièrement par rapport à l'optimisation par estimation-maximisation. Par ailleurs, nos résultats démontrent qu'une convergence plus rapide que l'algorithme de Powell peut être obtenue en utilisant l'optimisation par algorithmes génétiques et l'optimisation par essais particulaires.

**1.4 Contributions de la thèse**

Les contributions principales de notre thèse se résument comme suit :

- Proposition d'un nouvel algorithme de lissage ontologique exploitant l'information sémantique retrouvée dans les ontologies pour le lissage des modèles de langage :

- Amélioration de la performance de la RAP, en particulier dans un contexte de corpus réduit.

- Amélioration de la perplexité.

- Capacité d'adaptation pour les corpora hors contextes :

- Entrainement sur le corpus *Wall Street Journal*, validation sur le *Billion Word Corpus*.

- Évaluation des métriques issues de la théorie des graphes pour l'ajustement des poids des N-grammes inédits.
* Utilisation et évaluation d’algorithmes évolutifs pour l’optimisation des poids d’interpolation des modèles de langage.

* Comparaison empirique avec d’autres algorithmes de lissage statistique sur les corpus suivants :
  * Reconnaissance automatique de la parole sur le corpus *Wall Street Journal*.

* Conception d'une suite logicielle permettant de générer les N-grammes lissés :
  * Compatible avec le standard C++11.
  * Optimisation de la vitesse de traitement :

* Traitement parallèle.

* Algorithmes efficaces.

* Production d'une suite de procédures d'apprentissage pour la reproduction des résultats sous Linux (Python + Bash + Perl + Matlab).

## 1.5 Organisation du manuscrit

Cette thèse par articles comporte deux grandes sections :

La première section introduit le concept de la modélisation du langage et la met en contexte par rapport à notre parcours et notre démarche scientifique. Un résumé en français de nos algorithmes et modèles, ainsi que les résultats obtenus y sont présentés.

* Le chapitre 2 introduit la modélisation du langage et passe en revue la littérature. Les méthodes de lissage y sont abordées et décrites statistiquement.

* Le chapitre 3 présente de façon succincte, notre démarche ainsi que notre algorithme de lissage basé sur les ontologies.

* Le chapitre 4 présente les améliorations et les évaluations additionnelles que nous avons effectuées suite aux articles présentés dans la deuxième section de cette thèse.

La deuxième section présente les articles publiés ou soumis à des conférences évalués par les pairs.

* Le chapitre 5 présente un système qui permet à l'utilisateur travaillant dans un environnement très bruyant d'interagir par la parole avec un réseau d'identification par radiofréquence (RFID) publié et présenté à ICASSP 2011.
* Le chapitre 6 propose une amélioration au gestionnaire de dialogue proposé au chapitre 5 via la mise en œuvre d'un générateur de motifs basé sur les ontologies. Ce nouveau cadre de dialogue est proposé afin de donner aux opérateurs humains une plus grande flexibilité de communication avec le système. Le système sera dorénavant en mesure de tenir compte des variations possibles de commandes types. Ce travail est publié et présenté à CCECE 2012.

* Dans le chapitre 7, nous introduisons une nouvelle méthode de lissage des modèles de langage basée sur l'information sémantique trouvée dans les ontologies et qui est spécialement adaptée pour la modélisation du langage dans un contexte de ressources limitées. Cette méthode a été publiée et présentée à ICASSP 2014.

* Le chapitre 8 examine l'utilisation de mesures tirées de la théorie des graphes pour améliorer les performances de l'algorithm de lissage de modèle de langage proposé au chapitre 7. Ces travaux ont été publiés et présentés à EUSIPCO 2016.

Finalement, nous concluons notre travail au chapitre 9 en résumant les résultats obtenus et en posant des pistes de recherche futures.
<figure><img src="image_5.png" /></figure>
# 2 MODÉLISATION DU LANGAGE

## 2.1 Introduction

La plupart des interfaces intégrant l'interaction vocale se répartissent en trois grandes catégories. La première catégorie comprend des interfaces de commande et de contrôle (C & C) qui reposent sur une grammaire étroitement liée à la tâche à accomplir pour permettre à l'utilisateur d'interagir avec le système [10]. Le principal avantage de celle-ci réside dans leur facilité de mise en œuvre et le taux de reconnaissance élevé des commandes, ce qui est largement attribuable à l'espace très restreint de recherche, qu'implique l'utilisation d'un vocabulaire fixe et connu d'avance. Cependant, un de leurs principaux inconvénients est la charge cognitive élevée que ces interfaces induisent lorsque les utilisateurs interagissent avec le système, et ce, en raison de leur manque de flexibilité et du manque de jeux de commandes uniformes. Prenons, par exemple, la reconnaissance vocale utilisée par les fabricants automobiles : un usager qui a l'habitude d'une Ford, utilisant le système SYNC [25], ne sera pas nécessairement en mesure d'utiliser le même vocabulaire dans une voiture Mercedes qui utilise le système LINGUATRONIC [26].

La deuxième catégorie d'interfaces est basée sur les serveurs vocaux interactifs (SVI) qui guident les utilisateurs par le moyen d'invités, afin de faire valider l'énoncé de l'usager à chaque étape [11]. Ce style d'interaction est principalement utilisé dans le cas de la navigation de menus de centres d'appels. Son manque relatif<fnref n="11" /> d'efficacité pour une interaction rapide en fait un choix peu adapté à un usage quotidien.

Enfin, les interfaces de la troisième catégorie utilisent le traitement du langage naturel pour analyser la parole de l'utilisateur et pour déterminer l'objectif de sa requête. Cette analyse peut être réalisée par de multiples moyens, tels le traitement automatique du langage naturel (TALN), le traitement et le filtrage par motif [12], ainsi que la sémantique linguistique. Par conséquent, pour être efficace, en raison d'un vocabulaire pratiquement « illimité », ce type d'interface doit avoir recours à une reconnaissance automatique de la parole précise de même qu'à un interpréteur sémantique efficace ou à un gestionnaire de dialogue efficace : la Figure 2.1 présente l'architecture

<footnote n="11">¹¹ Par rapport aux interfaces de C&C.</footnote>
de base d'un tel système de dialogue. La première composante de ce système concerne principalement cette thèse. Il s'agit notamment de la reconnaissance de la parole proprement dite et est illustrée par la Figure 2.2. La reconnaissance de la parole prend comme entrée un signal porteur d'information : l'onde sonore. Le signal est paramétré : découpé en trames (généralement de 10 ms) où l'on considère que le signal est stationnaire pour ensuite en extraire des paramètres que l'on juge pertinents (énergie, formants, etc.). Ce vecteur de paramètres est ce qu'on appelle l'observation *O*. Cette observation est ensuite comparée à un modèle acoustique pour en déduire la séquence la plus probable de symboles représentatifs (généralement des phonèmes), elle est utilisée de pair avec le modèle du langage pour produire comme sortie une chaîne de symboles (mots) qui sera utilisée comme entrée à la seconde composante du système de dialogue, soit celle de la compréhension de la parole.

Cette étape, telle que définie par la Figure 2.3, permet de déduire le sens, de désambiguïser ou, tout simplement, d'interpréter la chaîne de symboles que le système reçoit comme entrée. Cela est généralement accompli au moyen d'une base de connaissance qui est consultée/utilisée par un ensemble de techniques ; traitement du langage naturel, filtrage par motif, machine à vecteurs de support, etc. pour en arriver à une décomposition arborescente, ou à une commande. Dans ce dernier cas, par exemple, la commande `COMMANDE(de=YQM, a=YUL, date=2018-06-07)` servira d'entrée au gestionnaire de dialogue, illustré par la Figure 2.4, responsable de maintenir les vecteurs suivants :

* de l'état actuel dans lequel l'utilisateur se trouve ;

* de l'état actuel dans lequel le système se trouve ;

* des actions possibles au moment présent.

La sortie du gestionnaire de dialogue est constituée d'un ensemble de commandes. Par exemple, la commande `CONFIRMER(de=YQM, a=YUL, date=2018-06-07)` servira d'entrée au générateur de réponses. Celui-ci exécutera l'action demandée ou générera un retour d'information pour l'utilisateur (à l'aide d'un générateur automatique de langage naturel dans le cas des interfaces purement vocales).
<figure><img src="image_6.png" /><figcaption>Figure 2.1 : Architecture générale d'un système de dialogue verbal.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 2.2 : Décomposition des composantes de reconnaissance automatique de la parole et compréhension de la parole dans le contexte d'un système de dialogue verbal.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 2.3 : Décomposition de la composante gestionnaire de dialogue dans le contexte d'un système de dialogue verbal.</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Figure 2.4 : Décomposition de la composante génératrice de réponses dans le contexte d'un système de dialogue verbal.</figcaption></figure>

Dans ce contexte, pourquoi s'intéresser particulièrement à la modélisation du langage ? La réponse est assez simple : une modélisation du langage précise est primordiale pour minimiser la propagation d'erreurs tout au long de la chaîne de traitement. En effet, nous pourrions difficilement imaginer que le module de compréhension de la parole puisse présenter une sortie pertinente au gestionnaire de dialogue si la séquence reçue de la reconnaissance automatique de la parole est truffée d'erreurs. Il est donc facile de voir en quoi ces deux tâches sont intimement liées. Toute amélioration aux modèles de langage ne peut donc qu'avoir un impact positif sur le système dans son ensemble.

Comme nous le verrons dans les sections à venir, le rôle (formel) du modèle de langage est d'attribuer une probabilité à une chaîne W de n caractères donnés :

$$P(W) = P(w_1, w_2, w_3, \dots, w_{n-1}, w_n). \tag{2.1}$$

## 2.2 Modélisation du langage pour la reconnaissance automatique de la parole

Comme il a déjà été précisé, la **reconnaissance automatique de la parole** (RAP) repose sur un principe fondamental qui consiste à observer une séquence acoustique pour en déduire un ou une séquence de mot(s). Nous pouvons formaliser cela à l'aide d'une simple équation :
$$ \widehat{W} = \underset{W \in \mathcal{L}}{\operatorname{argmax}} P(W|O). \qquad (2.2) $$

Cette équation se lit de la façon suivante : $\widehat{W}$ le mot reconnu (ou la séquence de mots) est égal à la probabilité maximale d'observation du mot $W$, étant donné l'observation acoustique $O$ pour un lexique $\mathcal{L}$ donné. Comme l'estimation de $P(W|O)$ est difficile<fnref n="12" />, nous pouvons utiliser la règle de Bayes pour la simplifier :

$$ P(W|O) = \frac{P(W)P(O|W)}{P(O)}. \qquad (2.3) $$

L'objectif de la modélisation du langage est de résoudre l'a priori, $P(W)$, de l'équation de la RAP :

$$ \widehat{W} = \underset{W \in \mathcal{L}}{\operatorname{argmax}} P(W|O) = \underset{W \in \mathcal{L}}{\operatorname{argmax}} \overbrace{P(\widehat{W})}^{\text{a priori}} \overbrace{P(O|W)}^{\text{a posteriori}} \qquad (2.4) $$

Où $\widehat{W}$ est le mot (ou la séquence de mots) le plus probablement prononcé, $P(W)$ est l'a priori, $P(O|W)$ est la probabilité conditionnelle, ou, a posteriori, que l'on ait observé l'événement acoustique $O$ étant donné le mot $W$<fnref n="13" />. Plus précisément, le modèle de langage nous permet de déterminer la probabilité que le mot $W$ soit prononcé. Notons par ailleurs que le modèle acoustique est généralement modélisé à l'aide de modèles de Markov cachés.

Considérons l'extrait suivant tiré du *Petit Prince* (De Saint-Exupéry [28]). Il est à noter que les symboles $\langle s \rangle$ et $\langle /s \rangle$ sont généralement utilisés pour marquer les débuts et fins de phrase dans les corpus utilisés en traitement du langage naturel, le symbole de fin de phrase est particulièrement important pour que le modèle puisse tenir compte de phrases de longueur arbitraire :

<footnote n="12">¹² Brown [27] illustre bien pourquoi cette estimation est difficile, voire sans intérêt immédiat. Nous sommes moins intéressé (philosophiquement et statistiquement) à connaître toutes les observations acoustiques possibles liées à un mot, une phrase, etc. (essentiellement infinies) qu'à connaître la probabilité d'une observation acoustique particulière étant donné un mot. Par exemple il est évident que la signature acoustique du mot « chat » ne pourrait pas être associée au mot « ristretto », c.-à-d. $P(O|W) = 0$ dans ce cas.</footnote>

<footnote n="13">¹³ Le lecteur perspicace aura constaté la disparition de $P(O)$ dans l'équation (2.4). En effet, il est possible de l'« éliminer », car cette probabilité revient essentiellement à une constante (d'un point de vue intuitif, on pourrait aussi affirmer que l'on est « certain » d'avoir observé cet événement acoustique $O \to P(O) = 1$).</footnote>
s'il vous plaît dessine-moi un mouton 


 hein 


 dessine-moi un mouton 
.

Supposons que l'on cherche à prédire la probabilité que « mouton » soit le prochain mot dans la phrase débutant par les mots suivants : « dessine-moi un... »

Formellement, nous calculons la probabilité d'un mot *w* étant donné son historique *h* : P(*w*|*h*).
Par conséquent, si nous revenons à l'exemple précédent, le travail du modèle de langage est de
calculer :

$$
P(\text{mouton}|\text{dessine-moi un}). \tag{2.5}
$$

Une méthode simple, permettant de calculer cette probabilité, consiste à diviser le nombre de fois où nous avons observé « dessine-moi un mouton », dans le texte, par le nombre de fois où nous avons observé « dessine-moi un ». Tel que :

$$
P(\text{mouton}|\text{dessine-moi un}) = \frac{C(\text{mouton}|\text{dessine-moi un})}{C(\text{dessine-moi un})}. \quad (2.6)
$$

Cette méthode équivaut donc à calculer l’estimation du maximum de vraisemblance. Il est alors évident que « mouton » sera le prochain mot avec 100 % de certitude.

Les cas réels ne sont cependant pas si facilement calculables. De plus, l'exemple présenté ci-dessus
met en évidence une des lacunes de cette approche : il nous faut un nombre minimal d'occurrences
pour pouvoir estimer la vraisemblance d'un événement. Nous obtenons normalement ces
occurrences à partir de très larges corpus de texte. Or, cela n'est pas toujours pratique ou fiable,
puisque de nouvelles phrases peuvent constamment être construites [29] et qu'aucun corpus
n'existe qui puisse couvrir tout ce qui a déjà été dit ou écrit.

Par exemple, il serait impossible de prédire avec exactitude une nouvelle phrase ou expression,
puisque, par définition, son compte (nombre d'apparitions) est zéro. Par ailleurs, nous pouvons
facilement déduire qu'à mesure que la longueur de la phrase augmente et que le vocabulaire croit,
cet exercice s'avère peu pratique. C'est pourquoi il nous est nécessaire d'avoir recours à des
modèles statistiques, parfois complexes, pour être en mesure de fournir à l'engin de reconnaissance
automatique des *a priori* plausibles. C'est notamment le cas des N-grammes qui sont utilisés dans
la majorité des applications commerciales et qui servent (presque) toujours de référence aux chercheurs du domaine. Ce sont d'ailleurs ces mêmes modèles qui seront utilisés pour l'ensemble de notre travail et qui seront présentés dans la sous-section suivante.

## 2.3 Les N-grammes

Les N-grammes sont des outils versatile. Elles sont utilisées tant dans le domaine de la reconnaissance automatique de la parole que dans ceux de la traduction automatique, du marquage de parties de discours (part-of-speech tagging), de la récapitulation de texte, de la reconnaissance de l'écriture, du traitement du langage, de la recherche d'information, etc.

Comme nous l'avons vu précédemment, l'objectif des modèles de langage dans le contexte de la RAP est de prédire le prochain mot appartenant à une séquence de mots donnée :

$$P(w_n|h) = P(w_1, w_2, \dots, w_{n-1}, w_n), \qquad (2.7)$$

où $h = w_1, w_2, \dots, w_{n-1}$. Cela est relativement simple lorsque les séquences sont très courtes. Par contre, cela devient plus difficile à mesure que l'historique croit. Nous pouvons simplifier cette équation en une multiplication de probabilités conditionnelles en utilisant la règle de chaîne :

$$ \begin{aligned} P(w_n|h) &= P(w_1)P(w_2|w_1)P(w_3|w_1, w_2) \dots P(w_n|w_1, w_2, \dots, w_{n-1}) \\ &= \prod_{n=1}^{N} P(w_n|w_1, w_2, \dots, w_{n-1}) \end{aligned} \qquad (2.8) $$

Nous pouvons ensuite traduire l'équation (2.8) en estimation du maximum de vraisemblance tel que :

$$P(w_n|h) = \frac{C(w_1)}{\sum_{w_i \in \mathcal{L}} C(w_i)} \cdot \frac{C(w_2|w_1)}{C(w_1)} \cdot \dots \cdot \frac{C(w_n|w_1, w_2, \dots, w_{n-1})}{C(w_1, w_2, \dots, w_{n-1})} \qquad (2.9)$$

où $\sum_{w_i \in \mathcal{L}} C(w_i)$ est la somme de tous les comptes.

Bien que l'équation (2.8) soit (relativement) plus facile à résoudre que l'équation (2.7), il n'en demeure pas moins que, plus la séquence est longue, plus l'exercice est difficile. L'objectif des
modèles de langage basés sur les N-grammes est donc de simplifier la prédiction du N-ième mot basé sur les N − 1 mots précédents.

Retournons à notre exemple précédent : un modèle bigramme utiliserait seulement le mot précédent pour prédire le prochain mot, un trigramme les deux mots précédents et ainsi de suite. Nous approximons donc la probabilité du N-ième mot, w_n, étant donné son historique des N − 1 mots précédents, h_{N−1} = w_{n−N+1}^{n−1}, à l'aide de l'équation

$$
\begin{align*}
P(w_n|h) \approx P(w_n|h_{N-1}) &= P(w_n|w_{n-N+1}^{n-1}) \\
&= \prod_{n=1}^{N} P(w_n|w_{n-N+1} \dots w_{n-1}). \tag{2.10}
\end{align*}
$$

Ainsi, dans notre exemple, au lieu de calculer P(mouton|s'il vous plaît dessine-moi un), nous calculerons P(mouton|un) pour un bigramme, P(mouton|dessine-moi un) pour une tri-gramme, et ainsi de suite. Nous appelons cette propriété l'hypothèse de Markov, « Markov assumption », en anglais.

Encore une fois, la façon la plus simple d’estimer la probabilité de ces N-grammes est d’avoir
recours à l’estimation du maximum de vraisemblance. Nos comptes seront alors normalisés dans
le but d’obtenir des (vraies) probabilités se situant entre 0 et 1. L’équation suivante démontre
comment on appliquerait la simplification permise par les N-grammes dans le contexte d’un
bigramme :

$$
P(w_n|w_{n-1}) = \frac{C(w_n w_{n-1})}{C(w_{n-1})}. \tag{2.11}
$$

Ce qui peut être généralisé pour n’importe quel ordre par

$$
P(w_n|h_{N-1}) = \frac{C(w_{n-N+1}^n)}{\sum_{w_n} C(w_n|w_{n-N+1}^{n-1})} = \frac{C(w_{n-N+1}^n)}{C(w_{n-N+1}^{n-1})}. \quad (2.12)
$$

Néanmoins, un des problèmes inhérents aux N-grammes est qu’elles sont sensibles au corpus
d’entrainement. Par exemple, un modèle de langage entrainé sur le texte du Petit Prince ne sera
certainement pas en mesure de prédire correctement un discours sur l’interdépendance quantique
ou encore sur le fonctionnement d’un arbre à cames. Par ailleurs, puisque les écrits et la parole ne
suivent pas les mêmes règles grammaticales et syntaxiques, des N-grammes entrainés sur un
corpus purement littéraire ne seront pas en mesure de performer adéquatement si on tente de les
utiliser dans un contexte de RAP spontanée. Cela nous amène naturellement vers le problème du
surajustement dû aux données éparses. En assumant un vocabulaire limité à 10 000 mots, un
trigramme idéalement modélisé devra couvrir 10¹² trigrammes. Des corpus de taille considérables
seront alors nécessaires pour entrainer de tels modèles : Wikipédia [30]–[32], BREF [33], One
Billion Word Corpus [34], pour n’en nommer que quelques-uns. Admettons maintenant une
couverture complète du dictionnaire Larousse (environ 135 000 mots), nous aurons alors
~2,46x10¹⁵ trigrammes possibles, si nous poussons l’exercice et considérons plutôt des
6-grammes, qui sont maintenant monnaie courante dans les systèmes commerciaux, nous en
aurons 6,053x10³⁰... Il devient alors évident qu’il est techniquement impossible (pour le
moment) de traiter, ou même de stocker une telle quantité d’information. Si l’on considère une
moyenne de 19 octets par entrée (18 octets de hachage par 6-gramme + 1 octet par probabilité
(quantifiée)), nous pouvons donc estimer qu’environ 115 015 457,67 yottaoctets<fnref n="14" /> seront
nécessaires pour stocker toutes ces 6-grammes<fnref n="15" />. Même si l’on imagine un algorithme de
compression atteignant un taux de compression de 1/1 000 000, la quantité de données (115 Yo)
dépasserait largement la capacité mondiale de stockage totale de 44x10²⁴ octets prévue pour 2020,
et ce, pour le français seulement. C’est pourquoi il est nécessaire d’avoir recours à des **algorithmes
de lissage** pour contourner ou minimiser l’effet de ces problèmes. Une autre raison de la nécessité
des algorithmes de lissage peut s’illustrer assez facilement à l’aide d’un simple exemple.
Admettons, encore une fois, la séquence « dessine-moi un », bien que nous ayons déjà observé
mouton dans notre corpus, il serait tout aussi raisonnable de penser que chat, chien, hippopotame
soient tout aussi plausibles comme suite dans la séquence. Cependant, sans les avoir préalablement
observés dans notre corpus, nous ne serions pas en mesure de leur attribuer une probabilité autre
que 0 sans avoir recours à une autre technique ou un autre type de lissage. Il serait alors impossible
pour le système de « retourner » le mot, et ce, même si le signal acoustique est sans équivoque.

Deux approches permettant de pallier les problèmes de pénurie et de dispersion de données sont
communément utilisées : le lissage statistique et le lissage sémantique. Le lissage statistique va

<footnote n="14">¹⁴ 1 yotta = 10²⁴ ou un quadrillion (1000 trilliards) selon l'échelle longue (septillion pour les états-unien(ne)s...).</footnote>

<footnote n="15">¹⁵ Il est pratique courante dans la littérature de laisser tomber les préfixes à partir du trigramme pour privilégier une notation numérique plus facile à lire (21-gramme est, on l' imagine, plus intuitif qu'icosikaihenagramme...).</footnote>
essentiellement redistribuer une partie de la masse de probabilité des événements vus aux événements non vus, tandis que le lissage sémantique va plutôt tenter de considérer directement le sens des mots pour maximiser la probabilité des séquences qui « ont un sens ».

## 2.4 Le lissage statistique

Comme nous faisons souvent face à un problème de pénurie de données avec les N-grammes, nous devons trouver un moyen d’en mitiger les effets. La méthode la plus couramment utilisée consiste à modifier les estimations du maximum de vraisemblance, EMV, des N-grammes qui n’ont pas (ou peu) été vus. Le lissage est le terme utilisé pour décrire cette redistribution de masse de probabilité. La section qui suit décrit les approches de base ainsi que le lissage Witten-Bell et Kneser-Ney utilisé dans l’ensemble de cette thèse.

### 2.4.1 Lissage additif

Le lissage additif, ou lissage de Laplace, est la forme la plus simple de lissage et consiste à ajouter une valeur $\delta$ (généralement entre 0 et 1) à tous les comptes des N-grammes (d'où le nom de « add-one smoothing » lorsque $\delta = 1$) tel que :

$$P_{add}(w_n) = \frac{C(w_n) + \delta}{\sum_{n=1}^{V} C(w_n) + \delta|V|} \qquad (2.13)$$

$$P_{add}(w_n|h_{N-1}) = \frac{C(w_n|w_{n-N+1}^{n-1}) + \delta}{C(w_n|w_{n-N+2}^{n-1}) + \delta|V|} \qquad (2.14)$$

Cette méthode de lissage, en particulier le « add-one smoothing », ne performe généralement pas de façon satisfaisante et est principalement utilisée comme méthode introductive à la modélisation du langage. Sa principale lacune vient du fait que trop de masse de probabilité est déplacée vers les zéros. Reprenons l'exemple tiré du compte Le Petit Prince tel que résumé dans le Tableau 2.1. Nous constatons que par le simple fait d'ajouter « 1 » biaise considérablement les proportions statistiques. Cela est particulièrement évident lorsque nous reconstituerons les comptes originaux à partir des probabilités lissées avec l'algorithme de Laplace. Nous avons maintenant l'équivalent de trois fois plus d'occurrences de « un » dans le corpus que « s'il » comparativement à un ratio original de 1 sur 2. Les tableaux 2.1 à 2.6 résument le même scénario, mais cette fois pour les bigrammes.
<table><caption>Tableau 2.1 : Résumé des comptes originaux $C(w_i)$, des comptes ajustés $C_{+1}(w_i)$, des probabilités originales $P(w_i)$, des probabilités ajustées $P_{+1}(w_i)$ et des comptes reconstitués, $C'(w_i)$, à partir de ces dernières.</caption><thead><tr><th>w<sub>i</sub></th><th>C(w<sub>i</sub>)</th><th>C<sub>+1</sub>(w<sub>i</sub>)</th><th>P(w<sub>i</sub>)</th><th>P<sub>+1</sub>(w<sub>i</sub>)</th><th>C'(w<sub>i</sub>)</th></tr></thead><tbody><tr><td>s'il</td><td>15</td><td>16</td><td>0,000 955 05</td><td>0,000 869 707</td><td>0,013 045 605</td></tr><tr><td>vous</td><td>55</td><td>56</td><td>0,003 501 85</td><td>0,003 043 975</td><td>0,167 418 601</td></tr><tr><td>plaît</td><td>3</td><td>4</td><td>0,000 191 01</td><td>0,000 217 427</td><td>0,000 652 28</td></tr><tr><td>dessine-moi</td><td>5</td><td>6</td><td>0,000 318 35</td><td>0,000 326 14</td><td>0,001 630 701</td></tr><tr><td>un</td><td>236</td><td>237</td><td>0,015 026 11</td><td>0,012 882 535</td><td>3,040 278 306</td></tr><tr><td>mouton</td><td>33</td><td>34</td><td>0,002 101 11</td><td>0,001 848 127</td><td>0,060 988 205</td></tr><tr><td>hein</td><td>2</td><td>3</td><td>0,000 127 34</td><td>0,000 163 07</td><td>0,000 326 14</td></tr></tbody></table>

<table><caption>Tableau 2.2 : Tableau des comptes du bigramme</caption><thead><tr><th></th><th>s'il</th><th>vous</th><th>plaît</th><th>dessine-moi</th><th>un</th><th>mouton</th><th>hein</th></tr></thead><tbody><tr><th>s'il</th><td>0</td><td>3</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>vous</th><td>1</td><td>1</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>plaît</th><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><th>dessine-moi</th><td>0</td><td>0</td><td>0</td><td>0</td><td>5</td><td>0</td><td>0</td></tr><tr><th>un</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>13</td><td>0</td></tr><tr><th>mouton</th><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>hein</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

<table><caption>Tableau 2.3 : Probabilités pour tous les bigrammes possibles.</caption><thead><tr><th></th><th>s'il</th><th>vous</th><th>plaît</th><th>dessine-moi</th><th>un</th><th>mouton</th><th>hein</th></tr></thead><tbody><tr><th>s'il</th><td>0</td><td>0,2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>vous</th><td>0,018 181 8</td><td>0,018 181 8</td><td>0,036 363 6</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>plaît</th><td>0</td><td>0</td><td>0</td><td>0,666 666 7</td><td>0</td><td>0</td><td>0</td></tr><tr><th>dessine-moi</th><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><th>un</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0,055 084 7</td><td>0</td></tr><tr><th>mouton</th><td>0,030 303</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>hein</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>
<table><caption>Tableau 2.4 : Comptes Laplace ajustés pour $\delta = 1$, les comptes qui étaient égaux à 0 apparaissent en gris.</caption><thead><tr><th></th><th>s'il</th><th>vous</th><th>plaît</th><th>dessine-moi</th><th>un</th><th>mouton</th><th>hein</th></tr></thead><tbody><tr><th>s'il</th><td>1</td><td><strong>4</strong></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>vous</th><td><strong>2</strong></td><td><strong>2</strong></td><td><strong>3</strong></td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>plaît</th><td>1</td><td>1</td><td>1</td><td><strong>3</strong></td><td>1</td><td>1</td><td>1</td></tr><tr><th>dessine-moi</th><td>1</td><td>1</td><td>1</td><td>1</td><td><strong>6</strong></td><td>1</td><td>1</td></tr><tr><th>un</th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td><strong>14</strong></td><td>1</td></tr><tr><th>mouton</th><td><strong>2</strong></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>hein</th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr></tbody></table>

<table><caption>Tableau 2.5 : Nouvelles probabilités lissées pour $\delta = 1$. Les probabilités pour les bigrammes préexistantes sont en gras.</caption><thead><tr><th></th><th>s'il</th><th>vous</th><th>plaît</th><th>dessine-moi</th><th>un</th><th>mouton</th><th>hein</th></tr></thead><tbody><tr><th>s'il</th><td>0,000 370</td><td><strong>0,001 478</strong></td><td>0,000 370</td><td>0,000 370</td><td>0,000 370</td><td>0,000 370</td><td>0,000 370</td></tr><tr><th>vous</th><td><strong>0,000 728</strong></td><td><strong>0,000 728</strong></td><td><strong>0,001 092</strong></td><td>0,000 364</td><td>0,000 364</td><td>0,000 364</td><td>0,000 364</td></tr><tr><th>plaît</th><td>0,000 371</td><td>0,000 371</td><td>0,000 371</td><td><strong>0,001 114</strong></td><td>0,000 371</td><td>0,000 371</td><td>0,000 371</td></tr><tr><th>dessine-moi</th><td>0,000 371</td><td>0,000 371</td><td>0,000 371</td><td>0,000 371</td><td><strong>0,002 226</strong></td><td>0,000 371</td><td>0,000 371</td></tr><tr><th>un</th><td>0,000 342</td><td>0,000 342</td><td>0,000 342</td><td>0,000 342</td><td>0,000 342</td><td><strong>0,004 783</strong></td><td>0,000 342</td></tr><tr><th>mouton</th><td><strong>0,000 734</strong></td><td>0,000 367</td><td>0,000 367</td><td>0,000 367</td><td>0,000 367</td><td>0,000 367</td><td>0,000 367</td></tr><tr><th>hein</th><td>0,000 371</td><td>0,000 371</td><td>0,000 371</td><td>0,000 371</td><td>0,000 371</td><td>0,000 371</td><td>0,000 371</td></tr></tbody></table>

<table><caption>Tableau 2.6 : Comptes reconstitués des bigrammes. Les comptes qui étaient égaux à 0 apparaissent en gris.</caption><thead><tr><th></th><th>s'il</th><th>vous</th><th>plaît</th><th>dessine-moi</th><th>un</th><th>mouton</th><th>hein</th></tr></thead><tbody><tr><th>s'il</th><td>0,005 543</td><td><strong>0,022 173</strong></td><td>0,005 543</td><td>0,005 543</td><td>0,005 543</td><td>0,005 543</td><td>0,005 543</td></tr><tr><th>vous</th><td><strong>0,040 058</strong></td><td><strong>0,040 058</strong></td><td><strong>0,060 087</strong></td><td>0,020 029</td><td>0,020 029</td><td>0,020 029</td><td>0,020 029</td></tr><tr><th>plaît</th><td>0,001 114</td><td>0,001 114</td><td>0,001 114</td><td><strong>0,003 341</strong></td><td>0,001 114</td><td>0,001 114</td><td>0,001 114</td></tr><tr><th>dessine-moi</th><td>0,001 855</td><td>0,001 855</td><td>0,001 855</td><td>0,001 855</td><td><strong>0,011 128</strong></td><td>0,001 855</td><td>0,001 855</td></tr><tr><th>un</th><td>0,080 629</td><td>0,080 629</td><td>0,080 629</td><td>0,080 629</td><td>0,080 629</td><td><strong>1,128 801</strong></td><td>0,080 629</td></tr><tr><th>mouton</th><td><strong>0,024 229</strong></td><td>0,012 115</td><td>0,012 115</td><td>0,012 115</td><td>0,012 115</td><td>0,012 115</td><td>0,012 115</td></tr><tr><th>hein</th><td>0,000 743</td><td>0,000 743</td><td>0,000 743</td><td>0,000 743</td><td>0,000 743</td><td>0,000 743</td><td>0,000 743</td></tr></tbody></table>
Cette démonstration, bien que simple, illustre bien le problème inhérent au lissage additif. Comme la majorité des N-grammes de niveau supérieur (trigrammes, 4-grammes, etc.) compteront généralement peu d'événements vus par rapport aux non-événements, une quantité disproportionnée de masse statistique sera redistribuée aux comptes égaux à zéro. À titre d'exemple, 75 % de la masse de probabilité pour les bigrammes débutant par « s'il » est assignée aux événements qui n'ont pas été vus. Si l'on considère maintenant le bigramme « dessine-moi un », on observe que le compte original qui était égal à deux a diminué par un facteur de trois pour passer de 2 à 0,667. C'est pourquoi le lissage par ajout est principalement utilisé comme exercice introductif au lissage des modèles de langage et ainsi permettre aux étudiants de mieux saisir son fonctionnement.

## 2.4.2 Décompte de Good-Turing

Le décompte de Good-Turing [35], ou **actualisation** Good-Turing, est central à plusieurs autres méthodes de lissage. L'intuition derrière cette méthode de lissage est d'utiliser le compte des événements que l'on a vu **une fois** pour estimer le compte des événements que l'on **n'a jamais vu**. Par ailleurs, Chen et Goodman [36] démontrent que plusieurs de ces méthodes sont des cas spéciaux de l'estimation Good-Turing. De plus, elle est rarement utilisée par elle-même puisqu'elle n'inclut pas les combinaisons de différents ordres (essentiellement les contextes avec, éventuellement, leur distribution unigrammes).

Plus formellement, le lissage Good-Turing utilise le compte $N_c$ des N-grammes qui apparaissent $c$ fois pour lisser les comptes qui apparaissent $c-1$ fois. Le vecteur $N_c$ résultant est ce qu'on appelle un vecteur de **fréquence de fréquences**. On aura alors :

$$N_c = \sum_{\{w_n: C(w_n)=c\}} 1. \qquad (2.15)$$

Puisque nous allons redistribuer de la masse statistique vers les événements non vus, il est impératif d'ajuster nos comptes originaux afin de nous assurer de toujours avoir des statistiques valides. Nous remplacerons donc les comptes EMV originaux, $c$, par des comptes $c^*$ **actualisés** selon :

$$c^* = (c + 1) \frac{N_{c+1}}{N_c} \qquad (2.16)$$
où $c$ est le compte EMV original,
$N_c$ est le nombre d'événements vus « $c$ » fois,
$N_{c+1}$ est le nombre d'événements vus « $c+1$ » fois.

Un des problèmes avec le décompte Good-Turing est que l'équation est indéfinie pour les cas où $N_c = 0$ (division par zéro). Pour remédier à ce problème, plusieurs moyens peuvent être utilisés pour lisser les $N_c = 0$. La plus simple consiste à effectuer une simple régression linéaire de la forme logarithmique, telle que :

$$ \log(N_c) = a + b \log(c) \tag{2.17} $$

pour substituer les $N_c = 0$. Cela nous mène donc au calcul des probabilités lissées selon l'algorithme de Good-Turing tel que :

$$ P_{GT}(W) = \begin{cases} \frac{N_1}{N}, & \text{si } c(W) = 0 \\ \frac{c^*}{N}, & \text{si } c(W) > 0 \end{cases}, \tag{2.18} $$

où l'on utilise le ratio de N-grammes vus une fois par rapport au nombre total de N-grammes vus lorsque le compte du N-gramme est de 0, sinon on utilise le compte ajusté $c^*$ divisé par le nombre total N de N-grammes vus.

Dans la pratique, nous considérons que les comptes élevés, $c > k$, sont fiables et on évitera généralement de les lisser si possible. Katz [37] suggère une limite $k = 5$, nous définirons donc

$$ c^* = c \text{ pour } c > k. \tag{2.19} $$

Par le fait même, nous devons corriger notre équation (2.16) initiale pour prendre en considération cette masse « non lissée » :

$$ c^* = \frac{(c+1) \frac{N_{c+1}}{N_c} - c \frac{(k+1)N_{k+1}}{N_1}}{1 - \frac{(k+1)N_{k+1}}{N_1}}, \text{ pour } 1 \le c \le k \tag{2.20} $$
Si nous reprenons l'exemple précédent du Petit Prince, et, assumant un vocabulaire de 20 000 mots, nous obtenons les tables des fréquences des fréquences (Tableau 2.7 et 2.9) ainsi que les probabilités (Tableau 2.8 et 2.10) suivantes :

<table><caption>Tableau 2.7 : Fréquence des fréquences des comptes ajustés Good-Turing et des comptes ajustés Katz pour $k = 5$ des unigrammes du texte *Le Petit Prince*.</caption><thead><tr><th>C</th><th>Compte des comptes</th><th>C<sup>*</sup></th><th>C<sup>*</sup><sub>Katz<sub>k=5</sub></sub></th></tr></thead><tbody><tr><td>0</td><td>17 309</td><td>0,091 3</td><td>0,108 604</td></tr><tr><td>1</td><td>1580</td><td>0,526 6</td><td>0,436 747</td></tr><tr><td>2</td><td>416</td><td>1,197 1</td><td>1,044 761</td></tr><tr><td>3</td><td>166</td><td>2,650 6</td><td>2,584 301</td></tr><tr><td>4</td><td>110</td><td>3,636 4</td><td>3,567 36</td></tr><tr><td>5</td><td>80</td><td>3,150 0</td><td>2,798 946</td></tr><tr><td>6</td><td>42</td><td>6,666 7</td><td>6</td></tr><tr><td>7</td><td>40</td><td>4,800 0</td><td>7</td></tr><tr><td>8</td><td>24</td><td>7,875 0</td><td>8</td></tr><tr><td>9</td><td>21</td><td>9,523 8</td><td>9</td></tr><tr><td>10</td><td>20</td><td>8,250 0</td><td>10</td></tr></tbody></table>

<table><caption>Tableau 2.8 : Comptes et probabilités d'un échantillon d'unigrammes ajustés selon le lissage Good-Turing et le lissage Katz pour $k = 5$ du texte *Le Petit Prince*.</caption><thead><tr><th>w<sub>i</sub></th><th>C(w<sub>i</sub>)</th><th>C<sup>*</sup>(w<sub>i</sub>)</th><th>P(w<sub>i</sub>)</th><th>P<sub>GT</sub>(w<sub>i</sub>)</th><th>P<sub>Katz<sub>k=5</sub></sub>(w<sub>i</sub>)</th></tr></thead><tbody><tr><td>s'il</td><td>15</td><td>14,113 416</td><td>0,000 955 05</td><td>0,000 899</td><td>0,000 955 049</td></tr><tr><td>vous</td><td>55</td><td>54,072 391</td><td>0,003 501 85</td><td>0,003 443</td><td>0,003 501 846</td></tr><tr><td>plait</td><td>3</td><td>2,650 602</td><td>0,000 191 01</td><td>0,000 169</td><td>0,000 168 764</td></tr><tr><td>dessine-moi</td><td>5</td><td>3,150 000</td><td>0,000 318 35</td><td>0,000 201</td><td>0,000 200 56</td></tr><tr><td>un</td><td>236</td><td>235,059 872</td><td>0,015 026 11</td><td>0,014 966</td><td>0,015 026 105</td></tr><tr><td>mouton</td><td>33</td><td>32,083 002</td><td>0,002 101 11</td><td>0,002 043</td><td>0,002 101 108</td></tr><tr><td>hein</td><td>2</td><td>1,197 115</td><td>0,000 127 34</td><td>0,000 076</td><td>7,622 03 × 10<sup>-5</sup></td></tr></tbody></table>
<table><caption>Tableau 2.9 : Fréquence des fréquences des comptes ajustés selon le lissage Good-Turing et des comptes ajustés le lissage Katz pour k=5 des unigrammes du texte *Le Petit Prince*. Les comptes originaux sont lissés selon une régression linéaire telle que définie à l'équation (2.17).</caption><thead><tr><th>C</th><th>Compte des comptes (loi de puissance)</th><th>C<sup>*</sup></th><th>C<sup>*</sup><sub>Katz<sub>k=5</sub></sub></th></tr></thead><tbody><tr><td>0</td><td>17 309 000 000</td><td>0,090 6</td><td>0,107 82</td></tr><tr><td>1</td><td>1568,600 000</td><td>0,519 8</td><td>0,428 67</td></tr><tr><td>2</td><td>407,671 076</td><td>1,364 0</td><td>1,243 26</td></tr><tr><td>3</td><td>185,348 251</td><td>2,286 5</td><td>2,151 16</td></tr><tr><td>4</td><td>105,951 617</td><td>3,240 2</td><td>3,096 07</td></tr><tr><td>5</td><td>68,661 695</td><td>4,209 4</td><td>4,059 41</td></tr><tr><td>6</td><td>48,171 057</td><td>5,187 4</td><td>6</td></tr><tr><td>7</td><td>35,697 814</td><td>6,171 0</td><td>7</td></tr><tr><td>8</td><td>27,536 280</td><td>7,158 2</td><td>8</td></tr><tr><td>9</td><td>21,901 042</td><td>8,147 9</td><td>9</td></tr><tr><td>10</td><td>17,844 822</td><td>9,246 4</td><td>10</td></tr></tbody></table>

<table><caption>Tableau 2.10 : Comptes et probabilités d'un échantillon d'unigrammes ajustés Good-Turing et Katz pour $k=5$ du texte *Le Petit Prince*. Les comptes originaux sont lissés selon une régression linéaire telle que définie à l'équation (2.17).</caption><thead><tr><th>w<sub>i</sub></th><th>C(w<sub>i</sub>)</th><th>C<sup>*</sup>(w<sub>i</sub>)</th><th>P(w<sub>i</sub>)</th><th>P<sub>GT</sub>(w<sub>i</sub>)</th><th>P<sub>GT<sub>k=5</sub></sub>(w<sub>i</sub>)</th></tr></thead><tbody><tr><td>s'il</td><td>15</td><td>13,117 25</td><td>0,000 955 05</td><td>0,000 835</td><td>0,000 955 049</td></tr><tr><td>vous</td><td>55</td><td>54,072 39</td><td>0,003 501 85</td><td>0,003 443</td><td>0,003 501 846</td></tr><tr><td>plâit</td><td>3</td><td>2,286 54</td><td>0,000 191 01</td><td>0,000 146</td><td>0,000 145 584</td></tr><tr><td>dessine-moi</td><td>5</td><td>4,209 43</td><td>0,000 318 35</td><td>0,000 268</td><td>0,000 268 014</td></tr><tr><td>un</td><td>236</td><td>235,059 87</td><td>0,015 026 11</td><td>0,014 966</td><td>0,015 026 105</td></tr><tr><td>mouton</td><td>33</td><td>32,083 00</td><td>0,002 101 11</td><td>0,002 043</td><td>0,002 101 108</td></tr><tr><td>hein</td><td>2</td><td>1,363 95</td><td>0,000 127 34</td><td>0,000 087</td><td>8,684 26 × 10<sup>-5</sup></td></tr></tbody></table>

### 2.4.3 Lissage par interpolation (Jelinek et Mercer)

Bien que les techniques de lissage vues dans les sections précédentes permettent, jusqu'à un certain point, d'améliorer les performances, la généralisation, des modèles de langage, celles-ci ne suffisent pas à elles-mêmes pour obtenir des modèles de langage qui performent bien dans des tâches courantes. C'est pourquoi elles sont habituellement utilisées de pair avec d'autres méthodes
de lissage telles que le lissage par repli « Backoff » ou le lissage par interpolation puisque leur lacune principale est que les N-grammes d'ordre supérieurs ($N \ge 2$) ne sont pas en mesure d'exploiter l'information inhérente à la distribution des N-grammes d'ordre inférieurs. Prenons l'exemple suivant :

dessine-moi un mouton

dessine-moi un xénomorphe

Si l'on assume qu'aucun de ces trigrammes n'ait été vu, on devrait normalement, à moins d'être un grand fan de la fiction Alien<fnref n="16" />, assigner une plus grande probabilité à l'expression « dessine-moi un mouton » que « dessine-moi un xénomorphe ». Toutefois, les algorithmes de lissage vus jusqu'à présent ne permettent pas de faire la distinction entre les deux. Pourtant, il serait plus logique d'aller voir la distribution de l'ordre inférieur pour assigner une probabilité aux N-grammes jamais vue. C'est l'intuition derrière le lissage par interpolation. La méthode intuitive la plus simple et est l'interpolation linéaire où

$$P_{\text{interp.}}(w_n|w_{n-N+1}^{n-1}) = \sum_{i=1}^{N} \lambda_i P_{\text{EMV}}(w_n|w_{n-N+i}^{n-1}) \quad (2.21)$$

et où

$$\sum_{i=1}^{N} \lambda_i = 1.$$

À titre d'exemple, supposons disposer du trigramme x, y, z, nous aurons alors :

$$P_{\text{interp.}}(z|x, y) = \lambda_1 P_{\text{EM}}(z|x, y) + \lambda_2 P_{\text{EMV}}(z|y) + \lambda_3 P_{\text{EM}}(z). \quad (2.22)$$

Une version plus élaborée conditionne les probabilités selon des poids $\lambda_i$ qui dépendent du contexte $w_{n-N+1}^{n-1}$ où

<footnote n="16">¹⁶ On parlera alors d'adaptation du modèle de langage.</footnote>
$$P_{\text{interp.}}(w_n|w_{n-N+1}^{n-1}) = \sum_{i=1}^{N} \lambda_i(w_{n-N+1}^{n-1}) P_{\text{EMV}}(w_n|w_{n-N+i}^{n-1}) \quad (2.23)$$

et où

$$\sum_{i=1}^{N} \lambda_i(w_{n-N+1}^{n-1}) = 1.$$

Afin que la somme des probabilités soit égale à 1 (sinon on ne pourrait évidemment pas parler de statistiques, mais plutôt de pondération<fnref n="17" />). Nous serons donc en mesure d'attribuer plus de poids aux trigrammes ayant un contexte fiable (bigramme ayant un « grand » nombre d'apparitions) et moins de poids aux autres trigrammes ayant un contexte moins fiable. En outre, il nous est possible de reculer jusqu'à l'ordre 0. Une technique courante consiste à assigner une probabilité uniforme telle que

$$P_{\text{unif.}}(w_i) = \frac{1}{|V|}. \qquad (2.24)$$

Comme on peut le constater par l'équation (2.23), nous aurons idéalement des poids $\lambda_i(w_{n-N+1}^{n-1})$ distincts pour chaque historique distinct. Il est très difficile (pour le moment) de tous les optimiser, en particulier pour les ordres supérieurs, en raison de la croissance exponentielle d'historiques possibles et de la quantité phénoménale de données nécessaire à l'optimisation d'un tel nombre de paramètres (pour ce qui est de la complexité computationnelle, les avancées récentes et à venir en computation quantique risquent de rendre cet obstacle chose du passé). Jelinek et Mercer [39], Brown et al. [40], proposent donc de placer les comptes dans un nombre de seaux (« buckets ») basé sur leur similarité. L'équation, récursive, qu'ils proposent est la suivante :

$$P_{\text{JM}}(w_n|w_{n-N+1}^{n-1}) = \lambda(w_{n-N+1}^{n-1}) P_{\text{EMV}}(w_n|w_{n-N+1}^{n-1}) \\ + (1 - \lambda(w_{n-N+1}^{n-1})) P_{\text{JM}}(w_n|w_{n-N+2}^{n-1}). \quad (2.25)$$

<footnote n="17">¹⁷ Notons que, dans un contexte de modèles de langage très volumineux, la méthode par pondération peut nous donner des résultats plus que satisfaisants [38]</footnote>
Idéalement ce conditionnement sera effectué sur un corpus dit de développement<fnref n="18" />. Les paramètres $\lambda$ seront alors optimisés, à l'aide d'un algorithme de notre choix, pour minimiser la **perplexité** (ou tout autre métrique d'intérêt) du modèle par rapport au corpus de développement.

### 2.4.4 Lissage par repli « backoff »

Comme le lissage par interpolation, le lissage par repli fait appel aux N-grammes d'ordre inférieur pour attribuer une probabilité aux événements non vus. Un des algorithmes les plus connus est le repli de Katz [37] : si on rencontre un N-gramme ayant un compte de zéro, on l'approxime en se repliant vers sa (N-1)-gramme tel que

$$P_{\text{katz}}(w_n|w_{n-N+1}^{n-1}) = \begin{cases} P^*(w_n|w_{n-N+1}^{n-1}), & \text{si } C(w_n|w_{n-N+1}^{n-1}) > 0 \\ \alpha(w_{n-N+1}^{n-1})P_{\text{katz}}(w_n|w_{n-N+2}^{n-1}), & \text{sinon} \end{cases} \quad (2.26)$$

où $\alpha$ est un facteur de normalisation nécessaire pour que les probabilités soient à 1,
$P^*$ est la probabilité actualisée.

L'équation (2.26) nous montre que nous utilisons simplement la probabilité actualisée si le N-gramme a déjà été vu, sans quoi nous nous replions de façon récursive jusqu'à ce que nous atteignions une soit un (N-1)-gramme déjà vu, ou éventuellement une probabilité unigramme actualisée.

Encore une fois, si l'on reprend l'exemple du trigramme $x, y, z$, nous aurons alors :

$$P_{\text{katz}}(z|x, y) = \begin{cases} P^*(z|x, y), & \text{si } C(z|x, y) > 0 \\ \alpha(x, y)P_{\text{katz}}(y), & \text{sinon si } C(z|y) > 0 \\ P^*(z) & \text{sinon} \end{cases} \quad (2.27)$$

$$P_{\text{katz}}(z|y) = \begin{cases} P^*(z|y), & \text{si } C(z|y) > 0 \\ \alpha(y)P^*(z), & \text{sinon} \end{cases}.$$

Les $\alpha$ sont calculés pour le contexte tel que :

<footnote n="18">¹⁸ De façon générale, un corpus utilisé pour la modélisation du langage est composé de trois parties : partie entrainement « training », comporte la majorité du texte, partie de développement « dev. » qui est utilisé strictement pour l'optimisation des paramètres et partie d'évaluation « test » qui comme le nom l'indique, est utilisée pour évaluer nos modèles.</footnote>
$$ \alpha(w_{n-N+1}^{n-1}) = \frac{1 - \sum_{\{w_n: C(w_n|w_{n-N+1}^{n-1}) > 0\}} P^*(w_n|w_{n-N+1}^{n-1})}{1 - \sum_{\{w_n: C(w_n|w_{n-N+1}^{n-1}) > 0\}} P^*(w_n|w_{n-N+2}^{n-1})} \quad (2.28) $$

ceux-ci représentent un ratio de la masse de probabilité restante au niveau du N-gramme par rapport à la masse de probabilité restante au niveau du (N-1)-gramme.

*Repli stupide*<fnref n="19" /> « *Stupid backoff*»

Une technique de repli proposée assez récemment par Brants et al. [38] et qui a fait ses preuves est le **repli stupide**. L'intuition derrière cette technique est que puisque la création de modèles de langage volumineux est complexe, que l'on devrait pouvoir se contenter d'utiliser la force brute rendue possible par la disponibilité de corpus de très grande taille. On abandonne donc l'idée de construire des modèles de langage représentant une vraie distribution de probabilité : on se contente de construire un **modèle de scores pondérés**. On peut justifier ce choix en arguant que ce qui importe vraiment dans notre équation (2.4) initiale est que le mot ayant le **score** le plus important soit choisi. L'équation originale proposée ne fait pas appel à des probabilités actualisées et utilise directement les probabilités EMV. Par ailleurs, comme on ne peut plus vraiment parler de probabilités, on notera S le score retourné par l'équation :

$$ S(w_n|w_{n-N+1}^{n-1}) = \begin{cases} P(w_n|w_{n-N+1}^{n-1}), & \text{si } C(w_n|w_{n-N+1}^{n-1}) > 0 \\ \alpha S(w_n|w_{n-N+2}^{n-1}), & \text{sinon} \end{cases} \quad (2.29) $$

et où $\alpha$ est le facteur d'ajustement commun à tous les N-grammes et où Brants et al. [38] ont déterminé de façon empirique qu'une valeur de 0,4 était plus que satisfaisante.

### 2.4.5 Witten-Bell

L'intuition du lissage Witten-Bell (Witten et Bell [24]) repose sur la supposition que la fréquence avec laquelle un (N-1)-gramme constitue un contexte soit proportionnelle à la probabilité estimée qu'elle préfixe un N-gramme inédit<fnref n="20" />. Pour illustrer cela, comparons les bigrammes- « je suis » et « je supporte » rencontrées dans l'œuvre Le Petit Prince, le bigramme- « je suis » préfixe beaucoup plus de trigrammes distincts (20) comparativement à seulement une pour « je

<footnote n="19">¹⁹ Les auteurs remarquent que le nom « *Stupid backoff* » avait été donné à la technique parce qu'ils pensaient que quelque chose d' aussi simple (« *stupid* ») ne pourrait jamais fonctionner. Ils avaient tort, mais ont décidé de garder le nom quand même (qui est d'ailleurs bien apprécié par tout scientifique avec, ne serait-ce, qu'un grain d'humour).</footnote>

<footnote n="20">²⁰ On fait souvent référence à cette propriété dans la littérature en employant l'expression **diversité des mots prédits**.</footnote>
supporte ». Il serait raisonnable de supposer que « je suis grand » est beaucoup plus probable que « je supporte grand » même si ces deux trigrammes n'ont jamais été vus. Le lissage Witten-Bell modélise donc la probabilité d'observer un N-gramme pour la première fois. L'équation générale du lissage Witten-Bell (Witten et Bell [24], Chen et Goodman [36]), qui est un cas particulier du lissage Jelinek et Mercer, est définie par :

$$
P_{\text{WB}}(w_n|w_{n-N+1}^{n-1}) = \lambda(w_{n-N+1}^{n-1})P(w_n|w_{n-N+1}^{n-1}) + (1-\lambda(w_{n-N+1}^{n-1}))P_{\text{WB}}(w_n|w_{n-N+2}^{n-1}) \quad (2.30)
$$

Pour calculer les paramètres d'ajustement λ on se base sur le nombre de mots distincts qui suivent
un historique $w_{n-N+1}^{n-1}$ tel que :

$$
N_{1+}(w_{n-N+1}^{n-1} \bullet) = |\{w_n : C(w_n|w_{n-N+1}^{n-1}) > 0\}| \quad (2.31)
$$

où $N_{1+}(w_{n-N+1}^{n-1} \bullet)$ est le nombre de N-grammes vus une ou plusieurs fois et qui débutent par
$w_{n-N+1}^{n-1}$,

• est une variable libre (n'importe quel mot ou unigramme) suivant l'historique $w_{n-N+1}^{n-1}$.

Le reste de l'équation suit une notation mathématique plutôt classique où $|x|$ réfère à la cardinalité d'un ensemble (le nombre d'éléments distincts), $\{y\}$ représente un ensemble quelconque et $\{w_n: C(w_n|w_{n-N+1}^{n-1}) > 0\}$ est l'ensemble de tous les N-grammes se terminant par $w_n$ ayant un compte supérieur à zéro. La notation $N_{1+}$ peut quant à elle être généralisée par $N_{k\pm}$ pour signifier toute expression qui apparaît $k$ fois, $k$ ou plusieurs fois ($k+$), ou $k$ ou moins de fois ($k$-). Nous verrons plus tard que cette notation est utilisée dans d'autres algorithmes de lissage, tel que le lissage Kneser-Ney. Par conséquent, on peut lire $N_{1+}(w_{n-N+1}^{n-1} \bullet)$ comme étant le nombre de mots distincts que le (N-1)-gramme $w_{n-N+1}^{n-1}$ précède. Pour calculer les $\lambda_{w_{n-N+1}^{n-1}}$, sensibles au contexte, Witten et Bell proposent :

$$
1 - \lambda(w_{n-N+1}^{n-1}) = \frac{N_{1+}(w_{n-N+1}^{n-1} \bullet)}{N_{1+}(w_{n-N+1}^{n-1} \bullet) + C(w_{n-N+1}^{n-1})} \quad (2.32)
$$

En substituant (2.32) dans (2.30) on obtient [36] :
$$P_{WB}(w_n|w_{n-N+1}^{n-1}) = \frac{C(w_n|w_{n-N+1}^{n-1}) + N_{1+}(w_{n-N+1}^{n-1}\bullet)P_{WB}(w_n|w_{n-N+2}^{n-1})}{N_{1+}(w_{n-N+1}^{n-1}\bullet) + C(w_{n-N+1}^{n-1})} \quad (2.33)$$

Le lissage Witten-Bell (selon (2.30)) accordera ainsi plus de poids à un N-gramme déjà vu et, sinon, sera en mesure d'estimer la probabilité de rencontrer une nouvelle N-gramme.

### 2.4.6 Décompte absolu (Absolute discounting)

Le décompte absolu (Ney, Essen, and Kneser [41]) est une variante du lissage par interpolation. Au lieu de multiplier la probabilité d'ordre supérieur (le N-gramme) par un facteur $\lambda$, on va, à l'inverse du lissage additif, soustraire une constante $0 \le D \le 1$ aux N-grammes vus une fois ou plus pour ensuite redistribuer cette masse aux N-grammes jamais vus :

$$P_{abs}(w_n|w_{n-N+1}^{n-1}) = \frac{\max\{C(w_n|w_{n-N+1}^{n-1}) - D, 0\}}{C(w_{n-N+1}^{n-1})} + (1 - \lambda_{w_{n-N+1}^{n-1}})P_{abs}(w_n|w_{n-N+2}^{n-1}). \quad (2.34)$$

Pour que la distribution de probabilité se somme à un, nous définissons

$$1 - \lambda_{w_{n-N+1}^{n-1}} = \frac{D}{C(w_{n-N+1}^{n-1})} N_{1+}(w_{n-N+1}^{n-1}\bullet). \quad (2.35)$$

Ney, Essen et Kneser [41] suggèrent une valeur de D :

$$D = \frac{N_1}{N_1 + 2N_2}. \quad (2.36)$$

Où $N_1$ et $N_2$ respectent la notation vue précédemment ($N_1$ est le nombre de N-grammes vus exactement une fois et $N_2$ le nombre de N-grammes vus exactement deux fois). Church et Gale montrent empiriquement dans [42] comment les comptes supérieurs à 3 ont essentiellement un décompte Good-Turing relativement constant. Cette démonstration inspirera d'ailleurs Kneser et Ney à proposer le lissage Kneser-Ney dans [43].

### 2.4.7 Kneser-Ney

Le lissage Kneser-Ney (Kneser et [43]) est, tel que mentionné précédemment, basé sur le décompte absolu. À l'inverse du lissage Witten-Bell qui tente de modéliser la diversité des mots prédits, le lissage Kneser-Ney va plutôt tenter de modéliser la **diversité des historiques**. C'est-à-dire qu'à l'inverse de Witten-Bell, qui se résume à considérer le nombre de N-grammes différents constitués par l'historique $h_{N-1}$, le lissage Kneser-Ney va plutôt considérer le nombre d'historiques dans
lesquels le mot $w_n$ apparaît. On parle alors ici de **probabilité de continuation** : c'est-à-dire la probabilité qu'un mot complète un nouvel historique. Admettons que l'on doit reculer à un unigramme pour compléter la phrase suivante :


 j'ai le ______ que toi 


Le mot « même » semblerait à première vue beaucoup plus probable que « prince » pour compléter cette phrase. Toutefois, si on se fie aux comptes du texte Le Petit Prince, le mot « prince » est beaucoup plus fréquent (172 occurrences) que « même » (24 occurrences) et donc, un unigramme choisira plutôt « prince » pour compléter la phrase. Le lissage Kneser-Ney exploite l'intuition que même si « prince » est fréquent, il l'est seulement après le mot « petit », c'est-à-dire dans le bigramme « petit prince ». Le mot « même » quant à lui complète beaucoup plus de bigrammes différents.

C'est sur cette intuition de continuité proposée par Kneser et [43], mais présenté de façon beaucoup plus claire par Chen et Goodman [36] que s'appuie l'estimation Kneser-Ney où :

$$P_{KN}(w_n|w_{n-N+1}^{n-1}) = \frac{\max\{C(w_n|w_{n-N+1}^{n-1}) - D, 0\}}{C(w_{n-N+1}^{n-1})} + \frac{D \cdot N_{1+}(w_{n-N+1}^{n-1} \bullet)}{C(w_{n-N+1}^{n-1})} P_{KN}(w_n|w_{n-N+2}^{n-1}). \quad (2.37)$$

Pour trouver la distribution unigramme, on a :

$$P_{KN}(w_n) = \frac{N_{1+}(\bullet w_n)}{N_{1+}(\bullet\bullet)} \quad (2.38)$$

où $N_{1+}(\bullet w_n) = |\{w_{n-1}: C(w_n|w_{n-1}) > 0\}|$ est le nombre bigrammes vus que le mot $w_n$ complète,

$N_{1+}(\bullet\bullet) = \sum_{w_n} N_{1+}(\bullet w_n)$ est le nombre total de **types** 21 de bigrammes vus.

En généralisant (2.37) pour les N-grammes de plus grand ordre, on obtient :

<footnote n="21">21 Le terme type fait ici référence aux uniques, par exemple la phrase « un mouton dans un champ » compte cinq mots, mais seulement quatre types (un, mouton, dans, champ).</footnote>
$$P_{KN}(w_n|w_{n-N+2}^{n-1}) = \frac{N_{1+}(\bullet w_{n-N+2}^n)}{N_{1+}(\bullet w_{n-N+2}^{n-1}\bullet)} \quad (2.39)$$

où

$$N_{1+}(\bullet w_{n-N+2}^n) = |\{w_{n-N+1}: C(w_n|w_{n-N+2}^{n-1}, w_{n-N+1}) > 0\}| \quad (2.40)$$

et

$$\begin{align*} N_{1+}(\bullet w_{n-N+2}^{n-1}\bullet) &= |\{(w_n, w_{n-N+1}): C(w_n|w_{n-N+2}^{n-1}, w_{n-N+1}) > 0\}| \\ &= \sum_{w_n} N_{1+}(\bullet w_{n-N+2}^n) \quad (2.41) \end{align*}$$

où $N_{1+}(\bullet w_{n-N+2}^n)$ est le nombre de N-grammes que le (N-1)-gramme $w_{n-N+2}^n$ complète.

$N_{1+}(\bullet w_{n-N+2}^{n-1}\bullet)$ est le nombre total de types de N-grammes différents vus avec $w_{n-N+2}^{n-1}$.

Par exemple, pour le 4-gramme s, x, y, z nous aurions

$$N_{1+}(\bullet x, y, z) = |\{s: C(s, x, y, z) > 0\}|$$

$$N_{1+}(\bullet x, y\bullet) = |\{(s, z): C(s, x, y, z) > 0\}| = \sum_{z} N_{1+}(\bullet x, y, z)$$

### 2.4.8 Kneser-Ney modifié (Modified Kneser-Ney)

Le lissage Kneser-Ney modifié (Chen et Goodman [44]) est l'une des versions les plus performantes du lissage Kneser-Ney. Au lieu d'utiliser un seul facteur de décompte, trois (4 si on compte $D_0 = 0$) différentes valeurs sont utilisées, soit $D_1$, $D_2$ et $D_{3+}$ et respectivement appliqués aux N-grammes avec un compte d'un, deux et trois ou plus, respectivement :

<footnote n="22">22 Cette équation n'est que très rarement abordée formellement d'un point de vue des ordres supérieurs dans la littérature. Ceci nous laisse donc deux interprétations possibles, soit le nombre total de types de N-grammes vus, ou le nombre total de types de N-grammes ayant comme cœur $w_2, w_3, \dots, w_{n-1}$. D'ailleurs Chen et Goodman [44] simplifient à $P_{KN}(w_n|w_{n-N+1}^{n-1}) = \frac{\max\{N_{1+}(w_{n-N+1}^n)-D_0\}}{\sum_{w_n} N_{1+}(w_{n-N+1}^n)} + \frac{D_1 \cdot N_{1+}(w_{n-N+1}^{n-1}\bullet)}{\sum_{w_n} N_{1+}(w_{n-N+1}^{n-1}\bullet)} P_{KN}(w_n|w_{n-N+2}^{n-1})$ pour les ordres inférieurs.</footnote>
$$
D = \begin{cases} 0 & \text{si } C = 0 \\ D_1 & \text{si } C = 1 \\ D_2 & \text{si } C = 2 \\ D_{3+} & \text{si } C \ge 3 \end{cases} \tag{2.42}
$$

Si on modifie (2.37) pour tenir compte de cette modification, on obtient :

$$
P_{MKN}(w_n|w_{n-N+1}^{n-1}) = \frac{C(w_n|w_{n-N+1}^{n-1}) - D(C(w_n|w_{n-N+1}^{n-1}))}{C(w_{n-N+1}^{n-1})} + \gamma(w_{n-N+1}^{n-1})P_{MKN}(w_n|w_{n-N+2}^{n-1}). \tag{2.43}
$$

Pour que le tout somme à 1, on définit

$$
\gamma(w_{n-N+1}^{n-1}) = \frac{D_1 N_1(w_{n-N+1}^{n-1} \bullet) + D_2 N_2(w_{n-N+1}^{n-1} \bullet) + D_{3+} N_{3+}(w_{n-N+1}^{n-1} \bullet)}{C(w_{n-N+1}^{n-1})} \quad (2.44)
$$

et où on définit généralement (pour la simplicité et parce que ça fonctionne bien) :

$$
Y = \frac{N_1}{N_1 + 2N_2}
$$

$$
D_1 = 1 - 2Y \frac{N_2}{N_1} \tag{2.45}
$$

$$
D_2 = 2 - 3Y \frac{N_3}{N_2}
$$

$$
D_{3+} = 3 - 4Y \frac{N_4}{N_3}.
$$

Cela est cohérent avec l'observation de Church et Gale [42] que les comptes supérieurs à 3 ont
essentiellement un décompte Good-Turing relativement constant.

2.4.9 Basé sur les classes

Le lissage des *N*-grammes basé sur les classes repose sur l'intuition que des mots appartenant à la même classe auront un comportement similaire. Un exemple souvent utilisé est celui d'un système de réservation de vols commerciaux aériens. On veut modéliser le bigramme « vers Bathurst », mais on a seulement rencontré « vers Toronto », « vers Montréal », « vers Moncton » dans notre corpus d'entrainement. Si on sait que « bathurst » est une ville, on pourra alors prédire la probabilité qu'il apparaisse après « vers ». L'algorithme de lissage par classe le plus simple est le regroupement IBM (*IBM clustering*) [40] et est généralisé par Uszkoreit et Brants dans [45] :
$$P(w_n|w_{n-N+1}^{n-1}) \approx P(w_n|c(w_n)) \times P(c(w_n)|w_{n-N+1}^{n-1}) \quad (2.46)$$

où $P(w_n|c(w_n)) = \frac{C(w_n)}{C(c_n)}$ la fréquence relative du mot par rapport à la classe,

$P(c(w_n)|w_{n-N+1}^{n-1}) = \frac{C(w_{n-N+1}^{n-1}c(w_n))}{C(w_{n-N+1}^{n-1})}$ la probabilité que la classe $c_n$ suive la séquence de mots $w_{n-N+1}^{n-1}$.

Les classes pourront être définies de façon manuelle, ou automatique selon les besoins. Par ailleurs, les mots peuvent appartenir à plusieurs classes dans le cas du regroupement « soft », ou à une seule classe dans le cas du regroupement « hard ». Finalement, ces N-grammes sont habituellement interpolés avec des N-grammes conventionnels afin d'obtenir des performances adéquates.

## 2.5 Un résumé d'autres techniques récentes de lissage

Bien que cette thèse se concentre sur le lissage des N-grammes, cette section présente d'autres méthodes de modélisation et de lissage du langage que nous n'avons pas pu couvrir dans le cadre de cette thèse, mais que nous jugions tout de même important de mentionner étant donné leur adoption grandissante dans le domaine de la modélisation du langage.

### 2.5.1 Lissage bayésien

Bien que l'approche bayésienne ait été largement adoptée par la communauté en apprentissage machine, il demeure que son application dans le domaine du traitement de la parole est relativement limitée [46]. Une des approches bayésiennes ayant connu un fort succès est la modélisation par processus Pitman-Yor (hiérarchiques) [47]–[49]. Les modèles basés sur le processus PY sont illustrés par l'équation suivante :

$$G \sim PY(d, \alpha_0, G_0). \quad (2.47)$$

où $G = [G(w)]_{w \in \mathcal{L}}$ est le vecteur des probabilités unigrammes $G(w)$ des mots du vocabulaire $\mathcal{L}$.
$G_0 = [G_0(w)]_{w \in \mathcal{L}}$ est une distribution de base pour les $w$ et où on assume généralement que $G_0 = 1/|\mathcal{L}|$ pour tout $w \in \mathcal{L}$ dans la pratique.

$0 \le d \le 1$ est un paramètre de décompte.

$\alpha_0$ est un paramètre d'influence et est utilisé avec $d$ pour contrôler le degré de variabilité autour de $G_0$.

La métaphore la plus souvent utilisée pour expliquer ce processus est celle du restaurant chinois [50]. Cette métaphore définit la probabilité qu'un client entrant au restaurant s'assoie à la table $k$ est proportionnel au nombre de clients déjà assis à cette table $c_k - d$, ou à une nouvelle table de façon proportionnelle à $\alpha_0 + d_m$, et, où $m$. est le nombre de tables déjà occupées. Nous obtenons alors :

$$p(z_i = k | z^{-i}, d, \alpha_0) = \begin{cases} \frac{c_k - d}{\alpha_0 + c.} & 1 \le k \le m. \\ \frac{\alpha_0 + d_m}{\alpha_0 + c.} & k = m. + 1. \end{cases} \quad (2.48)$$

La probabilité que le $i$-ème client choisit la table, indexée par $z_i$, $k$ étant donné la disposition des sièges choisie par les $i-1$ clients précédents et où $z^{-i} = \{z_1, ..., z_{i-1}\}$ et $c$. est le nombre total de clients. Cela nous permettra par la suite de définir le lissage Pitman-Yor hiérarchique, tel que :

$$P_{PYH}(w_n|h_{N-1}, S, d_{|h_{N-1}|}, \alpha_{|h_{N-1}|}) = \frac{C(w_{n-N+1}^n) - d_{|h_{N-1}|} N_{1+}(\bullet w_n)}{\alpha_{|h_{N-1}|} + C(w_{n-N+1}^{n-1})} \\ + \frac{\alpha_{|h_{N-1}|} + d_{|h_{N-1}|} N_{1+}}{\alpha_{|h_{N-1}|} + C(w_{n-N+1}^{n-1})} , \quad (2.49) \\ \times P_{PYH}(w_n|h_{N-2}, S, d_{|h_{N-2}|}, \alpha_{|h_{N-2}|})$$

où les inférences du modèle, $S$, font appel à l'échantillonnage de Gibbs ;

$0 \le d_{|h_{N-1}|} \le 1$ est un paramètre de décompte propre au contexte $h_{N-1}$, (ou à sa longueur);

$\alpha_{|h_{N-1}|}$ est un paramètre d'influence propre au contexte $h_{N-1}$ (ou à sa longueur) et est utilisé avec $d_{|h_{N-1}|}$ pour contrôler le degré de variabilité autour de $G_0$, la distribution unigramme globale moyenne.
Par ailleurs, Teh démontre dans [47] comment le lissage Kneser-Ney interpolé peut être généralisé par un modèle de langue Pitman-Yor hiérarchique. Une autre des propriétés intéressantes du processus Pitman-Yor est qu’il produit une loi de puissance qui est similaire à ce que l’on retrouve dans le langage naturel [47] (voir la loi de Zipf–Mandelbrot [51], [52]).

La difficulté principale qui a fait en sorte que ces techniques bayésiennes ne soient pas adoptées à plus grande échelle est due à leur complexité computationnelle (nombre de paramètres très élevés, entre autres). Cependant, comme pour le cas des réseaux de neurones, les avancés en termes de puissances de calcul, autant du point de vue des unités centrales multicœurs et des processeurs graphiques (Graphical Processing Unit [GPU]) font en sorte que nous nous attendons à l’arrivée de l’application de techniques complètement bayésiennes pour le traitement de la parole et, notamment, pour la modélisation du langage.

## Allocation de Dirichlet latente

Le lissage, ou l'adaptation des modèles de langage basés sur la sémantique est un domaine de recherche qui s'appuie sur la recherche effectuée dans la sphère de la recherche d'information/indexation des données. En effet, les moteurs de recherche, par exemple, ont pour but de lier des mots, des expressions, à des documents pour retourner les plus pertinents à l'utilisateur. Ces mêmes principes peuvent être exploités pour nous permettre de faire ressortir les sujets traités dans un discours, et du même coup, nous permettre de donner une sorte de mémoire à long terme à nos modèles de langage qui pourront alors privilégier les termes importants au sujet ou aux sujets en cours.

L'allocation de Dirichlet latente [53] (ADL) est un modèle hiérarchique bayésien à trois niveaux basé à la fois sur les mots qui sont modélisés comme une mixture finie sur un ensemble sous-jacent de sujets et la mixture de ces sujets 23(topic) propres à l'ensemble des documents (vus, et éventuellement jamais vus) d'une collection donnée. C'est donc un modèle probabiliste **génératif** de corpus qui nous permet de déterminer le sujet d'un document basé sur sa distribution de sujets qui sont eux-mêmes définis par une distribution de mots telle que :

<footnote n="23">23 Notons que par sujet nous entendons sujet d'un point de vue majoritairement statistique et pas nécessairement du point de vue de la fonction grammaticale qui donne au verbe son nombre et son genre.</footnote>
$$P(d_l, t_l, \theta_{d_l} | \alpha, \beta) = P(\theta_{d_l} | \alpha) \prod_{i=1}^{N} P(t_{i,l} | \theta_{d_l}) P(w_{i,l} | t_{i,l}, \beta), \qquad (2.50)$$

où w est un mot, $d_l = [w_{1,l}, w_{2,l}, ..., w_{N,l}]$ est un document et est composé d'une séquence de mots où $w_{n,l}$ est le nième mot dans la séquence du $l^e$ document et $t_l = [t_{1,l}, t_{2,l}, ..., t_{N,l}]$ est l'ensemble de sujets assignés à chaque mot $w_{n,l}$ du document $d_l$ et où $t_{i,l} \in \{t_1, t_2, ..., t_K\}$ est tiré de l'ensemble des K sujets définissant le corpus. $d_l$ est alors un document appartenant à un corpus de M documents tel que $D = \{d_1, d_2, ..., d_M\}$. Les paramètres $\alpha$ et $\beta$ sont des paramètres au niveau du corpus et sont échantillonnés une seule fois lors de « l'entrainement » pour maximiser la densité marginale du « document » d'entrainement. Les paramètres $\alpha = \{\alpha_1, ..., \alpha_K\}$ représentent les paramètres Dirichlet pour les K sujets latents au corpus et $\beta_{t_k, w_n} = P(w_n|t_k)$ est le paramètre Dirichlet propre aux mots. Finalement, $\theta_{d_l}$ est un vecteur de variables propres à chaque document $d_l$ et représente sa distribution de sujets.

En généralisant pour les N-grammes, nous obtenons un modèle de langage ADL basé sur l'historique [54] :

$$P_{ADL}(w_n|h_{N-1}, \alpha, \beta) = \sum_{k=1}^{K} \beta_{t_k, w_n} \frac{g(h_{N-1}, \alpha_k)}{\sum_{j=1}^{K} g(h_{N-1}, \alpha_j)}, \qquad (2.51)$$

où l'historique $h_{N-1}$ est transformé en un espace de sujets à l'aide d'une fonction $g(\cdot)$ qui prend le paramètre Dirichlet $\alpha$ comme entrée pour trouver les hyperparamètres Dirichlet a priori dépendants des sujets qui sont utilisés pour générer le mot $w_n$ prédit.

## 2.5.2 Modèle de langage basé sur les réseaux de neurones

Finalement, aucune thèse contemporaine portant sur la modélisation du langage ne pourrait exister sans, au moins, mentionner les avancées récentes, principalement à partir de 2003 [55] et plus récemment [18], [56]–[62] dans les modèles de langage basés sur les réseaux de neurones récurrents (RNR). Un de leurs principaux avantages est leur capacité de regroupement sémantique automatique des mots, de la réduction de la dimensionnalité<fnref n="24" /> et de leur capacité à la généralisation. Par ailleurs, un de leurs avantages distincts par rapport aux N-grammes conventionnels est la

<footnote n="24">²⁴ Un antidote, en quelque sorte, contre le fléau de la dimensionnalité (« *curse of dimensionality* ») telle que décrite par Richard E. Bellman dans [63], [64]</footnote>
capacité des RNR à tenir compte des dépendances lointaines et donc de contourner les limitations
inhérentes à l'hypothèse de Markov propre aux N-grammes : nous ne sommes plus limités aux
N - 1 derniers mots. Cela est particulièrement vrai pour les RNR implémentant une longue
mémoire à court terme « Long Short Term Memory » (LSTM) originalement proposé par
Hochreiter et Schmidhuber [65] et ensuite amélioré par Gers dans [66] où il propose un mécanisme
de commande synaptique permettant aux neurones d'oublier l'information considérée comme
désuète. Sa première implémentation connue dans le domaine de la modélisation du langage fut
proposée par Sundermeyer et al. dans [67] et appliqué et étendu dans un contexte de modélisation
du langage de grande échelle dans [62] par Jozefowicz et al, Merity et al. [68] en régularisant et
optimisant d'énormes modèles ou encore Shazeer et al. qui ajoutent une mixture d'experts
(Mixture-of-Experts) entre chaque couche LSTM [69] afin de réduire encore plus la perplexité de
leurs modèles de langage.

Une façon simple de représenter un modèle de langage par RNR LSTM est illustrée à la Figure 2.5.
Chaque mot du vocabulaire est encodé dans un vecteur $\mathbf{w}(n)$ selon un codage 1-de-$V$, où $V$ est le
nombre de mots dans le vocabulaire (essentiellement un vecteur binaire où seul l'index du mot $w_v$
est égal à 1). Les vecteurs $\mathbf{s}(\cdot)$ représentent l'état actuel et passé du réseau. À la sortie, $\mathbf{y}(n)$, on
emploie une fonction d'activation « softmax » (fonction exponentielle normalisée : une
normalisation des fonctions logistiques) afin de s'assurer d'avoir de vraies probabilités. On
entrainera le réseau à l'aide d'algorithmes de rétropropagation du gradient pour finalement obtenir
une sortie telle que :

$$
\mathbf{y}(n) \rightarrow P(w_{n+1} | w_n, \mathbf{s}(n-1)). \tag{2.52}
$$

et où

$$
s_j(n) = f \left( \sum_i x_i(n) u_{ji} \right) \tag{2.53}
$$

$$
y_k(n) = g \left( \sum_j s_j(n) v_{kj} \right) \tag{2.54}
$$

où $f(z)$ est la fonction d'activation (de neurone) sigmoïde :
<figure><img src="image_10.png" /><figcaption>Figure 2.5 : Architecture d'un ML basé sur les réseaux de neurones récurrents avec LSTM.</figcaption></figure>

$$f(z) = \frac{1}{1 + e^{-z}} \qquad (2.55)$$

et $g(z)$ est la fonction softmax (fonction exponentielle normalisée) :

$$g(z_w) = \frac{e^{z_w}}{\sum_k e^{z_k}} \text{. pour tout } w \in \{1, \dots, K\} \qquad (2.56)$$

où $\sum g(z_w) = 1$

Afin de réduire la complexité de calcul d'un très grand vocabulaire, il est possible d'emprunter l'intuition des modèles basés sur les classes (disjointes) afin de prédire $P(w_n|w_1^{n-1})$ :

$$P(w_n|w_1^{n-1}) \approx P(w_n|w_1^{n-1}, c(w_n)) \times P(c(w_n)|w_1^{n-1}) \qquad (2.57)$$

La tendance actuelle en termes de classification à l'aide des réseaux de neurones se concentre principalement à l'application du « Deep Learning », ou apprentissage profond, popularisé par Krizhevsky et al. dans [70] et qui consiste tout simplement en un réseau de neurones avec une hiérarchie de plusieurs couches cachées (réseau de neurones profond (RNP)). Chaque couche du réseau sert essentiellement à détecter des motifs de plus en plus complexes et est ce qui en fait leur force principale.
Notons d'ailleurs que bien que tout réseau de neurones à multiples couches cachées puisse être représenté par un réseau de neurones équivalent à une couche cachée, Montúfar et Morton [71] démontrent comment la profondeur permet à un RNP de représenter une machine Boltzmann restreinte ayant un nombre de paramètres exponentiellement plus grand que le nombre de paramètres requis par le RNP. Montúfar et al. [72] proposent que chaque couche divise l'espace de paramètres en un nombre exponentiel d'ensembles, ce qu'un réseau à une seule couche cachée ne peut accomplir.

Un des problèmes pratiques de l'implémentation de l'apprentissage profond découle de la complexité de configuration des paramètres du modèle initial (l'architecture du modèle). Zoph et Le proposent ainsi une stratégie d'optimisation d'hyperparamètres, le *Neural Architecture Search* [73]. Ils basent leur travail sur l'observation que la structure et la connectivité d'un réseau de neurones peuvent être spécifiées par une chaîne de caractères de longueur variable. Zoph et Le proposent donc d'utiliser un RNR pour déterminer les paramètres initiaux optimaux de l'architecture (représenté par une chaîne de caractères) qui servira ensuite à générer un réseau neuronal enfant qui sera entrainé de façon conventionnelle. Leur expérimentation empirique démontre que cette stratégie permet d'automatiquement générer des architectures performantes ce qui devrait permettre aux chercheurs de plus rapidement évaluer différents modèles de réseaux de neurones en évitant de devoir passer énormément de temps à optimiser les paramètres initiaux de ceux-ci.

Bien que la majorité des modèles présentés jusqu'à présent dans le contexte de l'apprentissage profond reposent des réseaux de neurones récurrents, plus précisément sur les LSTM en traitement de la parole, Benes et al. [74] proposent un modèle basé sur un modèle de réseau de neurones à propagation avant (*feedforward network*), soit le *Residual Memory Networks* et où les couches sont réparties dans le temps avec des lien résiduel et des connexions à temporisation à toutes les *t* – 3 couches qui permettent au réseau de tenir compte de contextes temporels longs. Un de ses avantages est qu'il peut permettre une réduction substantielle de la taille des modèles comparativement à un réseau LSTM équivalent tout en maintenant une performance similaire sur une tâche de modélisation du langage basée sur le PennTreeBank [74].

Finalement, bien que les réseaux de neurones font maintenant partie intégrante d'une grande majorité de la recherche dans le domaine de la modélisation du langage, il ne faut toutefois pas
croire que les modèles statistiques, telles que les N-grammes, devraient être relégués aux
oubliettes. En effet, Jozefowickz et al. dans [62] soulignent l'importance des N-grammes dans les
modèles de langage de très grande taille :

> « Despite the fact that simpler models, such as N-grams, only use a short history of previous words to predict the next word, they are still a key component to high quality, low perplexity LMs. Indeed, most recent work on large scale LM has shown that RNNs are great in combination with N-grams, as they may have different strengths that complement N-gram models, but worse when considered in isolation »
> 
> (Jozefowicz et al. [62])

Nous noterons aussi la complexité de réplication des résultats inhérente aux modèles de langages basés sur les réseaux de neurones, tel que souligné par Henderson et al. dans [75], Islam et al. dans [76] ou encore Reimers et Gurevych dans [77].

## 2.6 Évaluation de la performance des modèles de langage

L'évaluation et, par le fait même, la comparaison des modèles de langage se font habituellement à l'aide de deux mesures principales<fnref n="25" />, soit la perplexité et le taux d'erreur des mots. La perplexité, étroitement liée à l'entropie, nous donne un indice sur la capacité d'un ML de prédire un (ou un ensemble de) corpus. Bien que cette mesure est généralement corrélée à une amélioration de la reconnaissance automatique de la parole, cela n'est pas toujours le cas [78], mais demeure tout de même utile. C'est pourquoi, pour les applications spécifiques à la RAP, nous évaluons les modèles de langage par rapport au taux d'erreur des mots. Les sous-sections ci-dessous introduisent ces concepts importants un peu plus en détail.

### 2.6.1 Perplexité

L'évaluation **extrinsèque** des modèles de langage est généralement un exercice assez long. Nous devons, par exemple, effectuer une évaluation complète (de bout en bout) de la RAP sur un ou plusieurs corpus de test donné pour pouvoir comparer des modèles entre eux. Celui qui obtiendra le plus faible taux d'erreurs des mots sera généralement considéré comme étant le meilleur dans

<footnote n="25">²⁵ Loin d'être idéales [21], mais qui nous donnent tout de même un bon aperçu du pouvoir prédictif des modèles de langage.</footnote>
la pratique. Par contre, cela est généralement assez long, pouvant prendre de plusieurs heures à plusieurs jours dépendamment de la rigueur et de la complexité du test.

C'est pourquoi nous allons généralement débuter par une évaluation **intrinsèque** de nos modèles de langage. La **perplexité** est le moyen le plus souvent utilisé pour l'évaluation rapide des modèles de langage. La perplexité, une mesure basée sur l'entropie croisée, nous permet de mesurer la capacité du modèle de langage à prédire un corpus de test donné (généré à l'aide d'une distribution de référence *p* inconnue). Par ailleurs, plus sa capacité de prédiction est bonne (une haute probabilité sera attribuée), plus le modèle de langage est considéré comme bon. Par ailleurs, la perplexité est souvent utilisée comme fonction objective lors de l'optimisation des modèles de langage.

Formellement, la perplexité, $PP(T)$, d'un modèle de langage sur un ensemble de test est une fonction de la probabilité que le modèle de langage va attribuer à l'ensemble de test. Pour un ensemble de test $T = w_1, w_2, ..., w_N$ d'une longueur $N$ :

$$PP(T) = \sqrt[N]{\prod_{i=1}^{N} \frac{1}{P(w_i|w_1, ..., w_{i-1})}} \quad (2.58)$$

Puisque nous utilisons des N-grammes, cela peut se généraliser à

$$PP(T) = \sqrt[N]{\prod_{i=1}^{N} \frac{1}{P(w_i|h)}} \quad (2.59)$$

Une propriété intéressante de la perplexité est qu'en prenant son logarithme nous obtenons l'entropie<fnref n="26" /> du modèle de langage, propriété familière à tout praticien de la théorie de l'information. La réduction de l'entropie était d'ailleurs l'objectif initial du lissage Witten-Bell qui était destiné à la compression de texte.

## 2.6.2 Taux d'erreur des mots (Word Error Rate)

Le taux d'erreur des mots (TEM), ou « Word Error Rate (WER) », en anglais, est généralement reconnu comme étant la mesure principale de la performance de la reconnaissance automatique de

<footnote n="26">²⁶ Quantité moyenne d'information par symbole. Un symbole peut être un mot, une lettre, etc. Le logarithme à la base 2 est habituellement choisi puisque celui-ci **nous donne le nombre moyen de bits/symbole**, ce qui est très utile dans tout processus de télécommunication en général.</footnote>
la parole. Le TEM relève de l'application de la distance de Levenshtein au niveau des mots plutôt que des phonèmes : un outil nous permettant de mesurer la similarité entre deux chaînes de caractères. Pour ce faire nous tentons d'aligner les deux chaînes et nous calculons le nombre minimal de caractères (ou mots dans notre cas) qu'il faut supprimer, insérer ou remplacer pour passer d'une chaîne (l'hypothèse de reconnaissance) à l'autre (le texte de référence). Par ailleurs, contrairement à la distance de Levenshtein où nous sommons simplement les erreurs, le WER comptera le nombre de suppressions, de substitutions et d'insertions tel que :

$$ TEM = \frac{(S + O + I)}{N}, \qquad (2.60) $$

où N est le nombre de mots dans la phrase de référence ;

S est le nombre de substitutions (mots incorrectement reconnus) par rapport à la phrase de référence ;

O est le nombre de suppressions (mots omis) par rapport à la phrase de référence ;

I est le nombre d'insertions (mots ajoutés) à la phrase de référence.

Parfois (peut-être pour sonner un peu plus positif), on rapporte plutôt le taux de reconnaissance des mots « Word Recognition Rate » (WRR) :

$$ WRR = \frac{N - (S + O + I)}{N} \qquad (2.61) $$

La majeure partie de la recherche effectuée dans le domaine du traitement du signal et de la modélisation du langage vise donc en fin de compte à réduire le taux d'erreur. Cependant, on peut arguer que ce n'est pas nécessairement la meilleure mesure de performance réelle [79], en particulier dans un contexte de compréhension de la parole.
<figure><img src="image_11.png" /></figure>
# 3 LISSAGE DES N-GRAMMES BASÉ SUR LES ONTOLOGIES

## 3.1 Mise en contexte

Nos travaux de thèse ont tout d'abord débuté dans le but d'être en mesure de concevoir rapidement des interfaces basées sur le dialogue pour la gestion d'inventaire assistée par des réseaux d'identification par radiofréquence (RFID), en particulier dans des environnements bruyants. Les avantages d'un tel système, basé sur le dialogue, complètement mains libres et combiné à la technologie RFID, promet d'améliorer la rapidité, l'ergonomie ainsi que la sécurité de plusieurs opérations telles que la prise de commandes, la gestion de la qualité, le suivi et la surveillance des actifs, les opérations d'expédition, et autres opérations découlant. Notre objectif premier était de proposer à une compagnie locale un système complet de suivi d'inventaire qui mettrait à l'avant-plan notre expertise dans le domaine.

Le système qui a résulté de cette première étape de nos travaux permet à l'utilisateur travaillant dans un environnement très bruyant d'interagir par la parole avec un réseau d'identification RFID. Un nouveau cadre de dialogue fut proposé dans [80] afin de donner aux opérateurs humains la capacité de communiquer avec le système d'une façon plus naturelle. Tel que nous l'avons mentionné dans l'introduction, un des problèmes les plus courants attribués aux interfaces opérant sur le modèle de « commande et contrôle » est leur manque de flexibilité par rapport aux énoncés reconnaissables. Afin de rendre notre système plus flexible, nous avons choisi d'implémenter un gestionnaire de dialogue basé sur le langage AIML (Artificial Intelligence Markup Language) qui a été conçu pour le développement d'agents conversationnels (visant le clavardage). Ce langage permet au système de répondre à des requêtes formulées en langage naturel par l'intermédiaire de détection de motifs (pattern matching). Cela a aussi comme avantage de rendre le système beaucoup plus robuste par rapport aux erreurs de reconnaissance automatique de la parole (les erreurs sur les mots sans importance sont ignorées), ce qui est particulièrement problématique dans des environnements très bruyants. De plus, afin de faire face à des environnements très bruyants et changeants, une technique en ligne d'amélioration du sous-espace vectoriel du signal basé sur
la variance de l'erreur de reconstruction de Karhunen-Loève Transform (ERV-KLT), basée sur les travaux de [81], [82], est proposé par notre collègue. Nous avons démontré dans [80] le caractère naturel du dialogue et sa robustesse face aux erreurs de reconnaissance automatique de la parole, ainsi que l'efficacité de l'amélioration du signal d'un point de vue perceptuel. Cependant, il demeure qu'un des désavantages principaux que nous avons rencontrés avec le langage AIML est la nécessité de créer des motifs pour toutes les variations d'une commande possible. Par exemple, un des problèmes rencontrés est qu'une simple requête de recherche d'inventaire nécessite une multitude de motifs pour couvrir tous les lemmes, les conjugaisons et toutes autres variations possibles. Ce travail de conception requiert beaucoup de temps et est sujet aux oublis et à l'erreur humaine.

### 3.1.1 Générateur de motif et analyseur sémantique pour systèmes de dialogue verbaux

C'est avec l'idée de faciliter la conception de vocabulaire que nous avons proposé une amélioration au gestionnaire de dialogue dans [83]. La solution proposée vise à faciliter la conception de grammaire/motifs types de domaine via la mise en œuvre d'un générateur de motif basé sur les ontologies. Ce nouveau cadre de dialogue est proposé afin de donner aux opérateurs humains une plus grande flexibilité de communication avec le système qui sera dorénavant en mesure de tenir compte des variations possibles des commandes types. Avec ce nouveau cadre, le concepteur n'a qu'à spécifier un motif par action ou requête possible et le système va automatiquement générer le plus de variations possible en se basant sur les relations ontologiques de ses termes principaux.

Nous avons choisi de nous orienter vers les ontologies du fait de leur capacité de relier des concepts de façon à la fois relationnelle et hiérarchique et en nous inspirant, entre autres, des travaux d'Estival et al. [84]. L'algorithme génératif est quant à lui inspiré des travaux de Kauchak et al. [85] sur la paraphrase dans le contexte de l'évaluation automatique des résultats de traduction automatique du langage.

Nos résultats [83] démontrent que le système est en mesure de générer de nouveaux motifs à partir des motifs de base tout en minimisant l'impact au niveau de la perplexité du modèle de langage généré. De plus, ces mêmes motifs permettent une plus grande flexibilité d'élocution de la part des utilisateurs dans la mesure où ils n'ont pas à retenir un vocabulaire fixe, mais ont simplement besoin de comprendre ce qu'ils veulent faire.
Cependant, un problème persiste. Si les modèles de langage ne sont pas en mesure de tenir compte de ces nouvelles variations, le système ne sera pas capable de les reconnaître. Nous avons donc focalisé notre attention vers les modèles de langage qui permettent justement la reconnaissance de telles phrases nouvelles.

## 3.2 Lissage ontologique

Dans cette section nous résumons notre contribution principale, soit une méthode originale de lissage de modèles de langage visant à améliorer la performance des N-grammes. Un des problèmes avec les techniques actuelles est qu’elles ne se généralisent pas nécessairement aux mots se trouvant dans la même classe/sous-classe sémantique, surtout s’ils n’ont jamais été vus. Prenons l’exemple suivant traduit (traduction libre) de la chanson enfantine « Mary had a little lamb » :

> Marie avait un petit agneau.

Les comptes des mots tels que chaton, chiot, souris, etc. sont tous des animaux et il serait raisonnable de les lisser de façon proportionnelle au mot agneau, et ce, même s’ils n’ont jamais été vus (il en va de même pour le verbe avoir et l’adjectif petit, voir même le prénom). En effet, les phrases :

* Marie voudrait un petit chaton.

* Marie a un grand chien.

* Jean avait une petite souris.

sont toutes des phrases sémantiquement similaires et valides en français. Alors, comment-fait-on pour modéliser convenablement ces phrases si nous ne les avons jamais vues ? Bien que la modélisation basée sur les classes pourrait potentiellement nous aider, qu’advient-il si nous n’avons jamais rencontré ces mots en particulier ? C’est pour répondre à cette question que nous avons proposé dans [86], et amélioré dans [87], une méthode de lissage qui tient compte de ces relations en mettant à profit l’information latente inhérente aux ontologies.
### 3.2.1 Les ontologies

L'ontologie est « ... l'étude de l'être en tant qu'être... » (Aristote [21]). De ce fait, les ontologies sont utilisées pour structurer les termes et les concepts propres à un (ou plusieurs) domaine de connaissance de façon hiérarchique et relationnelle afin d'ultimement décrire leur sens et ainsi nous permettre de raisonner à propos de ces objets. Les entités logiques et philosophiques peuvent elles-mêmes être regroupées de façon contextuelle à l'aide d'opérateurs relationnels (relations sémantiques, relations de subsomption) nommés, p. ex. : Terme:chat Relation:manger Terme:souris. La figure suivante (Figure 3.1) montre une partie de l'ontologie WordNet par rapport au mot « cat » (chat en anglais) pour une distance (chemin le plus court) de 1 et où les relations sont celles de synonymie.

<figure><img src="image_12.png" /><figcaption>Figure 3.1 : Échantillon de l'ontologie complète ayant comme nœud central le terme chat. La taille des nœuds représente leur degré de connectivité et leur couleur leur catégorie grammaticale : adjectifs (noir), adverbes (non représentés, blanc), noms (gris clair) et des verbes (gris). Les couleurs des arêtes représentent le type de relation entre les nœuds. On notera que la longueur des lignes n'a aucune signification autre que l'amélioration de la clarté de l'illustration.</figcaption></figure>

Source : Y. Benahmed, S.-A. Selouani, et D. O'Shaughnessy, « A Bin-Based Ontological Framework for Low-Resource N-Gram Smoothing in Language Modelling », dans Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference on, 2014, p. 4918-4922.
Puisque les ontologies (informatiques) contiennent une quantité importante d’information et qu’on
peut en résumer le rôle comme « [les] ontologies sont aux données ce que la grammaire est au
langage » [22]. Il devient apparent que les ontologies devraient être en mesure de nous permettre
d’aider nos modèles de langage à mieux prendre en compte les relations entre les mots et nous
donner des modèles qui reflètent notre compréhension du langage.

L'objectif principal est donc d'exploiter ces ontologies pour introduire une notion de savoir dans
les modèles de langage, c'est-à-dire, d'être en mesure d'attribuer des probabilités plus élevées à
des N-grammes inédits, mais qui sont sémantiquement liées à des N-grammes vus ou qui
fonctionnent de façon similaire. En d'autres mots nous tenterons à la fois de paraphraser<fnref n="27" /> les
N-grammes déjà vus et de générer des N-grammes décrivant des sujets similaires. Nous désirons
ainsi à la fois réduire la perplexité des modèles de langage et augmenter la performance de la
reconnaissance de la parole grâce à nos algorithmes de lissages ontologiques.

De cette façon, en analysant l'information contenue à l'intérieur de celle-ci, nous serons en mesure
de lisser nos modèles de langage en lissant ses probabilités avec celles des termes connexes, c'est-
à-dire utiliser les comptes des N-grammes apparentés $C(w_r|h)$ pour chaque mot $w_r \in W_R$
apparenté à $w_n$ et son contexte $h$ et où $W_R$ est un vecteur de $R$ mots apparentés à $w_n$. Inversement,
pour lisser les N-grammes jamais vus, nous pouvons utiliser le compte $C(w_n|h)$ des N-grammes
connus pour générer des comptes lissés $C(w_r|h)$ sémantiquement plausibles.

Nous pensons que cette hypothèse est raisonnable, surtout pour les dialogues parlés où les
locuteurs peuvent échanger des mots pour des termes connexes qui leur viennent à l'esprit plus
rapidement. En outre, étant donné que ce travail vise à aider à réduire la dispersion des données
qui sont utilisées pour le lissage, nous proposons la technique suivante basée sur l'interpolation
pour lisser les modèles de langage à faibles ressources en ajoutant intelligemment des informations
latentes. En d'autres mots, nous cherchons à remplir, de façon intelligente, une matrice creuse.

L'ontologie WordNet

Pour ce travail, nous avons utilisé l'ontologie WordNet [88]. Il s'agit essentiellement d'une grande
base de données lexicale de la langue anglaise et où l'unité principale est le sens des mots

<footnote n="27">27 paraphrase (n.f.) (grec *paraphrasis*) : Formulation différente d'un énoncé sans altération de son contenu [23].</footnote>
représenté par des synsets (synonymes cognitifs). Nous avons utilisé la forme relationnelle où les relations principales caractérisent la synonymie (l'état d'être un synonyme). Chaque lemme est classifié selon sa catégorie grammaticale et compte : 21 479 adjectifs, 4 481 adverbes, 117 798 noms et 11 529 verbes pour un total de 155 287 sens uniques. Nous avons choisi cette ontologie en particulier, car plusieurs librairies existaient déjà pour la traiter [89], [90] en plus d'être bien documentée et utilisée dans plusieurs travaux de recherche.

### 3.2.2 Bin-Based Ontological Smoothing

Le lissage consiste à créer $B_d$ bacs de comptes lissés qui tiennent compte de tous les mots reliés $w_r^d$ trouvés à une distance $d$, le chemin le plus court (nombre d'arcs à parcourir), de l'ontologie à partir du mot original $w_n$ et où $d = 1, 2, ..., d_{max}$ où $d_{max}$ est la distance maximale de $w_n$ qui sera considérée. Par exemple, dans la Figure 3.1 la distance $d(cat,tiger) = 1$, $d(feline,cattish) = 2$, etc. Plus formellement, pour chaque $C(w_n|w_{n-N+1}^{n-1}) \in B_d$:

$$C'(w_n|w_{n-N+1}^{n-1}) = \frac{1}{R} \sum_{d=1}^{d_{max}} \sum_{r=1}^{R_d} \frac{C(w_r|w_{n-N+1}^{n-1})}{d} \quad (3.1)$$

où R est le nombre total de mots qui ont une relation avec $w_n$ jusqu'à une distance $d_{max}$. De cette façon, R est le nombre total de mots reliés à chaque mot $w_n$ et $R_d \le R = \sum_{d=1}^{d_{max}} R_d$ est le nombre de mots connexes qui sont à une distance $d$. Le principe derrière l'utilisation du chemin le plus court en tant que mesure de la distance conceptuelle et sémantique est justifié dans [91], soit « ...when is-a hierarchies are defined ... shortest path length can be used to measure conceptual distance between concepts » qui peut se traduire comme « lorsque des hiérarchies “est-un” sont définies, le chemin le plus court peut être utilisé pour mesurer la distance conceptuelle entre deux concepts ».

Les relations que nous considérons sont celles de synonymie, d'hyperonymie et d'hyponymie. Le Larousse définit ces termes comme suit :

* Synonymie : « Relation qu'entretiennent entre eux divers termes ou expressions ayant le même sens ou un sens voisin ».

* Hyperonymie : « Rapport d'inclusion entre des unités lexicales, considéré comme orienté du plus général au plus spécifique. (C'est l'inverse de l'hyponymie.) [Chien est dans un
rapport d'hyperonymie avec basset, caniche, etc.] ».

Indicatif d'une **descente vers une feuille** dans la hiérarchie de l'ontologie.

* Hyponymie : « Rapport d'inclusion entre des unités lexicales, considéré comme orienté du plus spécifique au plus général. (C'est l'inverse de l'hyperonymie.) [Chien est dans un rapport d'hyponymie avec carnivore, animal, etc.] ».

Indicatif d'une **remontée vers la racine** dans la hiérarchie de l'ontologie.

Les comptes générés ontologiquement sont ensuite utilisés pour générer des modèles de langage $LM_{B_d}$ pour chaque bac. Enfin, ces modèles de langage sont interpolés avec le modèle de langue principal lissé à l'aide de l'algorithme de Witten-Bell afin d'obtenir un modèle final :

$$P'(w_n|w_{n-N+1}^{n-1}) = \lambda_1 P(w_n|w_{n-N+1}^{n-1}) + \sum_{d=1}^{d_{max}} \lambda_{d+1} P_{B_d}(w_n|w_{n-N+1}^{n-1}) \quad (3.2)$$

où $d_{max}$ est la distance maximale des arêtes considérées ;

$P_{B_d}(w_n|w_{n-N+1}^{n-1})$ sont les probabilités obtenues à partir des comptes lissés de chaque bac ;

$\lambda$ sont les poids de mixture, avec $\sum_{i=1}^D \lambda_i = 1$ pour s'assurer que le tout somme à 1 et peuvent être obtenus grâce à n'importe quel algorithme d'optimisation linéaire. La raison principale qui nous a amené à utiliser le lissage Witten-Bell, plutôt que le lissage Kneser-Ney, vient premièrement de son lissage basé sur la diversité des contextes et deuxièmement, de façon plus pragmatique, nous l'avons choisi, car nous ne sommes pas au courant de l'existence d'une version **continue** de l'algorithme de lissage Kneser-Ney, ce qui le rend incompatible avec les comptes fractionnels générés par notre algorithme de lissage.

## 3.3 Méthodologie expérimentale

La méthodologie expérimentale générale que nous avons utilisée pour l'évaluation de notre algorithme de lissage novateur peut se décrire comme suit. L'ensemble des expérimentations effectuées dans cette thèse ont été réalisées à l'aide du corpus WSJ1 [92] (Continuous Speech Recognition Phase II) basé sur le Wall Street Journal. Nous formons nos modèles de langage de
base sur les 76 136 phrases fournies par l'ensemble de formation du corpus WSJ1 pour un total de
1 243 340 mots.

L'ensemble de développement/validation, comportant 4 340 phrases et un total de 71 759 mots, est utilisé pour l'optimisation des paramètres pertinents. Nous nous en servons donc pour optimiser les poids d'interpolation globaux, définis par l'équation 3.2, en utilisant soit la perplexité, soit le taux d'erreur des mots, comme fonction objective à minimiser. Dans cette section, nous optimisons nos poids d'interpolation grâce à l'algorithme d'optimisation de Powell [93] tiré de la bibliothèque SciPy [111] avec comme fonction objective le taux d'erreur des mots.

Les boîtes à outils SRILM [93] et HTK [112] ont été utilisées pour nos expériences de modélisation du langage et de reconnaissance automatique de la parole, respectivement. Nous obtenons tout d'abord les comptes bruts pour nos modèles à l'aide de la boîte à outils SRILM. Ces comptes bruts sont ensuite utilisés pour générer des bacs de comptes lissés ontologiquement pour chaque groupe de distance ontologique. Le vocabulaire des comptes lissés n'étant pas restreint, de nouveaux mots pourront s'introduire aux bacs de comptes lissés, ceux-ci seront par la suite filtrés lors de la création des modèles de langage finaux (options « -vocab [dictionnaire] -limit-vocab » du programme ngram de la suite SRILM). Notons que, conformément à l'équation (7.2), la majorité des comptes sont des comptes fractionnaires. Ensuite, des ML Witten-Bell sont créés pour chaque bac. Enfin, un modèle de langage mixte est créé en mélangeant chaque ML à base de bacs avec le LM Witten-Bell original. Malheureusement, la trousse d'outils SRILM ne prend pas en charge les comptes fractionnaires pour le lissage de Kneser-Ney (continuous Kneser Ney counts) et, par conséquent, nous ne pouvons pas interpoler correctement le modèle de base de KN avec nos bacs.

3.3.1 Résultats expérimentaux

Comme première évaluation de notre méthode de lissage ontologique, nous avons utilisé les ensembles d'évaluation/test Hub 1 (lecture de base du WSJ) et Spoke 1 (adaptation des modèles de langage) (10 347 mots dans 582 phrases) du corpus WSJ1 sans filtrer les phrases avec des mots hors vocabulaire. Le dictionnaire fermé WSJ de 20 k mots est utilisé pour un taux total de mots hors vocabulaire (MHV) de 5,41 %.

Nos résultats expérimentaux [86] démontrent qu'il est possible d'obtenir, d'une part, une réduction significative de la perplexité du modèle (jusqu'à 9,85 % par rapport au modèle de base) et, d'autre part, de réduire le taux d'erreur de mots d'une manière statistiquement significative par rapport à
la fois au modèle original lissé à l'aide de l'algorithme de Witten-Bell et d'un autre modèle de langue de base lissé à l'aide de l'algorithme de Kneser-Ney entrainé sur le corpus « Wall Street Journal-Based Continuous Speech Recognition Phase II » [92].

Nous sommes d'avis que ces résultats intéressants permettent de poser les bases théoriques pour que d'autres chercheurs puissent appliquer cette technique de lissage ontologiques pour les langues où les ressources textuelles propres à la modélisation du langage sont limitées.

Suite à ces résultats encourageants, nous nous sommes posé la question à savoir si la théorie des graphes, telle qu'appliquée dans le domaine de la théorie de l'information et des réseaux (sociaux), pouvait apporter de l'information supplémentaire à nos modèles. C'est pourquoi nous avons par la suite examiné l'apport des mesures tirées de la théorie des graphes à la généralisation de notre algorithme de lissage de modèle de langage. Plus spécifiquement, nous avons exploré l'effet des mesures HITS, PageRank, Modularité et degré pondéré sur la performance de la reconnaissance automatique de la parole, de même que par rapport à la perplexité des modèles de langage.

## 3.4 Théorie des réseaux

La théorie des graphes, ou, (philosophiquement) plus spécifiquement dans notre cas, l'étude des réseaux, est un outil qui nous permet de quantifier et de qualifier l'influence des nœuds et des arcs à l'intérieur d'un réseau. Ce champ d'études sert aussi à détecter des communautés qui demeureraient cachées autrement. Son utilité, autant dans les domaines de la biologie, de la sociologie, de l'économie, en dit long sur sa capacité de modélisation des relations. Ce sont ces propriétés qui nous intéressent dans ce travail.

Les types de mesures que nous avons choisis sont les mesures de centralité. Ces mesures soulignent l'importance des nœuds dans un graphe. Dans le contexte de la modélisation du langage, cela pourrait, par exemple, être l'importance d'un mot dans une ontologie, ou par rapport à un document (nombre d'occurrences pour un document *D*). Cette intuition est d'ailleurs à la base de multiples algorithmes en recherche de l'information et de classification des documents tels que le TF-IDF, HITS, PageRank, Modularité, etc.
Le choix des mesures HITS et PageRank et Modularité est motivé par leur simplicité, leur capacité de rapidement calculer l'importance relative des nœuds, que l'algorithme PageRank peut être considéré comme une modélisation d'un processus Markovien [94] et parce que les approximations de premier ordre de plusieurs algorithmes de classement donnent les mêmes résultats [95]. Le choix de la mesure de modularité est quant à elle dû à sa capacité de rapidement classer les nœuds en communautés. Finalement, le degré pondéré est utilisé comme référence de base.

### 3.4.1 Degré

Le degré et son dérivé, le degré pondéré, sont les mesures les plus simples de centralité d'un graphe. Ils comptent essentiellement le nombre d'arcs incidents, tel que défini par

$$ 
\begin{align*}
d_i^- &= \sum_j A(j, i) \\
d_i^+ &= \sum_j A(i, j) \tag{3.3} \\
d_i &= d_i^- + d_i^+
\end{align*}
$$

où $d_i^-$ est le degré entrant pondéré, le nombre d'arcs qui entrent vers le nœud $i$ si $A(j, i) = 1 \forall M(i, j)$,

$d_i^+$ est le degré sortant pondéré, le nombre d'arcs qui sortent du nœud $i$ si $A(i, j) = 1 \forall M(i, j)$,

$d_i$ est le degré pondéré,

$A(i, j)$ est le poids de l'arc entre les nœuds $i$ et $j$ et est égal à un (1) dans le cas du degré non pondéré.

Nous pouvons alors réécrire cette équation dans le contexte d'un réseau de mots en tant que

$$ d(w_i) = \sum_{w_j \in M(w_i)} A(w_i, w_j), \tag{3.4} $$

où $d(w_i)$ est le degré du mot $w_i$

$w_j \in M(w_i)$ est l'ensemble des mots $w_j$ qui sont liés à $w_i$

$A(w_i, w_j)$ est le poids de l'arc entre les mots $w_i$ et $w_j$.
Si l'on reprend l'ontologie vue à la Figure 3.1, nous pouvons par exemple calculer le degré du mot « cat » :

$$d(\text{cat}) = d^{-}(\text{cat}) + d^{+}(\text{cat}) = 57 \qquad (3.5)$$

Afin d'éviter les débordements arithmétiques, il n'est pas rare de normaliser les degrés sur une échelle de 0 à 1.

Deux autres mesures peuvent par ailleurs être utilisées soit le degré entrant $d^{-}$, et le degré sortant $d^{+}$ qui quantifient respectivement le poids des arcs vers le nœud $w_{i}$ et le poids des arcs hors du nœud $w_{i}$. Ces mesures sont d'ailleurs utilisées comme base pour d'autres mesures.

### 3.4.2 Hyperlink-Induced Topic Search

L'algorithme HITS (Hyperlink-Induced Topic Search) [96] a originalement été conçu pour évaluer l'autorité des pages Web en analysant leurs liens. Il retourne une liste de centralité de hubs et d'autorité pour chaque nœud dans le graphe. La relation entre hub et autorité est maintenue à l'aide d'un algorithme mutuellement récursif :

$$aut(w_i) = \sum_{w_j^- \in M(w_i)} hub(w_j, w_i), hub(w_i) = \sum_{w_j^+ \in M(w_i)} aut(w_i, w_j) \qquad (3.6)$$

où aut($w_i$) et hub($w_i$) sont les scores d'autorité et de hub du mot $w_i$ respectivement. L'algorithme procède de la sorte :

1. On assigne 1 comme valeur d'autorité et de hub pour chaque mot.

2. On met à jour la valeur autorité de chaque mot en sommant la valeur hub des mots $w_j^- \in M(w_i)$ qui pointent vers $w_i$ (liens entrants).

3. On met à jour la valeur hub de chaque mot en sommant la valeur autorité des mots $w_j^+ \in M(w_i)$ vers lesquels $w_i$ pointe (liens sortants).

4. On recommence jusqu'à la stabilisation du système :

$$|aut_n(w_i) - auth_{n-1}(w_i)| \le \epsilon \text{ et } |hub_n(w_i) - hub_{n-1}(w_i)| \le \epsilon.$$
Cet algorithme nous permettra donc de déterminer les nœuds d'importance dans le « graphe », en d'autres mots, une bonne *autorité* est pointée par plusieurs bons hubs, et qu'un bon hub pointe vers plusieurs bonnes autorités. Dans le cas des graphes non dirigés, les valeurs de hub et d'autorité sont égales. Le choix de l'une au l'autre revient donc à un choix personnel/philosophique. Notre raisonnement pour l'utilisation de cette mesure est basé sur l'intuition que les hubs représenteront des mots spécifiques, alors que les autorités représenteront des mots plus généraux.

### 3.4.3 PageRank

L'algorithme PageRank [97] est un algorithme itératif qui nous donne la probabilité qu'un utilisateur parcourant le Web se rende de façon aléatoire à n'importe quelle page donnée. Nous assumons que le mot $w_i$ a des mots $w_j \in M(w_i)$ qui pointent vers lui ; $M(w_i)$ est définis précédemment comme étant l'ensemble des mots liés par $w_i$. Le PageRank d'un mot $w_i$ est donc :

$$PR(w_i) = \frac{1 - \delta}{N} + \delta \left( \sum_{w_j \in M(w_i)} \frac{PR(w_j)}{L(w_j)} \right) \qquad (3.7)$$

Où $PR(w_i)$ est le PageRank du mot $w_i$, $L(w_j)$ est le nombre de mots liés par $w_j$. Le paramètre $\delta$ est un facteur d'amortissement qui prend une valeur entre 0 et 1 et est habituellement égal à $\delta = 0.85$.

Un des avantages de l'algorithme PageRank est qu'il peut aussi être appliqué aux graphes (notons que le WWW est en fait un graphe et que le bût de l'algorithme PageRank est essentiellement d'attribuer une cote d'importance relative à chacun des nœuds ($PR(x_s) \in \{S_1, S_2, ..., S_s\} \in \{WWW\}$). L'hypothèse de ce travail est qu'un faible indice PageRank suggère une faible probabilité de substitution d'un mot $w_i$ pour un mot $w_j$. Le PageRank sert donc essentiellement de facteur de pondération où $0 \le PR \le 1$ avec 0 indiquant aucune probabilité de substitution et 1 une « garantie » de substitution. En pratique, le PageRank est toujours inférieur à 1 puisqu'une garantie de substitution est fondamentalement illogique (le mot original ne serait jamais réutilisé).

La supposition de ce travail est qu'un faible PageRank suggère une faible probabilité de substitution du mot $w_i$ par le mot $w_j$, nous l'utiliserons donc comme un facteur de pondération sachant que $0 \le PR \le 1$.
### 3.4.4 Modularité

La modularité est utilisée pour découvrir et caractériser la structure des communautés dans un réseau. La qualité $-1 \le Q \le 1$ de ces communautés C est définie [7] par leur Modularité [98] telle que :

$$Q = \frac{1}{2m} \sum_{w_i, w_j} \left[ A(w_i, w_j) - \frac{d(w_i), d(w_j)}{2m} \right] \sigma(c(w_i), c(w_j)), \qquad (3.8)$$

où $A(w_i, w_j)$ le poids de l'arc entre les mots $w_i, w_j$,

$c(w)$ retourne la communauté à laquelle appartient le mot $w$,

$d(w)$ le degré (non pondéré) du mot $w$,

$m = \frac{1}{2} \sum_{w_i, w_j} A(w_i, w_j)$ est un facteur de normalisation du degré pondéré,

la fonction $\sigma(u, v)$ est égale à 1 si $u = v$ et 0 sinon (en d'autres mots, 1 s'ils font partie de la même communauté et 0 sinon).

L'intuition derrière le choix de cette mesure est basée sur l'agrégation par thème (topic clustering) où nous supposons que la transition d'une classe de modularité à une autre classe de modularité indique un changement de contexte. Pour ce travail, la modularité est donc utilisée comme un facteur de pénalisation lorsque les mots liés n'appartiennent pas à la même communauté. Nous nous en servons aussi pour découvrir des sujets inconnus ou des classes de lemmes à l'intérieur de l'ontologie et pénaliser les comptes des mots de différentes communautés dans l'équation (3.1). Nous avons choisi de définir le facteur de pénalité $\alpha$ tel que :

$$\alpha(w_n, w_r) = \begin{cases} 1 & \text{si } c(w_n) = c(w_r) \\ \frac{1}{e} & \text{sinon} \end{cases}. \qquad (3.9)$$

### 3.4.5 Méthodologie expérimentale

Tel que définie à la section 3.3, notre méthodologie expérimentale de base se base sur le corpus Wall Street Journal-based Continuous Speech Recognition Phase II et les boîtes à outils SRILM et HTK.
Tel que décrit à la section 3.3, nous avons utilisé la perplexité du modèle de langage sur l'ensemble de développement (~4,3 k mots) comme fonction objective pour optimiser les poids d'interpolation de nos modèles de langage (voir équation 3.2).

Nous avons par la suite évalué nos résultats sur les ensembles d'évaluation Hub 1 (lecture de base du WSJ), Spoke 1 (adaptation des modèles de langage), Spoke 2 (indépendance du domaine) et Spoke 9 (dictée spontanée du WSJ) pour un total de 23 k mots dans 1 285 sentences sans filtrage. Le dictionnaire fermé WSJ de 20 k mots est utilisé pour l'évaluation, donnant un taux total de MHV de 5,64 %.

### 3.4.6 Résultats expérimentaux

L'ensemble des parties d'un ensemble (*powerset*) des bacs a été évalué pour chaque mesure de réseau. Le *powerset* désigne l'ensemble de tous les sous-ensembles d'un ensemble $S$, incluant $S$ lui-même, ainsi que l'ensemble vide. Par exemple, admettons l'ensemble $S = \{x, y, z\}$, son ensemble des parties d'un ensemble, $\wp(S)$, sera [99] :

$$ \wp(S) = \{\{\}, \{x\}, \{y\}, \{z\}, \{x, y\}, \{x, z\}, \{y, z\}, \{x, y, z\}\} $$

Nos résultats [87] montrent que l'interpolation des bacs originaux à des distances $d = 1, 3$ et $5$ donne lieu à une amélioration du taux d'erreur des mots de 0,71 % par rapport à l'interpolation des bacs 1 à 5 tout en réduisant la taille des modèles. Finalement, nous avons trouvé que la modularité, le PageRank et l'HITS sont prometteurs et méritent une étude plus approfondie dans le futur. Par ailleurs, les relations d'antonymie mériteraient aussi d'être explorées dans le futur dans un contexte de paraphrase puisque les expressions de négation ou antonymiques sont tout aussi sémantiquement plausibles, par exemple :

* Jean a un chat

* Jean *n'a pas* de chat

* Marie aime les moutons

* Marie déteste les moutons

Comme nos travaux dans [87] ont démontré qu'il pouvait exister des combinaisons irrégulières des bacs de distances, nous avons décidé de pousser notre analyse plus en profondeur jusqu'aux bacs d'une distance de 7.
Finalement, nous avons observé que les algorithmes évolutionnaires nous offrent la possibilité d'explorer de vastes espaces de recherche de façon moins « séquentielle » que les algorithmes d'optimisation classiques. Ces algorithmes stochastiques devraient nous permettre d'élargir l'espace de recherche pour pouvoir ensuite éliminer les bacs ainsi que les ordres qui ne contribuent pas beaucoup au modèle et donc de faire ressortir les paramètres les plus importants de nos modèles de langage. Par ailleurs, puisque ces problèmes d'optimisation sont complexes en raison du grand nombre de paramètres, le choix des algorithmes évolutionnaires nous semble particulièrement pertinent. Dans ce contexte, nous en profiterons pour comparer la performance de différents algorithmes d'optimisation dans le but de trouver les meilleurs poids d'interpolation des modèles de langage.
<figure><img src="image_13.png" /></figure>
# 4 OPTIMISATION DE LA MODÉLISATION DU LANGAGE PAR LES ALGORITHMES ÉVOLUTIONNAIRES

## 4.1 Introduction

Les algorithmes évolutionnaires (AE) ont une longue histoire dans le domaine de l'optimisation. Ces algorithmes permettent, par le biais de la simulation de processus évolutionnaires biologiques (stochastiques), de couvrir une grande partie de l'espace de recherche, pour autant qu'ils soient bien adaptés au problème à l'étude (ce qui est d'ailleurs une des faiblesses souvent décriées de l'optimisation par algorithmes évolutionnaires), de façon à trouver rapidement une solution globalement satisfaisante. Un avantage considérable est qu'ils ont généralement moins tendance à tomber dans le piège d'une solution locale, contrairement à plusieurs méthodes d'optimisation classiques. Cela est principalement dû au fait que la plupart de ces algorithmes intègrent un principe de mutation qui leur permet de découvrir des solutions globalement satisfaisantes.

Des centaines d'algorithmes évolutionnaires ont été utilisés avec succès pour optimiser une grande variété de problèmes au courant des dernières décennies.

Pour ce qui est du domaine de la parole, ils ont été utilisés avec succès pour le rehaussement de la parole, la reconnaissance de locuteurs, l'adaptation au locuteur, la reconnaissance automatique de la parole, et le traitement du langage [100]. Par contre, outre leur utilisation pour l'optimisation des réseaux de neurones (modèles de langage basés sur les réseaux de neurones), les AE n'ont pas, à notre connaissance, été utilisés de façon notable dans l'optimisation des modèles de langage.

Nous proposons donc d'évaluer la capacité des AE à trouver des solutions optimales pour l'interpolation de nos modèles de langage et de les comparer aux algorithmes classiques principalement utilisés dans le domaine : la méthode de Powell [101] et l'optimisation par l'algorithme espérance-maximisation.
Nous désirions aussi évaluer les algorithmes évolutionnaires pour déterminer leur capacité de dynamiquement minimiser la taille de nos modèles de langage en réduisant le nombre de bacs à interpoler avec le modèle de langage principal. Nous avons montré dans [87] qu'il est possible de réduire le nombre de bacs tout en préservant des performances optimales.

Contrairement aux algorithmes conventionnels, nous croyons qu'il est possible pour les algorithmes évolutionnaires de réaliser cette opération en une seule exécution, due à leurs propriétés stochastiques, contrairement aux algorithmes conventionnels qui requièrent l'exploration complète de l'ensemble des parties d'un ensemble<fnref n="28" /> possibles.

Dans ce travail, nous nous intéresserons principalement aux algorithmes évolutionnaires bioinspirés que l'on retrouve dans deux grandes catégories<fnref n="29" /> :

1. Les algorithmes génétiques, qui tentent d'adapter une solution à un espace de recherche en simulant les processus (darwiniens) évolutifs d'une espèce : croisement des gènes, mutations, survie du plus apte.

2. Les algorithmes collaboratifs, qui simulent les stratégies de survie de groupes d'individus : le mouvement d'un banc de poissons pour se nourrir ou minimiser la prédation, le mouvement d'une nuée d'oiseau dans une volée mixte d'alimentation, le comportement d'une colonie de fourmis à la recherche de nourriture (principe du superorganisme), etc.

Plus précisément, nous avons principalement examiné un algorithme génétique et un algorithme basé sur les colonies, soit l'optimisation par essais particuliers (OEP).

Les sections 4.2 et 4.3 présentent, respectivement, une introduction aux algorithmes génétiques et à l'optimisation par essais particuliers.

<footnote n="28">28 Pour l'ensemble $E = \{x, y, z\}$, l'ensemble des parties d'un ensemble, $P(E)$, ou, le Power Set en anglais, est $P(E) = \{\{\}, \{x\}, \{y\}, \{z\}, \{x, y\}, \{x, z\}, \{y, z\}, \{x, y, z\}\}$.</footnote>

<footnote n="29">29 Nous retrouvons aussi maintenant de plus en plus d'algorithmes inspirés par divers phénomènes physiques, tels que l'optimisation par (champ de) force centrale (Central Force Optimization, CFO) [102], [103] et, plus récemment, l'algorithme gravitationnel de recherche (Gravitational Search Algorithm, GSA) [104], [105]. Le premier est un algorithme déterministe de recherche multidimensionnel, simulant une sonde interstellaire qui parcourt l'espace de recherche sous l'influence de la gravité. Le second simule un ensemble de masses (solutions potentielles) qui interagissent entre elles selon les lois newtoniennes de la gravité et du mouvement.</footnote>
Dans la section 4.4, nous évaluons les différents algorithmes d'optimisation et comparons leur performance face à la méthode de Powell qui est couramment utilisée pour optimiser les modèles de langage [36], [78], [106].

Finalement, la section 4.5 conclut notre travail et propose des directions pour des travaux futurs.

## 4.2 Algorithmes génétiques

Les algorithmes génétiques (AG), Genetic Algorithms en anglais, sont probablement les algorithmes évolutionnaires les plus connus. En s'inspirant de la théorie de l'évolution, les AG reproduisent la **sélection naturelle** où les meilleurs individus (qui **survivent**) d'une espèce vont se **reproduire** dans le but de rendre l'espèce plus forte, et, du même coup, profiter des **mutations** aléatoires inhérentes à la biologie qui ont permis à la vie **d'évoluer et de s'adapter** à différents écosystèmes.

### 4.2.1 Individus

À la base de tout algorithme évolutionnaire repose le concept d'individu. L'individu représente un membre de l'espèce que l'on veut faire évoluer. Plus concrètement, dans le domaine de l'optimisation, les individus représentent une solution possible au problème. Ils sont généralement représentés par leur gène qui consiste en un vecteur de paramètres à « optimiser » et où chaque élément du vecteur constitue un allèle.

### 4.2.2 Génération

Chaque génération comporte un nombre plus ou moins élevé d'individus. On appelle la première génération la génération initiale. Plusieurs méthodes d'initialisation de la génération initiale existent et nous en choisissons une en fonction de nos connaissances du problème à l'étude. Lorsque nos connaissances du problème sont limitées, nous allons souvent procéder à une initialisation dite aléatoire<fnref n="30" /> des paramètres des individus. À chaque génération un certain nombre d'individus seront **sélectionnés** pour se **croiser**, passer à la génération suivante ou mourir en fonction de leur performance (telle que mesurée selon une fonction objective).

<footnote n="30">³⁰ Voir le chapitre 6 de [107] pour une discussion sur le hasard et la chance.</footnote>
### 4.2.3 Sélection

La sélection est l'action de choisir des individus qui se reproduiront et/ou survivront à la prochaine génération. C'est cette étape que l'on considère comme étant l'analogue à la sélection naturelle. Comme pour le processus biologique, on aura tendance à choisir les individus les mieux **adaptés** (meilleure performance) pour se reproduire et générer des enfants qui seront évalués à la prochaine génération. L'objectif est donc de prendre les meilleures solutions connues jusqu'à présent et les **croiser** dans le but d'obtenir progressivement de meilleurs résultats. Certains de ces enfants performeront bien, et d'autres moins bien, dans un processus de diversification qui convergera idéalement vers une solution satisfaisante.

C'est cette étape qui est la plus longue puisqu'elle exige une évaluation de tous les individus de la population. C'est justement cette fonction d'évaluation, la **fonction objective**, qui peut exiger un temps de calcul considérable. Prenons par exemple le cas de l'évaluation d'un modèle de langage pour la reconnaissance automatique de la parole. La meilleure fonction objective, donc la **mesure de performance absolue**, est celle qui utiliserait le taux d'erreur de reconnaissance. Par contre, cela nous contraint énormément en termes de temps, puisque l'évaluation complète d'un corpus de test demande du temps :

> Par exemple, admettons 10 minutes par évaluation par individu avec une population de 100 individus sur 200 générations. Nous aurons alors l'équivalent de 139 jours de calcul !

Il serait peut-être alors plus judicieux d'utiliser une autre mesure proxy de performance, une **mesure de performance relative**, par exemple la perplexité qui se calcule beaucoup plus rapidement. Toutefois, nous devons nous assurer de bien choisir/concevoir notre fonction objective puisqu'ultimement ce sera elle qui déterminera le sort de notre optimisation.

Plusieurs algorithmes de sélection sont possibles, mais le type de sélection le plus simple est celui de la sélection par roulette (roue de la Fortune).
### 4.2.3.1 Roulette

Dans la sélection par roulette, les chances de sélection pour la reproduction sont proportionnelles à la performance de chaque individu. Admettons cinq individus, chacun ayant la mesure de performance suivante :

* Individu 1 : score = 10

* Individu 2 : score = 20

* Individu 3 : score = 30

* Individu 4 : score = 40

* Individu 5 : score = 50

Ici, l'individu 5 est le mieux adapté et l'individu 1 est le moins adapté. Nous créerons alors une roue de la Fortune où chaque secteur représentera la probabilité d'être choisi en fonction de la performance relative de chaque individu. Nous choisirons alors les paires de parents en « tournant » la roulette. Dans notre exemple, l'individu 1 a 7 % de chance d'être choisi, l'individu 2, 13 % et ainsi de suite (voir Figure 4.1 pour l'ensemble des probabilités). Une fois le premier parent choisi, nous procédons à un deuxième tour de roulette, et ce, jusqu'à ce qu'un parent différent soit choisi. Nous pouvons éviter d'avoir la chance de retomber sur le premier individu choisi en mettant à jour notre roue pour tenir compte des probabilités ajustées (Figure 4.2).

<figure><img src="image_14.png" /><figcaption>Figure 4.1 : Illustration du concept de la roulette dans le contexte d'un algorithme génétique. Chaque secteur du graphique en secteurs représente les probabilités, relatives à leur performance, d'être choisi comme parent pour chaque individu de la population.</figcaption></figure>
<figure><img src="image_15.png" /><figcaption>**Figure 4.2 :** Illustration des probabilités relatives restantes ajustées après le tirage au premier tour de l'individu 5.</figcaption></figure>

### 4.2.3.2 Tournoi

Pour la sélection par tournoi, on choisit $τ \ge 2$ individus pour participer à un tournoi. Le tournoi consiste à comparer la performance des individus choisis pour déterminer le gagnant qui servira de parent pour la reproduction.

Dans sa version la plus simple, le **tournoi strict**, l'individu ayant la performance la plus élevée sera toujours choisi, et, si l'individu le plus performant de la population est choisi dans un tournoi, il gagnera avec 100 % de probabilité. Dans un **tournoi souple**, tous les individus ont une chance $0 < p < 1$ de gagner.

### 4.2.3.3 Logique de l'étalon

Dans la logique de l'étalon, l'individu avec la meilleure performance de chaque génération est toujours utilisé pour toutes les opérations de recombinaison. Simon [108] montre comment cette logique de sélection tend à beaucoup mieux performer que les algorithmes qui ne les mettent pas en œuvre. Par ailleurs, cette logique a comme avantage de réduire le coût computationnel de sélection puisque l'on a un seul autre individu au minimum (versus 2) à choisir par opération de reproduction.

### 4.2.3.4 Logique de l'élitisme

Dans la logique de l'élitisme, nous choisirons toujours les *E* meilleurs individus pour passer à la prochaine génération. Une des motivations derrière cette logique est que les meilleurs individus agissent comme une mémoire des meilleures solutions potentielles. En effet, dû aux effets de
croisement et de mutation, nous n'avons aucune garantie que les individus de la génération $g + 1$ soient mieux adaptés que ceux de la génération $g$.

Nous pouvons accomplir cela soit en produisant $N - E$ descendants où $N$ est la taille de la population et $E$ est le nombre d'élites à conserver. Une autre façon serait de produire $N$ descendants et remplacer les $E$ moins performants par les $E$ élites de la génération précédente.

De façon générale, les AE qui implémentent l'élitisme performent généralement mieux que les AE qui ne l'implémentent pas, sauf pour certains cas particuliers (fonctions objectives dispendieuses ou dynamiques [108]).

### 4.2.4 Croisement

La reproduction des individus se fait par croisement<fnref n="31" />, un processus analogue à l'enjambement des chromosomes. Pour le **croisement simple**, nous choisissons une position de croisement aléatoirement pour chaque paire d'individus (parents) choisis pour la reproduction et nous effectuerons un croisement entre les deux à partir du point choisi. La Figure 4.3 présente un exemple d'un croisement entre deux individus dans un cas d'AG binaire : pour chaque paire de parents, une paire d'enfants est conçue. C'est cette étape qui est responsable de l'exploration de l'espace de recherche par le biais de la création de nouveaux individus qui intègrent les paramètres de leurs parents et qui nous permettent (idéalement) de **diversifier** la population.

<figure><img src="image_16.png" /><figcaption>Figure 4.3 : Illustration du processus de croisement, à partir du quatrième allèle, pour un algorithme génétique binaire. Le point de croisement est généralement choisi de façon aléatoire.</figcaption></figure>

Nous pouvons généraliser le croisement simple en croisement en Mpoints par l'équation :

<footnote n="31">³¹ Enjambement pour reprendre le terme biologique, ou encore entrecroisement sont tous deux des termes acceptables et couramment utilisés dans la littérature.</footnote>
$$
\begin{align*}
\mathbf{y}_1(g) \leftarrow & \begin{bmatrix}
x_a(1) & \cdots & x_a(m_1) \\
x_b(m_1+1) & \cdots & x_b(m_2) \\
\vdots & \ddots & \vdots \\
x_a(m_{m-1}+1) & \cdots & x_a(m_m) \\
x_b(m_m+1) & \cdots & x_b(m_{m+1}) \\
\vdots & \ddots & \vdots \\
x_b(m_{M-1}+1) & \cdots & x_b(m_M) \\
x_a(m_M+1) & \cdots & x_a(N)
\end{bmatrix} \\
\mathbf{y}_2(g) \leftarrow & \begin{bmatrix}
x_b(1) & \cdots & x_b(m_1) \\
x_a(m_1+1) & \cdots & x_a(m_2) \\
\vdots & \ddots & \vdots \\
x_b(m_{m-1}+1) & \cdots & x_b(m_m) \\
x_a(m_m+1) & \cdots & x_a(m_{m+1}) \\
\vdots & \ddots & \vdots \\
x_a(m_{M-1}+1) & \cdots & x_a(m_M) \\
x_b(m_M+1) & \cdots & x_b(N)
\end{bmatrix} \tag{4.1}
\end{align*}
$$

où $\mathbf{y}_i(g)$ est le $i$-ème descendant de la génération $g$ des parents $\mathbf{x}_a$ et $\mathbf{x}_b$,

$x_\beta(k)$ représente le $k$-ème allèle du chromosome $x_\beta$,

$N$ est le nombre total d'allèles dans le chromosome,

$m_m$ sont des points de croisement,

$M$ est le nombre de points de croisement, si $M = 0$ alors $\mathbf{y}_i(g)$ seront des clones et si $M = 1$ on aura un croisement simple, $M = 2$, un croisement double, etc.

<figure><img src="image_17.png" /><figcaption>**Figure 4.4 :** Illustration du processus de croisement multipoints, pour un algorithme génétique binaire. Le point de croisement est généralement choisi de façon aléatoire.</figcaption></figure>

Le cas des algorithmes génétiques continus peut, pour sa part, être un peu plus complexe que le
cas des AG binaires. En effet, il n’est pas toujours approprié d’effectuer une reproduction par
croisement. Nous présentons ci-dessous deux méthodes qui nous ont servi pour notre travail de
thèse (voir chapitres 8 et 9 pour plus de détails), soit le croisement arithmétique et le croisement
heuristique.

4.2.4.1 Arithmétique

Le croisement arithmétique est utilisé exclusivement avec les algorithmes génétiques continus. Il s'apparente au processus d'interpolation utilisé dans la modélisation du langage

$$
\begin{align*}
\mathbf{y}(g) &\leftarrow U[x_a(k), x_b(k)] \\
&= \alpha x_a(k) + (1-\alpha)x_b(k) \tag{4.2}
\end{align*}
$$

où $\alpha \sim U[0,1]$ est tiré d'une distribution uniforme (ou tout autre type de distribution) entre 0 et 1,
$0 < k < N$ est le $k$ième allèle dans un chromosome.

$$
\begin{align*}
\mathbf{y}_1(g) &= \alpha x_a(k) + (1-\alpha)x_b(k) \\
\mathbf{y}_2(g) &= (1-\alpha)x_a(k) + \alpha x_b(k) \tag{4.3}
\end{align*}
$$

Un des avantages du croisement arithmétique est qu'il nous est possible de garantir le respect des bornes est des contraintes linéaires [109].

4.2.4.2 Heuristique

L'algorithme de croisement heuristique décrit ici est celui utilisé que nous avons utilisé tel que défini par [109]. Ce croisement heuristique va retourner un seul enfant qui se retrouve à une courte distance du parent ayant la meilleure performance dans une direction opposée à celle du parent avec la pire performance et est défini par l'équation :

$$
\[
\mathbf{y}(g) = \mathbf{x}_b + R * (\mathbf{x}_a - \mathbf{x}_b), \tag{4.4}
\]
$$

où la distance de l'enfant par rapport au meilleur parent est déterminée par le ratio R et où $\mathbf{y}(g) = \mathbf{x}_a$ quand $R = 1$.

4.2.5 Mutation

Un des problèmes avec les AG est que de bons candidats initiaux peuvent monopoliser la reproduction et biaiser la solution pour nous amener vers un optimum local. Pour contrer cela,
nous faisons appel à la mutation. La mutation nous permet de **diversifier** notre population, et, par le fait même, d'explorer un espace de solution plus vaste.

Tout comme son analogue biologique, la mutation est un phénomène qui se doit d’être assez rare, sinon nous aurions essentiellement une évolution complètement aléatoire de nos gènes. À l’inverse, un taux de mutation trop faible ne nous permettra pas d’explorer efficacement l’espace de recherche.

Nous permettrons donc à chaque allèle de chaque enfant de muter selon une probabilité $\rho$ prédéfinie, tel que (pour un AG binaire) :

$$ 
\begin{gathered}
r \leftarrow U[0,1] \\
y(k) \leftarrow \begin{cases} y(k), & r(k) \ge \rho \\ y(k)^{-1}, & r(k) < \rho \end{cases}
\end{gathered} 
\qquad (4.5) 
$$

où $r$ est un vecteur contenant un nombre entre 0 et 1 tiré d'une distribution uniforme (ou tout autre type de distribution) pour chaque allèle,

$\rho$ est la probabilité de mutation,

$y(k)^{-1}$ est l'inverse de $y(k) : 0 \text{ si } y(k) = 1, 1 \text{ sinon.}$

La Figure 4.5 montre un exemple d'une mutation sur un chromosome dans le cas d'un AG binaire.

<figure><img src="image_18.png" /><figcaption>**Figure 4.5 :** Illustration du résultat de la mutation d'un allèle sur un chromosome dans le cas d'un AG binaire.</figcaption></figure>

Dans le cas d'un AG continu, plusieurs options de mutation s'offrent à nous. Une des plus simples est la mutation uniforme centrée sur l'individu :
$$r_i \leftarrow U[0,1]$$

$$y_i(k) \leftarrow \begin{cases} y_i(k), & r_i(k) \ge \rho \\ U[y_i(k) - \alpha_i(k), y_i(k) + \alpha_i(k)], & r_i(k) < \rho \end{cases} \quad (4.6)$$

$$\alpha_i(k) = \min(y_i(k) - y_{min}(k), y_{max}(k) - y_i(k)),$$

où $r_i$ est un vecteur contenant un ensemble de nombres entre 0 et 1 tirés d'une distribution uniforme pour le $i$-ème enfant de la population et où $i \in [1, N]$,

$y_i$ est le $i$-ème enfant de la population,

$y_{min}(k)$ et $y_{max}(k)$ sont respectivement les valeurs minimales et maximales du $k$-ième allèle de la population.

$\alpha$ est alors choisi afin de maximiser l'exploration de l'espace de recherche sans, toutefois, dépasser les bornes du domaine de recherche.

### 4.2.6 Critère d'arrêt

Comme nous ne pouvons connaître d'avance la solution, il est important de définir un ou des critères d'arrêts afin d'éviter que l'algorithme **tourne à l'infini**. Parmi les choix usuels, nous retrouvons des critères d'arrêts basés sur le nombre de générations, la différence entre la solution ou un seuil que l'on considère comme adéquat.

### 4.2.7 Algorithme général de l'optimisation par algorithme génétique

Cela nous permet de définir un algorithme génétique général :
**Initialiser la première génération**, une population aléatoire de *N* individus **x** = {*x*<sub>i</sub>}, i ∈ [1, *N*]

**Définir** la fonction de sélection f<sub>s</sub>

**Définir** la fonction de croisement f<sub>c</sub>

**Définir** la fonction de mutation f<sub>m</sub>

**Définir** le nombre d'élites φ<sub>é</sub>

**Définir** le taux de croisement φ<sub>c</sub>

**Définir** le taux de mutation φ<sub>m</sub>

**Évaluer** la performance de chaque individu p<sub>i</sub> ← f(x<sub>i</sub>), i ∈ [1, *N*]

**Tant que non** (critère de terminaison)

**Pour chaque** individu x<sub>i</sub>, i ∈ [1, *N*]

$p_i \leftarrow f(x_i)$

**Prochain** individu

**Définir** les φ<sub>é</sub> élites

$$
\mathbf{E}_{\bullet} = \{p_{(1)}, \dots, p_{(\phi_{\bullet})}\} = \left\{ \min_{i=1}^{\phi_{\bullet}} \mathbf{p}_{\bullet}, \max_{i=1}^{2} \mathbf{p}_{\bullet}, \dots, \max_{i=1}^{\phi_{\bullet}} \mathbf{p}_{\bullet} \right\}, i \in [1, \phi_{\bullet}]
$$

**Ajouter** les élites à la prochaine génération **y** ← **E**<sub>•</sub>

**Pour** k = 1: *N* * φ<sub>c</sub>

Sélectionner les candidats pour le croisement

**Si** Étalon

$x_{p1} = \mathbf{E}_{(1)}$

Choisir deuxième parent x<sub>p2</sub> = f<sub>s</sub>(x)

**Sinon**

Choisir premier parent $x_{p1} = f_s(\boldsymbol{x})$

Choisir deuxième parent x<sub>p2</sub> = f<sub>s</sub>(x)

**Fin Si**

**Croiser** les deux parents **y** ← *c*<sub>*k*</sub> = f<sub>c</sub>(x<sub>p1</sub>, x<sub>p2</sub>) et ajouter à la prochaine génération

**Prochain** *k*

**Pour** *k* = 1: *N* * φ<sub>m</sub>

**Sélectionner** aléatoirement un candidat pour la mutation x<sub>k,m</sub>

Muter l'individu et ajouter le mutant à la prochaine génération **y** ← f<sub>m</sub>(x<sub>k,m</sub>)

**Prochain** *k*

Les individus de la génération **y** deviennent les nouveaux **x**, **x** = **y**, **y** = {0}

**Prochaine** génération

<caption>**Figure 4.6 :** Algorithme général de l'optimisation par algorithme génétique.</caption>

Où f(x) est la fonction objective utilisée pour évaluer la performance des individus.

E. est l'ensemble ordonné des élites de la génération courante.

p est le vecteur de la performance de chaque individu de la génération courante.
## 4.3 Optimisation par essais particulaires

Les algorithmes d'optimisation par essais particulaires, ou Particle Swarm Optimization (PSO) en anglais sont des algorithmes basés sur l'intelligence collective des colonies ou groupes d'individus. L'inspiration de ces algorithmes vient de l'observation des essais d'oiseaux [110] et des bancs de poissons où les individus semblent démontrer une forme d'intelligence collective soit pour échapper aux prédateurs, soit pour accroitre leur succès alimentaire ou encore pour minimiser leur dépense énergétique [111] pour n'en nommer que quelques-uns.

Chaque individu, ou particule, représente une solution candidate au problème à optimiser. Différents facteurs feront en sorte que chacune de ces particules parcours, généralement de façon linéaire, l'espace paramétrique multidimensionnel à la recherche de la meilleure solution possible. La vitesse et la direction dans lesquelles l'individu parcours l'espace sera influencé par divers paramètres internes (individuels) et externes (influence du groupe).

<figure><img src="image_19.png" /><figcaption>Figure 4.7 : Exemple de convergence d'un essais particulaires cherchant un minimum global d'une fonction..</figcaption></figure>

Source : Par Ephramac — Travail personnel, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=54975083

### 4.3.1 Inertie

L'inertie, phénomène à la base physique et posée par Kepler [112] se définit comme étant la résistance d'un objet au changement de son état. Les individus ont tendance à résister au changement, de faire les choses comme avant, l'influence de la société ou du groupe pourra
« encourager » un changement d'attitude. Le principe d'inertie, représenté par $ω$, tel que définit pour l'optimisation par essais particulaires a initialement été défini par Shi et Eberhart [113]. Afin d'éviter que les particules ne « bougent » sans arrêt dans l'espace de solution sans converger, la valeur d'inertie sera généralement initialisée à une valeur maximale qui sera par la suite progressivement diminuée jusqu'à 0 : plus la solution est bonne, moins l'individu aura tendance à vouloir bouger, ce qui aide l'algorithme à garantir une convergence éventuelle.

Une autre façon de voir l'impact de l'inertie sur le comportement de l'OEP est que lorsque $ω$ est élevé ($ω > 1,2$), l'OEP se comporte plus comme un algorithme de recherche global, et lorsqu'il est petit ($ω < 0,8$), l'OEP se comporte plutôt comme un algorithme de recherche local. De cette façon, le résultat final est moins dépendant de l'état de notre population initiale puisque durant les premières générations les individus auront tendance à explorer une grande partie de l'espace de solution possible et au fur et à mesure que l'algorithme progresse, la population aura naturellement tendance à se diriger vers la meilleure solution possible.

### 4.3.2 Apprentissage individuel

Le principe de l'apprentissage individuel est représenté par le taux d'apprentissage cognitif $\phi_1$ qui est basé sur le renforcement positif, c'est-à-dire que l'on apprend de nos succès. Si la solution trouvée à la génération actuelle est meilleure que la meilleure solution trouvée à date par l'individu, celui-ci continuera d'explorer l'espace dans la direction actuelle. Sinon, l'individu ralentira sa cadence pour éventuellement changer de direction si la solution continue de ne pas s'améliorer.

### 4.3.3 Influence par le groupe

Le principe de l'influence par le groupe est le même que celui de l'influence de la société, ci-dessous, sauf que la sphère d'influence est généralement plus limitée, mais plus forte. Les individus vont donc avoir tendance à suivre le groupe. Dans l'optimisation par essais particulaires, ce paramètre est défini comme étant le taux d'apprentissage social $\phi_2$ : on apprend par le succès de ses pairs. Ce paramètre fera en sorte qu'un individu tende à se diriger vers le voisin (voir section 4.3.5) ayant trouvé la meilleure solution à date, ou faire en sorte que le groupe tende à se diriger vers l'individu ayant trouvé la meilleure solution à date.
### 4.3.4 Influence de la société

Les individus vont regarder ce que les individus réussissent et vont combattre leur inertie afin d'émuler leur succès. Dans l'optimisation par essais particulaires, ce paramètre est défini comme étant le taux d'apprentissage global $\phi_3$ et s'apparente au concept d'élitisme vu dans les algorithmes génétiques.

Le concept est donc similaire à celui de l'influence par le groupe, mais à l'échelle globale.

### 4.3.5 Voisinage

Le voisinage définit à la fois la topologie de la relation entre les individus d'un groupe ainsi que la taille de celui-ci. Plusieurs formes de topologies s'offrent à nous et reflètent le type de topologie que l'on pourrait retrouver dans un réseau informatique : anneau, maillage complet, étoile, carré, etc.

<figure><img src="image_20.png" /><figcaption>Figure 4.8 : Exemple de topologies de voisinage.</figcaption></figure>

Par ailleurs, ce voisinage peut être défini de façon soit statique : le voisinage est défini au début de l'algorithme et demeure fixe tout au long de son exécution ; soit dynamique : le voisinage va évoluer au fur et à mesure que le l'algorithme progresse et que les individus de déplacent dans l'espace de recherche. Une autre approche populaire consiste en l'initialisation d'un voisinage et, lorsque le taux de convergence semble stagner, on réinitialise le voisinage de façon aléatoire afin de stimuler une plus grande couverture de l'espace de recherche.

### 4.3.6 Taux d'apprentissage

En plus de l'apprentissage par renforcement positif ($\phi_1, \phi_2, \phi_3$), les individus peuvent aussi apprendre de leurs propres erreurs $\phi_4$ ainsi que des erreurs du groupe $\phi_5$ et de la société $\phi_6$ : l'apprentissage par le renforcement négatif. Les individus, et la société auront donc tendance à éviter les mauvaises stratégies.

Cela nous permet finalement de généraliser l'équation de la mise à jour de la vitesse telle que :
$$v_i \leftarrow \omega v_i + \phi_1(b_i - x_i) + \phi_2(h_i - x_i) + \phi_3(g - x_i) \\ - \phi_4(\bar{b}_i - x_i) - \phi_5(\bar{h}_i - x_i) - \phi_6(\bar{g} - x_i), \qquad (4.7)$$

où : $x_i$ est le ième individu (ou la ième solution candidate)

$v_i$ est le vecteur de vitesse du ième individu (la vitesse de déplacement de l'individu dans les n dimensions de la solution).

$\omega$ est le vecteur n-dimensionnel d'inertie. Shi et Eberhart [113] proposent de faire varier, de façon décroissante, l'inertie des particules à chaque génération afin de ralentir les particules, ce qui améliore la convergence.

$\phi_j$ sont les taux d'apprentissage : $\phi_1$ le taux d'apprentissage cognitif, $\phi_2$ le taux d'apprentissage social, $\phi_3$ le taux d'apprentissage global, $\phi_4$, le taux d'apprentissage cognitif d'évitement, $\phi_5$, le taux d'évitement social, $\phi_6$, le taux d'évitement global.

$g$ et $\bar{g}$ sont, respectivement, la meilleure et la pire solution actuelle de toute la population.

$h_i$ et $\bar{h}_i$ sont, respectivement, la meilleure et la pire solution du voisinage, de taille $\sigma$, du ième individu.

$b_i$ et $\bar{b}_i$ sont, respectivement, la meilleure et la pire solution à date du ième individu.

### 4.3.7 Algorithme général de l'optimisation par essais particulaires

Finalement, dans la Figure 4.9, nous définissons un algorithme général d'optimisation par essais particulaires.