All publications sorted by year |
2023 |
Le challenge ARC ({\em Abstraction and Reasoning Corpus}) a été proposé pour pousser la recherche en IA vers plus de capacité de généralisation plutôt que vers toujours plus de performance. C'est une collection de tâches uniques où il s'agit d'apprendre à générer une grille colorée en fonction d'une autre, et ce à partir de quelques exemples seulement. En contraste avec les programmes transformatifs proposés par les approches existantes, nous proposons des modèles centrés-objets analogues aux programmes naturels produits par des humains. Le principe MDL ({\em Minimum Description Length}) est exploité pour une recherche efficace dans le vaste espace des modèles. Nous obtenons des résultats encourageants avec une classe de modèles simples: des tâches variées sont résolues et les modèles appris sont proches des programmes naturels. |
2022 |
A growing part of Big Data is made of knowledge graphs. Major knowledge graphs such as Wikidata, DBpedia or the Google Knowledge Graph count millions of entities and billions of semantic links. A major challenge is to enable their exploration and querying by end-users. The SPARQL query language is powerful but provides no support for exploration by end-users. Question answering is user-friendly but is limited in expressivity and reliability. Navigation in concept lattices supports exploration but is limited in expressivity and scalability. % In this paper, we introduce a new exploration and querying paradigm, Abstract Conceptual Navigation (ACN), that merges querying and navigation in order to reconcile expressivity, usability, and scalability. ACN is founded on Formal Concept Analysis (FCA) by defining the navigation space as a concept lattice. We then instantiate the ACN paradigm to knowledge graphs (Graph-ACN) by relying on Graph-FCA, an extension of FCA to knowledge graphs. We continue by detailing how Graph-ACN can be efficiently implemented on top of SPARQL endpoints, and how its expressivity can be increased in a modular way. Finally, we present a concrete implementation available online, Sparklis, and a few application cases on large knowledge graphs. |
2021 |
The open nature of Knowledge Graphs (KG) often implies that they are incomplete. Knowledge graph completion (aka. link prediction) consists in inferring new relationships between the entities of a KG based on existing relationships. Most existing approaches rely on the learning of latent feature vectors for the encoding of entities and relations. In general however, latent features cannot be easily interpreted. Rule-based approaches offer interpretability but a distinct ruleset must be learned for each relation. In both latent- and rule-based approaches, the training phase has to be run again when the KG is updated. We propose a new approach that does not need a training phase, and that can provide interpretable explanations for each inference. It relies on the computation of Concepts of Nearest Neighbours (C-NN) to identify clusters of similar entities based on common graph patterns. Different rules are then derived from those graph patterns, and combined to predict new relationships. We evaluate our approach on standard benchmarks for link prediction, where it gets competitive performance compared to existing approaches. |
During the last decade, the need for reliable and massive Knowledge Graphs (KG) increased. KGs can be created in several ways: manually with forms or automatically with Information Extraction (IE), a natural language processing task for extracting knowledge from text. Relation Extraction is the part of IE that focuses on identifying relations between named entities in texts, which amounts to find new edges in a KG. Most recent approaches rely on deep learning, achieving state-of-the-art performances. However, those performances are still too low to fully automatize the construction of reliable KGs, and human interaction remains necessary. This is made difficult by the statistical nature of deep learning methods that makes their predictions hardly interpretable. In this paper, we present a new symbolic and interpretable approach for Relation Extraction in texts. It is based on a modeling of the lexical and syntactic structure of text as a knowledge graph, and it exploits extit{Concepts of Neighbours}, a method based on Graph-FCA for computing similarities in knowledge graphs. An evaluation has been performed on a subset of TACRED (a relation extraction benchmark), showing promising results. |
Graph pattern mining algorithms ease graph data analysis by extracting recurring structures. However, classic pattern mining approaches tend to extract too many patterns for human analysis. Recently, the GraphMDL algorithm has been proposed, which reduces the generated pattern set by using the \emph{Minimum Description Length} (MDL) principle to select a small descriptive subset of patterns. The main drawback of this approach is that it needs to first generate all possible patterns and then sieve through their complete set. In this paper we propose GraphMDL+, an approach based on the same description length definitions as GraphMDL but which tightly interleaves pattern generation and pattern selection (instead of generating all frequent patterns beforehand), and outputs a descriptive set of patterns at any time. Experiments show that our approach takes less time to attain equivalent results to GraphMDL and can attain results that GraphMDL could not attain in feasible time. Our approach also allows for more freedom in the pattern and data shapes, since it is not tied to an external approach. |
The results of a SPARQL query are generally presented as a table with one row per result, and one column per projected variable. This is an immediate consequence of the formal definition of SPARQL results as a sequence of mappings from variables to RDF terms. However, because of the flat structure of tables, some of the RDF graph structure is lost. This often leads to duplicates in the contents of the table, and difficulties to read and interpret results. % We propose to use nested tables to improve the presentation of SPARQL results. A nested table is a table where cells may contain embedded tables instead of RDF terms, and so recursively. We introduce an automated procedure that lifts flat tables into nested tables, based on an analysis of the query. We have implemented the procedure on top of Sparklis, a guided query builder in natural language, in order to further improve the readability of its UI. It can as well be implemented on any SPARQL querying interface as it only depends on the query and its flat results. We illustrate our proposal in the domain of pharmacovigilance, and evaluate it on complex queries over Wikidata. |
As more and more data are available as RDF graphs, the availability of tools for data analytics beyond semantic search becomes a key issue of the Semantic Web. Previous work require the modelling of data cubes on top of RDF graphs. We propose an approach that directly answers analytical queries on unmodified (vanilla) RDF graphs by exploiting the computation features of SPARQL~1.1. We rely on the NAF design pattern to design a query builder that completely hides SPARQL behind a verbalization in natural language; and that gives intermediate results and suggestions at each step. Our evaluations show that our approach covers a large range of use cases, scales well on large datasets, and is easier to use than writing SPARQL queries. |
2020 |
In this chapter, we introduce Formal Concept Analysis (FCA) and some of its extensions. FCA is a formalism based on lattice theory aimed at data analysis and knowledge processing. FCA allows the design of so-called concept lattices from binary and complex data. These concept lattices provide a realistic basis for knowledge engineering and the design of knowledge-based systems. Indeed, FCA is closely related to knowledge discovery in databases, knowledge representation and reasoning. Accordingly, FCA supports a wide range of complex and intelligent tasks among which classification, information retrieval, recommendation, network analysis, software engineering and data management. Finally, FCA is used in many applications demonstrating its growing importance in data and knowledge sciences. |
Since the birth of the Semantic Web, numerous knowledge bases have appeared. The applications that exploit them rely on the quality of their data through time. In this regard, one of the main dimensions of data quality is conformance to the expected usage of the vocabulary. However, the vocabulary usage (i.e., how classes and properties are actually populated) can vary from one base to another. Moreover, through time, such usage can evolve within a base and diverges from the previous practices. Methods have been proposed to follow the evolution of a knowledge base by the observation of the changes of their intentional schema (or ontology); however, they do not capture the evolution of their actual data, which can vary greatly in practice. In this paper, we propose a data-driven approach to assess the global evolution of vocabulary usage in large RDF graphs. Our proposal relies on two structural measures defined at different granularities (dataset vs update), which are based on pattern mining techniques. We have performed a thorough experimentation which shows that our approach is scalable, and can capture structural evolution through time of both synthetic (LUBM) and real knowledge bases (different snapshots and updates of DBpedia). |
Knowledge graphs offer a versatile knowledge representation, and have been studied under different forms, such as conceptual graphs or RDF graphs in the Semantic Web. A challenge is to discover conceptual structures in those graphs, in the same way as Formal Concept Analysis (FCA) discovers conceptual structures in tables. FCA has been successful for analysing, mining, learning, and exploring tabular data, and our aim is to help transpose those results to graph-based data. Previous several FCA approaches have already addressed relational data, hence graphs, but with various limits. We propose Graph-FCA as an extension of FCA where a dataset is a hypergraph instead of a binary table. We show that it can be formalized simply by replacing objects by tuples of objects. This leads to the notion of "n-ary concept", whose extent is an n-ary relation of objects, and whose intent is a "projected graph pattern". In this paper, we formally reconstruct the fundamental results of FCA for knowledge graphs. We describe in detail the representation of hypergraphs, and the operations on them, as they are much more complex than the sets of attributes that they extend. We also propose an algorithm based on a notion of "pattern basis" to generate and display n-ary concepts in a more efficient and more compact way. We explore a few use cases, in order to study the feasibility and usefulness of Graph-FCA. We consider two use cases: workflow patterns in cooking recipes and linguistic structures from parse trees. In addition, we report on experiments about quantitative aspects of the approach. |
Plusieurs algorithmes de fouille de motifs ont été proposés pour identifier des structures récurrentes dans les graphes. Le principal défaut de ces approches est qu'elles produisent généralement trop de motifs pour qu'une analyse humaine soit possible. Récemment, des méthodes de fouille de motifs ont traité ce problème sur des données transactionnelles, séquentielles et relationnelles en utilisant le principe MDL (Minimum Description Length). Dans ce papier, nous proposons une approche MDL pour sélectionner un sous-ensemble représentatif de motifs sur des graphes non-orientés étiquetés. Une notion clé de notre approche est l'introduction de ports pour encoder les connections entre occurrences de motifs, sans perte d'information. Nos expériences montrent que le nombre de motifs est drastiquement réduit et que les motifs sélectionnés peuvent avoir des formes complexes. |
Pattern mining algorithms allow to extract structures from data to highlight interesting and useful knowledge. However, those approaches can only be truly helpful if the users can actually understand their outputs. Thus, visualization techniques play a great role in pattern mining, bridging the gap between the algorithms and the users. In this demo paper we propose GraphMDL Visualizer, a tool for the interactive visualization of the graph patterns extracted with GraphMDL, a graph mining approach based on the MDL principle. GraphMDL Visualizer is structured according to the behavior and needs of users when they analyze GraphMDL results. The tool has different views, ranging from more general (distribution of pattern characteristics), to more specific (visualization of specific patterns). It is also highly interactive, allowing the users to customize the different views, and navigate between them, through simple mouse clicks. GraphMDL Visualizer is freely available online. |
Many graph pattern mining algorithms have been designed to identify recurring structures in graphs. The main drawback of these approaches is that they often extract too many patterns for human analysis. Recently, pattern mining methods using the Minimum Description Length (MDL) principle have been proposed to select a characteristic subset of patterns from transactional, sequential and relational data. In this paper, we propose an MDL-based approach for selecting a characteristic subset of patterns on labeled graphs. A key notion in this paper is the introduction of ports to encode connections between pattern occurrences without any loss of information. Experiments show that the number of patterns is drastically reduced. The selected patterns have complex shapes and are representative of the data. |
Tables are a common form of query results, notably in SPARQL. However, due to the flat structure of tables, all structure from the RDF graph is lost, and this can lead to duplications in the table contents, and difficulties to interpret the results. We propose an extension of SPARQL 1.1 aggregations to get nested results, i.e. tables where cells may contain embedded tables instead of RDF terms, and so recursively |
As more and more data are available as RDF graphs, the availability of tools for analytical queries beyond semantic search becomes a key issue of the Semantic Web. Previous work require the modelling of data cubes on top of RDF graphs. We propose an approach that directly answers analytical queries on unmodified RDF graphs by exploiting the computation features of SPARQL 1.1 (aggregations, expressions). We rely on the NAF design pattern to design a query builder user interface that is user-friendly by completely hiding SPARQL behind a verbalization in natural language; and responsive by giving intermediate results and suggestions at each step. Our evaluations show that our approach covers a large range of use cases, and scales well on large datasets. |
Les concepts de voisins définissent une forme symbolique de similarité entre les entités d'un graphe de connaissances. Partant d'une entité, chaque concept de voisins est un cluster d'entités voisines partageant un même motif de graphe centré sur l'entité. Dans ce papier démo, nous rappelons les définitions des concepts de voisins et nous présentons une extension de la librairie Jena dont l'API permet de calculer les concepts de voisins pour un modèle RDF(S) Jena. Nous présentons également une interface graphique permettant à un utilisateur d'effectuer ces calculs de façon simple et interactive. |
The Knomana knowledge base brings together knowledge from the scientific literature on the use of plants with pesticidal or antibiotic effects on animals, plants, and human beings to propose protection solutions using local plants. In this literature, the elements of the 3-tuple (protected organism, protecting plant, pest) are named using the binomial nomenclature consisting of the genus name followed by the species name. In some instances, authors use the abbreviation "sp." in the singular or "spp." in the plural, as species name, to indicate the indeterminate status of the species for a guaranteed genus. To suggest protection solutions, the indeterminacy of the species has to be hypothesized based on assigning the sp./spp. to the other species in the same genus and conversely. This paper discusses the classification of ternary data containing some indeterminate values generated by three extensions of Formal Concept Analysis. |
2019 |
2018 |
Pharmacovigilance is in charge of studying the adverse effects of pharmaceutical products. In this field, pharmacovigilance specialists experience several difficulties when searching and exploring their patient data despite the existence of standardized terminologies (MedDRA). In this paper, we present our approach to enhance the way pharmacovigilance specialists perform search and exploration on their data. First, we have developed a knowledge graph that relies on the OntoADR ontology to semantically enrich the MedDRA terminology with SNOMED CT concepts, and that includes anonymized patient data from FAERS. Second, we have chosen and applied a semantic search tool, Sparklis, according to the user requirements that we have identified in pharmacovigilance. |
Pharmacovigilance is in charge of studying the adverse effects of pharmaceutical products. In this field, pharmacovigilance specialists experience several difficulties when searching and exploring their patient data despite the existence of standardized terminologies (MedDRA). In this paper, we present our approach to enhance the way pharmacovigilance specialists perform search and exploration on their data. First, we have developed a knowledge graph that relies on the OntoADR ontology to semantically enrich the MedDRA terminology with SNOMED CT concepts, and that includes anonymized patient data from FAERS. Second, we have chosen and extended a semantic search tool, Sparklis, according to the user requirements that we have identified in pharmacovigilance. We report the results of a usability evaluation that has been performed by human factors specialists to check the benefits of our proposal. |
Query relaxation has been studied as a way to find approximate answers when user queries are too specific or do not align well with the data schema. We are here interested in the application of query relaxation to similarity search of RDF nodes based on their description. However, this is challenging because existing approaches have a complexity that grows in a combinatorial way with the size of the query and the number of relaxation steps. We introduce two algorithms, answers partitioning and lazy join, that together significantly improve the efficiency of query relaxation. Our experiments show that our approach scales much better with the size of queries and the number of relaxation steps, to the point where it becomes possible to relax large node descriptions in order to find similar nodes. Moreover, the relaxed descriptions provide explanations for their semantic similarity. |
Controlled natural languages (CNL) have the benefits to combine the readability of natural languages, and the accuracy of formal languages. They have been used to help users express facts, rules or queries. While generally easy to read, CNLs remain difficult to write because of the constrained syntax. A common solution is a grammar-based auto-completion mechanism to suggest the next possible words in a sentence. However, this solution has two limitations: (a) partial sentences may have no semantics, which prevents giving intermediate results or feedback, and (b) the suggestion is often limited to adding words at the end of the sentence. % We propose a more responsive and flexible CNL authoring by designing it as a sequence of sentence transformations. Responsiveness is obtained by having a complete, and hence interpretable, sentence at each time. Flexibility is obtained by allowing insertion and deletion on any part of the sentence. Technically, this is realized by working directly on the abstract syntax, rather than on the concrete syntax, and by using Huet's zippers to manage the focus on a query part, the equivalent of the text cursor of a word processor. |
Sparklis is a SPARQL query builder that can connect to any endpoint, and that interacts with users in natural language only. Users are guided in the building of their queries so that they do not have to know the schema, and so that empty results are almost completely avoided. This demo paper presents a number of recent extensions to Sparklis. Most notably, it now supports analytical queries, Wikidata statement qualifiers, and the display of results on a map or as a slideshow. |
Relational Concept Analysis (RCA) has been introduced in order to allow concept analysis on multi-relational data. It significantly widens the field of application of Formal Concept Analysis (FCA), and it produces richer concept intents that are similar to concept definitions in Description Logics (DL). However, reading and interpreting RCA concept lattices is notoriously difficult. Nica {\em et al} have proposed to represent RCA intents by cpo-patterns in the special case of sequence structures. We propose an equivalent representation of a family of RCA concept lattices in the form of a hierarchy of concept graphs. Each concept belongs to one concept graph, and each concept graph exhibits the relationships between several concepts. A concept graph is generally transversal to several lattices, and therefore highlights the relationships between different types of objects. We show the benefits of our approach on several use cases from the RCA litterature. |
As more and more data are available as RDF graphs, the availability of tools for data analytics beyond semantic search becomes a key issue of the Semantic Web. Previous work has focused on adapting OLAP-like approaches and question answering by modelling RDF data cubes on top of RDF graphs. We propose a more direct -- and more expressive -- approach by guiding users in the incremental building of SPARQL~1.1 queries that combine several computation features (aggregations, expressions, bindings and filters), and by evaluating those queries on unmodified (vanilla) RDF graphs. We rely on the NF design pattern to hide SPARQL behind a natural language interface, and to provide results and suggestions at every step. We have implemented our approach on top of {\sc Sparklis}, and we report on three experiments to assess its expressivity, usability, and scalability. |
2017 |
Sparklis is a Semantic Web tool that helps users explore and query SPARQL endpoints by guiding them in the interactive building of questions and answers, from simple ones to complex ones. It combines the fine-grained guidance of faceted search, most of the expressivity of SPARQL, and the readability of (controlled) natural languages. No knowledge of the vocabulary and schema are required for users. Many SPARQL features are covered: multidimensional queries, union, negation, optional, filters, aggregations, ordering. Queries are verbalized in either English or French, so that no knowledge of SPARQL is ever necessary. All of this is implemented in a portable Web application, Sparklis, and has been evaluated on many endpoints and questions. No endpoint-specific configuration is necessary as the data schema is discovered on the fly by the tool. Online since April 2014, thousands of queries have been formed by hundreds of users over more than a hundred endpoints. |
Nous introduisons la notion de {\em concept de voisins} comme alternative à la notion de distance numérique dans le but d'identifier les objets les plus similaires à un objet requête, comme dans la méthode des plus proches voisins. Chaque concept de voisins est composé d'une intension qui décrit symboliquement ce que deux objets ont en commun et d'une extension qui englobe les objets qui se trouvent entre les deux. Nous définissons ces concepts de voisins pour des données complexes, les graphes de connaissances, où les n{\oe}uds jouent le rôle d'objets. Nous décrivons un algorithme {\em anytime} permettant d'affronter la complexité élevée de la tâche et nous présentons de premières expérimentations sur un graphe RDF de plus de 120.000 triplets. |
2016 |
Heterogeneity of data and data formats in bioinformatics entail mismatches between inputs and outputs of different services, making it difficult to compose them into workflows. To reduce those mismatches, bioinformatics platforms propose ad'hoc converters, called shims. When shims are written by hand, they are time-consuming to develop, and cannot anticipate all needs. When shims are automatically generated, they miss transformations, for example data composition from multiple parts, or parallel conversion of list elements. This article proposes to systematically detect convertibility from output types to input types. Convertibility detection relies on a rule system based on abstract types, close to XML Schema. Types allow to abstract data while precisely accounting for their composite structure. Detection is accompanied by an automatic generation of converters between input and output XML data. % We show the applicability of our approach by abstracting concrete bioinformatics types (e.g., complex biosequences) for a number of bioinformatics services (e.g., blast). We illustrate how our automatically generated converters help to resolve data mismatches when composing workflows. % We conducted an experiment on bioinformatics services and datatypes, using an implementation of our approach, as well as a survey with domain experts. The detected convertibilities and produced converters were validated as relevant from a biological point of view. Furthermore the automatically produced graph of potentially compatible services exhibited a connectivity higher than with the ad'hoc approaches. Indeed, the experts discovered unknown possible connexions. |
Expressions, such as mathematical formulae, logical axioms, or structured queries, account for a large part of human knowledge. It is therefore desirable to allow for their representation and querying with Semantic Web technologies. We propose an RDF design pattern that fulfills three objectives. The first objective is the structural representation of expressions in standard RDF, so that expressive structural search is made possible. We propose simple Turtle and SPARQL abbreviations for the concise notation of such RDF expressions. The second objective is the automated generation of expression labels that are close to usual notations. The third objective is the compatibility with existing practice and legacy data in the Semantic Web (e.g., SPIN, OWL/RDF). We show the benefits for RDF tools to support this design pattern with the extension of SEWELIS, a tool for guided exploration and edition, and its application to mathematical search. |
The Semantic Web is founded on a number of Formal Languages (FL) whose benefits are precision, lack of ambiguity, and ability to automate reasoning tasks such as inference or query answering. This however poses the challenge of mediation between machines and users because the latter generally prefer Natural Languages (NL) for accessing and authoring knowledge. In this paper, we introduce the NF design pattern based on Abstract Syntax Trees (AST), Huet's zippers and Montague grammars to zip together a natural language and a formal language. Unlike question answering, translation does not go from NL to FL, but as symbol NF suggests, from ASTs (A) of an intermediate language to both NL (NF). ASTs are built interactively and incrementally through a user-machine dialog where the user only sees NL, and the machine only sees FL. |
This work focuses on the statistical questions introduced by the QALD-6 challenge. With the growing amout of semantic data, including numerical data, the need for RDF analytics beyond semantic search becomes a key issue of the Semantic Web. We have extended SPARKLIS from semantic search to RDF analytics by covering the computation features of SPARQL (expressions, aggregations and groupings). We could therefore participate to the new task on statistical questions, and we report the achieved performance of SPARKLIS. Compared to other participants, SPARKLIS does not translate spontaneous questions by users, but instead guide users in the construction of a question. Guidance is based on the actual RDF data so as to ensure that built questions are well-formed, non-ambiguous, and inhabited with answers. We show that SPARKLIS enables superior results for both an expert user (94\% correct) and a beginner user (76\% correct). |
We propose a novel approach to ontology authoring that is centered on semantics rather than on syntax. Instead of writing axioms formalizing a domain, the expert is invited to explore the possible worlds of her ontology, and to eliminate those that do not conform to her knowledge. Each elimination generates an axiom that is automatically derived from the explored situation. We have implemented the approach in prototype PEW (Possible World Explorer), and conducted a user study comparing it to Protégé. The results show that more axioms are produced with PEW, without making more errors. More importantly, the produced ontologies are more complete, and hence more deductively powerful, because more negative constraints are expressed. |
With the rise of the Semantic Web, more and more relational data are made available in the form of knowledge graphs (e.g., RDF, conceptual graphs). A challenge is to discover conceptual structures in those graphs, in the same way as Formal Concept Analysis (FCA) discovers conceptual structures in tables. Graph-FCA has been introduced in a previous work as an extension of FCA for such knowledge graphs. In this paper, algorithmic aspects and use cases are explored in order to study the feasability and usefulness of G-FCA. We consider two use cases. The first one extracts linguistic structures from parse trees, comparing two graph models. The second one extracts workflow patterns from cooking recipes, highlighting the benefits of n-ary relationships and concepts. |
Knowledge acquisition is a central issue of the Semantic Web. Knowledge cannot always be automatically extracted from existing data, thus contributors have to make efforts to create new data. In this paper, we propose FORMULIS, a dynamic form-based interface designed to make RDF data authoring easier. FORMULIS guides contributors through the creation of RDF data by suggesting fields and values according to the previously filled fields and the previously created resources. |
2015 |
Dans les domaines scientifiques, particulièrement en bioinformatique, des services élémentaires sont composés sous forme de workflows pour effectuer des expériences d'analyse de données complexes. À cause de l'hétérogénéité des ressources, la composition de services est une tâche difficile. Les utilisateurs, en composant des workflows, manquent d'assistance pour retrouver et interconnecter les services compatibles. Les solutions existantes utilisent des services spéciaux définis de manière manuelle pour gérer les conversions de formats de données entre les entrées et sorties des services dans les workflows. Cela est pénible pour un utilisateur final. Gérer les incompatibilités des services avec des convertisseurs manuels prend du temps et est lourd. Il existe des solutions automatisées pour faciliter la composition de workflows mais elles sont généralement limitées dans le guidage et l'adaptation des données entre services. La première contribution de cette thèse propose de détecter systématiquement la convertibilité des sorties vers les entrées des services. La détection de convertibilité repose sur un système de règles basé sur une abstraction des types d'entrée et sortie des services. L'abstraction de types permet de considérer la nature et la composition des données d'entrée et sortie. Les règles permettent la décomposition et la composition ainsi que la spécialisation et la généralisation de types. Elles permettent également de générer des convertisseurs de données à utiliser entre services dans les workflows. La deuxième contribution propose une approche interactive qui permet de guider des utilisateurs à composer des workflows en fournissant des suggestions de services et de liaisons compatibles basées sur la convertibilité de types d'entrée et sortie des services. L'approche est basée sur le modèle des Systèmes d'Information Logiques (LIS) qui permettent des requêtes et une navigation guidées et sûres sur des données représentées avec une logique uniforme. Avec notre approche, la composition de workflows est sûre et complète vis-à-vis de propriétés désirées. Les résultats et les expériences, effectués sur des services et des types de données en bioinformatique, montrent la pertinence de nos approches. Nos approches offrent des mécanismes adaptés pour gérer les incompatibilités de services dans les workflows, en prenant en compte la structure composite des données d'entrée et sortie. Elles permettent également de guider, étape par étape, des utilisateurs à définir des workflows bien formés à travers des suggestions pertinentes. |
This paper proposes an interactive approach that guides users in the step-by-step composition of services by providing safe suggestions based on type convertibility. % Users specify the points of the workflow (called the focus) they want to complete, and our approach suggests services and connections whose data types are compatible with the focus. % We prove the safeness (every step produces a well-formed workflow) and the completeness (every well-formed workflow can be built) of our approach. |
Knowledge graphs offer a versatile knowledge representation, and have been studied under different forms, such as conceptual graphs or Datalog databases. With the rise of the Semantic Web, more and more data are available as knowledge graphs. FCA has been successful for analyzing, mining, learning, and exploring tabular data, and our aim is to help transpose those results to graph-based data. Previous FCA approaches have already addressed relational data, hence graphs, but with various limits. We propose G-FCA as an extension of FCA where the formal context is a knowledge graph based on n-ary relationships. The main contributions is the introduction of ``n-ary concepts'', i.e. concepts whose extents are n-ary relations of objects. Their intents, ``projected graph patterns'', mix relationships of different arities, objects, and variables. In this paper, we lay first theoretical results, in particular the existence of a concept lattice for each concept arity, and the role of relational projections to connect those different lattices. |
La conception d'ontologies constitue souvent un frein à l'adoption des techniques de l'ingénierie des connaissances et du Web sémantique. Une raison est bien sûr l'emploi de formalismes et des concepts logiques qui y sont associés. Une autre raison qui nous semble plus profonde est le fossé entre syntaxe et sémantique, c'est-à-dire entre la forme de surface de l'ontologie (axiomes) et ce qu'elle rend nécessaire/possible/impossible (modèles). Ce fossé entraîne des divergences entre l'intention du concepteur et sa modélisation qui se manifestent par des inférences inattendues, voire des incohérences. Nous proposons une nouvelle approche de conception d'ontologies fondée sur l'exploration et l'élimination interactive de ``mondes possibles'' (modèles). Elle réduit le fossé syntaxe/sémantique en interdisant par construction la production d'incohérence, et en montrant en permanence au concepteur ce qui peut être inféré ou non. Un prototype, PEW (Possible World Explorer), permet d'expérimenter cette approche et de la comparer à d'autres éditeurs d'ontologies. |
2014 |
In many domains where information access plays a central role, there is a gap between expert users who can ask complex questions through formal query languages (e.g., SQL), and lay users who either are dependent on expert users, or must restrict themselves to ask simpler questions (e.g., keyword search). Because of the formal nature of those languages, there seems to be an unescapable trade-off between expressivity and usability in information systems. The objective of this thesis is to present a number of results and perspectives that show that the expressivity of formal languages can be reconciled with the usability of widespread information systems (e.g., browsing, Faceted Search (FS)). The final aim of this work is to empower people with the capability to produce, explore, and analyze their data in a powerful way. \paragraph{} We have proposed a number of theories and implementations to better reconcile expressivity and usability, and applied them to a number of contexts going from file systems to the Semantic Web. In this thesis, we introduce an unifying framework inspired by Formal Concept Analysis (FCA) to factor out the main ideas of all those results: Abstract Conceptual Navigation (ACN). The principle of ACN is to guide users by letting them {\em navigate} in a conceptual space where places are {\em concepts} connected by navigation links. Concepts are characterized by a formal query, and are made of two parts: an {\em extension} and an {\em intension}. The extension is made of query results while the intension is made of the query itself and an index of query increments over results. Finally, navigation links are formally defined as query transformations. The conceptual space is not static but is induced by concrete data, and evolves with it. ACN therefore combines the {\em expressivity} of formal query languages with the {\em guidance} of conceptual navigation. The {\em readability} of queries is improved by verbalizing them to (or parsing them from) a Controlled Natural Language (CNL). Readability and guidance together support usability by speaking user's language, and by providing a systematic assistance. |
The Semantic Web (SW) is now made of billions of triples, which are available as Linked Open Data (LOD) or as RDF stores. The SPARQL query language provides a very expressive way to search and explore this wealth of semantic data. However, user-friendly interfaces are needed to bridge the gap between end-users and SW formalisms. Navigation-based interfaces and natural language interfaces require no or little training, but they cover a small fragment of SPARQL's expressivity. We propose SQUALL, a query and update language that provides the full expressiveness of SPARQL~1.1 through a flexible controlled natural language (e.g., solution modifiers through superlatives, relational algebra through coordinations, filters through comparatives). A comprehensive and modular definition is given as a Montague grammar, and an evaluation of naturalness is done on the QALD challenge. SQUALL is conceived as a component of natural language interfaces, to be combined with lexicons, guided input, and contextual disambiguation. It is available as a Web service that translates SQUALL sentences to SPARQL, and submits them to SPARQL endpoints (e.g., DBpedia), therefore ensuring SW compliance, and leveraging the efficiency of SPARQL engines. |
Heterogeneity of data and data formats in bioinformatics often entail a mismatch between inputs and outputs of different services, making it difficult to compose them into workflows. To reduce those mismatches bioinformatics platforms propose ad'hoc converters written by hand. This article proposes to systematically detect convertibility from output types to input types. Convertibility detection relies on abstract types, close to XML Schema, allowing to abstract data while precisely accounting for its composite structure. Detection is accompanied by an automatic generation of converters between input and output XML data. Our experiment on bioinformatics services and datatypes, performed with an implementation of our approach, shows that the detected convertibilities and produced converters are relevant from a biological point of view. Furthermore they automatically produce a graph of potentially compatible services with a connectivity higher than with the ad'hoc approaches. |
Linked data is increasingly available through SPARQL endpoints, but exploration and question answering by regular Web users largely remain an open challenge. Users have to choose between the expressivity of formal languages such as SPARQL, and the usability of tools based on navigation and visualization. In a previous work, we have proposed Query-based Faceted Search (QFS) as a way to reconcile the expressivity of formal languages and the usability of faceted search. In this paper, we further reconcile QFS with scalability and portability by building QFS over SPARQL endpoints. We also improve expressivity and readability. Many SPARQL features are now covered: multidimensional queries, union, negation, optional, filters, aggregations, ordering. Queries are now verbalized in English, so that no knowledge of SPARQL is ever necessary. All of this is implemented in a portable Web application, Sparklis, and has been evaluated on many endpoints and questions. |
SPARKLIS is a Semantic Web tool that helps users explore SPARQL endpoints by guiding them in the interactive building of questions and answers, from simple ones to complex ones. It combines the fine-grained guidance of faceted search, most of the expressivity of SPARQL, and the readability of (controlled) natural languages. No endpoint-specific configuration is necessary, and no knowledge of SPARQL and the data schema is required from users. This demonstration paper is a companion to the research paper~\cite{Fer2014iswc}. |
2013 |
The Semantic Web is now made of billions of triples, which are available as Linked Open Data (LOD) or as RDF stores. The most common approach to access RDF datasets is through SPARQL, an expressive query language. However, SPARQL is difficult to learn for most users because it exhibits low-level notions of relational algebra such as union, filters, or grouping. We present SQUALL, a high-level language for querying and updating an RDF dataset. It has a strong compliance with RDF, covers all features of SPARQL 1.1, and has a controlled natural language syntax that completely abstracts from low-level notions. SQUALL is available as two web services: one for translating a SQUALL sentence to a SPARQL query or update, and another for directly querying a SPARQL endpoint such as DBpedia. |
Because the Web of Documents is composed of structured pages that are not meaningful to machines, search in the Web of Documents is generally processed by keywords. However, because the Web of Data provides structured information, search in the Web of Data can be more precise. SPARQL is the standard query language for querying this structured information. SPARQL is expressive and its syntax is similar to SQL. However, casual user can not write SPARQL queries. Sewelis is a search system for the Web of Data offering to explore data progressively and more user-friendly than SPARQL. Sewelis guides the search with a query built incrementally because users only have to select query elements in order to complete the query. However, Sewelis does not scale to large datasets such as DBpedia, which is composed of about 2 billion triples. In this report, we introduce Scalewelis. Scalewelis is a search system for the Web of Data that is similar to Sewelis but scalable. Moreover, Scalewelis is independent to data because it connects to SPARQL endpoints. We took part in a challenge on DBpedia with Scalewelis. We were able to answer to 70 questions out of 99 with acceptable response times. |
This paper reports on the participation of the system {\sc squall2sparql} in the QALD-3 question answering challenge for DBpedia. {\sc squall2sparql} is a translator from SQUALL, a controlled natural language for English, to SPARQL 1.1, a standard expressive query and update language for linked open data. It covers nearly all features of SPARQL 1.1, and is directly applicable to any SPARQL endpoint. |
This paper overviews the participation of Scalewelis in the QALD-3 open challenge. Scalewelis is a Faceted Search system. Faceted Search systems refine the result set at each navigation step. In Scalewelis, refinements are syntactic operations that modify the user query. Scalewelis uses the Semantic Web standards (URI, RDF, SPARQL) and connects to SPARQL endpoints. |
2012 |
Faceted search and querying are two well-known paradigms to search the Semantic Web. Querying languages, such as SPARQL, offer expressive means for searching RDF datasets, but they are difficult to use. Query assistants help users to write well-formed queries, but they do not prevent empty results. Faceted search supports exploratory search, i.e., guided navigation that returns rich feedbacks to users, and prevents them to fall in dead-ends (empty results). However, faceted search systems do not offer the same expressiveness as query languages. We introduce {\em Query-based Faceted Search} (QFS), the combination of an expressive query language and faceted search, to reconcile the two paradigms. We formalize the navigation of faceted search as a navigation graph, where navigation places are queries, and navigation links are query transformations. We prove that this navigation graph is {\em safe} (no dead-end), and {\em complete} (every query that is not a dead-end can be reached by navigation). In this paper, the LISQL query language generalizes existing semantic faceted search systems, and covers most features of SPARQL. A prototype, Sewelis, has been implemented, and a usability evaluation demonstrated that QFS retains the ease-of-use of faceted search, and enables users to build complex queries with little training. |
Les expressions mathématiques comptent pour une part importante dans les connaissances humaines. Nous en proposons une représentation en RDF afin de pouvoir les intégrer aux autres connaissances dans le Web sémantique. Nous étendons ensuite le langage de description et d'interrogation LISQL afin de concilier des représentations non-ambiguës, des requêtes expressives et des notations naturelles et concises. Par exemple, la requête exttt{int(...?X $\hat{~}$ 2...,?X)} permet de trouver les intégrales en~$x$ dont le corps contient la sous-expression~$x^2$. Tout cela permet d'utiliser Sewelis, un système d'information logique pour le Web sémantique, pour la représentation et l'exploration guidée d'expressions mathématiques. Ce guidage dispense les utilisateurs de maîtriser la syntaxe de LISQL et le vocabulaire tout en leur garantissant des expressions bien formées et des résultats à leurs requêtes. |
Formal languages play a central role in the Semantic Web. An important aspect regarding their design is syntax as it plays a crucial role in the wide acceptance of the Semantic Web approach. The main advantage of controlled natural languages (CNL) is to reconcile the high-level and natural syntax of natural languages, and the precision and lack of ambiguity of formal languages. In the context of the Semantic Web and Linked Open Data, CNL could not only allow more people to contribute by abstracting from the low-level details, but also make experienced people more productive, and make the produced documents easier to share and maintain. We introduce SQUALL, a controlled natural language for querying and updating RDF graphs. It has a strong adequacy with RDF, an expressiveness close to SPARQL 1.1, and a CNL syntax that completely abstracts from low-level notions such as bindings and relational algebra. We formally define the syntax and semantics of SQUALL as a Montague grammar, and its translation to SPARQL. It features disjunction, negation, quantifiers, built-in predicates, aggregations with grouping, and n-ary relations through reification. |
A number of information systems offer a limited exploration in that users can only navigate from one object to another object, e.g. navigating from folder to folder in file systems, or from page to page on the Web. An advantage of conceptual information systems is to provide navigation from concept to concept, and therefore from set of objects to set of objects. The main contribution of this paper is to push the exploration capability one step further, by providing navigation from set of concepts to set of concepts. Those sets of concepts are structured along a number of dimensions, thus forming a cube of concepts. We describe a number of representations of concepts, such as sets of objects, multisets of values, and aggregated values. We apply our approach to multi-valued contexts, which stand at an intermediate position between many-valued contexts and logical contexts. We explain how users can navigate from one cube of concepts to another. We show that this navigation includes and extends both conceptual navigation and OLAP operations on cubes. |
With the persistent deployment of ontological specifications in practice and the increasing size of the deployed ontologies, methodologies for ontology engineering are becoming more and more important. In particular, the specification of negative constraints is often neglected by the human expert, whereas they are crucial for increasing an ontology's deductive potential. % We propose a novel, arguably cognitively advantageous methodology for identifying and adding missing negative constraints to an existing ontology. To this end, a domain expert navigates through the space of satisfiable class expressions with the aim of finding absurd ones, which then can be forbidden by adding a respective constraint to the ontology. % We give the formal foundations of our approach, provide an implementation, called Possible World Explorer (PEW) and illustrate its usability by describing prototypical navigation paths using the example of the well-known pizza ontology. |
Quand un utilisateur crée un nouvel objet dans le Web s\'emantique, les outils existants n'exploitent ni les objets existants et leurs propri\'et\'es, ni les propri\'et\'es d\'ej\`a connues du nouvel objet. Nous proposons UTILIS, une m\'ethode d'aide \`a la cr\'eation de nouveaux objets. UTILIS cherche des objets similaires au nouvel objet en appliquant des r\`egles de relaxation \`a sa description. % Les propri\'et\'es des objets similaires servent de suggestions pour compl\'eter la description du nouvel objet. % Une \'etude utilisateur men\'ee avec des \'etudiants en master montre que les suggestions d'UTILIS ont \'et\'e utilis\'ees. Les utilisateurs ont trouv\'e les suggestions pertinentes : dans la plupart des cas, ils pouvaient trouver l'\'el\'ement recherch\'e dans les trois premiers ensembles de suggestions. De plus, ils les ont appr\'eci\'ees, car la majorit\'e souhaitent les avoir dans un \'editeur de donn\'ees du Web s\'emantique. |
With existing tools, when creating a new object in the Semantic Web, users benefit neither from existing objects and their properties, nor from the already known properties of the new object. % We propose UTILIS, an interactive process to help users add new objects. While creating a new object, relaxation rules are applied to its current description to find similar objects, whose properties serve as suggestions to expand the description. % A user study conducted on a group of master students shows that students, even the ones disconcerted by the unconventional interface, used UTILIS suggestions. In most cases, they could find the searched element in the first three sets of properties of similar objects. % Moreover, with UTILIS users did not create any duplicate whereas with the other tool used in the study more than half of them did. |
UTILIS (Updating Through Interaction in Logical Information Systems), introduced in a research paper at EKAW'12, is an interactive process to help users create new objects in a RDF graph. While creating a new object, relaxation rules are applied to its current description to find similar objects, whose properties serve as suggestions to expand the description. UTILIS is implemented in Sewelis, a system that reconciles the expressiveness of querying languages (e.g., SPARQL), and the benefits of exploratory search found in faceted search. The same interaction principles are used for both exploration and creation of semantic data. We illustrate the UTILIS approach by applying Sewelis to the semantic annotation of comic panels, reusing the dataset that was used for a user evaluation. |
We have explored in different perspectives on how categorial grammars can be considered as Logical Information Systems (LIS), where objects are organized and queried by logical properties, both theoretically and practically. LIS have also been considered for the development of pregroup grammars. We propose to illustrate these points with the CAMELIS tool that is an implementation of Logical Information Systems (LIS) and that has been developped at Irisa Rennes. CAMELIS may give another view on linguistic data, and provide an easy help to browse, to update, to create and to maintain or to test such data. |
2011 |
Since the beginning of data processing, the companies have realized the importance of information management solutions. The gathered data are a powerful asset to study the trends and make choices for the future. The Business Intelligence appeared in the mid-90s (the information synthesis to assist decision-making) with OLAP (On-Line Analytical Processing, a tools set for exploration, analysis and display of multidimensional data) and S-OLAP (Spatial OLAP, OLAP with spatial support). A OLAP user, unspecialized in computer sciences, does not need to know a language to handle multidimensional data, create graphics, etc. However, we consider that the OLAP data model is too rigid, because of its permanent multidimensionnal structure and because each content must have a single aggregate value. This observation is the starting point of this thesis. We propose a new paradigm of information system, able to analyze and explore multidimensional and multivalued data. To model this paradigm, we use the logical information systems (LIS) which is an information system that has common features with OLAP, especially on the data mining aspects. Our paradigm is defined by a flexible data model, an easy navigation and modular representation. We concluded this thesis by the application of this paradigm on several topics, including the exploration of geographic data. |
We have proposed an interactive fault localization method based on two data mining techniques, formal concept analysis and association rules. A lattice formalizes the partial ordering and the dependencies between the sets of program elements (e.g., lines) that are most likely to lead to program execution failures. The paper provides an algorithm to traverse that lattice starting from the most suspect places. The main contribution is that the algorithm is able to deal with any number of faults within a single execution of a test suite. In addition, a stopping criterion independent of the number of faults is provided. |
Data mining techniques are used in order to discover emerging knowledge (patterns) in databases. The problem of such techniques is that there are, in general, too many resulting patterns for a user to explore them all by hand. Some methods try to reduce the number of patterns without a priori pruning. The number of patterns remains, nevertheless, high. Other approaches, based on a total ranking, propose to show to the user the top-k patterns with respect to a measure. Those methods do not take into account the user's knowledge and the dependencies that exist between patterns. In this paper, we propose a new way for the user to explore extracted patterns. The method is based on navigation in a partial order over the set of all patterns in the Logical Concept Analysis framework. It accommodates several kinds of patterns and the dependencies between patterns are taken into account thanks to partial orders. It allows the user to use his/her background knowledge to navigate through the partial order, without a priori pruning. We illustrate how our method can be applied on two different tasks (software engineering and natural language processing) and two different kinds of patterns (association rules and sequential patterns). |
Logical Information Systems (LIS) are based on Logical Concept Analysis, an extension of Formal Concept Analysis. This paper describes an application of LIS to support group decision. A case study gathered a research team. The objective was to decide on a set of potential conferences on which to send submissions. People individually used Abilis, a LIS web server, to preselect a set of conferences. Starting from 1041 call for papers, the individual participants preselected 63 conferences. They met and collectively used Abilis to select a shared set of 42 target conferences. The team could then sketch a publication planning. The case study provides evidence that LIS cover at least three of the collaboration patterns identified by Kolfschoten, de Vreede and Briggs. Abilis helped the team to build a more complete and relevant set of information (Generate/Gathering pattern); to build a shared understanding of the relevant information (Clarify/Building Shared Understanding); and to quickly reduce the number of target conferences (Reduce/Filtering pattern). |
Faceted search and querying are two well-known paradigms to search the Semantic Web. Querying languages, such as SPARQL, offer expressive means for searching RDF datasets, but they are difficult to use. Query assistants help users to write well-formed queries, but they do not prevent empty results. Faceted search supports exploratory search, i.e., guided navigation that returns rich feedbacks to users, and prevents them to fall in dead-ends (empty results). However, faceted search systems do not offer the same expressiveness as query languages. We introduce Query-based Faceted Search (QFS), the combination of an expressive query language and faceted search, to reconcile the two paradigms. In this paper, the LISQL query language generalizes existing semantic faceted search systems, and covers most features of SPARQL. A prototype, Sewelis (aka. Camelis 2), has been implemented, and a usability evaluation demonstrated that QFS retains the ease-of-use of faceted search, and enables users to build complex queries with little training. |
Faceted search and querying are the two main paradigms to search the Semantic Web. Querying languages, such as SPARQL, offer expressive means for searching knowledge bases, but they are difficult to use. Query assistants help users to write well-formed queries, but they do not prevent empty results. Faceted search supports exploratory search, i.e., guided navigation that returns rich feedbacks to users, and prevents them to fall in dead-ends (empty results). However, faceted search systems do not offer the same expressiveness as query languages. We introduce semantic faceted search, the combination of an expressive query language and faceted search to reconcile the two paradigms. The query language is basically SPARQL, but with a syntax that better fits in a faceted search interface. A prototype, Camelis 2, has been implemented, and a usability evaluation demonstrated that semantic faceted search retains the ease-of-use of faceted search, and enables users to build complex queries with little training. |
La mise à jour des bases de connaissances existantes est cruciale pour tenir compte des nouvelles informations, régulièrement découvertes. Toutefois, les données actuelles du Web Sémantique sont rarement mises à jour par les utilisateurs. Les utilisateurs ne sont pas suffisament aidés lors de l'ajout et de la mise à jour d'objets. Nous proposons une approche pour aider l'utilisateur à ajouter de nouveaux objets de manière incrémentale et dynamique. Notre approche est fondée sur les Systèmes d'Information Logiques pour l'interaction utilisateur. Pour le guidage, le système cherche les objets ayant des propriétés en commun avec la description de l'objet en cours de création. Les propriétés de ces objets, non présents dans la description, servent de suggestions pour compléter la description de l'objet. |
Updating existing knowledge bases is crucial to take into account the information that are regularly discovered. However, this is quite tedious and in practice Semantic Web data are rarely updated by users. This paper presents UTILIS, an approach to help users create and update objects in RDF(S) bases. While creating a new object, $o$, UTILIS searches for similar objects, found by applying relaxation rules to the description of $o$, taken as a query. The resulting objects and their properties serve as suggestions to expand the description of $o$. |
Languages play a central role in the Semantic Web. An important aspect regarding their design is syntax as it plays a crucial role in the wide acceptance of the Semantic Web approach. Like for programming languages, an evolution can be observed from low-level to high-level designs. High-level languages not only allow more people to contribute by abstracting from the details, but also makes experienced people more productive, and makes the produced documents easier to share and maintain. We introduce SQUALL, a high-level language for querying and updating semantic data. It has a strong adequacy with RDF, an expressiveness very similar to SPARQL 1.1, and a controlled natural language syntax that completely abstracts from low-level notions such as bindings and relational algebra. We first give an informal presentation of SQUALL through examples, comparing it with SPARQL. We then formally define the syntax and semantics of SQUALL as a Montague grammar, and its translation to SPARQL. |
Faceted search and querying are the two main paradigms to search the Semantic Web. Querying languages, such as SPARQL, offer expressive means for searching knowledge bases, but they are difficult to use. Query assistants help users to write well-formed queries, but they do not prevent empty results. Faceted search supports exploratory search, i.e., guided navigation that returns rich feedbacks to users, and prevents them to make navigation steps that lead to empty results (dead-ends). However, faceted search systems do not offer the same expressiveness as query languages. We introduce {\em semantic faceted search}, the combination of an expressive query language and faceted search to reconcile the two paradigms. The query language is basically SPARQL, but with a syntax that extends Turtle with disjunction and negation, and that better fits in a faceted search interface: LISQL. We formalize the navigation of faceted search as a navigation graph, where nodes are queries, and navigation links are query transformations. We prove that this navigation graph is {\em safe} (no dead-end), and {\em complete} (every query that is not a dead-end can be reached by navigation). That formalization itself is a contribution to faceted search. \KILL{The expressiveness of LISQL is shown comparable to SPARQL, and they are based on the same relational algebra.} A prototype, Camelis~2, has been implemented, and a usability evaluation with graduate students demonstrated that semantic faceted search retains the ease-of-use of faceted search, and enables most users to build complex queries with little training. |
Query-based Faceted Search (QFS), introduced in a research paper at ISWC'11, reconciles the expressiveness of querying languages (e.g., SPARQL), and the benefits of exploratory search found in faceted search. Because of the interactive nature of QFS, which is difficult to fully render in a research paper, we feel it is important to complement it with a demonstration of our QFS prototype, Sewelis (aka. Camelis 2). An important addition to the research paper is the extension of QFS to the guided edition of RDF bases, where suggestions are based on existing data. This paper motivates our approach, shortly presents Sewelis, and announces the program of the demonstration. Screencasts of the demonstration, as well as material (program and data) to reproduce it, are available at { t http://www.irisa.fr/LIS/softwares/sewelis}. |
2010 |
Dans le domaine des bases de données, les outils de calcul de règles d'association et de dépendances fonctionnelles affichent traditionnellement les résultats sous forme d'une liste de règles, difficiles à lire. Nous proposons ici de projeter une relation d'une base de données sur un cube de données OLAP, afin d'afficher ces règles de manière plus structurée et plus intuitive. De plus, nous montrons que les liens de navigation d'OLAP peuvent aider l'utilisateur à naviguer dans ces règles produites. |
Discovering dependencies in data is a well-know problem in database theory. The most common rules are Functional Dependencies (FDs), Conditional Functional Dependencies (CFDs) and Association Rules (ARs). Many tools can display those rules as lists, but those lists are often too long for inspection by users. We propose a new way to display and navigate through those rules. Display is based on On-Line Analytical Processing (OLAP), presenting a set of rules as a cube, where dimensions correspond to the premises of rules. Cubes reflect the hierarchy that exists between FDs, CFDs and ARs. Navigation is based on a lattice, where nodes are OLAP views, and edges are OLAP navigation links, and guides users from cube to cube. We present an illustrative example with the help of our prototype. |
Concept lattices have been successfully used for information retrieval and browsing. They offer the advantage of combining querying and navigation in a consistent way. Conceptual navigation is more flexible than hierarchical navigation, and easier to use than plain querying. It has already been applied to formal, logical, and relational contexts, but its application to the semantic web is a challenge because of inference mechanisms and expressive query languages such as SPARQL. The contribution of this paper is to extend conceptual navigation to the browsing of RDF graphs, where concepts are accessed through SPARQL-like queries. This extended conceptual navigation is proved consistent w.r.t. the context (i.e., never leads to an empty result set), and complete w.r.t. the conjunctive fragment of the query language (i.e., every query can be reached by navigation only). Our query language has an expressivity similar to SPARQL, and has a more natural syntax close to description logics. |
We explore different perspectives on how categorial grammars can be considered as Logical Information Systems (LIS) both theoretically, and practically. Categorial grammars already have close connections with logic. We discuss the advantages of integrating both approaches. We consider more generally different ways of connecting computational linguistic data and LIS as an application of Formal Concept Analysis. |
2009 |
Since the arrival of digital cameras, many people are faced to the challenge of organizing and browsing the overwhelming flood of photos their life produces. The same is true for all sorts of documents, e.g.~emails, audio files. Existing systems either let users fill query boxes without any assistance, or drive them through rigid navigation structures (e.g., hierarchies); or they do not let users put annotations on their documents, even when this would support the organization and retrieval of any documents on customized criteria. We present a tool, {\sc Camelis}, that offers users with an organization that is dynamically computed from documents and their annotations. {\sc Camelis} is designed along the lines of Logical Information Systems (LIS), which are founded on logical concept analysis. Hence, (1) an expressive language can be used to describe photos and query the collection, (2) manual and automatic annotations can be smoothly integrated, and (3) expressive querying and flexible navigation can be mixed in a same search and in any order. This presentation is illustrated on a real collection of more than 5,000 photos. |
De nombreuses décisions sont prises en commission, par exemple pour affecter des ressources. Les critères de décision sont difficiles à exprimer et la situation globale est en général trop complexe pour que les participants puissent l'appréhender pleinement. Dans cet article, nous décrivons un processus de décision où l'analyse de concepts est utilisée pour faire face à ces problèmes. Grâce à l'analyse de concepts, les personnes fair play ont la possibilité d'être équitables envers les candidats et de faire preuve de cohérence dans leurs jugements sur toute la durée de la réunion. |
Formal concept analysis is recognized as a good paradigm for browsing data sets. Besides browsing, update and complex data are other important aspects of information systems. To have an efficient implementation of concept-based information systems is difficult because of the diversity of complex data and the computation of conceptual structures, but essential for the scalability to real-world applications. We propose to decompose contexts into simpler and specialized components: logical context functors. We demonstrate this allows for scalable implementations, updatable ontologies, and richer navigation structures, while retaining genericity. |
Exploratory search is about browsing and understanding an information base. It requires a more interactive process than retrieval search, where the user sends a query and the system returns answers. Logical Information Systems (LIS) support exploratory search by guiding users in the construction of queries, and by giving summaries of query results. The contribution of this paper is to adapt and extend LIS to the Semantic Web. We define a summarization and navigation data structure that provides rich views over data, and guides users from view to view. This guiding is proved consistent (i.e., never leads to an empty result set), and complete (i.e., every query can be reached by navigation only). The query language covers a large fragment of SPARQL, and is more concise by using a syntax close to description logics. Our approach could be implemented on top of existing tools for storing, reasoning and querying. |
2008 |
Today, the thematic layer is still the prevailling structure in geomatics for handling geographical information. However, the layer model is rigid: it implies partitionning geographical data in predefined categories and using the same description schema for all elements of a layer. Recently, Logical Information Systems (LIS) introduced a new paradigm for information management and retrieval. Using LIS, we propose a more flexible organisation of vectorial geographical data at a thiner level since it is centered on the geographical feature. LIS do not rely on a hierarchical organisation of information, and enable to tightly combine querying and navigation. In this article, we present the use of LIS to handle geographical data. In particular, we detail a data model for geographical features and the corresponding querying and navigation model. These models have been implemented in the GEOLIS prototype, which has been used to lead experiments on real data. |
Formal Concept Analysis (FCA) is a natural framework to learn from examples. Indeed, learning from examples results in sets of frequent concepts whose extent contains mostly these examples. In terms of association rules, the above learning strategy can be seen as searching the premises of rules where the consequence is set. In its most classical setting, FCA considers attributes as a non-ordered set. When attributes of the context are partially ordered to form a taxonomy, Conceptual Scaling allows the taxonomy to be taken into account by producing a context completed with all attributes deduced from the taxonomy. The drawback, however, is that concept intents contain redundant information. In this article, we propose a parameterized algorithm, to learn rules in the presence of a taxonomy. It works on a non-completed context. The taxonomy is taken into account during the computation so as to remove all redundancies from intents. Simply changing one of its operations, this parameterized algorithm can compute various kinds of concept-based rules. We present instantiations of the parameterized algorithm to learn rules as well as to compute the set of frequent concepts. |
The semantic web aims at enabling the web to understand and answer the requests from people and machines. It relies on several standards for representing and reasoning about web contents. Among them, the Web Ontology Language (OWL) is used to define ontologies, i.e. knowledge bases, and is formalized with description logics. In this paper, we demonstrate how dynamic taxonomies and their benefits can be transposed to browse OWL~DL ontologies. We only assume the ontology has an assertional part, i.e. defines objects and not only concepts. The existence of relations between objects in OWL leads us to define new navigation modes for crossing these relations. A prototype, Odalisque, has been developed on top of well-known tools for the semantic web. |
Because of the expansion of geo-positioning tools and the democratization of geographical information, the amount of geo-localized data that is available around the world keeps increasing. So, the ability to efficiently retrieve informations in function of their geographical facet is an important issue. In addition to individual properties such as position and shape, spatial relations between objects are an important criteria for selecting and reaching objects of interest: e.g., given a set of touristic points, selecting those having a nearby hotel or reaching the nearby hotels. In this paper, we propose Logical Concept Analysis (LCA) and its handling of relations for representing and reasoning on various kinds of spatial relations: e.g., Euclidean distance, topological relations. Furthermore, we present an original way of navigating in geolocalized data, and compare the benefits of our approach with traditional Geographical Information Systems (GIS). |
Recent work in fault localization crosschecks traces of correct and failing execution traces. The implicit underlying technique is to search for association rules which indicate that executing a particular source line will cause the whole execution to fail. This technique, however, has limitations. In this article, we first propose to consider more expressive association rules where several lines imply failure. We then propose to use Formal Concept Analysis (FCA) to analyze the resulting numerous rules in order to improve the readability of the information contained in the rules. The main contribution of this article is to show that applying two data mining techniques, association rules and FCA, produces better results than existing fault localization techniques. |
In academia, many decisions are taken in committee, for example to hire people or to allocate resources. Genuine people often leave such meetings quite frustrated. Indeed, it is intrinsically hard to make multi-criteria decisions, selection criteria are hard to express and the global picture is too large for participants to embrace it fully. In this article, we describe a recruiting process where logical concept analysis and formal concept analysis are used to address the above problems. We do not pretend to totally eliminate the arbitrary side of the decision. We claim, however, that, thanks to concept analysis, genuine people have the possibility to 1) be fair with the candidates, 2) make a decision adapted to the circumstances, 3) smoothly express the rationales of decisions, 4) be consistent in their judgements during the whole meeting, 5) vote (or be arbitrary) only when all possibilities for consensus have been exhausted, and 6) make sure that the result, in general a total order, is consistent with the partial orders resulting from the multiple criteria. |
taux acceptation 19/70 = 27\% |
Dynamic taxonomies and faceted search are increasingly used to organize and browse document collections. The main function of dynamic taxonomies is to start with the full collection, and zoom-in to a small enough subset of items for direct inspection. In this paper, we present other navigation modes than zoom-in for less directed and more exploratory browsing of a document collection. The presented navigation modes are zoom-out, shift, pivot, and querying by examples. These modes correspond to query transformations, and make use of boolean operators. Therefore, the current focus is always clearly specified by a query. |
2007 |
Geographical data are mainly structured in layers of information. However, this model of organisation is not convenient for navigation inside a dataset, and so limits geographical data exploration to querying. We think information retrieval could be made easier in GIS by the introduction of a navigation based on geographical object properties. For this purpose, we propose a prototype, GEOLIS1, which tightly combines querying and navigation in the search process of geographical data. GEOLIS relies on Logical Information Systems (LIS), which are based on Formal Concept Analysis (FCA) and logics. In this paper, we detail data organisation and navigation process in GEOLIS. We also present the results of an experimentation led on a real dataset. |
Formal Concept Analysis (FCA) is a natural framework for learning from positive and negative examples. Indeed, learning from examples results in sets of frequent concepts whose extent contains only these examples. In terms of association rules, the above learning strategy can be seen as searching the premises of exact rules where the consequence is fixed. In its most classical setting, FCA considers attributes as a non-ordered set. When attributes of the context are ordered, Conceptual Scaling allows the related taxonomy to be taken into account by producing a context completed with all attributes deduced from the taxonomy. The drawback, however, is that concept intents contain redundant information. In this article, we propose a parameterized generalization of a previously proposed algorithm, in order to learn rules in the presence of a taxonomy. The taxonomy is taken into account during the computation so as to remove all redundancies from intents. Simply changing one component, this parameterized algorithm can compute various kinds of concept-based rules. We present instantiations of the parameterized algorithm for learning positive and negative rules. |
Since the arrival of digital cameras, many people are faced to the challenge of organizing and retrieving the overwhelming flow of photos their life produces. Most people put no metadata on their photos, and we believe this is because existing tools make a very limited use of them. We present a tool, Camelis, that offers users with an organization of photos that is dynamically computed from the metadata, making worthwhile the effort to produce it. Camelis is designed along the lines of Logical Information Systems (LIS), which are founded on logical concept analysis. Hence, (1) an expressive language can be used to describe photos and query the collection, (2) manual and automatic metadata can be smoothly integrated, and (3) expressive querying and flexible navigation can be mixed in a same search and in any order. This presentation is illustrated by experiences on a real collection of more than 5000 photos. |
Strings are an important part of most real application multi-valued contexts. Their conceptual treatment requires the definition of {\em substring scales}, i.e., sets of relevant substrings, so as to form informative concepts. However these scales are either defined by hand, or derived in a context-unaware manner (e.g., all words occuring in string values). We present an efficient algorithm based on suffix trees that produces complete and concise substring scales. Completeness ensures that every possible concept is formed, like when considering the scale of all substrings. Conciseness ensures the number of scale attributes (substrings) is less than the cumulated size of all string values. This algorithm is integrated in Camelis, and illustrated on the set of all ICCS paper titles. |
Dynamic taxonomies have been proposed as a solution for combining querying and navigation, offering both expressivity and interactivity. Navigation is based on the filtering of a multidimensional taxonomy w.r.t. query answers, which helps users to focus their search. We show that properties that are commonly used only in queries can be integrated in taxonomies, and hence in navigation, by the use of so-called logics. Hand-designed taxonomies and concrete domains (e.g., dates, strings) can be combined so as to form complex taxonomies. For instance, valued attributes can be handled, and different roles between documents and locations can be distinguished. Logical Information Systems (LIS) are characterized by the combination of querying and navigation, and the systematic use of logics. |
2006 |
Today, the thematic layer is still the prevailling structure in geomatics for handling geographical information. However, the layer model is rigid: it implies partitionning geographical data in predefined categories and using the same description schema for all elements of a layer. Recently, Logical Information Systems (LIS) introduced a new paradigm for information management and retrieval. Using LIS, we propose a more flexible organisation of vectorial geographical data at a thiner level since it is centered on the geographical feature. LIS does not rely on a hierarchical organisation of information, and enable to tightly combine querying and navigation in a same search. In this article, we present a work in progress about the use of LIS model to handle geographical data. In particular, we detail a data model for geographical features and the corresponding querying and navigation model. These models have been implemented in the GEOLIS prototype, which has been used to lead experiments with real data. |
Formal Concept Analysis (FCA) considers attributes as a non-ordered set. This is appropriate when the data set is not structured. When an attribute taxonomy exists, existing techniques produce a completed context with all attributes deduced from the taxonomy. Usual algorithms can then be applied on the completed context for finding frequent concepts, but the results systematically contain redundant information. This article describes an algorithm which allows the frequent concepts of a formal context with taxonomy to be computed. It works on a non-completed context and uses the taxonomy information when needed. The results avoid the redundancy problem with equivalent performance. |
Logic Functors form a framework for specifying new logics, and deriving automatically theorem provers and consistency/completeness diagnoses. Atomic functors are logics for manipulating symbols and concrete domains, while other functors are logic transformers that may add connectives or recursive structures, or may alter the semantics of a logic. The semantic structure of the framework is model theoretic as opposed to the verifunctional style often used in classical logic. This comes close to the semantics of description logics, and we show indeed that the logic~${\cal ALC}$ can be rebuilt using logic functors. This offers the immediate advantage that variants of~${\cal ALC}$ can be explored and implemented almost for free. This report comes with extensive appendices describing in detail a toolbox of logic functors (definitions, algorithms, theorems, and proofs). |
2005 |
Many application domains make use of specific data structures such as sequences and graphs to represent knowledge. These data structures are ill-fitted to the standard representations used in machine learning and data-mining algorithms: propositional representations are not expressive enough, and first order ones are not efficient enough. In order to efficiently represent and reason on these data structures, and the complex patterns that are related to them, we use domain-specific logics. We show these logics can be built by the composition of logical components that model elementary data structures. The standard strategies of top-down and bottom-up search are ill-suited to some of these logics, and lack flexibility. We therefore introduce a dichotomic search strategy, that is analogous to a dichotomic search in an ordered array. We prove this provides more flexibility in the search, while retaining completeness and non-redundancy. We present a novel algorithm for learning using domain specific logics and dichotomic search, and analyse its complexity. We also describe two applications which illustrates the search for motifs in sequences; where these motifs have arbitrary length and length-constrained gaps. In the first application sequences represent the trains of the East-West challenge; in the second application they represent the secondary structure of Yeast proteins for the discrimination of their biological functions. |
A logical view of formal concept analysis considers attributes of a formal context as unary predicates. In a first part, we propose an augmented definition that handles {\em binary relations} between objects. A Galois connection is defined on augmented contexts. It represents concept inheritance as usual, but also relations between concepts. As usual, labeling operators are also defined. In particular, concepts and relations are visible and labeled in a single structure. In a second part, we show how relations can be used for navigating in an augmented concept lattice. This part augments the theory of Logical Information Systems. An implementation is sketched, and first experimental results are presented. |
We present Logical Information Systems (LIS). A LIS can be viewed as a schema-less database whose objects are described by logical formulas. Objects are automatically organized according to their logical description, and logical formulas can be used for representing both queries and navigation links. The key feature of a LIS is that it answers a query with a set of navigation links expressed in the same logic as the query. As navigation links are dynamically computed from any query, and can be used as query increments, it follows that querying and navigation steps can be combined in any order. We then present LISFS, a file-system implementation of a LIS, where objects are files or parts of files. This has the benefit to make LIS features available right now to existing applications. This implementation can easily be extended and specialized through a plug-in mechanism. Finally, we present some applications in the field of personal databases (e.g., music, images, emails), and demonstrate that building specialized interfaces for visualizing databases can be done easily through LISFS navigation. |
2004 |
Logical information systems (LIS) use logic in a uniform way to describe their contents, to query it, to navigate through it, to analyze it, and to maintain it. They can be given an abstract specification that does not depend on the choice of a particular logic, and concrete instances can be obtained by instantiating this specification with a particular logic. In fact, a logic plays in a LIS the role of a schema in databases. We present the principles of LIS, the constraints they impose on the expression of logics, and hints for their effective implementation. |
BLID (Bio-Logical Intelligent Database) is a bioinformatic system designed to help biologists extract new knowledge from raw genome data by providing high-level facilities for both data browsing and analysis. We describe BLIDrsquos novel data browsing system which is based on the idea of Logical Information Systems. This enables combined querying and navigation of data in BLID (extracted from public bioinformatic repositories). The browsing language is a logic especially designed for bioinformatics. It currently includes sequence motifs, taxonomies, and macromolecule structures, and it is designed to be easily extensible, as it is composed of reusable components. Navigation is tightly combined with this logic, and assists users in browsing a genome through a form of human-computer dialog. |
2003 |
2002 |
Les deux principaux paradigmes de recherche d'information, la navigation et l'interrogation, sont souvent dissociés. Les systèmes hiérarchiques offrent une structure de navigation figée qui ne convient pas à toutes les utilisations ; ce qu'ils compensent par des outils de recherche. Ceux-ci, fondés sur l'interrogation, sont plus souples mais sont plus difficiles à utiliser pour les non-initiés et rendent délicat le contrôle du volume des réponses. Il apparaît donc comme nécessaire de combiner étroitement navigation et interrogation. Pour réaliser cette combinaison, nous nous fondons sur l'Analyse de concepts (AC) qui permet de construire automatiquement, à partir d'une description des objets, une structure de navigation appelée «treillis de concepts», où les concepts jouent à la fois le rôle de répertoire et de requête. Comme dans l'AC les descriptions se limitent à des ensembles d'attributs, nous avons généralisé l'AC pour les remplacer par des formules d'une logique arbitraire. Ceci nous semble important pour traiter des applications diverses. Les Systèmes d'information logiques (SIL) se définissent donc par la combinaison navigation/interrogation, l'emploi de la logique (descriptions, requêtes et liens de navigation) et la généricité. Sur cette base, nous avons développé plusieurs mécanismes pour faciliter l'expression et la découverte de connaissances. Les connaissances d'un domaine peut être exprimées par une terminologie. Un dialogue homme-machine, fondé sur le treillis de concepts, permet de retrouver des objets (navigation) et de découvrir des régularités entre les objets (extraction de connaissances). Un mécanisme d'apprentissage offre une assistance à la classification des objets. Enfin, un prototype a été développé pour d'expérimenter ces mécanismes. Il est générique dans le sens où il ne dépend pas de la logique employée. Ces logiques peuvent être assemblés à l'aide d'un jeu de composants logique, que nous avons constitué. |
A formal context associates to objects a description that combines automatically extracted properties (intrinsic) and manually assigned ones (extrinsic). The extrinsic properties are expressed by users according to intentions that are often subjective and changing, and determine the classification and retrieval of objects. So, we find it important to assist users in this task through the automatic suggestion of extrinsic properties to be assigned and even the discovery of rules to automate these assignements. The principle is to learn from the description of existing objects the extrinsic description of a new object. Because of the changing nature of users' intentions, the assistance given in the incremental building of a logical context must be interactive. We present formal principles, and an application to the classification of email messages. |
Formal Concept Analysis (FCA) is interested in the formation of concept lattices from binary relations between objects and attributes, a.k.a. contexts. Many algorithms have been proposed to generate the set of all concepts, and also the edges of the lattice between these concepts. We develop the principle and the code of a new algorithm combining two existing ones, Godin's and Bordat's algorithms. Then, we show by both a theoretical and practical study that it is the most efficient algorithm for sparse contexts, which are usually found in real applications. |
Logical Information Systems (LIS) use logic in a uniform way to describe their contents, to query it, to navigate through it, to analyze it, and to maintain it. They can be given an abstract specification that does not depend on the choice of a particular logic, and concrete instances can be obtained by instantiating this specification with a particular logic. In fact, a logic plays in a LIS the role of a schema in data-bases. We present the principles of logical information systems, the constraints they impose on the expression of logics, and hints for their effective implementation. |
Logic-based applications often use customized logics which are composed of several logics. These customized logics are also often embedded as a black-box in an application. So, implementing them requires the specification of a well-defined interface with common operations such as a parser, a printer, and a theorem prover. In order to be able to compose these logic, one must also define composition laws, and prove their properties. We present the principles of logic functors and their compositions for constructing logics that are ad-hoc, but sound. An important issue is how the operations of different sublogics inter-operate. We propose a formalization of the logic functors, their semantics, implementations, proof-theoretic properties, and their composition. |
2001 |
We present a generalization of logic All I Know by presenting it as an extension of standard modal logics. We study how this logic can be used to represent complete and incomplete knowledge in Logical Information Systems. In these information systems, a knowledge base is a collection of objects (e.g., files, bibliographical items) described in the same logic as used for expressing queries. We show that usual All I Know (transitive and euclidean accessibility relation) is convenient for representing complete knowledge, but not for incomplete knowledge. For this, we use \emph{serial} All I Know (serial accessibility relation). |
Logic-based applications often use customized logics which are composed of several logics. These customized logics are also often embedded as a black-box in an application. Their implementation requires the specification of a well-defined interface with common operations such as a parser, a printer, and a theorem prover. In order to be able to compose these logics, one must also define composition laws, and prove their properties. We present the principles of logic functors and their compositions for constructing customized logics. An important issue is how the operations of different sublogics inter-operate. We propose a formalization of the logic functors, their semantics, implementations, and their composition. |
Logical Concept Analysis is Formal Concept Analysis where logical formulas replace sets of attributes. We define a Logical Information System that combines navigation and querying for searching for objects. Places and queries are unified as formal concepts represented by logical formulas. Answers can be both extensional (objects belonging to a concept) and intensional (formulas refining a concept). Thus, all facets of navigation are formalized in terms of Logical Concept Analysis. We show that the definition of being a refinement of some concept is a specific case of Knowledge Discovery in a formal context. It can be generalized to recover more classical KD~operations like machine-learning through the computation of necessary or sufficient properties (modulo some confidence), or data-mining through association rules. |
2000 |
We present the design of a file system whose organization is based on Concept Analysis ``à la Wille-Ganter''. The aim is to combine querying and navigation facilities in one formalism. The file system is supposed to offer a standard interface but the interpretation of common notions like directories is new. The contents of a file system is interpreted as a Formal Context, directories as Formal Concepts, and the sub-directory relation as Formal Concepts inclusion. We present an organization that allows for an efficient implementation of such a Conceptual File System. |
We propose a generalization of Formal Concept Analysis (FCA) in which sets of attributes are replaced by expressions of an almost arbitrary logic. We prove that all FCA can be reconstructed on this basis. We show that from any logic that is used in place of sets of attributes can be derived a contextualized logic that takes into account the formal context and that is isomorphic to the concept lattice. We then justify the generalization of FCA compared with existing extensions and in the perspective of its application to information systems. |
1999 |
Nous proposons une généralisation de l'analyse de concepts formels (ACF) dans laquelle les ensembles d'attributs sont remplacés par des expressions d'une logique presque arbitraire. Nous prouvons que toute l'ACF peut être reconstruite sur cette base. Nous montrons qu'à partir de toute logique utilisée à la place des ensembles d'attributs, on peut dériver une logique contextualisée qui prend en compte le contexte formel et qui est isomorphe au treillis de concepts. Nous comparons ensuite la généralisation de l'ACF aux extensions qui y ont déjà été apportées. Enfin, nous présentons nos perspectives d'application aux systèmes d'information. |
FCA,logic,SI |
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All person copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Les documents contenus dans ces répertoires sont rendus disponibles par les auteurs qui y ont contribué en vue d'assurer la diffusion à temps de travaux savants et techniques sur une base non-commerciale. Les droits de copie et autres droits sont gardés par les auteurs et par les détenteurs du copyright, en dépit du fait qu'ils présentent ici leurs travaux sous forme électronique. Les personnes copiant ces informations doivent adhérer aux termes et contraintes couverts par le copyright de chaque auteur. Ces travaux ne peuvent pas être rendus disponibles ailleurs sans la permission explicite du détenteur du copyright.
This document was translated from BibTEX by bibtex2html