Projet SHERPA

Thèmes de recherche

Connaissances descriptives: objets, types et contraintes
Connaissances méthodologiques et résolution coopérative de problèmes
Connaissances fonctionnelles
1. Simulation et contraintes dans les bases de connaissances
Connaissances terminologiques et textuelles
Aides à la construction de bases de connaissances
Dynamique et confrontation de bases de connaissances
Granularité dans la représentation du temps et de l'espace
Modélisation de cartes génomiques
Recherche d'informations sur le Web

Connaissances descriptives: objets, types et contraintes

Le modèle et système Troeps

Le modèle Troeps [Mariño& 90, Mariño 93, Sherpa 95] est à la fois le support et le produit de plusieurs travaux fondamentaux au sein du projet Sherpa. Il succède à Shirka. Le développement d'une version opérationnelle d'un système de gestion de bases de connaissances mettant en oeuvre ce modèle est donc crucial pour le projet en ce qu'elle permet d'expérimenter, de valider et de capitaliser les résultats de recherche. Le modèle Troeps peut être brièvement présenté en rappelant ses caractéristiques les plus originales:

concepts/classes: la distinction entre concepts et classes permet de séparer les aspects ontologiques (création et structure des objets) de leurs aspects taxonomiques (conditions d'appartenance) [Euzenat 93b]. Cette séparation a le mérite de réconcilier modèles de connaissance à objets (qui traitent des aspects taxonomiques) et langages de programmation à objets (qui traitent des aspects ontologiques);
points de vue: la séparation concept/classe réduit l'importance des classes et permet d'envisager qu'un objet soit attaché à des classes différentes. Ainsi, chaque concept peut être vu sous des points de vue différents qui déterminent des taxonomies de classes différentes;
classification: la classification, dans les modèles de connaissances à objets, consiste à trouver, au sein d'une taxonomie de classes, les places possibles d'un objet ou d'une classe d'objets. L'intérêt de ce mécanisme réside principalement dans sa faculté à éliminer les positions impossibles pour un objet. L'algorithme de classification prend en compte l'existence de ces points de vue et des passerelles qui les relient: de l'appartenance de l'instance à une classe dans un point de vue, il est possible de conclure à son appartenance à une classe d'un autre point de vue si ces deux classes sont reliées [Mariño 91, Mariño 93].

Une version opérationnelle de Troeps est disponible ici.

Au delà de cette implémentation, l'étude des rapports entre langages de programmation à objets et représentations de connaissances a conduit, dans le cadre du projet soutenu par le GREG, à une proposition d'implémentation du modèle Troeps sur PowerClasses [Euzenat 94c], le langage à objets associé à Talk et proposé par Ilog.

Ce modèle est le cadre de travaux fondamentaux sur la représentation de connaissances, plus particulièrement sur les types, les contraintes et les systèmes classificatoires. Il est le support des travaux sur le construction coopérative de bases de connaissance.

Types

L'adjonction d'un système de types à un modèle de connaissances à objets comme Troeps présente de nombreux avantages liés à l'extensibilité, à la connexion avec des modules procéduraux, ainsi qu'à l'efficacité et à la sécurité de mécanismes d'inférence tels que la classification. Le système de types développé, appelé Metéo [Capponi 94a, 95b] , comprend deux niveaux de typage:

D'une part, des classes de types (appelés C-types) représentent des structures de données particulières (spécification d'ensembles de valeurs et d'opérations applicables à ces valeurs). De nouveaux C-types, tels que matrice ou séquence génomique, peuvent être intégrés par l'utilisateur; ils seront considérés de la même façon que les C-types primitifs comme entier. Un C-type permet la description d'opérations de manipulation de ses valeurs, ainsi que la spécification d'opérations de manipulation de ses parties: c'est au niveau du C-type qu'est décrite, par exemple, la relation de sous-typage qui tient compte des propriétés de ses valeurs. De même, c'est au niveau du C-type que peut être décrite la mesure de similarité entre deux valeurs.
D'autre part, à chaque C-type est associé un ensemble de delta-types qui représentent des parties de l'ensemble caractérisé par le C-type. Les delta-types sont organisés en treillis par la relation de sous-typage traduisant l'inclusion ensembliste. Par exemple, dans le cas du C-type entier, les delta-types sont des unions d'intervalles fermés de valeurs entières; la relation de sous-typage dérive de la relation d'inclusion entre unions d'intervalles. Le système de types considère de façon générique les opérations des C-types et les utilise pour l'interface entre le modèle de connaissances et la base de types. Il est constitué principalement d'une opération de typage (comprenant une phase de normalisation), d'une opération de test de sous-typage, d'opérations génériques telles que l'union, la disjonction ou l'intersection de types. Ces opérations génériques utilisent les opérations particulières de chaque C-type.

Les primitives offertes par le système de types sont directement utilisables par les mécanismes d'instanciation et d'inférence du modèle de connaissances, tels que le filtrage, la classification de classe ou d'instance, la gestion de contraintes ou encore l'activation d'attachements procéduraux.

L'existence même de Metéo permet de reconsidérer le rôle tenu par un langage de représentation des connaissances. Par son extensibilité, Metéo autorise l'intégration de nouvelles structures de données, sur lesquelles une batterie d'opérations ensemblistes sera automatiquement définie. C'était le besoin de ces opérations qui incitait l'utilisateur à définir ces structures de données en termes du langage de représentation, bien que ce dernier ne soit pas adapté à l'intégration de données procédurales. Ces structures peuvent maintenant être définies dans Metéo, indépendamment du modèle de connaissances.

Contraintes

Afin de donner plus d'expressivité aux modèles de connaissance à objets, un système de représentation et de satisfaction de contraintes a été développé [Gensel& 94, Gensel 95b]. Ce système permet d'exprimer des "problèmes de satisfaction de contraintes" (CSP), dont les variables sont des attributs d'objets généralisés aux chemins d'attributs, les domaines sont un sous-ensemble particulier des types (domaines finis, entiers, réels...) et les contraintes sont prises dans une bibliothèque de contraintes (arithmétiques, booléennes, ensemblistes...). Outre son intégration naturelle dans un modèle à objets, le système présente l'originalité de proposer une représentation des domaines à l'aide d'unions d'intervalles. Par ailleurs, il traite les chemins d'attributs à valeur construite (c'est-à-dire sous forme d'ensembles ou de listes) en unissant ou en emboîtant ces valeurs. La maintenance des contraintes numériques exploite les principes de l'arithmétique des intervalles. La résolution des contraintes est basée sur un algorithme de "forward-checking" paramétrable pour les domaines finis et sur une méthode de fractionnement dynamique pour les domaines infinis ou continus.

Le système construit est capable d'interagir avec le module de types Metéo (en particulier pour manipuler des types externes).

Systèmes classificatoires

Un système classificatoire propose une définition abstraite des facultés de classification d'individus (objets, valeurs, tuples) ou de catégories (classes, types, contraintes) sans se préoccuper de leur structure [Euzenat 93a]. Il ne considère que deux ordres partiels organisant les catégories exprimables et les catégories exprimées. Dans ce cadre, les objets s'interprètent comme des individus, les catégories comme des ensembles d'individus et les ordres partiels comme l'inclusion ensembliste. Autour de cette abstraction, les opérations de produit, d'appauvrissement et de restriction ont été introduites [Euzenat 94a]; elles permettent de construire de nouveaux systèmes classificatoires à partir de systèmes préexistants. Les algorithmes de classification ne dépendant que des propriétés propres des systèmes classificatoires peuvent alors être conçus. De tels algorithmes ont été définis et implémentés pour diverses propriétés (exclusivité, exhaustivité...) des systèmes classificatoires considérés.

Ainsi, en montrant que les systèmes de types et de contraintes présentés précédemment sont des systèmes classificatoires, il est possible d'en construire de plus complexes (correspondant par exemple aux concepts de Troeps). Dans ce cadre, les algorithmes de classification de classes et d'objets sont définis sans tenir compte des particularités de ces systèmes. C'est sur cette base qu'est développé Troeps [Capponi& 95].

Insertion dans un treillis

Dans un système de gestion de types, la vitesse de calcul de la relation de sous-typage, ainsi que des opérations de sous-type le plus étendu et de sur-type le plus restreint, est un facteur important pour l'efficacité globale du système. Cela conduit souvent à la structuration de l'ensemble des types existants dans une base de connaissances sous forme de treillis de types. La structure de treillis permet, en effet, si elle est bien exploitée, un accès direct aux résultats des opérations ci-dessus. En revanche, lors d'une modification dans l'ensemble des types gérés, se résumant le plus souvent en une insertion d'un nouveau type, il est obligatoire, au risque de perdre les propriétés de treillis, de répercuter ces modifications sur la structure de treillis de manière appropriée.
Ce problème du maintient incrémental de la structure d'un treillis, qu'il soit de types ou non, revient à rechercher la complétion de Dedekind-McNeille de l'ordre obtenu en insérant de manière directe le nouvel élément dans le treillis. Un algorithme de construction de cette complétion a été conçu [Valtchev 97b]. Il se fonde sur des propriétés structurelles de l'ordre intermédiaire, en particulier sur la correspondance bijective entre un ensemble d'éléments du treillis initial liés au nouvel élément et l'ensemble des éléments artificiels nécessaires à la restitution de la structure de treillis. En effet, l'insertion directe de l'élément en question peut résulter en la violation de l'unicité de certaines bornes supérieures et inférieures d'éléments du treillis qui sont comparables au nouvel élément. Ainsi, la stratégie de complétion revient à rechercher ces distorsions locales (une seule borne est considérée à la fois) dans la structure du treillis et de les "réparer" en insérant les éléments artificiels nécessaires, à raison d'un par distorsion.
À l'heure actuelle, c'est le seul algorithme qui résout ce genre de problème, c'est-à- dire le maintient incrémental de la structure de treillis, de manière directe et en minimisant le coût des complétions. Les autres algorithmes qui peuvent être utilisés pour compléter un ordre partiel vers un treillis sont soit plus coûteux en temps de calcul, soit produisent une structure nettement plus large.

Connaissances méthodologiques et résolution coopérative de problèmes

La résolution d'un problème revient très souvent à choisir des modules algorithmiques, puis à enchaîner leurs exécutions. Les modèles de tâches permettent de décrire, d'une part les modules en termes des objets qu'ils acceptent en entrée et produisent en sortie, d'autre part des enchaînements de ces modules (stratégies) en vue de la résolution d'une classe de problèmes. La résolution proprement dite d'un problème consiste alors à exécuter la tâche associée en la décomposant récursivement et de façon opportuniste (c'est-à-dire en tenant compte des résultats intermédiaires obtenus) en sous-tâches plus élémentaires jusqu'à l'exécution directe de procédures. À chaque pas de décomposition, le problème courant, représenté par une tâche, est tout d'abord caractérisé par sa classification dans une hiérarchie de tâches de même catégorie. Il en résulte une décomposition particulière en sous-problèmes et le cycle caractérisation-décomposition se répète sur chacun de ces sous-problèmes.
Ces principes de représentation et d'exploitation de connaissances méthodologiques sont étudiés depuis plusieurs années au sein du projet Sherpa. Ils ont en particulier permis le développement des environnements de résolution de problèmes Scarp [Willamowski 94b] et PowerTask (en collaboration avec Ilog dans le cadre du projet soutenu par le Greg). Ils continuent de faire l'objet de recherches en particulier sur l'ajout de stratégies et la résolution distribuée.

Ajout de stratégies de résolution

Ajouter une stratégie de résolution, qui permette de résoudre un nouveau type de problème, se fait par la construction d'un nouveau schéma (ou plan) de décomposition de tâches en sous-tâches, à moins que l'on ne sache réutiliser un plan existant. Trois niveaux de difficulté croissante peuvent être distingués:

réutilisation de plans: remplacer les données du plan connu par celles du nouveau problème en conservant la structure existante;
adaptation de plans: créer une nouvelle méthode de résolution par composition et réutilisation de sous-plans existants;
modification de plans: adaptation de plans existants et aide à la création des chaînons manquants afin de permettre un enchaînement cohérent des sous-plans utilisés.

Les principales difficultés rencontrées concernent alors la recherche et l'appariement des plans. Rechercher pour le plan à construire un ou plusieurs plans appropriés ne peut se faire sans une évaluation préalable des ressemblances et des dissemblances entre le problème à résoudre et les différents plans existants. Il faut donc rechercher une mesure de similarité appropriée au formalisme de résolution de problèmes utilisé, en identifiant une similarité de contenu, une similarité de structure et une similarité de résultat.

Dans le but de comparer ces différentes résolutions d'une même tâche, nous avons défini un modèle de représentation canonique des graphes de décomposition et de spécialisation de tâches en utilisant les structures de E-graphes (graphes orientés sans circuit ni sommet isolé possédant un seul sommet d'entrée et un seul de sortie). Des opérations de concaténation et d'alternance ont été définies, les propriétés d'associativité et de distributivité de la concaténation par rapport à l'alternance ont été vérifiées [Ferreira Da Cunha 96]. Ce travail s'est concrétisé par l'implémentation d'un module de recherche de formes canoniques pour les différents modèles de tâches développés au sein du projet. Ce module est associé à une évaluation des dissemblances : ainsi, les différences des deux stratégies comparées sont identifiées et des modifications sont proposées à l'utilisateur afin de lui permettre une unification éventuelle des deux stratégies.

Reconnaissance d'intentions

La reconnaissance d'intentions s'inscrit dans le cadre d'une reconnaissance de plans, lorsqu'une résolution faite par l'utilisateur n'a pas abouti et que ce dernier est "perdu". Le mécanisme de reconnaissance d'intentions doit alors proposer à l'utilisateur un raisonnement et une solution à son problème en adaptant le comportement du système pour qu'il tienne compte des essais et recherches que l'utilisateur a déjà effectués. À partir des théories de Kautz et Allen, qui consistent à déterminer la classe des plus petits ensembles de plans parmi ceux qui contiennent les actions observées, un algorithme a été proposé [Mestre 95, Mestre& 95]. Cet algorithme original a permis de tirer parti de la représentation de connaissances des processus de résolution par graphe de tâches, ainsi que de la notion de but.

Fondamentalement, le problème de la reconnaissance d'intentions est donc un problème de mise en évidence de similarités entre réseaux de tâches : celui construit par l'utilisateur et ceux connus dans la base de tâches. Trois critères de similarité ont été dégagés [Collin 94]: une similarité portant sur le contenu des stratégies, une similarité portant sur leur structure et une similarité portant sur leur résultat. La première est évaluée par application d'une méthode numérique/symbolique de mesure de similarité entre deux graphes de tâches. La seconde l'est en effectuant un test d'isomorphisme (au moyen d'un algorithme de recherche arborescente informée de type division-évaluation -- "branch and bound") sur des graphes de décomposition re-étiquetés. Enfin, la troisième se définit par extension de la notion de subsomption au cas des plans et des actions élémentaires qui les composent. Cette différenciation ne doit cependant pas masquer le caractère fortement corrélé de ces trois composantes, ni l'intérêt de les unifier en une unique mesure de similarité.

