Memoire Online - Algorithmes évolutionnaires dans les systèmes de parole

Republique Algerienne Democratique et Populaire
Ministere de l^'Enseignement Superieur et de la Recherche Scientifique

Universite Abderrahmane Mira de Bejaia
Faculte des Sciences Exactes
Departement d^'Informatique

Merci à tous ceux qui ont contribué de près ou de loin à la réalisation de ce travail.

Résumé

La nature variable du signal de la parole fait que son traitement, dans ses différents niveaux, soit une tâche très difficile. Etant donné qu'il n'existe pas de méthodes exactes pour traiter cette variabilité, les systèmes de parole ont toujours recours à des méthodes d'approximation. Dans ce travail, nous avons étudié les possibilités d'application d'une famille de ces méthodes d'approximation connue sous le nom d'Algorithmes évolutionnaires. Ce sont des méthodes qui reposent sur le principe d'évolution et de sélection naturelles. Nous avons réalisé une étude comparative entre deux méthodes particulières de cette famille : les stratégies d'évolution et la programmation génétique après avoir proposé des possibilités de mise en oeuvre dans les systèmes de parole pour chacune d'elle.

A l'issue de cette étude, nous avons constaté que la puissance de chaque méthode se situe dans la catégorie des problèmes à laquelle elle a initialement été conçue. Les stratégies d'évolution offrent des possibilités importantes en optimisation, et peuvent être appliquées efficacement dans la phase de reconnaissance. La programmation génétique quant à elle, peut améliorer la qualité d'apprentissage et des traitements linguistiques, vu ses performances en matière de développement automatique des programmes.

Abstarct

The variable nature of the speech signal makes that its treatment, in its different levels, is a very difficult task. Since exact methods don't exist to treat this variability, the speech systems always have resort to approximation methods. In this work, we studied the possibilities of application of a family of these approximation methods known as evolutionary algorithms. These are the methods that rest on the principle of natural evolution and selection. We realized a comparative survey enters two particular methods of this family : the evolution strategies and the genetic programming after having proposed possibilities of implementation in the speech systems for each of her.

At the end of this survey, we noted that the power of every method is located in the category of the problems to which it has been initially conceived. The evolution strategies offer important possibilities in optimization, and can be applied efficiently in the phase of recognition. The genetic programming as for her, can improve the quality of learning and linguistics treatments, seen its performances concerning automatic development of programs.

		Table des matières
2	1.8 Traitements linguistiques de haut niveau 1.9 Conclusion Algorithmes évolutionnaires		20 22 23
	2.1	Principes d'inspiration	23
	2.2	Cycle de base d'un algorithme évolutionnaire	24
	2.3	Principales familles	24
		2.3.1 Algorithmes génétiques	24
		2.3.2 Programmation génétique	26
		2.3.3 Stratégies d'évolution	26
		2.3.4 Programmation évolutionnaire	26
	2.4	Population et représentation des individus	27
	2.5	Evaluation et Sélection	29
		2.5.1 Sélection par roulette	29
		2.5.2 Sélection par rang	30
		2.5.3 Sélection steady-state	30
		2.5.4 Sélection par tournoi	30
		2.5.5 Elitisme	30
		2.5.6 Sélection de seuil	31
	2.6	Reproduction	31
		2.6.1 Création et duplication	31
		2.6.2 Mutation	31
		2.6.3 Recombinaison	32
	2.7	Application dans les systèmes de parole	32
	2.8	Avantages et inconvénients	34
	2.9	Conclusion	35
3	Stratégies d'évolution et Programmation génétique		36
	3.1	Stratégies d'évolution	36
		3.1.1 Populations dans les SE	36
		3.1.2 Evolution différentielle	37
		3.1.3 Sélection	37
		3.1.4 Mutation	37
		3.1.5 Recombinaison	38
		3.1.6 Auto adaptation	39
		3.1.7 Mise en oeuvre dans les systèmes de parole	40
	3.2	Programmation génétique	41
		3.2.1 Population	41
		3.2.2 Evaluation et sélection	42

Table des figures

1.1	Classification morphologique des signaux	4
1.2	phonèmes du français, symboles de l'alphabet phonétique international	10
1.3	Echelle de Mel	15
1.4	Exemple de graphe de décodage	17
1.5	Exemple de classification phonétique	17
1.6	Chemin optimal par DTW	18
1.7	Exemple de découpage syntaxique	21
2.1	Cycle de base d'un algorithme évolutionnaire	25
3.1	Schéma d'un croisement direct	39
3.2	Exemples de création par la méthode Full	42
3.3	Exemples de création par la méthode Grow	42
3.4	Différentes possibilités de Mutation	44
3.5	Recombinaison par échange de sous-arbres	44
3.6	Permutation	44
3.7	Encapsulation	45
3.8	Permutation	45
3.9	Permutation	46
4.1	Résumé récapitulatif de l'analyse comparative	58

Depuis l'arrivée des premières générations des ordinateurs, l'idée de les contrôler à travers des claviers avec un jeu de caractère restreint a toujours été remise en cause. Le rêve de communiquer avec les machines de façon plus sophistiquée, plus naturelle et spontanée n'a cessé de submerger l'esprit humain. Dans les années 50, cette idée a commencée à devenir une réalité, grâce à des réalisations qui ont permis de contrôler le fonctionnement d'un ordinateur avec un nombre très limité de commandes orales, qu'il comprenait.

Avec toute l'évolution que les systèmes de parole ont connue depuis cette époque, les résultats obtenus sont encore loin d'être idéal, et le domaine demeure un sujet de recherche très actif. Les ordinateurs n'ont plus maintenant à faire à des données exactes telles que les caractères et les nombres, mais plutôt à des données de nature très variable. Pour cette raison, tous les systèmes de paroles doivent passer par des périodes d'apprentissage durant lesquelles ils apprennent à faire face à ce problème de variabilité, en utilisant le plus souvent des méthodes statistiques et probabilistes. En fait, une étape d'apprentissage n'est pas tout à fait suffisante, le problème doit encore être affronté lors de la phase de reconnaissance pour estimer les correspondances entre les données déjà apprises et les nouvelles données. Il en résulte par conséquent un travail important de calcul et d'optimisation.

Etant donné qu'il n'existe pas de méthodes exactes plus efficaces, les systèmes de parole, quelque soit le modèle qui leur est adopté, ont toujours recours à des méthodes d'approximation (heuristiques) pour remédier à la complexité du calcul. Une famille importante de ces heuristiques, connues sous le nom d'Algorithmes évolutionnaires, a commencé à émerger il y a une trentaine d'années, et a pratiquement intégré tous les domaines scientifiques. Ces méthodes ont suivi une nouvelle approche inspirée du processus d'évolution naturelle, et se sont basées sur les principes d'évolution et de sélection. Avec cette approche très simple et intuitive, ces algorithmes ont pu fournir des résultats très intéressants là où ils ont été appliqués. Toutefois, les travaux sur les systèmes de parole qui sont fondés sur des algorithmes évolutionnaires ne sont pas nombreux. Le présent travail consiste en une analyse théorique des possibilités d'ap-

plication de ces algorithmes dans les systèmes de parole. Ces systèmes sont complexes et très compliqués; en conséquence de quoi, un modèle directe basé sur un algorithme évolutionnaire ne peut être défini. Nous étudierons donc la façon par laquelle ces algorithmes peuvent contribuer à l'amélioration de la qualité et de la performance des systèmes de parole, que ce soit durant l'apprentissage ou lors de a phase de traitement avec ses différent niveaux.

Ce document est divisé sur trois chapitres. Le premier présente un état de l'art général sur les systèmes de reconnaissance de la parole. Nous essayons de traiter d'un maximum d'aspect afin de pouvoir identifier toutes les possibilités d'application des algorithmes évolutionnaires. Nous traitons donc des caractéristiques du signal vocal, de ses niveaux ainsi que de son processus de traitement, de l'apprentissage et des traitements linguistiques.

Le second chapitre expose, de façon générale, les éléments de base des algorithmes évolutionnaires. Nous tentons de discuter chaque élément sans tenir compte d'une méthode particulière. A la fin, le chapitre récapitule l'ensemble des travaux, que nous avons pu réunir, sur les systèmes de parole qui ont utilisé des algorithmes évolutionnaires.

Dans les deux derniers chapitres, nous effectuons une étude comparative de deux méthodes particulières : les stratégies d'évolution et la programmation génétique. Dans le troisième chapitre, nous donnons une présentation détaillée des deux méthodes, et dans le dernier une analyse comparative. Dans le troisième chapitre aussi, nous proposons des possibilités de mise en oeuvre, pour chacune des deux méthodes, dans les différents modèles et niveaux de traitement.

En traitant d'un ensemble important d'aspects relatifs au traitement de la parole, et en choisissant deux types d'algorithmes évolutionnaires largement différents, nous espérons pouvoir couvrir un maximum de possibilités et de déceler les différentes options que peut offrir les algorithmes évolutionnaires pour les systèmes de parole.

1.1 Généralités sur les signaux

Un signal est la représentation physique de l'information qu'il transmet de sa source à sa destination. La nature physique du signal peut être de n'importe quelle grandeur mesurable (ondes acoustiques, signale optique, magnétique ou radioélectrique).

Les signaux peuvent être classés en de différents types selon différents critères. Si l'on considère la durée des signaux, on peut les diviser en des signaux à durée limitée et des signaux à durée illimitée. Ces derniers se décomposent à leur tour en des signaux à énergie finie, à puissance moyenne finie et des signaux causaux. Selon leur évolution, il existe des signaux déterministes (périodiques, pseudopériodiques et transitoires) dont l'évolution peut être parfaitement décrite par un model mathématique, contrairement aux signaux aléatoires dont le comportement est imprévisible dans le temps et pour la représentation desquels on doit se contenter des observations statistiques. Un autre mode de classification est selon la morphologie. On distingue des signaux analogiques, quantifiés, échantillonnés et numériques. Une dernière classification est suivant la représentation spectrale par laquelle un signal est classé par le domaine de variation de la fréquence moyenne (basse fréquence, haute fréquence...).[143]

Le signal qui véhicule l'information est fréquemment distordu. Cette distorsion peut prendre naissance à la prise du signale ou durant la transmission. On est donc fréquemment amené à filtrer le signal. Un filtre est un dispositif susceptible de privilégier les composantes d'un signal dont les fréquences sont situées dans un certain domaine, tout en affaiblissant les autres. Les filtres peuvent aussi être utilisés pour la mise en forme du signal. Ceci inclus toutes les modifications que l'on peut faire subir à un signal pour faire apparaitre certaines caractéristiques ou pour en masquer d'autres.

Les signaux primaires porteurs d'information sont pratiquement toujours de type analogique (amplitude et temps continu)[143]. Un système d'acquisition ou tout autres système traite des données sous forme de suite de nombre discrets. Le rôle de l'échantillonnage est de représenter le signal sous forme de suite de valeurs ponctuelles en procédant à un découpage, dans le temps, du signal.

1.2 Le signal vocal

Le signal vocal correspond à une variation de la pression de l'aire causée par le système articulatoire. Le phénomène s'accompagne d'une propagation d'énergie entre la source et le destinataire. Cette propagation est impossible dans le vide et sa vitesse ne dépond que de la nature du milieu et de ses caractéristiques physiques. Ces milieux ne transmettent que les ondes dont les fréquences ont des valeurs bien précises : c'est le phénomène d'amortissement.

Le signal vocal possède plusieurs propriétés : il est produit par l'homme, il est très variable du fait de la diversité phonétique et il est modifié par l'environnement sonore. Ces propriétés font du signal vocal un signal complexe, variable et souvent bruité.[113]

1.2.1 Caractéristiques déterminantes

Le signal vocal forme une résonnance lorsque les fréquences du signal peuvent être modélisées comme des multiples d'une fréquence de base appelée fréquence fondamentale. Les différents multiples de cette fréquence sont appelés des harmoniques.

Pour le signale vocale, la fréquence fondamentale est celle à laquelle la glotte s'ouvre et se ferme périodiquement.[82]

Chaque phonème contient un grand nombre d'harmoniques dont les amplitudes relatives dépendent de la configuration du conduit vocal. Ils présentent donc un timbre. Ce timbre est lié à la position, à l'amplitude et la largeur de bande des maxima du spectre. La production d'un phonème fait apparaître une ou plusieurs résonnances qu'on regroupe sous le nom de formants. La position des fréquences formantiques, pour un locuteur donné, peut varier d'une élocution à l'autre, même dans le même contexte. Mais elles varient beaucoup plus encor entre un locuteur et un autre.

1.2.2 Informations véhiculées par la parole

La parole transmet plusieurs types d'informations : linguistiques, paralinguistiques mais aussi extralinguistiques. La transmission d'informations linguistiques est le premier objectif de la parole. Cependant, les informations paralinguistiques comme l'intonation modifient et ajoutent des éléments utiles pour la compréhension. Les informations dites extralinguistiques comme les variabilités dues aux locuteurs sont souvent des facteurs qui perturbent les systèmes.[63]

Les informations linguistiques sont de plusieurs types. Un message est composé de phrases, de mots. Chacun de ces mots peut être décomposé en syllabes. La syllabe est une combinaison de phonèmes dont le noyau est une voyelle parfois entourée de plusieurs consonnes. Le phonème est la plus petite unité segmentale distinctive. Le phonème n'est pas un élément unique en lui même. Pour un même phonème, on pourra trouver différentes variantes acoustiques appelées allophones. Il existe donc des traits caractéristiques communs ou discriminants que l'on peut exploiter dans la tâche d'extraction de caractéristiques.

Les informations paralinguistiques regroupent les composantes du signal de parole qui ne sont pas à proprement parler des informations linguistiques. Souvent, elles permettent une meilleure compréhension du contexte linguistique. L'intonation est un exemple d'information paralinguistique utile à la compréhension. Une phrase selon qu'elle soit prononcée de manière déclarative ou interrogative peut changer sensiblement de sens. Des variabilités dues aux locuteurs sont également comprises dans les informations paralinguistiques. L'état émotif, affectif et l'attitude du locuteur sont des exemples de ces variabilités. Le niveau social ainsi que l'accent régional sont également des informations paralinguistiques. Par définition, les émotions ne sont pas contrôlables par le locuteur. Quant aux autres informations paralinguistiques comme le ni-

veau social, le locuteur ne contrôle pas ces informations dans le cas d'une conversation naturelle.

De nombreuses autres informations dites extralinguistiques sont présentes dans le signal de parole. Elles transmettent essentiellement des caractéristiques propres aux locuteurs comme le genre ou l'âge. L'environnement sonore, Les conditions de prise de son et le canal de transmission sont des exemples d'informations extralinguistiques.

1.2.3 Niveaux de complexité

La parole est un signal très complexe et son traitement est un problème très difficile. Les sources de complexité sont de natures différentes, elles peuvent être liées au locuteur, à l'environnement sonore ou au signal lui-même.

Il y a d'abord le problème de la variabilité intra et inter-locuteurs. Le système est-il dépendant du locuteur ou indépendant du locuteur? Evidemment, les systèmes dépendants du locuteur sont plus faciles à développer et sont caractérisés par de meilleurs taux de reconnaissance que les systèmes indépendants du locuteur étant donné que la variabilité du signal de parole est plus limitée. Cette dépendance au locuteur est cependant acquise au prix d'un entraînement spécifique à chaque utilisateur.

