Séminaire des doctorants

Thème : Fournir un modèle de représentation et de communication agent, simple mais puissant leur permettant d'apprendre en étant dit (learning- bybeing-told). Gérer la représentation de l'interlocuteur dans une conversation entre agents.

Problème : Gérer l'adaptabilité des agents dans une société, assurer le transfert de la connaissance et adapter les agents vers une vue et une utilisation orientée service, telle qu'elle est nécessaire aujourd'hui sur le Web et demain sur le GRID.

Contributions : Le travail présenté est issu du modèle STROBE de Stefano Cerri et fourni un modèle de représentation des agents : les agents comme des interpréteurs de langages. Ainsi qu'un modèle de communication qui permet de modifier dynamiquement ces interpréteurs.

Intérêts :

• L'apprentissage est réalisé aux 3 niveaux : donnée, contrôle et interpréteur. Ce dernier étant ce que nous appelons l'apprentissage au méta-niveau. Un exemple « jouet » de dialogue professeur - élève illustre comment un agent peut apprendre à un autre un nouveau performatif.
• Permettre la spécification dynamique d'un problème, c'est-à-dire spécifier et exécuter un programme en même temps par le dialogue. Un exemple de scénario e-commerce illustre l'intérêt pour la génération dynamique de service.

Tous les chercheurs en informatique rencontreront un jour ou l'autre dans leur vie (reprenez-moi si je me trompe) un problème d'algorithmique de graphes. D'autres chercheurs se dévouent pour leur faciliter la tâche en écrivant des algorithmes (ou des heuristiques) efficaces pour les plus jolis problèmes qu'on leur soumet. Au LIRMM, c'est la mission que s'est donnée l'équipe Algorithmique Combinatoire du projet VAG.

J'aurai le plaisir de vous en parler jeudi ("vous" étant les doctorant, mais aussi les ex-doctorants cordialement invités). Mon but n'est pas de vous présenter une liste exhaustive des problèmes rencontrés, ni des techniques d'écriture d'algorithmes (ces listes étant potentiellement infinies) mais juste de vous donner un exemple (comme par hasard très proche de mon sujet de thèse). Il s'agit du problème de l'orientation transitive. Je vous expliquerai comment une résolution efficace du problème est en relation avec une bonne connaissance des structures du graphe (condition assez fréquente pour pouvoir écrire de bons algorithmes). En l'occurrence, la structure est la décomposition modulaire. Ce sera l'occasion de dire un mot des décompositions de graphe en général et de celle-ci en particulier. Puis on verra un outil algorithmique, l'affinage de partitions, qui permet d'écrire l'algorithme efficace.

Le travail présenté aborde le thème de l'émergence multi-niveaux. On peut définir le concept d'émergence de la façon suivante : apparition inattendue, au sien d'un système, d'un phénomène qui n'avait pas semblé inhérent aux différentes parties de ce système. La notion d'émergence est capitale dans l'étude des systèmes complexes, qu'ils soient biologiques, physiques, informationnels, logiciels, etc. Dans la nature, ces systèmes sont majoritairement caractérisés par une structure multi-échelle issue d'émergences multiples. Cela se traduit par l'apparition d'une émergence au sein d'un système dont les parties sont elles-mêmes le produit d'émergences passées.

Que ce soit dans une approche systèmes multi-agents pour caractériser la nature, le fonctionnement et les résultats des interactions entre agents, dans une approche vie artificielle, pour comprendre les mécanismes intrinsèques des structures vivantes ou encore dans une approche systèmes auto-organisés pour interpréter les organisations inhérentes aux interdépendances des parties d'un système ; la compréhension du phénomène de l'émergence multiple est fondamentale pour l'étude de l'organisation et de la structuration des systèmes.

Nous présentons à cet effet, un modèle générique de système multi-agents qui assure l'émergence multiple de structures. Ce modèle met en ½uvre des agents réactifs au comportement récursif. Nous avons réalisé plusieurs simulations de ce système, simulations que nous présenterons et analyserons afin d'exhiber l'intérêt d'un tel travail pour l'étude du phénomène émergent et la modélisation de systèmes complexes comme les systèmes multi-agents.

Le pavage par dominos est un problème classique parmi les problèmes de pavage. Il consiste a décider si un polyomino (une union simplement connexe de cubes unités à sommets à coordonnées entières) est pavable par des dominos (une union de deux cubes adjacents par face) et le cas écheant à fournir un pavage du polyomino considéré.

En 1992, E. Bougé et M. Cosnard ont démontré, que les polyominos possèdant des propriétés symétriques sont pavables si et seulement s'ils sont équilibrés. Plus précisément, ils ont prouvé qu'un polyomino trapézoïdal, (un empilement de rectangles de taille décroissante) est pavable si et seulement s'il est équilibré (i.e. il contient autant de faces noires que de faces blanches pour une coloration type échiquier de Z^2).

Dans cet exposé, je donnerais une nouvelle et courte preuve de ce résultat puis je généraliserai ces résultats aux dimensions supérieures.