Dialogue coopératif

L'utilisation d'un environnement coopératif d'aide à la résolution de problèmes par des utilisateurs non informaticiens, comme des médecins, ne peut être complètement effective que par la mise en place d'une interface spécialisée qui permette une coopération efficace entre le système et l'utilisateur. Dans le domaine du diagnostic médical, une étude du processus de coopération système-utilisateur a permis de préciser les nécessités d'interface pour plusieurs catégories identifiées d'utilisateurs. Un ensemble de propositions pour la réalisation d'une interface spécialisée a été élaboré et a défini clairement les fonctionnalités automatisables, les dialogues devant être mis en oeuvre avec l'utilisateur, ainsi que les contrôles et les aides à fournir lors d'une résolution. Outre la définition d'interfaces de dialogue, l'insertion d'un ensemble d'images représentant des planches anatomiques a permis de faciliter l'acquisition des données, mais aussi la présentation synthétique des résultats [Morneau 96].

Sémantique des tâches décomposables et spécialisables

Une sémantique opérationnelle de ce modèle de tâches a été établie [Crampé 94]. Elle permet de concilier un modèle de tâches aussi expressif que Scarp avec une sélection rationnelle des tâches à exécuter telle que celle utilisée dans Tram [Chaillot 93]. La sélection rationnelle permet d'arbitrer, pour le même but à atteindre et dans une situation donnée, entre l'exécution immédiate d'une tâche déjà sélectionnée et une recherche coûteuse de tâches plus utiles au sens de la théorie de la décision. Le choix est fondé sur l'espérance de gain d'utilité entre la méthode courante et des méthodes plus difficiles d'accès. Un moteur de tâches mettant en oeuvre ce modèle a été méta-programmé en Prolog.

