**Initialiser** une population aléatoire de N individus $\boldsymbol{x} = \{x_i\}, i \in [1, N]$

**Initialiser** le vecteur n-dimensionnel de véclocité de chaque individu $v_i, i \in [1, N]$

**Définir** la valeur maximale d'inertie $\omega_{max}$

**Initialiser** la meilleure position à date de chaque individu $b_i \leftarrow x_i, i \in [1, N]$

**Définir** la meilleure position à date de toute la société

$$g \leftarrow \operatorname{argmin}\{f(B)\}$$

**Initialiser** la pire position à date de chaque individu $\bar{b}_i \leftarrow x_i, i \in [1, N]$

**Définir** la pire position à date de toute la société $\bar{g} \leftarrow \operatorname{argmax}\{f(\bar{B})\}$

**Définir** la taille du voisinage $\sigma < N$

**Définir** les valeurs maximales d'influence $\phi_{1,max}, \phi_{2,max}, \phi_{3,max}, \phi_{4,max}, \phi_{5,max}, \phi_{6,max}$

**Initialiser** le vecteur n-dimensionnel de véclocité maximale $v_{i,max}, i \in [1, n]$

**Initialiser** le vecteur n-dimensionnel d'inertie $\omega_{i,max}, i \in [1, n]$

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

**Pour chaque** individu $x_i, i \in [1, N]$

$$H_i \leftarrow \{\sigma \text{ voisins les plus près d}'x_i\}$$

$$h_i \leftarrow \operatorname{argmin}_x \{f(x): x \in H_i\}$$

$$\bar{h}_i \leftarrow \operatorname{argmax}_x \{f(x): x \in H_i\}$$

**Pour chaque** valeur d'influence $\phi_j, j \in [1,6]$

Générer un vecteur aléatoire $\phi_j$ avec $\phi_j(k) \sim U[0, \phi_{j,max}]$
pour $k \in [1, n]$

**Prochaine** valeur d'influence

$$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)$$

Si $|v_i| > v_{max}$ alors

$$v_i \leftarrow v_i v_{max} / |v_i|$$

**Fin si**

$$x_i \leftarrow x_i + v_i$$

$$b_i \leftarrow \operatorname{argmin}\{f(x_i), f(b_i)\}$$

$$\bar{b}_i \leftarrow \operatorname{argmax}\{f(x_i), f(\bar{b}_i)\}$$

$$g \leftarrow \operatorname{argmin}\{f(x_i), f(g)\}$$

$$\bar{g} \leftarrow \operatorname{argmax}\{f(x_i), f(\bar{g})\}$$

**Prochain** individu

Mettre à jour le vecteur d'inertie $\omega = \omega - \delta(t)$

**Prochaine** génération

<caption>**Figure 4.9 :** Algorithme général de l'optimisation par essaim particulaire.</caption>

où $f(x)$ est la fonction objective utilisée pour calculer la performance de l'individu $x$,
$B$ est l'ensemble des meilleures positions,
$\bar{B}$ est l'ensemble des pires positions,
$H_i$ est le voisinage de l'individu $x_i$ et
$\delta(t)$ est un facteur d'ajustement de l'inertie et où l'inertie diminuera généralement de génération $t$ en génération $t + 1$.

## 4.4 Évaluation et comparaison de la performance d'algorithmes évolutionnaires pour l'optimisation des poids d'interpolation

Dans cette section nous évaluons la capacité des AE à trouver des solutions optimales pour l'interpolation de nos modèles de langage et les comparerons aux algorithmes classiques principalement utilisés dans le domaine : la méthode de Powell [101] et l'optimisation par l'algorithme espérance-maximisation. Les questions auxquelles nous souhaitons répondre sont les suivantes :

* Est-ce que les algorithmes évolutionnaires peuvent obtenir de meilleurs résultats que les algorithmes classiques ?

* Est-ce que les algorithmes évolutionnaires peuvent obtenir une solution plus rapidement que les algorithmes classiques ?

* Est-ce que les algorithmes évolutionnaires peuvent réduire dynamiquement le nombre de bacs qui seront interpolés avec le modèle de langage principal ?

* Quel est l'effet des différents paramètres sur la vitesse de convergence de l'algorithme génétique ainsi que sur la performance de la solution obtenue ?

Afin de répondre à ces questions, nous avons généré des bacs jusqu'à une distance ontologique de 7 nœuds comparativement à 5 nœuds dans nos travaux précédents [86], [87].

De surcroît, comme les algorithmes évolutionnaires sont de nature stochastique, nous comparons leurs performances respectives à l'aide de la méthode de Monte-Carlo à 55 tours. Cela nous permettra d'avoir un portrait plus juste de leur performance respective.

La procédure utilisée pour générer les modèles de langage de base est la même que celle utilisée pour nos travaux ultérieurs [86], [87] et est décrite plus en détail à la section 3.3.

Nous utilisons l'outil SRILM [93] pour obtenir les comptes bruts du corpus d'entrainement. Nous utilisons ensuite notre algorithme de lissage ontologique pour générer des comptes lissés pour
chaque bac de distance tel que défini à la section 3. Bien que ces comptes lissés comportent maintenant de nouveaux mots, ceux-ci sont éliminés lors de la génération du modèle de langage final. Nous utilisons l’ensemble d’entrainement de 76 000 phrases du corpus WSJ1 [92] pour un total de 1,2 M mots.

Un modèle de base (trigramme) lissé à l'aide de l'algorithmme Witten-Bell est créé et servira de modèle de langage de base pour l'interpolation des bacs issus de notre algorithme de lissage basé sur les ontologies.

Les expériences ont été effectuées sur un ordinateur double processeur à 6 cœurs par processeurs avec la technologie Hyper-Threading d’Intel pour un total de 24 processeurs logiques et 48 Gio de mémoire vive.

### 4.4.1 L'analogie entre paramètres évolutionnaires et ceux du modèle de langage

Afin de faciliter la compréhension de la pertinence de l'approche utilisant les AE que nous proposons pour optimiser la modélisation du langage, nous explicitons dans ce qui suit la relation entre les paramètres évolutionnaires et ceux relatifs au modèle du langage.

Ainsi, les poids d'interpolation représentent les paramètres de la population et la perplexité du modèle de langage interpolé définit la fonction objective :

Pour l'optimisation par algorithmes génétique, l'analogie est la suivante : chaque individu, défini par un chromosome $\alpha_i$, représente les poids $\lambda$ d'interpolation des bacs ontologiques, ainsi que les bacs qui seront interpolés. Chaque allèle $a_i(k)$ représente donc soit un poids $\lambda_k$ d'interpolation, soit un bit d'activation $\delta_k$.

Pour l'optimisation par essais particulaires, l'analogie est similaire : chaque individu $x_i$ est représenté par sa position dans l'espace de recherche et où sa position est définie par les poids d'interpolation $\lambda_k$ et les bits d'activation $\delta_k$ des bacs ontologiques.

Pour illustrer plus clairement le concept, admettons une distance ontologique $D = 3$ et où $h = w_{n-N+1}^{n-1}$. En reprenant l'équation 3.2 :

$$P'(w_n|h) = \lambda_0 P(w_n|h) + \sum_{d=1}^{3} \lambda_d P_{B_d}(w_n|h).$$
Afin de simplifier l'implémentation du problème d'optimisation, nous définissons

$$ \lambda_0 = 1 - \sum_{j=1} \lambda_j $$

Si on développe celle-ci, on obtient alors :

* Un individu sera représenté par un vecteur

$$ x_i = \{ (\lambda_1, \lambda_2, \lambda_3), (\delta_1, \delta_2, \delta_3) \} $$

Où

$0 \le \lambda_j \le 1$ et $0 < \sum_j \lambda_j < 1$ sont les poids d'interpolation des bacs $P_{B_j}$ à optimiser.

$0 \le \delta_j \le 1$ sont les marqueurs d'activation correspondants aux bacs $P_{B_j}$ et où la désactivation s'effectue à $\delta_j < 0,5$. Les bacs désactivés ne seront donc pas interpolés au modèle de langage principal et leur poids sera redistribué à $\lambda_0$.

Admettons un individu $x_i = \{(0,1;0,5;0,5); (0,8;0,8;0,3)\}$, le modèle de langage pour cet individu sera alors égal à $P'_{x_i}(w_n|h) = 0,4P(w_n|h) + 0,1P_{B_{d_1}}(w_n|h) + 0,5P_{B_{d_2}}(w_n|h)$.

### 4.4.2 Initialisation et paramètres de la population

Comme pour les algorithmes conventionnels, le choix de topologie des individus peut avoir un impact significatif sur la performance des algorithmes évolutionnaires [108], [114]. En effet, si le choix de paramètres caractérisant le problème n'est pas judicieux, il se peut que l'algorithme converge vers une solution insatisfaisante ou nécessite un très grand nombre de générations pour converger.

Pour notre problème d'optimisation des poids d'interpolation de nos modèles de langage, nous avons opté pour une topologie mixte pour nos chromosomes/individus. Pour fin de simplification nous utiliserons la nomenclature des algorithmes génétiques.

Nos chromosomes sont composés de $K = 2k$ allèles réels et «binaires» simulés et où $k = d_{max}$ bacs potentiels à interpoler. Les $k$ premiers allèles, de format réel, représentent les poids d'interpolation actifs, les $k$ derniers allèles, de format binaire simulé, représentent un vecteur
d’activation des bacs. Cela nous permet à la fois d’optimiser les poids d’interpolation individuels et de désactiver (désactivation à $\delta_i < 0,5$) les bacs qui contribuent peu ou pas à la solution. Nous avons choisi comme valeur de désactivation 0,5 afin de simuler une valeur binaire :

$$ \delta_i = \begin{cases} 1 & si \quad 0,5 \le \delta_i \le 1 \\ 0 & si \quad 0 \le \delta_i < 0,5 \end{cases} $$

Nous noterons ici que le choix de probabilités non équiprobables entre le 0 et 1 binaire a été choisie afin de statistiquement encourager le maintien du plus grand nombre de bacs. Ainsi, si l’algorithme tend vers une désactivation, ceci nous donne une certaine garantie par rapport à son élimination. Nous avons choisi cette topologie particulière afin de renforcer la robustesse de la méthode et d’optimiser le temps de calcul. En effet, lors de nos premières expériences, nous utilisions des chromosomes à valeurs réelles de taille $k = d_{max}$ avec une désactivation des bacs basée sur un seuil plancher ($\lambda_i < 1,0E^{-6}$). Cependant, la vitesse de convergence était très lente (approximativement une demi-journée par tentative sur un ordinateur à 24 processeurs logiques et 48 Gio de mémoire vive).

### 4.4.3 Évaluation de la mutation, de la sélection et du taux de croisement

Dans cette section, nous évaluons l’effet sur la vitesse de convergence de l’optimisation par algorithme génétique de la variation des taux de mutation et de croisement et du nombre de candidats utilisés pour l’algorithme de sélection. Tous les résultats présentés représentent la moyenne de 25 simulations Monte-Carlo.

Dans cette section nous présentons aussi les résultats de l’évaluation des modèles de langage obtenus pour chaque expérience. Comme à la section 4.4.7, les modèles de langage ont été évalués sur le corpus d’évaluation du Wall Street Journal-based Continuous Speech Recognition (CSR) Corpus Phase II (WSJ1) [92]. Les ensembles utilisés pour l’évaluation sont les suivants :

* Hub 1 (base de référence WSJ lue),

* Spoke 1 (adaptation des modèles de langage),

* Spoke 2 (indépendance du domaine)

* Spoke 9 (diction spontanée WSJ)
Cela nous donne un total de 23 000 mots dans 1285 phrases sans filtrage des phrases contenant des mots hors vocabulaire. Le vocabulaire (fermé) utilisé est le vocabulaire WSJ standard de 20 000 mots. Le taux de mots hors vocabulaire est de 5,64 %.

Tel que décrit à la section 3.3, l'ensemble de développement/validation, comportant 4 340 phrases et un total de 71 759 mots, est utilisé pour l'optimisation des poids d'interpolation des bacs.

### 4.4.3.1 Nombre de candidats, sélection par tournoi

Tel que vu à la section, la sélection est l'action de choisir des individus qui se reproduiront et/ou survivront à la prochaine génération. La sélection par tournoi choisit un nombre fixe d'individus de façon aléatoire et choisit le meilleur individu du groupe. Il est donc possible que seulement de mauvaises solutions soient choisies. Nous évaluons donc l'effet du nombre d'individus choisi afin de déterminer si un nombre de candidats plus élevé apportera de meilleurs résultats puisque plus de chance de choisir des individus performants.

Les paramètres fixes utilisés pour l'évaluation sont décrits dans le Tableau 4.1. Notons d'ailleurs qu'afin de légèrement accélérer la vitesse de convergence que nous avons augmenté la valeur *FunctionTolerance* (seuil à partir duquel on considère qu'une solution stable est obtenue), passant de 0,01 à 0,05.

La Figure 4.10 présente la vitesse de convergence moyenne de l'optimisation par algorithme génétique avec de 2 à 15 individus choisis aléatoirement pour le tournoi de sélection.

En analysant la Figure 4.10.a, optimisation sans amorçage, nous notons une convergence plus rapide avec 4 individus et, de façon surprenante, la plus lente avec 5 individus (17 générations de plus). La sélection à 8 individus semble avoir tendance à diverger vers les dernières générations. La sélection à 9 individus a un comportement aberrant, mais finit par converger plus rapidement qu'avec 5 individus.
<table><caption>Tableau 4.1 : Paramètres fixes utilisés pour l'évaluation du nombre d'individus choisis pour la fonction de sélection par tournoi.</caption><thead><tr><td>Paramètre</td><td>Description</td><td>Valeur</td></tr></thead><tbody><tr><td>PopulationSize</td><td>Nombre d'individus</td><td>70</td></tr><tr><td>CreationFcn</td><td>Fonction de création d'individus</td><td>@gacreationuniform</td></tr><tr><td>MutationFcn</td><td>Fonction de mutation</td><td>@mutationadaptfeasible</td></tr><tr><td>CrossoverFcn</td><td>Fonction de croisement</td><td>@crossoverarithmetic</td></tr><tr><td>SelectionFcn</td><td>Fonction de sélection</td><td>@selectiontournament</td></tr><tr><td>CrossoverFraction</td><td>Pourcentage des individus qui sont le fruit d'un croisement</td><td>0,8</td></tr><tr><td>EliteCount</td><td>Nombre d'élites retenus</td><td>3</td></tr><tr><td>FitnessScalingFcn</td><td>Fonction de mise à l'échelle de la fonction de coût</td><td>@fitscalingrank</td></tr><tr><td>FunctionTolerance</td><td>Changement minimum constant considéré avant que l'algorithme termine.</td><td>0,05</td></tr></tbody></table>

Les résultats de l'optimisation avec amorçage sont beaucoup plus homogènes que ceux obtenus sans amorçage. Les expériences utilisant 3, 8 et 15 individus ressortent un peu du lot et prennent plus de temps à passer le cap du 114.5 que les autres. Le tournoi à 6 individus converge en moyenne vers une meilleure solution plus rapidement que les autres.

Les Figures 4.10 (a) et (b) présentent les résultats de l'évaluation de la perplexité des modèles de langage obtenus selon les différents paramètres. Les résultats obtenus ne nous permettent pas de prédire les résultats attendus : aucun motif apparent ne ressort. Cela nous porte à conclure que le comportement sera probablement très dépendant du problème à optimiser et que, pour la sélection par tournoi, le seul moyen de choisir le nombre optimal d'individus pour un problème donné est de façon empirique. Cela cadre d'ailleurs avec les applications du « monde réel » où l'on utilisera habituellement, comme dans notre cas, un ensemble de données de développement pour déterminer les paramètres optimaux propres à un problème d'optimisation.
<figure><img src="image_21.png" /><figcaption>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.</figcaption></figure>
Évaluation et comparaison de la performance d'algorithmes évolutionnaires pour l'optimisation des poids d'interpolation

Cela dit, dans notre cas particulier, les meilleurs résultats sont obtenus avec des tournois à 5 individus pour l'optimisation sans amorçage et des tournois à 6 individus pour l'optimisation avec amorçage.

Finalement, le Tableau 4.2 présente un résumé des résultats obtenus pour chaque groupe d'expérience. Sans amorçage, les meilleurs résultats, en moyenne, sont obtenus avec des tournois de 5 individus, tandis que les pires en moyenne le sont avec des tournois de 9 individus. Pour ce qui est de l'optimisation avec amorçage, les meilleurs résultats, en moyenne, sont obtenus avec des tournois à 12 participants.

Ces résultats sont cohérents avec ceux obtenus dans la section 4.4.6 où nous avons utilisé des tournois à 6 individus.

<table><caption>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.</caption><thead><tr><th rowspan="2">Nombre d'individus</th><th colspan="3">Perplexité (tournoi)</th><th colspan="3">Perplexité (tournoi+EM)</th></tr><tr><th>Moyenne</th><th>Min</th><th>Max</th><th>Moyenne</th><th>Min</th><th>Max</th></tr></thead><tbody><tr><td>2</td><td>207,143</td><td>177,793</td><td>268,193</td><td>171,8481</td><td>171,413</td><td>172,859</td></tr><tr><td>3</td><td>219,180</td><td>170,331</td><td>291,152</td><td>171,9017</td><td>171,319</td><td>174,064</td></tr><tr><td>4</td><td>186,512</td><td>170,339</td><td>247,984</td><td>171,6158</td><td>170,977</td><td>172,097</td></tr><tr><td>5</td><td><strong>185,515</strong></td><td>170,294</td><td><strong>228,911</strong></td><td>171,9779</td><td>171,322</td><td>174,674</td></tr><tr><td>6</td><td>213,531</td><td>171,008</td><td>317,868</td><td>171,4919</td><td>171,382</td><td><strong>171,682</strong></td></tr><tr><td>7</td><td>222,291</td><td>171,466</td><td>349,469</td><td>171,6857</td><td>171,239</td><td>172,827</td></tr><tr><td>8</td><td>197,488</td><td>170,289</td><td>245,475</td><td>171,5837</td><td>171,264</td><td>171,877</td></tr><tr><td>9</td><td>223,268</td><td>171,181</td><td>332,296</td><td>171,6814</td><td>171,269</td><td>172,347</td></tr><tr><td>10</td><td>196,194</td><td>171,859</td><td>229,375</td><td>171,5666</td><td>171,248</td><td>171,853</td></tr><tr><td>11</td><td>217,584</td><td>170,277</td><td>310,086</td><td>171,7819</td><td>171,441</td><td>173,029</td></tr><tr><td>12</td><td>191,062</td><td>170,950</td><td>247,366</td><td><strong>171,4039</strong></td><td>171,075</td><td>171,726</td></tr><tr><td>13</td><td>214,863</td><td>170,260</td><td>282,979</td><td>171,5757</td><td>171,153</td><td>172,523</td></tr><tr><td>14</td><td>199,774</td><td>170,191</td><td>260,211</td><td>171,5608</td><td>171,024</td><td>172,958</td></tr><tr><td>15</td><td>212,655</td><td><strong>170,188</strong></td><td>446,248</td><td>171,5395</td><td><strong>170,81</strong></td><td>172,816</td></tr></tbody></table>
<figure><img src="image_22.png" /><figcaption>Figure 4.11 : Résultats de l'évaluation des modèles de langages obtenus avec différent nombre d'individus par tournois. (a) présente les résultats de l'optimisation sans amorçage tandis que (b) présente les résultats de l'optimisation avec amorçage.</figcaption></figure>
### 4.4.3.2 Taux de croisement

La reproduction des individus se fait par croisement, un processus analogue à l'enjambement des chromosomes. 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.

Dans cette section, nous évaluons l'effet du taux de croisement sur la performance des modèles de langage obtenus. Le taux de croisement représente la proportion d'individus qui seront le résultat d'une opération de croisement. La fonction de croisement utilisée pour cette évaluation est la fonction de croisement arithmétique. Le Tableau 4.3 résume les paramètres statiques utilisés pour cette évaluation.

La Figure 4.11 présente les résultats moyens de convergence obtenus avec les différents taux de croisement. Un taux de 30 % converge le plus rapidement et obtient les meilleurs résultats en termes de perplexité (voir Tableau 4.4) lors de l'optimisation sans amorçage. Cela est assez surprenant et semble indiquer qu'un faible taux de croisement est très bénéfique pour ce problème particulier d'optimisation.

<table><caption>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.</caption><thead><tr><td>Paramètre</td><td>Description</td><td>Valeur</td></tr></thead><tbody><tr><td>PopulationSize</td><td>Nombre d'individus</td><td>70</td></tr><tr><td>CreationFn</td><td>Fonction de création d'individus</td><td>@gacreationuniform</td></tr><tr><td>MutationFn</td><td>Fonction de mutation</td><td>@mutationadaptfeasible</td></tr><tr><td>CrossoverFn</td><td>Fonction de croisement</td><td>@crossoverarithmetic</td></tr><tr><td>SelectionFn</td><td>Fonction de sélection</td><td>@selectiontournament (tournoi à 6 individus)</td></tr><tr><td>Taux de mutation</td><td>Pourcentage des individus qui subiront une mutation</td><td>0,20</td></tr><tr><td>EliteCount</td><td>Nombre d'élites retenus</td><td>3</td></tr><tr><td>FitnessScalingFn</td><td>Fonction de mise à l'échelle de la fonction de coût</td><td>@fitscalingrank</td></tr><tr><td>FunctionTolerance</td><td>Changement minimum constant considéré avant que l'algorithme termine.</td><td>0,005</td></tr></tbody></table>
Évaluation et comparaison de la performance d'algorithmes évolutionnaires pour l'optimisation des poids d'interpolation

Pour ce qui est de l'optimisation avec amorçage, les taux de croisement de 80 % et 90 % convergent le plus rapidement. Cela est assez cohérent avec le concept de l'amorçage où la population initiale reflète une solution adéquate, et un taux de croisement trop faible n'aura pas

<figure><img src="image_23.png" /><figcaption>Figure 4.12 : Convergence moyenne suite à 25 simulations Monte-Carlo de l'optimisation par AG : (a) représente la convergence moyenne pour un taux de croisement de 10 % à 90 % sans amorçage. (b) représente la convergence moyenne pour un taux de croisement de 10 % à 90 % avec amorçage.</figcaption></figure>
tendance à améliorer la performance des meilleurs individus, voir aura tendance à l'empirer. Cette
observation se confirme avec un taux de croisement de 10 % où la solution obtenue est pire que la
solution proposée lors de l'amorçage. Il est cependant important de noter, qu'avec amorçage, que
la pire solution est obtenue avec un taux de croisement de 20 % (Figure 4.11 [b]) : la meilleure
solution obtenue lors de l'optimisation ne donnera pas nécessairement lieu à la meilleure solution
pratique. Pour ce qui est des autres taux de croisement, l'algorithme converge de façon beaucoup
plus prévisible.

La Figure 4.13 et le Tableau 4.4 présentent les résultats de l'évaluation de la perplexité des modèles de langage obtenus selon les différents taux de croisements évalués. Comme ce fut le cas pour l'évaluation de la taille des groupes pour la sélection par tournoi, les résultats obtenus nous permettent difficilement de prédire les résultats attendus. Par contre, nous constatons tout de même une tendance un peu plus nette par rapport à l'évaluation de la fonction de sélection.

