Coordonnées

Département d'informatique
Université du Québec à Montréal
CP 8888, Succ. Centre-ville
Montréal (Québec) H3C 3P8
Tél: 514-987-3000, #5516
Bureau: PK-4525
Courriel: blondin_masse[point]alexandre
[arobase]uqam[point]ca

À propos

J'ai complété mon doctorat en mathématiques-informatique sous la supervision des professeurs Srecko Brlek, de l'Université du Québec à Montréal, au Canada, et de Laurent Vuillon, de l'Université de Savoie, en France.

Depuis le 1er août 2014, je suis professeur adjoint à l'Université du Québec à Montréal, au Canada.

Liens utiles

Graphes

[english]

Je travaille présentement au sein d'un projet dans lequel nous nous intéressons à la structure induite par l'espace définitionnel d'un dictionnaire. Ce travail se déroule en collaboration avec Guillaume Chicoisne, Zhe Fu, Philippe Galinier, Yassine Gargouri, Stevan Harnad, Mélodie Lapointe, Martin Lavoie, Marcos Lopes, Mélanie Lord, Odile Marcotte, Olivier Picard, Fatiha Sadat et Philippe Vincent-Lamarre.

Dictionnaires

Nous utilisons une approche basée sur la théorie des graphes pour représenter l'espace définitionnel. Par exemple, considérons le dictionnaire D dont les définitions se trouvent dans le tableau 1.

Word Definition Word Definition
apple red fruit good not bad
bad not good light not dark
banana yellow fruit no not
color light dark not no
dark not light red dark color
edible good tomato red fruit
fruit edible yellow light color

D peut être représenté par un graphe orienté comme l'illustre la figure ci-bas :

A toy dictionary

Un petit dictionnaire représenté par un graphe orienté

Plus précisément, à chaque mot du dictionnaire correspond un sommet et il existe un arc du sommet u vers le sommet v si le mot u se trouve dans la définition du mot v.

Tous les mots n'ont pas la même importance ni la même fréquence dans une langue. Lorsque nous nous concentrons sur les dictionnaires, nous remarquons que certains mots apparaissent dans les définitions mais ce n'est pas toujours le cas. Par exemple, les mots apple, banana et tomato de la figure 1 n'ont aucun successeur. Ils peuvent donc être supprimés puisqu'il est possible de les récupérer en inspectant leur définition. Ce processus peut être répété, de sorte que les mots fruit, red et yellow sont également supprimés, suivi des mots color et edible jusqu'à ce qu'on ne puisse plus retirer aucun mot. Le sous-dictionnaire unique obtenu est appelé noyau d'ancrage (ou simplement noyau) du dictionnaire (voir figure ci-bas).

Noyau d'ancrage du dictionnaire jouet

Noyau d'ancrage du dictionnaire jouet

Le noyau d'ancrage K présente plusieurs caractéristiques notables :

  • Tout mot du dictionnaire complet peut être atteint par définition seulement à partir de K;
  • Tout cycle du dictionnaire appartient au noyau K.
  • Il est unique à chaque dictionnaire;
  • D'un point de vue empirique, les dictionnaires de langue naturelle se réduisent à 10% de leur taille originale lorsqu'on calcule K.

Le lecteur curieux est invité à lire une introduction à ces différents concepts dans [1].

Ensembles d'ancrage de cardinalité minimale