Ce travail a permis de mettre en évidence des aspects (utilité mono-critère et indépendance de l'environnement) qui permettent de compiler statiquement le programme d'évaluation des tâches au lieu d'évaluer dynamiquement l'espérance.

Environnement distribué de résolution de problèmes

Une version répartie de l'environnement PowerTask a été réalisée [Parmentier& 98]: elle permet d'exécuter les méthodes associées aux tâches élémentaires sur les sites mêmes où elles sont développées et maintenues, alors que les capacités de suivi, par l'utilisateur, du processus de résolution de problèmes restent identiques. Cette maquette est actuellement réétudiée en collaboration avec le projet SIRAC afin de faire l'objet d'une version diffusable auprès de nos partenaires biologistes.

La mise en oeuvre de l'exécution répartie nécessite la définition de mécanismes de localisation des compétences et l'élaboration de processus de synchronisation permettant l'interaction entre les tâches réparties sur les différents sites. Ces deux points entraînent une modification du modèle de tâches (par exemple, par l'adjonction de descripteurs pour la localisation des tâches distantes), et la création de nouveaux opérateurs (tels que l'opérateur de parallélisation) et des mécanismes de synchronisation élémentaire qui lui sont nécessaires. L'utilisation de cet environnement réparti requiert, en plus des modifications structurelles et opérationnelles déjà citées, une analyse des nouvelles possibilités et contraintes amenées par la répartition. Par exemple, la prise en compte de contraintes temporelles et de disponibilité des ressources matérielles et logicielles lors du processus de résolution est nécessaire afin d'assurer un déroulement satisfaisant des résolutions. Les stratégies de résolution devront aussi tenir compte de la puissance de calcul des machines, de leur charge de travail et de la disponibilité des compétences et des données.
Ceci permettra d'évaluer le coût et le gain apportés par une méthode envisagée dans un processus de résolution. Cette évaluation se fera à partir d'une analyse multi-critères permettant de mesurer la performance de la méthode, basée sur sa précision, son temps d'exécution, la place mémoire utilisée, la disponibilité des données nécessaires, la nécessité d'interaction avec l'utilisateur, etc.

Connaissances fonctionnelles

Dans le cadre d'une convention avec l'université Pierre Mendès-France de Grenoble nous abordons le problème de l'introduction de mécanismes de simulation dans un système de représentation des connaissances par objets. L'objectif applicatif est d'abord de concevoir et de réaliser un environnement pour la construction et la simulation de modèles combinant connaissances qualitatives (objets) et quantitatives (systèmes d'équations et/ou contraintes numériques). À plus long terme, ces outils et techniques pourront être utilisés pour représenter les connaissances de comportement en biologie moléculaire, en particulier sur les interactions géniques impliquées dans le développement, comme celles traitées par la base de connaissance Knife).