Le système reconnaît-il des mots isolés ou de la parole continue? Evidemment, il est plus simple de reconnaître des mots isolés bien séparés par des périodes de silence que de reconnaître la séquence de mots constituant une phrase. En effet, dans ce dernier cas, non seulement la frontière entre mots n'est plus connue mais, de plus, les mots deviennent fortement articulés. Dans le cas de la parole continue, le niveau de complexité varie également selon qu'il s'agisse de texte lu, de texte parlé ou, beaucoup plus difficile, de langage naturel avec ses hésitations, phrases grammaticalement incorrectes, faux départs, etc.

La taille du vocabulaire et son degré de confusion sont également des facteurs importants. Les petits vocabulaires sont évidemment plus faciles à reconnaître que les grands vocabulaires, étant donné que dans ce dernier cas, les possibilités de confusion augmentent. Certains petits vocabulaires peuvent cependant s'avérer particulièrement difficiles à traiter; ceci est le cas, par exemple, pour l'ensemble des lettres de l'alphabet, contenant surtout des mots très courts et acoustiquement proches.

Le système est-il robuste, c'est-à-dire capable de fonctionner proprement dans des conditions difficiles? En effet, de nombreuses variables peuvent affecter significati-

vement les performances des systèmes de reconnaissance bruits d'environnement, acoustique déformé et bruits corrélés avec le signale de parole utile, systèmes d'acquisition de différents caractéristiques, bande fréquentielle limitée, etc.

1.3 Traitement de la parole

Les technologies de traitement de la parole recouvrent différents domaines d'application. On distingue essentiellement la synthèse vocale et la reconnaissance vocale. Cependant, dans la plupart des applications courantes, ces deux techniques sont sou-vent associées[72]. L'identification et la vérification du locuteur font aussi partie du domaine de traitement de la parole.

La synthèse vocale peut être définie comme la communication de la machine à l'homme. La synthèse vocale recouvre tous les aspects liés à l'interprétation, par la machine, du langage humain. Dans les applications de reconnaissance vocale on distingue les systèmes de commandes vocales et les systèmes de dictée.

Les systèmes de commande vocale permettent à l'utilisateur de contrôler des équipements. Certaines applications ne permettent que le contrôle par un nombre limités de mots ou de courtes phrases. D'autres systèmes permettent à l'utilisateur de s'exprimer par des phrases mais sont entrainés à repérer certains mots de la phrase, mots qui se trouvent dans leurs dictionnaires internes et sur lesquels ils basent leurs actions. On trouve aussi d'autres applications beaucoup plus évoluées où l'on peut s'adresser au système en langage naturel.

Les systèmes de dictée constituent le problème le plus difficile à résoudre dans le domaine de reconnaissance vocale[72]. Comme pour les systèmes de commande vocale, il existe des systèmes de reconnaissance discrète dans lesquels l'utilisateur doit parler avec de courtes poses entre chaque mot, et des systèmes à reconnaissance continue qui permettent à l'utilisateur de dicter son texte de façon continue et à une vitesse de locution normale.

La vérification du locuteur consiste à déterminer si un locuteur est bien celui qu'il prétend être. Dans ce type d'applications, il s'agit donc de trancher entre les deux hypothèses soit le locuteur est bien le locuteur autorisé, c'est à dire celui dont l'identité est revendiquée, soit nous avons affaire à un imposteur qui cherche à se faire passer pour un locuteur autorisé. Les applications classiquement envisagées pour la vérification du locuteur correspondent donc à l'idée de "serrure vocale" qui peut être utilisée,

par exemple, pour valider des transactions bancaires effectuées par téléphone, ou pour compléter un dispositif d'accès (à un bâtiment, un système informatique, etc.)

L'identification du locuteur consiste à reconnaître la voix d'un locuteur parmi une population (une base de données) composée de N locuteurs connus. En identification, la réponse apportée n'est plus de type binaire (acceptation ou rejet) comme dans le cas de la vérification puisqu'il est nécessaire de désigner un locuteur parmi un groupe. La sortie du système correspond à l'identité du locuteur de la base de référence qui est la plus "proche" du signal de parole inconnu. Dans cette tâche, on fait l'hypothèse que le signal de parole à identifier est prononcé par l'un des locuteurs de la base de référence (identification en ensemble fermé)

Il est à noter que pour une identification en ensemble ouvert, la combinaison des deux tâches précédentes est nécessaire identification du locuteur le plus probable parmi les locuteurs de la base des données, puis vérification que l'échantillon inconnu a bien été prononcé par le locuteur choisi dans l'étape d'identification.

Pour une application de vérification ou d'identification, il est nécessaire de disposer d'une base de données contenant des enregistrements de référence correspondant à chacun des locuteurs autorisés. En pratique, on ne conserve pour chaque locuteur que les paramètres utiles pour la reconnaissance extraits de ses enregistrements de référence. Ces informations constituent les données de référence du locuteur.

1.4 Niveaux de traitement

L'information portée par le signal de la parole peut être analysée de bien de façon. On en distingue généralement plusieurs niveaux de description acoustique, phonétique, phonologique, morphologique, syntaxique, sémantique et pragmatique.[63]

1.4.1 Niveau acoustique

La parole apparait physiquement comme une variation de la pression de l'air causée et émise par le système articulatoire. L'étude acoustique de ce signal consiste à le transformer dans un premier temps en un signal électrique (souvent numérique) qui peut être soumis à un ensemble de traitement acoustique qui visent à mettre en évidence les traits acoustiques correspondant aux grandeurs perceptuelles formant, intensité et timbre. Le signal est en suite échantillonné et pondéré par une fenêtre de

pondération (souvent une fenêtre de Hamming). En effectuant une transformée de Fourier à ces échantillons, on peut séparer les sons voisés et non voisés selon la structuration des fréquences, et les formants et les timbres selon la forme générale des spectres (enveloppe spectrale).

On peut aussi séparer les sons voisés et non voisés en représentant l'évolution temporelle du spectre sous forme d'un diagramme à deux dimensions temps-fréquence appelé spectrogramme, comme on peut représenter l'évolution de la fréquence fondamentale.

1.4.2 Niveau phonétique

A ce niveau, ce n'est pas tant le signal qui importe que la façon dont il est produit par le système articulatoire. La parole peut être décrite comme le résultat de l'action volontaire et coordonnée d'un certain nombre de muscles. L'alphabet phonétique international associe des symboles phonétiques (phonèmes ou unités phonétiques élémentaires) aux sons de telle façon à permettre l'écriture compacte et universelle des prononciations.

Ces différents symboles sont regroupés en trois classes principale : les voyelles, les semi-voyelles (ou semi-consonnes)et les liquides et les consonnes. La production de chaque classe de phonèmes fait appel à un ensemble distingué d'éléments de l'appareil articulatoire et chaque élément se trouve réagir différemment d'un phonème à un autre. Les traits acoustiques du signal de la parole sont évidemment liés sa production. L'intensité du son est liée à la pression de l'aire en amont. Sa fréquence, qui n'est rien d'autre que la fréquence du cycle ouverture/fermeture des cordes vocales, est déterminée par la tension des muscles qui les contrôlent. En fin, son spectre est le résultat du filtrage du signal par le conduit vocal.

Il est aussi important de noter qu'une bonne connaissance des mécanismes de l'audition et des propriétés perceptuelles de l'oreille humaine est aussi importante qu'une métrise des mécanismes de production. En effet, tout ce qui peut être mesuré acoustiquement ou observé par la phonétique articulatoire n'est pas nécessairement perçu. La plage des fréquences perçues par l'oreille humaine est bornée par une limite supérieure proche de 16000 Hz, ce qui limite considérablement la fréquence d'échantillonnage. En plus, même dans l'intervalle de son domaine d'audition, l'oreille ne présente pas une sensibilité identique à toutes les fréquences. Enfin, les sons peuvent se chevaucher et un son peut donc en masquer un autre. Ce chevauchement, appelé phénomène de masquage, peut aider à réduire le débit binaire du signal acoustique.

FIGURE 1.2 - phonèmes du français, symboles de l'alphabet phonétique international

1.4.3 Niveau phonologique et morphologique

La phonologie est l'interface nécessaire entre la phonétique et la description linguistique de niveau plus élevé. Elle introduit la notion d'unités phonétique du discours qui est la plus petite unité phonétique distinctive. Ces unités constituent un ensemble structuré dans lequel chaque élément est différent des autres, la différence étant à chaque fois porteuse de sens contrairement aux niveaux précédant où la parole est considérée comme si elle ne portait aucune signification.

Les variations phonétiques articulatoires dues à des différences régionales ou de la dynamique vocale ne donnent pas naissance à de nouveaux phonèmes. Ces effets sont connus sous le nom de réduction, assimilation et coarticulation[15]. Les phénomènes coarticulatoires sont dus au fait que chaque articulateur évolue de façon continue entre les positions articulatoires. Au contraire, la réduction et l'assimilation prennent leur origine dans des contraintes physiologiques et sont sensibles au débit parlé. L'assimilation est causée par le recouvrement de mouvements articulatoires et peut aller jusqu'à modifier un trait acoustique du phonème prononcé. La réduction est plutôt due au fait que les cibles articulatoire sont moins bien atteintes dans le parler rapide.ces phénomènes sont en grande partie responsables des traitements réalisés des signaux de la

La description phonologique de la parole doit rendre compte de la durée, de la densité et de la fréquence fond mentale des phonèmes. La durée des silences et des phones détermine le rythme de la phrase, tandis que l'évolution de la fréquence fondamentale constitue sa mélodie.

La suite des phonèmes prononcés correspond à des mots choisis dans le lexique des mots de la langue. L'étude morphologique étudie la façon dont les mots peuvent être construit à partir de mots de base, et par conséquent, et étant donné la richesse de la langue, réduire la taille du vocabulaire.

1.4.4 Niveaux syntaxique, sémantique et pragmatique

Toute suite de mots du lexique ne forme pas une phrase correcte. En effet, la liste des phrases admises, bien qu'infinie, est restreinte par leur syntaxe. Les grammaires ne servent pas qu'à dresser les frontières entre les phrases régulièrement construites, mais elles permettent également l'organisation hiérarchique des phrases.

Bien que la syntaxe restreigne le nombre de phrases acceptables, elle ne constitue cependant pas une limite exhaustive d'acceptabilité. En effet, un nombre de phrase syntaxiquement correcte ne sont pas toutes admissibles. L'étude des significations des mots, de la façon dont ils sont liés les un aux autres fait l'objet de la sémantique lexicale. Il s'agit principalement d'étudier les problèmes d'ambiguïté. Notons que la différence entre syntaxe et sémantique reste relativement floue, car il ne s'agit pas de l'étude des conditions de vérité comme dans les expressions logiques.

Le dernier niveau est le niveau pragmatique. Contrairement au sens sémantique, que l'on qualifie souvent d'indépendant du contexte, le sens pragmatique est définie comme dépendant du contexte. Tout ce qui réfère au contexte dans lequel une phrase s'inscrit et la relation entre le locuteur et son auditoire, a quelque chose à voire avec la pragmatique. Son étendue couve l'étude de sujets tels que les présuppositions, les implications de dialogue, les actes de parole...

1.5 Processus de traitement

La reconnaissance de la parole est un processus complexe composé de plusieurs étapes qu'on classe généralement en trois phases : la phase de prétraitement qui prépare le signale pour améliorer la qualité du décodage, la phase de reconnaissance qui

constitue l'étape la plus importante et enfin la phase des traitements linguistiques de plus haut niveau.

Les premiers succès en reconnaissance vocale ont été obtenus dans les années 70 à l'aide d'un paradigme de reconnaissance de mots par l'exemple. L'idée, très simple dans son principe, consiste à faire prononcer un ou plusieurs exemples des mots susceptibles d'être reconnus, à les enregistrer et à les comparer avec le signale à reconnaître. Ce principe est mieux adapté à la reconnaissance monolocuteur de mots isolés et à petit vocabulaire. Mais dès que la taille du vocabulaire devient importante, le principe devient inadapté, sans prendre en compte la continuité de la parole et la variabilité des locuteurs.

Pour remédier à ces manques, et concevoir un système réellement multilocuteur et à plus grand vocabulaire, il devient nécessaire de mener la reconnaissance sur base d'unités de parole de plus petite taille (typiquement les phonèmes). On ne se contente plus alors d'exemples de ces unités, mais on cherche plutôt à en déduire un model qui sera applicable à n'importe quelle voix.

1.5.1 Prétraitement

Les prétraitements débutent par un échantillonnage des signaux, suivi d'une préaccentuation. Le signal est divisé en fenêtres de longueur entre 20 et 30 ms. Le signal final est obtenu en multipliant le signal par une fonction de pondération. La préaccentuation consiste en un filtrage du signal de la parole pour égaliser les graves et les aigues. D'autres prétraitements, ayant pour but d'augmenter la robustesse, sont par fois mis en oeuvre comme par exemple la normalisation des sons ou la soustraction spectrale qui a pour effet d'éliminer les bruits additifs.

Le choix de la fenêtre est très important. Parmi les fenêtres utilisées on trouve les fenêtres de Hamming, Hanning, Blackman ou de Kaiser. Le choix de la fenêtre se fait le plus souvent en fonction de l'application car les fenêtres présentent différentes atténuations à des fréquences bien précises. Cependant, il faut noter que la plupart des systèmes sont directement conçus sur des fenêtres de Hamming. Les efforts de conception sont consacrés à d'autres étapes comme l'extraction des paramètres.[113]

La phase de reconnaissance est représentée par l'ensemble des processus qui ont pour objet de faire passer le signal de sa forme acoustique vers une forme linguistique constituée d'unités phonétiques élémentaires et d'associer à ces dernières les correspondances linguistiques appropriées. Ces correspondances seront par la suite pas-

sées au module linguistique pour des traitements de plus haut niveau. Ces traitements concernent l'analyse lexicale, syntaxique, sémantique et pragmatique. Tous les traitements linguistiques ne sont pas présents dans tous les systèmes de reconnaissance, selon le domaine considéré et selon le besoin, le système peut exclure un traitement ou un autre.

1.5.2 Extraction des paramètres

L'extraction des paramètres est l'objet principal de l'analyse de la parole et c'est le passage obligé de toutes les applications de traitement de la parole.[113]

En considérant le degré de connaissance associé au signal, il existe des méthodes d'extraction non paramétriques qui sont basées généralement sur une représentation fréquentielle du signal sans tenir compte de sa structure fine. Les méthodes paramétriques ou les méthodes d'identification en revanche, sont fondée sur une connaissance des mécanismes de production de la parole. Elles reposent sur un model. Celui-ci repose sur un ensemble de paramètres numériques, dont les niveaux de variation représentent l'ensemble des signaux couverts par le model. Pour un signal et un model donné, l'analyse estime les paramètres du model pour lui faire correspondre le signal analysé.