L'optimisation sans amorçage semble privilégier de faibles taux de croisement, avec une
performance marquée à 10 % et 30 %. En effet, les résultats obtenus sont très stables avec un écart-
type de 10,98, et 10,63 respectivement. Avec un taux de croisement de 70 %, nous observons un
pic particulièrement difficile à expliquer étant donné que nous nous attendons à ce qu'un fort taux
de croisement encourage la diversité et l'amélioration progressive de la population.

Les résultats obtenus avec amorçage ont un comportement inverse : les pires résultats sont obtenus avec de faibles taux de croisement et les meilleurs résultats sont observés à un taux de croisement de 60 %, 70 % et 90 %. Il est ici difficile de dire avec certitude lequel des taux de croisement est le plus favorable : un taux de 60 % produit les meilleurs résultats en moyenne, ainsi que le meilleur résultat absolu, tandis que les taux de 70 % et 90 % produisent des résultats beaucoup plus prévisibles.
<figure><img src="image_24.png" /><figcaption>Figure 4.13 : Résultats de l'évaluation des modèles de langage obtenus avec différent taux de croisement pour la fonction de croisement arithmétique. (a) présente les résultats de l'optimisation sans amorçage tandis que (b) présente les résultats de l'optimisation avec</figcaption></figure>
<table><caption>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.</caption><thead><tr><th rowspan="2">Taux de croisement</th><th colspan="3">Perplexité (croisement)</th><th colspan="3">Perplexité (croisement+EM)</th></tr><tr><th>Moyenne</th><th>Min</th><th>Max</th><th>Moyenne</th><th>Min</th><th>Max</th></tr></thead><tbody><tr><td>10 %</td><td>178,154</td><td><strong>170,182</strong></td><td>200,4</td><td>172,003</td><td>170,994</td><td>174,667</td></tr><tr><td>20 %</td><td>185,256</td><td>170,802</td><td>217,835</td><td>173,048</td><td>171,194</td><td>181,42</td></tr><tr><td>30 %</td><td><strong>176,648</strong></td><td>170,261</td><td><strong>198,148</strong></td><td>172,669</td><td>171,233</td><td>181,547</td></tr><tr><td>40 %</td><td>187,018</td><td>170,543</td><td>212,299</td><td>172,065</td><td>171,413</td><td>175,21</td></tr><tr><td>50 %</td><td>181,061</td><td>170,505</td><td>201,754</td><td>171,962</td><td>171,342</td><td>174,114</td></tr><tr><td>60 %</td><td>191,941</td><td>170,414</td><td>294,583</td><td><strong>171,637</strong></td><td><strong>170,974</strong></td><td><strong>172,359</strong></td></tr><tr><td>70 %</td><td>219,010</td><td>171,794</td><td>350,714</td><td>172,107</td><td>171,305</td><td>177,217</td></tr><tr><td>80 %</td><td>210,518</td><td>173,85</td><td>331,942</td><td>171,904</td><td>171,254</td><td>173,645</td></tr><tr><td>90 %</td><td>197,845</td><td>179,712</td><td>222,759</td><td>171,761</td><td>171,395</td><td>172,44</td></tr></tbody></table>

### 4.4.3.3 Taux de mutation

Comme nous l'avons vu à la section 4.2.5, la mutation nous permet de diversifier notre population, et, par le fait même, d'explorer un espace de solution plus vaste. En principe, un taux de mutation trop faible risque de converger vers une solution locale, tandis qu'un taux de mutation trop élevé risque plutôt de nous empêcher de converger vers une solution convenable. C'est pourquoi il est important d'essayer d'atteindre un équilibre entre un taux trop faible ou un taux trop élevé de mutation, cela est particulièrement pertinent pour l'optimisation avec amorçage où la solution initiale proposée devrait être une solution optimale locale.

Le Tableau 4.5 présente un résumé des paramètres statiques utilisés pour évaluer l'influence du taux de mutation sur l'optimisation par algorithmes génétiques des poids d'interpolation du modèle de langage.

La fonction de mutation utilisée dans le cadre de ce travail est la fonction Matlab d'adaptation possible (adapt feasible). Cette fonction génère essentiellement un vecteur de directions aléatoires qui prennent en considération les limites et contraintes linéaires de la fonction à optimiser [109]. Elle vérifie par la suite si les valeurs résultantes donnent un résultat valide et satisfont aux limites
<table><caption>Tableau 4.5 : Paramètres statiques pour l'évaluation de la mutation.</caption><thead><tr><td>Paramètre</td><td>Description</td><td>Valeur</td></tr></thead><tbody><tr><td>PopulationSize</td><td>Nombre d'individus</td><td>70</td></tr><tr><td>CreationFcn</td><td>Fonction de création d'individus</td><td>@gacreationuniform</td></tr><tr><td>MutationFcn</td><td>Fonction de mutation</td><td>@mutationadaptfeasible</td></tr><tr><td>CrossoverFcn</td><td>Fonction de croisement</td><td>@crossoverarithmetic</td></tr><tr><td>SelectionFcn</td><td>Fonction de sélection</td><td>@selectiontournament (tournoi à 6 individus)</td></tr><tr><td>CrossoverFraction</td><td>Pourcentage des individus qui sont le fruit d'un croisement</td><td>0,8</td></tr><tr><td>EliteCount</td><td>Nombre d'élites retenus</td><td>3</td></tr><tr><td>FitnessScalingFcn</td><td>Fonction de mise à l'échelle de la fonction de coût</td><td>@fitscalingrank</td></tr><tr><td>FunctionTolerance</td><td>Changement minimum constant considéré avant que l'algorithme termine.</td><td>0,005</td></tr></tbody></table>

et contraintes. Une fois ces valeurs validées, la fonction génère un nouvel individu qui vera sa performance évaluée.

La Figure 4.13 présente les résultats moyens de convergence obtenus avec les différents taux de mutation. Outre les taux de mutation de 50 % et de 70 % qui ressortent du lot, la convergence s'effectue de façon assez similaire. Le taux de mutation de 50 % peine initialement à converger vers une solution optimale, mais débloque à partir de la 36ᵉ génération. Par contre, le taux de mutation de 70 % semble problématique dans la mesure où il a tendance à diverger à partir de la 32ᵉ génération. Ce comportement ne semble cependant pas se traduire à un taux de mutation de 80 % puisque celui-ci converge assez rapidement.

Pour l'optimisation avec amorçage, la convergence s'effectue de façon très similaire avec tous les taux de mutation, sauf 80 % où la solution moyenne proposée est supérieure à la moyenne.

La Figure 4.14 présente les résultats de l'évaluation des modèles de langage sur le corpus d'évaluation. Pour le cas de l'optimisation sans amorçage, les résultats suivent à peu près la forme d'une cloche, avec des résultats qui s'améliorent à 20 %, mais se dégradent à 30 % pour ensuite
s'améliorer à partir de 60 %. Encore une fois, ces résultats nous semblent un peu contre-intuitifs : nous nous attendions à une dégradation de performance proportionnelle à l'augmentation du taux de mutation. Nous obtenons donc de meilleurs résultats entre 60 % et 80 %.

L'optimisation avec amorçage pour sa part produit des résultats plus ou moins stables avec une forte croissance à 80 % qui corroborent le comportement observé et ce à quoi nous nous attendions comme résultat.
<figure><img src="image_25.png" /><figcaption>Figure 4.14 : Convergence moyenne suite à 25 simulations Monte-Carlo de l'optimisation par AG : (a) représente la convergence moyenne pour un taux de mutation de 10 % à 80 % sans amorçage. (b) représente la convergence moyenne pour un taux de mutation de 10 % à 80 % avec amorçage.</figcaption></figure>

Finalement, le Tableau 4.6 présente un résumé des résultats obtenus. Les meilleurs résultats sont obtenus, en moyenne, avec un taux de mutation de 70 % pour l'optimisation sans amorçage, ce qui
<figure><img src="image_26.png" /><figcaption>Figure 4.15 : Résultats de l'évaluation des modèles de langage obtenus avec différent taux de croisement pour la fonction de croisement arithmétique.</figcaption></figure>

correspond plus ou moins à ce que nous avons observé dans le Tableau 4.4. Les résultats de l'optimisation avec amorçage semble privilégier, en moyenne, un taux de mutation de 40 %.
Globalement, les résultats correspondent à ceux obtenus section 4.4.6 où nous avions utilisé un taux de mutation de 20 %.

<table><caption>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.</caption><thead><tr><th rowspan="2">Taux de mutation</th><th colspan="3">Perplexité (mutation)</th><th colspan="3">Perplexité (mutation+EM)</th></tr><tr><th>Moyenne</th><th>Min</th><th>Max</th><th>Moyenne</th><th>Min</th><th>Max</th></tr></thead><tbody><tr><td>10 %</td><td>204,248</td><td>170,586</td><td>322,195</td><td>171,632</td><td>171,089</td><td>173,373</td></tr><tr><td>20 %</td><td>194,898</td><td><strong>170,195</strong></td><td>241,844</td><td>171,560</td><td>171,162</td><td><strong>172,31</strong></td></tr><tr><td>30 %</td><td>204,386</td><td>170,754</td><td>316,561</td><td>171,710</td><td>171,2</td><td>172,865</td></tr><tr><td>40 %</td><td>207,109</td><td>171,123</td><td>451,805</td><td><strong>171,532</strong></td><td>171,257</td><td>172,368</td></tr><tr><td>50 %</td><td>205,540</td><td>170,291</td><td>261,271</td><td>171,714</td><td>171,254</td><td>173,049</td></tr><tr><td>60 %</td><td>193,135</td><td>170,998</td><td>276,066</td><td>171,666</td><td>171,092</td><td>172,615</td></tr><tr><td>70 %</td><td><strong>192,919</strong></td><td>170,288</td><td><strong>237,890</strong></td><td>171,681</td><td>171,319</td><td>173,129</td></tr><tr><td>80 %</td><td>193,258</td><td>170,45</td><td>355,380</td><td>171,985</td><td><strong>171,01</strong></td><td>177,189</td></tr></tbody></table>

### 4.4.4 Paramètres de l'optimisation par algorithmes génétiques

Pour l'optimisation par algorithmes génétiques, nous utilisons l'utilitaire d'algorithmes génétiques de l'Optimization Toolbox de Matlab [115].

Les paramètres utilisés pour nos expériences ont été soit déduits empiriquement (fonction de sélection), soit en se basant sur la documentation fournie par MathWorks [109] et le guide disponible à la page 50 de Simon [108] et en utilisant notre expérience, paramètres qui sont très similaires à ceux que nous avons obtenus de façon empirique dans la section précédente.

Le Tableau 4.7 résume les paramètres que nous avons modifiés ainsi que leurs valeurs respectives.
<table><caption>Tableau 4.7 : Paramètres significatifs utilisés pour l'optimisation par algorithme génétique.</caption><thead><tr><td>Paramètre</td><td>Description</td><td>Valeur</td></tr></thead><tbody><tr><td>PopulationSize</td><td>Nombre d'individus</td><td>70</td></tr><tr><td>CreationFcn</td><td>Fonction de création d'individus</td><td>@gacreationuniform</td></tr><tr><td>MutationFcn</td><td>Fonction de mutation</td><td>@mutationadaptfeasible</td></tr><tr><td>CrossoverFcn</td><td>Fonction de croisement</td><td>@crossoverarithmetic</td></tr><tr><td>SelectionFcn</td><td>Fonction de sélection</td><td>@selectiontournament (tournoi à 6 individus)</td></tr><tr><td>CrossoverFraction</td><td>Pourcentage des individus qui sont le fruit d'un croisement</td><td>0,70</td></tr><tr><td>EliteCount</td><td>Nombre d'élites retenus</td><td>3</td></tr><tr><td>FitnessScalingFcn</td><td>Fonction de mise à l'échelle de la fonction de coût</td><td>@fitscalingrank</td></tr><tr><td>FunctionTolerance</td><td>Changement minimum constant considéré avant que l'algorithme termine.</td><td>0,001</td></tr></tbody></table>

### 4.4.5 Paramètres de l'optimisation par essais particuliers

Pour l'optimisation par essais particuliers, nous avons utilisé la librairie [116] et choisi nos paramètres (Tableau 4.8) selon la liste de choix de paramètres proposés dans le rapport technique de Pedersen [117]. Ceux-ci ont été obtenus de façon empirique et visent à permettre aux chercheurs de rapidement choisir des paramètres leur permettant d'obtenir rapidement de bons résultats.

<table><caption>Tableau 4.8 : Paramètres significatifs utilisés pour l'optimisation par essais particuliers.</caption><thead><tr><td>Paramètre</td><td>Valeur</td></tr></thead><tbody><tr><td>AccelerationFcn</td><td>psoiterate</td></tr><tr><td>CognitiveAttraction φ<sub>1</sub></td><td>1,6319</td></tr><tr><td>SocialAttraction φ<sub>2</sub></td><td>0,6239</td></tr><tr><td>PopulationSize</td><td>70</td></tr><tr><td>StallGenLimit</td><td>10</td></tr></tbody></table>
### 4.4.6 Fonction objective

Nous utilisons comme fonction objective, pour les deux approches d'optimisation, AG et PSO, la mesure de perplexité du modèle de langage par rapport à un corpus de développement : un corpus, souvent tiré d'un plus large corpus, strictement utilisé pour l'optimisation des paramètres.

Rappelons que selon l'équation (2,58), la perplexité d'un texte $T = w_1, ..., w_N$ se mesure comme suit :

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

Le choix de la perplexité comme fonction objective est justifié par son faible coût computationnel comparativement à une évaluation complète utilisant le score obtenu par la RAP.

### 4.4.7 Résultats

#### 4.4.7.1 Optimisation sans amorçage

Nos résultats, illustrés par la Figure 4.16 et la Figure 4.17, démontrent que l'optimisation par essais particulaires converge vers une solution potentielle beaucoup plus rapidement en moyenne que l'optimisation par algorithmes génétiques. Nous observons aussi que l'optimisation par la méthode de Powell explore l'espace de recherche de façon beaucoup plus erratique. Notons par ailleurs que nous avons filtré les figures 4.15 (b) et 4.16 (b) afin d'éliminer le bruit causé par les solutions hors bornes proposées par la méthode de Powell.

Plus spécifiquement, la Figure 4.17 nous permet de constater les grandes différences en termes de déviation standard entre les différentes méthodes d'optimisation. L'OEP converge en moyenne de façon beaucoup plus stable que l'optimisation par AG et par méthode de Powell. Par contre, bien que l'optimisation par AG produise une moins grande déviation standard en moyenne que la méthode de Powell lors de la phase d'optimisation, nous verrons plus tard, qu'en moyenne, que l'AG converge vers des solutions moins optimales que les deux autres algorithmes d'optimisation.
<figure><img src="image_27.png" /><figcaption>Figure 4.16 : Convergence moyenne sur 55 simulations de Monte-Carlo de la méthode de Powell vers une solution et où les barres verticales représentent la déviation standard. (a) illustre la convergence originale tandis que (b) filtre les solutions hors normes obtenues par l'algorithme de Powell.</figcaption></figure>

La méthode de Powell quant à elle, mise en évidence dans la Figure 4.16, nécessite en moyenne 450 itérations avant de converger vers une solution. Nous constatons d'ailleurs que nous n'obtenons pas de solutions potentiellement correctes avant environ 350 itérations. La courbe très «bruitée» de l'optimisation moyenne de la méthode de Powell résulte de la façon dont
Évaluation et comparaison de la performance d’algorithmes évolutionnaires pour l’optimisation
des poids d’interpolation

l’algorithme est mis en œuvre dans SciPy [118] et qui ne lui permet pas de prendre compte des
bornes pour les poids d’interpolation ainsi que des contraintes. Nous pénalisons donc sévèrement

<figure><img src="image_28.png" /><figcaption>Figure 4.17 : Convergence moyenne sur 55 simulations de Monte-Carlo des différents algorithmes d'optimisations avec amorçage sur le corpus de développement. (a) illustre la convergence originale tandis que (b) filtre les solutions hors normes obtenues par l'algorithme de Powell. Les barres verticales indiquent la déviation standard.</figcaption></figure>
toute solution proposée où les poids d'interpolation $\lambda_i < 0$ ou $\lambda_i > 1$ ou encore $\sum \lambda_i > 1$.
Malgré cette limitation, nous avons tout de même opté pour l'outil SciPy en raison de sa très grande
adoption par la communauté scientifique due à sa robustesse, sa flexibilité, ses fonctionnalités et
sa rapidité. En effet, SciPy est une couche logicielle mince permettant de faire appel à plusieurs
librairies scientifiques implémentées en Fortran et en C qui ont fait leurs preuves au fil du temps.

4.4.7.2 Optimisation avec amorçage par Maximisation de l'espérance

L'initialisation de la population peut avoir un impact majeur sur la capacité des algorithmes évolutionnaires à rapidement converger vers une solution et qu'elle soit optimale. Une technique populaire dans le contexte de l'optimisation de systèmes complexes est l'utilisation de connaissances expertes. Cette technique consiste à faire appel à un expert de domaine et utiliser ses connaissances du domaine pour initialiser la population. Nous simulerons cet expert en générant un individu qui représente une solution convenable obtenue par l'algorithme d'optimisation espérance-maximisation.

Nous avons utilisé la suite logicielle SRILM [93] avec sa commande compute-best-mix pour obtenir un point de départ informatif. Cette commande utilise l’algorithme espérance-maximisation pour calculer les poids d’interpolation optimaux des modèles de langage. L’avantage principal de l’algorithme espérance-maximisation est sa rapidité d’exécution, mais au prix d’une solution généralement sous-optimale.

Nous avons donc procédé à une première optimisation des poids d'interpolation à l'aide de l'algorithme espérance-maximisation et utilisé les poids obtenus comme point de départ (amorçage) pour nos trois algorithmes d'optimisation.

La Figure 4.17 présente les résultats moyens obtenus avec amorçage pour chaque algorithme d'optimisation sur 55 simulations de Monte-Carlo, à l'exception de la méthode de Powell qui elle n'a été exécutée qu'une seule fois dû à sa nature heuristique.

La Figure 4.17 quant à elle offre un portrait comparatif de l'optimisation des algorithmes évolutionnaires avec et sans amorçage.

La méthode de Powell voit elle aussi sa vitesse de convergence grandement améliorée. Nous pouvons maintenant obtenir une solution en approximativement 100 générations. Par ailleurs,
Évaluation et comparaison de la performance d’algorithmes évolutionnaires pour l’optimisation des poids d’interpolation

comme la méthode de Powell réalise des minimisations unidimensionnelles en suivant des directions conjuguées, nous aurons toujours le même résultat à partir d’un même point de départ puisque la tangente calculée sera toujours la même. Cela est dû au fait que l’on varie seulement une variable à la fois et que l’on garde seulement la valeur qui a eu le plus d’impact positif sur la solution. Cela explique aussi pourquoi nous n’avons pas à effectuer de simulations de Monte-Carlo

<figure><img src="image_29.png" /><figcaption>Figure 4.18 : Comparaison de la vitesse de convergence entre (a) l'optimisation par algorithme génétique avec et sans amorçage (b) l'optimisation par essais particulaires avec et sans amorçage.</figcaption></figure>
pour la méthode de Powell avec amorçage. Nous avons tout de même choisi de l'inclure à la Figure 4.17 comme référence.

L'algorithme génétique converge lui aussi beaucoup plus rapidement : en moyenne en 30 générations contre 59 en moyenne sans amorçage. Nous verrons aussi au Tableau 4.9 que la perplexité de la solution moyenne des AG est grandement réduite en termes de perplexité et d'écart-type.

Finalement, comme nous avons pu le constater par les Figures 4.16 et 4.17, l'algorithme d'OEP converge aussi plus rapidement : 41 générations en moyenne comparativement à 47 générations en moyenne sans amorçage.

Nous croyons que la stratégie de recherche de l'optimisation par essais particuliers lui permet de garantir un niveau de robustesse beaucoup plus élevé par rapport aux variations du point de départ que l'algorithme génétique qui privilégie essentiellement une exploration (large) de l'espace de recherche basé sur les mutations.

### 4.4.7.3 Évaluation de la perplexité des modèles de langage

Dans cette section nous présentons les résultats de l'évaluation des modèles de langage obtenus par chaque algorithme. Les modèles de langage ont été évalués sur le corpus d'évaluation du Wall Street Journal-based Continuous Speech Recognition (CSR) Corpus Phase II (WSJ1) [92]. Les ensembles utilisés pour l'évaluation sont les suivants :

* Hub 1 (base de référence WSJ lue),

* Spoke 1 (adaptation des modèles de langage),

* Spoke 2 (indépendance du domaine)

* Spoke 9 (diction spontanée WSJ)

Cela nous donne un total de 23 000 mots dans 1285 phrases sans filtrage des phrases contenant des mots hors vocabulaire. Le vocabulaire (fermé) utilisé est le vocabulaire WSJ standard de 20 000 mots. Le taux de mots hors vocabulaire est de 5,64 %.

Comme la Figure 4.19 et le Tableau 4.9 l'illustrent, l'algorithme d'optimisation qui performe le moins bien en moyenne est l'algorithme génétique sans amorçage. Par contre l'AG obtient le meilleur score, soit une perplexité de 170.141 sur le corpus d'évaluation. En contrepartie, c'est
Évaluation et comparaison de la performance d'algorithmes évolutionnaires pour l'optimisation des poids d'interpolation

<table><caption>Tableau 4.9 : Sommaire des résultats de l'évaluation des modèles de langage optimisés selon les différents algorithmes d'optimisation et évalués sur l'ensemble de test WSJ1 Hub 1 Spoke 1, 2 et 9.</caption><thead><tr><th rowspan="2">Algorithme d'optimisation</th><th colspan="3">Perplexité</th></tr><tr><th>Moyenne</th><th>Min</th><th>Max</th></tr></thead><tbody><tr><td>WB</td><td>323,26</td><td>-</td><td>-</td></tr><tr><td>KN</td><td>232,047</td><td>-</td><td>-</td></tr><tr><td>AG</td><td>194,587</td><td><strong>170,141</strong></td><td>303,549</td></tr><tr><td>AG + EM</td><td>171,650</td><td>170,904</td><td>175,271</td></tr><tr><td>OEP</td><td>171,596</td><td>171,331</td><td>173,536</td></tr><tr><td>OEP + EM</td><td>171,411</td><td>171,296</td><td>171,852</td></tr><tr><td>Powell</td><td>171,767</td><td>171,279</td><td>175,153</td></tr><tr><td>Powell + EM</td><td><strong>171,399</strong></td><td>171,399</td><td><strong>171,399</strong></td></tr></tbody></table>

aussi l'algorithme génétique qui nous donne la solution la moins performante : une perplexité maximale de 303,549. Lorsque l'algorithme génétique est combiné avec une phase d'amorçage, nous obtenons en moyenne des solutions équivalentes aux autres algorithmes d'optimisation.