Simulation et contraintes dans les bases de connaissances

Afin de modéliser et simuler des systèmes complexes, il apparaît souvent profitable d'introduire des connaissances symboliques qui rendent explicites les hypothèses et conditions de validité du modèle numérique adopté. Le problème est ici abordé sous l'angle de la représentation de connaissances par objets qui permet la coexistence de connaissances numériques (équations et/ou contraintes) et symboliques (objets, contraintes symboliques). Les premiers travaux ont porté sur la définition d'un langage de modélisation permettant d'intégrer connaissances symboliques et numériques, ainsi que sur la conception de mécanismes de résolution adaptés. Les résultats obtenus ont été implantés dans le logiciel AMIA et validés sur des applications complexes. Il est aussi souvent intéressant dans ce contexte de mener des simulations sous contraintes pour déterminer, par exemple, comment atteindre un objectif donné. La simulation apparaît alors comme un cas particulier des problèmes de satisfaction de contraintes. Les travaux en cours portent sur l'élaboration de mécanismes de résolution alliant des techniques de simulation et de satisfaction de contraintes. En particulier, une représentation et des techniques de résolution des problèmes de satisfaction de contraintes ensemblistes sont étudiées.

Connaissances terminologiques et textuelles

La construction d'une base de connaissances est très clairement un processus de modélisation. Le processus incrémental et coopératif de construction d'une base de connaissances scientifiques, par exemple en biologie moléculaire, soulève le problème de l'intelligibilité du contenu de la base pour un spécialiste qui n'a pas participé à son élaboration [Rechenmann 96]. L'utilisation d'une base par des personnes autres que celles qui ont directement participé à sa conception requiert donc que soient explicités les choix et les hypothèses de modélisation. S'agissant de représenter des connaissances d'un domaine scientifique tel que la biologie moléculaire, ces choix et ces hypothèses reposent pour beaucoup sur la littérature spécialisée. Il est donc nécessaire de relier les connaissances formalisées sous la forme d'objets aux documents justifiant leur pertinence scientifique ainsi que leur modélisation.

