Classification in areas (2024-02-10)

Class? est un jeu dans lequel les joueurs doivent organiser leurs cartes en fonction d’une classification cachée. Les cartes posées par les autres joueurs leur permettent de deviner où mettre les leurs. Il a été conçu pour que des écoliers appréhendent que les mêmes objets peuvent être classés de différentes manières et qu’il est possible de transmettre une classification sans l’expliciter. Le jeu fait appel a des notions qui se présentent facilement à l’aide des cartes à jouer comme des ensembles définis par des conditions nécessaires et suffisantes (classes). Cela permet d’introduire des classifications hiérarchiques et des notions algorithmiques (tests de conditions, récursion) pour les manipuler. Enfin, il nécessite de raisonner logiquement sur ces notions. Class? a été joué avec succès par des élèves du CM2 à la seconde. Nous nous sommes donc posé la question de son positionnement en tant que ressource pédagogique. Il apparait tout d’abord qu’il ne semble pas illustrer de concepts particulièrement mis en avant par les programmes officiels de l’éducation nationale. Il offre plutôt une manière alternative de renforcer des notions transversales très importantes en informatique. Nous caractérisons Class? par rapport aux efforts d’informatique sans ordinateurs et à d’autres jeux utilisables à cette fin. Finalement, nous discutons d’une décomposition de Class? en une succession de jeux plus simples permettant d’introduire les notions impliquées l’une après l’autre.

The Semantic Web is an extension of the web that enables people to express knowledge in a way that machines can reason with it. At the web scale, this knowledge may be described using different ontologies, and alignments have been defined to express these differences. Furthermore, the same individual may be represented by different instances in different datasets. Dealing with knowledge heterogeneity in the Semantic Web requires comparing these knowledge structures. Our objective is to understand heterogeneity and benefit from this understanding, not to reduce diversity. In this context, we have studied and contributed to techniques and measures for comparing knowledge structures on the Semantic Web along three dimensions: ontologies, alignments, and instances. At the ontology level, we propose measures for the ontology space and alignment space. The first family of measures relies solely on the content of ontologies, while the second one takes advantage of alignments between ontologies. At the alignment level, we investigate how to assess the quality of alignments. First, we study how to extend classical controlled evaluation measures by considering the semantics of aligned ontologies while relaxing the all-or-nothing nature of logical entailment. We also propose estimating the quality of alignments when no reference alignment is available. At the instance level, we tackle the challenge of identifying resources from different knowledge graphs that represent the same entity. We follow an approach based on keys and alignments. Specifically, we propose the notion of a link key, algorithms for extracting them, and measures to assess their quality. Finally, we recast this work in the perspective of the dynamics and evolution of knowledge.

Relational concept analysis (RCA) is an extension of formal concept analysis allowing to deal with several related contexts simultaneously. It has been designed for learning description logic theories from data and used within various applications. A puzzling observation about RCA is that it returns a single family of concept lattices although, when the data feature circular dependencies, other solutions may be considered acceptable. The semantics of RCA, provided in an operational way, does not shed light on this issue. In this report, we define these acceptable solutions as those families of concept lattices which belong to the space determined by the initial contexts (well-formed), cannot scale new attributes (saturated), and refer only to concepts of the family (self-supported). We adopt a functional view on the RCA process by defining the space of well-formed solutions and two functions on that space: one expansive and the other contractive. We show that the acceptable solutions are the common fixed points of both functions. This is achieved step-by-step by starting from a minimal version of RCA that considers only one single context defined on a space of contexts and a space of lattices. These spaces are then joined into a single space of context-lattice pairs, which is further extended to a space of indexed families of context-lattice pairs representing the objects manipulated by RCA. We show that RCA returns the least element of the set of acceptable solutions. In addition, it is possible to build dually an operation that generates its greatest element. The set of acceptable solutions is a complete sublattice of the interval between these two elements. Its structure and how the defined functions traverse it are studied in detail.

Class? is an enjoyable card game aiming at grouping colourful cards into meaningful classes. It illustrates facets of reasoning with classifications. In order to introduce Class? progressively, this small gamebook provides a sequence of games before getting to the Class? game itself and beyond. The games are presented in increasing order of difficulty so that a game will benefit from mastering of previous ones.

The discovery of link keys between two RDF datasets allows the identification of individuals which share common key characteristics. Actually link keys correspond to closed sets of a specific Galois connection and can be discovered thanks to an FCA-based algorithm. In this paper, given a pattern concept lattice where each concept intent is a link key candidate, we aim at identifying the most relevant candidates w.r.t adapted quality measures. To achieve this task, we introduce the "Sandwich" algorithm which is based on a combination of two dual bottom-up and top-down strategies for traversing the pattern concept lattice. The output of the Sandwich algorithm is a poset of the most relevant link key candidates. We provide details about the quality measures applicable to the selection of link keys, the Sandwich algorithm, and as well a discussion on the benefit of our approach.

Relational concept analysis (RCA) extends formal concept analysis (FCA) by taking into account binary relations between formal contexts. It has been designed for inducing description logic TBoxes from ABoxes, but can be used more generally. It is especially useful when there exist circular dependencies between objects. In this case, it extracts a unique stable concept lattice family grounded on the initial formal contexts. However, other stable families may exist whose structure depends on the same relational context. These may be useful in applications that need to extract a richer structure than the minimal grounded one. This issue is first illustrated in a reduced version of RCA, which only retains the relational structure. We then redefine the semantics of RCA on this reduced version in terms of concept lattice families closed by a fixed-point operation induced by this relational structure. We show that these families admit a least and greatest fixed point and that the well-grounded RCA semantics is characterised by the least fixed point. We then study the structure of other fixed points and characterise the interesting lattices as the self-supported fixed points.