Outre l'algorithme génétique sans amorçage qui sort de l'ordinaire, les autres algorithmes d'optimisation convergent en moyenne vers des solutions très similaires, avec ou sans amorçage.

L'avantage principal de l'implémentation de l'amorçage basé sur l'algorithme espérance-maximisation est une réduction considérable du temps moyen de convergence de chaque algorithme d'optimisation ainsi qu'une réduction de la variation des solutions proposées.

Ces résultats sont cohérents avec ceux de la littérature : les algorithmes (stochastiques) d'optimisation auront tendance à converger vers une solution optimale plus rapidement. Par ailleurs, lorsque l'on intègre des connaissances spécifiques aux problèmes dans nos algorithmes de recherche, nous pouvons nous attendre à obtenir de meilleurs résultats en moyenne. Finalement, comme nous cherchons non seulement à obtenir une solution optimale, mais aussi une solution optimale rapidement, l'utilisation de l'amorçage devient une étape cruciale.

Nous calculons la vitesse de convergence des différents algorithmes d'optimisation en nous basant sur le nombre total d'appels de la fonction objective. Cette méthode de calcul a été privilégiée suite
au profilage des différents algorithmes d'optimisation et où nous avons observé qu'environ 99%
du temps d'exécution est représenté par le calcul de la fonction objective. La méthode de Powell
sans amorçage avec une moyenne de 3500 appels (500 itérations * 7 appels par itération) avant
l'atteinte de notre condition d'arrêt est la plus lente. L'algorithme d'OEP demande en moyenne au
moins 2870 appels, ce qui le rend près de 20 % plus rapide que la méthode de Powell. Par ailleurs,
contrairement à la méthode de Powell qui est plus séquentielle par sa nature, l'OEP, et l'AG
peuvent faire appel à un parallélisme plus fin. Le plancher s'établit à un processus par individu
versus 1 processus par variable par itération. Pour notre ordinateur d'évaluation, qui compte 24
cœurs logiques, cela revient à environ 120 appels totaux par processeur pour l'optimisation par
essais particulaires. Nous obtenons alors une solution beaucoup plus rapidement avec
l'optimisation par essais particulaires. L'AG avec amorçage demandera quant à lui en moyenne
un total de 88 appels par processeur (environ 2100 appels de fonction), ce qui est encore plus
rapide que la méthode de Powell puisque nous pouvons obtenir un niveau supérieur de parallélisme
avec l'AG<fnref n="32" />.

Un des principaux avantages des algorithmes évolutionnaires d'optimisation est qu'ils permettent
de réduire le nombre de bacs à interpoler parallèlement à la recherche d'une solution optimale
(réduction de la perplexité). La Figure 4.19 présente un portrait global de la capacité de chaque
algorithme à réduire le nombre de bacs.

On remarque que l'AG propose une plus grande variété de solutions potentielles et qui réduisent
le plus le nombre de bacs en moyenne (5 bacs en moyenne). C'est aussi l'algorithme qui propose
le plus petit nombre de bacs à interpoler.

L'OEP propose en moyenne des solutions comptant entre 5 et 6 bacs à interpoler et certaines
solutions proposées par l'algorithme d'optimisation peuvent réduire jusqu'à 4 le nombre de bacs
à interpoler.

Lorsque la phase d'amorçage est implémentée, les deux algorithmes évolutionnaires obtiennent en
moyenne la même réduction de bacs : entre 6 et 7 avec un minimum de 4 bacs pour l'optimisation

<footnote n="32">³² Notons que le nombre maximal de fils concurrents pour la méthode de Powell correspond au nombre de paramètres à optimiser. Pour les algorithmes évolutionnaires, le nombre maximal de fils concurrents (outre le parallélisme attribuable à la fonction objective choisie) correspond au nombre d'individus dans la population.</footnote>
Évaluation et comparaison de la performance d'algorithmes évolutionnaires pour l'optimisation des poids d'interpolation

par essais particulaires. Nous pensons que cela s'explique par le fait que point de départ soit beaucoup plus près de la solution optimale, ce qui réduit l'espace de recherche exploré.

<figure><img src="image_30.png" /><figcaption>Figure 4.19 : Résultats de l'évaluation des modèles de langage optimisés selon les différents algorithmes d'optimisation et évalués sur l'ensemble de tests WSJ1 Hub 1 Spoke 1, 2 et 9. La ligne représente la médiane, le marqueur (X) la moyenne et les barres verticales représentent la variabilité empirique des valeurs en dehors des quartiles. Les points représentent les valeurs hors-norme.</figcaption></figure>
La Figure 4.20 présente la relation observée entre le nombre de bacs interpolés avec le modèle de langage principal et la perplexité du modèle de langage optimisé.

Nous constatons encore une très grande variance pour l'AG. L'algorithme génétique est néanmoins en mesure de proposer une solution presque optimale avec quatre bacs (perplexité de 173.147). Les meilleurs résultats en moyenne sont obtenus avec 5 bacs. Cette figure nous permet d'ailleurs de constater que, contrairement aux autres algorithmes d'optimisation, l'AG converge de façon très variable et que l'algorithme produit des résultats qui sont faiblement et inversement corrélés au nombre de bacs (coefficient de corrélation *r* = -0.196 53).

L'optimisation par essais particuliers converge de façon beaucoup moins variable. Nous constatons une plus grande variation (proportionnellement) avec 4 bacs. Les résultats obtenus sont aussi plus (inversement) corrélés au nombre de bacs avec *r* = -0.294 41 et un coefficient de détermination *R*² = 0.221 05. Nous avons donc une faible corrélation qui est inverse au nombre de bacs : un nombre de bacs croissant aura un faible impact positif sur la perplexité du modèle de langage.

<figure><img src="image_31.png" /><figcaption>Figure 4.20 : Sommaire du nombre de bacs à interpoler obtenus par les différents algorithmes d'optimisation.</figcaption></figure>
<table><caption>Tableau 4.10 : Taux d'observation des bacs retenus pour les solutions obtenues par les différents algorithmes d'optimisation.</caption><thead><tr><th></th><th>d1</th><th>d2</th><th>d3</th><th>d4</th><th>d5</th><th>d6</th><th>d7</th></tr></thead><tbody><tr><td>GA</td><td>1</td><td>0,864</td><td>0,661</td><td>0,186</td><td>0,729</td><td>0,814</td><td>0,847</td></tr><tr><td>GA+EM</td><td>1</td><td>1</td><td>0,964</td><td>0,554</td><td>1,000</td><td>0,964</td><td>0,964</td></tr><tr><td>OEP</td><td>0,947</td><td>0,947</td><td>0,789</td><td>0,263</td><td>0,789</td><td>0,842</td><td>0,825</td></tr><tr><td>OEP+EM</td><td>1</td><td>0,982</td><td>0,964</td><td>0,655</td><td>0,982</td><td>0,982</td><td>0,964</td></tr></tbody></table>

Par ailleurs, globalement, les bacs les plus retenus (voir Tableau 4.10) sont d1 98,7 %, d2 94,8 %, d6 90 %, d7 90 %, d5 87,5 %, d3 84,5 % et d4 41,4 %. Il apparaît donc que les bacs d'une distance ontologique supérieure à 5 contribuent de façon significative à la performance obtenue du modèle de langage final.

Tel qu'observé à la Figure 4.19, l'amorçage réduit de façon très significative la variance de l'algorithme génétique. Son coefficient de corrélation passe à $r = -0,29738$. Le nombre de bacs a un impact légèrement plus important, mais il demeure néanmoins négligeable.

L'OEP voit principalement son coefficient de corrélation passer à $r = 0,04774$. L'amorçage fait donc en sorte que le nombre de bacs influence encore moins la solution finale obtenue.

Finalement, la Figure 4.21 nous permet d'observer pourquoi l'algorithme génétique sans amorçage obtient de moins bons résultats que les autres algorithmes d'optimisations. C'est l'algorithme qui couvre la plus grande surface dans l'espace de solution. Les résultats sont très fortement inversement corrélés au poids d'interpolation du modèle de langage primaire $\lambda_0 : r = -0,88334$ et $R^2 = 0,7803$. L'AG obtient de meilleurs résultats lorsque la solution proposée converge vers $0,6 < \lambda_0 < 0,7$, ce qui est consistant avec les résultats obtenus par les autres algorithmes d'optimisation et qui sont représentés par les points sur l'axe horizontal supérieur.

L'amorçage permet à l'AG d'intégrer des connaissances spécifiques aux problèmes dès la première génération, ce qui a pour effet de considérablement réduire sa dispersion dans l'espace de recherche. La tendance de l'AG à couvrir un plus grand espace de recherche lui permet d'ailleurs d'obtenir des solutions légèrement supérieures aux autres algorithmes d'optimisation. Nous observons maintenant une forte corrélation entre la valeur $\lambda_0$ et la perplexité du modèle de langage avec un coefficient $r = 0,89545$. De plus, la variation de perplexité pour des poids $\lambda_0$ très
<figure><img src="image_32.png" /><figcaption>**Figure 4.21** : Relation entre le nombre de bacs à interpoler obtenus par chaque algorithme et la perplexité telle qu'évaluée sur le corpus d'évaluation. (a) montre les résultats complets tandis que (b) montre les résultats sans l'algorithme génétique afin de mieux observer le comportement des autres algorithmes d'optimisation.</figcaption></figure>

similaires illustre bien que la perplexité soit aussi influencée par les poids d'interpolation des autres bacs ainsi que les bacs qui sont retenus par l'algorithme d'optimisation.

L'optimisation par essais particulaires obtient des résultats qui sont beaucoup plus centrés autour de $\lambda_0 = 0,658$. Comme les solutions obtenues par l'algorithme génétique, les solutions de l'OEP
sont aussi fortement corrélées à λ₀ avec un coefficient de corrélation *r* = 0,801 16. Nous notons cependant les données aberrantes aux points (0,665 812 ; 173,859) et (0,667 268 ; 173,558) qui illustrent la corrélation linéaire moyenne entre λ₀ et la perplexité du modèle de langage obtenu.

L'amorçage ressert encore plus les résultats obtenus par l'OEP. Un autre effet de l'amorçage est la réduction de l'influence du poids d'interpolation λ₀ sur la perplexité des modèles de langage obtenus. Le coefficient de corrélation passe à *r* = 0,568 85, une faible corrélation linéaire positive. La performance de la solution obtenue est donc plus dépendante ($R^2_{\lambda_0}$ = 0,323 59) des autres facteurs : $\lambda_{1+}$, choix des bacs.

Globalement, les meilleurs résultats sont obtenus entre 0,63 < λ₀ < 0,675 avec une tendance croissante de la perplexité à partir de λ₀ > 0,65. Notons d'ailleurs que le meilleur résultat obtenu, une perplexité de 170,149, à l'aide de l'algorithme génétique a été obtenu avec λ₀ = 0,574 19. Cela semble indiquer que d'autres variations des différents algorithmes, ou des paramètres différents, seraient potentiellement en mesure d'obtenir, en moyenne, des résultats supérieurs à ceux que nous avons obtenus.
<figure><img src="image_33.png" /><figcaption>Figure 4.22 : Relation entre le poids d’interpolation λ et la perplexité des modèles de langage obtenus lors de l’optimisation.</figcaption></figure>
## 4.5 Évaluation du taux d'erreur des mots

Tel que décrit à la section 4.4.7.3 ci-dessus, le corpus utilisé pour l'entrainement des modèles acoustiques et des modèles de langage et pour l'évaluation est le corpus Wall Street Journal-based Continuous Speech Recognition Phase II.

Le même dictionnaire que celui utilisé lors de l'évaluation de la perplexité, soit le dictionnaire WSJ à vocabulaire clos de 20 000 mots (taux de mots hors vocabulaire de 5,64 %), est utilisé pour l'évaluation.

La version 3.4.1 du logiciel HTK [119] a été utilisée pour la partie reconnaissance automatique de la parole.

Le taux d'erreur des mots (TEM), calculé selon l'équation (4.9), est utilisé pour comparer la performance des différents modèles de langage.

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

où
* O est le nombre d'omissions,
* S est le nombre de substitutions,
* I est le nombre d'insertions, et
* N est le nombre de mots dans la phrase originale.

L'entrainement des modèles acoustiques a été réalisé en suivant le protocole d'apprentissage proposé par Vertanen [120] avec une phase d'entrainement discriminatif additionnelle (critère Minimum Phone Error). Nos modèles acoustiques sont entrainés sur l'ensemble complet d'entrainement du corpus WSJ1 et utilisent l'ensemble de 40 phonèmes du dictionnaire CMU [121]. Les modèles obtenus pour le décodage acoustique sont des triphones « extra-mot » (cross-word) à état liés (tied-state) à 32 gaussiennes par état et 64 pour le modèle de silence. Ces modèles sont représentés par un vecteur 39-dimensionnel de Coefficients Cepstraux à Fréquence de Mel (Mel Frequency Cepstrum Coefficient) avec l'énergie, éq. (4.10), du signal, le delta, éq. (4.11), (« dynamique » du signal) et l'accélération, éq. (4.12):
$$E = \log \sum_{n=1}^{N} s_n^2 \qquad (4.10)$$

$$d_t = \frac{\sum_{\theta=1}^{\Theta} (c_{t+\theta} - c_{t-\theta})}{2 \sum_{\theta=1}^{\Theta} \theta^2} \qquad (4.11)$$

$$a_t = \frac{\sum_{\theta=1}^{\Theta} (d_{t+\theta} - d_{t-\theta})}{2 \sum_{\theta=1}^{\Theta} \theta^2} \qquad (4.12)$$

où $\{s_n, n = 1, N\}$ représente le nième échantillon de la parole, $c_t$ représente un coefficient statique de la parole à l'instant $t$, $d_t$ est le coefficient delta à l'instant $t$, $a_t$ est le coefficient d'accélération à l'instant $t$, et $\Theta$ est la taille de la fenêtre et où $\Theta = 3$ dans notre cas.

L'outil HDecode [119] est utilisé pour l'évaluation de la RAP avec les paramètres suivants pour la largeur du faisceau d'élagage (pruning beam width), de la pénalité d'insertion de mot et de l'échelle du modèle de langage<fnref n="33" /> : 220, -4 et 15, sont utilisés pour l'évaluation de la RAP.

Comme l'évaluation par décodage complet de la RAP est une opération particulièrement lente, nous avons d'abord procédé à un « rescoring<fnref n="34" /> » (réassignation des poids de transition, ou renotation) d'un réseau des 100 énoncés les plus probables générés à l'aide d'un bigramme lissé à l'aide de l'algorithme de Witten-Bell afin d'identifier les meilleurs modèles obtenus par les différents algorithmes d'optimisation.

Comme l'illustre le Tableau 4.11, les meilleurs résultats (préliminaires) obtenus par rescoring sont, en moyenne, obtenus à l'aide de l'optimisation par l'algorithme génétique. Pour leur part, les autres algorithmes d'optimisation produisent en moyenne des résultats équivalents et légèrement supérieurs à ceux obtenus par le modèle de langage lissé à l'aide de la méthode Kneser-Ney. Nous soulignerons aussi le fort taux d'erreur des phrases, frôlant le 100 %, qui résulte du haut taux

<footnote n="33">³³ Le détail des paramètres et de leur signification sont documentés dans [122].</footnote>

<footnote n="34">³⁴ Nous privilégierons l'utilisation du terme rescoring dans ce document puisque le terme est plus succinct que sa traduction et capture mieux, à notre avis, le concept.</footnote>
<table><caption>Tableau 4.11 : Moyennes des résultats, exprimés en pourcentages, obtenus lors de l'évaluation de la performance de la reconnaissance automatique de la parole des modèles de langage par « rescoring » pour les divers algorithmes d'optimisation comparés aux trigrammes de bases lissées à l'aide des algorithmes Witten-Bell et Kneser-Ney.</caption><thead><tr><th>Modèle</th><th>Corr.</th><th>Sub.</th><th>Supp.</th><th>Ins.</th><th>Err</th><th>Err Ph.</th></tr></thead><tbody><tr><td>WB</td><td>49,90</td><td>40,70</td><td>9,40</td><td>6,10</td><td>56,30</td><td>99,70</td></tr><tr><td>KN</td><td><strong>50,80</strong></td><td>39,40</td><td>9,70</td><td>5,80</td><td>55,00</td><td>99,70</td></tr><tr><td>Powell</td><td>50,28</td><td>39,55</td><td>10,19</td><td>5,40</td><td>55,11</td><td>99,70</td></tr><tr><td>Powell + EM</td><td>50,28</td><td>39,55</td><td>10,19</td><td>5,40</td><td>55,11</td><td>99,70</td></tr><tr><td>AG</td><td>49,95</td><td><strong>38,89</strong></td><td><strong>11,15</strong></td><td><strong>4,65</strong></td><td><strong>54,69</strong></td><td><strong>99,58</strong></td></tr><tr><td>AG + EM</td><td>50,25</td><td>39,54</td><td>10,20</td><td>5,40</td><td>55,13</td><td>99,70</td></tr><tr><td>OEP</td><td>50,24</td><td>39,54</td><td>10,23</td><td>5,38</td><td>55,13</td><td>99,70</td></tr><tr><td>OEP + EM</td><td>50,21</td><td>39,60</td><td>10,20</td><td>5,40</td><td>55,16</td><td>99,70</td></tr></tbody></table>

d'erreur des mots obtenus et qui fait en sorte que presque toutes les phrases reconnues contiennent au moins une erreur.

Par ailleurs, comme observée dans la section précédente et illustrée par la Figure 4.23, l'optimisation par algorithme génétique produit les résultats ayant la plus grande variance, tandis que les algorithmes d'optimisation par essais particulaires et par l'algorithme de Powell obtiennent des solutions beaucoup plus stables.

Nous avons par la suite procédé à une évaluation de la corrélation entre la perplexité du modèle de langage et sa performance en termes de taux d'erreur de mots. La Figure 4.24 présente la relation entre la perplexité des modèles de langage obtenus par les différents algorithmes d'optimisation et le TEM. Puisque nous avions précédemment procédé à l'évaluation de l'effet des divers paramètres d'optimisation pour les algorithmes génétiques, nous avons choisi d'inclure tous les résultats dans l'analyse. Cela nous permet de bien caractériser la relation potentielle entre la perplexité et le TEM.

Comme nous pouvons l'observer pour l'algorithme génétique, une augmentation de la perplexité du modèle de langage influence faiblement (coefficient de corrélation de 0,037) de façon négative le taux d'erreur des mots. La tendance est relativement plus marquée pour l'algorithme génétique avec amorçage avec un coefficient de corrélation de 0,288. La tendance s'inverse pour
<figure><img src="image_34.png" /><figcaption>Figure 4.23. Résultats de l'évaluation des modèles de langage optimisés selon les différents algorithmes d'optimisation et évalués sur l'ensemble de test WSJ1 Hub 1, Spoke 1, 2 et 9. La ligne représente la médiane, le marqueur (X) la moyenne et les barres verticales représentent la variabilité empirique des valeurs en dehors des quartiles. Les points représentent les valeurs hors norme.</figcaption></figure>

l'optimisation par essais particuliers où nous constatons plutôt une tendance à l'amélioration du taux d'erreur lorsque la perplexité augmente (coefficient de corrélation de -0,296). Nous devons toutefois être prudent dans notre interprétation de ces résultats puisque l'AG avec amorçage et l'OEP sont beaucoup plus circoncis dans leur variation de perplexité que l'algorithme génétique sans amorçage. Le portrait est similaire pour le cas de l'OEP avec amorçage (coefficient de corrélation de -0,3189) où la variation de perplexité est encore plus bornée. L'optimisation par algorithme de Powell poursuit la même tendance avec un coefficient de corrélation de -0,198. Finalement, lorsque nous analysons le portrait global, nous pouvons tout de même constater une faible tendance, un peu contre-intuitive, de l'amélioration du TEM proportionnelle à une augmentation de la perplexité (coefficient de corrélation de -0,264). Nous sommes d'avis que ce résultat un peu contre-intuitif est potentiellement dû au fait que nous avons procédé à une évaluation de la reconnaissance automatique de la parole par rescoring du réseau des N-meilleurs résultats plutôt que par décodage complet.
<figure><img src="image_35.png" /><figcaption>Figure 4.24 : Taux d'erreur des mots versus perplexité. Notons que nous avons inclus, dans la sous-figure globale, la ligne de tendance linéaire du système.</figcaption></figure>
Après avoir identifié les meilleures solutions proposées par chaque algorithme, nous avons procédé à la reconnaissance automatique de la parole complète (full decoding). Les résultats obtenus sont résumés dans le Tableau 4.12 :. Nous pouvons constater que les résultats obtenus par les différents algorithmes d'optimisation s'équivalent en termes de performance. Cependant, comme nous l'avons expliqué précédemment, l'avantage des algorithmes évolutionnaires réside dans leur rapidité (parallélisme) et leur capacité à réduire le nombre de bacs pour l'interpolation (diminution de la complexité) tout en maintenant une précision équivalente à l'algorithme de Powell. Nous notons une diminution relative moyenne d'environ 14 % du taux d'erreur des mots ainsi qu'une augmentation relative d'environ 4,2 % du taux de phrases correctement reconnues.

Afin de déterminer si les améliorations obtenues sont statistiquement significatives, nous avons procédé à l'analyse de la variance des différents modèles de langage obtenus. Ces résultats sont résumés dans le Tableau 4.13 et ont été obtenus grâce à l'outil SCTK [123]. Comme nous pouvons le constater, tous les algorithmes d'optimisation ont produit des modèles de langage avec lissage ontologique ayant une performance supérieure ($p < 0.001$) aux modèles de base lissés à l'aide des algorithmes de Witten-Bell et Kneser-Ney respectivement. Nous pouvons donc conclure que pour ce problème particulier d'optimisation qu'il n'y a pas de différence significative de performance entre les solutions proposées par l'algorithme de Powell et les algorithmes évolutionnaires. Cependant, les algorithmes évolutionnaires nous permettent plus facilement de réduire la complexité de la solution proposée que l'algorithme de Powell.