Selon que l'on prenne en compte l'évolution fréquentielle ou temporelle du signal de la parole, on distingue des méthodes d'analyse spectrales et des méthodes d'analyse temporelles. L'analyse spectrale est basée sur deux principe : le premier est que le timbre de la parole dépend de la position, dans l'échelle des fréquences, des formant qui sont liés aux résonnances du conduit vocal, le deuxième est le fait que le spectre du signal vocal présente une certaine stabilité pendant plusieurs centièmes ou même dixièmes de secondes. On pourra donc appliquer une transformée de Fourrier aux intervalles de stabilité du spectre et pouvoir isoler les différentes fréquences qui le composent. L'analyse peut être réalisée en utilisant des filtres analogique (unique ou multiples en parallèle) ou des filtres numériques. Les filtres numériques présentent une précision plus élevée et plus de possibilité de simulation mais avec un prix de complexité considérable.

L'analyse temporelle utilise le fait que certains évènement, comme la fermeture brusque du conduit vocal, sont mieux caractérisée par l'évolution temporelle du signal que par son spectre. La fonction d'autocorrélaton, le taux de passage à zéro et la prédiction sont les principales techniques d'analyse temporelle.

L'analyse prédictive est sûrement la plus utilisée. Le conduit vocal, filtrant le signal d'excitation, peut être assimilé à un filtre récursif : avec une bonne approximation, le signal émis à un instant donné peut être calculé à partir des valeurs qu'il a prises aux instants antérieurs (exploitation de l'aspect redondant de la parole).

Les analyses fréquentielles exigent d'être effectuées sur une durée suffisamment langue. Il en résulte qu'elles sont peu adaptées à l'étude des phénomènes évoluant rapidement. La prédiction élimine une part importante de la redondance que présente le signal de la parole et fait, par conséquent, débarrasser l'analyse des éléments n'apportant pas de nouvelles informations.

1.5.3 Représentation du signal de la parole

Le codage prédictif linéaire Il repose sur l'hypothèse de linéarité du processus de production de la parole. Chaque échantillon peut être prédit à partir d'une pondération linéaire d'un nombre fini d'échantillons précédents, étant donné que la forme du conduit vocale n'évolue pas rapidement.

Le codage prédictif linéaire est largement utilisé en traitement de la parole notamment en transmissions. Le model est de plus facile à mettre en oeuvre dans les systèmes à temps réel. Ce model par définition ne prend pas en charge les phénomènes non linéaire, et de plus, il n'est pas optimisé pour la tâche de reconnaissance. En effet, des travaux ont montré qu'il est possible de mettre en oeuvre une meilleure représentation, et on fait naissance à des modèles plus optimisés comme la prédiction linéaire perceptive, la prédiction linéaire perceptive RASTH, le codage WLPC...

Le codage cepstrale la représentation cepstrale est une représentation non paramétrique : elle ne fait pas intervenir de model comme le cas du codage linéaire. On obtient le cepstre en appliquent une transformée de Fourrier au signal, calculer le logarithme du résultat, à qui on applique en fin une transformée de Fourrier inverse.

Le cepstre possède plusieurs propriétés intéressantes qui en font une représentation efficace. Parmi ces propriétés, le logarithme qui permet par un procédé de filtrage l'élimination des effets convolutifs dans le domaine temporel. En effet, grâce à la fonction logarithmique, les bruits deviennent additifs et une simple soustraction (soustraction cepstrale) permet l'annulation de ces bruits.

Le codage MFCC (Mel Frequency Cepstral Coding) C'est la technique de codage la
plus utilisée en traitement de la parole. Elle intègre la notion de bancs de filtres qui

sont déployés non par une échelle en Hz mais sur une échelle non linéaire : l'échelle de Mel. Cette échelle est issue de la connaissance sur la perception humaine. La résolution perceptive des fréquences diffère selon qu'on écoute des sons de basses ou de hautes fréquences.

Le codage MFCC représente la référence des procédés d'extraction de caractéristiques, et toutes les méthodes proposées doivent s'y comparer.[113]

1.6 Modèles de reconnaissance

1.6.1 Modèles markoviens

Dans le cadre des modèles markoviens, les unités acoustiques sont modélisées par des chaînes de Markov cachées. A chaque état du modèle est associée une distribution de probabilité modélisant la généralisation des modèles acoustiques via cet état.[17]

L'ensemble des paramètres markoviens (états, matrice de transition...) sont estimés lors d'une phase d'apprentissage. Les différentes méthodes d'apprentissage permettent, à partir d'un certain échantillon, de déterminer les paramètres qui maximisent les probabilités de génération des unités acoustiques.

Les modèles de reconnaissances markoviens utilisent, en outre des paramètres habituels, des modèles de langage. Ils permettent d'estimer la probabilité de production des mots en connaissant leur historique. Lors de la phase d'apprentissage, on calcule

les probabilités d'apparition des unités à partir des évènements observés, et de généralise par la suite ces estimations à des évènements qui n'ont pas été observés.

A la phase de reconnaissance, le système génère un ensemble de mots de départ, dits hypothèses, à partir des informations récoltées lors de l'apprentissage. Cet ensemble sera modélisé sous forme d'un graphe ou d'un treillis de mots. Le système explore ce graphe afin de trouver le chemin qui maximisera la probabilité de correspondance.

Les modèles markoviens sont les plus utilisés dans le domaine de reconnaissance vocale et constituent un domaine de recherche très prometteur. Leurs principal problème est la difficulté de leur intégrer des informations non acoustiques.

1.6.2 Modèles de classification

Dans ce type de modèles, la reconnaissance vocale est considérée comme un problème de classification automatique. La classification automatique consiste à attribuer une parmi un ensemble de classes à chacun des objets à classifier. La structure des classes et leurs nombre peuvent être connus avant la classification ou déterminés automatiquement par le système. Dans le premier cas, on parle de classification supervisée. Elle repose sur un échantillon de prototypes qui représentent chacun une classe. Les objets seront en suite répartis selon les classes auxquelles ils appartiennent. Chaque unité acoustique représente une classe. Les prototypes sont constitués manuellement lors d'une phase d'apprentissage. Par la suite, le modèle estime, pour chaque unité à reconnaître, sa classe appropriée. Il existe plusieurs méthodes pour estimer les correspondances phonétiques : les méthodes probabilistes gaussiennes, les réseaux de neurones, la règle du proche voisin, mesures de dissimilarité, etc.

La classification a largement été appliquée à des problèmes similaires comme la reconnaissance des formes et le recalage des images médicales. On utilise généralement la méthode du plus proche voisin. En reconnaissance vocale, c'est plutôt les mesures de dissimilarité qui sont utilisées. Etant donné que les approches algorithmiques de classification sont relativement anciennes, ce modèle permet de profiter de tous les résultats théoriques et les avancées des travaux en la matière.

1.6.3 Modèles à comparaison dynamique

La méthode DTW (Dynamic Time Warping) est une méthode de résolution dynamique. Elle est basée sur le principe de recalage temporel. Les images acoustiques des unités sources et celles des unités à reconnaître ne sont pas parfaitement identiques

à cause de la différence dans les vitesses de locution. Ce principe est pratiquement le même que celui utilisé dans la reconnaissance des formes et il a largement été utilisé pour le recalage des images médicales. Le modèle utilise une mesure de différence entre les vecteurs sources et ceux du mot à identifier pour tenter de trouver des correspondances optimales.

L'algorithme commence par l'estimation locale des distances entre les deux ensembles de vecteurs. Il utilise ensuite une méthode de programmation dynamique pour obtenir un optimum global qui minimise la différence accumulée entre les deux ensembles.

Dans ce type de modèles, on représente chaque couple d'unités phonétiques dans une matrice dont les lignes représente les vecteurs de l'unité de référence, et les colonnes ceux de l'unité à reconnaître. Les éléments de la matrice représentent les différences locales entres les vecteurs. Le problème revient donc à trouver un chemin optimal (minimal) entre le premier et le dernier élément de la matrice.

1.6.4 Autres modèles

La quantification vectorielle est une méthode non-paramétrique qui permet de décrire un ensemble de données par un faible nombre de vecteurs formant un dictionnaire associé aux données. Le dictionnaire est en général calculé de telle façon que la distance moyenne entre un vecteur issu des données et son plus proche voisin dans le dictionnaire soit la plus petite possible. La quantification vectorielle est une technique de groupage qui est d'autant plus adaptée que les données présentent naturellement des "points d'accumulation" autour desquels la densité de vecteurs issus des données est importante. Compte tenu de la nature du signal de parole, le choix d'un tel modèle

semble assez judicieux. En general, la quantification vectorielle est realisee par une methode dite "spliting K-means" (optimisations successives de dictionnaires de taille croissante) qui permet de contourner le delicat problème de l'initialisation de l'algorithme de recherche iterative des vecteurs du dictionnaire.

Le modèle de melange de distributions gaussiennes (Gaussian mixture model (GMM)) consiste à supposer que la distribution des donnees peut être decrite comme une somme ponderee de densites gaussiennes multidimensionnelles. Ce modèle de melange est classique dans le domaine de la reconnaissance de forme car il correspond à une situation où les donnees appartiennent à un ensemble de classes distinctes, avec une probabilite d'appartenance propre à chaque classe. Le cas particulier considere ici est celui où dans chaque classe les donnees suivent une loi gaussienne. Ce choix tient essentiellement au fait que la loi gaussienne appartient à une famille de distributions dite exponentielles pour lesquelles le problème de l'identification des composantes du melange se trouve simplifie. Pour le signal de parole, ce modèle ne paraît donc pas deraisonnable et il est d'autre part assez proche de la caracterisation fournie par la quantification vectorielle. La difference etant qu'avec la quantification vectorielle, on se contente de mettre en evidence un certain nombre de "points d'accumulation" des paramètres mesures, alors qu'avec le modèle de melange de distributions gaussiennes, on cherche en plus à decrire la distribution des paramètres mesures autours de ces points d'accumulation.

1.7 Apprentissage

Quelque soit le modèle considere, il doit obligatoirement debuter par une phase d'apprentissage. L'apprentissage automatique (Machine Learning) est un procede qui permet au système de generaliser les connaissances qui a pu apprendre, grâce à des donnees dejà traitees manuellement, à des donnees inconnues. C'est une technique d'intelligence artificielle qui est appliquee dans une large gamme de domaines, en premier lieu en classification.

Dans les systèmes de parole, l'apprentissage constitue une phase cruciale. Pour chaque unite phonetique (mot ou phonème), le système calcule une estimation à partir d'un echantillon de donnees de reference. Le choix de cet echantillon est très important: il faut à la fois minimiser la taille et generaliser la presentation. Ces deux objectifs sont plus ou mois contradictoires. Si l'on choisi un ensemble d'echantillons très petit, on risque d'avoir une mauvaise representation comme reference. Ce qui entrainerait de mauvaises consequences lors de la reconnaissance. De même, avec un ensemble très

grand, le problème peut devenir complètement irrésolvable. Il convient donc de trouver un compromis.

Dans les modèles markoviens, le système apprend, à partir d'un ensemble de mots donné, à prévenir l'apparition d'un mot à partir des mots déjà apparus. Dans les modèles de classification, l'apprentissage consiste à adapter le système à classifier des phonèmes dont l'image acoustique est légèrement différente de celle du prototype source correspondant. Quant aux modèles à base de DTW, l'apprentissage se préoccupe plutôt de surpasser les décalages temporels dus aux variations de vitesses de locution.

1.8 Traitements linguistiques de haut niveau

Les traitements linguistiques ne sont pas tous disponibles dans tous les systèmes de reconnaissance. Par exemple, dans les systèmes de commande à mots isolés, aucun traitement linguistique n'est nécessaire, voire n'est utile. Dans les systèmes de dictée, une analyse lexicale et syntaxique est incontournable; par contre, aucun intérêt ne serait apporté par une analyse sémantique. Mais dans les applications de dialogue oral par téléphone, toutes les analyses doivent être mises en coopération pour qu'elle soit plutôt efficace.

Dans la plupart des systèmes, ces différents niveaux d'analyse linguistique sont séquentiels et donc indépendant de point de vue temporel. Cependant, une combinaison entre eux peut s'avérer bénéfique. Par exemple, l'introduction d'une analyse sémantique dans la phase de reconnaissance peut améliorer la précision et lever l'ambigüité. Cette technique est en quelque sorte implicitement introduite dans les modèles markoviens dans lesquels, la probabilité de correspondance d'un mot ne dépend pas seulement de son image acoustique, mais aussi de suite de mots qui le précèdent.

Les applications de dialogue oral téléphonique se répondent de plus en plus et couvre une grande variété de domaines. Dans ce type d'applications, un module de compréhension (d'analyse sémantique) est indispensable pour la traduction des phrases, issues du module de reconnaissance et dont la nature est très spontanée, à des commandes effectives.

Dans certaines applications, la compréhension s'effectue suivant deux phases d'analyses séquentielles. La première phase établie un découpage des phrases en groupes syntaxiques (groupe nominal, groupe verbal, ...), et de leurs associer les étiquettes sémantiques correspondantes. La phase suivante effectue un rattachement sémantico-

pragmatique qui a pour but de relier les constituants minimaux résultants de la première phase, et de définir les dépendances entre eux.

D'autres modèles tels que les arbres de décision sémantiques, le boosting ou les SVM, combinent les opérations de reconnaissance et de compréhension en une seule phase. Les arbres de décision sémantiques sont généralement les plus utilisées. C'est une technique qui repose sur les grammaires régulières. Les règles de la grammaire sont constituées automatiquement à partir d'un corpus d'entraînement.

Un des défis des applications de compréhension orale, qui doivent souvent confronter, est l'aspect spontané de la parole. Le problème se présente principalement dans les hésitations, les fragments inutiles, les répétitions et les déformations syntaxiques et sémantiques. Ces applications doivent donc filtrer les phrases reconnues pour extraire ce qui est utile de ce qui ne l'est pas.

1.9 Conclusion

Dans ce chapitre nous avons passé en revu les éléments essentiels intervenant dans le processus de traitement de la parole. Nous avons d'abord illustré certains aspects du traitement du signal de façon général ainsi que les caractéristiques du signal vocal, en faisant apparaître en particulier l'importance et la complexité de l'information qu'il contient. Par la suite, nous avons présenté les différents niveaux de traitement de la parole. Après avoir décrit de façon général son déroulement, nous avons détaillé, dans une certaine mesure, le processus de traitement de la parole en décrivant les différents éléments qu'y interviennent.

Dans une autre partie, nous avons traité des modèles de reconnaissance. Nous avons essayé d'illustrer les principaux modèles de reconnaissance et éventuellement certains avantages et inconvénients. En fin nous avons survolé rapidement la phase d'apprentissage et les traitements linguistiques, notamment les problèmes relatifs à la compréhension de la parole spontanée.

Il reste néanmoins plusieurs autres problèmes d'importance capitale, en particulier ceux qui ont un rapport avec le processus de décodage comme la détermination de la fréquence fondamentale, la recherche des formants et la suppression des bruits de fond. Ces problèmes ont le plus souvent une part intéressante dans la complexité du domaine. Nous n'en dirons pas davantage dans ce mémoire, une étude exhaustive ferait intervenir de nouveaux concepts et dépasserait largement le cadre de ce travail.

Chapitre 2

Algorithmes évolutionnaires