Bien que le noyau d'ancrage ait des propriétés intéressantes, il n'est pas minimal. Il suffit de remarquer que d'autres mots peuvent être supprimés sans compromettre la compréhension des autres mots. Poursuivons l'exemple de la figure 1. On vérifie que seulement trois mots suffisent. En effet, nous pouvons choisir exactement un mot parmi bad and good, un mot parmi no et not et, finalement, un mot parmi dark et light. En fait, il y a exactement huit possibilités. Par exemple, imaginons qu'un individu ne connaisse que les mots bad, not et light. Alors il peut lire les définitions du mot good et l'apprendre (puisqu'il connaît tous les mots de la définition de good) et ainsi de suite, jusqu'à ce que tous les mots du dictionnaire soient appris.

Par conséquent, il est tout à fait pertinent de calculer de tels sous-ensembles de mots suffisamment grands et choisis convenablement. Nous les appelons ensembles d'ancrage. Clairement, le noyau d'ancrage est un ensemble d'ancrage, mais, comme il a été mentionné plus haut, il n'est pas minimal. Nous souhaiterions donc trouver des ensembles d'ancrage de taille minimale. Il a été démontré que ce problème est équivalent au problème de trouver un ou des transversaux de cycles de cardinalité minimale dans les graphes orientés [1], qui s'énonce comme suit :

Problème 1 Soit G un graphe orienté. Le problème du transversal de cycles de cardinalité minimale est le problème de trouver un sous-ensemble de sommets U du graphe G satisfaisant les propriétés suivantes :

  • U est de taille minimale;
  • Si nous supprimons les sommets de U du graphe G ainsi que tous leurs arcs incidents, alors G est acyclique, c'est-à-dire qu'il ne contient aucun cycle.

Malheureusement, ce problème est NP-complet, c'est-à-dire qu'il est très improbable que nous parvenions un jour à trouver un algorithme polynomial permettant de calculer un transversal de cycles de cardinalité minimale pour la classe générale des graphes orientés.

En août 2011, nous avons été en mesure de calculer des ensembles d'ancrage de cardinalité minimale pour deux petits dictionnaires anglais. Nous travaillons actuellement sur un algorithme nous permettant de calculer de tels ensembles pour de plus gros dictionnaires tels que WordNet et le Merriam Webster. Notre stratégie actuelle combine des opérateurs de contraction de graphes présentés par Lin et Jou dans [2] ainsi qu'un programme linéaire adapté au problème du transversal de cycles de cardinalité minimale.

Hiérarchies

En parallèle au calcul d'ensembles d'ancrage de cardinalité minimale, nous sommes intéressés à classifier les mots selon leur importance dans le processus de l'ancrage symbolique. Plus précisément soit G un graphe orienté. Il est possible de construire un nouveau graphe H comme suit :

  • Chaque composante fortement connexe de G est un sommet de H;
  • Soient C et D deux composantes fortements connexes de G. Alors il existe un arc (C,D) dans H s'il existe un sommet u dans C et un sommet v dans D tels que (u,v) est un arc de G.

Il est facile de démontrer que le graphe résultant est acyclique. En d'autres termes, H est le graphe quotient obtenu par rapport à la relation d'équivalence "appartient à la même composante fortement connexe" sur les sommets.

Par conséquent, il est possible d'associer à toute composante fortement connexe (et donc à tout mot du dictionnaire) un entier indiquant son niveau dans l'ordre induit par le graphe quotient acyclique ainsi obtenu. Plus précisément, les mots de niveau 0 sont ceux appartenant au coeur du dictionnaire, les mots de niveau 1 sont ceux n'ayant que des mots de niveau 0 comme prédécesseurs, les mots de niveau 2 sont ceux n'ayant que des mots de niveau 0-1 comme prédécesseurs, etc.

Lorsqu'on étudie différentes variables psycholinguistiques et leur évolution selon la hiérarchie de niveaux ainsi induite, nous remarquons que

  • Au fur et à mesure que le niveau des mots augmente, ceux-ci sont plus facilement représentables par une image et deviennent plus abstraits;
  • Les mots de niveau 0 sont plus fréquents et sont appris plus tôt, alors que les mots de niveaux 1, 2, 3, ... sont moins fréquents et appris plus tard. En revanche, il n'y a aucune différence significative entre les mots de niveaux 1, 2, 3, ...

Le schéma ci-bas résume ces observations :

Variables psycholinguistiques

Évolution des variables psycholinguistiques par rapport à la hiérarchie sur les mots

Le lecteur est référé à [3] pour plus de détails à propos de ces résultats statistiques.

Dans l'année qui suit, nous souhaitons étendre ces différents résultats à d'autres dictionnaires afin de vérifier leur universalité. Nous considérons également d'autres problèmes très intéressants liés à la désambiguïsation définitionnelle et les relations sémantiques. Toute personne intéressée par la question est invitée à me joindre.

Références

[1] (1, 2) A. Blondin Massé, G. Chicoisne, Y. Gargouri, S. Harnad, O. Marcotte et O. Picard. How is meaning grounded in dictionary definitions?, (TextGraphs-3) 3e Atelier sur l'algorithmique de graphes pour les langues naturelles (24 août 2008, Manchester, Royaume-Uni), 8p.
[2] H.-M. Lin et J.-Y. Jou, On computing the minimum feedback vertex set of a directed graph by contraction operations, IEEE Trans. on CAD of Integrated Circuits and Systems 19(3): 295-307, 2000.
[3] O. Picard, A. Blondin Massé, S. Harnad, O. Marcotte, G. Chicoisne et Y. Gargouri. Hierarchies in Dictionary Definition Space, (NIPS-Graphs 2009) Analyse de réseau et d'apprentissage à l'aide de graphes (11 décembre 2009, Whistler, Canada, 9p.