Avec l'évolution des capacités des ordinateurs et des réseaux de communication un nouvel enjeu apparaît : comment partager et exploiter au mieux cette formidable quantité de ressources ? Le modèle client / serveur qui régit actuellement l'Internet présente de sérieuses limitations face aux problématiques du passage à l'échelle, de la répartition de charge et de la mise en commun de ressources. Le modèle pair à pair (P2P) a été proposé pour pallier ces limitations. Dans un système P2P chaque participant est à la fois consommateur (client) et producteur (serveur) de ressources et de services. Les applications des systèmes P2P sont le calcul distribué, le stockage distribué ou encore le partage de données/connaissances et de services. Les systèmes P2P posent de nombreux défis à relever : le passage à l'échelle, l'(auto-)organisation décentralisée, la gestion de l'hétérogénéité, ...

Le sujet abordé dans cette présentation est le partage de données à grande échelle au travers d'un système P2P : on parle de PDMS (Peer Data Management System). Les pionniers dans ce domaine sont maintenant devenus célèbres (Napster, Gnutella, KaZaa, ...), mais nous ne pouvons pas encore parler de réel partage de données puisqu'ils se limitent à du simple échange de fichiers et des recherches par mots-clés. Notre objectif est de développer un système de médiation de données afin de manipuler de façon transparente des données hétérogènes dans un réseau de type P2P. En particulier, il faut être capable de traiter des requêtes émises sur un tel réseau, de manière à fournir aux usagers un accès uniforme aux sources de données. Les besoins pour un PDMS sont à l'intersection des systèmes dynamiques et distribués, et des bases de données. Les problématiques introduites par les PDMS par rapport aux SGBD classiques sont : la localisation des données, la médiation dynamique (intégration de schémas et réécriture de requêtes), la volatilité des sources et la taille du système. Dans cet exposé je présenterai l'architecture fonctionnelle XPeer que nous proposons comme support pour la réalisation de PDMS.

La quantité de données accessibles sous format électronique au travers du web croît de jour en jour et ce d'une manière considérable. Ces données sont généralement distribuées, hétérogènes et multiformes. De nombreux problèmes se posent pour les utilisateurs qui veulent les exploiter. Un des problèmes soulevés par la communauté informatique est d'associer une description sémantique des données véhiculées par le web afin de les rendre compréhensibles par des utilisateurs humains et "faciles" à traiter par des entités informatiques. Actuellement, il existe deux approches. La première consiste à utiliser des langages de représentation de conaissances pour spécifier le sens des concepts d'une part, et d'autre part, des techniques de raisonnements peuvent s'appliquer sur des données en format RDF. L'inconvénient de cette dernière approche est que la grande masse de données sur le web est en format XML. La deuxième approche est celle adoptée dans la communauté bases de données est qui jusqu'ici était très centrée sur la structuration des données au détriment des liens sémantiques inter-sources.

Le sujet de thèse traite les aspects construction et restructuration de schéma de médiation dans le cadre de l'architecture de médiation à la large échelle basée sur le concept de super-peer. L'objectif est de pouvoir élaborer l'ontologie ou le schéma global partagé par tous les peers du système; maintenir cette ontologie en fonction des modifications du réseau (arrivée et départ des peers) et enfin faire évoluer les schémas de médiation lorsque un seuil défini sera atteint.

L'homme tente de faire faire à un ordinateur du résumé de textes depuis plus de 40 ans et il est encore loin de parvenir à une totale satisfaction. Nombreuses et variées fûrent les façons d'aborder ce problème. Ces différentes approches étant basées sur des techniques du domaine du TALN ou empruntant celles d'autres domaines comme la recherche ou extraction d'information. Cet exposé consiste principalement en un tour d'horizon sur le résumé automatique et se termine par l'orientation que j'ai choisie et les objectifs que je me suis fixés. Les principaux facteurs qui caractérisent les différents types de résumés seront tout d'abord exposé : la nature des données sources, des données cibles et pour quel usage le résumé est effectué. Je présenterai ensuite les différentes approches utilisées pour faire du résumé: du résumé dit par extraction jusqu'à celui dit par reformulation. Certaines techniques utilisées dans ces deux types de résumé seront alors étudiées. Puis je préciserai avantages et inconvénients pour chaque type d'approche. Enfin, je terminerai mon exposé en discutant des options que j'ai choisies et de l'utilité, pour le résumé automatique, des outils de l'équipe TAL qui sont à ma disposition.

Je présenterai la notion d'algorithme dynamique, illustrée par 2 exemples, puis introduirai l'outil de représentation de graphes qu'est la décomposition modulaire. A l'appui de cette introduction, nous aborderons le problème du maintient dynamique de la décomposition modulaire d'un graphe. Ceci sera fait dans 2 cas : d'abord sur les cographes orientés pour lesquels un algorithme entièrement dynamique de maintient de la décomposition modulaire sera présenté. Puis, nous essaierons de jauger la difficulté du problème sur les graphes non orientés quelconques.