Les algorithmes évolutionnaires regroupent un ensemble d'algorithmes inspirés du processus d'évolution naturelle. Ces algorithmes sont utiles pour la résolution de problèmes où les algorithmes classiques d'optimisation, d'apprentissage ou de conception automatique sont incapables de produire des résultats satisfaisants. Ils appartiennent à la classe des méthaheuristiques qui, à leur tour, font partie des méthodes heuristiques. Ce sont des méthodes d'approximation qui fournissent des résultats de bonne qualité, en sacrifiant éventuellement l'exactitude ou l'optimalité de la solution, à des problèmes souvent réputés difficiles pour lesquels on ne connait pas de méthodes exactes plus efficace.

2.1 Principes d'inspiration

- Les individus d'une espèce à grande fertilité ont plus de chance de survivre pour longtemps.

- Sous l'absence d'influence externe, la dimension d'une espèce reste, en gros, constante. - Encore, sans influences externes, la ressource de nourriture est limitée mais reste équilibrée avec le temps.

- Les individus luttent pour la survie à cause de la concurrence sur les ressources limitées.

- Il n'existe pas d'individus équivalents, notamment pour les espèces à reproduction sexuelle.

- Les différences entre individus peuvent affecter leurs aptitudes, et par conséquent, leur capacité de survie.

- Les bons individus ont plus de chances de survivre et de produire d'autes bons individus.

- Les individus qui survivent transmettront, probablement, leurs caractéristiques

- Les espèces évoluent lentement, et s'adaptent de plus en plus à leur environnement.

2.2 Cycle de base d'un algorithme évolutionnaire

Tous les algorithmes évolutionnaires font évoluer un ensemble (population) de solutions (individus). La population initiale est générée aléatoirement. En suite, Pour chaque individus, on calcul le résultat d'une fonction d'évaluation (fitness) mesurant le degré de leur adaptation. L'utilité de chaque individu étant maintenant connue, l'algorithme filtre la population courante en éliminant les individus ayant obtenus un mauvais résultat lors du processus d'évaluation, tout en préservant les autres. Après avoir sélectionné les bons individus, ces derniers seront combinés ou variés afin d'en produire de nouveaux. Les nouveaux individus sont sensés être d'une qualité aussi bonne que ceux de la génération précédente. Ils seront passés à leur tour à la phase de sélection, et ainsi de suite jusqu'à atteindre un des critères d'arrêt.L'algorithme devrait tendre, de plus en plus, vers la solution optimale. Le critère d'arrêt est le plus souvent relatif au nombre de générations. Mais il peut cependant dépendre du degré d'évolution (amélioration) de l'algorithme, de la distance entre individus ou du facteur de temps.

2.3 Principales familles

2.3.1 Algorithmes génétiques

Les algorithmes génétiques sont les plus populaires des algorithmes évolutionnaires. Ils impliquent l'évolution d'une population de vecteurs de dimension fixe composés de caractères, généralement des bits. L'idée des algorithmes génétiques est vaguement inspirée des chaînes d'ADN, qui composent tout organisme vivant. Les AG sont utilisés dans le but de découvrir une solution, généralement numérique, résolvant un problème donné, et ce sans avoir de connaissance à priori sur l'espace de recherche. Seul un critère de qualité est nécessaire pour discriminer différentes solutions. Dans la plupart des cas, ce critère, l'adéquation, est une mesure objective qui permet de quantifier la capacité de l'individu à résoudre le problème donné. Le processus de recherche s'effectue en appliquant itérativement à une population de solutions potentielles des opérations de variation génétique (généralement le croisement et la mutation), et des opérations de sélection naturelle biaisées vers les individus les plus forts. En utilisant ce processus, la population de solutions potentielles évolue dans le temps jusqu'à ce

qu'un certain critère d'arrêt soit atteint. Dans un contexte d'optimisation de fonctions à paramètres réels, une variante importante des AG consiste à représenter les individus directement par des vecteurs de nombres réels.

2.3.2 Programmation génétique

La programmation génétique est un paradigme permettant la programmation automatique d'ordinateurs par des heuristiques basées sur les mêmes principes dévolution que les algorithmes génétiques : des opérations de variation génétique et des opérations de sélection naturelle. La différence entre la programmation génétique et les algorithmes génétique réside essentiellement dans la représentation des individus. En effet, la programmation génétique consiste à faire évoluer des individus dont la structure est similaire à des programmes informatiques. La programmation génétique représente les individus sous forme d'arbres, c'est-à-dire des graphes orientés et sans cycle, dans lesquels chaque noeud est associé à une opération élémentaire relative au domaine du problème. Plusieurs autres représentations comme des programmes linéaires et des graphes cycliques, ont été utilisées depuis. La programmation génétique est particulièrement adaptée à l'évolution de structures complexes de dimensions variables.

2.3.3 Stratégies d'évolution

Les stratégies d'évolution représentent les individus comme un ensemble de caractéristiques de la solution potentielle. En général, cet ensemble prend la forme d'un vecteur de nombres réels de dimension fixe. Les stratégies dévolution s'appliquent à une population de parents à partir de laquelle des individus sont sélectionnés aléatoirement afin de générer une population de descendants. Ceux-ci sont ensuite modifiés par des mutations qui consistent à ajouter une valeur générée aléatoirement selon une fonction de densité de probabilité paramétrée. Les paramètres de la fonction de densité de probabilité, nommés les paramètres de la stratégie, évoluent eux aussi dans le temps selon les mêmes principes que les paramètres caractérisant les individus. Pour former la nouvelle population, des individus sont choisis parmi les meilleurs individus des descendants, ou parmi les meilleurs individus des parents et descendants. Les stratégies dévolution modernes peuvent aussi intégrer une approche multi-échelle ou des stratégies d'évolution sont imbriquées.

2.3.4 Programmation évolutionnaire

La programmation évolutionnaire a été initialement conçue dans le but de faire évoluer des machines à états finis et a été par la suite étendue aux problèmes d'optimisation de paramètres. Cette approche met l'emphase sur la relation entre les parents et leurs descendants plutôt que de simuler des opérateurs génétiques d'inspiration naturelle. Contrairement aux trois autres algorithmes évolutionnaires classiques, la programmation évolutionnaire n'utilise pas une représentation spécifique mais plutôt un

modèle évolutionnaire de haut niveau, jumelé à une représentation et à un opérateur de mutation directement appropriés au problème à résoudre.

Pour effectuer de la PE, une population de solutions potentielles au problème est d'abord générée aléatoirement. Chaque individu de la population produit un ensemble de descendants résultant de mutations. Une opération de sélection naturelle est alors appliquée afin de former une nouvelle population. Le processus de mutation-sélection est répété itérativement jusqu'à ce qu'une solution acceptable soit trouvée. ¹

2.4 Population et représentation des individus

La population est la représentation de l'ensemble des solutions possibles. Indépendamment, les individus sont des éléments statiques qui ne peuvent pas s'adapter, c'est la population qui forme donc l'unité d'évolution et d'adaptation. C'est pour cette raison que la plupart des opérateurs de sélection prennent en compte la totalité de la population. La diversité d'une population est la mesure du nombre des différentes solutions existantes. Il n'existe aucune façon de mesurer la diversité d'une population, on se réfère généralement au nombre d'aptitudes différentes, au degré de cette différance ou au nombre d'individus différents.[?]

A chaque itération d'un algorithmes évolutionnaires, de nouveaux individus sont créés. A la prochaine itération, les individus de la génération précédente peuvent être conservés (avec de mêmes ou de différentes chances que ceux de la génération courante) ou tout simplement jetés. Les algorithmes qui changent complètement de génération (c'est-à-dire qui ne conservent que les nouveaux individus à la prochaine itération) sont appelés algorithmes à sélection générationnelle (Extinctive EA). Par contre, ceux qui ne modifient qu'une partie de la population sont des algorithmes à remplacement stationnaire ou préservatif (Préservative EA). Dans ce cas la population de la prochaine génération est constituée de la combinaison de la population courante et la nouvelle génération.

Les algorithmes générationnelles à leur tour peuvent être divisés en algorithmes à sélection gauche ou droite. Dans le premier cas, les bons individus ne sont pas autorisés à participer à la reproduction de la nouvelle génération pour éviter une convergence prématurée des individus. Contrairement, se sont les mauvais individus qui n'ont pas le droit de participer à a reproductin pour garantir une certaine qualité.

Il existe un autre type d'algorithmes évolutionnaires, souvent appelés algorithmes élitistes(Elitist algorithms), qui assurent qu'au moins une copie des meilleurs individus de la génération courante sera présente dans la prochaine génération. Les algorithmes évolutionnaires à état stable (Steady-State EA ou SSEA) sont des algorithmes préservatifs qi ont la particularité de produire un nombre d'individus faible comparé au nombre d'individus qui ont participés à leur production.

Le premier pas dans la définition d'un algorithmes évolutionnaires est de lier le vrai monde au Monde des algorithmes évolutionnaires. Il s'agit de définir une sorte de passerelle entre le contexte original du problème et l'espace du problème à résoudre où l'évolution aura lieu. Les objets qui forment des solutions dans le contexte original sont appelés phénotypes, et leurs représentations génotypes.

L'efficacité d'un algorithme dépend pleinement du choix de codage. Trouver une structure de donnée et un codage adéquat est dès lors un des objectifs les plus importants. En organisant les données d'une certaine manière on favorise leur traitement automatique efficace et rapide. Adopter une structure de données appropriée pour un problème informatique peut également contribuer à decomplexifier de manière significative une application informatique et ainsi participer à la diminution du taux d'erreurs.[142]

Il existe principalement trois types de représentations dans l'ensemble des algorithmes évolutionnaires. La représentation binaire est le cadre générale des algorithmes génétiques classiques. Chaque individu est représenté par un vecteur binaire où chaque élément peut prendre la valeur 0 ou 1. Cette représentation s'adapte bien à des problèmes où les solutions potentielles ont une représentation binaires canoniques. Elle s'applique aussi à des problèmes d'optimisation continus, mais il est alors nécessaire d'adopter une technique de codage approproiée.

Dans la représentation réelle, l'espace de recherche est l'espace des réels ou un sous ensemble. Cette représentation a été initialement introduite par les stratégies d'évolution, mais son utilisation s'est rapidement étendue aux autres types d'algorithmes évolutionnaires.

Le dernier type est celui utilisant une structure arborescente. Ce type de codage est à la base de la programmation génétique pour la représentation et l'évaluation des instructions des programmes informatiques. Il a été en suite utilisé comme une technique de codage supplémentaire dans les algorithmes génétiques.

2.5 Evaluation et Sélection

Dans les approches classiques, l'évaluation d'un individu ne dépend pas de celle des autres. Le résultat fourni par la fonction d'évaluation va permettre d'accepter ou de refuser un individu pour ne garder que les individus ayant le meilleur coût en fonction de la population courante. Cette méthode permet de conserver les individus performants et d'éliminer progressivement les individus peu adaptés. C'est donc la fonction qui permet de mesurer le degré d'aptitude d'un individu à son environnement. Dans plusieurs applications pratiques, cette qualité est croissante avec la qualité de solution, mais dans certains problèmes, notamment ceux d'optimisation, cette qualité peut être décroissante.

Le fait que le processus d'évaluation soit individuel a sûrement ses avantages : l'algorithme n'a besoin ni de conserver des historiques ni de prendre en compte le reste de la population. Cela permet de gagner en mémoire et d'être indépendant de la taille de la population. Cette individualité permet en outre de profiter davantage des possibilités de parallélisassion.

A mesure de ne sélectionner que les meilleurs individus, ces derniers peuvent tendre à se regrouper et à se ressembler. Dans ce cas, la population risque de se trouver dans un cas très homogène et de ne plus évoluer. Plusieurs techniques ont été proposées pour pouvoir échapper à ce problème de diversification. Ces techniques, comme le scaling et la sharing[86, 148], utilisent des principes tels que l'historique d'évaluation pour tenter d'incorporer plus d'informations et de refléter, par conséquent, de façon plus générale, l'état globale de la population.

La sélection permet de filtrer la population courante, en se basant sur la fonction d'évaluation, de telle façon à permettre aux bons individus de survivre et de devenir des parents. Il existe un bon nombre de méthodes de sélection dans la littérature, nous présentons brièvement quelques unes ci-dessous.

2.5.1 Sélection par roulette

Il s'agit de la méthode la plus courante. Les individus parents sont sélectionnés proportionnellement à leur performance. Meilleur est le résultat fourni par l'évaluation d'un individu, plus grande est sa probabilité d'être sélectionné. Le nombre de fois qu'un individu sera sélectionné est égal à son évaluation divisée par la moyenne de l'évaluation de la population totale. Plus exactement, la partie entière représente le nombre de fois qu'il sera sélectionné, et la partie flottante la probabilité qu'il aura d'être

sélectionné à nouveau. On peut comparer cette méthode de sélection a une roulette de casino sur laquelle sont placés tous les individus de la population, la largeur allouée a chacun des individus étant en relation avec leur valeur d'évaluation. Ensuite, la bille est lancée et s'arrête sur un individu. Les meilleurs individus peuvent ainsi être tirés plusieurs fois et les plus mauvais ne jamais être sélectionnés.

2.5.2 Sélection par rang

La sélection par roulette présente des inconvénients lorsque la valeur d'évaluation des individus varie énormément. La sélection par rang trie d'abord la population par évaluation. Ensuite, chaque individu se voit associé un rang en fonction de sa position. Ainsi le plus mauvais individu aura le rang 1, le suivant 2, et ainsi de suite jusqu'au meilleur individu qui aura le rang N, pour une population de N individus. La sélection par rang d'un individu est identique à la sélection par roulette, mais les proportions sont en relation avec le rang plutôt qu'avec la valeur de l'évaluation. Avec cette méthode de sélection, tous les individus ont une chance d'être sélectionnés. Cependant, elle conduit à une convergence plus lente vers la bonne solution. Ceci est du au fait que les meilleurs individus ne diffèrent pas énormément des plus mauvais.

2.5.3 Sélection steady-state

Le principe de base consiste à garder une grande partie de la population à la génération suivante. A chaque génération sont sélectionnés quelques individus, parmi ceux qui ont les meilleures évaluations, pour créer un ensemble d'individus enfants. Les individus ayant les évaluations les plus faibles sont ensuite remplacés par les nouveaux. Le reste de la population survit à la nouvelle génération.

2.5.4 Sélection par tournoi

Soit une population de m individus. On forme m paires d'individus. Ensuite, il faut déterminer un nouveau paramètre, à savoir la probabilité de victoire du plus fort. Cette probabilité représente la chance que le meilleur individu de chaque paire soit selectionné. En principe cette probabilité doit être grande. A partir des m paires, on détermine ainsi m individus pour la reproduction.

2.5.5 Elitisme

A la création d'une nouvelle population, il y a de grandes chances que les meilleurs individus soient modifiés, et donc perdus après les opérations de reproduction. Pour éviter cela, on utilise la méthode élitiste. Elle consiste à copier un ou plusieurs des

meilleurs individus dans la nouvelle génération. Ensuite, on génère le reste de la population selon l'algorithme de reproduction usuel. Cette méthode permet de ne pas perdre les meilleures solutions.