Trois types d'information nécessaires à la compréhension des connaissances représentées ont été identifiés: définition de la terminologie, justification de la validité scientifique des connaissances et explication des choix de modélisation effectués. Pour que ces trois types d'information soient accessibles à partir des connaissances formalisées, nous proposons un environnement informatique composé de quatre bases: une base de connaissances, une base de modélisation, une base de textes et une base terminologique. Cette dernière, SiLex [Lemaire 96], contient la définition de l'ensemble du vocabulaire utilisé dans l'environnement et constitue l'interface entre le vocabulaire de l'utilisateur et le contenu de la base de connaissances et de la base de textes. Il aide ainsi l'utilisateur à sélectionner les termes pertinents pour atteindre le contenu de la base de connaissances ou un sous-ensemble de documents correspondant à une interrogation précise sur une connaissance formalisée. Par ailleurs, SiLex permet une modélisation plus homogène, car elle favorise un accord entre les concepteurs d'une communauté sur l'acception des termes utilisés.

Ce modèle a été intégré dans le logiciel Troeps.

Aides à la construction de bases de connaissances

La classification conceptuelle est une opération qui a pour but de découvrir les connaissances implicites qui sont présentes au sein d'un ensemble de données en y détectant les similarités ou les dissemblances. En sortie, les méthodes de classification conceptuelle organisent et condensent l'information qui était présente dans les données initiales sous la forme d'une structure qui peut être soit une partition, soit une hiérarchie de classes. En pratique, la classification est une opération qui apporte une aide efficace dans l'analyse d'un problème ou la modélisation d'un domaine. Cette problématique générale conduit à explorer les quatre axes de recherche suivants:

définition et mise en oeuvre de mesures de similarité dans les langages à objets;
construction incrémentale de bases de connaissances par formation de concepts;
opérationalisation des systèmes à base de connaissances;
production d'explications pour la conception de bases de connaissances.

Similarité et représentation par objets

La classification conceptuelle peut être réalisée en utilisant les algorithmes développés dans le cadre de l'analyse des données. Cependant, ces méthodes s'appuient sur l'usage de matrices de similarité qui servent à quantifier les ressemblances et les différences qui existent entre les informations. Lorsqu'on travaille avec des modèles à objets, tout le problème est alors de définir des mesures de ressemblance qui soient capables de prendre en compte les différentes informations modélisées dans les objets et qui sont de nature plus complexe que les informations classiquement traitées en analyse des données. Entre autres, la présence de relations entraîne des traitements particuliers. Les travaux du projet sur ce thème visent à réexprimer la mesure de similarité comme un problème de résolution d'un système d'équations linéaires [Bisson 94c, Bisson 95], ce qui permet d'évaluer simultanément les similarités structurelles (relations) et locales (attributs) entre les instances, sans qu'il soit nécessaire d'explorer l'espace des appariements possibles entre les instances.

