L'Agence nationale de la recherche Des projets pour la science

Translate this page in english

Chaires d’excellence (CHEX)
Edition 2012


CEDAR


Contraintes et Evènements Dirigeant l’Automatisation du Raisonnement

Le projet CEDAR consite en une étude experimentale de représentation de connaissances qui soit une alternative aux méthodes prévalentes à ce jour.
Les deux défis les plus importants pour le Web Sémantique sont le passage à l'échelle et la distribution. Le passage à l'échelle pour un système de base de connaissance orienté « web » bien conçu le rend capable de traiter des volumes croissants de connaissances sans dégradation inacceptable de performance. La distribution est aussi complexe puisque cela signifie qu'on doit pouvoir traiter efficacement et sans faille des connaissances résidant sur tout le réseau dans des conditions « réelles ».

Nous sommes convaincus que la solution aux deux défis est offerte par le formalisme de contraintes de graphes à traits à sortes ordonnées
Les objectifs du projet CEDAR sont : (1) développer, implémenter, et tester une approche par contraintes à la représentation des connaissances et le raisonnement automatique, où toutes les connaissances sont exprimées dans une représentation graphique universelle telle que RDF (ou Linked Data), de la même façon que les données le sont par des tables dans le modèle relationnel ; (2) rendre un tel système de raisonnement par contraintes capable de prendre en compte des contraintes temporelles pour le calcul évènementiel utilisant des sources multiples de connaissances distribuées où l'environnement évolue en temps réel (par ex., des moniteurs adaptifs pour la qualité de service, le maintien de l'évolution de bases de connaissances, la reconciliation des connaissances distribuées, etc.). Atteindre ces objectifs constituera une contribution dans un domaine essentiel, avec des résultats originaux et innovants dont le potentiel est important - la possibilité d'un Web sémantique supportant la montée en charge sur des bases de connaissances distribuées - et cela, grâce à une base formelle différente de la majorité des poursuites similaires, et testée sur des benchmarks réalistes.

Contraintes de graphes ordo-sortés à traits pour la représentation des connaissances et le raisonnement avec passage à l'échelle et distribution
Notre but est de fournir une preuve tangible et testable que l'approche de la représentation des connaissances par la logique de contraintes de graphes OSF peut : (1) être exprimée dans les standards émergeant de formats de représentation de connaissances par triplets RDF - et utilisée à la fois pour exprimer et satisfaire des contraintes structurelles et temporelles ; (2) au travers de tests et de simulations, expérimenter avec des architectures pour la gestion et l'accès à des connaissances RDF distribuées qui passent à l'échelle ; (3) utiliser, tester, et démontrer un moteur de raisonnement OSF sur des données RDF réelles exprimant les connaissances selon l'architecture que se sera avérée la plus performante dans les benchmarks de simulations pour des bases distribuées et passant à l'échelle. Le travail proposé dans ce projet doit innover dans deux enjeux essentiels concernant la technologie de représentation d'ontologies par triplets : le raisonnement et la gestion des connaissances. (A) L'innovation clef du projet est que sa technologie de raisonnement ontologique est la logique de contraintes de graphes OSF plutôt que la logique de description qui caractérise la famille de systèmes de représentation de connaissances de type OWL qui forme la majorité des formalismes existants. L'originalité des graphes OSF est qu'ils se représentent directement en RDF constituant de contraintes formelles qui peuvent s'interprèter comme des contrainte structurelles ou temporelles. (B) L'autre contribution essentielle de ce projet est la gestion de grandes quantités de données distribuées sous forme de triplets RDF. Cette partie expérimentera avec l'organisation et l'optimisation de bas niveau, par test et simulation, de bases de connaissance en format RDF sur lesquelles un moteur de raisonnement OSF peut être utilisé. La mesure de succès du projet sera de démontrer que le résultat de (A) peuvent être mis en œuvre sur des benchmarks réels grâce aux résultats de (B).

Résultats

Ce que nous proposons se caractérise comme une synthèse de plusieurs travaux antérieurs en intelligence artificielle, en représentation des connaissances, et en programmation logique par contraintes, où cette dernière technologie est le lien pour le maintien et l'accès aux connaissances distribuées dans le nouveau contexte des médias interconnectées. L'adoption de RDF comme un standard par le W3C pour le Web Sémantique pour exprimer les connaissances sous forme de graphe se trouve en parfaite adéquation avec, et justifie, ce que nous proposons. En effet, la formalisation de la représentation par graphes OSF utilise exactement une représentation par triplet pour la résolution de contraintes. L'approche que nous défendons est de voir de tels graphes commes des contraintes simples et faciles à satisfaire - et ce, essentiellement pour des raisons pratiques. Cela permet de représenter et de manipuler des objets dont la structure est un graphe ordo-sortée à traits de manière simple, efficace, et pratique. Ce formalisme est un rendu formel de base des idées informelles essentielles derrière les réseaux sémantiques des années 80 et 90. L'aspect le plus intéressant et que cela permet un rendu immédiate de ce genre de graphes en contraintes efficacement solvables. Le raisonement sur des structures complexes de très grande taille s'effectue ainsi en interprétant de tels graphes comme des ensembles conjonctifs ou disjonctifs de contraintes élémentaires. De plus, is se trouve que ces contraintes élémentaires correspondent naturellement à une représentation par triplets telle que proposée par RDF (proposé par le W3C comme format universel pour representer toutes les connaissances du Web Sémantique sur Internet), ainsi que les héritiers de RDF tels que RDF Schéma, RDFa, LinkedData, SKOS, etc., ... En termes plus simples, la technologie OSF fournit un ensemble d'outils formels et pratiques appropriés pour le Web Sémantique.