2.5.6 Sélection de seuil

La sélection de seuil ou sélection déterministe (truncation selection), sélectionne un nombre d'individus inférieur à la taille de la population supposée après sélection. Si la taille de la population après sélection est s, alors la sélection de seuil choisi un nombre k < s (généralement s/2 ou s/3) des meilleurs individus et les insert autant de fois que nécessaire pour que la taille maximale de la population soit atteinte. La sélection de seuil est principalement utilisée dans les stratégies d'évolution de type (u, A)-ES ou (u+ A)-ES. Récemment, lassig et al.[?] a démontré que la sélection de seuil est la stratégie de sélection optimale pour le croisement, pourvu que la valeur de k soit judicieusement choisie.

2.6 Reproduction

Les algorithmes évolutionnaires utilisent les informations recueillies dans les générations précédentes pour créer l'ensemble des individus de la prochaine génération. Les opérations associées sont la création, la duplication, la mutation et la recombinaison (ou le croisement).

2.6.1 Création et duplication

La création est la production brute d'un individu de façon complètement aléatoire sans aucun modèle préalable. C'est ce qui se passe lors de la génération de la population initiale. Toutefois, le programme peut faire appel à la création des générations qui suivent et ce afin de préserver la diversité de la population. La duplication est analogue à la division cellulaire. Elle est généralement utilisée pour garantir la présence d'un nombre minimal de bons individus en évitant leur disparition à force des mutations successives.

2.6.2 Mutation

La mutation est un opérateur qui agit sur un seul individu pour en produire un autre légèrement modifié. C'est un opérateur purement aléatoire qui a pour rôle d'éviter à l'algorithme de se retrouver dans des situations de saturation et de préserver la

diversité de la population. Mais il peut cependant constituer le principal, voir le seul, opérateur de reproduction.

Dans le cas du codage binaire, la mutation consiste à inverser les bits d'un génotype avec une faible probabilité. La mutation la plus employé dans les codages binaires est la mutation stochastique qui inverse chaque bit indépendamment avec une certaine probabilité relative à la taille du génotype. Un autre type de mutation est l'inversion d'un seul bit choisi au hasard avec une certaine probabilité.

La principale technique utilisée pour la mutation réelle est l'ajout d'un bruit Gaussien aux différentes composantes du vecteur. La difficulté de cette approche est l'ajustement de l'écart-type du bruit généré. En effet, au début de l'évolution d'une population, l'écart-type doit être assez élevé pour générer de fortes perturbations et ainsi explorer rapidement tout l'espace de recherche. Une fois les pics de la fonction étudiée localisés, l'algorithme doit être capable de déterminer avec précision les solutions optimales.

2.6.3 Recombinaison

La recombinaison est utilisée pour créer de nouveaux individus en combinant les éléments déjà existant. Elle consiste à échanger un ou plusieurs fragments des deux génotypes. Les croisements binaires les plus utilisés opèrent sur un fragment, deux fragments ou sur tous les fragments (croisement uniforme). Dans le cas de représentation réelle, il y a deus manières de recombiner deux génotypes : choisir l'un des deux individus (croisement discret ou par dominance), ou combiner linéairement les deux (croisement intermédiaire ou linéaire). Pour la représentation structurée comme le cas des arbres binaires, la recombinaison se fait principalement par échange de structures (sous arbres).

2.7 Application dans les systèmes de parole

Les algorithmes évolutionnaires ont été appliqués avec succès dans de nombreux domaines d'optimisation mono et multi-objectif, économie et finances, biologie, robotique, médecine etc ². Dans certaines applications, les algorithmes évolutionnaires ont pu fournir des résultats qui n'ont jamais été obtenus avec d'autres méthodes (le meilleur résultat pour le PVC a été obtenu avec un algorithme génétique).

Cependant, leur usage dans le domaine de traitement de la parole est très restreint, notamment dans le processus de reconnaissance proprement dit. Les résultats théoriques, à leur tour sont pratiquement inexistants : aucun model évolutionnaire n'a été définie pour le problème de reconnaissance. Les algorithmes évolutionnaires sont utilisés soit comme des méthodes d'optimisation pour d'autres modèles (comme le model HMM), soit comme des model de traitement secondaires (comme l'adaptation au locuteur). Et dans la plupart des cas, ce sont des algorithmes génétiques qui sont utilisés.

Les premiers travaux ont porté sur l'adaptation des systèmes aux variations phonétiques et à l'amélioration de leur robustesse[11]. Des stratégies d'évolution et des algorithmes génétiques ont été hybridés avec des réseaux de neurones pour augmenter la robustesse des systèmes de reconnaissance aux variabilités dues à l'environnement. Les réseaux de neurones font partie des réseaux adaptatifs non linéaires[115]. L'idée principale est d'utiliser un algorithmes évolutionnaires pour se situer dans des espaces de recherche globaux et prometteurs, et d'utiliser un réseau de neurone pour rechercher des optima locaux. L'apport des algorithmes évolutionnaires était dans le fait que la diversité de la population ainsi que sa taille sont les facteurs clé pour une bonne adaptation aux environnements qui changent rapidement.

D'autres travaux ont essayé d'adapter les paramètres du modèle acoustique avant le début de la reconnaissance avec un algorithme génétique[139]. Il s'agit principalement de remédier aux problèmes relatifs aux changements des paramètres du signal acoustique tels que la fréquence d'échantillonnage et le débit binaire. Les paramètres du signal à reconnaître ne sont pas nécessairement les mêmes que ceux du signal d'apprentissage, et une adaptation devient dès lors nécessaire. Le principe est d'associer à chaque vecteur source une matrice de transformation, et à chaque caractère d'un individu une probabilité de mutation. Ces individus seront sélectionnés selon les taux de transformation obtenu avec les vecteurs sources transformés, comparés au model acoustique cible.

Dans les model a base de DTW, une idée consiste à remplacer la programmation dynamique par un algorithme génétique pour estimer les différences cumulées entre les vecteur[155, 156]. La population est un ensemble de chemins qui seront combinés et filtrés jusqu'à aboutir à un chemin optimal.

Les techniques récentes de la vérification du locuteur reposent de plus en plus sur des approches multi codeurs. Un algorithme génétique a été mis en oeuvre pour optimiser la complémentarité entre les codeurs.[22]

Un algorithme génétique a aussi été utilisé en coopération avec un réseau de neurones pour la segmentation et le regroupement du locuteur. Il s'agit d'identifier les segments du signal produits par le même locuteur. Elle a pour objectif de détecter les moments de changement du locuteur. Elle est suivie d'une étape de regroupement qui consiste à étiqueter les segments obtenus en fonction des locuteurs. Son domaine d'intérêt est essentiellement dans l'indexation des documents sonores.[29]

2.8 Avantages et inconvénients

- Un large domaine d'application les algorithmes évolutionnaires ont été utilisés avec succès dans une large gamme de problèmes. Ceci est principalement dû au fait de la simplicité et de l'intuitivité du processus de l'évolution naturelle.

- Adaptés aux espaces de recherche complexes contrairement aux algorithmes évolutionnaires, la définition des autres méthodes heuristique à des problèmes complexes est une tâche très difficile.

- Faciles à paralléliser le concept de population et la faiblesse, ou voir la non existence, de dépendances entre les individus rend la parallélisation très facile et permet ainsi de réduire considérablement le temps d'exécution.

- Complexité la simplicité de l'idée de base des algorithmes évolutionnaires sera payée par une grande consommation en termes de ressources.

- Difficulté d'ajustement de paramètres ceci constitue le principal problème des algorithmes évolutionnaires[150]. Certains algorithmes sont conçus pour résoudre des problèmes spécifiques et leur adaptation sera très difficile. Les autres algorithmes plus généraux nécessitent un grand nombre de paramètre à ajuster. Par ailleurs, les algorithmes évolutionnaires sont très sensible à la fonction d'évaluation et un seul changement dans le problème peut mener à un comportement tout à fait différent.

- Nature heuristique la nature heuristique des algorithmes évolutionnaires implique, par définition, qu'ils constituent des méthodes d'approximation qui ne donnent aucune garantie d'exactitude ou d'optimalité. En outre, il n'existe aucune façon de prédire leurs temps d'exécution.

2.9 Conclusion

Nous avons présenté dans ce chapitre une vue d'ensemble des algorithmes évolutionnaires, et de leur modeste implication dans les systèmes de reconnaissance automatique de la parole. Nous avons essayé dans un premier lieu de caractériser les principes d'évolution naturelle desquels les algorithmes évolutionnaire ont inspirés. Et après une présentation de leur fonctionnement de base, nous avons détaillé chacun de leurs composants principaux, en listant éventuellement quelques exemples de fonctionnement.

Dans un deuxième lieu, nous avons récapitulé, dans la mesure de possible, les travaux sur les systèmes de parole dans lesquels les algorithmes évolutionnaires ont contribué à l'amélioration de leur fonctionnement. Nous avons vu que ces contributions étaient très restreintes, et que dans la plupart du temps, elles étaient limitées à des améliorations secondaires et n'utilisaient pour cela que des algorithmes génétiques.

Plusieurs techniques et résultats concernant le fonctionnement des différents éléments des algorithmes évolutionnaires n'ont pas été décrits. Ceci est du au fait que les plus grands apports des algorithmes évolutionnaires ont concerné des problèmes d'optimisation et notamment des problèmes d'optimisation multi-objective. Par conséquent, une grande partie des travaux et résultats théoriques ont été réalisés suivant cette optique, et ne peuvent généralement apporter aucun intérêt aux systèmes de reconnaissance.

Nous présentons ici une étude détaillée de deux familles d'algorithmes évolutionnaires : les stratégies d'évolution et la programmation génétiques. Le choix des deux méthodes a été dans l'objectif de réaliser une étude aussi générale que possible des algorithmes évolutionnaires. Les deux méthodes étant très différentes dans leurs objectifs de base, dans la façon de représenter les individus et dans leurs opérateurs de variation. Cela permet en outre de déceler les avantages et les inconvénients de chacune. Nous traiterons plus en détail de toutes ces différences et autres dans le prochain chapitre.

3.1 Stratégies d'évolution

Les stratégies d'évolution (SE) sont historiquement le premier type d'AE à avoir été utilisé. Elles ont été introduites par Rechenberg en 1965 comme des heuristiques d'optimisation basée sur le principe d'adaptation et d'évolution. Les SE utilisent usuellement des vecteurs de nombres réels pour représenter l'espace des solutions. La mutation et la sélection représentent les opérateurs fondamentaux de reproduction et la recombinaison est moins commune. Le schéma d'exécution générale des SE est semblable au fonctionnement de base d'un AE.

3.1.1 Populations dans les SE

Les SE les plus simples sont les (1 + 1)-ES. Dans ce type de population on reproduit un seul enfant à partir d'un seul parent et on garde le meilleur entre eux. Les (p. + 1)- ES utilisent u parents pour produire un seul fils. Lorsque les p. parents produisent plusieurs fils (A fils), on parle des (p. + A)-ES. Généralement A est supérieur à p.. Après

sélection, seulement les u meilleurs individus parmi l'ensemble des parents et des fils seront conservés. Il est possible que les u individus soient choisis uniquement parmi les fils (les parents seront supprimés dans tous les cas), on parle alors des (u, A)-ES.

Dans les (u/p + A)-ES, un nouveau paramètre p est introduit désignant le nombre de parents qui participeront à la reproduction d'un seul individu. Dans le cas précédant, ce paramètre valait implicitement 1. De façon analogue, les (u/p + A)-ES sont des (u/p, A)-ES où les parents et les fils ont tous une chance de survivre dans la prochaine génération. Un dernier type est (u', A^'(u, A)ã)-ES. Ce sont des SE emboitées où A^' fils sont crées et isolés pour y générations d'une population de taille u'. Dans chaque des ygénération, A fils sont créés, desquels u des meilleurs individus passeront à la prochaine génération. Après y générations, les meilleurs individus de chacune des y précédentes générations seront sélectionnés. Le processus recommence avec A^' nouveaux individus.

3.1.2 Evolution différentielle

L'évolution différentielle est une méthode pour l'optimisation mathématique des fonctions multidimensionnelles. Elle est très utile lorsque les paramètres ne peuvent pas être codés comme des vecteurs réels. L'idée principale derrière l'évolution différentielle est l'utilisation d'un opérateur de recombinaison ternaire pour la création de nouvelles générations. Le nouvel individu est créé en ajoutant la différence entre deux individu à un troisième individu. Cette méthode a beaucoup évoluée depuis le model de base et plusieurs amélioration lui ont été proposées.

3.1.3 Sélection

Le but de l'opérateur de sélection est de guider la recherche vers des régions prometteuses. Contrairement aux autres opérateurs de variation (mutation et recombinaison), la sélection donne une direction à la recherche. Selon le type de population, l'ancienne génération peut entrer comme candidate à la sélection ou être éliminée dès le départ. La préservation de la génération précédente est recommandée lorsque l'espace de recherche est non borné [?]. Dans le cas où l'espace est borné et discret, et dans les problèmes d'optimisation notamment, la sélection sans préservation est généralement utilisée. Dans les deux cas, les SE utilisent la méthode sélection de seuil.

3.1.4 Mutation

Usuellement, la mutation est l'opérateur de sélection de base dans les SE. La structure de cet opérateur dépend du problème à résoudre. Bien qu'il n'existe aucune mé-

thodologie pour le définir, certaine règles ont été posées en se basant sur une analyse des implémentations réussies des SE et sur certaines considérations théoriques. Etant donnée une génération de départ, la première exigence est que tout autre état doit pouvoir être atteint après un nombre fini de mutation. La sélection exploite l'information de la fonction d'évaluation pour guider la recherche vers des espaces prometteurs, alors que la mutation explore cet espace de recherche. La mutation ne doit pas utiliser toute l'information de valuation mais seulement celle de la population parentale (initiale). La dernière règle exige que la langueur moyenne du pas de la mutation doive s'adapter à l'environnement global d'aptitude dans le but d'assurer l'évolution du système. C'est-à-dire que les variations doivent être produites de telle façon à ce qu'il y ait une possibilité d'amélioration.

Il reste à noter que, bien que ces règles donnent des grandes lignes pour orienter la définition des opérateurs de mutation, leur importance peut varier d'un problème à un autre. Comme les populations dans les SE sont souvent des vecteurs de réels, la mutation consiste à ajouter un bruit gaussien en évoluant au même temps son écart type.

3.1.5 Recombinaison

Au moment où la mutation agit sur un seul individu, la recombinaison partage l'information de plusieurs parents. Contrairement aux algorithmes génétiques où le croisement entre deux parents produit deux fils, l'opérateur de recombinaison standard dans les SE en produit un seul. Selon le type de la population, l'algorithme peut produire plus d'un individu par recombinaison.

Comme il a été noté au chapitre précédant, il existe deux types de recombinaison dans le cas des représentations réelles : le croisement direct et la recombinaison intermédiaire. Le croisement direct utilise un choix aléatoire en deux phases. Dans la première phase, un sous ensemble de la population, dont le cardinal est égal à la dimension des vecteurs, est choisi aléatoirement. Dans la seconde phase, et de façon aléatoire aussi, chaque vecteur i va contribuer d'un élément d'ordre i pour former la ième composante du fils.

