Academic literature on the topic 'Raffinement des graphes de connaissances'

La proliferation et le grand succes des applications incorporant des reseaux de neurones artificiels (rna) dans plusieurs domaines montrent l'utilite du paradigme rna. Neanmoins, ce paradigme a une limite : son incapacite inherente a fournir une explication des resultats obtenus. C'est essentiellement pour vaincre cette limite que plusieurs chercheurs se sont interesses a combiner les rna et les systemes symboliques de maniere a profiter de leurs avantages et eviter leurs faiblesses. Dans cette these, nous decrivons notre contribution a ce domaine de recherche. Nos travaux s'articulent autour de trois axes : l'insertion de connaissances dans un rna, l'extraction de regles a partir d'un rna et l'utilisation d'un rna pour raffiner une base de regles existante. Dans le premier axe : apres une etude critique des principales techniques developpees, nous avons propose deux techniques d'extraction de regles. La premiere, miter, associe a chaque neurone un calibre de poids. Ce dernier est traduit sous forme d'une regle symbolique de la forme m-parmi-n. La seconde, emire, extrait des regles a partir d'un rna sans tenir compte de sa structure interne et en utilisant uniquement ses entrees pertinentes. Dans le deuxieme axe : apres une presentation des principales techniques existantes, nous avons propose deux techniques d'insertion de regles symboliques dans un rna. La premiere, ruleneur, associe a chaque regle ecrite sous une forme normale disjonctive un neurone. La seconde, opneur, associe a chaque operateur logique (et ou ou) un neurone. Dans le troisieme axe, apres une presentation des differents systemes hybrides, nous avons propose le systeme ranni qui combine les deux axes precedents en utilisant un module probabiliste pour leur mise-a-jour.

En l'absence d'une autorité de nommage centrale sur le Web de données, il est fréquent que différents graphes de connaissances utilisent des noms (IRIs) différents pour référer à la même entité. Chaque fois que plusieurs noms sont utilisés pour désigner la même entité, les faits owl:sameAs sont nécessaires pour déclarer des liens d’identité et améliorer l’exploitation des données disponibles. De telles déclarations d'identité ont une sémantique logique stricte, indiquant que chaque propriété affirmée à un nom sera également déduite à l'autre et vice versa. Bien que ces inférences puissent être extrêmement utiles pour améliorer les systèmes fondés sur les connaissances tels que les moteurs de recherche et les systèmes de recommandation, l'utilisation incorrecte de l'identité peut avoir des effets négatifs importants dans un espace de connaissances global comme le Web de données. En effet, plusieurs études ont montré que owl:sameAs est parfois incorrectement utilisé sur le Web des données. Cette thèse étudie le problème de liens d’identité erronés ou inappropriés qui sont exprimés par des liens owl:sameAs et propose des solutions différentes mais complémentaires. Premièrement, elle présente une ressource contenant la plus grande collection de liens d’identité collectés du LOD Cloud, avec un service Web à partir duquel les données et leur clôture transitive peuvent être interrogées. Une telle ressource a à la fois des impacts pratiques (elle aide les utilisateurs à trouver différents noms pour la même entité), ainsi qu'une valeur analytique (elle révèle des aspects importants de la connectivité du LOD Cloud). En outre, en s’appuyant sur cette collection de 558 millions liens d’identité, nous montrons comment des mesures de réseau telles que la structure de communauté du réseau owl:sameAs peuvent être utilisées afin de détecter des liens d’identité éventuellement erronées. Pour cela, nous attribuons un degré d'erreur pour chaque lien owl:sameAs en fonction de la densité de la ou des communautés dans lesquelles elles se produisent et de leurs caractéristiques symétriques. L'un des avantages de cette approche est qu'elle ne repose sur aucune connaissance supplémentaire. Finalement, afin de limiter l'utilisation excessive et incorrecte du owl:sameAs, nous définissons une nouvelle relation pour représenter l'identité de deux instances d’une classe dans un contexte spécifique (une sous-partie de l’ontologie). Cette relation d'identité s'accompagne d'une approche permettant de détecter automatiquement ces liens, avec la possibilité d'utiliser certaines contraintes expertes pour filtrer des contextes non pertinents. La détection et l’exploitation des liens d’identité contextuels détectés sont effectuées sur deux graphes de connaissances pour les sciences de la vie, construits en collaboration avec des experts du domaine de l’institut national de la recherche agronomique (INRA)<br>In the absence of a central naming authority on the Web of data, it is common for different knowledge graphs to refer to the same thing by different names (IRIs). Whenever multiple names are used to denote the same thing, owl:sameAs statements are needed in order to link the data and foster reuse. Such identity statements have strict logical semantics, indicating that every property asserted to one name, will also be inferred to the other, and vice versa. While such inferences can be extremely useful in enabling and enhancing knowledge-based systems such as search engines and recommendation systems, incorrect use of identity can have wide-ranging effects in a global knowledge space like the Web of data. With several studies showing that owl:sameAs is indeed misused for different reasons, a proper approach towards the handling of identity links is required in order to make the Web of data succeed as an integrated knowledge space. This thesis investigates the identity problem at hand, and provides different, yet complementary solutions. Firstly, it presents the largest dataset of identity statements that has been gathered from the LOD Cloud to date, and a web service from which the data and its equivalence closure can be queried. Such resource has both practical impacts (it helps data users and providers to find different names for the same entity), as well as analytical value (it reveals important aspects of the connectivity of the LOD Cloud). In addition, by relying on this collection of 558 million identity statements, we show how network metrics such as the community structure of the owl:sameAs graph can be used in order to detect possibly erroneous identity assertions. For this, we assign an error degree for each owl:sameAs based on the density of the community(ies) in which they occur, and their symmetrical characteristics. One benefit of this approach is that it does not rely on any additional knowledge. Finally, as a way to limit the excessive and incorrect use of owl:sameAs, we define a new relation for asserting the identity of two ontology instances in a specific context (a sub-ontology). This identity relation is accompanied with an approach for automatically detecting these links, with the ability of using certain expert constraints for filtering irrelevant contexts. As a first experiment, the detection and exploitation of the detected contextual identity links are conducted on two knowledge graphs for life sciences, constructed in a mutual effort with domain experts from the French National Institute of Agricultural Research (INRA)