<table><caption>Tableau 4.12 : Résumé des résultats obtenus par les divers modèles de langage suite au décodage complet.</caption><thead><tr><th>Modèle</th><th>Corr.</th><th>Sub.</th><th>Supp.</th><th>Ins.</th><th>Err</th><th>Err Ph.</th></tr></thead><tbody><tr><td>WB</td><td>75,4</td><td>19,4</td><td>5,2</td><td>3,1</td><td>27,7</td><td>77,3</td></tr><tr><td>KN</td><td>74,2</td><td>19,3</td><td>6,5</td><td>2,5</td><td>28,3</td><td>77,5</td></tr><tr><td>Powell</td><td><strong>78,6</strong></td><td><strong>16,6</strong></td><td><strong>4,8</strong></td><td>2,5</td><td>23,9</td><td><strong>76,2</strong></td></tr><tr><td>Powell + EM</td><td><strong>78,6</strong></td><td><strong>16,6</strong></td><td><strong>4,8</strong></td><td>2,5</td><td>23,9</td><td><strong>76,2</strong></td></tr><tr><td>AG</td><td>78,4</td><td>16,7</td><td><strong>4,8</strong></td><td><strong>2,4</strong></td><td>24</td><td>76,3</td></tr><tr><td>AG + EM</td><td><strong>78,6</strong></td><td><strong>16,6</strong></td><td><strong>4,8</strong></td><td>2,5</td><td><strong>23,8</strong></td><td><strong>76,2</strong></td></tr><tr><td>OEP</td><td><strong>78,6</strong></td><td><strong>16,6</strong></td><td><strong>4,8</strong></td><td><strong>2,4</strong></td><td><strong>23,8</strong></td><td>76,3</td></tr><tr><td>OEP + EM</td><td><strong>78,6</strong></td><td><strong>16,6</strong></td><td><strong>4,8</strong></td><td><strong>2,4</strong></td><td><strong>23,8</strong></td><td>76,3</td></tr></tbody></table>
<table><caption>Tableau 4.13 : Comparaison statistique selon l'analyse de la variance de la performance des différents modèles de langage. Le symbole ~ indique que les modèles s'équivalent statistiquement.</caption><thead><tr><th>Modèle</th><th>KN</th><th>AG</th><th>OEP</th><th>AG+EM</th><th>OEP+EM</th><th>POW</th><th>POW+EM</th></tr></thead><tbody><tr><td>WB</td><td>~<br>p &lt; 0,001</td><td>AG<br>p &lt; 0,001</td><td>OEP<br>p &lt; 0,001</td><td>AG + EM<br>p &lt; 0,001</td><td>OEP + EM<br>p &lt; 0,001</td><td>POW<br>p &lt; 0,001</td><td>POW<br>p &lt; 0,001</td></tr><tr><td>KN</td><td></td><td>AG<br>p &lt; 0,001</td><td>OEP<br>p &lt; 0,001</td><td>AG + EM<br>p &lt; 0,001</td><td>OEP + EM<br>p &lt; 0,001</td><td>POW<br>p &lt; 0,001</td><td>POW<br>p &lt; 0,001</td></tr><tr><td>AG</td><td></td><td></td><td>~<br>p &lt; 0,001</td><td>~<br>p &lt; 0,001</td><td>~<br>p &lt; 0,001</td><td>~<br>p &lt; 0,001</td><td>~<br>p &lt; 0,001</td></tr><tr><td>OEP</td><td></td><td></td><td></td><td>~<br>p &lt; 0,001</td><td>~<br>p &lt; 0,001</td><td>~<br>p &lt; 0,001</td><td>~<br>p &lt; 0,001</td></tr><tr><td>AG+EM</td><td></td><td></td><td></td><td></td><td>~<br>p &lt; 0,001</td><td>~<br>p &lt; 0,001</td><td>~<br>p &lt; 0,001</td></tr><tr><td>OEP+EM</td><td></td><td></td><td></td><td></td><td></td><td>~<br>p &lt; 0,001</td><td>~<br>p &lt; 0,001</td></tr><tr><td>POW</td><td></td><td></td><td></td><td></td><td></td><td></td><td>~<br>p &lt; 0,001</td></tr></tbody></table>

Le Tableau 4.15 présente un résumé de la perplexité des modèles de langage qui ont obtenu les meilleurs résultats lors de l'évaluation de la RAP. Nous pouvons constater que tous les modèles de langage ontologiques optimisés ont une perplexité inférieure aux modèles de références.