Contrairement, la recombinaison intermédiaire utilise l'information contenue dans l'ensemble de tous les parents pour la création du fils. Cela se fait en calculant la moyenne des composantes du rang i de tous les parents pour former la i^ème composante du fils. Comme cette technique a été conçue pour des espaces de vecteurs réels,

son utilisation dans des espaces discrets doit inclure des procédures d'arrondissement probabilistes supplémentaires.

3.1.6 Auto adaptation

Après un certain nombre de générations, la stratégie devient très lente et son taux d'évolution devient très faible. Tout se déroule autour du paramètre de mutation p. p étant l'écart type de la loi selon laquelle ce paramètre évolue au cours des générations (le plus souvent c'est la loi gaussienne). En choisissant une valeur de p trop petite, on obtient une évolution très rapide, mais au pris d'une efficacité très faible. Dans le cas contraire, c'est-à-dire avec un p très grand, la mutation éloigne largement la recherche de la région à laquelle appartient l'optimum. Entre les deux extrémités il y a un intervalle de valeurs pour lesquels on obtient une performance presque optimale. Cet intervalle est appelé fenêtre d'évolution.

Une des méthodes les plus connues pour la régulation du paramètre p, dans le cas des (1 + 1)-SE, est la 1/5th rule. Elle consiste à maintenir une valeur de p constante durant un certain nombre de générations et estimer le taux de réussite des mutations avec une telle valeur. Si le taux de réussite est supérieur à 20%, on diminue la valeur de p, dans le cas contraire, on l'augmente.

Le problème dans la 1/5th rule est qu'elle ne peut être appliquée que pour les (1 + 1)-SE qui ne dépende que d'un seul paramètre (p). L'auto adaptation est une technique plus générale. L'idée de base est de lier l'évolution des paramètres de la stratégie à

l'évolution des individus. A mesure qu'on effectue des mutations et des recombinaisons, les individus évoluent et tendent vers la solution optimale. En incluant les paramètres de la stratégie dans ces évolutions, on espère qu'ils évoluent eux aussi de façon positive et qu'ils tendent vers les paramètres optimaux.

3.1.7 Mise en oeuvre dans les systèmes de parole

La reconnaissance dans les modèles Markoviens est basée sur le graphe de décodage. Comme une exploration complète serait irréalisable, plusieurs heuristiques réduisant l'espace de recherche ont été utilisée (généralement A*). Il est clair que les méthodes évolutionnaires sont plus avantageuses lorsqu'il s'agit de considérer de façon entière l'espace de recherche (recherche globale).

Les algorithmes évolutionnaires ont déjà été utilisés pour résoudre des problèmes se présentant sous forme de graphes (problème du voyageur de commerce). Le graphe sera codé sur une matrice carrée. Les lignes et les colonnes représentent toutes les deux l'ensemble des mots générés auparavant et les éléments de la matrice représenteront les probabilités de transition. La population est donc un ensemble de chemins dans ce graphe. Les chemins, et donc les groupes de mots, qui seront conservés lors de la phase de sélection sont ceux qui ont une plus grande probabilité de corresponde à l'ensemble des mots à identifier.

Ce principe peut être appliqué de façon similaire au problème de recalage temporel par DTW. Chaque couple d'ensembles de vecteurs source-test sera codé sur une matrice dont les éléments représentent les distances locales entre chaque couple de vecteurs. L'algorithme génère un ensemble aléatoire de chemins et le fait évoluer dans le but de parvenir au chemin optimal entre les débuts et les fins des deux ensembles.

Pour les modèles de classification, la pluparts des travaux pour leurs intégrer les algorithmes évolutionnaires ont concerné le cas non supervisé, dans lequel l'algorithme doit lui-même définir les classes. Toutefois, la classification phonétique est sans doute une classification supervisée. En effet, chaque unité phonétique correspond à une classe dont les paramètres sont déterminés à la phase d'apprentissage.

Chaque individu correspondra à une classification. Une façon simple pour coder les classifications est de considérer le continuum vocal entier comme un vecteur dont les éléments sont les segments correspondants aux unités phonétiques. L'ensemble des vecteurs acoustiques représentant ces unités sera donc considéré comme une composante élémentaire. De cette façon, chaque élément i d'un individu dans la population

va correspondre à la composante i du continuum vocal, et sa valeur à la classe phonétique à laquelle il appartient. A chaque itération, la fonction fitness évalue le degré de correspondance de l'ensemble de la classification au continuum vocal en se basant sur la qualité de classification individuelle de chaque unité phonétique. Avec cette évolution, l'algorithme évitera de procéder à une énumération complète des classifications possibles.

3.2 Programmation génétique

Le terme programmation génétique peut avoir deux différentes significations. En premier, il peut être utilisé pour regrouper tous les algorithmes évolutionnaires dont la population est sous forme d'une structure de données arborescente. Dans le deuxième cas, il est utilisé pour désigner tous les algorithmes évolutionnaires qui font évoluer des programmes, c'est-à-dire des algorithmes évolutionnaires dont la population est constituée de programmes informatiques.

La programmation génétique a été, à la base, conçue pour faire évoluer, de façon automatique, des programmes informatiques. En programmation génétique, certaines données en entrée et leurs résultats correspondants en sortie sont déjà connus. L'objectif est de trouver le meilleur algorithme, au sens de la performance, qui, étant donné un ensemble de situations de départ, fourni les résultats appropriés.

Compte tenu de l'apport de l'arborescence de la population qu'elle manipule, l'utilisation de la programmation génétique s'est vite propagée vers d'autres domaines tels que l'optimisation, l'Ingegneri électrique, le data mining, la médecine, la robotique, etc.

3.2.1 Population

La programmation génétique fait évoluer une population constituée d'un ensemble d'arbres. La génération de la population initiale est une étape décisive et compliquée. L'espace de recherche étant infini, il est très difficile de répartir plus ou moins équitablement la population initiale sur l'espace de recherche de telle sorte que cet espace soit au maximum parcouru. Pour générer cette population initiale, la première chose à faire est de limiter la profondeur de l'arbre, limitant ainsi l'espace de recherche et assurant une convergence de l'algorithme.

Nous devrions donc disposer d'un ensemble initial d'arbre dont la profondeur ne dépasse pas une certaine valeur maximal d. il existe trois façon pour créer cette population. La méthode full crée des arbres dont la profondeur a exactement la valeur d.

la méthode grow, elle aussi, crée des arbres dont la longueur ne dépasse pas d, mais qui peut être inférieur. Un choix aléatoire décide si un noeud qui vient d'être ajouter à l'arbre sera considéré comme une feuille ou pas. La méthode ramped half-and-half, quant à elle, est une méthode mixte. Pour chaque arbre à créer, un nombre r est aléatoirement choisi entre 2 et d. En suite, l'arbre sera créé soit avec la méthode full, soit avec la méthode half avec r comme profondeur maximale. Cette méthode est plus préférée comme elle produit des arbres de profondeurs différentes et assure ainsi une plus grande diversité.

3.2.2 Evaluation et sélection

Comme tout algorithme évolutionnaire, lorsqu'une solution est générée, sa qualité d'adaptation est évaluée. La façon de ce faire est très dépendante du problème à traiter par l'algorithme. Ainsi, pour un problème de classification, plus le nombre d'exemple bien classés par le programme généré est élevé, plus sa qualité sera grande. Pour un problème de regression, un écart entre les valeurs générées par le programme et les valeurs exemples est calculé; et plus cet écart est élevé, mois la qualité du programme sera bonne. Ainsi ces valeurs sont incomparables entre elle.

Il existe trois représentations possibles de la valeur d'évaluation pour remédier au problème d'incompatibilité. La Représentation standardisées considère que la meilleure

valeur possible est 0 et que toutes les valeurs sont positives. La représentation normalisée est similaire à la représentation précédente, mais les valeurs sont ici comprises entre 0 et 1. En fin, la représentation ajustée est similaire à la représentation normalisée, où le meilleur score possible est 1.

La programmation génétique utilise souvent la sélection par tournoi. Avec cette méthode, un ensemble d'individus est sélectionné au hasard pour participer à un tournoi de la meilleure aptitude. Normalement, la sélection passe sans remplacement, c'est-àdire que tous les individus du tournoi doivent être différents. En programmation génétique, deux tournois se déroulent en parallèle pour produire les deux parents d'un croisement. Avant que les vainqueurs subissent la variation, une copie de chacun d'eux est conservée pour remplacer le plus mauvais perdant du tournoi. L'avantage des tournois est qu'ils peuvent être lancés indépendamment les uns des autres, et n'exigent pas d'informations globales sur la population.

3.2.3 Reproduction

Les individus peuvent subir de petites variations durant le processus de reproduction de l'algorithme évolutionnaire. Une telle mutation est habituellement définie comme la sélection aléatoire d'un noeud, la suppression de ce noeud ainsi que ses descendants, et finalement leur remplacement par un autre noeud. De cette idée, trois opérateurs peuvent être dérivés : le remplacement aléatoire de certains noeuds, l'insertion de nouveaux noeuds et la suppression de certains noeuds.

L'opérateur de recombinaison par défaut est l'échange de sous-arbres. Un sousarbre est aléatoirement sélectionné de chacun des deux parents, il est en suite enlevé et transféré à l'autre partenaire. Si des restrictions sont imposées sur la profondeur maxi-male de l'arbre, les opérateurs de recombinaison doivent les respecter et ne pas les dépasser. La recombinaison part de l'idée que les caractéristiques des bons individus vont se propager dans la population, et en s'intégrant dans de d'autres bons individus, ils amélioreront leurs qualité. Cependant, la recombinaison peut avoir des effets désastreux quant à leurs aptitudes.

La permutation est un opérateur de reproduction unaire. Un noeud est sélectionné au hasard et déplacé de façon aléatoire dans l'arbre (généralement en gardant le même

FIGURE 3.4 - Différentes possibilités de Mutation
FIGURE 3.5 - Recombinaison par échange de sous-arbres

parent), pour produire l'arbre fils. Le but principal est de réarranger les noeuds des bons individus pour les rendre moins fragiles à d'autres opérateurs tels que la recombinaison.

L'idée de l'encapsulation est de rechercher des sous-arbres potentiellement utiles et de les agréger en un seul noeud. Cela permettra d'assurer leur regroupement et d'empêcher d'autres opérateurs de reproduction de les séparer. L'encapsulation permet en outre de faire propager le sous-arbre potentiel de façon entière dans le reste de la population.

L'emballage consiste à sélectionner au début un noeud it de façon aléatoire dont au moins un fils est libre, et de créer par la suite un autre noeud iii, en dehors de l'arbre. On déplace maintenant le noeud it (et éventuellement tous ses descendants) dans cet espace vide. En fin, on insert le noeud iii dans la position qu'occupait le noeud it précédemment. Le but de cette méthode est d'autoriser des modifications des noeuds qui ont une grande probabilité d'être utiles.

Le lifting est l'opérateur inverse de l'emballage. Il consiste à faire monter un noeud dans l'arbre. On commence par la sélection arbitraire d'un noeud de l'arbre. Ce noeud

Dans la plupart des opérations de reproduction, aussi bien dans la mutation que dans la recombinaison, certains noeuds dans l'arbre doivent être choisis. Une bonne façon pour ce faire est d'attribuer une probabilité de sélection équivalente à tous les noeuds comme est le cas de la méthode de sélection uniforme. Par conséquent, le poids de chaque noeud sera défini comme le nombre des sous-arbres dont il est la racine (le nombre de ses descendants). De cette façon, la probabilité qu'un noeud soit choisi est l'inverse de son poids.

3.2.4 Programmation génétique linéaire

La programmation génétique linéaire (ou GPL pou Linear Genetic Programming) a été créée, comme son origine, pour le développement automatique des programmes. Comme la structure d'arbre n'est pas la seule façon de représenter un programme, et comme tous les problèmes ne peuvent pas être modélisés sous forme d'arbres, l'idée de la programmation génétique linéaire est de représenter les individus sous forme de séquences linéaires de vecteurs réels. La différence entre cette représentation et celle des stratégies d'évolution et certaines version d'algorithmes génétiques, est que les individus ne sont pas des vecteurs de réels, mais plutôt des séries de vecteurs de réels, c'est-à-dire des vecteurs de vecteurs.

L'avantage de la programmation génétique linéaire est que grâce à la structure linéaire de ses individus, son champ d'application peut s'étendre à plusieurs autres problèmes pour lesquels, une modélisation arborescente est impossible ou inadéquate, et ce, en profitant de au même temps de la richesse de la programmation génétique en opérateurs de reproduction. Cependant, l'application de certains opérateurs devient inefficace ou voir impossible, vu que leur puissance réside essentiellement dans le fait

qu'ils sont dédiés à être appliqués sur des arbres. Pour l'évolution des programmes informatiques, le problème devient beaucoup plus compliqué. En effet, le contrôle de flux du programme ne sera plus implicite comme est le cas des arbres, mais il sera assuré par un mécanisme de sauts. L'ajout ou la suppression d'un ou de plusieurs éléments modifiera complètement la sémantique du programme.

Pour ces raisons, un nouvel opérateur été défini. En biologie, Des protéines homologues sont des protéines dont les gènes qui les codent ont une origine commune. On reconnaît deux protéines homologues car elles ont des structures spatiales proches et des séquences en acides aminés qui présentent des similarités. Les fonctions de ces protéines peuvent être plus ou moins semblables. En programmation génétique linéaire avec le croisement habituel, il est difficile à l'évolution d'établir une structure claire entre les positions spatiales et les fonctionnalités. Le croisement collant ressemble à l'homologie en n'autorisant l'échange que des éléments se situant dans les mêmes positions spatiales. Il choisit en premier une séquence d'éléments puis l'échange avec la séquence qui se trouve à exactement la même position dans le deuxième parent.

3.2.5 Approches basées sur les graphes

Plutôt que d'utiliser des structures arborescentes ou linéaires, ces approches utilisent une structure de graphes. Il est clair que la structure de graphe est plus générale, dans la mesure où toutes les structures précédentes peuvent être modélisées sous forme de graphes. En outre, la représentation matricielle que permettent les graphes peut s'avérer quelques fois très avantageuse. L'utilisation des graphes prend tout son intérêt lorsqu'il s'agit d'optimisation. En effet, la plupart des problèmes d'optimisation ont été modélisés sous forme de graphes. L'avantage de cette approche est que tous les opérateurs de reproduction en programmation génétique sont toujours valables. Il reste seulement à considérer ou pas les arcs perdus lors des transformations.

3.2.6 Mise en oeuvre dans les systèmes de parole

Pour appliquer la programmation génétique aux modèles markoviens, deux solutions sont envisageables. La première consiste à transformer le graphe de décodage en un arbre de décodage. Par conséquent, le modèle ne contiendra plus de cycle, et les sommets aux bouts des arcs supprimés seront dupliqueés pour préserver les liens. Une fois l'arbre conçu, ont construit à partir de lui, et de façon aléatoire, un ensemble initial de sous-arbres représentant chacun un chemin. Cet ensemble initial sera soumis aux opérateurs de variation et de sélection jusqu'à aboutir à un chemin satisfaisant au sens de l'optimalité.