Cette thèse se situe dans le cadre de méthodes de conception de systèmes répartis s'appuyant sur des techniques de raffinement d'actions. En considérant la technique de description formelle lotos comme langage d'étude, elle aborde des problèmes théoriques concernant l'adéquation de différentes sémantiques du parallélisme pour la mise en oeuvre du raffinement d'actions. Bien que la sémantique d'entrelacement soit souvent considérée comme étant la plus simple pour exprimer le parallélisme, elle ne permet pas de représenter correctement le comportement de systèmes concurrents dès que les actions ne sont plus atomiques. La non atomicité des actions implique l'utilisation de sémantiques de vrai parallélisme, dont deux, la maximalité et la causalité, sont développées ici pour lotos. Dans le but de mieux comprendre différents aspects du raffinement d'actions, et de faciliter son exploitation ultérieure, nous avons défini le modèle des arbres maximaux qui est à la base de la sémantique dénotationnelle proposée pour lotos. Cette sémantique a été prouvée compatible avec la sémantique opérationnelle structurée de maximalite de lotos étendu par un opérateur de raffinement d'actions. Pour comparer sémantiques de maximalite et de causalité, la même approche technique a été utilisée pour proposer une nouvelle définition des arbres causaux, dans laquelle les références statiques ont été remplacées par des références dynamiques. Les arbres ainsi obtenus sont appelés arbres causaux dynamiques. Finalement, dans le but de passer de l'étude théorique du raffinement d'actions à sa mise en oeuvre pratique, nous avons proposé une solution permettant d'effectuer un raffinement syntaxique d'actions en lotos, et qui prend en compte le problème du rendez-vous multiple

