D&sambigu&sation lexicale de textes :... (PDF Download Available)
See all >4 CitationsSee all >46 ReferencesSee all >1 Figure
7.24Université Grenoble Alpes2.51Université Pierre Mendès France - Grenoble 26.35Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM)AbstractIn this article, we present the notions of local and global algorithms, for the word sense disambiguation of texts. A local algorithm allows to calculate the semantic similarity between two lexical objects. Global algorithms propagate local measures at the upper level. We use this notion to compare an ant colony algorithm to other methods from the state of the art: a genetic algorithm and simulated annealing. Through their evaluation on a reference corpus, we show that the run-time efficiency of the ant colony algorithm makes the automated estimation of parameters possible and in turn the improvement of the quality results as well. Last, we study several late classifier fusion strategies over the results to improve the performance.
Dans cet article, nous présentons la notion d’algorithme local et d’algorithme global pour la désambigu?sation lexicale de textes. Un algorithme local permet de calculer la proximité sémantique entre deux objets lexicaux. L’algorithme global permet de propager ces mesures lo- cales à un niveau supérieur. Nous nous servons de cette notion pour confronter un algorithme à colonies de fourmis à d’autres méthodes issues de l’état de l’art, un algorithme génétique et un recuit simulé. En les évaluant sur un corpus de référence, nous montrons que l’efficacité temporelle des algorithmes à colonies de fourmis rend possible l’amélioration automatique du paramétrage et, en retour, leur amélioration qualitative. Enfin, nous étudions plusieurs stra- tégies de fusion tardive des résultats de nos algorithmes pour améliorer leurs performances.Discover the world's research14+ million members100+ million publications700k+ research projectsFigures
Désambigu?sation lexicale de textes :efficacité qualitative et temporelled’un algorithme à colonies de fourmisDidier Schwab — Jér?me Goulian — Andon TchechmedjievUniv. Grenoble Alpes, Laboratoire d’Informatique de Grenoble équipe GETALP41 rue des mathématiques, BP 53 38041 Grenoble Cedex 9{Didier.Schwab,Jerome.Goulian,Andon.Tchechmedjiev}@imag.fr, http://getalp.imag.fr/WSD/R?SUM?. Dans cet article, nous présentons la notion d’algorithme local et d’algorithme globalpour la désambigu?sation lexicale de textes. Un algorithme local permet de calculer la proximitésémantique entre deux objets lexicaux. L’algorithme global permet de propager ces mesures lo-cales à un niveau supérieur. Nous nous servons de cette notion pour confronter un algorithmeà colonies de fourmis à d’autres méthodes issues de l’état de l’art, un algorithme génétiqueet un recuit simulé. En les évaluant sur un corpus de référence, nous montrons que l’efficacitétemporelle des algorithmes à colonies de fourmis rend possible l’amélioration automatique duparamétrage et, en retour, leur amélioration qualitative. Enfin, nous étudions plusieurs stra-tégies de fusion tardive des résultats de nos algorithmes pour améliorer leurs performances.ABSTRACT. In this article, we present the notions of local and global algorithms, for the wordsense disambiguation of texts. A local algorithm allows to calculate the semantic similaritybetween two lexical objects. Global algorithms propagate local measures at the upper level. Weuse this notion to compare an ant colony algorithm to other methods from the state of the art: agenetic algorithm and simulated annealing. Through their evaluation on a reference corpus, weshow that the run-time efficiency of the ant colony algorithm makes the automated estimation ofparameters possible and in turn the improvement of the quality results as well. Last, we studyseveral late classifier fusion strategies over the results to improve the performance.MOTS-CL?S : désambigu?sation lexicale fondée sur des similarités, algorithmes locaux/globaux,algorithmes à colonies de fourmis, algorithmes stochastiques d’optimisation.KEYWORDS: Word Sense Disambiguation based on similarity measures, local/global algorithms,Ant Colony Algorithms, Stochastic optimization algorithms.TAL. Volume 54 – n? 1/2013, pages 99 à 138
100 TAL. Volume 54 – n? 1/20131. IntroductionLa désambigu?sation lexicale est une t?che centrale pour le traitement automa-tique des langues. Elle peut en effet permettre d’améliorer de nombreuses applicationscomme l’extraction d’informations multilingues, le résumé automatique ou encore latraduction automatique. Schématiquement, il s’agit de choisir quel est le sens le plusapproprié pour chaque mot d’un texte dans un inventaire prédéfini. Par exemple, dans<< La souris mange le fromage. >>, l’animal devrait être préféré au dispositif électro-nique. De nombreux travaux existent sur le sujet, que l’on sépare habituellement enapproches supervisées et non supervisées. Les premières utilisent des apprentissagesréalisés gr?ce à des corpus manuellement annotés, contrairement aux secondes. Nouspensons que cette typologie devrait être raffinée. En effet, de nombreuses approchesutilisent, généralement sans le dire, un algorithme local et un algorithme global. L’al-gorithme local permet de donner une mesure de la proximité sémantique entre deuxobjets lexicaux (sens, mots, constituants, etc.) tandis que l’algorithme global permetde propager les mesures locales à un niveau supérieur. Cette double typologie nouspara?t pourtant centrale et permet de mieux caractériser les propriétés des systèmes dedésambigu?sation lexicale. Ainsi un système peut être constitué d’un algorithme localplus ou moins supervisé et d’un algorithme global lui aussi plus ou moins supervisé.Dans cet article, nous présentons cette notion et montrons qu’elle permet de mieuxcomprendre certaines propriétés et performances des systèmes mais aussi de mieuxévaluer une certaine limite de la non supervision complète. Nous nous servons en-suite de cette notion pour confronter un algorithme à colonies de fourmis (ACA) àd’autres méthodes issues de l’état de l’art, un algorithme génétique (GA) et un recuitsimulé (SA). En les évaluant sur un corpus de référence, nous montrons que l’efficacitétemporelle des algorithmes à colonies de fourmis rend possible l’amélioration auto-matique du paramétrage et, en retour, l’amélioration qualitative des résultats. Enfin,nous étudions plusieurs stratégies de fusion tardive des résultats de nos algorithmes etmontrons que l’une d’elle atteint le niveau de la référence premier sens et rivalise avecles moins bons algorithmes supervisés.2. Désambigu?sation lexicale : bref état de l’artSchématiquement, une t?che de désambigu?sation lexicale consiste à choisir quelest le sens le plus approprié pour chaque mot d’un texte. Comme rappelé en intro-duction, de nombreux travaux existent sur le sujet. Le lecteur pourra consulter (Ide etVéronis, 1998) pour les travaux antérieurs à 1998 et (Agirre et Edmonds, 2006) ou(Navigli, 2009) pour un état de l’art complet.2.1. Approches superviséesLes approches supervisées (ou d’apprentissage automatique) reposent sur l’utili-sation d’un nombre important de ressources annotées. Les données d’apprentissage
Fourmis et désambigu?sation lexicale 101permettent alors de créer un classifieur qui peut déterminer le sens le plus adapté d’unmot dans un contexte donné. De nombreuses méthodes supervisées comme les listes etarbres de décision, les classifications na?ves bayésiennes, les réseaux de neurones, lesapproches de type plus proches voisins, les machines à vecteurs de support, etc. ontété appliquées au problème de la désambigu?sation lexicale. Même si les méthodessupervisées tendent à donner de meilleurs résultats (sur l’anglais) que les méthodesnon supervisées, à la fois en termes de vitesse et de qualité, leur principal désavan-tage est qu’elles nécessitent une grande quantité de données annotées manuellementpour un inventaire de sens donné, une langue donnée ou pour un domaine spécifiquedonné (sport, finance...). Cette constatation, que nous partageons avec Navigli et La-pata (2010), nous a conduits à nous intéresser plus particulièrement à des approchesnon supervisées.2.2. Approches non superviséesLes approches non supervisées n’utilisent pas de corpus annotés. Certaines de cesméthodes utilisent des corpus non annotés pour construire des vecteurs de mots ou desgraphes de cooccurrences tandis que d’autres utilisent des sources de connaissance ex-ternes (dictionnaires, thésaurus, bases lexicales...). Ces méthodes consistent à donnerun score censé refléter la proximité des objets linguistiques (généralement des mots oudes sens de mots) comparés. Ces scores peuvent être des similarités (au sens mathéma-tique du terme) et donc avoir une valeur entre 0 et 1, des distances, et donc respecterleurs trois propriétés (séparation, symétrie et inégalité triangulaire) ou plus générale-ment une valeur positive non bornée. Parmi ces mesures, on peut citer les mesuresou distances entre vecteurs (vecteurs conceptuels (Schwab, 2005), LSA (Deerwesteret al., 1990)), les mesures fondées sur une distance taxonomique dans un réseau lexi-cal (nombre d’arcs dans le graphe entre deux sens), qu’elles utilisent toutes (Hirst etSt-Onge, 1998) ou une partie des relations du réseau (Rada et al., 1989 ; Leacock etChodorow, 1998 ; Wu et Palmer, 1994), les mesures basées sur le contenu d’informa-tion (Resnik, 1995 ; Lin, 1998 ; Seco et al., 2004) ou encore des mesures hybridescombinant plusieurs de ces approches (Li et al., 2003 ; Pirró et Euzenat, 2010). Lelecteur pourra consulter (Pedersen et al., 2005 ; Cramer et al., 2010 ; Navigli, 2009)pour un panorama plus complet. En désambigu?sation lexicale, ces mesures sont uti-lisées de fa?on locale entre deux sens de mots, et sont ensuite appliquées à un niveauglobal. Dans cet article, nous utilisons une telle mesure comme score local (voir sec-tion 3.1.2).2.3. Approches semi-superviséesUne catégorie intermédiaire, constituée des approches semi-supervisées, utilisequelques données annotées comme, par exemple, un sens par défaut issu d’un cor-pus annoté lorsque l’algorithme principal échoue (Navigli, 2009).
102 TAL. Volume 54 – n? 1/20133. Algorithmes locaux et globaux pour la désambigu?sation lexicale fondée surdes similaritésDe nombreux systèmes de désambigu?sation lexicale reposent sur la notion d’algo-rithme local et d’algorithme global. L’algorithme local permet de donner une mesurede la proximité sémantique entre deux objets lexicaux (sens, mots, constituants, etc.)tandis que l’algorithme global permet de propager les mesures locales à un niveausupérieur.3.1. Algorithmes locauxLes algorithmes locaux sont les méthodes présentées dans la section 2.2. En an-glais, langue de notre corpus d’évaluation, elles sont souvent utilisées sur WordNet.3.1.1. Bases lexicales utilisées en désambigu?sation lexicale : WordNet et BabelNetWordNet (Fellbaum, 1998) est une base lexicale pour l’anglais très largement uti-lisée dans le cadre de la désambigu?sation lexicale. Elle est organisée en ensembles desynonymes (synsets) auxquels sont associées leurs parties du discours et les relationssémantiques qu’ils entretiennent avec d’autres synsets (antonymes, hyponymes, mé-ronymes...) ainsi qu’une définition. La version actuelle de WordNet, la 3.0, contientplus de 155 000 mots pour 117 000 synsets.Il existe depuis peu BabelNet (Navigli et Ponzetto, 2012), une base alignant lessens de WordNet à ceux de Wikipedia ce qui permet de définir les termes avec desdéfinitions dans plusieurs langues. Nous commen?ons à l’exploiter par ailleurs maisl’algorithme local de cet article se base seulement sur la partie WordNet.3.1.2. Notre algorithme local : inspiré par LeskL’algorithme local utilisé dans cet article est une variante de l’algorithme de Lesk(Lesk, 1986). Proposé il y a plus de vingt-cinq ans, cet algorithme se caractérise par sasimplicité. Il ne nécessite qu’un dictionnaire et aucun apprentissage. Le score donnéà une paire de sens est le nombre de mots – ici simplement les suites de caractèresséparées par des espaces – en commun dans leur définition, sans tenir compte ni deleur ordre, ni de sous-séquences communes (approche sac de mots), ni d’informationsmorphologiques ou syntaxiques. Les variantes de cet algorithme sont encore aujour-d’hui parmi les meilleures sur l’anglais (Ponzetto et Navigli, 2010).Notre algorithme local exploite les liens présents dans WordNet. Au lieu d’utiliseruniquement la définition d’un sens, elle utilise également la définition des différents
Fourmis et désambigu?sation lexicale 103sens qui lui sont liés1. Cette idée est similaire à celle de Banerjee et Pedersen (2002)2.Cet algorithme local est nommé dans la suite Leskext.Pour des raisons d’efficacité (Schwab et al., 2011 ; Schwab et al., 2012), les dé-finitions sont transformées en vecteurs d’entiers qui sont triés, chaque entier corres-pondant à un mot. Notre algorithme de propagation à colonies de fourmis utilise éga-lement ces pseudodéfinitions créées à la volée (voir partie 5.2.2.3). L’implantation etle dictionnaire qui permettent d’utiliser Leskextpeuvent être trouvés sur le site dusous-groupe WSD du GETALP3et en particulier sur la page dédiée à cet article4.Récemment, Miller et al. (2012) ont présenté un algorithme local qui obtient demeilleurs résultats que notre Leskext(voir section 6.6). Il s’agit d’une nouvelle exten-sion des définitions fondée sur leur voisinage dans un corpus. Cette solution sembletrès simple à mettre en oeuvre et nous étudions actuellement cette possibilité. Nousrappelons au lecteur que cet article concerne les algorithmes globaux et que nous au-rions pu choisir n’importe quel algorithme local pour l’illustrer.3.2. Algorithmes globaux stochastiques pour la désambigu?sation lexicaleUn algorithme global propage à un niveau supérieur les mesures locales. Nous pré-sentons dans les section suivantes chacun des algorithmes étudiés. Le lecteur trouveraen annexes leur description complète en langage algorithmique.3.2.1. Approche exhaustiveLa méthode de propagation la plus directe est la recherche exhaustive utilisée parexemple dans (Banerjee et Pedersen, 2002). Il s’agit de considérer les combinaisonsde l’ensemble des sens des mots dans le même contexte (fenêtre de mots, phrase,texte, etc.), de donner un score à chacune de ces combinaisons et de choisir celle quia le meilleur score. Le principal problème de cette méthode est la rapide explosioncombinatoire qu’elle engendre. Considérons la phrase suivante (dans laquelle seizemots ont une entrée dans notre dictionnaire) tirée du corpus d’évaluation que nousutilisons dans la partie 6.1, << The pictures they painted were flat, not round as a figureshould be, and very often the feet did not look as if they were standing on the groundat all, but pointed downwards as if they were hanging in the air. >>, ?picture? et ?air?ont neuf sens, ?paint? quatre, ?be?, ?point? et ?figure? treize, ?flat? dix-sept, ?very? et ?often?deux, ?foot? et ?ground? onze, ?look? dix, ?stand? douze, ?at all? et ?downwards? un et ?hang?quinze. Il y a alors 137 051 946 345 600 combinaisons de sens possibles à analyser.Ce nombre est comparable à la quantité d’opérations (et le calcul d’une combinaison1. L’ensemble des relations sémantiques présentes dans WordNet est utilisé.2. Banerjee et Pedersen (2002) introduisent également une notion de sous-séquence identiquedans les définitions. Nous n’avons pas encore testé cette variante dont la complexité algorith-mique est nettement supérieure à celle de notre algorithme.3. http://getalp.imag.fr/WSD/4. http://getalp.imag.fr/static/wsd/GETALP-WSD-ACA/TAL-54-1/index.xhtml
104 TAL. Volume 54 – n? 1/2013nécessite des dizaines voire des centaines d’opérations) que peuvent théoriquementeffectuer 542 processeurs Intel Xeon Phi Coprocessor 5110P (1,053 GHz, 60 coeurs,240 fils d’exécutions simultanées, 2 700 dollars l’unité), les plus rapides existant à lami-2013 en une seconde. Le calcul exhaustif est donc très compliqué à réaliser dansdes conditions réelles et, surtout, rend impossible l’utilisation d’un contexte d’analyseplus important.Pour contourner ce problème, plusieurs approches sont possibles. Les premières,dites approches complètes, tentent de réduire la combinatoire en utilisant des tech-niques d’élagage et des heuristiques de choix. Dans le cadre de la désambigu?sationlexicale, c’est le cas par exemple de l’approche proposée par Hirst et St-Onge (1998),fondée sur les cha?nes lexicales (une mesure de similarité sémantique à base de dis-tance taxonomique exploitant l’ensemble des relations de WordNet), combinant desrestrictions5lors de la construction de la cha?ne lexicale globale avec une heuristiquede choix gloutonne. Selon Navigli (2009) le problème majeur d’une telle approche estson manque de précision du fait de la stratégie gloutonne employée. Différentes amé-liorations ont toutefois été proposées parmi lesquelles on peut notamment citer Silberet McCoy (2000). D’autres approches complètes intéressantes ont été menées dans lecadre de la désambigu?sation lexicale non supervisée ; citons en particulier Brody etLapata (2008).Les secondes méthodes, dites approches incomplètes parce qu’elles n’explorentqu’une partie de l’espace de recherche, utilisent des heuristiques permettant de seguider vers des zones de l’espace de recherche semblant plus prometteuses. Ces heu-ristiques s’appuient en général sur des probabilités et les choix sont réalisés de fa?onstochastique, c’est ce qui nous intéresse ici.On peut alors distinguer deux grandes familles de méthodes :– les approches par voisinage (de nouvelles configurations sont créées à partir deconfigurations existantes) parmi lesquelles on trouve des approches issues de l’intel-ligence artificielle comme les algorithmes génétiques ou des méthodes d’optimisationcomme le recuit simulé ;– les approches constructives (de nouvelles configurations sont générées par ajoutitératif d’éléments de solution aux configurations en cours de construction) parmi les-quelles on trouve par exemple les algorithmes à base de fourmis3.2.2. Cadre de notre étude, hypothèse de travailL’objectif de cet article est de comparer notre algorithme à colonies de fourmis (ap-proche incomplète constructive) à d’autres approches incomplètes. Nous avons choiside confronter dans un premier temps notre approche à deux approches par voisinage5. De telles restrictions, pour diminuer le nombre de combinaisons à examiner, peuvent éga-lement être fondées sur l’utilisation de corpus comme par exemple la recherche des cha?neslexicales compatibles (Gale et al., 1992 ; Vasilescu et al., 2004). Ces approches rentrent alors,de ce fait, dans le cadre de la désambigu?sation lexicale supervisée.
Fourmis et désambigu?sation lexicale 105ayant été utilisées dans le cadre de la désambigu?sation lexicale non supervisée : lesalgorithmes génétiques (Gelbukh et al., 2003) et le recuit simulé (Cowie et al., 1992).Notre hypothèse de travail, dans cet article, est en effet de considérer comme fe-nêtre d’analyse, le texte. Ce choix est également effectué par Cowie et al. (1992) pourleurs algorithmes de recuit simulé et par Gelbukh et al. (2003) pour leur algorithmegénétique ; cette idée étant reprise récemment par Navigli et Lapata (2010). De nom-breuses approches, en revanche, toujours pour des raisons calculatoires et parfois sansle dire explicitement, utilisent un contexte plus réduit. Nous y voyons deux problèmes.Le premier est que nous n’avons aucun moyen d’assurer la cohérence entre les senschoisis. Deux sens généralement incompatibles entre eux pourront être choisis car lecontexte ne comprend pas le deuxième mot. Par exemple, même avec une fenêtre desix mots avant et six mots après, la phrase << L’homme est rentré chez lui vers 19 h 30et a garé sa voiture sur le parking. Le chien était bien en place lorsque l’homme ran-gea son fusil. >>, << fusil >> n’entre pas en compte pour désambigu?ser le terme << chien >>.Le second problème est qu’un texte conserve généralement une certaine unité séman-tique. Par exemple, comme le constatent Gale et al. (1992) ou Hirst et St-Onge (1998),un mot utilisé plusieurs fois dans un texte aura généralement le même sens ; cette in-formation ne pouvant pas être exploitée avec un fenêtrage.C’est en raison de cette présence d’un fenêtrage que nous avons écarté de notreétude des approches telles que Lesk étendu simplifié6de Miller et al. (2012) ou l’appli-cation à la désambigu?sation lexicale faite par Mihalcea et al. (2004) de l’algorithmede PageRank (Brin et Page, 1998)7, bien que travaillant sur un espace de recherchesous forme de graphe comme les algorithmes à colonies de fourmis.Par ailleurs, l’objectif de cet article n’est pas ici de comparer entre elles les qualitésde ces trois approches incomplètes par rapport à l’optimum. En effet, nous souhaitonsà terme nous placer dans le cadre d’applications nécessitant une désambigu?sation entemps réel. Or, nos premières expériences (Schwab et al., 2011) nous ont permis deconstater que l’algorithme exhaustif utilisant notre mesure sémantique locale, évalué,faute de mieux étant donnée la combinatoire, sur un contexte réduit (la phrase) n’étaiten mesure de ne fournir un optimum que dans environ 77 % des cas.6. Le choix des termes Lesk simplifié, Lesk étendu simplifié est d’ailleurs certainement peupertinent. Dans la perspective algorithme local/global, ces noms font un mélange peu propiceà la compréhension. L’algorithme global compare simplement un sens de mot aux mots dansle contexte du mot à désambigu?ser. L’algorithme local peut reposer sur plusieurs matériaux :un dictionnaire de définitions simples, un dictionnaire de définitions étendues gr?ce à un réseausémantique, un dictionnaire de définitions étendues gr?ce à un corpus, etc. Nous préférons leterme de Lesk-contexte. Sur la question des performances, Lesk-contexte est un algorithme trèsefficace et rapide mais qui ne nous semble pas offrir de réelles perspectives d’améliorations,en particulier vers la désambigu?sation utilisant des informations de nature multilingue (désam-bigu?sation d’une langue peu dotée par un inventaire de sens décrit dans d’autres langues à lamanière de BabelNet par exemple).7. Cet algorithme, par ailleurs déterministe, simule une marche aléatoire.
106 TAL. Volume 54 – n? 1/20133.2.3. Présentation généraleL’objectif des algorithmes étudiés ici est d’assigner à chaque mot wid’un textede m mots, l’un de ses sens wi,j. La définition du sens j du mot i est notée d(wi,j).L’espace de recherche correspond à toutes les combinaisons de sens possibles pour letexte considéré. Ainsi, une configuration C du problème est représentée par un vecteurd’entiers tel que j = C[i] est le sens wi,j.3.3. Configuration et score global (fonction de co?t)Ces algorithmes ont besoin d’une mesure pour permettre une évaluation pertinented’une configuration donnée. Le score du sens sélectionné pour un mot donné peut êtreexprimé par la somme des scores locaux entre ce sens et les sens sélectionnés detous les autres mots du contexte considéré. Ainsi, pour évaluer une configuration duproblème donné, on peut considérer comme mesure globale, comme fonction de co?t,la somme des scores de tous les sens sélectionnés des mots du texte :Score(C) =Pmi=1Pmj=iLeskext(wi,C[i], wj,C[j]).4. Deux algorithmes stochastiques de l’état de l’art4.1. Algorithme génétique pour la désambigu?sation lexicaleL’algorithme génétique (GA pour genetic algorithme), inspiré de Gelbukh et al.(2003), peut être découpé en cinq étapes distinctes : initialisation, sélection, croise-ment, mutation et évaluation. Mis à part l’initialisation, les autres étapes sont exécu-tées dans cet ordre pour chaque génération de la population.L’étape d’initialisation consiste en la génération aléatoire d’une population de λindividus (λ configurations du problème). La taille de la population reste inchangéependant toute l’exécution de l’algorithme.Pendant l’étape de sélection, le score de chaque individu de la population est cal-culé. Un taux de croisement (CR pour Crossover Ratio) est utilisé pour déterminerquels individus de la population seront choisis pour un croisement. La probabilitéqu’un individu soit choisi est pondérée en fonction de son score et de celui du meilleurindividu de la population. Les individus qui ne sont pas sélectionnés pour un croise-ment sont clonés dans la nouvelle population. Par ailleurs, le meilleur individu estsystématiquement ajouté à la nouvelle population.L’étape de croisement consiste à trier les individus en fonction de leur score globalpuis de les croiser. Si le nombre d’individus est impair, l’individu au score le plusbas est ajouté directement dans la nouvelle population. L’opération de croisement estalors appliquée pour chacune des paires d’individus. Les paires sont formées selonl’ordre décroissant des scores globaux de chacun des individus. Les gènes des deux
Fourmis et désambigu?sation lexicale 107individus (les sens sélectionnés dans les configurations) sont alors échangés autour dedeux pivots choisis aléatoirement (tout ce qui est entre les pivots est échangé).? l’étape de mutation, chaque individu a ensuite une probabilité de muter (para-mètre MR (pour Mutation Rate)). L’étape de mutation consiste à réaliser MN change-ments aléatoires sur les individus (configurations) concernés par la mutation.L’étape d’évaluation correspond à l’évaluation du critère de terminaison de l’al-gorithme, à savoir ici une convergence du score du meilleur individu. Pour vérifierla convergence, un seuil STH est utilisé. En d’autres termes, si le score du meilleurindividu reste le même pendant STH générations, l’algorithme se termine.4.2. Recuit simulé pour la désambigu?sation lexicaleLa méthode du recuit simulé (SA pour simulated annealing) telle que décrite dans(Cowie et al., 1992) est fondée sur les principes physiques du refroidissement desmétaux.La méthode du recuit simulé travaille sur la même représentation du problème quel’algorithme génétique présenté dans la section précédente. Cependant il ne travailleque sur une unique configuration du problème, choisie aléatoirement au départ. L’al-gorithme s’exécute en cycles. Chaque cycle est composé de IN itérations. Les autresparamètres sont la température initiale T08et le taux de refroidissement ( ClR pour Co-oling Rate, ∈ [0; 1]). ? chaque itération, une modification aléatoire est réalisée sur laconfiguration courante Ccpour produire une nouvelle configuration C0c. ?tant donné?E = Score(Cc) - Score(C0c), la probabilité P (A) d’acceptation9de la configura-tion C0cà la place de Ccest :P (A) =(1 if ?E & 0e-?ETsinonLa configuration courante peut évoluer vers une configuration ayant un score infé-rieur afin d’empêcher l’algorithme de converger vers un maximum local et lui permetainsi d’explorer d’autres parties de l’espace de recherche qui contiendront le maxi-mum global.Si, à la fin d’un cycle, la configuration courante est restée inchangée par rapport àcelle du cycle précédent, l’algorithme se termine. Dans le cas contraire, la températureest abaissée de T ·ClR. En d’autres termes, plus il faut de cycles pour que l’algorithme8. Le choix de la température initiale passe par le choix de la probabilité d’acceptation initiale.Dans les expériences décrites section 6.3, nous nous pla?ons exactement dans le même contexteque Cowie et al. (1992) (même table de décroissance de probabilités) en reprenant leurs hypo-thèses initiales.9. Cette probabilité est issue de lois thermodynamiques.
108 TAL. Volume 54 – n? 1/2013converge, plus la probabilité d’accepter des scores plus faibles diminue ; ceci garantitque l’algorithme puisse se terminer.La configuration avec le score le plus haut est sauvegardée à chaque étape. Cetteconfiguration sera celle qui sera considérée comme résultat indépendamment de laconfiguration courante à la convergence de l’algorithme.5. Algorithme global fondé sur des colonies de fourmis5.1. Algorithmes à colonies de fourmisLes algorithmes à colonies de fourmis ont pour origine la biologie et les obser-vations réalisées sur le comportement social des fourmis. En effet, ces insectes ontcollectivement la capacité de trouver le plus court chemin entre leur fourmilière et unesource d’énergie. Il a pu être démontré que la coopération au sein de la colonie estauto-organisée et résulte d’interactions entre individus autonomes. Ces interactions,souvent très simples, permettent à la colonie de résoudre des problèmes complexes.Ce phénomène est appelé intelligence en essaim (Bonabeau et Théraulaz, 2000). Il estde plus en plus utilisé en informatique où des systèmes de contr?le centralisés gagnentsouvent à être remplacés par d’autres, fondés sur les interactions d’éléments simples.En 1989, Jean-Louis Deneubourg étudie le comportement des fourmis biologiquesdans le but de comprendre la méthode avec laquelle elles choisissent le plus courtchemin et le retrouvent en cas d’obstacle. Il élabore ainsi le modèle stochastique dit deDeneubourg (Deneubourg et al., 1989), conforme à ce qui est observé statistiquementsur les fourmis réelles quant à leur partage entre les chemins. Ce modèle stochastiqueest à l’origine des travaux sur les algorithmes à colonies de fourmis.Le concept principal de l’intelligence en essaim est la stygmergie,c’est-à-dire l’interaction entre agents par modification de l’environnement. Unedes premières méthodes que l’on peut apparenter aux algorithmes à fourmis estl’écorésolution qui a montré la puissance d’une heuristique de résolution collectivefondée sur la perception locale, évitant tout parcours explicite de graphe d’états(Drogoul, 1993).En 1992, Marco Dorigo et Luca Maria Gambardella con?oivent le premier algo-rithme fondé sur ce paradigme pour le célèbre problème combinatoire du voyageurde commerce (Dorigo et Gambardella, 1997). Dans les algorithmes à base de fourmisartificielles, l’environnement est généralement représenté par un graphe et les fourmisvirtuelles utilisent l’information accumulée sous la forme de chemins de phéromonedéposée sur les arcs du graphe. De fa?on simple, une fourmi se contente de suivre lestraces de phéromones déposées précédemment ou explore au hasard dans le but detrouver un chemin optimal, fonction du problème posé, dans le graphe.Ces algorithmes offrent une bonne alternative à tout type de résolution de pro-blèmes modélisables sous forme d’un graphe. Ils permettent un parcours rapide et ef-ficace du graphe et offrent des résultats comparables à ceux obtenus par les différentes
Fourmis et désambigu?sation lexicale 109méthodes de résolution et heuristiques utilisées en algorithmique des graphes. Leurgrand intérêt réside dans leur capacité à s’adapter à un changement de l’environne-ment. Le lecteur trouvera dans (Dorigo et Stützle, 2004) ou (Monmarche et al., 2009)de bons états de l’art sur la question.5.2. ACA : algorithme à colonies de fourmis pour la désambigu?sation lexicaleDans cette section, nous présentons notre algorithme à colonies de fourmis pourla désambigu?sation lexicale. Il est nommé dans la suite ACA (pour Ant Colony Algo-rithm).5.2.1. Vue d’ensembleL’environnement des fourmis est un graphe. Il peut être linguistique – morpholo-gique comme dans (Rouquet et al., 2010) ou morphosyntaxique comme dans (Schwabet Lafourcade, 2007 ; Monmarche et al., 2009) – ou être simplement organisé en fonc-tion des éléments du texte.En fonction de l’environnement choisi, les résultats de l’al-gorithme ne sont évidemment pas les mêmes. Des recherches sont actuellement me-nées à ce sujet mais, dans cet article, nous ne nous intéressons qu’à un cas de basec’est-à-dire un graphe simple (voir figure 1), sans information linguistique externe,afin de mieux faire comprendre la mécanique de nos algorithmes. Dans ce graphe,TexteSensPhrase PhrasePhraseMotMotMot Mot Mot MotSensSens SensSensSensSens Sens Sens123 41098765111213141516171819Figure 1. Environnement utilisé dans cette expérience : texte, phrases et mots corres-pondent aux noeuds dits normaux (noeuds 1 à 10), un sens de mot correspond à unefourmilière (noeuds 11 à 19).nous distinguons deux types de noeuds : les fourmilières et les noeuds normaux. Sui-vant les idées développées dans (Schwab, 2005) et (Monmarche et al., 2009), chaquesens possible d’un mot est associé à une fourmilière. Les fourmilières produisent desfourmis. Ces fourmis se déplacent dans le graphe à la recherche d’énergie puis larapportent à leur fourmilière mère qui pourra alors créer de nouvelles fourmis. Unefourmi a une odeur qui correspond à la définition du sens de leur fourmilière mère.Pour une fourmi, un noeud peut être : (1) la fourmilière mère où elle est née ; (2)une fourmilière ennemie, toutes les fourmilières qui correspondent à un autre sens du
110 TAL. Volume 54 – n? 1/2013même mot ; (3) une fourmilière potentiellement amie, toutes celles qui ne sont pasennemies ; (4) un noeud qui n’est pas une fourmilière : les noeuds normaux.Par exemple, dans la figure 1, pour une fourmi née dans la fourmilière 19, la four-milière 18 est une ennemie car elles ont toutes deux le même père (le noeud 10), lesfourmilières potentiellement amies sont les noeuds 11 à 17 et les noeuds normaux sontles noeuds 1 à 10.Les déplacements des fourmis se déroulent en fonction des scores locaux (cf.section 3.1.2), de la présence d’énergie, du passage des autres fourmis (les fourmislaissent des traces sur les arcs où elles passent sous la forme de phéromone) et duvecteur odeur des noeuds (les fourmis déposent une partie de leur odeur sur les noeudsnormaux où elles passent). Une fois arrivée sur la fourmilière d’un autre terme (cor-respondant à un sens de ce terme), une fourmi peut choisir de revenir directement àsa fourmilière mère. Elle établit alors, entre les deux fourmilières, un pont que lesautres fourmis sont, à leur tour, susceptibles d’emprunter et de renforcer gr?ce à leurphéromone. Ainsi ces fourmis pourront aller d’une fourmilière à une autre sans avoirà remonter jusqu’à la racine de l’arbre. Ce renforcement a lieu si les informationslexicales conduisent les autres fourmis à emprunter le pont et dispara?t dans le casinverse. Ainsi, les fourmis établissent de nombreux liens entre fourmilières de senscompatibles.Les ponts correspondent donc à des interprétations de la phrase. L’émergence detels circuits dans le graphe contribue à la monopolisation des ressources de la colonie(fourmis et énergie) et à l’épuisement des ressources associées aux autres fourmilières(ces cas correspondent donc aux sens incompatibles dans le contexte avec les informa-tions lexicales considérées). Le fait de ne pas considérer dès le départ, dans l’espacede recherche, tous les ponts possibles entre les fourmilières potentiellement amies,mais de laisser leur construction éventuelle aux fourmis cherchant à rejoindre leurfourmilière mère est pertinent dans ce cadre. Notre approche reste constructive tout enlimitant le nombre de configurations à explorer10.5.2.2. Détails de l’algorithmeLes tableaux 1 et 2 présentent les principales notations ainsi que les paramètres(et leurs valeurs) utilisés dans la suite de l’article. Les sections 5.5 et 6.3 reviendronten détail sur les paramètres principaux de l’algorithme et l’estimation des valeursutilisées dans les expérimentations menées.5.2.2.1. ?nergieAu début de la simulation, le système possède une certaine énergie qui est répar-tie équitablement sur chacun des noeuds. Les fourmilières utilisent celle qu’elles pos-sèdent pour fabriquer des fourmis avec une probabilité fonction de cette même énergie10. Cette approche se distingue en cela des approches classiques d’optimisation considérantl’ensemble des configurations dans l’espace de recherche initial.
Fourmis et désambigu?sation lexicale 111Notation DescriptionFAFourmilière correspondant au sens AfAFourmi née dans la fourmilière FAV (X) Vecteur odeur associé à X. X est un noeud ou une fourmiE(X) ?nergie possédée par X. X est un noeud ou une fourmiEvalf(N) ?valuation du noeud N par fEvalf(A) ?valuation de l’arc A (quantité de phéromone présente) par f?(t/c)(A) Quantité de phéromone présente sur l’arc A à l’instant t ou au cycle cTableau 1. Principales notations pour l’algorithme à colonies de fourmisNotation Description ValeurEF?nergie utilisée par une fourmilière 1pour produire une fourmiEa?nergie prise par une fourmi 1lorsqu’elle arrive sur un noeudθ Phéromone déposée par une fourmi 1lors de la traversée d’un arcEmax?nergie maximale que peut porter une fourmi 2-10δ ?vaporation de la phéromone entre chaque cycle 20-80 %E0Quantité initiale d’énergie sur chaque noeud 5-20ω Durée de vie d’une fourmi 5-20 (cycles)LVLongueur du vecteur odeur 30-150 (dim.)δVProportion du vecteur odeur déposée 10-90 %par une fourmi lorsqu’elle arrive sur un noeudcacNombre de cycles de la simulation 100Tableau 2. Paramètres et valeurs pour l’algorithme à colonies de fourmiset suivant une courbe sigmo?de classiquement utilisée dans les réseaux de neurones ar-tificiels (Lafourcade, 2011). Comme dans (Schwab et Lafourcade, 2007) ou (Guinandet Lafourcade, 2010), notre fonction sigmo?de11estarctan(x)π+12. Ces fourmis sedéplacent dans le graphe et cherchent à ramener leur énergie à leur fourmilière mèrequi sera alors à même de produire de nouvelles fourmis. Les fourmis ont une durée devie (ω) limitée (un nombre identique de cycles fixé a priori cf. tableau 2). Lorsqu’unefourmi meurt, toute l’énergie qu’elle transportait (et celle qui avait été utilisée par la11. La fonction sigmo?de a été choisie car elle permet d’avoir une valeur positive même lorsquele niveau d’énergie est négatif. Ainsi, les fourmilières concernées peuvent tout de même fabri-quer quelques fourmis. L’idée est de leur donner une dernière chance au cas où ces fourmis,trouvant des informations lexicales pertinentes, rapportent de l’énergie et relancent la produc-tion de la fourmilière.
112 TAL. Volume 54 – n? 1/2013fourmilière pour la produire) est déposée sur le noeud où elle se trouve. Ainsi la quan-tité d’énergie présente dans le système reste constante. C’est un point fondamental quipermet la convergence de l’algorithme vers une solution (renforcement de l’énergiedans quelques fourmilières, au détriment des autres).5.2.2.2. Phéromone de passageLes fourmis ont deux types de comportements. Elles peuvent soit chercher del’énergie, soit chercher à revenir à leur fourmilière mère. Lorsqu’elles se déplacentdans le graphe, elles laissent des traces sur les arcs où elles passent sous la formede phéromone. La phéromone influe sur les déplacements des fourmis qui préfèrentl’éviter lorsqu’elles cherchent de l’énergie et préfèrent la suivre lorsqu’elles tentent derevenir déposer cette énergie à leur fourmilière mère.Lors d’un déplacement, une fourmi laisse une trace en déposant sur l’arc A traverséune quantité de phéromone θ ∈ IR+. On a alors ?t + 1(A) = ?t(A) + θ.? chaque cycle, il y a une légère évaporation des phéromones. Cette baisse sefait de fa?on linéaire jusqu’à la disparition totale de la phéromone. Nous avons ainsi,?c + 1(A) = ?c(A) × (1 - δ) où δ est la proportion de phéromone qui s’évapore àchaque cycle.5.2.2.3. OdeurL’odeur d’une fourmilière est une représentation vectorielle correspondant à ladéfinition du sens correspondant (Schwab et al., 2012). Il s’agit donc de la définitiondu sens sous forme de vecteurs de nombres entiers. Chaque fourmi née dans cettefourmilière porte la même odeur, le même vecteur (voir section 3.1.2). Les noeudsnormaux sont initialisés avec des composantes vides. Lors de son déplacement sur lesnoeuds normaux du graphe, une fourmi propage son vecteur. Le vecteur V(N) porté parun noeud normal N est modifié lors du passage d’une fourmi. La fourmi dépose unepartie de son vecteur, un pourcentage des composantes prises au hasard qui remplacela même quantité d’anciennes valeurs, elles aussi choisies au hasard.Cette propagation intervient dans le déplacement des fourmis. Laisser une partiede son vecteur, c’est laisser une trace de son passage. Ainsi plus un noeud est proched’une fourmilière plus il y a de chances que les fourmis de cette fourmilière y soientpassées. Ce phénomène permet aux fourmis de revenir à leur fourmilière, ou éven-tuellement de se tromper et de se diriger vers des fourmilières amies. Cette erreur estainsi potentiellement bénéfique puisqu’elle peut permettre de créer un pont entre lesdeux fourmilières (cf.section 5.2.2.4). En revanche, lorsqu’une fourmi se trouve surune fourmilière, le vecteur n’est pas modifié ; ces noeuds conservent ainsi un vecteurconstant tout au long de la simulation.5.2.2.4. Création et suppression de pontsUn pont peut être créé lorsqu’une fourmi atteint une fourmilière potentiellementamie, c’est-à-dire lorsqu’elle arrive sur un noeud qui correspond à un sens d’un autre
Fourmis et désambigu?sation lexicale 113mot que celui de la fourmilière mère. Dans ce cas, la fourmi évalue non seulement lesnoeuds liés à cette fourmilière mais aussi le noeud correspondant à sa fourmilière mère.Si ce dernier est sélectionné12, il y a création d’un pont entre les deux fourmilières. Cepont est ensuite considéré comme un arc standard par les fourmis, c’est-à-dire que lesnoeuds qu’il lie sont considérés comme voisins. Si le pont ne porte plus de phéromone,il dispara?t.5.2.3. Déroulement de l’algorithmeL’algorithme consiste en une itération potentiellement infinie de cycles. ? toutmoment, la simulation peut être interrompue et l’état courant observé. Durant un cycle,on effectue les t?ches suivantes : (1) éliminer les fourmis trop vieilles (en fonction dela durée de vie paramétrée) ; (2) pour chaque fourmilière, solliciter la production d’unefourmi (une fourmi peut ou non voir le jour, de fa?on probabiliste) ; (3) pour chaquearc, diminuer le taux de phéromone (évaporation des traces) ; (4) pour chaque fourmi,déterminer son mode (recherche d’énergie ou retour à la fourmilière ; le changementétant fait de manière probabiliste), la déplacer et créer un pont interprétatif le caséchéant ; (5) calculer les conséquences du déplacement des fourmis (sur l’activationdes arcs et l’énergie des noeuds).Les déplacements d’une fourmi sont aléatoires mais influencés par son environne-ment. Lorsqu’une fourmi est sur un noeud, elle estime tous les noeuds voisins et tousles arcs qui les lient. La probabilité d’emprunter un arc Ajpour aller à un noeud Niest P (Ni, Aj) = max(Evalf(Ni,Aj)Pk=n,l=mk=1,l=1Evalf(Nk,Al), ?) où Evalf(N, A) est l’évaluationdu noeud N en prenant l’arc A, c’est-à-dire la somme de Evalf(N) et de Evalf(A).? permet à certaines fourmis de choisir des destinations évaluées comme improbablesmais qui permettraient d’atteindre des informations lexicales et des ressources quis’avèreraient intéressantes ensuite.Une fourmi qui vient de na?tre (c’est-à-dire d’être produite par sa fourmilière)part à la recherche d’énergie. Elle est attirée par les noeuds qui portent beaucoupd’énergie (Evalf(N) =E(N)Pm0E(Ni)) et évite les arcs qui portent beaucoup de phé-romone (Evalf(A) = 1 - ?t(A)) afin de permettre l’exploration de plus de so-lutions. Elle continue à collecter de l’énergie jusqu’au cycle où un tirage aléa-toire avec la probabilité P (retour) =E(f)Emaxla fera passer en mode retour. Dansce mode, elle va (statistiquement) suivre les arcs avec beaucoup de phéromone(Evalf(A) = ?t(A)) et aller vers les noeuds dont l’odeur est proche de la sienne(Evalf(N) =Leskext(V (N),V (fA))Pi=ki=1Leskext(V (Ni),V (fA))).12. De la même manière qu’expliqué en section 5.2.3, sans tenir compte de la phéromone si lepont n’existe pas encore.
114 TAL. Volume 54 – n? 1/20135.3. Exemple illustréGr?ce au parcours que va réaliser une fourmi (figures 2, 3, 4), nous illustrons main-tenant les différentes étapes de l’algorithme ACA sur la phrase << La souris contr?lel’ordinateur. >>. Les vecteurs des définitions sont représentés sous le noeud correspon-dant et sont précédés de la lettre V. Le niveau d’énergie est représenté par des barresempilées précédées par la lettre E. Les lignes entre les noeud représentent les che-mins et leur épaisseur la concentration de phéromone. Les numéros dans les cerclesmontrent les déplacements successifs de la fourmi. La quantité d’énergie que la fourmiporte lors de l’étape est matérialisée par les barres empilées à c?té du dessin de lafourmi et nommée E(A). Les nombres dans les vecteurs sous les fourmilières corres-pondent aux mots des définitions des sens correspondants (voir section 3.1.2).Pour cet exemple, nous suivons une fourmi qui na?t dans la fourmilière de?souris/dispositif ? correspondant au premier sens pour le nom ?souris?.Phrasesouris#ncontr?ler#vordinateur#nsouris
rongeurcontr?ler
vérifiercontr?ler
dirigerordinateur
machineVVVVVVVV1 69813 47211165V613174211915EEEEEEEEEsouris
dispositifFigure 2. Exemple : état de l’environnement au départSur la figure 3, la fourmi débute en mode recherche de nourriture. Elle prend uneunité d’énergie sur sa fourmilière (1) et commence à explorer le graphe en démarrantpar le noeud correspondant au nom ?souris#n? (2), le seul choix que l’environnementlui offre à ce moment-là. Sur le chemin vers ce noeud, elle dépose sa phéromone puis,en arrivant, elle prend une barre d’énergie. Elle dépose également un peu de son odeursur le noeud. Cette odeur est matérialisée par le dép?t de deux composants pris auhasard parmi ceux de sa fourmilière mère, soit ceux de ?souris/dispositif ?.La fourmi choisit ensuite de suivre le chemin (3) où elle dépose sa phéromone pouratteindre la racine de l’environnement (4). Elle y dépose également deux composantsdu vecteur de la fourmilière mère pris au hasard et prend une barre d’énergie. ? cestade, la fourmis possède trois barres d’énergie et une décision pseudo-aléatoire va lafaire passer en mode retour à la fourmilière mère.Comme une fourmi ne peut pas revenir sur un noeud d’où elle vient sauf sic’est sa seule possibilité, notre fourmi a le choix entre aller sur ?contr?ler#v? ou sur?ordinateur#n?.
Fourmis et désambigu?sation lexicale 115Les fourmis venant d’?ordinateur/machine? ont déposé une part de leur vecteur sur?ordinateur#n?. Le vecteur de ce noeud a donc plus d’éléments en commun avec le vec-teur de notre fourmis que celui de ?contr?ler#v?. Notre fourmi a donc plus de chancesd’aller vers ?ordinateur#n?. C’est ce qu’elle fait tout en déposant sa phéromone surson chemin (5). La fourmi laisse son odeur sur le noeud d’arrivée mais ne prend pasd’énergie puisqu’elle est en mode retour (6). Ensuite, elle ne peut qu’aller (7) vers?ordinateur/machine? (8).Figure 3. Exemple : déplacement d’une fourmi, mode recherche (1,2,3,4) et moderetour (5,6,7,8)Pour cette fourmi, le noeud ?ordinateur/machine? est un noeud potentiellement ami.Elle a donc la possibilité de construire un pont vers sa fourmilière mère. Ce choixest réalisé de manière pseudo-aléatoire (voir figure 4). Ce pont devient un arc quepourront emprunter d’autres fourmis et en particulier celles de ?ordinateur/machine? etde ?souris/dispositif ? donc les vecteurs partagent beaucoup de composants. La fourmichoisit donc de l’emprunter et y dépose sa phéromone (9). Elle atteint sa fourmilièremère et y dépose toute l’énergie qu’elle peut porter (10). La fourmi repasse en moderecherche et reprend ses déplacements jusqu’au noeud où elle va mourir et déposeral’énergie qu’elle transportera alors ainsi que l’énergie qu’il a fallu pour la fabriquer.5.4. ?valuation globale, fonction de co?t? la fin de chaque cycle, nous construisons la configuration courante, c’est-à-direque, pour chaque mot, nous prenons le sens correspondant à la fourmilière ayant leplus d’énergie.? la fin de la simulation, le résultat est la configuration qui obtient le plus grandscore. Il s’agit d’une modification par rapport à l’algorithme original présenté dans(Schwab et al., 2011).
116 TAL. Volume 54 – n? 1/2013Phrasesouris#ncontr?ler#vordinateur#nsouris
rongeurcontr?ler
vérifiercontr?ler
dirigerordinateur
machineVVVVVVVV1 69813 47211165V613174211915EEEEEEEEEsouris
dispositifE910E(A)E(A)661818Figure 4. Exemple : mode retour et création de pont (étapes 9 et 10)5.5. Paramètres importantsLes paramètres suivants ont une influence sur certains des phénomènes émergentsque conna?t le système :– la quantité maximale d’énergie qu’un noeud peut porter (Emax) influence la tailledu ou des cycles parcourus par une fourmi. Comme les fourmis ne peuvent pas revenirimmédiatement sur un arc qu’elles viennent de traverser, elles réalisent forcément uncircuit pour revenir à leur fourmilière mère (elles peuvent cependant mourir avant d’yarriver). La taille du circuit dépend du moment où elles décident de revenir, c’est-à-dire de Emax;– l’évaporation de la phéromone entre chaque cycle du système (δ) est l’une desmémoires du système. Plus il y a d’évaporation, moins les traces des fourmis jouentun r?le important. Les chemins interprétatifs doivent être plus rapidement confirméspar de nouvelles fourmis faute de quoi ils sont plus rapidement oubliés par le systèmeglobal ;– la quantité initiale d’énergie sur les noeuds (E0) et la durée de vie des fourmis(ω) influencent le nombre de fourmis qui peuvent être produites et donc la probabilitéde renforcement de certains chemins et circuits plus litigieux pour le système ;– la taille du vecteur d’odeur (Lv) ainsi que la quantité de composants déposéspar une fourmi sur un noeud normal (δV) influencent la mémoire globale du système.Plus le vecteur odeur des noeuds normaux est grand, plus longtemps le souvenir dupassage d’une fourmi sera conservé. La quantité de composants déposés influencecette mémoire de fa?on inverse : plus il y en a, moins le souvenir du passage seralong.
Fourmis et désambigu?sation lexicale 117Par la dynamique du système, ces paramètres sont liés entre eux. Nous avons menédes expériences afin d’estimer au mieux leurs valeurs. Elles sont décrites section 6.3.6. ?valuation pratiqueDans cette section, nous présentons tout d’abord notre corpus de test et les mé-triques utilisées pour évaluer la t?che de désambigu?sation lexicale visée. Nous pré-sentons ensuite les expériences menées et les valeurs des paramètres que nous avonsdéterminées pour chacun des algorithmes. Enfin nous concluons cette partie par unecomparaison des performances de chaque algorithme, à la fois en termes de qualité dela désambigu?sation réalisée et en temps d’exécution.6.1. Corpus d’évaluationNous avons testé notre méthode sur le corpus de la t?che gros grain, une des dix-huit t?ches de la campagne d’évaluation SemEval 2007 (Navigli et al., 2007) danslaquelle les organisateurs fournissent un inventaire de sens plus grossiers que ceuxde WordNet. Pour chaque terme, les sens considérés comme proches (par exemple,<< neige/précipitation >> et << neige/couverture >> ou << porc/animal >> et << porc/viande >>)sont groupés. Les compétiteurs étaient libres de se servir de cet inventaire (sens gros-siers connus a priori) ou non (sens grossiers connus a posteriori). Dans le premiercas, le nombre de choix à faire pour chaque mot est réduit et la t?che moins com-pliquée. Dans le second cas, les sens annotés sont jugés corrects s’ils sont dans lebon groupement ; ce qui revient à accepter un intervalle d’erreur. Notre objectif est detester un système en vue d’une utilisation dans un cadre applicatif réel. L’inventairede sens grossiers n’étant disponible que pour les 2 269 mots utilisés dans le corpusd’évaluation, nous ne l’utilisons donc pas. Dans les expériences présentées ici, nousnous situons ainsi dans un cas de sens connus a posteriori.Le corpus d’évaluation est composé de cinq textes. Les tableaux 3 et 4 présententdiverses informations sur ce corpus.Texte Genre Nombre de Nombre de Nombre de Mots à annoterphrases mots mots à annoter par phrased001 Journalisme 35 951 368 10,51d002 Critique littéraire 41 987 379 9,24d003 Voyage 59 1 311 500 8,47d004 Informatique 76 1 326 677 8,91d005 Biographies 34 802 345 10,15Total 245 5 377 2 269 9,26Tableau 3. Les cinq textes du corpus
118 TAL. Volume 54 – n? 1/2013Nombre Nombre Nombre de Nombre de Nombre dede mots de sens sens moyen mots monosémiques sens moyen(tous mots) (mots polysémiques)d001 368 1 896 5,15 66 6,06d002 379 2 257 5,96 64 6,96d003 500 3 234 6,48 91 7,68d004 677 3 688 5,45 108 6,29d005 345 2 955 8,57 28 9,23Total 2 269 14 030 6,18 357 7,15Tableau 4. Polysémie dans la version a posteriori du corpus6.2. MétriquesNous utilisons quatre métriques pour évaluer la qualité des solutions produites. Ils’agit des mesures standard pour l’évaluation des t?ches de désambigu?sation lexicale(Navigli, 2009) :La première métrique, la Couverture (C), est définie par le quotient du nombrede réponses produites par le nombre de réponses attendues. En d’autres termes, ellereprésente la proportion du texte ayant été désambigu?sée :C =nombre de r?eponses produitesnombre de r?eponses attenduesLa deuxième métrique, la Précision (P ), est définie par le quotient du nombre deréponses correctes produites par le nombre total de réponses produites :P =sens correctement annot?essens annot?esLa troisième métrique, le Rappel (R), est définie par le quotient du nombre deréponses correctes produites par le nombre total de réponses attendues :R =sens correctement annot?essens `a annoterLa dernière métrique, la F-mesure, F1, représente la << moyenne harmonique pon-dérée de la Précision et du Rappel >>. Elle regroupe ainsi P et R dans une seule mesure :F1=2 · P · RP + R
Fourmis et désambigu?sation lexicale 119Il est important de noter que, pour les trois algorithmes étudiés ici (hormis l’algo-rithme exhaustif), la couverture est toujours de 100 %, ce qui veut dire que :P = R = F1puisque F1=2 · P · PP + P=2 · P22 · P= P6.3. Tests et configurations expérimentalesLes objectifs des expériences présentées ici ont été de déterminer les paramètresde chacun des algorithmes en termes de vitesse d’exécution et de qualité des solutionsproduites, puis de les comparer. Pour chacun des algorithmes, nous avons sélectionnédes valeurs de références puis plusieurs expériences de désambigu?sation lexicale ontété conduites avec différentes valeurs de paramètres.Comme le montre le tableau 5, le recuit simulé nécessite trois paramètres, les algo-rithmes génétiques et l’algorithme à colonies de fourmis en nécessitent sept13. Testerl’ensemble des valeurs pour chaque paramètre est évidement impossible car chacunest dans un domaine continu et même parfois ouvert. En revanche, on peut restreindreces domaines à un certain nombre de valeurs. Comme ces paramètres sont intercor-rélés par construction des algorithmes, il faudrait alors tester l’ensemble des combi-naisons, ce qui entra?nerait rapidement une explosion combinatoire. L’estimation desvaleurs des paramètres peut alors être réalisée de plusieurs manières pouvant être ounon associées :– a priori, avant de tester, en se fondant sur la dynamique de chaque algorithme.Par exemple, pour l’algorithme à fourmis, l’énergie maximale que peut porter unefourmi doit être inférieure à sa durée de vie si on veut qu’elle puisse passer en moderetour et pour l’algorithme génétique, le nombre de chromosomes ne doit pas être tropélevé si on ne veut pas que l’exécution soit trop longue ;– empiriquement, tester manuellement (ou plus exactement semi-manuellement)plusieurs combinaisons de paramètres que l’on pense intéressantes puis analyserquelle est l’influence individuelle des paramètres et quels sont les compromis qu’ils’agit de faire ;– par apprentissage automatique, à l’aide d’une méthode d’optimisation comme,par exemple, un algorithme génétique ou un recuit simulé.On le voit, l’ensemble de ces techniques nécessite une certaine supervision. Ils’agit même d’une limitation claire de la supervision absolue pour les algorithmes glo-baux de désambigu?sation lexicale fondée sur des connaissances. Ils ont tous des para-mètres qu’il convient de choisir (taille de fenêtre pour Lesk-contexte ou les méthodesde Sinha et Mihalcea (2007) et de Mihalcea et al. (2004), des paramètres appris auto-matiquement pour Degree (Ponzetto et Navigli, 2010)). Alors que les deux premièresméthodes d’estimation des paramètres ont été utilisées dans (Schwab et al., 2011),nous testons ici la troisième, détaillée dans (Tchechmedjiev et al., 2012).13. Les valeurs de EF, Ea, et θ sont fixées.
120 TAL. Volume 54 – n? 1/20136.4. ParamètresLes paramètres des trois algorithmes sont résumés dans le tableau 5. Pour les four-mis, qui nous intéressent ici, il y a en tout sept paramètres, dont cinq sont discrets(représentés par des entiers) et deux sont continus (représentés par des réels positifsentre zéro et un). Initialement, nous avions déterminé les valeurs de quelques para-mètres en appliquant des changements itératifs et indépendants. Bien entendu, unetelle approche est limitée du fait qu’il s’agit d’une heuristique s’appuyant sur l’hypo-thèse que les paramètres du système sont indépendants. Ce n’est pas le cas de l’al-gorithme à colonies de fourmis comme nous en avons discuté en section 5.5. Vu lenombre de paramètres, même avec une connaissance préalable du fonctionnement del’algorithme, on peut au mieux choisir des intervalles pour les valeurs des paramètresafin de limiter l’explosion combinatoire.De plus, du fait du nombre de paramètres et des intervalles de valeurs, une énu-mération exhaustive n’est pas envisageable. Le calcul du nombre de combinaisons (enprenant des pas de 0,01 pour les paramètres continus) donne : 60 × 60 × 100 × 55 ×25 × 35 × 100 = 17 325 · 108combinaisons ; à cela s’ajoute la nature probabilistedes algorithmes qui requiert au moins 50 à 100 exécutions pour pouvoir calculer siles résultats sont significatifs, on atteint ainsi rapidement 17 325 · 109combinaisons.Même en supposant que l’algorithme n’ait besoin que de 1 seconde pour s’exécuter,la recherche des paramètres prendrait tout de même 549 372 ans.Pour cette raison, nous nous sommes intéressés à l’application d’une méthoded’estimation automatique pour trouver les paramètres optimaux c’est-à-dire un en-semble de valeurs de paramètres qui mène à un F-score aussi haut que possible.Notre méthode utilise un recuit simulé pour lequel chaque élément de la confi-guration correspond à un paramètre. En utilisant le premier texte pour l’apprentissage,les valeurs obtenues après ce processus détaillé dans (Tchechmedjiev et al., 2012) sontω = 10, Ea= 1, Emax= 8, E0= 10, δv= 0, 9, δ = 0, 9, LV= 90.6.5. Comparaison qualitativeNous analysons nos résultats en calculant s’ils sont significatifs par une analyse devariance (ANOVA) (Miller, 1997). Il faut donc vérifier l’hypothèse de normalité. Nousavons ainsi calculé la corrélation entre les quantiles théoriques de la distribution nor-male et les quantiles empiriques. Pour toutes les mesures et tous les algorithmes, nousavions toujours une corrélation d’au moins 0,99, par conséquent le test de Shapiro etWilk (1965) est non significatif. En revanche, le test d’homoscédasticité de Levene(1960) est significatif avec p toujours inférieur à 10-6.Le tableau 6 présente les résultats en fonction du score F1, du temps d’exécutionet du nombre d’évaluations de la mesure de similarité, ainsi que les écarts-types res-pectifs pour les texte 2 à 5. Les résultats sont significatifs deux à deux pour les troisalgorithmes avec p-ajusté inférieur à 0,01. Sachant que le premier texte à été utilisé
Fourmis et désambigu?sation lexicale 121CR M R MN λ ST H1,0 0,15 1 1 000 100,9 0,3 20 500 200,6 0,8 50 200 300,3 1,0 80 50 40(a) Algorithme génétiqueT0ClR IN1 000 1,00 2 000700 0,9 1 000400 0,5 700100 0,3 4001 0,1 100(b) Recuit simuléω EmaxE0LVδ δV20 10 20 150 80 1015 8 15 120 60 3010 6 10 90 40 505 4 5 60 20 702 30 90(c) Colonies de fourmisTableau 5. Valeurs des paramètres testés (valeurs optimales en gras)Algorithme F1( %) σF1T ime(s) σT imeSim. Eval. σ(S.Ev.)1ersens 77,59 N/A N/A N/A N/A N/AA.C.A. 76,41 0,0048 65,46+ 0,199 1 559 049+ 17 482,45S.A. 74,23+ 0,0028 1 436,6+ 167,3 4 405 304+ 50 805,27G.A. 73,98+ 0,0052 4 537,6+ 963,2 137 158 739+ 13 784,43Tableau 6. Comparaisons des scores F1, temps d’exécution et nombre d’évaluationde la mesure de similarité pour les algorithmes (+
p & 0, 01) sur les textes 2 à 5pour la recherche de paramètres, les scores F1présentés ici sont calculés sur les quatreautres textes seulement, afin de supprimer tout biais.De même, la tableau 7 présente les scores F1pour les trois algorithmes avec plu-sieurs stratégies de fusion tardive : un vote majoritaire pour les trois algorithmes ainsiqu’une stratégie de vote par majorité pondéré pour ACA. Nous appliquons également
122 TAL. Volume 54 – n? 1/2013Algorithme F1( %) σF1( %)Vote majoritaire pondéré ACA 77,79+ 0,18Référence S,P,F, 77,59 N/AVote majoritaire ACA 77,50+ 0,48Vote majoritaire SA 75,18+ 0,10Vote majoritaire GA 74,53+ 0,31Tableau 7. Comparaison des scores F1après l’application d’une stratégie de vote(+
p & 0, 01) sur les textes 2 à 5un test post hoc de Tukey HSD (Abdi et Williams, 2010) qui indique la significativitédeux à deux entre tous les algorithmes et types de votes avec un p-ajusté inférieur à0, 01.(a) Exécution normale (b) Vote par majoritéFigure 5. Bo?tes à moustaches des scores F1comparés à la référence du premier sens(pointillé)Les figures 5a et 5b présentent respectivement des bo?tes à moustaches des distri-butions des scores F1pour les trois algorithmes, avec et sans vote, par rapport à laréférence du sens le plus courant.Vis-à-vis du score F1, SA et GA obtiennent des résultats similaires, même si les ré-sultats de SA sont légèrement meilleurs et présentent une variabilité de la distributionde scores inférieure.Pour ACA, les scores sont en moyenne meilleurs de 1,61 % par rapport au SAet 1,76 % meilleur que le GA, avec des variabilités similaires. Les trois algorithmes
Fourmis et désambigu?sation lexicale 123obtiennent tous des résultats inférieurs à la référence du sens le plus fréquent, mêmesi le maximum pour ACA s’en rapproche. Après l’application du vote par majoritésur les résultats dix par dix, pour SA et GA il y a une légère amélioration des scores,respectivement une augmentation de 0,95 % et de 0,61 % avec p & 0, 01. Pour ACA,il y a une amélioration plus importante (p & 0, 01) de 1,09 % (malgré les quelquesdonnées aberrantes représentées par des cercles). ACA a tendance à converger sur dessolutions proches de la référence du premier sens. Après le vote, la distribution estpresque centrée autour de la référence du premier sens en ce qui concerne le score.Quand on ajoute au vote des poids donnés par les valeurs d’énergie de l’algorithmeà colonies de fourmis, le score moyen augmente de 0,29 %, ce qui le place 0,20 %au-dessus de la référence du sens le plus fréquent. De plus, la distribution est bienplus compacte et ne comporte plus de valeurs aberrantes. Cette stratégie ne peut pasêtre utilisée avec les deux autres algorithmes qui ne pondèrent pas les sens d’un mêmemot.En ce qui concerne les temps d’exécution, il y a d’énormes différences entre lesalgorithmes, le plus lent étant l’algorithme génétique, qui, en moyenne prend 1 h 30(± 16 min). Le recuit simulé est bien plus rapide et prend en moyenne 24 min(± 2,8 min), mais reste tout de même bien plus lent que l’algorithme à colonies defourmis qui, en moyenne, converge en 65 s (± 190 ms). Comme l’on pourrait s’yattendre, le nombre d’évaluations de la