cible

Projet

Les travaux pluridisciplinaires du réseau de recherche DiLan coordonné par Bruno Gaume (CLLE-ERSS & IRIT) portent sur la compréhension et l’exploitation des propriétés caractéristiques des grands graphes de terrain et plus particulièrement des graphes issus de la linguistique, des sciences cognitives et du web.

Les grands graphes de terrains sont les graphes que l’on trouve en pratique, ils sont construits à partir de données issues de différents domaines d’études : l’épidémiologie (contacts, ...), l’économie (échanges, ...), la sociologie (accointances, ...), la linguistique (réseaux sémantiques, ...), la psychologie (associations sémantiques, ...), la biologie (neurones, interactions protéine-protéine, ...), la technologie (internet, ...), ... ou bien encore le graphe du web (hyperliens entre pages).

Plusieurs études récentes montrent un fait remarquable qui est que tous ces graphes, pourtant d’origines si diverses, possèdent des propriétés identiques bien particulières et font partie de la classe des Réseaux Petits Mondes Hiérarchiques (RPMH : faible densité en arcs, moyenne des chemins courts, existence de zones denses en arcs, incidence des sommets en loi de puissance). Un autre fait tout aussi remarquable est que cette classe des RPMH est très petite au regard de l’ensemble des graphes possibles : la probabilité de tirer au hasard parmi l'ensemble des graphes possibles un graphe possédant ces propriétés est très proche de zéro. C'est-à-dire que les graphes auxquels nous avons à faire dans la vraie vie se ressemblent tous par leur structure commune, bien qu’intrinsèquement cette structure soit très rare d’un point de vue probabiliste.

Dans ce cadre le groupe de recherche DiLan a développé une méthode stochastique pour l’étude de la structure des grands graphes de terrain de type RPMH (métrologie, visualisation, navigation, génération automatique, …). Cette méthode qui est implémentée sous la forme d’un atelier logiciel Prox, consiste à transformer un graphe en une chaîne de Markov dont les états sont les sommets du graphe en question. Des particules se baladent aléatoirement de sommets en sommets dans le graphe en empruntant les arcs du graphe. Ce sont les dynamiques des trajectoires des particules qui nous donnent les propriétés structurelles des graphes étudiés.

Cette approche, qui est une forme de connexionnisme structurel, permet de proposer une modélisation géométrique du sens où les RPMH sont non seulement une excellente compression de la forme du sens, mais de plus permettent une navigation et un accès très efficace à l’information, avec une dynamique d’acquisition du général vers le particulier par raffinement (enfant L1), ainsi qu’une excellente robustesse en cas de déficit (aphasie, apprenant L2, …), et un raisonnement à granularité variable ce qui permet de faire chuter la complexité.

L’un des objectifs est par exemple de mieux comprendre comment l’enfant acquiert et reproduit le lexique de sa langue maternelle, de quelques mots, puis quelques centaines, jusqu’à disposer du réseau lexical général d’un adulte.

Les interfaces d’accès à l’information (bases de données, dictionnaires, Web, …) pourront alors être adaptées aux fonctionnalités du cerveau humain, tout comme par le passé ont été adaptés les outils à la morphologie de la main humaine.

DicoSyn

+ d'informations

Illustration par prox
http://prox.irit.fr
Pour expliquer l’esprit de la technologie que nous développons, nous illustrerons notre propos sur les dictionnaires de synonymes. Un dictionnaire de synonymes est un graphe réflexif et symétrique : les sommets du graphe sont les vedettes du dictionnaire, et il existe un arc entre deux sommets A et B si ils sont en relation de synonymie dans ce dictionnaire.

Formes Locales
Dans notre dictionnaire de synonymes, le mot « écorce » a 12 synonymes, c’est-à-dire 13 voisins dans le graphe : « écorce », « apparence », « aspect », « croûte », « dehors », « enveloppe », « peau », « pelure », « robe », « superficie », « vernis », « zeste », « écale ».
Sur ce sommet « écorce », lâchons une particule qui parcourt le réseau de sommet en sommet en empruntant ses arcs pas à pas (quand la particule est sur un sommet A, au pas suivant elle peut atteindre équiprobablement l’un des voisins de A). Au premier pas depuis le sommet « écorce », seuls les 13 voisins de « écorce » ont donc une probabilité non nulle d’être visités par la particule, puis la particule poursuit aléatoirement sa balade pas à pas à travers le réseau. La dynamique de la particule étant entièrement gouvernée par la seule structure du réseau, quelques sommets ont alors beaucoup plus de chance d’être visités que d’autres. Sélectionnons par exemple un diamètre de 50 sommets les plus probablement visités par la particule durant ses premiers pas quand elle débute sa balade depuis le sommet « écorce ». Chacun des 50 sommets ainsi sélectionnés est alors placé dans l’espace 3D en fonction de la dynamique qu’a la particule quand elle y débute sa balade. Si un sommet A est proche d’un sommet B dans l’espace de projection c’est que la dynamique de la balade débutant par A est semblable à la dynamique de la balade débutant par B, et c’est la topologie du réseau dans sa globalité qui structure la dynamique des trajectoires de la particule à travers les arcs du réseau.