La deuxième solution est d'utiliser le modèle linéaire de la programmation génétique. Comme a été le cas dans les stratégies d'évolution, on considère la représentation matricielle du graphe de décodage, et chaque vecteur va donc représenter un chemin. Cependant, les opérateurs de variation de la programmation génétique classique ne conviennent pas tous au modèle linéaire et leur efficacité ne peut être garantie. Il est donc préférable de conserver la première solution.

Il en sera de même pour les modèles de classification et les modèles à comparaison dynamique, puisqu'une représentation arborescente n'aura aucun intérêt. Toutefois, la programmation génétique peut servir à améliorer la qualité des classifiers, notamment si l'on utilise des arbres de décision. La programmation génétique peut contribuer à améliorer la classification. On commence par un ensemble aléatoire d'arbre de décision, qu'on fait évoluer au fur et à mesure des générations. L'évaluation peut considérer soit la qualité de représentation des unités phonétique par les règles de décision, soit le degré de correspondance des unités à leur classes. Cette idée peut être généralisée de la même façon aux traitement liguistiques basés sur des arbres de décision.

3.3 Conclusion

Nous avons effectué dans ce chapitre une étude approfondie des les stratégies d'évolution et de la programmation génétique. Nous avons traité des différentes populations, des stratégies de sélection et des différents opérateurs de variation ainsi que leurs caractéristiques. Certains aspects relatifs aux différents composants ont aussi été présentés. Par la suite, nous avons proposé, pour chacune des deux méthodes, une mise en oeuvre dans les différents modèles de reconnaissance évoqués au premier chapitre.

Le dernier chapitre sera consacré à une analyse comparative, dans laquelle nous discuterons des similarités et différences, des avantages et inconvénients et des puissances et faiblesses des deux approches.

Au chapitre précédent, nous avons eu une vue assez large des stratégies d'évolution et de la programmation génétique. Nous établissons ici une analyse comparative quant à leurs éléments essentiels, leurs objectifs et leurs efficacités dans les systèmes de parole. L'analyse sera focalisée sur les éléments suivants l'objectif de conception original, la spécificité, le compromis entre l'exploitation et l'exploration, la représentation des individus et les opérateurs de variation.

4.1 Objectifs

Contrairement à toutes les autres approches évolutives qui se sont présentées comme des techniques d'intelligence artificielle, les stratégies d'évolution ont été conçues dès le départ pour résoudre des problèmes d'optimisation. La structure des individus en tant que vecteurs de réels, facilite le codage des solutions, simplifie leur adaptation et élargie le domaine de couverture. Ainsi, leur principe de développement n'est-il pas adapté à des problèmes reposant sur l'intelligence artificielle tels que l'apprentissage automatique. Les problèmes qui manipulent des données variables ont souvent besoin d'un mécanisme d'adaptation qui est assuré par une fonction d'apprentissage. Les stratégies d'évolution ont été conçues pour travailler sur des données exactes et ne peuvent assurer un travail d'apprentissage, à moins qu'elles soient utilisées de façon secondaire comme outils d'amélioration dans d'autres approches adaptatives telles que les réseaux de neurones.

La programmation génétique dans sa version de base, a suivi un nouveau paradigme de résolution. Au lieu de faire évoluer des populations de solutions, elle fait évoluer des programmes qui mènent à ces solutions, en se basant sur des résultats déjà obtenus avec des réalisations manuelles. La programmation génétique a donc été développée dans cette optique conception automatique de programmes. Contrairement aux stra-

tégies d'évolution, la programmation génétique est très bien adaptée aux problèmes ayant besoin d'une phase d'apprentissage. Au cours des générations, le programme apprend à concevoir le chemin par lequel les données en entrée parviennent aux données, qui auraient déjà été calculées, en sortie.

Pour ce faire, la programmation génétique doit adopter un modèle de population qui conviendra le mieux à la nature de ses individus : une structure arborescente. Il est naturel que ce modèle ne pourra pas représenter tous les problèmes, et c'est ici que se situe un des défauts majeurs de la programmation génétique. En effet, l'élaboration d'un modèle arborescent à un problème dont la nature ne l'est pas n'est pas toujours une tâche facile, et ce n'est pas toujours possible.

On constate clairement que les objectifs de base de développement de chacune des deux méthodes ont une influence capitale sur leurs orientations structurelles, et par conséquent, sur la nature des problèmes auxquels elles peuvent s'adapter, et aussi au degré de facilité de cette adaptation.

Tous les systèmes de reconnaissance débutent par une phase d'apprentissage, en utilisant généralement des méthodes statistiques ou des réseaux de neurones, mais aussi des arbres de décision. Si le modèle utilisé en apprentissage est le même que celui utilisé en reconnaissance, comme est le cas des modèles markoviens, il convient d'utiliser la programmation génétique pour améliorer l'apprentissage, et donc pour pouvoir mieux généraliser les connaissances acquises lors de cette phase. Dans le cas contraire, c'est-à-dire si les modèles ne sont pas les mêmes, la programmation génétique n'aura plus aucune utilité. La phase de reconnaissance doit, dans ce cas, faire appel à des méthodes d'approximation à chaque fois que deux couples d'unités doivent être comparées. A cette étape, Les stratégies d'évolution peuvent être utilisées soit pour améliorer la précision des comparaisons, soit pour réduire leurs nombre.

4.2 Spécificité

Tous les algorithmes évolutionnaires sont des méthodes générales, c'est-à-dire qu'elles n'ont pas besoin d'avoir, a priori, des connaissances sur le problème. Cette faculté de généralisation n'est pas toujours avantageuse. En effet, toute la puissance des méthodes spécifiques réside dans le fait qu'elles utilisent des connaissances propres au problème.

Selon certains, des mécanismes généraux suffisamment puissant ont eux même la faculté de mener efficacement la recherche sans disposer d'information spécifiques du

problème (contexte de boite noire). C'est notamment le point de vue classique sur les algorithmes génétiques. Malheureusement, de même qu'il ne peut pas exister de stratégie avantageuse dans un jeu de hasard, il existe également des limitations théoriques fondamentales qui ruinent les espoirs d'une méthode aveugle dans le cas le plus général[91]. En fait, le théorème "No Free Lunch" montre que pour les problèmes de type boite noire, toutes les méthodes sont équivalentes et font aussi bien, ou plutôt aussi mal, que l'énumération aléatoire. Autrement dit, il n'existe pas de méthode surpassant les autres sur tous les problèmes.

Selon un point de vue opposé, la puissance d'une méthode générale est d'abord liée à son aptitude à intégrer des connaissances spécifiques du problème. La connaissance du problème la plus fondamentale réside dans le codage du problème et dans le choix de la population. L'importance du codage est cruciale. En effet, dans plusieurs problèmes de référence (comme le problème du voyageur de commerce) où différents codages ont été proposés, les résultats étaient très variés. Quoiqu'il n'existe pas de codage universellement efficace, un bon codage doit permettre de restreindre l'espace de recherche et d'intégrer un maximum de connaissances du problème.[91]