Perspectives

Nous sommes encouragés et réconfortés par les premiers résultats que nous avons obtenus. Les perspectives de nos travaux à ce stade sont d'étendre l'expressivité des connaissances que nous pouvons exprimer. Le prochain enjeu est de traiter des structures complexes et non juste des taxonomies. Cela se fera par l'addition de traits et d'agrégats pour permettre de représenter et de manipuler des concepts dotés de « rôles ». Un effort ultérieur sera de nous intéresser au raisonement sur les évènements en utilisant des techniques de contraintes d'ordonnancement. Quant à la partie expérimentale, nous devons maintenant considérer des configurations de Hadoop/MapReduce pour un plus grand nombre de nœuds de distribution capable de traiter des requêtes incrémentales. L'objectif ultime est de consolider toutes les parties du projet, chacune contribuant à améliorer le reste.

Productions scientifiques et brevets

Nous avons comparé FaCT++, HermiT, Pellet, TrOWL, Racerpro, SnoRocket, et notre prototype sur de très grosses taxonomies. Notre système est parmi les meilleurs pour la classification de concepts, et de plusieurs ordres de grandeur plus efficace pour la réponse aux requêtes. Ceci a été publié à ISWC 2013. Nous avons aussi mis à disposition sur notre site web un outil public pour que ce soit vérifiable par quiconque. Nous développons maintenant un raisonneur OSF complet pour des bases de triplets RDF. Pour la gestion de requêtes sur des bases de triplets RDF de très grande taille, utilisant le benchmark de l'université Lehigh, nous pouvons maintenant générer jusqu'à 1,6 milliards de triplets. Nous avons expérimenté avec 2 systèmes de gestion de triplets : SHARD (réparant plusieurs de ses failles), et Jena HBASE. Nous faisons maintenant le même travail avec RDFPig, Jena TDB, and Virtuoso. Nous avons aussi entrepris l'implémentation de notre propre système de gestion de triplets.

Partenaires

LIRIS Laboratoire d'Informatique en Image et Systèmes d'Information

Aide de l'ANR 500 760 euros
Début et durée du projet scientifique janvier 2013 - 24 mois

Résumé de soumission

Le projet CEDAR consiste en une étude formelle systématique et une
expérimentation pratique d'une approche de la répresentation de
connaissances offrant une alternative aux méthodes prévalentes jusqu'à
présent. Les deux défis les plus importants qui sont encore à relever
pour que les promesses du Web Sémantique se réalisent sont le passage à
l'échelle et la gestion de la distribution des connaissances. Le
problème du passage à l'échelle est qu'un système puisse faire face à la
montée en charge de la quantité de connaissances à gérer sans trop
souffrir de dégradation de performances. Quant au deuxième défi — gestion
de la distribution — il est tout aussi complexe car il exige de gérer
efficacement et automatiquement des connaissances provenant de multiples
sources sur le Net dans des conditions “réelles” (fautes de caches,
gestion de connexions non fiables, temps de réponse, requêtes
distribuées, etc.).

Ce projet propose de relever ces deux défis grâce à une approche
utilisant les contraintes de graphes à sortes ordonnées à traits - ou
"Order-Sorted Featured (OSF) graphs". Contrairement à la plupart des
approches les plus connues vers le Web Sémantique qui utilisent la
Logique de Description comme base de raisonnement (par ex., OWL), le
formalisme OSF permet une technique de raisonnement qui est
opérationnellement paresseuse (c.à.d. où rien n'est fait qui ne soit
nécessaire), permet une “memoisation” (c.à.d. mémoire des preuves)
instantanée (c.à.d. coût nul). Il est aussi capable de gérer des
hiérarchies de concepts de très grandes tailles grâce à des techniques
de modulation d'encodages binaires, et généralement de techniques
exploitant la structure spécifiques propre aux graphs OSF résultant de
bases de connaissances réelles.

Le projet CEDAR peut se résumer comme une tentative de vérifier tous
ceci sur des véritables bases de connaissances RDF de très grandes
tailles.

 

Programme ANR : Chaires d’excellence (CHEX) 2012

Référence projet : ANR-12-CHEX-0003

Coordinateur du projet :
Monsieur Hassan AIT-KACI (Laboratoire d'Informatique en Image et Systèmes d'Information)
hassanaitkaci@nullgmail.com

Site internet du projet : http://cedar.liris.cnrs.fr

 

Revenir à la page précédente

 

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.