En observant cette forme qui est une sorte de sculpture conceptuelle de « écorce », on peut identifier trois zones sémantiques ainsi géométrisées qui sont le reflet de la structure topologique du réseau des synonymes autour de « écorce » :

En faisant de même pour « maison » on peut par exemple visualiser la structure conceptuelle de « maison » :

Forme Global
Ajoutons à notre graphe un sommet Joker et connectons le à tous les autres. Sur ce sommet Joker, lâchons une particule qui parcourt le réseau de sommet en sommet en empruntant ses arcs pas à pas (quand la particule est sur un sommet A, au pas suivant elle peut atteindre équiprobablement l’un des voisins de A). Tout sommet du réseau a donc une probabilité non nulle d’être visité en un pas par la particule depuis le sommet Joker, puis la particule poursuit aléatoirement sa balade pas à pas à travers le réseau. La dynamique de la particule étant entièrement gouvernée par la seule structure du réseau, quelques sommets ont alors beaucoup plus de chance d’être visités que d’autres. En effet certains sommets sont au cœur de zones denses en arcs qui créent une confluence des trajectoires vers ces sommets. Sélectionnons par exemple un diamètre de 150 sommets les plus probablement visités par la particule durant ses premiers pas quand elle débute sa balade depuis le sommet Joker.
Chacun des 150 sommets ainsi sélectionnés est alors placé dans l’espace 3D en fonction de la dynamique qu’a la particule quand elle y débute sa balade. Si un sommet A est proche d’un sommet B dans l’espace de projection c’est que la dynamique de la balade débutant par A est semblable à la dynamique de la balade débutant par B, et c’est la topologie du réseau dans sa globalité qui structure la dynamique des trajectoires de la particule à travers les arcs du réseau. Le réseau sémantique ainsi géométrisé est donc le reflet de la structure topologique du réseau dans sa globalité.
Pour afficher la carte global d’un graphe il suffit de cliquer sur global : le graphe en cours est alors afficher depuis le sommet Joker. De plus seuls les sommets qui sont présents dans la carte locale en cours seront affichés dans la carte globale : ceci permet ainsi de contextualiser une carte locale dans la carte globale du graphe dont est extraite la carte locale en cours.

Des sommets virtuels
Dans notre dictionnaire de synonymes il n’existe pas de mots X ayant pour seuls synonymes X1=« monter » et X2=« descendre ». Aussi afin d’observer la structure qu’aurait un tel mot X, il suffit de formuler la requête [monter;descendre]. Ceci permet par exemple de voir que le mot charnière entre « monter » et « descendre » est le mot « sauter ». En faisant de même avec [commencer;finir], on peut voir que le mot charnière entre « commencer» et « finir» est le mot « partir ». Avec notre approche il est possible d’observer la structure qu’aurait un sommet X ayant n voisins dans un réseau en formulant la requête : [X1;X2;…;Xn].
Bien entendu les n sommets X1;X2;…;Xn doivent exister dans le réseaux observé.

Identifier les zones denses en arcs par élagage
Notre approche permet d’identifier les zones denses en arcs d’une carte en construisant des classes de sommets fortement connectés (ou clusters). Pour cela nous proposons un élagage des arcs les plus longs. Dans nos visualisation, si un sommet A est proche d’un sommet B c’est que la dynamique de la balade débutant par A est semblable à la dynamique de la balade débutant par B. La longueur d’un arc A↦B nous indique donc le niveau de similitude entre les dynamiques de ces deux balades :
- Si l’arc A↦B est court c’est que les dynamiques de ces deux balades sont très semblables ;
- Si l’arc A↦B est long c’est que les dynamiques de ces deux balade sont différentes ;
En élaguant les arcs les plus longs le graphe se déconnecte, créant ainsi des classes de sommets : Si deux sommets A et B appartiennent à une même classe, c’est parce que la dynamique de la balade débutant par A est semblable à la dynamique de la balade débutant par B. Par exemple en élaguant 40% des arcs les plus longs autour de « causer » on peut ainsi voir que le verbe « causer » a deux sens principaux : « parler » et « provoquer ». Si l’on continue l’élagage à 50% on descend à un niveau de granularité plus fin de « causer » qui se décompose alors en trois sens principaux : « provoquer », « converser », « papoter » :

provoquer, créer, occasionner, produire, susciter, déclencher, déterminer, ...

Insérer un lien vers une carte dans document
En cliquant sur Lien, on peut copier le lien affiché dans un document ou une page web pour créer un lien vers la carte en cours.