Toujours sur ce thème, une nouvelle mesure de dissimilarité (l'inverse de la similarité) s'appliquant de manière générale aux taxonomies a été proposée [Valtchev& 95, & 96]. Cette mesure (dite topologique) est fondée sur le plus court chemin entre deux classes au sein de la taxonomie. Elle apporte une assise aux algorithmes de construction de taxonomies. S'appliquant généralement aux systèmes classificatoires, elle concerne indifféremment tous les types de données incorporables dans Troeps, elle y est parfaitement intégrée.

Enfin, si Troeps dispose de mécanismes de classification fondés sur la structure des objets, il manque de mécanismes capables de construire la hiérarchie des classes et des sous-classes (le graphe de spécialisation) à partir d'instances. C'est ce que proposent les algorithmes d'analyse de données et d'apprentissage automatique. Le système T-tree [Euzenat 93c] est destiné à intégrer de tels algorithmes au sein de Troeps en profitant des avantages de ce dernier (représentation de plusieurs taxonomies grâce aux points de vue et leur comparaison à l'aide d'un algorithme d'inférence de passerelles).

Classification conceptuelle incrémentale

Certains travaux en "formation de concepts" ont défini des méthodes de classification "incrémentale". Dans ces méthodes, la hiérarchie des classes est restructurée grâce à des opérateurs chaque fois qu'une nouvelle information est soumise au système. Ainsi, à chaque étape, la nouvelle donnée est uniquement comparée avec les classes déjà construites, ce qui diminue le nombre de comparaisons et la complexité algorithmique du problème. Malheureusement, ces systèmes sont incapables de travailler avec des données contenant des informations relationnelles.

Un mécanisme général de classification incrémental a été proposé [Senneron 95] qui permet de combiner (1) l'avantage de travailler avec des langages de représentation des connaissances de haut niveau basés sur les modélisations à objets, et (2) l'avantage d'avoir des mécanismes de classification incrémentaux capables de traiter des masses importantes de données. Ce travail se poursuit dans le but d'introduire de nouveaux opérateurs de restructuration et en étudiant l'impact de l'ordre de présentation des données.

Opérationalisation de bases de connaissances

La construction d'une base de connaissances destinée à la résolution de problèmes a été reformulée comme la transformation progressive d'une base de connaissances n'ayant que des objectifs de modélisation et ce à l'aide d'un ensemble d'opérateurs tels que la sélection d'attributs, la modification de classes, la restructuration de la hiérarchie, etc. Cette transformation est guidée à l'aide d'un ensemble de problèmes déjà résolus, le but global étant de trouver une transformation qui optimise les performances prédictives de la base de résolution [Mancuso 95]. À terme, grâce à ce type d'outil, on peut espérer avoir une meilleure capitalisation des connaissances en étant capable de réutiliser des bases de connaissances déjà existantes. Ainsi, à partir d'une même modélisation, il devient possible de dériver plusieurs bases de connaissances différentes, chacune servant à résoudre un type de problème spécifique.

Explicabilité en catégorisation

La classification conceptuelle (ou catégorisation) est un mécanisme permettant de construire automatiquement une hiérarchie de classes à partir d'un ensemble caractéristique d'instances du domaine que l'on cherche à modéliser. Cependant, la qualité de la modélisation issue d'un système de classification dépend totalement de la pertinence des données initiales. Le processus de classification est constitué de deux étapes, qui sont la constitution du jeu de données et la construction de la hiérarchie. En pratique, il est donc nécessaire d'effectuer plusieurs itérations de type "essais/erreurs" au cours desquelles, en fonction des résultats obtenus, les données initiales sont révisées par l'utilisateur (ajout d'instances, modification du langage de description des instances...).
Les outils d'apprentissage symbolique automatique existants fonctionnent souvent comme des "boîtes noires". Lorsque les sorties du système sont partiellement incomplètes, incohérentes, voire inintelligibles, l'utilisateur néophyte a beaucoup de mal à voir quelles sont les informations qu'il doit modifier en entrée du système pour améliorer les sorties.
Ce travail vise ainsi à coupler le système de classification avec un système explicatif capable d'aider l'utilisateur à diagnostiquer les erreurs et à formuler les corrections à effectuer. Il est donc apparu nécessaire de répondre aux trois questions suivantes [Bisson 94b]:

quelles sont les attentes de l'utilisateur vis-à-vis du système?
quelles sont les explications à fournir pour aider l'utilisateur dans sa tâche?
quels sont les mécanismes d'apprentissage qui facilitent l'élaboration de ces explications?

Le principe est d'intégrer dans le système d'apprentissage un mécanisme de classification conceptuelle qui serve de médiateur entre les entrées et les sorties. Le schéma d'apprentissage se décompose alors en deux phases classification: le système d'apprentissage interprète et structure les informations fournies par l'utilisateur, discrimination: à partir de cette structuration, le système construit la base de résolution de problèmes. Il devient alors possible d'expliquer à des utilisateurs néophytes les résultats de chaque étape en fonction des informations obtenues lors des étapes précédentes. L'utilisateur peut "remonter" pas-à-pas des sorties qu'il souhaite modifier vers les éléments en entrée qui ont engendré les structures fautives et y apporter des corrections.

Cet axe de recherche vise donc à définir des méthodes de catégorisation dans lesquelles le système est capable d'expliquer ses choix à l'utilisateur, et ainsi de l'aider non seulement à construire la hiérarchie de classes, mais également à définir quelles sont les informations nécessaires pour y parvenir. Ces exigences ont conduit à la réalisation d'un système d'explication EILP [Gabriel 96a, b], qui est couplé au système de catégorisation KBG déjà existant. Dans EILP, il est non seulement possible de justifier les résultats de chaque étape de la construction de la hiérarchie de classes en fonction des informations fournies par l'utilisateur, mais aussi de lui proposer des modifications et de prédire l'impact qu'elles auront sur la base de connaissances finale.

Dynamique et confrontation de bases de connaissances

Le développement d'une base de connaissances est un processus incrémental et coopératif, au sens où plusieurs personnes sont susceptibles d'y contribuer. Nous étudions donc les moyens qui permettent de gérer ce processus de conception, d'une part en proposant un protocole qui régit les interactions entre la base et les personnes qui y contribuent, d'autre part en étudiant les mécanismes de révision de la base de connaissances.

Gestion de la dynamique

La gestion de la dynamique a été étudiée, au sein du projet Sherpa, sous plusieurs aspects complémentaires: dynamique des instances, dynamique des classes et dynamique des inférences.

Dynamique des instances: Le mécanisme de classification, en particulier dans sa version incrémentale, traite le premier aspect: la classe de rattachement d'une instance change quand les valeurs de ses attributs évoluent. Il est donc nécessaire de maintenir le lien entre l'appartenance à la classe et les valeurs d'attributs. Par ailleurs, les travaux dont l'objectif est d'assister la construction d'une base à partir d'instances caractéristiques du domaine à l'aide d'un mécanisme de catégorisation modifient les définitions de classes comme l'attachement des instances qu'il est nécessaire de maintenir.
Dynamique des classes: La possibilité pour une classe d'être modifiée oblige à garantir le comportement du système à la suite de modifications des classes d'objets, telles que l'ajout ou le déplacement de classes dans le graphe de spécialisation, l'ajout, la suppression ou la modification de contraintes sur les attributs. Des mécanismes d'aide à la définition et au positionnement de nouvelles classes dans une taxonomie ont été proposés [Capponi& 93]. Ils s'appuient maintenant sur le formalisme de types élaboré pour Troeps.
Dynamique des inférences: Enfin, maintenir une base dans un état cohérent vis-à-vis des inférences relève des travaux sur les TMS [Euzenat& 87], ATMS et CP-TMS [Euzenat 90, 91b]. Ce travail est actuellement relayé par celui sur la satisfaction de contraintes et celui sur la révision.

Tous ces aspects de la dynamique d'une base de connaissances sont pris en compte au sein du développement de Troeps.

Protocole de construction coopérative

Si les taxonomies peuvent être construites, de manière automatique ou assistée, à partir des objets sur lesquels elles portent, elles peuvent aussi être construites "à la main" par des spécialistes du domaine. Dans les domaines scientifiques qu'aborde le projet Sherpa, la construction d'une base de connaissances implique plusieurs intervenants. La construction incrémentale et coopérative d'une base de connaissances (ou d'une mémoire technique) fait intervenir simultanément plusieurs personnes sur des sites distants. Chacune d'entre elles est susceptible de soumettre des descriptions de classes d'objets inter-reliées pour les intégrer dans la base en cours de construction. Les échanges entre la base et les sites qui l'alimentent doivent être gérés afin d'assurer que le contenu de la base de connaissances croisse de manière consensuelle.
Afin de les aider dans la construction de leur base, une architecture et un protocole permettant de créer des bases "consensuelles" ont été proposés [Euzenat 95a]. Le protocole de coopération Co4, conçu au sein du projet Sherpa, permet à plusieurs utilisateurs de soumettre à une base de connaissances consensuelle des éléments de connaissance. Il s'appuie sur la métaphore de la soumission d'un article à un journal scientifique : les contributions sont distribuées à l'ensemble des souscripteurs de la base qui doivent répondre s'ils l'acceptent, la rejettent ou proposent des modifications. Le protocole gère la collecte des réponses et son résultat. Il gère de la même manière l'arrivée d'un nouveau souscripteur et permet récursivement à une base consensuelle de souscrire à une autre base. Le protocole termine, est vivace (live), équitable (fair) et implémente bien le consensus.
Ce protocole a aussi été décrit dans le langage de spécification de protocoles LOTOS par Charles Pecheur. Il a ainsi pu être testé à l'aide des outils de vérification de programmes développés à l'Inria Rhône-Alpes (action Vasy). La phase de test du protocole décrit en LOTOS a d'une part permis de corriger certains problèmes dans sa spécification et d'autre part de s'assurer de son bon fonctionnement. Plus de détails techniques sont disponibles en http://co4.inrialpes.fr

Un tel schéma de construction coopérative devrait permettre de développer des bases de connaissances scientifiques, mais aussi des mémoires techniques. Il fera ainsi l'objet d'expérimentations dans le cadre de SToRIA oú il est utilisé en conjonction avec Troeps.

Révision

La mise en oeuvre complète d'un système de construction coopératif de base de connaissance nécessite d'apporter une aide aux utilisateurs dans la gestion des conflits qui peuvent apparaître lorsqu'ils modifient la base. En effet, si leur modification entre en contradiction avec une connaissance déjà présente dans la base mais qu'ils n'ont pas introduite, il est important de pouvoir les aider à résoudre le conflit le mieux possible [Crampé& 96a]. C'est par exemple le cas si un objet est inséré dans la base avec une valeur d'attribut en dehors du domaine autorisé. L'approche de la révision de base de connaissances a été jusqu'à présent développée principalement dans un cadre logique. Cette approche peut être adaptée afin de prendre en compte la structuration supplémentaire apportée dans les représentations de connaissances par objets. Ainsi dans le cas de Troeps, il faut:

localiser (rapidement) (toutes) les sources d'une inconsistance;
ordonner ces sources en fonction de leur nature;
trouver une notion de préférence de modèles (de la base de connaissances) qui rende compte de cet ordre.

Le but est de présenter les révisions (les plus) acceptables aux utilisateurs afin qu'ils puissent les discuter et/ou les effectuer. Ainsi, dans l'exemple précédent, on pourra suggérer à l'utilisateur de modifier la valeur d'attribut, ou de ranger l'objet dans une classe plus appropriée (grâce à la classification) ou encore de modifier les domaines des classes.
Dans un premier temps, un langage d'objets a été formellement défini. Il a été doté d'une sémantique et d'un système déductif syntaxique correct et complet par rapport à cette sémantique [Crampé& 96b, 96c]. De plus, l'inconsistance a été caractérisée syntaxiquement, ce qui permet de la détecter en se basant sur les propriétés de localité du langage. Contrairement aux langages logiques classiques, l'inconsistance ne se propage pas à l'ensemble de la base, elle ne permet pas de tout déduire.
Dans un second temps, une notion de base révisée a été introduite; elle satisfait les postulats classiques de la révision, en particulier la minimalité, principe selon lequel il faut perdre le moins de connaissances possible. La minimalité peut de plus s'interpréter intuitivement selon la relation d'ordre entre les classes. Cependant, une minimalité basée sur l'inclusion ensembliste n'est pas un critère suffisant pour obtenir une base unique. Un algorithme est donc mis en oeuvre pour obtenir toutes les bases révisées minimales suite à un ajout inconsistant; il est interactif afin de maîtriser la complexité inhérente à la révision : le concepteur choisit à chaque étape du processus de révision parmi les différentes possibilités de modification de la base.
La contribution de ce travail devrait s'appliquer généralement à la correction d'erreurs dans tous les langages (de représentation ou de programmation) par objets fortement typés.

Les opérateurs de révision sont en cours d'intégration dans le système Troeps.

Granularité dans la représentation du temps et de l'espace

Dans le contexte de la représentation de connaissance abordée par le projet Sherpa, on s'intéresse à la notion d'approximation d'une représentation par une autre et à la granularité spatio-temporelle en particulier. Le changement de granularité est causé par la vision plus ou moins grossière d'une situation donnée. Ceci peut poser problème lorsque les représentations de la même situation sous deux granularités différentes sont confrontées.En effet, la description de certaines entités (certains évènements ou certaines régions de l'espace) ne sont plus prises en compte, cela modifie la topologie du domaine (deux entités qui ne se touchaient pas, peuvent venir en contact si l'espace entre eux vient à disparaître). La représentation grossière et la représentation précise de la situation ne sont alors plus forcement compatibles.

Un opérateur de changement de granularité permet de se rendre compte des perceptions possibles d'une situation sous une granularité différente. Les travaux sur la granularité des représentations qualitatives ont tout d'abord permis de proposer de tels opérateurs pour le temps (algèbre d'intervalles et algèbre de points) [Euzenat 93e], puis l'espace (intervalles en dimension quelconque et RCC-8) [Euzenat 94b]. Ils ont ensuite été prouvés unique par une approche plus algébrique [Euzenat 95c, d]. Dans le même temps, on s'est intéressé à la définition d'opérations permettant de construire des opérateurs de changement de granularité à partir d'opérateurs préexistants [Euzenat 95e].

Un certain nombre de problèmes intéressants restent à considérer dans ce travail : on peut d'abord penser à donner une interprétation numérique de cette granularité qualitative (en passant par les "multi-layered metric logics" d'Angelo Montanari). On peut s'intéresser aux propriétés générales (existence, unicité...) de la granularité dans un espace d'algèbres de relations (de manière à trouver les frontières). Enfin dans un cadre applicatif, les problèmes de généralisation cartographique (dans un cadre quantitatif) ou de génération de documents multimédia à différents niveaux de généralité méritent d'être abordés.

Modélisation de cartes génomiques

La modélisation de cartes génomiques pose de nombreux problèmes de représentation et de traitement. Les premiers proviennent de l'existence de plusieurs descriptions des entités du génome, les seconds de la complexité algorithmique de la construction des cartes, ajoutée à la nécessité de pouvoir traiter les incohérences issues des expériences. Dans un premier temps, la notion de carte a été précisée grâce à une formalisation qui spécifie comment sont construites les cartes génomiques et quelles sont les relations entre les entités qui y apparaissent. Dans un second temps, un algorithme de construction de cartes à partir de la description des relations entre les entités qui la constituent a été proposé, en s'appuyant sur des techniques de raisonnement temporel [Schmeltzer 95b].

Recherche d'informations sur le Web

Les moteurs de recherche courants, tels AltaVista ou Lycos, utilisent le plus souvent comme filtre d'accès un ensemble de mots-clés liés entre eux par des connecteurs logiques. Or, cette recherche par identité de motif conduit souvent, soit à l'obtention d'informations trop générales, soit à aucune information si le motif est trop spécifique. Conscients de ces limites, certains sites mettent en place des mécanismes d'aide principalement basés sur l'utilisation de thésaurus générés statiquement (Semio) ou dynamiquement (Lives topics d'AltaVista). Si ces mécanismes simplifient la formulation des requêtes, ils souffrent d'un excès de généralité se traduisant par des propositions non pertinentes.
Pour améliorer l'efficacité de la recherche, il semble nécessaire de l'articuler autour d'une base de connaissances définissant un ensemble prédéfini de critères normalisés et typés. L'avantage d'une telle approche est double. D'une part, la normalisation des critères de recherche permet de guider efficacement l'utilisateur dans la formulation de sa requête par l'intermédiaire de questionnaires dont le contenu peut changer dynamiquement au fur et à mesure de la saisie des informations. D'autre part, en explicitant la sémantique des critères par le typage, il devient possible d'effectuer des recherches plus souples basées sur la similarité des informations et non plus leur stricte égalité.
Le système FUSIN (FUzzy Search withIN sight) satisfait ces différents objectifs en offrant des outils permettant de construire et d'exploiter, parallèlement aux documents existants sur un site web, un modèle assurant une indexation bi- directionnelle entre ces documents et la base de connaissances. La recherche d'informations repose entièrement sur les mesures de similarité qui ont été mis au point au sein de l'activité de catégorisation. Le champ d'application de FUSIN concerne principalement les sites devant disposer de mécanismes d'interrogation souples et s'adressant à des publics ayant des niveaux d'expertise très divers; les sites de support produit/client en sont un bon exemple. Ce système sera expérimenté dans le cadre du réseau EMG-net.

https://www.inrialpes.fr/sherpa/rech-fra.html

Last update 15-DEC-2021