Une autre voix pour incorporer des connaissances supplémentaires, afin de tenter d'améliorer l'efficacité, est de les intégrer dans les opérateurs. Plus les opérateurs d'une méthode utilisent des connaissances spécifiques, plus cette méthode dispose de moyens potentiels pour conduire efficacement la recherche. En contrepartie, l'intégration de ces connaissances spécifiques (en supposant qu'elles soient disponibles), nécessite un effort pour spécialiser ou adapter la méthode. En général, une méthode offrant des possibilités d'intégrer des connaissances du problème a plus de chance de produire de bons résultats, mais demande un effort d'adaptation ou de spécialisation. Au contraire une méthode très générale qui prétend n'intégrer aucune connaissance propre ne peut pas être compétitive.[148]

La capacité de spécialisation que peut offrir une méthode d'adaptation doit se manifester comme une technique d'adaptation, et non pas comme une configuration prévue dès le départ pour un type de problème particulier. En effet, plus la méthode est spécifique, plus son champ d'application se restreint. Ces deux mesures sont plutôt contradictoires. Si la méthode est conçue pour un type particulier de problèmes, sa conception réalisée en conséquence et son efficacité seront meilleures qu'une méthode plus générale. Seulement, même si l'on peut appliquer la méthode à d'autres problèmes qui ne faisaient pas l'objet de sa conception au départ, les résultats ne seront pas aussi bons que ceux ayant été obtenus pour des problèmes de sa spécialité.

Les stratégies d'évolution ont adoptés un modèle très général. Avec la représentation réelle des individus, elles peuvent traiter n'importe quel problème d'optimisation. On ne peut pas dire que le fait qu'elles soient conçues pour des problèmes d'optimisation est un signe de spécification, car le domaine d'optimisation est loin d'être une limitation, sans compter le fait que pratiquement tous les domaines s'y réfèrent. Il se peut cependant que la représentation réelle soit un obstacle lors de la résolution de certains problèmes dont la nature est aussi simple pour que des nombres réels soient nécessaires.

Une des façons les plus importantes pour l'adaptation dans les stratégies d'évolution est la fonction d'auto-adaptation. En fait, nous verrons par la suite que l'apport de cette fonction ne se résume pas à cette adaptation. En évoluant les paramètres de variation, la stratégie permet de suivre en permanence l'évolution de la population et d'adapter la variation en conséquence; et comme cette population est sensée aller de mieux en mieux, la qualité des connaissances incorporées devrait être de plus en plus bonne. Par ailleurs le fait que l'adaptation ne soit pas constante est un facteur très important. En effet, Dans la plupart des méthodes, l'utilisation des informations spécifiques se fait dans une phase d'initialisation en adaptant la représentation de la population et les fragments de croisement au problème considéré, et ces paramètres restent constants durant toute le période d'exécution. Par contre, dans l'auto-adaptation, ces paramètres évoluent avec l'évolution des individus. Il se peut que les connaissances incorporées au lancement de l'algorithme ne soient plus valides après un certains nombre de génération.

En ce qui concerne la programmation génétique, il est un peut plus difficile de juger de sa spécificité. Il faut prendre en considération la différence de ses définitions, et aussi le niveau de spécification considérée. Si l'on tient au premier sens, la programmation génétique ne sera rien qu'une stratégie d'évolution avec une structure de population arborescente, avec, bien entendu, un ensemble d'opérateur différent, mais ceci n'a pas d'influence. Le seul effet que peut avoir cette structure est qu'elle limite le champ d'application aux problèmes pouvant être modélisés sous forme d'arbres, et même pour ceux-ci, un travail d'adaptation important peut devenir dans certains cas nécessaire.

Si l'on considère maintenant la deuxième définition, on peut voir les choses de deux angles différents. D'un premier angle, la programmation génétique peut être vue comme une méthode très spécifique, étant donné qu'elle ne peut optimiser que des programmes informatiques. Plusieurs opérateurs de variation relatifs à la programmation génétique n'ont un intérêt que si la population considérée est un ensemble de programmes. Dans le cas de l'encapsulation par exemple, si le groupe de noeuds ne correspond pas à une

fonction informatique (dans son sens le plus large), l'opérateur n'aura pas d'intérêt car seules les fonctions peuvent donner un sens à ce regroupement. Dans les autres cas, l'encapsulation ne fera que pénaliser la diversité de la population.

D'un deuxième angle, le fait d'optimiser un programme qui résoud un problème, est plus général qu'optimiser la solution du problème lui-même. Cette idée a un intérêt remarquable de son caractère généraliste. Si un programme donné est optimal, la résolution du problème associé n'aura plus besoin d'optimisation. Il suffit juste d'avoir un bon programme pour ne se soucier plus de la qualité de la solution.

Comme il n'existe aucun modèle évolutionnaire directe pour la reconnaissance, on a toujours recours à des modèles d'optimisation pour l'estimation des ressemblances. Ces modèles étant toujours précédés d'une phase d'apprentissage. Le meilleur compromis est d'utiliser une structure arborescente pour améliorer l'apprentissage, et de laisser les stratégies d'évolution s'occuper de la reconnaissance. Notons en fin qu'une fois que l'opération d'apprentissage a bien été effectuée, et qu'une bonne paramétrisation a été estimée, l'optimisation des correspondances phonétiques ne sera qu'un apport supplémentaire.

4.3 Exploitation et exploration

Les notions d'exploitation et d'exploration se sont apparues avec l'arrivée des algorithmes génétiques. L'exploitation (ou intensification) insiste sur la capacité d'examiner en profondeur des zones de recherche particulières, ou plus exactement utiliser des individus pertinents pour en produire d'autres, c'est-à-dire les exploiter. L'exploration, par contre, met en avant la capacité de découvrir des zones de recherche prometteuses (diversification). Il est donc très important d'examiner les algorithmes évolutionnaires en fonction de ces deux notions.

Bien que ces deux notions soient tellement complémentaires, il est quand même difficile de trouver un compromis ente elles. Mais il est remarquable que la préoccupation majeure des algorithmes évolutionnaires est la conservation de la diversité de la population. Ceci est du au fait que le rôle de l'exploration est plus important que celui de l'exploitation, dans la mesure où le premier est fondamental est le deuxième est moins essentiel. En effet, une bonne exploration de l'espace de recherche va permettre, tôt ou tard, de tomber sur une solution potentielle. Il est vrai qu'une exploration aveugle peut passer juste à coter d'une bonne solution sans qu'elle s'en rende compte, mais les bonnes solutions ont tendance à se regrouper. C'est à ce niveau là qu'intervient l'exploitation pour concentrer la recherche autour de ces solutions potentielles. Tout cela

explique comment le rôle de la fonction d'exploration est fondamental. Il ne sert à rien de penser à exploiter des bons individus si l'on ne peut même pas tomber sur eux. De plus, et comme il a été discuté au chapitre 2, l'abus de l'exploitation va mettre la population dans un état très homogène et l'empêcher d'évoluer.

C'est pour cette raison que les méthodes évolutionnaire ont souvent recouert au scaling et au sharing pour empêcher le regroupement prématuré des bons individus. On ajoute à tous ça le fait que la notion de "bon individu" est très relative. En effet, si un individu est considéré comme étant bon dans sa population en cours, ceci ne signifie en aucun cas qu'il est le meilleur. Ce qui nous mène au problème classique des heuristiques d'optimisation : le piège de l'optimum local.

Dans les stratégies d'évolution, l'exploitation est représentée principalement par l'opérateur de recombinaison, et l'exploration par l'opérateur de mutation. Les stratégies d'évolution se basent principalement sur l'exploitation, vu que la mutation est l'opérateur de reproduction fondamental. La mutation, en ajoutant des bruits aléatoires, permet une diversification aléatoire aussi de la population. De sa part la recombinaison permet d'orienter la recherche vers des zones prometteuses. De cette façon les stratégies d'évolution constituent un bon exemple de méthodes équilibrant entre l'exploitation et l'exploration.

Il est aussi important de noter que le maintient des fonctions d'auto-adaptation a un impact sur la diversification. Il peut être considéré comme un outil supplémentaire d'exploitation, puisqu'il permet d'utiliser la qualité globale de la population pour diriger la recherche.

Les opérateurs de création et de duplication, quoiqu'ils sont beaucoup moins fréquents, peuvent contribuer à leur tours au maintient de la stabilité globale de la population. Bien que la création ne soit souvent utilisée que lors de la génération de la population initiale, la méthode peut lui faire appel comme outil secondaire de diversification. En associant la recombinaison à la mutation, la reproduction sera toujours basée sur des bons individus. La création permet d'introduire des éléments complètement nouveaux, et de rediriger certaines parties de la recherche vers des régions totalement nouvelles. La duplication quant à elle, permet de garder une trace de quelques individus potentiels, pour garantir leur présence dans les prochaines générations. La duplication ne peut pas avoir d'effets destructifs : si les autres opérateurs produisent des individus moins meilleurs, la duplication portera un grand intérêt en étant la seule à produire quelque chose de bon. Dans le cas contraire, c'est-à-dire si les éléments dupliqués sont mauvais, la sélection s'en occupera.

Pour la programmation génétique, la recherche est plutôt orientée vers l'exploitation. Malgré que le jeu d'opérateur soit plus important ici que tous les autres algorithmes, la mutation est le seul qui offre des possibilités d'exploration. Cette orientation s'explique par le fait que la programmation génétique a été conçue pour le développement automatique de programmes, et montre encore une fois comment l'objectif initial d'une méthode influence son orientation. En effet, dans le cas d'une population de programmes, la notion de fonction peut s'agir d'une seule instruction comme de plusieurs. Cette idée de groupe potentiel d'individus n'a de sens que dans les programmes informatiques. Lorsque la recherche tombe sur fonction potentielle regroupant plusieurs instructions, il est important de la faire propager dans toute la population de façon entière. Dans le cas contraire, il y a un grand risque que ce groupe soit découpé et perde toute sont efficacité. La programmation génétique tient donc à profiter de façon maximale des capacités potentielles des sous-programmes d'individus qu'elle manipule avant de chercher à produire de nouveaux individus. Il convient aussi de prendre en compte que la structure arborescente de ses individus offre plus de possibilités de variation que les vecteurs, notamment dans le cas des programmes informatiques. Il suffi en effet d'une simple permutation entre deux arbres pour pouvoir changer radicalement la sémantique du programme, et donc de donner naissance à un individu tout à fait différent.

Pour conclure, nous dirons que le choix de la stratégie de recherche a été effectué dans les deux méthode de telle façon à ce qu'il soit le mieux convenable à la nature des problèmes auxquels chacune d'elles a été dédiée. Les stratégies d'évolution ont suivit une stratégie favorisant l'exploration pour échapper au piège de l'optimum local des problèmes d'optimisation. De son coté, la programmation génétique a pris en considération la nature générale de ses individus, et adopté une stratégie de recherche basée sur l'exploitation. Il ne reste donc à dire que l'usage approprié de l'une des deux méthodes impliquerait un choix judicieux de la stratégie de recherche.

4.4 Représentation des individus

Le choix du codage des individus est une étape décisive : tous les choix de conception qui suivent en dépendront, notamment en ce ce qui concerne le choix des opérateurs et de leurs priorités. La représentation doit aussi être choisie de façon à ce qu'elle convient le mieux à la nature des problèmes qu'elle est supposée traiter, notamment si la méthode est spécifique. Si la méthode est par contre générale, la représentation doit être facile à adapter aux différents problèmes couverts par la méthode.

Le codage réel dans les stratégies d'évolution a été choisi à la fois pour faciliter l'adaptation et augmenter la performance des opérateurs de reproduction. En effet, les représentations binaires ne sont pas toujours évidentes et réalisables. De plus, plus la valeur des individus est grande, moins la valeur des bits sera importante. Ceci a une influence négative sur la diversification. Si les chaînes binaires sont très longues, le changement d'un ou deux bits par croisement ou mutation (ce qui est généralement le cas dans les algorithmes génétiques) n'entrainera pas déformations importantes, et risque de saturer l'évolution du système. Par contre, un codage réel est toujours efficace de ce point de vue, étant donné que les opérateurs de reproduction qui lui sont associés sont toujours réalisés à base des opérations arithmétiques standards, qui ne dépendent pas de la valeur de l'individu. Et même si les individus sont considérés comme des suites de caractères indépendants, ces derniers auront toujours une valeur plus significative.

Les techniques d'auto-adaptation dans les stratégies d'évolutions reposent sur l'écart type de la distribution gaussienne. Celui-ci repose de sa part sur l'évolution des individus. La réalisation de cette chaîne efficace de dépendances n'aurait pas pu être possible si l'on ne disposait pas d'un codage réel. L'inconvénient de ces vecteurs est que la taille qu'ils occupent en mémoire ne dépend pas de leurs valeurs, et les petits nombres occupent autant de taille que les grands. Mais avec l'évolution technologique actuelle, les problèmes de mémoire ne sont plus un sujet de discussion. Néanmoins, la représentation binaire de certains problèmes est par fois plus naturelle. De plus, les opérations primaires sur les binaires (arithmétiques, logiques ou de décalage) sont plus rapides de plusieurs cycles que les opérations correspondantes aux réels.

Le modèle de population, basé sur les arbres, de la programmation génétique est d'une nature très spécifique. Ceci implique des efforts d'adaptation, si cette dernière est déjà possible. En effet, tous les problèmes ne peuvent pas se modéliser sous forme d'arbres. Et même si cela est possible, le modèle résultant n'est pas nécessairement efficace. Cependant, pour les problèmes dont l'arborescence est une nature, cette représentation est extrêmement efficace et aucun autre modèle ne peut la conquérir.

la représentation des programmes, qui fait l'objet principal de la programmation génétique, est un modèle très naturel. Son efficacité se situe essentiellement dans le fait que le contrôle de flux du programme est implicite et qu'il n'est plus nécessaire de le définir. En choisissant l'ordre d'évaluation de l'arbre (préfixée, infixée ou post fixée), on défini automatiquement l'ordre du déroulement du programme en parcourant l'arbre dans l'un de ces sens.

Les arbres ont aussi permis de définir un jeu d'opérateurs de variation très riche, et des nouvelles notions comme est le cas dans l'encapsulation. Il ne s'agit pas uniquement de la convenabilité de ces opérateurs aux programmes informatiques, mais à la structure elle-même, car même pour les autres modèles de la programmation génétique, ces opérateurs ne sont pas tous applicables et efficaces. Ces autres modèles sont encore au stade d'expérimentation, et l'on ne dispose pas de mesures sur leurs efficacités. En résumé, on peut constater que les choix des codages ont suivit les objectifs originaux des deux méthodes. Le codage réel reste toutefois plus performant si l'on prenne en considération toutes les mesures d'efficacité.

4.5 Opérateurs de reproduction

Au fil des sections précédentes, l'analyse des opérateurs de reproduction a pratiquement été effectuée. Ceci est tout à fait normal car les éléments sont fortement liées et interdépendants. Nous allons quand même donner un petit aperçu.

De façon générale, tous les opérateurs dépendent de leurs opérandes, et les opérateurs algorithmes évolutionnaires n'en font pas exception. Cette idée est beaucoup plus claire dans le cas des arbres où l'introduction d'une nouvelle structure de codage a mis en jour toute une série de nouveaux opérateurs. Même pour les opérateurs communs entre les différentes méthodes, leur efficacité n'est pas toujours la même. Ceci a laissé les algorithmes favoriser certains opérateurs par rapport autres. Le croisement a été choisi pour les binaires et la mutation a été choisie pour les réels. Pour les arbres de la programmation génétique, les choses sont un peut différentes du fait de la spécificité des opérateurs. Entre un problème et un autre, la priorité d'un opérateur peut augmenter ou diminuer, il se peut même que l'opérateur ne soit complètement pas utilisé. Enfin, la spécificité des opérateurs influence directement celle des méthodes associées. Plus l'opérateur est général, plus la gamme des problèmes auxquels il peut être appliqué sera large, et plus la méthode sera donc générale.

4.6 Récapitulatif

Au cours de cette analyse, l'idée qui ne cessait d'émerger était le fait que les éléments d'une méthode dépendent fortement de l'objectif de base de la conception de la méthode. Les stratégies d'évolution ont été créées comme des méthodes d'optimisation. Compte tenu de la diversité du domaine de l'optimisation, le modèle des stratégies d'évolution a été choisi de telle façon à couvrir un maximum de problèmes. La stratégie de recherche a été orientée vers la diversification en vu de surpasser le problème de l'optimum local. Et pour mieux convenir à la nature de ces problèmes, elles ont adopté une représentation réelle pour permettre une meilleure adaptation et une possibilité de contrôler les paramètres de recherche. De même la même façon, la conception de la programmation génétique pour le développement automatique des programmes explique le choix d'une structure arborescente pour représenter ses individus, l'orientation vers l'exploitation et la spécificité de ses opérateurs. Le tableau de la figure représente un résumé récapitulatif de cette analyse.

Les problèmes de reconnaissance automatique de la parole se présentent généralement sous forme de deux sous problèmes : un sous problème d'apprentissage et un autre de reconnaissance. Ce qui parait le plus convenable est de choisir un modèle arborescent pour améliorer l'apprentissage, et d'utiliser les stratégies d'évolution pour optimiser l'estimation des correspondances.

4.7 Conclusion

Dans ce dernier chapitre, nous avons élaboré une analyse comparative des stratégies d'évolution et de la programmation génétique en se basant sur la représentation donnée dans les chapitres 2 et 3. Nous avons analysé l'objectif, la spécificité, la stratégie de recherche, la représentation des individus et les opérateurs de chaque méthode. Nous avons à la fin réalisé que tout était dépendant de l'objectif de base de conception.

Dans le cadre des systèmes de parole, étant donné qu'il n'existe pas de modèle évolutionnaire pour eux, la programmation génétique peut servir principalement d'outil d'apprentissage et ptionnelement dans les traitements linguistiques, et les stratégies d'évolution peuvent permettre d'optimiser la reconnaissance.

Conclusion et Perspectives

Le défi le plus important que doivent lever les systèmes de parole est la robustesse à la variabilité de la parole. Cette robustesse est principalement à l'origine de la complexité de ces systèmes. Nous avons essayé dans ce travail de découvrir les possibilités de remédier à ce problème de complexité des systèmes de la parole en utilisant des algorithmes évolutionnaires.

Au cours de cette étude, nous avons, d'une part, réalisé que les problèmes rencontrés dans les systèmes de parole ne se restreignent pas à la phase de reconnaissance, mais ils s'étendent à tout le processus de traitement. Ceci nous a poussé à généraliser l'étude de mise en oeuvre des algorithmes évolutionnaires à toutes les étapes de traitement. D'autre part nous avons constaté que le choix d'une méthode évolutionnaire doit se focaliser principalement sur la nature des problèmes auxquelles elle a initialement été conçu et celle du problème à traiter. Tous les autres paramètres peuvent être adaptés d'une façon ou d'une autre au problème considéré. En fait, un choix judicieux effectué suivant cette optique ne laisse généralement pas beaucoup de paramètres à adapter.

A l'issue de cette analyse, la conclusion à laquelle nous avons abouti est un compromis entre l'usage des deux méthodes. Les stratégies d'évolution, avec leur nature très adaptée aux problèmes d'optimisation, peuvent améliorer les performances des opérations de reconnaissance. Que ce soit dans les modèles markoviens, de classification ou à recalage temporel, les stratégies d'évolution peuvent précieusement aider à estimer les correspondances phonétiques. De sa part, la programmation génétique, conçu à la base pour le développement automatique des programmes, est parfaitement adaptée à l'apprentissage automatique et aux traitements linguistiques, notamment s'ils sont basés sur des arbres de décision, à condition que les modèles utilisés dans les deux phases soient les mêmes.

L'analyse précédente a été réalisée suivant un raisonnement basé sur des remarques et des résultats théoriques. Bien que cette analyse fourni une large vision des possibilités d'application des algorithmes évolutionnaires, et des grandes lignes pour orienter le choix d'une méthode en dépit d'une autre, ses résultats ne peuvent pas constituer des mesures définitives. En effet, ce qui peut paraitre bon en théorie peut ne pas l'être en pratique. La complexité des systèmes de parole implique la présence de plusieurs paramètres qui peuvent influencer la qualité d'une méthode. Cette analyse doit impérativement être complétée par des tests pratiques faisant intervenir des paramètres différents du coté des systèmes de reconnaissances et des algorithmes évolutionnaires. De tels tests nécessiteraient un grand travail de recueil d'information et d'adaptation de paramètres, car les quelques environnements qui réunissent les outils de traitement de la parole et ceux des algorithmes évolutionnaires ne travaillent que sur des algorithmes génétiques.

Bibliographie

(ITS) Swiss Federal Institute of Technology Lausanne (EPFL), National Center of Competence in Research (NCCR)"Interactive Multimodal Information Management (IM)2" / IDIAP Research Institute, Martigny.

- IRISA/INRIA Rennes / ENST Paris - Dpt. INFRES / LIUM - Université du Maine, XXIVèmes Journées d'Étude sur la Parole - Nancy, 2002.

Nationale d'Ingénieurs de Tunis, 3rd International Conference : Sciences of Electronic, Technologies of Information and Telecommunications March 27-31, 2005 - TUNISIA.

Résumé: La nature variable du signal de la parole fait que son traitement, dans ses différents niveaux, soit une tâche très difficile. Etant donné qu'il n'existe pas de méthodes exactes pour traiter cette variabilité, les systèmes de parole ont toujours recours à des méthodes d'approximation. Dans ce travail, nous avons étudié les possibilités d'application d'une famille de ces méthodes d'approximation connus sous le nom d'Algorithmes évolutionnaires. Ce sont des méthodes qui reposent sur le principe d'évolution et de sélection naturelle. Nous avons réalisé une étude comparative entre deux méthodes particulières de cette famille : les stratégies d'évolution et la programmation génétique après avoir proposé des possibilités de mise en oeuvre dans les systèmes de parole pour chacune d'elle. A l'issue de cette étude, nous avons constaté que la puissance de chaque méthode se situe dans la catégorie des problèmes à laquelle elle a initialement été conçue. Les stratégies d'évolution offrent des possibilités importantes en optimisation, et peut être appliquée efficacement dans la phase de reconnaissance. La programmation génétique quant à elle, peut améliorer la qualité d'apprentissage et des traitements linguistique, vue ses performances en matière de développement automatique des programmes.

Mots clés: Systèmes de parole, Algorithmes évolutionnaires, Stratégies d'évolution, Programmation génétique.

Abstract: The variable nature of the speech signal makes that its treatment, in its different levels, is a very difficult task. Since exact methods don't exist to treat this variability, the speech systems always have resort to approximation methods. In this work, we studied the possibilities of application of a family of these approximation methods known as evolutionary algorithms. These are the methods that rest on the principle of natural evolution and selection. We realized a comparative survey enters two particular methods of this family : the evolution strategies and the genetic programming after having proposed possibilities of implementation in the speech systems for each of her. At the end of this survey, we noted that the power of every method is located in the category of the problems to which it has been initially conceived. The evolution strategies offer important possibilities in optimization, and can be applied efficiently in the phase of recognition. The genetic programming as for her, can improve the quality of learning and linguistics treatments, seen its performances concerning automatic development of programs.