L'analyse du graphe formé par les pages web et les liens hypertextes qui les relient, communément appelé graphe du Web, a permis d'améliorer la performance des moteurs de recherche actuels. Ainsi, lancé en 1998, le moteur de recherche Google classe les pages grâce à la combinaison de plusieurs facteurs dont le principal porte le nom de PageRank. Ce dernier est un indice numérique qui utilise le nombre de liens pointant sur les pages web.

Afin de mieux comprendre la structure complexe du Web, nous présentons un modèle d'extraction et de visualisation des communautés dans le graphe du Web. Il s'inspire du modèle PageRank, les pages étant modélisées comme des particules massives et les liens hypertextes comme des forces gravitationnelles.

Une Ontologie est un langage formel utilisé pour représenter de façon adéquate les connaissances pour raisonner dans un environnement donné. Pour palier à la difficulté de réviser une ontologie inadéquate sanctionnée par des informations paradoxales, nous proposons un cadre conceptuel de construction interactive d'ontologies respectant la logique de la découverte scientifique.

J'illustrerai comment un agent apprenant est capable d'aider un humain à localiser les sources de paradoxes dans une ontologie, afin de guider sa révision, en présentant le jeu d'Eleusis qui sert de démonstrateur pour les outils que nous mettons au point.

Les compilateurs majoritairement utilisés sont basés sur un principe de compilation séparée, alors que la plupart des optimisations des langages à objets nécessitent une connaissance globale du programme, en particulier l'analyse de type et les techniques d'implémentation de la liaison tardive. Les deux approches ont leurs avantages et leurs inconvénients et nous proposons d'intégrer des techniques d'optimisation globales, en particulier l'analyse de types et la coloration, dans un cadre de compilation séparée. Le code généré est décoré par des balises et complété par des informations sur le schéma des classes et la circulation des types dans leurs méthodes. Une phase globale précédant l'édition de liens effectue les optimisations globales à partir de ces dernières informations et fait les substitutions nécessaires dans le code généré par la phase locale.

La visualisation d'information est un processus aidant à l'analyse de grandes quantités de données. Ce processus, cyclique, inclut la structuration des données, le dessin et la navigation. Les domaines d'applications sont nombreux : génie logiciel, réseaux sociaux, biologie... Nos travaux portent sur ces trois domaines. Toutefois un effort particulier a été mené pour fournir un outil de visualisation aux biologistes. En effet l'apparition de nouvelles méthodes expérimentales en biologie (puces à ADN, cribles double hybrides...) fournit des masses de données nécessitant l'utilisation d'outils statistiques et... visuels. Nous avons donc développé un outil BIOTAG dédié à l'analyse des données d'expression des gênes. Cette application utilise un algorithme semi-automatique de dessin des voies métaboliques. Les réseaux métaboliques sont des graphes trés bien connus. Ce qui n'est pas le cas de tous les graphes apparaissant en biologie. La visualisation doit alors aider à répondre aux questions : Quels éléments regrouper pour en déduire des fonctions biologiques ? Quels sont les réactions essentielles au fonctionnement du réseau ? Cette visualisation exploratoire nous a amené à développer un outil de clustering hiérarchique basé sur la propriété Small World de ces réseaux. Cette méthode définit une métrique sur les arêtes qui permet l'identification des clusters du graphe. Nous l'avons appliqué, avec succés, à des graphes du génie logiciel.

Mon exposé évoquera la biologie, mais pas de panique, n'étant pas biologiste je n'entrerai pas dans les détails !

Le problème de l'alignement multiple est un problème central en bio-informatique. Le problème LCS qui consiste à trouver le plus long sous-mot commun à tous les mots d'un langage fini X est l'un de ses cas particuliers les plus étudiés.

Dans mon exposé, je considèrerai trois variantes du problème LCS notées respectivement LCUS, LCCS et LCUCS suivant que les mots du langage X pris en entrée sont non-orientés, circulaires ou circulaires et non-orientés. Je généraliserai à ces trois problèmes les résultats connus sur l'approximabilité et la complexité paramétrique du problème LCS.

Dans le cadre de la représentation du sens en TALN, nous développons actuellement un système d'analyse des aspects thématiques des textes et de désambiguïsation lexicale basée sur les vecteurs conceptuels. Ces vecteurs visent à représenter un ensemble d'idées associées à tout segment textuel. À partir de ce modèle, nous avons posé des hypothèses sur la construction des vecteurs. Dans cet exposé, nous montrons comment ces hypothèses, ainsi que des considérations techniques comme la possibilité de distribuer les tâches à effectuer ou la modularité, nous ont amenées à adopter une architecture multi-agents. Chaque agent possède un certain nombre de compétences, une mémoire qui lui est propre et peut interagir avec son environnement (les autres agents). Nous montrons comment le système global s'enrichit de l'apport des agents qui eux-même s'enrichissent du système (Phénomène de la double boucle). Pour finir, nous présentons les agents déjà implémentés et un exemple de leur collaboration.