Le premier chapitre montre que nos scénarios d'usages sont issus de problèmes de capitalisation, de gestion et de diffusion de connaissances. Nous étudions donc des mémoires individualisées (rattachées à un utilisateur donné), organisationnelles (rattachées à une organisation, notamment une entreprise) ou plus généralement communautaires (rattachées à une communauté d'intérêt ou de pratique). Nous donnons dans le premier chapitre des contextes d'application de nos travaux que nous utiliserons comme des scénarios motivants pour les chapitres suivants. Nous y définissons aussi notre positionnement en représentation des connaissances, notamment pour ce qui est de la représentation d'une mémoire à base d'ontologies.<br />Dans le deuxième chapitre, nous rappelons comment les formalismes à base de graphes peuvent être utilisés pour représenter des connaissances avec un degré variable de formalisation en fonction des besoins identifiés dans les scénarios d'application et des traitements à effectuer notamment pour la mise en place de webs sémantiques. Nous identifierons brièvement les caractéristiques de certains de ces formalismes qui sont utilisés dans nos travaux et les opportunités d'extensions qu'ils offrent. Nous synthétiserons aussi une initiative en cours pour factoriser la définition des structures mathématiques partagées par ces formalismes et réutiliser l'algorithmique des traitements communs à ces structures.<br />Dans le troisième chapitre nous expliquons que l'ontologie offre un support à d'autres types de raisonnement que la dérivation logique. Par exemple, la hiérarchie de notions contenue dans une ontologie peut être vue comme un espace métrique permettant de définir des distances pour comparer la proximité sémantique de deux notions. Nous avons mis en œuvre cette idée dans plusieurs scénarios comme l'allocation distribuée d'annotations, la recherche approchée ou le clustering. Nous résumons dans ce troisième chapitre diverses utilisations que nous avons faites des distances sémantiques et discutons notre position sur ce domaine. Nous donnons les scénarios d'utilisation et les distances utilisées dans un échantillon représentatif de projets que nous avons menés. Pour nous, cette première série d'expériences a permis de démontrer l'intérêt et le potentiel des distances, et aussi de souligner l'importance du travail restant à faire pour identifier et caractériser les familles de distances existantes et leur adéquation respective aux tâches pour lesquelles nos utilisateurs souhaitent être assistés.<br />Dans le quatrième chapitre, nous rappelons qu'un web sémantique, tel que nous en utilisons dans nos scénarios, qu'il soit public ou sur l'intranet d'une entreprise, repose généralement sur plusieurs serveurs web qui proposent chacun différentes ontologies et différentes bases d'annotations utilisant ces ontologies pour décrire des ressources. Les scénarios d'usage amènent souvent un utilisateur à formuler des requêtes dont les réponses combinent des éléments d'annotation distribués entre plusieurs de ces serveurs.<br />Ceci demande alors d'être capable :<br />(1) d'identifier les serveurs susceptibles d'avoir des éléments de réponse ;<br />(2) d'interroger des serveurs distants sur les éléments qu'ils connaissent sans surcharger le réseau;<br />(3) de décomposer la requête et router les sous-requêtes vers les serveurs idoines ;<br />(4) de recomposer les résultats à partir des réponses partielles.<br />Nous avons, avec le web sémantique, les briques de base d'une architecture distribuée. Le quatrième chapitre résume un certain nombre d'approches que nous avons proposées pour tenir compte de la distribution et gérer des ressources distribuées dans les webs sémantiques que nous concevons.<br />Les ontologies et les représentations de connaissances sont souvent dans le cœur technique de nos architectures, notamment lorsqu'elles utilisent des représentations formelles. Pour interagir avec le web sémantique et ses applications, le cinquième chapitre rappelle que nous avons besoin d'interfaces qui les rendent intelligibles pour les utilisateurs finaux. Dans nos systèmes d'inférences des éléments de connaissances sont manipulés et combinés, et même si les éléments de départ étaient intelligibles, l'intelligibilité des résultats, elle, n'est pas préservée par ces transformations.<br />Actuellement, et dans le meilleur des cas, les concepteurs d'interfaces mettent en œuvre des transformations ad hoc des structures de données internes en représentations d'interface en oubliant souvent les capacités de raisonnement que pourraient fournir ces représentations pour construire de telles interfaces. Dans le pire des cas, et encore trop souvent, les structures de représentation normalement internes sont directement mises à nu dans des widgets sans que cela soit justifié et, au lieu d'assister l'interaction, ces représentations alourdissent les interfaces.<br />Puisqu'elles reçoivent les contributions d'un monde ouvert, les interfaces du web sémantique devront être, au moins en partie, générées dynamiquement et rendues pour chaque structure devant rentrer en contact avec les utilisateurs. Le cinquième et dernier chapitre souligne cette opportunité croissante d'utiliser des systèmes à base d'ontologies dans l'assistance aux interactions avec nos utilisateurs.