Finalement, le Tableau 4.14 présente le taux de réduction du TEM observé pour une diminution d'un bit de l'entropie du modèle de langage par rapport au modèle de base lissé à l'aide de l'algorithme Witten-Bell. Nous obtenons donc une réduction moyenne du taux d'erreur des mots de 3,458 % par bit d'entropie croisée en moins du modèle de langage comparativement au modèle de base lissé par l'algorithme Witten-Bell et utilisé pour l'interpolation des bacs ontologiques. Ces résultats, bien que légèrement inférieurs à ceux obtenus par Goodman [78] (réduction d'environ 4,9 % par diminution de bit d'entropie croisée) demeurent tout de même significatifs, mais illustrent bien les limites et difficultés de la modélisation du langage pour l'amélioration de la reconnaissance automatique de la parole : puisque nous ne pouvons avoir des modèles de langage ayant seulement 1 bit d'entropie (ils seraient seulement valables pour le corpus de test ou
<table><caption>Tableau 4.15 : Récapitulatif des meilleurs résultats obtenus pour la reconnaissance automatique de la parole et la relation de ces résultats avec la perplexité et l'entropie croisée du modèle de langage obtenu.</caption><thead><tr><th></th><th>WB</th><th>KN</th><th>Powell</th><th>Powell + EM</th><th>AG</th><th>AG + EM</th><th>OEP</th><th>OEP + EM</th></tr></thead><tbody><tr><th>TEM (%)</th><td>27,7</td><td>28,3</td><td>23,9</td><td>23,9</td><td>24</td><td>23,8</td><td>23,8</td><td>23,8</td></tr><tr><th>PPL</th><td>323,26</td><td>232,05</td><td>171,42</td><td>171,4</td><td>181,28</td><td>171,32</td><td>171,41</td><td>171,53</td></tr><tr><th>Entropie (bits)</th><td>8,34</td><td>7,86</td><td>7,42</td><td>7,42</td><td>7,50</td><td>7,42</td><td>7,42</td><td>7,42</td></tr></tbody></table>

<table><caption>Tableau 4.14 : Diminution obtenue du taux d'erreur des mots en % par réduction d'un bit d'entropie du modèle de langage.</caption><thead><tr><th></th><th>Powell</th><th>Powell + EM</th><th>AG</th><th>AG + EM</th><th>OEP</th><th>OEP + EM</th></tr></thead><tbody><tr><th>Réduction TEM (%) par bit d'entropie croisée</th><td>3,478 %/bit</td><td>3,478 %/bit</td><td>3,088 %/bit</td><td>3,572 %/bit</td><td>3,569 %/bit</td><td>3,566 %/bit</td></tr></tbody></table>

d'entrainement), il est éventuellement nécessaire d'utiliser d'autres techniques pour réduire le taux d'erreur absolu (d'un signal acoustique « parfait ») comme la modélisation sémantique, pragmatique, logique, voire philosophique.

## 4.6 Discussion

Dans ce chapitre, nous avons comparé la performance de différents algorithmes dans le contexte de l'optimisation des poids d'interpolation des modèles de langage pour les *Bin-Based Ontologically Smoothed langage models* [86] et avons démontré que les algorithmes évolutionnaires sont en mesure de trouver des solutions optimales plus rapidement, tout en préservant la même précision, que la méthode de Powell qui est couramment utilisée pour l'optimisation des modèles de langage.
Nous avons démontré que la méthode de Powell, largement utilisée pour l'optimisation des modèles de langage, est à la fois en mesure d'obtenir des solutions satisfaisantes et est robuste face à l'initialisation aléatoire. L'amorçage, par l'initialisation de la « population » en utilisation des poids d'interpolation obtenus à l'aide de l'algorithme d'espérance-maximisation, lui a permis de converger plus rapidement vers une solution. Cependant, étant de nature séquentielle, cet algorithme n'est pas aussi rapide que les algorithmes évolutionnaires que nous pouvons agressivement paralléliser.

Nous avons aussi montré que l'optimisation par algorithme génétique, avec les paramètres de base utilisés, converge de façon imprévisible. Cependant, lorsque nous avons inclus l'amorçage, nous avons observé une diminution de 0,22 bit de l'entropie croisée moyenne. Cela a aussi permis à l'AG de converger beaucoup plus rapidement vers une solution optimale. C'est aussi l'algorithme qui a été en mesure d'obtenir les meilleures solutions lors de l'évaluation sur le corpus WSJ1.

Nous avons par ailleurs évalué l'effet des différents paramètres de l'algorithme d'optimisation par algorithmes génétiques. Nos résultats ont montré que les paramètres que nous avions choisis pour nos expériences étaient près des paramètres optimaux. Nous avons aussi observé que la modification du taux de mutation n'avait pas nécessairement le comportement auquel nous nous attendions, c'est-à-dire une dégradation des résultats proportionnelle à l'augmentation du taux de mutation. Finalement, nous avons pu observer que c'est le taux de croisement qui a le plus d'effet sur la performance globale de l'optimisation par algorithmes génétiques, avec le plus grand écart-type, autant pour l'optimisation sans amorçage que pour l'optimisation avec amorçage.

Nous avons aussi montré que l'optimisation par essais particulaires est l'algorithme d'optimisation qui converge de façon la plus stable. C'est l'algorithme qui obtient les meilleurs résultats en moyenne et a une déviation standard inférieure à celle de l'algorithme génétique. L'OEP est aussi l'algorithme qui obtient une solution optimale le plus rapidement.

Par la suite nous avons procédé à une évaluation exhaustive de la performance des modèles de langage obtenus dans une tâche de reconnaissance automatique de la parole. Nous avons pu constater, dans notre cas particulier, que la perplexité ou l'entropie croisée du modèle de langage optimisé était faiblement corrélée au taux d'erreur des mots obtenue. Toutefois, les modèles les plus performants en reconnaissance automatique de la parole sont tout de même ceux qui diminuent de façon substantielle l'entropie du modèle de langage : diminution moyenne de 0,9 bit
d'entropie pour les modèles optimaux choisis par rapport au modèle de base lissé par l'algorithme
de Witten-Bell.

Finalement, bien que lorsque l'on fournit un vecteur de solution résultant d'une optimisation par
EM et que les algorithmes obtiennent en moyenne des solutions similaires, il est de notre avis,
suite à nos observations, que l'optimisation par essais particulaires est le plus performant des
trois algorithmes d'optimisation évalués. L'OEP est plus rapide que la méthode de Powell et que
l'AG, en particulier lorsque l'on introduit le parallélisme. De plus, contrairement à la méthode de
Powell, les algorithmes évolutionnaires sont plus flexibles dans le sens où ils sont à la fois en
mesure de minimiser le coût de la fonction et réduire le nombre de bacs utilisé, et ce, sans avoir
recours à l'optimisation multiobjective.
Analyse sémantique pour systèmes de
dialogue verbaux
Articles
# 5 REAL-LIFE SPEECH-ENABLED SYSTEM TO ENHANCE INTERACTION WITH RFID NETWORKS IN NOISY ENVIRONMENTS

Application d'un système basé sur la parole facilitant l'interaction avec des réseaux RFID dans des environnements bruités.

Y. Benahmed<fnref n="1" />,<fnref n="2" />, S-A. Selouani<fnref n="2" />, D. O'Shaughnessy<fnref n="1" /> et A. H. Abolhassani<fnref n="3" />

**Article soumis à** : *The 37th International Conference on Acoustics, Speech and Signal Processing*

**Lieu de la conférence** : Prague, République tchèque

**Accepté et publié**

**Date de publication** : Mai 2011

## 5.1 Contribution des auteurs :

**Yacine Benahmed** : (candidat)

Co-écriture de l'article, conception du logiciel de gestion par RFID. Conception et développement du gestionnaire de dialogue, expérimentation, analyse des données, préparation des graphes, des figures et des tableaux.

**Douglas O'Shaughnessy** : (directeur)

Conseils techniques et théoriques, conseils de rédaction, édition, coauteur, corrections.

**Sid Ahmed Selouani** : (codirecteur)

Conseils techniques et théoriques, édition, coauteur, corrections.

**A. H. Abolhassani** : (coauteur)

<footnote n="1">¹INRS-EMT, 800 de la Gauchetière O, H5A 1K6, Montréal, Qc, Canada</footnote>

<footnote n="2">²LARIHS Lab. Université de Moncton, Campus de Shippagan, New Brunswick, Canada</footnote>

<footnote n="3">³VMR Lab. McGill University, Montreal, Quebec, Qc, H3A 2A7, Canada</footnote>
Co-écriture de l'article, conception et développement du module de débruitage (VRE-KLT), préparation et analyse des données résultats des expériences, préparation des tableaux.

## 5.2 Commentaires des évaluateurs

La majorité des commentaires des évaluateurs ont été pris en considération lors de la révision finale de la version de l'article présenté dans cette section.

### 5.2.1 Évaluateur no 1

*General Comments to Authors*

It would be good to highlight any novel ideas in the implementation of the AIML based interpreter, so the contribution in that area is more clear. Also, sufficiently distinguishing the new contribution in terms of the VRE criterion over the previous work (cited in paper) would help readers.

### 5.2.2 Évaluateur no 2

*General Comments to Authors*

This paper proposes to describe a speech-enabled RFID system that can operate in noisy environments. However, most of the effort was focused on their implementation of the KLT model, which was already discussed in ref. 7. So really the paper is about improving the recognition of the speech, rather than the entire system as indicated in the title/abstract.

### 5.2.3 Évaluateur no 3

*General Comments to Authors*

The speech-enabled system for RFID applications definitely has industry promise. The algorithm development seems heuristic and the proposal does not justify why the approach works better in factory environments. The system seems to work but no comparison to other approaches were provided to claim novelty.
## 5.3 Résumé

Cet article 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). Un nouveau cadre de dialogue est proposé afin de donner aux opérateurs humains la capacité de communiquer avec le système d'une façon plus naturelle. 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, à 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é sur la variance de l'erreur de reconstruction de Karhunen-Loève Transform (VER-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 en utilisant le framework Microsoft Speech API. Nos résultats démontrent à la fois que l'algorithme VER-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.

> Le texte qui suit est une copie exacte de l'acte de conférence référencé ici haut<fnref n="35" />.

<footnote n="35">³⁵ La numérotation des sections, équations, figures, graphiques, tableaux et références ont été adaptés pour correspondre à l'ordre retrouvé dans ce document.</footnote>
## 5.4 Abstract

This paper presents a system that allows the user to interact by speech with a Radio-Frequency IDentification (RFID) network working in a highly noisy environment. A new dialog framework is proposed in order to give the human operators the ability to communicate with the system in a more natural fashion. This is achieved by the implementation of the Artificial Intelligence Markup Language which, allows the system to respond to close-to natural language queries by means of pattern matching. Besides this, and in order to deal with highly noisy and changing environments, an online signal subspace enhancement technique based on the Variance of the Reconstruction Error of Karhunen-Loève Transform (VRE-KLT) is proposed. Both of the dialog naturalness and speech enhancement efficiency are evaluated in real-life situations by using the Microsoft Speech API framework.

*Index Terms*— Natural dialog, RFID, speech recognition, speech enhancement, KLT, AIML

## 5.5 Introduction

Speech-enabled interfaces that include both speech recognition and synthesis are sufficiently advanced to a point where it becomes feasible to design viable and desirable solutions in various data collection applications. One of these innovative applications consists of providing the speech modality to allow the human operators of a Radio Frequency IDentification (RFID) Network to communicate naturally with related devices and information systems. The advantages of speech hands-free and eyes-free systems combined with the RFID technology are expected to improve speed, ergonomics and safety of numerous operations such as order picking, quality management, tracking and monitoring of assets, and shipping operations. In order to maintain an acceptable level of accuracy, the use of speech recognition is however limited in widely used applications to a fairly short list of input keywords for control and commands. For instance in Microsoft's approach [124], numeric characters for voice data inputs are used to select the command. Increasingly, and in all types of tasks, users are now requiring more naturalness in their verbal communications with machines. Therefore, making the speech-enabled interfaces more natural is one of crucial issues for their deployment in real-life applications such RFID.
Most interfaces incorporating speech interaction fall into three broad categories. The first category includes Command and Control (C&C) interfaces that rely on a fixed task dependant grammar to provide user interaction [125]. Their main advantage is their ease of implementation and high command recognition rate. However, their downside is the high cognitive load they induce when users interact with the system because of its lack of flexibility and lack of uniform command sets. The second category is based on interactive voice response (IVR) that guides users by the means of prompts in order to validate the utterance at every step [126]. This style of interaction is mostly used in menu navigation such as that found with phone and cable companies. Its relative lack of efficiency for fast interaction makes it a poor choice for everyday use. Finally, the third category uses natural language processing to parse the user's utterance and to determine the goal of the request. This can be done through multiple ways such as semantic and language processing and [127]. Hence, to be effective, due to "limitless" vocabulary, this type of interface needs an accurate recognizer.

In this paper, we present an effective framework for interactive spoken dialog systems belonging to the third category, using a dynamic pattern matching technique based on Artificial Intelligence Markup Language (AIML) [128]. This system will be used by RFID operators in very noisy environments. To improve the performance of the speech recognition in severely degraded environments, an online signal subspace-based approach is used to dynamically optimizing the choice of the noise-free Karhunen-Love Transform (KLT) principal components.

The organization of the paper is as follows. Section 5.6 presents the overall System that combines RFID and speech technologies to improve enterprise operations and also describes the AIML-based dialog framework used in our application. Section 5.7 presents the proposed subspace approach in enhancement of the noisy signal. The performance evaluation is reported in section 5.8, and in section 5.9 the paper is concluded.

## 5.6 Speech-enabled RFID system

Typically, an RFID-based process involves a human operator to perform multiple and simultaneous tasks in order to effectively use a number of devices and input devices to update an information system. The workflow may include other additional tasks such as inspecting items received for damages, confirming the quantity of a given product, etc. To reduce the cognition load of those
operators and to improve their comfort, the sensor capabilities of RFID is nowadays a very promising solution. As illustrated in Figure 5.1, the proposed system enables the orchestration of RFID events and inputs into synchronized operations in order to provide more automation thanks to the speech modality. Data collection is performed through the RFID devices. The readers and tag communication is managed by the speech-enabled system. Operator can speak in order to modify power, select antenna, launch the Read/Write tags, check inventory, etc.

### 5.6.1 System details

The application is composed of two major components:

The first component is the speech input layer. Here speech utterances are captured in a buffer and passed either directly to the automatic speech recognition (ASR) system or to the noisy speech enhancer according to the user preferences. The N-best ASR recognition outputs are then fed to a dialog manager which, parses them and returns either a user-friendly message to the user to indicate that it did not understand the meaning of the utterance or the most likely command with its parameters to the business logic end. For example, if the system recognizes the user input "Show me

<figure><img src="image_36.png" /><figcaption>Figure 5.1 : The overall speech-enabled system interacting with RFID Network.</figcaption></figure>
the RFID Reader Configuration", the system would return the RFID set up form. Feeding the N-best ASR outputs gives a certain error tolerance to the system since the most likely recognized sentence is not always the best one.

The second component is the business layer. It is constantly listening for user input as well as listening for RFID device events such as unauthorized inventory check out.

### 5.6.2 Dialog interpreter

The dialog interpreter used in this particular application is an Artificial Intelligence Markup Language (AIML) parser. AIML is an XML compliant language designed to create chat bots that can fool users into thinking that they are chatting with a person. Its primary design feature is minimalism in the sense that it can reduce complex user utterances into simpler atomic components. As such, it is essentially a pattern matching system that maps well with Case-Based Reasoning [128]. AIML consists of categories that encapsulate a pattern, the user input, and a template, the possible answer. The AIML parser then tries to match what the user said to the most likely pattern and outputs the corresponding answer. Additionally, patterns can include wildcards which, are especially useful for our application. It also supports recursion which, enables the system to answer based on previous inputs.

## 5.7 VRE speech enhancement technique

A key issue in developing a KLT-based speech enhancement model is to choose the optimal number of principal components (PCs). If fewer PCs are selected than required, a poor model will be obtained and an incomplete representation of the process results. On the contrary, if more PCs than necessary are selected, the model will be over-parameterized and will include noise. Different approaches had been proposed in the past to select the optimal number of PCs among which, we can cite the Minimum Description Length (MDL) [129] that used in our evaluation tests. Generally speaking, enhancement is obtained by removing the noise subspace and optimally weighting the signal subspace to remove noise energies from this subspace. The motivation to choose KLT is its optimality in compression of information, while the DFT and the DCT are suboptimal.
In [81] we introduced a novel approach for the optimal subspace partitioning using the Variance of the Reconstruction Error (VRE) criterion. This criterion provides consistent parameter estimates and allows us to implement an automatic noise reduction algorithm that can be simply applied to the observed data. In this paper we propose a new VRE criterion and we use it to improve the performance of real-time speech recognition that is used for interacting with the RFID network. The main advantage of our method is that it is a wave-in-wave-out method and does not require the separation of noise information. This approach is well adapted to the kind of application we target.

### 5.7.1 Online VRE-KLT speech enhancement

Let's consider stochastic processes $X(t)$, $N(t)$, and $S(t)$, that have generated $x(t)$, $n(t)$, and $s(t)$, respectively, are wide sense ergodic. We define a real-valued observation vector $x(t) \in \mathbb{R}^K$ to be the sum of the signal vector $s(t) \in \mathbb{R}^K$ and a noise vector $n(t) \in \mathbb{R}^K$, i.e.,

$$x(t) = s(t) + n(t). \qquad (5.1)$$

We arrange a K-dimensional observation vector in a $M \times N$ Hankelstructured observation matrix $X_{M \times N}(t)$ where $K = M + N - 1$, i.e.,

$$X_{\{M \times N\}}(t) = \begin{pmatrix} x_t & x_{t-1} & \cdots & x_{t-N+1} \\ x_{t-1} & x_{t-2} & \cdots & x_{t-N} \\ \vdots & \vdots & \ddots & \vdots \\ x_{t-M+1} & x_{t-M} & \cdots & x_{t-M-N+2} \end{pmatrix}. \qquad (5.2)$$

Due to the ergodicity assumption, we can estimate the covariance matrix $R_{xx}$ using the zero-mean-scaled version of (5.2) as:

$$\hat{R}_{xx} = \frac{1}{M-1} X^T X \in \mathbb{R}^{N \times N}. \qquad (5.3)$$

Let $q_1, q_2, \dots, q_N$ be eigenvectors corresponding to the eigenvalues $\lambda_1, \lambda_2, \dots, \lambda_N$ of the correlation matrix $R_{xx} \in \mathbb{R}^{N \times N}$. By defining the Q matrix as :
$$Q = [q_1 \ q_2 \ \dots \ q_N] \in \mathbb{R}^{N \times N}, \qquad (5.4)$$

where the eigenvectors are orthonormal due to the symmetry in $R_{xx}$ and ordering the eigenvalues in decreasing order in a diagonal matrix:

$$\Lambda = \mathrm{diag}(\lambda_1, \lambda_2, \dots, \lambda_N) \in \mathbb{R}^{N \times N}$$

where $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_N \ge 0$.

For positive-definite matrices, we can decompose the original matrix $R_{xx}$ into its eigenvalue decomposition (EVD),

$$R_{xx} = Q \Lambda Q^T. \qquad (5.5)$$

The separation of eigenvectors and principal components matrices gives:

$$Q = [\hat{Q}_l | \tilde{Q}_{N-l}] \quad Y = [\hat{Y}_l | \tilde{Y}_{N-l}] \qquad (5.6)$$

$$X = \hat{Y}_l \hat{Q}_l^T + \tilde{Y}_{N-l} \tilde{Q}_{N-l}^T = \hat{X} + N \qquad (5.7)$$

with

$$\hat{X} = X \tilde{C}_l \quad \text{and} \quad N = X \tilde{C}_{N-l} \qquad (5.8)$$

where the matrices $\hat{C}_l = \hat{Q}_l \hat{Q}_l^T$ and $\tilde{C}_{N-l} = I_N - \hat{C}_l$ constitute the KLT model. The variable reconstruction approach is presented. Imagine that our signal is corrupted with a noise $n_j$ along a direction $\xi_j \in \mathbb{R}^N$:

$$x = s + n_j \xi_j, \qquad (5.9)$$
where $\|\xi_j\| = 1$. The task of signal reconstruction is to find an estimate for $s$ along the direction of upset $\xi_j$ to best correct the effect of the upset. In other words, we try to find $\hat{n}_j$ such that:

$$ \hat{s} = x - \hat{n}_j \xi_j \qquad (5.10) $$

has minimum model error, i.e.,

$$ n_j = \arg \min_{n_j} \|s - \hat{s}\| = \arg \min_{n_j} \|\tilde{s}\|^2 = \arg \min_{n_j} \|\tilde{x} - \tilde{n}_j \tilde{\xi}_j\|^2, \qquad (5.11) $$

where $\tilde{s}$ and $\hat{s}$ show the clean signal portion in the RS and PCS respectively. The solution to (5.12) can be easily found using least squares,

$$ \hat{n}_j = \frac{\hat{\xi}_j^T \tilde{x}}{\hat{\xi}_j^T \hat{\xi}_j} = \frac{\hat{\xi}_j^T x}{\hat{\xi}_j^T \hat{\xi}_j}. \qquad (5.12) $$

Substituting the above $\hat{n}_j$ into equation (5.11) we obtain the best signal reconstruction as follows.

$$ \hat{s} = \left( I - \frac{\tilde{\xi}_j \tilde{\xi}_j^T}{\tilde{\xi}_j^T \tilde{\xi}_j} \right) x = (-\tilde{\xi}_j^o \tilde{\xi}_j^{oT}) x, \qquad (5.13) $$

where $\tilde{\xi}_j^o \equiv \tilde{\xi}_j / \|\tilde{\xi}_j\|$. Substituting equation (5.10) into equation (5.11), we obtain,

$$ s - \hat{s} = (\hat{n}_j - n_j) \xi_j. \qquad (5.14) $$

Substituting equation (5.10) into equation (5.13) we get:

$$ \hat{n}_j - n_j = \frac{\tilde{\xi}_j^T s}{\tilde{\xi}_j^T \tilde{\xi}_j}. \qquad (5.15) $$

Therefore, the reconstruction error, is

$$ s - \hat{s} = (\hat{n}_j - n_j) \xi_j = \frac{\tilde{\xi}_j^T s}{\tilde{\xi}_j^T \tilde{\xi}_j} \xi_j. \qquad (5.16) $$
and

$$ \|s - \hat{s}\| = \frac{|\tilde{\xi}_j^T s|}{\tilde{\xi}_j^T \tilde{\xi}_j}. \qquad (5.17) $$

From equations (5.16) and (5.17) we observe that the variance of $(s - \hat{s})$ occurs only in the reconstruction direction $\xi_j$, which, is the same as the variance of $n_j - \hat{n}_j$ and, the reconstruction error $(s - \hat{s})$ depends on the number of PCs retained in the PCA model. The number of optimal PCs is then obtained by achieving the minimum reconstruction error. Further, if the reconstruction error is minimized for a particular magnitude $n_j$, it is minimized for all magnitudes. Therefore, we can simply determine the number of PCs for the case of $n_j = 0$ to achieve the best reconstruction. Assuming $n_j = 0$, the variance of the reconstruction error (VRE) in the direction $\xi_j$ can be calculated as follows,

$$ u_j \equiv \mathrm{var}\{\xi_j^T (x - \hat{s})\} = \mathrm{var}\{\hat{n}_j\} = \frac{\tilde{\xi}_j^T R_{xx} \tilde{\xi}_j}{(\tilde{\xi}_j^T \tilde{\xi}_j)^2}, \qquad (5.18) $$

where $R$ is the covariance (correlation) matrix defined in equation (5.3). In Equation (5.19), $u_j$ is the variance of the reconstruction error in the estimation of $s$ by using $\hat{s}$.

In order to find the number of PCs, we have to minimize $u_j$ with respect to the number of PCs. Considering different noise directions, we propose the VRE to be minimized as

$$ VRE(l) = \sum_{j=1}^{N} \frac{u_j(l)}{\xi_j^T R \xi_j}. \qquad (5.19) $$

In this equation we calculate the VRE by summing $u_j$ in all dimensions. In order to equalize the importance of each variable, variance-based weighting factors are applied. The criterion that we propose to define the optimal order of reconstruction is given by the following equation:

$$ l_{opt} = \min \left( \arg \min_{1} [VRE_{t-\alpha}(l)] \right), \qquad (5.20) $$
where *t* is the frame index and *α* is the number of past frames that are used to determine the optimal number of components. Equation (5.20) gives more robustness to the process of determining the order of reconstruction and prevents from rapid fluctuations of that optimal order that could be due to artifacts. In our case α = 3.

**5.8 Experiments and results**

**5.8.1 Evaluation of the dialog framework**

In order to evaluate if the flexibility of the AIML dialog scheme in the context of a RFID application,
we proceeded with informal dialog testing. We accomplish this by testing different ways of achieving
the task of going to the inventory screen and then having the system read out which items are checked
out. Table 5.1³⁶ shows possible valid scenarios. These examples show how the system can cope with
a certain measure of speech recognition inaccuracy as well as its ability to allow the user to express
him/her more fluently.

**5.8.2 Evaluation of the KLT-VRE enhancement method**

To evaluate the performance of the VRE enhancement technique, we carried out extensive objective
quality tests with the NOIZEUS database. We use all 30 sentences of the NOIZEUS database [130].
Noisy signals were generated by adding a factory noise from the Noisex-92 database [132] to the
clean signals of NOIZEUS database, at 0 dB, 5dB and 10 dB overall SNR. The frame sizes were
chosen to be 30 ms long with 40% overlap. An 8 kHz sampling frequency (downsampled from the
original) and a Hamming window were applied. The methods to be compared with VRE are the
Minimum description length (MDL) [129], Wiener and the Spectral Subtraction (SS) methods [130].
The objective measures used for the evaluation are the Weighted Spectral Slope (WSS) distance
(smaller reflects less distortion) and the Perceptual Evaluation of Speech Quality (PESQ). These
measures are chosen because ASR gives a trend corresponding to that of subjective intelligibility that
is strongly correlated to these measures [133]. For the definitions of these measures see [130]. In

<footnote n="36">³⁶ Le calcul du PSEQ utilisé dans le tableau 5.1 utilise l’algorithme de Loizou [130] qui a été supplanté par la norme UIT862.1[131] permettant de normaliser les scores PSEQ.</footnote>
<table><caption>Table 5.1 : Objective evaluation under a factory noise degradation.</caption><thead><tr><th>Objective Measures</th><th>Input SNR(dB)</th><th>Weiner</th><th>SS</th><th>MDL</th><th>VRE</th></tr></thead><tbody><tr><td rowspan="3">WSS</td><td>0</td><td>126.89</td><td>142.21</td><td>141.14</td><td><strong>126.48</strong></td></tr><tr><td>5</td><td>95.47</td><td>102.34</td><td>104.28</td><td><strong>93.88</strong></td></tr><tr><td>10</td><td><strong>65.32</strong></td><td>75.25</td><td>82.56</td><td>68.21</td></tr><tr><td rowspan="3">PESQ|UIT862.1</td><td>0</td><td>1.62 | 1.38</td><td>1.28 | 1.24</td><td>0.95 | 1.15</td><td><strong>1.74 | 1.45</strong></td></tr><tr><td>5</td><td>1.96 | 1.60</td><td>1.92 | 1.57</td><td>1.58 | 1.36</td><td><strong>2.14 | 1.75</strong></td></tr><tr><td>10</td><td><strong>2.74 | 2.45</strong></td><td>2.42 | 2.04</td><td>1.78 | 1.48</td><td>2.72 | 2.42</td></tr></tbody></table>

<table><caption>Table 5.2 : Possible valid dialogs of Speech-enabled system.</caption><tbody><tr><th colspan="2">Example with perfect speech recognition</th></tr><tr><td><b>User</b> : Show me the inventory please.<br/><b>System</b>: tab inventory<br/><b>User</b> : Tell me which items are checked out please.<br/><b>System</b>: read chkout inventory</td><td><b>User</b> : Go to inventory tab.<br/><b>System</b>: tab inventory<br/><b>User</b> : Are there any checked out products?<br/><b>System</b>: read chkout inventory</td></tr><tr><th colspan="2">Example with speech recognition errors</th></tr><tr><td><b>User</b> : Show better inventory peace.<br/><b>System</b>: tab inventory<br/><b>User</b> : The witch items or checked out please.<br/><b>System</b>: read chkout inventory</td><td><b>User</b> : Got inventory tab.<br/><b>System</b>: tab inventory<br/><b>User</b> : Arthur Anny checked out products?<br/><b>System</b>: read chkout inventory</td></tr></tbody></table>

VRE and MDL, $N = 21$ (KLT dimension). In Wiener, $\alpha$ (the smoothing factor for the Decision-Directed method for estimation of A Priori SNR) equals 0.99, and the smoothing factor for the noise updating is 9. In SS, $c$ (the scaling factor in silence periods) is set to 0.03. The results given in Table 5.1 show that VRE outperforms the other methods.

## 5.9 Conclusion and future work

Automatic speech recognition and text-to-speech have become sufficiently mature technologies to allow their effective inclusion in RFID networks. In this paper we presented a viable and realistic solution which, takes into account the difficulties faced by both the RFID and speech technologies.
We have incorporated an effective enhancement technique and a flexible dialog framework in a Microsoft platform. As expected, the results show that the implementation of AIML and VRE allows the RFID operators to interact more naturally with the system in noisy environments. Thus, this solution could constitute a promising answer to the growing need for ubiquitous access to information that is driving today's technological advances in many real-life applications using RFID technology. In future work will look at modifying the AIML framework to support semantic and pragmatic interpretation instead of pure textual analysis. This should provide a more flexible and powerful framework to create robust dialog management.
<figure><img src="image_37.png" /></figure>
# 6 ONTOLOGY-BASED PATTERN GENERATOR AND ROOT SEMANTIC ANALYSER FOR SPOKEN DIALOGUE SYSTEMS

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

Y. Benahmed<fnref n="1" />,<fnref n="2" />, S-A. Selouani<fnref n="2" /> et D. O’Shaughnessy<fnref n="1" />

**Article soumis à** : La 25e Conférence Canadienne de Génie Électrique et Génie Informatique

**Lieu de la conférence** : Montréal, Canada

**Accepté et publié**

**Date de publication** : 29 avril 2012

## 6.1 Contribution des auteurs :

**Yacine Benahmed:** (candidat)

Écriture de l'article, développement des logiciels et programmes, expérimentation, analyse des données, préparation des graphes, des figures et des tableaux.

**Douglas O’Shaughnessy:** (directeur)

Conseils techniques et théoriques, conseils de rédaction, édition, coauteur, corrections.

**Sid-Ahmed Selouani:** (codirecteur)

Conseils techniques et théoriques, édition, coauteur, corrections.

<footnote n="1">¹INRS-EMT, 800 de la Gauchetière O, H5A 1K6, Montréal, Qc, Canada</footnote>

<footnote n="2">²LARIHS Lab. Université de Moncton, Campus de Shippagan, New Brunswick, Canada</footnote>
## 6.2 Commentaires des évaluateurs

La majorité des commentaires des évaluateurs ont été pris en considération lors de la révision finale de la version de l'article présenté dans cette section.

### 6.2.1 Évaluateur no 1

*Comments for the Authors:*

This paper presents the dialogue interpreter subsystem which allows the user to interact by speech with a Radio-Frequency IDentification (RFID) network working in a highly noisy environment. Algorithms have been presented and the evaluation results are included. I feel that the results could be elaborated more. Overall, the paper has some merit.

### 6.2.2 Évaluateur no 2

*Comments for the Authors:*

General comments: 1. First part of Section 2: figure 1? Figure 1, also apply to all other cases. 2. Start Subsection 2.1 on the new page or move it up. 3. Caption of Fig.1: Network? network. 4. In Section 5: You have 5.1 but no 5.2, ... 5. Syntax error in the first sentence of Subsection 5.1. 6. Last sentence in the conclusion: English syntax error. 7. Inconsistency of writing references. See ref [2] and [3]. Also check conference formatting rules. 8. In Section 2.2: Where is Table 2.2 ??

### 6.2.3 Évaluateur no 3

*Comments for the Authors:*

The following small errors should need to be corrected: (VRE-KLT)[6]... (VRE-KLT) [6]... It was designed by Wallace[5]... It was designed by Wallace [5]... such as OWL 2[9] and SUO-KIF[10]. such as OWL 2 [9] and SUO-KIF [10]. WorndNet®[11]... WorndNet [11]... being a synonym[11]. being a synonym [11]. Zesch et al.[12] since... Zesch et al. [12] since... with TreeTagger[13]. with TreeTagger [13]. In order to evaluate if the flexibility... In order to evaluate the flexibility... [4] C. C. Fung G. O. Sing,... [4] C. C. Fung, G. O. Sing,... Reference [10] should be properly justified [12] Torsten Zesch, Christof Müller, and Iryna Gurevych,... [12] T. Zesch, C. Müller, and I. Gurevych,...
## 6.3 Résumé

Cet article propose une amélioration au gestionnaire de dialogue proposé dans [80]. Rappelons qu'il s'agit d'un système basé sur la parole facilitant l'interaction avec les réseaux RFID dans des environnements bruyants. Un des désavantages principaux que nous avons rencontrés avec le langage AIML est la nécessité de créer des motifs pour toute les variations d'une commande possible. Par exemple, un des problèmes 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. La solution proposée vise à faciliter la conception de grammaire/motifs-type 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 de commandes-type. 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é.

> Le texte qui suit est une copie exacte de l'acte de conférence référencé ici haut<fnref n="37" />.

<footnote n="37">³⁷ La numérotation des sections, équations, figures, graphiques, tableaux et références ont été adaptés pour correspondre à l'ordre retrouvé dans ce document.</footnote>
## 6.4 Abstract

This paper presents improvements in the dialogue interpreter subsystem for an application that allows the user to interact by speech with a Radio-Frequency IDentification (RFID) network working in a highly noisy environment. A new dialog framework is proposed in order to give the human operators the ability to communicate with the system in a more natural fashion. This is achieved by the implementation of the Artificial Intelligence Markup Language combined with an ontology-based pattern generation and root semantical analysis algorithms, which allows the system to respond to close-to natural language queries by means of pattern matching.

**IndexTerms**— Natural dialog, pattern generation, semantic analysis, natural language processing, AIML

## 6.5 Introduction

Speech-enabled interfaces that include both speech recognition and synthesis are sufficiently advanced to a point where it becomes feasible to design viable and desirable solutions in various data collection applications. One of these innovative applications consists of providing the speech modality to allow the human operators of a Radio Frequency IDentification (RFID) Network to communicate naturally with related devices and information systems. The advantages of speech hands-free and eyes-free systems combined with the RFID technology are expected to improve the speed, ergonomics and safety of numerous operations such as order picking, quality management, tracking and monitoring of assets, and shipping operations. In order to maintain an acceptable level of accuracy, the use of speech recognition is however limited in widely used applications to a fairly short list of input keywords for control and commands. For instance in Microsoft's approach [124], numeric characters for voice data inputs are used to select the command. Increasingly, and in all types of tasks, users are now requiring more naturalness in their verbal communications with machines. Therefore, making the speechenabled interfaces more natural is one of the crucial issues for their deployment in real-life applications such RFID.

Most interfaces incorporating speech interaction fall into three broad categories. The first category includes Command and Control (C&C) interfaces that rely on a fixed task dependent grammar to
provide user interaction [125]. Their main advantage is their ease of implementation and high command recognition rate. However, their downside is the high cognitive load they induce when users interact with the system because of its lack of flexibility and lack of uniform command sets. The second category is based on interactive voice response (IVR) that guides users by the means of prompts in order to validate the utterance at every step [126]. This style of interaction is mostly used in menu navigation such as that found with phone and cable companies. Its relative lack of efficiency for fast interaction makes it a poor choice for everyday use. Finally, the third category uses natural language processing to parse the user's utterance and to determine the goal of the request. This can be done through multiple ways such as semantic and language processing and filtering [127]. Hence, to be effective, due to "limitless" vocabulary, this type of interface needs an accurate recognizer.

However one problem still remains with the implementation of such interfaces, in the sense that a lot of handcrafting of rules and knowledge is still required. This quickly becomes an issue as the complexity of the interface increases since it is extremely time consuming and ultimately inconceivable to manually create a complete set of speech understanding rules.

In this paper, we present an effective framework for generating patterns from root semantical patterns for use with an interactive spoken dialog system belonging to the third category, using a dynamic pattern matching technique based on the Artificial Intelligence Markup Language (AIML) [128]. That is, the goal is to allow developers to quickly generate possible utterances for user interaction only by having to specify general utterance rules.

The organization of the paper is as follows. Section 6.6 presents the overall system that combines RFID and speech technologies to improve enterprise operations and also describes the AIML-based dialog framework used in our application. In Section 6.7 we briefly introduce the concept of ontologies and their pertinence in natural language processing. Section 6.8 introduces the ontology-based pattern generation and root semantic analysis algorithms. An evaluation of the system is reported in section 6.9, and in section 6.10 the paper is concluded.
## 6.6 Speech-enabled RFID system

Typically, an RFID-based process involves a human operator to perform multiple and simultaneous tasks in order to effectively use a number of devices and input devices to update an information system. The workflow may include other additional tasks such as inspecting items received for damages, confirming the quantity of a given product, etc. To reduce the cognitive load of those operators and to improve their comfort, the sensor capabilities of RFID nowadays provide a very promising solution. As illustrated in Figure 6.1, the proposed system enables the orchestration of RFID events and inputs into synchronized operations in order to provide more automation thanks to the speech modality. Data collection is performed through the RFID devices. The readers and tag communication are managed by the speech-enabled system. Operator can speak in order to modify power, select antenna, launch the Read/Write tags, check inventory, etc.

<figure><img src="image_38.png" /><figcaption>Figure 6.1 : The overall speech-enabled system interacting with the RFID Network.</figcaption></figure>

### 6.6.1 System details

The application is composed of two major components:

1. The first component is the speech input layer. Here speech utterances are captured in a buffer and passed either directly to the automatic speech recognition (ASR) system or to
the noisy speech enhancer according to the user preferences. Noisy speech is enhanced by
an online signal subspace enhancement technique based on the Variance of the
Reconstruction Error of the Karhunen-Loeve Transform (VRE-KLT) [12] whose main
advantage is that it is a wave-inwave-out method and does not require the separation of
noise information. The N-best ASR recognition outputs are then fed to a dialog manager
which, parses them and returns either a user-friendly message to the user to indicate that it
did not understand the meaning of the utterance or the most likely command with its
parameters to the business logic end. For example, if the system recognizes the user input
“Show me the RFID Reader Configuration”, the system would return the RFID set up
form. Feeding the N-best ASR outputs gives a certain error tolerance to the system since
the most likely recognized sentence is not always the best one.

2. The second component is the business layer. It is constantly listening for user input as well as listening for RFID device events such as unauthorized inventory check out.

6.6.2 AIML-based dialog interpreter

The dialog interpreter used in this application, like our previous work [9], [80], [134], relies on a pattern matching language to understand user's utterances. More specifically, the Artificial Intelligence Markup Language (AIML), an XML compliant language designed to create chat bots that can fool users into thinking that they are chatting with a person. It was designed by Wallace [128] to create chat bots rapidly and efficiently. Its primary design feature is minimalism, and reductionism by recursivity. That is, multiple inputs can be reduced to a general model. As such, it is essentially a pattern matching system that maps well with Case-Based Reasoning [128]. With AIML, botmasters effectively create categories that consist of a pattern, the user's input, and a template, the Bots' answer. The AIML parser then tries to match what the user said to the most likely pattern and outputs the corresponding answer. Additionally, patterns can include wildcards, which can be useful for catching irrelevant input or the target of requests. Moreover, the language supports recursion, which enables it to answer based on previous input. Table 6 presents an example of a simple grammar used to inquire about the quantity of a particular product that was shipped to a certain destination. The first category represents the general pattern to be identified (the actual search with its arguments). The star "*" found in the pattern tag represents a wildcard, and as such will match any input. In the template tag, we find the star tag. It points
<figure><img src="image_39.png" /><figcaption>Table 6.1 : Example of an AIML category.</figcaption></figure>

to the wildcard from the pattern and means that its value will be returned as output. For example
the input "How many *radios* shipped to *Montreal*" would return "N SHIPPED *radios* TO
*Montreal*". The second category uses the *srai* tag. It is used for reductionism, in this example, to
the "HOW MANY * SHIPPED TO *" pattern. Furthermore, the index attribute from the star tags
with value of 2 and 3 means that for the input "Tell me how many radios were shipped to Montreal"
the template would ignore the text preceding "how many" and reduce it to the "N SHIPPED *radios*
TO *Montreal*" output.

One of the main disadvantages that we encountered with the AIML language is that we needed to
manually create patterns for all possible utterances covered by the application. That is, for a simple
search request, multiple patterns were required to cover all lemmas, conjugation and variations
thereof. What we will seek to accomplish is to leverage the ontologies to create our patterns. The
designer will need only to specify one pattern per possible action/request and the system will
initially be able to generate all possible variations from the ontological relations; this is addressed
in section 6.8.
**6.7 Ontologies in natural language processing**

Ontologies are used to relate concepts in a hierachical and relational fashion that ultimately describe the meaning of terms. Logical and philosophical entities can be grouped contextually with the use of named relations. Figure 6.2 shows a portion of the entry for the ontology of a cat as it relates to rodents and birds. In this example, solid lines represent inheritance, dashed lines such as the ones connecting cat with bird and rodents represent functional relationships and the dotted line between vertebrate and spine represent inherited properties.

Ontologies can be described by numerous formal languages. It is therefore important to properly choose a language that fits the needs of the application, ideally choosing a standard-based language

<figure><img src="image_40.png" /><figcaption>Figure 6.2 : Example of a simple ontology diagram representing animals and their relations and properties.</figcaption></figure>

such as OWL 2 [135] and SUO-KIF [136]. This eventually ensures that the application will be
compatible with external ontologies and be able to quickly implement new knowledge with
minimal involvement from the developer.

6.8 Ontology-based speech pattern generator

6.8.1 Ontology

In the current itteration of our application, the ontology used is WordNet [88] from Princeton University. It is essentially a large (15,5287 defined words) lexical database of English nouns, verbs, adjectives and adverbs. The main relation between defined words is synonymy, the state of being a synonym. We are also currently working to increase the ontological knowledge of WordNet to exploit data from Wiktionary in the spirit of Zesch et al [31] since all defined terms are tagged with their part of speech and can have relations to other terms defined.

6.8.2 Pattern generation and root semantic analysis algorithms

The pattern generation algorithm is described as follows and is inspired by the work in paraphrasing
for automatic evaluation by Kauchak et al [85]. For an AIML grammar G composed of patterns Pᵢ,
first do part of speech tagging for every term Tⱼ in Pᵢ. That is, assign a part of speech tag, n for
noun, v for verb, adj for adjective and adv for adverb to every Tⱼ ⇒ Tⱼ<sup>pos</sup>. Then, for every term
Tⱼ<sup>pos</sup> return a vector Tⱼ<sup>pos</sup> of the kth ontologically related terms where k is the maximum relational
distance between two ontological roots defined by the number of links separating them. In this case
a simple depth-limited search is implemented with a complexity of O(|M| + |E|) where |M| is
the number of vertices (terms) and |E| is the number of edges (links), with the knowledge that there
is “no” solution and that the problem of optimality is not pertinent. That is we are not concerned
with the possibility of finding a solution that is more expensive than a solution in another path.
Finally generate a matrix of new patterns Pᵢ by a cartesian product of every Tⱼ<sup>pos</sup> with a maximum
complexity of O(N * M) where N is the number of terms in the pattern and M the number of
related terms for every term. Consequently, the overall approximate complexity of the algorithm is
O(LN(M + E)) where L is the number of patterns in the grammar.
<caption>**Algorithm 6.1 :** Ontological-based speech pattern algorithm where: *G* is the grammar, *P* the grammar's patterns and, *T* the pattern's terms.</caption>

for all $P_j \in G$ do
  for all $T_j \in P_i$ do
    do part-of-speech-tagging($T_j$)
    return vector $T_j^{pos}$ of related terms
  end for
  Combine $T_j^{pos}$ for matrix of new pattern $P_i$
end for

For the root semantic analysis algorithm, which allows novel utterances to be processed, the operation is simplified and works as follows. For each term $T_j$ in the recognized utterance $U$ do part of speech tagging to obtain $T_j^{pos}$. Then, for each $T_j^{pos}$ return a vector $T_j^{pos}$ of the $k^{th}$ ontologically related terms. Generate a matrix of new utterances $U$ by a cartesian product of every $T_j^{pos}$. Then, for each root pattern $P_{root}$ composed of $T_{root,j}$ terms in the grammar $G$ find the maximal similarity measure, in this case through a simple term frequency/inverse document frequency (tf-idf) measure. If the similarity is within 0.6, align the matching terms and push the unmatched terms to the wildcards.

<caption>**Algorithm 6.2 :** Ontological-based root semantical analysis algorithm where: *G* is the grammar, *P*<sub>root</sub> the grammar's root patterns and, *T*<sub>root,j</sub> the root pattern's terms, *U* the user's recognized utterance and *T*<sub>j</sub>*U*'s terms.</caption>

for all $T_j \in U$ do
  do part-of-speech-tagging($T_j$)
  return vector $T_j^{pos}$ of related terms
end for
Combine $T_j^{pos}$ for matrix of new pattern $P_i$
return $\text{argmax}(\text{tf-idf}(P_i, P_{root}))$

In our application, the part of speech tagging operation is done with TreeTagger [137]. Since TreeTagger's output is based on the Penn-Treebank tagset, a simple mapping is done between the Penn-Treebank tagset and the WordNet tagset used for our classification process. For even easier processing we can envisage converting the terms in every pattern to their lemma. Since TreeTagger can output the lemmas this would ultimately reduce the ontological search and ultimately reduce the complexity of the proposed algorithm.
# 6.9 Experiments and results

## 6.9.1 Evaluation of the pattern generator

In order to evaluate if the flexibility of the ontology-based pattern generation algorithm, we proceeded with the generation of all possible variations of the root patterns of the speech-enabled RFID application described in section 6.6. The original grammar consists of 47 distinct patterns. Furthermore in the interest of evaluating the impact of complexity we measure the generated language model's complexity before and after generation with the use of the SRILM [93] tool against a sample of 417,000 sentences extracted from Wiktionary. The pattern-generation algorithm yielded 133 additional patterns which should certainly and shows how the system can now cope better with a certain measure of utterance variability. Table 6.2 shows a sample of the new patterns generated by the algorithm with relation to their root pattern. We see that the patterns are still semantically significant in terms of user interaction. As for the perplexity of the new Original patterns grammar, as expected it only increased by around 0.15 points as illustrated by Table 6.3.

<table><caption>Table 6.2: Example of additional AIML categories generated by the pattern generation algorithm.</caption><thead><tr><th colspan="2">Original patterns</th></tr></thead><tbody><tr><td>how many * were shipped to *</td><td>* out inventory *</td></tr><tr><th colspan="2">Generated patterns</th></tr><tr><td>how many * were embarked to *</td><td>* out products *</td></tr><tr><td>how many * were sent to *</td><td>* out wares *</td></tr><tr><td>how many * were transported to *</td><td></td></tr></tbody></table>

<table><caption>Table 6.3: Perplexity (ppl) evaluation of original and generated grammars as measured by SRILM tool.</caption><thead><tr><th>Sentence</th><th>PPL</th></tr></thead><tbody><tr><td>Original</td><td>3.62633</td></tr><tr><td>Generated</td><td>3.77896</td></tr></tbody></table>
## 6.10 Conclusion and future work

In this paper we presented an improvement to a previously published system, which takes into account the difficulties faced by both the RFID and speech technologies. We have incorporated an effective and flexible dialog framework in a Microsoft platform through the implementation of a AIML pattern generation algorithm that leverages the knowledge contained within ontologies as well as the implementation of an algorithm to reduce novel utterances to their root semantical patterns without significantly altering the perplexity of the grammar. In future work will look at leveraging multiple domain ontologies through the use a distributed computing paradigm in order to more rapidly compute the semantic and pragmatic interpretations contained in user utterances.
<figure><img src="image_41.png" /></figure>
# 7 A BIN-BASED ONTOLOGICAL FRAMEWORK FOR LOW-RESOURCE N-GRAM SMOOTHING IN LANGUAGE MODELLING

Un cadre basé sur des groupements ontologiques pour le lissage de N-grammes dans un contexte de faibles ressources pour la modélisation du langage

Y. Benahmed<fnref n="1" />,<fnref n="2" />, S-A. Selouani<fnref n="2" /> et D. O’Shaughnessy<fnref n="1" />

**Article soumis à** : *The 39th International Conference on Acoustics, Speech and Signal Processing*

**Lieu de la conférence** : Florence, Italie

**Accepté et publié**

**Date de publication** : 4 mai 2014

## 7.1 Contribution des auteurs :

**Yacine Benahmed:** (candidat)

Écriture de l'article, développement des logiciels et programmes, expérimentation, analyse des données, préparation des graphes, des figures et des tableaux.

**Douglas O’Shaughnessy:** (directeur)

Conseils techniques et théoriques, conseils de rédaction, édition, coauteur, corrections.

**Sid-Ahmed Selouani:** (codirecteur)

Conseils techniques et théoriques, édition, coauteur, corrections.

<footnote n="1">¹INRS-EMT, 800 de la Gauchetière O, H5A 1K6, Montréal, Qc, Canada</footnote>

<footnote n="2">²LARIHS Lab. Université de Moncton, Campus de Shippagan, New Brunswick, Canada</footnote>
## 7.2 Commentaires des évaluateurs

La majorité des commentaires des évaluateurs ont été pris en considération lors de la révision finale de la version de l'article présenté dans cette section.

### 7.2.1 Meta évaluation no 1

#### Overall Evaluation

Interesting idea with some preliminary results from small-scale experiments. One main issue is that the interpolation weights in Eq ([7].4) are tuned on test sets, rather than a hold out dev sets, which makes the perplexity results in Table 1 unconvincing. Further, my guts feeling is that these weights should be better tied to $w_n$ rather than globally shared as the way the authors present it. Is there any theoretical or experimental justification for this?

The basic idea of integrating semantic relations have also been explored in other ways such as using word clustering, and integrate them into a max-ent (log-linear) LM. The authors should discuss the connections and comparisons.

### 7.2.2 Évaluateur régulier no 2

#### Comments to authors

The idea is interesting, but the experimental validation lacks a proper baseline comparison against simple class based LMs.

Also, working on an artificially weakened baseline makes the relevance of the work questionable: is there no actual low-resource task where the approach can be used to improve the state of the art?

### 7.2.3 Évaluateur régulier no 3

#### Comments to authors

Section 1: This talks about a specific kind of language modeling - namely "statistical language modeling" but manages to convey the impression that all language modeling is probabilistic. It would be useful to maintain this context whenever categorical statements are made, e.g. "Formally, we compute the probability of word w = w_n given its history or context"
"number of times that we observed h,w" should be "number of times that we observed {h,w}" or
some reasonable set/sequence notation.

Equations 1 and 2 are repetitions and should be consolidated.

Page 1, Section 1, last para: the reasoning is somewhat vague. Sensitivity to corpora and data sparseness are both related to one underlying cause - that word distributions in any language are observed to follow Zipf's law. Regardless of the size of the corpora, there will be a large number of N-grams that will not have sufficient counts. The patterns of N-grams differ in different text corpora, and Zipf's law compounds the differences to the extent that statistics obtained from one are largely inadequate to predict trends in the others.

Page 1, Section 1, 2nd column: The statement "if we train our model on text from Shakespeare, it is evident that the model will not be adequate for the prediction of astrophysical text." should be qualified more technically. The word "generalizability" would be more correct than the word "significance".

The statement "This paper combines Witten-Bell smoothing over Kneser-Ney smoothing is that our smoothing algorithm produces real numbered counts that are not supported by the current implementation of the SRILM Toolkit." does not make sense in its current form.

Section 2, first para: The significance of the length of the lines is not explained even in the caption of Fig. 1. If this is merely a stylistic reference the fact should be mentioned.

"by smoothing its probabilities with those of weighed n-grams of related terms" : "weighed" should be replaced with "weighted" here and elsewhere in the paper.

Section 3.1: Section 3: While the approach is interesting in itself and obviously works, there still remains the matter of providing good explanations in the paper. In a world where a lamb bleats while a dog barks, existing techniques assign minimal probability to the unseen N-grams "lamb barks" and "dog bleats". If however the ontologies of the two are merged as proposed, this probability is likely to be higher unless further semantic constraints are placed. To give a specific example: why would one expect a word that is 3 distant on WordNet from a word w to have 1/3rd the probability of w in every context? Here's a sanity check that is puzzling: Let R=1, assume that (w_n | history) is not in the training text, but w_n^, which is 3-distant from w_n, is present in the training text. Then, according to Eq.3:
$$P(w_n | history) = 1/3 * P(w_n^| history).$$

How can this be justified? Eq. 4 does average out these unexplained counts over many words, but it is not clear why this averaging is not the only reason why the technique does not fail. The premises on which this technique is built are not justified in the paper. E.g., why is WordNet distance any predictor for N-gram probabilities in the first place? Using the technique presented it should be possible to build a single language model from an ontology that would generalize to corpora containing all words present in the ontology, starting from a uniform language model. How would this model generalize in comparison to the models built from actual corpora that use standard smoothing techniques, or indeed no smoothing techniques?

Section 3.3: Again, "unweighed graph" should be "unweighted graph" to the best of my knowledge. this applies to all instances of the word "unweighed" in the paper.

Section 4: Experimental results: The LMs created are pre-smoothed using Witten-Bell and Kneser-Ney discounting. It is not clear why the proposed algorithm is used to smooth already smoothed N-gram counts. At least this is what comes across from the description in para 2, which is hard to interpret.

Section 4.1: "Unfortunately, the SRILMtoolkit does not support float counts for Kneser-Ney modeling" : there are issues with this statement. Here, and elsewhere, "discounting" or "smoothing" are replaced with the word "modeling". That is not accepted convention. "float counts" could be "floating point counts", although I am not sure why counts should be floating point numbers (unless some normalization is implicit in the word "count")

Section 4.3: "This experiment investigates the use impact" - seems to be an insertion here.

Figure 2 is indecipherable and not explained properly. What are we looking at? Why are there spikes in perplexity? What is the main message of this figure? The same comments hold for Figure 3. In fact the WER% spikes are unusual - good ASR systems do not behave this way under constrained optimization. Improvements in WER% in Table 2 do not seem to be statistically significant.

Section 4 in its entirety is poorly written, with multiple errors and unclear statements. Section 5 is also poorly written - it makes categorical statements such as "We showed that it reduced word error rate (WER) in a statistically significant manner compared with state-of-the-art LM techniques."
This conclusion is questionable given the contents of Table 2 and the lack of explanation thereof. Note also that unsupervised adaptation can actually reverse WER trends in comparable experiments, especially if the WERs variations are not statistically significant.

I suggest the authors simplify the graphs presented, show just one or two significant lines, and explain them properly.

## 7.3 Résumé

Dans cet 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) couverts 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. 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, 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 ».

> Le texte qui suit est une copie exacte de l'acte de conférence référencé ici haut<fnref n="38" />.

<footnote n="38">³⁸ La numérotation des sections, équations, figures, graphiques, tableaux et références a été adaptée pour correspondre à l'ordre retrouvé dans ce document.</footnote>
<figure><img src="image_42.png" /></figure>
## 7.4 Abstract

In this paper, we introduce a novel method of smoothing language models (LM) based on the semantic information found in ontologies that is especially adapted for limited-resources language modeling. We exploit the latent knowledge of language that is deeply encoded within ontologies. As such, this work examines the potential of using the semantic and syntactic relations between words from the WordNet ontology to generate new plausible contexts for unseen events to simulate a larger corpus. These unseen events are then mixed-up with a baseline Witten-Bell(WB) LM in order to improve its performance both in terms of language model perplexity and automatic speech recognition word error rates. Results indicate a significant reduction in the perplexity of the language model (up to 9.85% relative) all the while reducing word error rate in a statistically significant manner compared to both the original WB LM and baseline Kneser-Ney smoothed language model on the Wall Street Journal-based Continuous Speech Recognition Phase II corpus.

**Keywords:** Language modeling, context modeling, ontologies, low-resource speech recognition

## 7.5 Introduction

Language modeling is an integral part of the speech recognition task where the purpose is to try to reliably predict what the speaker is most likely to say next. Today, *n*-gram language modeling remains the dominant technique in automatic speech recognition applications. Formally, we compute the probability of word *w* = *w*<sub>*n*</sub> given its history or context *h*: P(*w*|*h*) where *h* = *w*<sub>*n*−1</sub>, *w*<sub>*n*−2</sub>, ..., *w*<sub>*n*−*N*</sub> - is obtained from counts of very large textual corpus. However, this is not always convenient or practically achievable since new sentences are constantly being created [29]. For example it would be impossible to predict a novel sentence, since its count would be zero. In addition, it is easy to see that as the length of the sentence and/or vocabulary grows, the task of obtaining those counts becomes impractical. The goal of *n*-gram language models then is to simplify the prediction of the *n*-th word based on the *n* − 1 previous words using maximum likelihood estimates (MLE):
$$P_{MLE}(w_n|h) = \frac{C(h, w_n)}{C(h)} \qquad (7.1)$$

Two well-known drawbacks of language modeling with n-grams are its sensitivity to the corpus and data sparseness, i.e. if we train our model on text from Shakespeare, it is evident that the model will not be adequate for the prediction of astrophysical text, namely the count of the word "magnetohydrodynamics" in a Shakespearian work C(magnetohydrodynamics astrophysics | h Shakespeare) is surely equal to 0. That is why multiple approaches exist to either obtain better language models (LM) or smooth existing ones in order to improve their statistical accuracy and generalizability. Notable techniques include discounting, interpolation and various backoff schemes such as Good-Turing Discounting, Witten-Bell discounting [24], Modified Kneser-Ney smoothing [36] or Hierarchical Pitman-Yor language models [138] used to smooth out low-order counts. Variable length n-grams and class-based n-grams [139] also enabled better performance of language models. Other work such as [140]–[143] looks into exploiting the vast amount of text available on the Web and raw n-gram counts such as those provided by Google.

Although we have made significant leaps in the area there is still room for progress. This is particularly true in the case where we don’t have access to training data that relates to the testing or real-world data or that such resources are limited and/or too expensive. It is for these reasons that this work mainly focuses on semantically expanding the information found in small corpus for smoothing language models.

In this work, we introduce a novel method of smoothing language models by exploiting the semantic information found in ontologies. It will be used in combination with Witten-Bell smoothing since the intuition behind this smoothing algorithm is to look at the diversity of contexts in which a particular history occurs: how likely is it to see a new n-gram given a particular history.

This is especially suited for our n-gram count smoothing algorithm since one of its goals is to generate a new set of probable n-gram events that enrich the contextual diversity of the language model.

The contribution of this work is the demonstration that ontological relations can reliably be used for smoothing existing ngram counts as well as producing novel n-gram contexts to enrich the
language model and increase its performance both in terms of perplexity and in an automatic speech
recognition task.

The outline of this paper is as follows. Section 7.6 introduces ontologies and the WordNet ontology
used in this work. Section 7.7 describes our proposed ontological n-gram count smoothing
algorithm. Section 7.8 proceeds with the description of the experiment set-up and the evaluation of
our algorithm. Finally, in section 7.9, we conclude and discuss our results.

7.6 Ontologies

Ontologies are used to relate concepts in a hierarchical and relational fashion that ultimately
describe the meaning of terms. Logical and philosophical entities can be grouped contextually with
the use of named relations. Figure 7.1 shows a portion of the entry for the ontology of a cat as it
relates to rodents and birds. In this example, solid lines represent inheritance, dashed lines such as
the ones connecting cat with bird and rodents represent functional relationships and the dotted lines
between vertebrate and spine represent inherited properties.

7.6.1 The WordNet ontology

We used the popular WordNet [88] as our base ontology from Princeton University. It is essentially
a large lexical database of English. The main relation between defined words is synonymy, the state
of being a synonym [88]. WordNet lemmas are classified by part of speech: adjectives (21,479),
adverbs (4,481), nouns (117,798) and verbs (11,529) for a total of 155,287 senses; however since
many words are found in multiple parts-of-speech, a total of 147,278 unique indexed words are
found in the ontology.

7.7 Ontology-based n-gram smoothing

In this section we introduce our novel technique to improve the performance of *n*-gram smoothing.
One of the problems with current language modeling techniques, as previously stated, is that they
do not necessarily generalize themselves to words of the same semantic class/sub-class. Counts for
words such as cat, dog, mouse, etc., all being animals, could be proportionally smoothed by the *n*-
gram entry for *lamb* from the example of section 2.2. The same could be said about relational
markers between objects where similar relations could be smoothed with the help of well established ones. As such, we propose a method of smoothing the *n*-gram counts by leveraging the latent information stored in ontologies. Ontologies are used to relate concepts in a hierarchical and relational fashion. As was stated in section 7.6, entities can be grouped logically and/or philosophically in a contextual fashion through the use of named and weighted relations. Figure 7.1 shows a portion of the WordNet ontology where the ontological distance from cat = 1.

Therefore, by studying the information contained within, we are able to smooth our *n*-gram language model by smoothing its probabilities with those of weighted *n*-grams of related terms, i.e., use the counts of related *n*-grams $C(w_r|h)$ for each word $w_r \in W_R$ related to $w_n$ and its context *h* to smooth the counts $C(w_n|h)$, where $W_R$ is a vector of *R* words related to $w_n$. Inversely,

<figure><img src="image_43.png" /><figcaption>Figure 7.1: Sample of the full ontology as related to a cat. The size of the nodes represent their degree of connectedness and their color their part of speech class: adjectives (black), adverbs (not shown, white), nouns (light gray) and verbs (gray). The colors of the edges represent the type of relation between nodes. Note that the length of the lines have no meaning other than to improve the clarity of the illustration.</figcaption></figure>
to smooth out zero counts, we can use the information from known $C(w_n|h)$ counts to generate semantically probable unseen $C(w_r|h)$ smoothed counts.

We believe that this is a reasonable assumption, especially for spoken dialogue where speakers can interchange words for related terms that come to mind more quickly. Furthermore, since this work seeks to help reduce the data sparseness of counts that are used for smoothing we propose the following technique based on interpolation to smooth low-resource language models by intelligently adding information not seen before.

### 7.7.1 Bin-Based Ontological Smoothing

The Bin-Based Ontological Smoothing Language Model (BBOSLM) smoothing technique consists of creating bins $B_d$ of smoothed counts taking into account all words found at a distance $d$, the shortest path (number of edges) in the ontology from words $w_n$ and $w_r$, from the original n-gram counts and where $d \le 1 \le d_{max}$ and $d_{max}$ is the maximal distance from $w_n$ that is considered in the ontology. For example, in figure 1, the distance $d(cat; tiger) = 1$, $d(feline; catfish) = 2$, etc. More formally, for each $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_{r=1}^{R_d} \frac{C(w_r|w_{n-N+1}^{n-1})}{d} \qquad (7.2)$$

where $R$ is the total number of words related to $w_n$ up to $d_{max}$. In practice, a vector of related words is pre-computed at the start of the program using a modified form of depth-limited iterative deepening depth-first search. As such, $R$ is the number of linked terms for each word and $R_d \le R$ is the number of related terms at distance $d$. The premise behind the use of the shortest path as a measure of conceptual or semantic distance is illustrated in [91], namely that “...when is-a hierarchies are defined ... shortest path length can be used to measure conceptual distance between concepts”. The ontologically generated counts are then used to generate language models for each bin $LM_{B_d}$. Finally, these language models are interpolated into the final smoothed BBOSLM:

$$P'(w_n|w_{n-N+1}^{n-1}) = \lambda_1 P(w_n|w_{n-N+1}^{n-1}) + \sum_{d=1}^{D} \lambda_{d+1} P_{B_d}(w_n|w_{n-N+1}^{n-1}) \qquad (7.3)$$
where $D = d_{max}$ is the maximum edge distance from the original in the ontology, $P_{B_d}(w_n|w_{n-N+1}^{n-1})$ are the probabilities obtained from the smoothed counts in each bin and where $\lambda$ are the mixture weights and

$$ \sum_{i=1}^{D} \lambda_{i} = 1 $$

are obtained with the help of Powell optimization.

### 7.7.2 Ontological smoothing algorithm

The first step in the ontological smoothing process is to convert the ontology to an efficient graph format for processing. Given an ontology $O$ (WordNet in this case) and part of speech classes $POS$, we convert the ontology to a directed graph $G$ where each node $N$ is a lexeme (lemma + forms). Each node can be from multiple classes, e.g. cat is both a noun and a verb and each edge $E$ represents a relation between two nodes.

The second step is to tag our corpus's terms by their part-ofspeech. For this task, we used the Penn-State TreeTagger [137]. This is to preserve the meaning of the n-gram counts. For example, we potentially wouldn't want to smooth the n-gram entry of a verb with that of a noun. As per [91] we restrict the search space to synonymous terms for this work. Once the corpus is tagged, we proceed with the counting task using the SRILM toolkit [93].

Our algorithm operates in $D$ passes: each pass creates a bin containing the smoothed counts for distance $d$ using (7.2). Each pass also adds unseen $w_r|h$ events in order to reduce the effects of limited corpus. Since the number of new counts generated can be particularly high given a large distance metric, we parallelized our algorithm. This gives us a speed-up of up to 52% on four threads with $d_{max} = 5$ for the whole smoothing process.

### 7.7.3 Ontology search algorithm for R related terms

Since the search space of the ontology is considerable we needed an efficient algorithm to look for the related terms of each ngram entry. The fact that we use an unweighted graph enabled us to avoid the inherent challenges of searching weighted directed graphs. The algorithm is a depth-limited form of unweighted iterative deepening depth-first search. Basically, as we progress
through the graph each relation is marked gray; we then recursively explore each unmarked child
node (we do not return to it since it has already been seen at a lower level), and thus the “shortest”
path to it is already known. This greatly reduces the cost of exploring the ontology all the while
guaranteeing optimal paths for each relation.

7.8 Experiments and results

7.8.1 Limited resources experimental setup

The experiments reported in this paper were performed using the Wall Street Journal-based
Continuous Speech Recognition Phase II corpus (WSJ1). We train our language models on the
76,136 sentences provided by the standard WSJ1 training sets for a total of 1,243,340 words. For
the evaluation we restricted ourselves to the Hub 1 and Spoke 1 tests (10,347 words in 582
sentences) without filtering out sentences with out-of-vocabulary words (OOV rate of 5.41%).

The SRILM toolkit and HTK toolkit [119] were used for our experiments for language modeling
and automatic speech recognition respectively. We obtain raw training counts using the SRILM
toolkit. These raw counts are then used to generate ontologically smoothed count bins for each
distance group, note that, as per eq. (7.2), the majority of the counts are fractional counts. Then,
WittenBell LMs were created for each bins. Finally, a mixture-based language model is created by
mixing up each bin-based LM with the original Witten-Bell LM. Optimal mixup weights were
obtained through the use of Powell's optimization algorithm [101] using the SciPy library [118]
with the objective function defined as the word error rate of the held-out development set consisting
of 4,340 sentences for a total of 71,759 words. Unfortunately, the SRILM toolkit does not support
fractional counts for Kneser-Ney smoothing and as such, we cannot properly interpolate the
baseline KN model with our bins.

Perplexity and word error rate (WER) are used to measure the performance of our language modeling technique. For the acoustic models, we use the well-known recipe from Vertanen [120]. Our model is trained by using all of the WSJ1 training data using the 40 phones set of the CMU dictionary. Cross-word tied-state triphones with 32 Gaussian mixtures per state and 64 Gaussian mixtures per silence state are eventually generated. The acoustic models are represented by Mel Frequency Cepstral Coefficients with energy, delta and acceleration (MFCC\_E\_D\_A) for a total of
a 39-dimensional feature vector. The HDecode tool with parameters for the pruning beam width, word insertion penalty, and the language model scale factor of 220.0, -4.0, and 15.0 respectively were used for the automatic speech recognition test.

7.8.2 Perplexity evaluation

Perplexity evaluation was performed on the Hub 1 (read WSJ baseline) and Spoke 1 (language model adaptation) portion of the WSJ1 corpus which consist of 582 sentences and 10,347 words.

The standard 20,000-word WSJ closed-vocabulary was used for the evaluation and backed-off trigram language models were generated using SRILM with the -float-counts option enabled.

The average path length of the ontology is 59.24 with a network diameter of 15 measured using
the Gephi toolkit [144]. The network diameter is a measure of the maximum distance between any
two pairs in the graph. Since it would be too computationally intensive to fully explore each node,
we chose to study the effects of $d_{max}$ from 1 to 5. From the ~346,000 original raw counts we end
up with ~15,284,000 smoothed counts for $B_5$. Figure 7.2 shows the evolution of the language
model perplexity throughout the Powell optimization algorithm for the Bin-based ontological
smoothing against the baseline models trained using Witten-Bell (WB) smoothing and the original
Kneser-Ney (UKN) smoothing. Note that we were not able to include results for Modified
KneserNey (MKN) smoothing as the SRILM toolkit kept computing negative discount parameters
for the trigrams. Results for both single and multiple bins mixup are provided. Figure 7.2 shows a
summary of the best results obtained. As was expected, our technique is able to significantly reduce
the perplexity of the baseline language models with the best model showing maximal perplexity
reduction of 9.85% for the WB LM. We were able to get very close to the perplexity of Kneser-
Ney discounting for $1 \le d \le 5$ (Table 7.1). However this is to be expected as the training
<figure><img src="image_44.png" /><figcaption>Figure 7.2: Perplexity evolution during the Powell WER optimization process to determine the best BBOSLM bin mixup weights for 20K word trigram LMs trained on the WSJ1 training corpus and conditioned the WSJ1 development corpus. The spikes are due to the algorithm trying to see if it is in a local optimum.</figcaption></figure>

process did not explicitly look at minimizing perplexity but rather minimizing Word Error Rates. This is consistent with the literature as it is well known that a reduction in perplexity will not always translate in improvements in automatic speech recognition tasks. The spikes in perplexity are due to the Powell algorithm exploring the bounded space to see if it is not currently in a local optimum. This is encouraging since it demonstrates that our technique can compete with state-of-the-art language modeling techniques.
<table><caption>Table 7.1: Comparison of perplexity on WSJ1 Hub 1 and Spoke 1 evaluation corpus using 20K word trigrams using best WER performing single and multiple bins mix-up.</caption><thead><tr><th>Language Model</th><th>Perplexity</th></tr></thead><tbody><tr><td>Witten-Bell</td><td>142.61</td></tr><tr><td>Kneser-Ney</td><td>117.15</td></tr><tr><td>BBOSLM</td><td>-</td></tr><tr><td>d = 1</td><td>137.46</td></tr><tr><td>d = 2</td><td>137.5</td></tr><tr><td>d = 3</td><td>137.92</td></tr><tr><td>d = 4</td><td>137.54</td></tr><tr><td>d = 5</td><td>137.53</td></tr><tr><td>1 ≤ d ≤ 2</td><td>137.14</td></tr><tr><td>1 ≤ d ≤ 3</td><td>128.55</td></tr><tr><td>1 ≤ d ≤ 4</td><td>129.45</td></tr><tr><td>1 ≤ d ≤ 5</td><td><strong>122.49</strong></td></tr></tbody></table>

### 7.8.3 Automatic speech recognition experiments

This experiment investigates the performance of the BBOSLM on word error rate in an automatic speech recognition task. Much like the perplexity evaluation, we provide the WER results for single bin mixup and multiple bins mixup in relation to the LM perplexity optimization process. The optimization process was run three times with evenly distributed starting $\lambda$ values, Figure 7.3 shows the optimization process for the best performing final models and starting with $\lambda_0 = 0.9$. Final $\lambda_1$ from eq. (7.3) values for the two best performing LMs, $BBOSLM_{d3}$ for single bin mixup and $BBOSLM_{d1-d5}$ for multiple bin mix-up, are 0.9962 and 0.8913 respectively. Globally, results show (Table 7.2) that the best performing LM are the ones mixing-up multiple smoothed counts bins. These results are confirmed by every statistical significance test available in the NIST Scoring Toolkit: a statistically significant reduction (mean $p = 0.001$) in word error rate of 6.8% relative for $BBOSLM_{d1-d5}$ and statistically significant reduction (mean $p = 0.01$) for $BBOSLM_{d4}$ with a
<figure><img src="image_45.png" /><figcaption>Figure 7.3: WER (%) evolution of the BBOSLM during the WER optimization process on WSJ1 development corpus using 20K word trigrams. The “large” spike in the training process is due to the Powell algorithm jumping in λ values to see if it is in a local optimum.</figcaption></figure>

<table><caption>Table 7.2: ASR performance comparison on WSJ1 Hub 1 and Spoke 1 evaluation corpus using 20K word trigrams using single and multiple bins mix-up.</caption><thead><tr><th>LMS</th><th>PPL</th><th>SUB</th><th>DEL</th><th>INS</th><th>WER</th></tr></thead><tbody><tr><td>WBLM</td><td>142.61</td><td>22.43</td><td>5.89</td><td>2.64</td><td>30.96</td></tr><tr><td>KNLM</td><td>117.15</td><td>21.87</td><td>7.71</td><td>1.41</td><td>30.98</td></tr><tr><td>BBOSLM</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>d = 1</td><td>137.46</td><td>21.2</td><td>6.65</td><td>1.72</td><td>29.56</td></tr><tr><td>d = 2</td><td>137.5</td><td>21.13</td><td>6.67</td><td>1.77</td><td>29.57</td></tr><tr><td>d = 3</td><td>137.92</td><td>20.99</td><td>6.67</td><td>1.78</td><td>29.44</td></tr><tr><td>d = 4</td><td>137.54</td><td>21.08</td><td>6.73</td><td>1.74</td><td>29.55</td></tr><tr><td>d = 5</td><td>137.53</td><td>21.05</td><td>6.79</td><td>1.73</td><td>29.57</td></tr><tr><td>1 ≤ d ≤ 2</td><td>137.14</td><td>21.18</td><td>6.65</td><td>1.73</td><td>29.56</td></tr><tr><td>1 ≤ d ≤ 3</td><td>128.55</td><td>20.69</td><td>6.76</td><td>1.58</td><td>29.03</td></tr><tr><td>1 ≤ d ≤ 4</td><td>129.44</td><td>20.72</td><td>6.74</td><td>1.6</td><td>29.06</td></tr><tr><td>1 ≤ d ≤ 5</td><td>122.49</td><td>20.23</td><td>7.03</td><td>1.59</td><td>28.85</td></tr></tbody></table>
considerable reduction in insertion and substitution rates compared to the baseline Witten-Bell
discounted LM.

7.9 Conclusion and discussion

In this paper, we introduced an original method of preprocessing and smoothing n-gram counts based on the semantic information found in ontologies for use in limited resources automatic speech recognition. It exploits the relations found in ontologies to create bins of new n-gram events related to existing n-gram events. These bins are transformed into language models (LM) and then mixed-up with the original LM. Experiments demonstrate that our smoothing technique reduced the perplexity of a given language model by up to 9.85% when considering bins of related words with a maximal ontological distance of up to 5. In addition, we evaluated our language models on the Hub 1 and Spoke 1 tasks of the Wall Street Journal-based Continuous Speech Recognition Phase II corpus. We showed that it reduced word error rate (WER) in a statistically significant manner compared to Kneser-Ney discounting (p = 0.001). The fact that we were able to obtain statistically significant performance increase indicate that it shows promise as a tool for language model smoothing, especially when textual resources are sparse. Future work will look to incorporate different ontological distance metrics such as those proposed by Jing et al. [145] as well as exploring information theory based schemes to weight the different relations between words described by the ontology.
# 8 EVALUATION OF GRAPH METRICS FOR OPTIMIZING BIN-BASED ONTOLOGICALLY SMOOTHED LANGUAGE MODELS

Évaluation de l'utilisation des mesures de graphes pour l'optimisation des modèles de langage basé sur le lissage par groupements ontologiques

Y. Benahmed<fnref n="1" />,<fnref n="2" />, S-A. Selouani<fnref n="2" /> et D. O'Shaughnessy<fnref n="1" />

**Article soumis à :** EUSIPCO 2016

**Lieu de la conférence :** Budapest, Hongrie

**Accepté**

**Date d'acceptation :** 28 mai 2016

## 8.1 Contribution des auteurs :

**Yacine Benahmed:** (candidat)

Écriture de l'article, développement des logiciels et programmes, expérimentation, analyse des données, préparation des graphes, des figures et des tableaux.

**Douglas O'Shaughnessy:** (directeur)

Conseils techniques et théoriques, conseils de rédaction, édition, coauteur, corrections.

**Sid-Ahmed Selouani:** (codirecteur)

Conseils techniques et théoriques, édition, coauteur, corrections.

<footnote n="1">¹INRS-EMT, 800 de la Gauchetière O, H5A 1K6, Montréal, Québec, Canada</footnote>

<footnote n="2">²LARIHS Lab. Université de Moncton, campus de Shippagan, New-Brunswick, Canada</footnote>
## 8.2 Commentaires des évaluateurs

La majorité des commentaires des évaluateurs ont été pris en considération lors de la révision finale de la version de l'article présenté dans cette section.

### 8.2.1 Évaluateur no 1

*Comments and Recommended Changes:*

In this work, the authors present a continuation of previous work regarding bin-based ontologically smoothed language models (BBOSLM), which have been first published at ICASSP 2014. The additions include the evaluation of various graph measures for distance calculations between words in BBOSLM, evaluating the entire powerset of bins for interpolation with the background LM, as well as testing the approach on more corpora/data.

While incorporating the various graph measures did lead to slight regressions over the unmodified BBOSLM, it is still an interesting approach. By evaluating the whole powerset of bins, it could be shown that certain bins do not contribute to gains. Overall, significant improvements in WER over the baseline model could be achieved.

It might be interesting to see the WER results of the different methods for the single evaluation corpora. Maybe a certain method/graph measure improves on a certain part of the test data?

To better assess the quality of the ASR baseline, it would be helpful to quote state-of-the-art results from other groups as well, if they are accessible.

### 8.2.2 Évaluateur no 2

*Comments and Recommended Changes:*

This work presents a set of methods for optimizing bin-based ontologically smoothed language models (BBOSLM). The main novelty in this work is the use of different graph measures (Weighted degree, HITS, PageRank, Modularity) to optimize ontology distances between words when estimating the BBOSLM.

Bin-based ontological smoothing is a relatively new approach within language modeling. Therefore it is nice that the authors devoted a section for explaining this method separately.
In terms of results, BBOSLM offers some improvements (WER, perplexity) compared to standard smoothing methods such as Witten-Bell and Kneser-Ney. The graph measures, which were the novelty in this work, did not give any additional improvements compared to the original BBOSLM approach.

How many bin configurations were evaluated in the ASR experiments? The difference in performance between the different BBOSLM models seem quite small. It would be beneficial to also include statistical significance tests. It would also be good if the authors could more specifically elaborate how graph measures could still be useful for improving performance of BBOSLM models.

### 8.2.3 Évaluateur no 3

**Comments and Recommended Changes:**

The differences in perplexity are rather small, as well as the differences in WER. Moreover better error rates are obtained with models having a perplexity worse than that of the baseline (KNLM).

However, only selected best results appear in Table II, and most of them correspond to combinations that do not appear in Table 1.

This let the reader wonder on the significance and reliability of the results. No confidence interval, nor any significant test are reported. Would the same 'best' configuration also be the best on another data set?

Is exactly the same behavior observed on the various subsets (spoke 1, spoke 2 and spoke 9)?

### 8.2.4 Évaluateur no 4

**Comments and Recommended Changes:**

The authors propose in this article to use graph metrics to capture additional semantic or relational information found in ontologies. The paper is well written, enough information being given to understand the general idea of the paper. The paper is well written. I particularly appreciated the description of all training parameters.

I have few questions regarding the paper :
- Could the authors provide the best results results (in terms of perplexity and WER) of the considered corpus?

- Could the authors give more information about the reason why not that particular bins (1, 3 and 5) perform better WER than all the bins? Regarding to perplexity, this is not observed since all bins used together allows to get the lowest perplexity, why?

Are the gains significant?

## 8.3 Résumé

Cet article examine l'utilisation de mesures tirées de la théorie des graphes pour améliorer les performances d'un algorithme de lissage de modèle de langage. Le *Bin-Based Ontological Smoothing* a été utilisé avec succès pour améliorer la performance de modèles de langage dans des tâches de reconnaissance automatique de la parole. Cette technique utilise les ontologies pour estimer la vraisemblance de nouvelles expressions pour un modèle de langue donné. 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 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. L'ensemble complet de l'interpolation des groupements est évalué. 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. Finalement, la modularité, le PageRank et l'HITS sont prometteurs et méritent une étude plus approfondie.

> Le texte qui suit est une copie exacte de l'acte de conférence référencé ici haut<fnref n="39" />.

<footnote n="39">³⁹ La numérotation des sections, équations, figures, graphiques, tableaux et références a été adaptée pour correspondre à l'ordre retrouvé dans ce document.</footnote>
## 8.4 Abstract

This paper investigates the use of graph metrics to further enhance the performance of a language model smoothing algorithm. Bin-Based Ontological Smoothing has been successfully used to improve language model performance in automatic speech recognition tasks. It uses ontologies to estimate novel utterances for a given language model. Since ontologies can be represented as graphs, we investigate the use of graph metrics as an additional smoothing factor in order to capture additional semantic or relational information found in ontologies. More specifically, we investigate the effect of HITS, PageRank, Modularity, and weighted degree, on performance. The entire power set of bins is evaluated. Our results show that the interpolation of the original bins at distances 1, 3 and 5 resulted in an improvement in WER of 0.71% relative over the interpolation of bins 1 to 5. Furthermore, modularity, PageRank and HITS show promise for further study.

## 8.5 Introduction

Language modeling is a crucial part of automatic speech recognition (ASR) systems as well as of many other tasks such as part-of-speech tagging, natural language processing, document classification, information retrieval, etc. More specifically for ASR however, language modeling enables recovering the probability of a sentence or sequence of words $S = w_1, ..., w_i$ given an acoustic signal $A$, that is

$$P(S|A) = P(A|S)P(S) P(A),$$

where $P(S)$ represents the language model (LM), the probability of the sentence $S$. The goal of n-gram language models is to simplify the prediction of the i-th word based on the n-1 previous words, essentially a Markov chain of order $(n-1)$, using maximum likelihood estimates (MLE):

$$P_{MLE}(w_i|h) = C(h, w_i)C(h). \qquad (8.1)$$
8.5.1 Motivation

Two well-known drawbacks of language modeling with ngrams are its sensitivity to the corpus
and data sparseness, i.e., if we train our model on text from Shakespeare, it is evident that the
model will not be adequate for the prediction of astrophysical text. That is why multiple approaches
exist to either obtain better language models (LM) or smooth existing ones in order to improve
their statistical accuracy and significance. Notable techniques include discounting, interpolation
and various backoff schemes such as Good-TuringDiscounting [35], [146], Witten-Bell smoothing
[36], Modified Kneser-Ney smoothing [36] or Hierarchical PitmanYor language models [138] used
to smooth out low-order counts. Another drawback of n-gram language models is that they only
can capture natural language semantics to a certain extent, mainly by capturing direct co-
occurrences which do not completely reflect the co-occurrence networks from natural language.
This is well documented in work by Biemen et al. [147]. Furthermore, work by Yan et al. [148]
provide interesting insights on the use of ontologies in language modeling but only concentrates
on document retrieval task. This is why bin-based ontologically smoothed language models
(BBOSLM) [86] were proposed to exploit the semantic information found within the WordNet
[88] ontology.

Graph theory, or network analysis, has gathered a lot of research interest over the last few decades. It can be seen as a powerful tool to quantify and qualify the importance and influence of nodes within a graph or detect hidden communities of interest. It is widely used in natural language processing for modeling relations between words. It is this ability that we are interested in examining in this work. We propose to study the effect of different network metrics used as additional weighting factors to the distance based similarity measure used in the original BBOSLM.

8.5.2 Contribution

The contribution of this work is the evaluation of the use of graph measures in ontology distance
optimisation between words in BBOSLM. Furthermore, whereas previous work restricted itself to
evaluating a linear incrementation of bins combination, we extend this work by evaluating the
entire powerset of bins interpolated with the original Witten-Bell smoothed language model. That
is, we look at the entire power set (155 distinct combinations) of bins (described in Section 8.6
below) interpolated with the original language model. We also extend the evaluation to the Spokes 2 and 9 of the Wall Street Journal Continuous Speech Recognition Phase II corpus for a total of 1285 sentences up from the 582 sentences used in the original work.

The outline of this paper is as follows. In Section 8.6.2, network analysis and the graph metrics of interest are briefly presented. Section 8.6.4 describes the bin-based ontological n-gram count smoothing algorithm with the additional $\alpha$ weighing factor. Section 8.7 proceeds with the description of the experiment set-up and the evaluation of the use of different network metrics. Finally, in section 8.8, we conclude and discuss our results.

## 8.6 Bin-based ontological smoothing

Bin-based Ontological Smoothing [86] was proposed in order to smooth counts based on the ontological distance $d$ between words found in an ontology, namely the WordNet ontolology. As stated in the introduction, the intuition behind this proposed technique was to exploit the relations found between words in ontologies to try to capture the fact that a given message could be expressed in different ways and that similar messages could be expressed in a similar way. For example, “the dog barked” and “the bird sang” are both very similar and different at the same time. For this, we consider the relations between words in the WordNet as an “is-a” hierarchy. This makes it possible to assume that the shortest path between words can be used as a simple measure of conceptual/semantical distance [91].

In Bin-Based Ontological Smoothing, we begin by generating smoothed bins $B = \{B_1, B_2, ..., B_{d_{max}}\}$ of smoothed n-gram counts that take into account all of the related words $\{(w_i, w_r) : \min(d(w_i, w_r)) = d\}$, completing the ngram context $w_{i-1}^{i-n+1}$. Then, let

$$B_d = \{(w_i^{i-n+1}, w_r | w_{i-1}^{i-n+1}) : \min\{d(w_i, w_r) = d\}\}$$

be the bin $B_d$ of smoothed n-grams where $w_i^{i-n+1}$ is the original n-gram, $w_r$ $w_{i-1}^{i-n+1}$ is the set of related n-gram with ontological distance $d$ between the original word $w_i$ and related word $w_r$. We than generate smoothed counts following equation (8.2):
$$C_{B_d}(w_i|w_{i-1}^{i-n+1}) = \frac{1}{dR} \sum_{w_r} C(w_r|w_{i-1}^{i-n+1}) \qquad (8.2)$$

where $R$ is the total number of words related to $w_i$ up to the maximal distance $d_{max}$ such that $R = |\{(w_i, w_r): d(w_i, w_r) \le d_{max}\}|$ and $d$ is the current distance. In practice we pre-compute a vector of related words for each $w_i$ up to the maximum distance of interest $d_{max}$ with a modified depth-limited iterative deepening depth first search. This greatly reduces the computational complexity of generating the smoothed counts. We then use those new smoothed counts to derive statistical language models using available complimentary smoothing techniques. However, previous work [86] found that Witten-Bell smoothing produced better overall results than Kneser-Ney-based smoothing. Finally, these language models are linearly interpolated into the final smoothed Bin-based Ontological Smoothed LM:

$$P'(w_i|w_{i-1}^{i-n+1}) = \lambda_0 P(w_i|w_{i-1}^{i-n+1}) + \sum_{d=1}^{d_{max}} \lambda_d P_{B_d}(w_i|w_{i-1}^{i-n+1}). \qquad (8.3)$$

where $d_{max}$ is the maximum edge distance from the original in the ontology, $P_{B_d}(w_i|w_{i-1}^{i-n+1})$ are the probabilities obtained from the smoothed counts in each bin and where $\lambda$ are the mixture weights and

$$\sum_{i=0}^{d_{max}} \lambda_i = 1$$

can be obtained with the help of any linear optimization algorithm.

### 8.6.1 Ontological smoothing algorithm

The first step in the ontological smoothing process is to convert the ontology to an efficient graph format for processing. Given an ontology $O$ (WordNet in this case) and part of speech classes POS, we convert the ontology to an undirected graph $G$ where each node $N$ is a lexeme (lemma + forms). Each node can be from multiple classes, e.g. cat is both a noun and a verb and each edge $E$ represents a relation between two nodes.

The second step is to tag the corpus's terms by their part-of-speech. For this task, we used the Penn-State TreeTagger [137]. This is to preserve the meaning of the n-gram counts. For example,
we want to avoid smoothing the ngram entry of a verb with that of a noun. As per [91] we restrict the search space to synonymous terms for this work. Once the corpus is tagged, we proceed with the counting task using the SRILM.

The smoothing algorithm then operates in dmax passes: each pass creates a bin $B_d$ containing the smoothed counts for distance $d$ using (8.2). As stated in section II each pass also adds unseen $w_r|h$ events in order to smooth zero count n-grams.

## 8.6.2 Network Analysis

Graph theory or network analysis has gathered a lot of research interest over the last few decades. It can be seen as a powerful tool to quantify and qualify the importance and influence of nodes within a graph or detect hidden communities of interest. Its use in many areas of research, be it biology, sociology, economy etc. speaks volumes of its versatility in modeling relations. It is this ability that we are interested in studying in this work. We propose to study the effect of different network metrics used as additional weighting factors to the distance based similarity measure used in the previous work. More specifically, we investigate if using HITS Centrality, PageRank Centrality, Modularity, and a baseline weighted degree can improve the performance of the smoothing method.

### 8.6.2.1 Weighted Degree

Degree and its ponderated form, Weighted degree, are the simplest measures of centrality in graphs. It essentially counts the number of edges incident to a node and is defined as:

$$WD_i = \sum_j A_{ij}. \qquad (8.4)$$

where $WD_i$ is the weighted degree of edge $i$, the sum of the weight of all edges attached to it, and $A_{ij}$ is the edge weight between nodes $i$ and $j$. This equation can easily be rewritten with respect to a word network as follows:

$$WD(w_i) = \sum_j A(w_i, w_j). \qquad (8.5)$$
That is, $WD(w_i)$ is the weighed degree of word $w_i$ and $A(w_i, w_j)$ is the edge weight between words $w_i, w_j$.

### 8.6.2.2 HITS

The HITS (Hyperlink-Induced Topic Search) algorithm [96] rates Web pages by analysing their links. It gives a list of hub and authority centralities for each node in a graph. The relation between hubs and authorities is maintained by the mutually recursive algorithm

$$ auth(p) = \sum_{i=1}^{n} hub(i), \quad hub(p) = \sum_{i=1}^{n} auth(i), \qquad (8.6) $$

which can be rewritten as:

$$ auth(w_i) = \sum_{w_j} hub(w_j), \quad hub(w_i) = \sum_{w_j} auth(w_j), \qquad (8.7) $$

where $auth(w_i)$ and $hub(w_i)$ are the authority and hub scores of word $w_i$ based respectively on the hub and authority score of connected words $w_j$ (inbound for authority and outbound for hub). That is, good hubs point to authoritative words and authoritative words are pointed by good hubs. Each node starts with a value of 1 for both authority and hub, we update $auth$ values followed by $hub$ values. They are then are normalized respectively by the square root of the sum of their squares and the process repeats until the variation falls below a set threshold.

### 8.6.2.3 PageRank

The PageRank [97] algorithm is an iterative algorithm that gives the probability of a random surfer clicking its way randomly to any given web page. We assume word $w_i$ has words $w_j... w_{j+n}$ which point to it. The PageRank of a word $w_i$ is then given as follows:

$$ 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 (8.8) $$

where $PR(w_i)$ is the PageRank of word $w_i$ and $L(w_j)$ is the number of words linked by $w_j$. The parameter $\delta$ is a damping factor which can be set between 0 and 1 and is usually set to $\delta = 0.85$, $w_j \in M(w_i)$ is defined as the set of words linked by word $w_i$ and $N$ is the total number of words in the vocabulary.
One advantage of the PageRank algorithm is that it can also be applied to undirected graphs. The assumption of this work is that a low PageRank suggests a low probability of substitution of word $w_i$ for word $w_j$ and is then used as a weighing factor with $0 \le PR \le 1$.

### 8.6.2.4 Modularity

Modularity is a technique used for the detection and characterization of community structure in any given network. The quality $-1 \le Q \le 1$ of such communities c is defined by their Modularity defined in [98] such that:

$$Q = \frac{1}{2m} \sum_{w_i, w_j} \left[ A_{ij} - \frac{D(w_i)D(w_j)}{2m} \right] \sigma(c(w_i), c(w_j)), \qquad (8.9)$$

where $A_{ij}$ is the edge weight between words $w_i$ and $w_j$, $D(w)$, the (unweighted) degree of word $w$, the $\sigma$-function $\sigma(u, v)$ is 1 if $u = v$ and 0 otherwise (in other words, 1 if they are in the same community, 0 otherwise). For this work, modularity is used to penalize words that are from different communities c, that is, when $c(w_i) \neq c(w_j)$. We use it to try to uncover unknown topics or lemma classes within the ontology and penalize counts from words in different communities.

## 8.6.3 The WordNet ontology

The WordNet [88] ontology is used in this work. It is a essentially a large lexical database of English. The main relation between defined words is synonymy, the state of being a synonym [88]. It was chosen due to it's well documented nature and widespread use in the literature.

## 8.6.4 Weighting adjustments

The basis for this work is the hypothesis that less important words (essentially less connected words) should contribute less to smoothing counts of n-grams and more important words should contribute more. For this work, we consider the ontology as an undirected graph and we use the previously mentioned measures from network theory to extract meaningful information. It is then used to compute adjustment weights from an $\alpha$-function for each ontological relation between words $w_i$ and $w_j$. As such, this work proposes the following modification to the original equation (8.2):
$$CB_d(w_i|w_{i-1}^{i-n+1}) = \frac{1}{dR} \sum_{w_r} \alpha(w_r) C(w_r|w_{i-1}^{i-n+1}), \qquad (8.10)$$

where $\alpha(w_r)$ is the adjustment weight for related word $w_r$ for the given network metric function. It represents the importance of $w_r$ within the ontology. Furthermore, for the special case of Modularity, we define the $\alpha$-function as such:

$$\alpha_{\text{Mod}}(w_i, w_r) = \begin{cases} 1, & \text{if } c(w_i) = c(w_r) \\ \frac{1}{e}, & \text{otherwise} \end{cases}.$$

All graph metrics were computed using Gephi [144] and as such, the standard algorithms for HITS ($\epsilon = 1.0E-4$) and PageRank (damping factor $\delta = 0.85$) were used. A notable exception being the Modularity computation, which uses the fast algorithm for unfolding communities proposed by Blondel et al. [149]. It is an efficient algorithm that results in high modularity partitioning. To speed up computation time, all properties are pre-computed and stored in a hashkey based binary storage matrix.

# 8.7 Experiments and results

## 8.7.1 Experimental Setup

The experiments reported in this paper were performed using the Wall Street Journal-based Continuous Speech Recognition Phase II corpus (WSJ1). The training of our models uses the 76k sentences provided by the basic WSJ1 training sets for a total of 1.2M words. For the evaluation we used the Hub 1 (read WSJ baseline), Spoke 1 (language model adaptation), Spoke 2 (domain-independence) and Spoke 9 (spontaneous WSJ dictation) test data (23k words in 1285 sentences) without filtering out sentences with out-of-vocabulary words. The standard 20K words WSJ closed vocabulary (OOV rate of 5.64%) was used for the evaluation and backed-off trigram language models were generated using SRILM with the -float-counts option enabled for the bins.

The SRILM toolkit [93] and HTK toolkit [119] were used for language modeling and automatic speech recognition respectively. We first generated the raw training counts using the SRILM toolkit. These raw counts are then used to generate ontologically smoothed floating point raw count bins for each distance group. Then, Witten-Bell LMs were created for each bin. Finally, a mixture-
based language model was created by mixing up each bin-based LM with the original Witten-Bell LM. Mixup weights were obtained through the use of Powell's optimization algorithm [101] using the SciPy library [118] with the objective function defined as the perplexity (PPL) of the held-out development set, consisting of 4.3k sentences. We chose the Powell optimization algorithm instead of the EM algorithm provided by compute-best-mix script from the SRILM toolkit because of empirical observations where we consistently obtained better results by using the Powell algorithm. Secondly, the obtained mixture weights do not achieve the same level of performance (in terms of perplexity and ASR (without bayes)) that we get from the use of the Powell algorithm. Unfortunately, the SRILM toolkit does not support float counts for Kneser-Ney modeling and as such attempts to mix KN-based bins with the original KN LM resulted in severe performance degradation.

Perplexity (PPL) and Word Error Rate (WER) are used to compare the performance of the different language models. For the acoustic models, we used the recipe from Vertanen [120] with additional discriminative training (MPE criterion). Our model is trained by using all of the WSJ1 training data using the 40 phones set of the CMU dictionary. Full details of the configuration used can be found in [86]. The HDecode tool with parameters for the pruning beam width, word insertion penalty, and the language model scale factor of 220.0, -4.0, and 15.0 respectively were used for the ASR test.

The average path length of the ontology is 59.24 with a network diameter of 15 measured using the Gephi toolkit. The network diameter is a measure of the maximum distance between any two pairs in the graph. Since it would be too computationally intensive to fully explore each node, we study bins with words that are up to $d_{max}$ = 5. From the ~ 346k original raw counts we end up with ~ 15.3M smoothed counts for $d_{max}$ = 5.

## 8.7.2 Perplexity evaluation

Table 8. shows a summary of the best results obtained (due to the number of different combinations (155), only the best results are presented). These results show that our technique is able to significantly reduce the perplexity of the baseline Witten-Bell smoothed LM (WBLM) with the best model showing a maxium perplexity reduction of 9% relative for the interpolation of bins B1 to B5 and with only a difference of 1.2% relative to Kneser-Ney smoothing. Results from the LMs
using graph metrics closely match the original results. The Authority and PageRank centrality slightly reduce perplexity compared to the original for single bin interpolation at $d = 4$ and produce equivalent results to each other. We believe that this is due to the similarity (mean difference of 1.79E-05) between the measures obtained from both algorithms. Modularity shows particular interest since it performs better than the original counts from B3 to interpolation of bins B1,B2,B3,B4. As for LMs with bins adjusted with the weighted degree measure, their performance is worse across the board, with a perplexity score higher than the original WBLM.

### 8.7.3 Automatic speech recognition experiments

This experiment evaluates the effect of the graph measures as well as the exploration of the entire powerset on BBOSLMs in the context of automatic speech recognition.

We provide only the best results in Tables 8.1 and 8.2 for each graph metric as well as the unmodified BBOSLM with $\alpha(m) = 1$. Results from the LM combining unmodified bins 1 to 5 are also included for comparison purposes. The BBOSLM using only the three bins B1, B3, B5 gave the best results with a WER of 23.93% compared to a WER of 24.10% for the original BBOSLM using all five bins. This strongly suggests that not all bins contribute positively to the final language model. It is also interesting to see that better performance can be achieved by using fewer data. By

<table><caption>Table 8.1: Comparison of perplexity on wsj1 hub 1, spoke 1, spoke 2 and spoke 9 evaluation corpora using 20k word trigrams using single and multiple bins mix-up for each network metric.</caption><thead><tr><th>LMS</th><th>BBOSLM</th><th>BBOSLM Auth</th><th>BBOSLM Mod</th><th>BBOSLM PR</th><th>BBOSLM WD</th><th>WB</th><th>KN</th></tr></thead><tbody><tr><td>original</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>149.11</td><td><strong>134.65</strong></td></tr><tr><td>d = 1</td><td>147.01</td><td>147.01</td><td>148.44</td><td>147.01</td><td>160.24</td><td>-</td><td>-</td></tr><tr><td>d = 2</td><td>145.11</td><td>145.11</td><td>147.65</td><td>145.11</td><td>159.47</td><td>-</td><td>-</td></tr><tr><td>d = 3</td><td>144.71</td><td>144.71</td><td>142.85</td><td>144.71</td><td>157.12</td><td>-</td><td>-</td></tr><tr><td>d = 4</td><td>142.66</td><td>142.66</td><td>141.86</td><td>142.66</td><td>156.08</td><td>-</td><td>-</td></tr><tr><td>d = 5</td><td>142.87</td><td>142.83</td><td>141.63</td><td>142.83</td><td>158.4</td><td>-</td><td>-</td></tr><tr><td>1 ≤ d ≤ 2</td><td>139.26</td><td>139.18</td><td>140.39</td><td>139.18</td><td>158.37</td><td>-</td><td>-</td></tr><tr><td>1 ≤ d ≤ 3</td><td>138.55</td><td>138.55</td><td>137.56</td><td>138.55</td><td>158.57</td><td>-</td><td>-</td></tr><tr><td>1 ≤ d ≤ 4</td><td>137.41</td><td>137.5</td><td><strong>136.27</strong></td><td>137.5</td><td>156.47</td><td>-</td><td>-</td></tr><tr><td>1 ≤ d ≤ 5</td><td>136.31</td><td>136.33</td><td>137.24</td><td>136.59</td><td>155.76</td><td>-</td><td>-</td></tr></tbody></table>
<table><caption>Table 8.2: ASR performance comparison of the best performing LMs on WSJ1 Hub 1, Spoke 1, Spoke 2 and Spoke 9 evaluation corpora using 20k word trigrams using single and multiple bins mix-up.</caption><thead><tr><th>LMS</th><th>PPL</th><th>SUB</th><th>DEL</th><th>INS</th><th>WER</th></tr></thead><tbody><tr><td>WBLM</td><td>149.11</td><td>17.96</td><td><strong>4.32</strong></td><td>3.14</td><td>25.42</td></tr><tr><td>KNLM</td><td><strong>134.65</strong></td><td>17.88</td><td>5.63</td><td>2.29</td><td>25.79</td></tr><tr><td>BBOSLM</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>bins<sub>d1-d5</sub></td><td>136.31</td><td>16.61</td><td>5.27</td><td><strong>2.22</strong></td><td>24.1</td></tr><tr><td>bins<sub>d1,d3,d5</sub></td><td>137.36</td><td><strong>16.53</strong></td><td>5.17</td><td>2.23</td><td><strong>23.93</strong></td></tr><tr><td>aut<sub>d1,d3,d5</sub></td><td>138.11</td><td>16.62</td><td>5.17</td><td><strong>2.22</strong></td><td>24.01</td></tr><tr><td>mod<sub>d1,d5</sub></td><td>137.65</td><td>16.58</td><td>5.14</td><td>2.26</td><td>23.98</td></tr><tr><td>pr<sub>d1,d3,d5</sub></td><td>138.11</td><td>16.62</td><td>5.17</td><td><strong>2.22</strong></td><td>24.01</td></tr><tr><td>wdeg<sub>d5</sub></td><td>158.4</td><td>17</td><td>4.88</td><td>2.43</td><td>24.31</td></tr></tbody></table>

looking at the other best performers, we see that the trend is maintained in the sense that bins B1, B3 and B5 are used in the majority of best performers. This behaviour deserves further investigation in future work. Even though the α weighted BBOSLMs did not outperform the best LM, they still perform better than both Witten-Bell and Kneser-Ney smoothed language models. Like with the perplexity experiments, weighted degree bins perform worse than the other graph metrics, yet this results in smaller word error rate than both KN and WB smoothing using only bin 5. We suspect that it might be symptomatic of a certain amount of robustness built into the BBOSLM smoothing algorithm.

## 8.8 Conclusion and discussion

In this paper, we evaluated the impact of using different graph metrics to weigh the relations between words in the WordNet ontology for use with the Bin-Based Ontological Smoothing (BBOS) proposed in previous work [86]. We observed from our experiments that the hypothesis that less important words (network node) should contribute less to the overall smoothed counts of bins is inconclusive and should be the subject of further study. Although performance using network metrics slightly degraded compared to the best performing unmodified BBOSLM we were still able to obtain better performance than Witten-Bell and Kneser-Ney smoothing. Furthermore, we were able to obtain better performance by reducing the number of bins used during
interpolation from five to three. This seems to indicate that only certain bins contribute positively
to the smoothing of counts and again gives us other interesting avenues for future research.
<figure><img src="image_46.png" /></figure>
# 9 CONCLUSION

Ce travail s'est concentré dans un premier temps sur le développement d'un algorithme de lissage de modèles de langage, des N-grammes, permettant d'exploiter l'information sémantique latente aux ontologies afin de permettre une meilleure modélisation probabiliste d'énoncés qui ne se retrouvent pas dans le corpus d'entrainement. Comme nous avons souvent tendance, lorsque nous parlons, à substituer un mot exact pour un autre mot qui nous vient à l'esprit plus rapidement, l'objectif était d'attribuer des probabilités aux N-grammes non vues basées sur les expressions sémantiquement similaires observées dans les corpus d'entrainement.

Dans un deuxième temps, nous nous sommes attaqué à un autre problème que nous rencontrons en modélisation du langage, soit l'optimisation des paramètres de lissage des modèles de langage. La plupart des travaux recensés se limitent à l'utilisation de l'algorithme Expectation Maximisation (très rapide, mais très approximatif), ou l'algorithme de Powell pour optimiser les paramètres. Or, ces algorithmes produisent soit des optimisations approximatives, soit se prêtent mal à la parallélisation. C'est dans le but d'obtenir des résultats à la fois meilleurs et de manière plus rapide que nous nous sommes penché sur la possibilité d'utiliser les algorithmes évolutionnaires pour optimiser les paramètres de l'algorithme de lissage original que nous avons proposé.

## 9.1 Conclusions principales

Les ontologies peuvent être utilisées pour rapidement créer un ensemble de règles flexibles lors de la conception d'interfaces vocales de type commande et contrôle.

Il est possible d'utiliser les ontologies pour lisser les modèles de langage basés sur les N-grammes :

* Il est possible, à partir d'un petit corpus, d'obtenir un modèle de langage qui prenne un lissage des énoncés jamais vus, mais qui sont sémantiquement similaires à ceux observés dans le corpus d'entrainement.

* Une normalisation de l'algorithme, par exemple pour le rendre compatible avec la méthode de Kneser-Ney, devrait, en principe, nous permettre d'obtenir des gains additionnels.
* Une approche par bacs, où les mots ayant un nombre similaire de « voisins », similaire à l'approche de la méthode Witten-Bell ou Kneser-Ney où les paramètres de lissage des mots ayant un nombre de contextes similaires sont regroupés en bacs, devraient aussi nous permettre de simplifier le modèle et d'améliorer sa performance.

* Nous avons posé les bases pour utilisation dans corpus restreints. Nous sommes d'avis que la méthode de lissage que nous avons proposé dans cette thèse pourra être utilisée par d'autres chercheurs dans des langes où les ressources textuelles sont restreintes.

Les métriques issues de la théorie des graphes sont prometteuses pour la pondération des relations ontologiques :

* Bien que nous n'avons pas obtenu la réduction de perplexité escomptée suite à leur utilisation sous forme de poids de pondération, nous sommes d'avis qu'une intégration plus approfondie de ces métriques, par exemple en ajustant les poids selon un ensemble de plus petits corpus comme pour la classification de documents et en considérant l'ontologie comme un graphe dirigé plutôt qu'un graphe non dirigé et en ajustant les paramètres utilisés pour les calculer, devrait permettre d'obtenir des gains de performance additionnels.

Les algorithmes évolutionnaires, en particulier l'optimisation par essais particulaires permettent de rapidement optimiser les poids d'interpolation des modèles de langage :

* Les résultats obtenus, en termes de perplexité, à l'aide des algorithmes évolutionnaires sont en moyenne supérieurs à ceux obtenus par l'optimisation par l'algorithme de Powell.

* L'optimisation par algorithme génétique produit des résultats beaucoup plus variables (plus grande variance) que l'optimisation par essais particulaires, mais, en contrepartie, permet d'obtenir la plus grande réduction absolue de perplexité.

* Nous avons montré qu'il est possible de partir des résultats obtenus avec l'algorithme d'espérance-maximisation, dans le but de simuler un paramétrage initial expert, d'obtenir des résultats beaucoup plus rapidement et avec une moins grande variance.

* Les algorithmes évolutionnaires ont un avantage inhérent en termes de vitesse comparativement à l'algorithme de Powell grâce à la plus grande prédisposition au parallélisme de ces derniers.
* Nous avons montré que les résultats obtenus permettent de réduire le taux d’erreur des mots de façon statistiquement significative dans une tâche de reconnaissance automatique de la parole.

## 9.2 Contributions principales

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

* Nous avons proposé un nouvel algorithme de lissage ontologique exploitant l’information sémantique retrouvée dans les ontologies pour le lissage des modèles de langage et comparaison empirique avec d’autres algorithmes de lissage statistique.

* Nous avons évalué l’utilisation des mesures issues de la théorie des graphes pour pondérer les relations ontologiques pour le lissage des modèles de langage.

* Nous avons comparé la performance d’algorithmes évolutionnaires, algorithmes génétiques et optimisation par essais particulaires, pour l’optimisation des poids d’interpolation des modèles de langage lissés à l’aide de notre algorithme de lissage ontologique.

* Nous avons conçu 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.

* Nous avons produit une suite de procédures d’entrainement pour la reproduction des résultats sous Linux (Python + Bash + Perl + Matlab).

## 9.3 Travaux futurs

Nous sommes d’avis que bien que l’algorithme de lissage que nous avons proposé permette d’obtenir des gains de performances en termes de réduction de la perplexité des modèles de langage et d’amélioration du taux de reconnaissance automatique de la parole, qu’il demeure que les concepts introduits pourront être approfondis dans le but d’obtenir d’encore meilleures
performances. Nous nous attendons donc à poursuivre nos travaux, en particulier dans les trois
domaines suivants :

* Généralisation et ajustement de l’algorithme de lissage afin de simplifier les calculs.

* Généralisation de l’algorithme sur de plus grands contextes : paraphrases.

* Utilisation des ontologies pour améliorer les modèles de langage basés sur les réseaux de neurones, en particulier les modèles basés sur le long term short memory.

* Approfondir l'évaluation de l'effet du taux de mutation de l'optimisation par algorithmes génétiques sans amorçage. Les résultats obtenus ont privilégié un taux de mutation de 80 %, ce qui est contre-intuitif. Nous soupçonnons le processus de génération aléatoire de la population initiale qui produit peut-être des individus qui se trouvent tous très loin de la solution optimale. Nous proposerons l'implémentation d'un taux de mutation variable afin d'évaluer si l'algorithme privilégiera un taux de mutation plus raisonnable au fil des générations.

* Analyser pourquoi les dépendances ontologiques très lointaines contribuent à l'amélioration du modèle de langage. Est-ce qu'elles sont liées au contexte, au corpus ou est-ce dû à une meilleure (re)distribution des *N*-grammes de faibles comptes.

* Le problème d'optimisation des poids d'interpolation des modèles de langage comportait un espace de recherche assez restreint et les algorithmes évolutionnaires n'ont pas été en mesure, en moyenne, de proposer de meilleures solutions finales que celles obtenues à l'aide de l'optimisation par l'algorithme de Powell. Nous tenterons donc d'évaluer ces derniers dans un contexte plus complexe, par exemple pour l'optimisation des poids des bacs pour le lissage Kneser-Ney et un lissage plus complexe basé sur les ontologies.