L'explosion de données relationnelles largement disponiblessous la forme de graphes de connaissances a permisle développement de multiples applications, dont les agents personnels automatiques,les systèmes de recommandation et l'amélioration desrésultats de recherche en ligne.La grande taille et l'incomplétude de ces bases de donnéesnécessite le développement de méthodes de complétionautomatiques pour rendre ces applications viables.La complétion de graphes de connaissances, aussi appeléeprédiction de liens, se doit de comprendre automatiquementla structure des larges graphes de connaissances (graphes dirigéslabellisés) pour prédire les entrées manquantes (les arêtes labellisées).Une approche gagnant en popularité consiste à représenter ungraphe de connaissances comme un tenseur d'ordre 3, etd'utiliser des méthodes de décomposition de tenseur pourprédire leurs entrées manquantes.Les modèles de factorisation existants proposent différentscompromis entre leur expressivité, et leur complexité en temps et en espace.Nous proposons un nouveau modèle appelé ComplEx, pour"Complex Embeddings", pour réconcilier expressivité etcomplexité par l'utilisation d'une factorisation en nombre complexes,dont nous explorons le lien avec la diagonalisation unitaire.Nous corroborons notre approche théoriquement en montrantque tous les graphes de connaissances possiblespeuvent être exactement décomposés par le modèle proposé.Notre approche, basées sur des embeddings complexesreste simple, car n'impliquant qu'un produit trilinéaire complexe,là où d'autres méthodes recourent à des fonctions de compositionde plus en plus compliquées pour accroître leur expressivité.Le modèle proposé ayant une complexité linéaire en tempset en espace est passable à l'échelle, tout endépassant les approches existantes sur les jeux de données de référencepour la prédiction de liens.Nous démontrons aussi la capacité de ComplEx àapprendre des représentations vectorielles utiles pour d'autres tâches,en enrichissant des embeddings de mots, qui améliorentles prédictions sur le problème de traitement automatiquedu langage d'implication entre paires de phrases.Dans la dernière partie de cette thèse, nous explorons lescapacités de modèles de factorisation à apprendre lesstructures relationnelles à partir d'observations.De part leur nature vectorielle,il est non seulement difficile d'interpréter pourquoicette classe de modèles fonctionne aussi bien,mais aussi où ils échouent et comment ils peuventêtre améliorés. Nous conduisons une étude expérimentalesur les modèles de l'état de l'art, non pas simplementpour les comparer, mais pour comprendre leur capacitésd'induction. Pour évaluer les forces et faiblessesde chaque modèle, nous créons d'abord des tâches simplesreprésentant des propriétés atomiques despropriétés des relations des graphes de connaissances ;puis des tâches représentant des inférences multi-relationnellescommunes au travers de généalogies synthétisées.À partir de ces résultatsexpérimentaux, nous proposons de nouvelles directionsde recherches pour améliorer les modèles existants,y compris ComplEx<br>The explosion of widely available relational datain the form of knowledge graphsenabled many applications, including automated personalagents, recommender systems and enhanced web search results.The very large size and notorious incompleteness of these data basescalls for automatic knowledge graph completion methods to make these applicationsviable. Knowledge graph completion, also known as link-prediction,deals with automatically understandingthe structure of large knowledge graphs---labeled directed graphs---topredict missing entries---labeled edges. An increasinglypopular approach consists in representing knowledge graphs as third-order tensors,and using tensor factorization methods to predict their missing entries.State-of-the-art factorization models propose different trade-offs between modelingexpressiveness, and time and space complexity. We introduce a newmodel, ComplEx---for Complex Embeddings---to reconcile both expressivenessand complexity through the use of complex-valued factorization, and exploreits link with unitary diagonalization.We corroborate our approach theoretically and show that all possibleknowledge graphs can be exactly decomposed by the proposed model.Our approach based on complex embeddings is arguably simple,as it only involves a complex-valued trilinear product,whereas other methods resort to more and more complicated compositionfunctions to increase their expressiveness. The proposed ComplEx model isscalable to large data sets as it remains linear in both space and time, whileconsistently outperforming alternative approaches on standardlink-prediction benchmarks. We also demonstrateits ability to learn useful vectorial representations for other tasks,by enhancing word embeddings that improve performanceson the natural language problem of entailment recognitionbetween pair of sentences.In the last part of this thesis, we explore factorization models abilityto learn relational patterns from observed data.By their vectorial nature, it is not only hard to interpretwhy this class of models works so well,but also to understand where they fail andhow they might be improved. We conduct an experimentalsurvey of state-of-the-art models, not towardsa purely comparative end, but as a means to get insightabout their inductive abilities.To assess the strengths and weaknesses of each model, we create simple tasksthat exhibit first, atomic properties of knowledge graph relations,and then, common inter-relational inference through synthetic genealogies.Based on these experimental results, we propose new researchdirections to improve on existing models, including ComplEx

Pour modéliser au mieux les phénomènes linguistiques dans les systèmes de traitement automatique des langues (traduction, analyse, etc. ), il faut disposer de ressources de qualité. Or, les ressources existantes sont souvent incomplètes et ne permettent pas de traiter correctement les données. Cette thèse s'intéresse à l'acquisition de connaissances linguistiques, plus précisément à leur extraction à partir de corpus. Nous étudions en particulier le problème des collocations, ces couples de termes dont l'un est choisi en fonction de l'autre pour exprimer un sens particulier (comme « pluie battante » où « pluie » exprime l'intensification). Pour permettre l'acquisition de données à grande échelle, il faut la rendre facile à réaliser de manière automatique, et simple à paramétrer par des linguistes aux connaissances limitées en programmation ; cela nécessite une modélisation adaptée et précise des données et des processus. Nous avons réalisé et décrivons MuLLinG, modèle de graphes linguistiques multiniveau, où chaque niveau représente l'information d'une manière différente,et les opérations de manipulation de ces graphes. Ce modèle permet de représenter et traiter divers types de ressources. En effet, les opérations associées ont été écrites pour être les plus génériques possibles : elles sont indépendantes de ce que peuvent représenter les nœuds et les arcs du graphe, et de la tâche à réaliser. Cela permet à notre modèle, mis en œuvre et utilisé pour plusieurs expérimentations (entre autres l'extraction de collocations), de voir un processus parfois complexe d'extraction de connaissances linguistiques comme une succession d'opérations simples de manipulation de graphes<br>In order to model at best linguistic phenomena, natural language processing systems need to have quality ressources at their disposal, yet existing ressources are most often incomplete and do not allow to treat data in an adequate manner in process like translation, analysis, etc. This thesis is about acquisition of linguistic knowledge, and more precisely about the extraction of that knowledge from corpora where it appears. We study especially the problem of the collocations, these couple of terms where one term is chosen in function of the other one to express a particular meaning (as « driving rain », where « driving » is used to express the intensification). To allow large-scale data acquisition, it is necessary to make it easy to realize in an automatic manner, and simple to configure by linguists with limited knowledge in computer programming. For that reason, we have to rely on a precise and suitable model for data and process. We describe MuLLinG, the multilevel linguistic graph we realized, where each level represents information in a different manner, and operations for the manipulation of these graphs. That model, based on a simple structure (the graph one), allows to represent, treat, and manage diverse kinds of ressources. Indeed, associated operations were written in order to be as most generic as possible, which means that they are independent of what nodes and edges represents, and of the task to realize. That enables our model, which has been implemented and used for several experiments, some concerning collocation extraction, to view a process (sometimes complex) of linguistic knowledge extraction, as a succession of small graph manipulation operations

Dans cette thèse, nous étudions l’impact des connaissances sur la calculabilité distribuée de problèmes au sein des réseaux distribués. Dans une première partie, nous caractérisons les connaissances nécessaires et suffisantes permettant de résoudre des problèmes tels la cartographie, l’élection et la k-élection dans un modèle particulier: les participants inconnus. Pour chacun des problèmes étudiés, une condition caractérisant les connaissances nécessaires et suffisantes est fournie et un algorithme utilisant toute connaissance satisfaisant notre condition est proposé (et montré correct). Nous étendons ensuite le modèle aux graphes anonymes. Avec la même méthodologie, nous présentons une condition nécessaire sur la connaissance à fournir aux processus pour résoudre le problème de l’élection. Dans la seconde partie, nous étudions l’impact des connaissances locales sur la calculabilité du problème de l’exploration de graphes anonymes avec arrêt. Nous introduisons un nouveau modèle d’agent mobile doté d’un capteur spécial, nommé jumelles, lui permettant de percevoir le graphe induit par les sommets adjacent à sa position dans le réseau. Dans ce modèle, nous caractérisons exactement les graphes explorables sans connaissance globale et nous proposons un algorithme les explorant. Cette connaissance locale apportée à un coût car la complexité de tout algorithme d’exploration pour ces graphes croît plus vite que toute fonction calculable. Pour finir, nous montrons que de larges familles de graphes peuvent être explorées efficacement avec jumelles: graphes triangulés, graphes de Johnson et certaines triangulations planaires<br>In this study, we show how knowledge impacts the computability in distributed systems. First, we characterize what we need to know to elect in the unknown participant model. This model is a natural extension for the message passing model that formalises dynamicity that occurs in some networks. We give a necessary and sufficient condition on the knowledge needed to solve the following fundamental problems : map construction, leader election and k-leader election. For each of them, we provide an algorithm solving the problem using any knowledge satisfying our condition. Then, we extend the model to anonymous networks. We characterize, with the same methodology, the knowledge needed to solve an election in this model and we provide an algorithm using such a knowledge and a bound on the size of the network. In the second part, we study the impact of local knowledge on the computability of the anonymous graph exploration problem. We introduce a new model of mobile agents where an agent is endowed with binoculars, a local sensor permitting to perceive the graph induced by the vertices adjacent to its location. In this model, we characterize the graphs that can be explored by a single mobile agent without any global information and we provide an algorithm exploring all of them. Unfortunately, universal algorithm has a cost : The number of moves required by such an algorithm cannot be bounded by a computable function. Finally, we prove that large classes of graphs like chordal graphs, Johnson graphs, . . . can be explored in a linear number of moves using binoculars by providing an exploration algorithm for the family of Weetman graphs

Nos recherches se sont déroulées dans le cadre d'un projet RNRT appelé RECIS en collaboration avec FT R&amp;D et l'INRIA. Le but de ce projet est d'étudier les modalités pour enrichir les services d'accès au contenu multimédia. Nous avons mis en place un modèle d'annotation de documents audiovisuels : E-SIA. Ce modèle représente les fragments de documents, les annotations, ainsi que les éléments de structuration des annotation par un graphe. Le modèle permet de documenter et de guider l'annotation tout en laissant une grande liberté aux utilisateurs. Nous avons développé un prototype client serveur qui permet l'annotation manuelle et automatique de documents ainsi que la navigation et la recherche dans les annotations. Nous avons étendu notre modèle d'annotation pour créer un cadre de traçage, de capitalisation et de réutilisation de l'expérience : Trèfle. Ce modèle permet de tracer l'utilisation d'un logiciel de manière contextuelle selon un modèle d'utilisation et d'un modèle d'observation dans un graphe. Nous considérons que dans une application informatique des utilisateurs manipulent des objets à l'aide de procédés<br>Our research has been carried out as a part of the RNRT project RECIS in collaboration with FT R&amp;D and the INRIA. The goal of this project is to study different techniques to enrich multimedia content access services. We created an audiovisual annotation model : E-SIA. This model represents documents fragments, annotations as well as annotation structuring elements as graph. The model enables to document and guide annotation providing in meantime a large degree of freedom to users. We have developed a client-server prototype application enabling manual and automatic video annotation as well as the navigation an search in these annotations. We have extended our annotation model in order to create an experience tracing, capitalization and reuse framework: Trèfle (Club). This model enables to trace in a contextual manner the use of a computer program following a use and an observation model in a graph. We consider that in a computer program users manipulate objects using procedures