Georg Gottlob, University of Oxford, UK
Title: The Hypergraph Transversal Problem: Applications and Complexity
Generating minimal transversals of a hypergraph, or, equivalently, dualizing a monotone DNF, is an important problem which has many applications in Computer Science. In this talk I will address this problem and its decisional variant, the recognition of the transversal hypergraph for another hypergraph. I will survey some results on problems which are known to be related to computing the transversal hypergraph, where I focus on problems in propositional Logic, formal concept analysis, databases, data mining, and Artificial Intelligence. I will then address the computational complexity of recognizing the transversal hypergraph. While the tractability and exact complexity of this problem have been open for over 30 years, it is known that the decision problem can be solved in quasipolynomial time, and in polynomial time with limited nondeterminism. Regarding the space complexity, it was recently shown that the problem is in quadratic logspace. I will also discuss large classes of instances on which the problem is known to be tractable.
Iven Van Mechelen, University of Leuven, Belgium
Title: The family of hierarchical classes models, formal concept analysis, and a broad range of related approaches: An exercise in identifying bridges
Twenty-five years ago, De Boeck and Rosenberg (1988) launched the development of a novel and intriguing set of models: the hierarchical classes family. I will start my talk with a brief review of the history of the start of this family, with special emphasis on the substantive concerns underlying the models and on their mathematical underpinnings. This will immediately pave the way for an analysis of the fairly intimate relation between the original hierarchical classes models and formal concept analysis.
A second part of the talk will start from three attributes that characterize the hierarchical classes family. Based on these attributes I will build a formal context that comprises hierarchical classes analysis, formal concept analysis, and a broad range of related methods as objects. This context may be most helpful in identifying bridges between numerous structures and analytic approaches that in the past have not always looked that well connected.
In a third and final part of the talk I will briefly outline some major new developments that have taken place within the hierarchical classes family over the past 25 years. It is conjectured that several of these may be relevant for related data-analytic approaches.
De Boeck, P., & Rosenberg, S. (1988). Hierarchical classes: Model and data analysis. Psychometrika, 53, 361-381.
Sébastien Ferré, University of Rennes 1, France
Title : Scaling Conceptual Navigation in Expressivity, Usability, and Efficiency
Conceptual navigation for the guided exploration of a collection of objects is an important application and research topic in the FCA community. Concept lattices play the role of navigation spaces, where formal concepts are places, and hierarchical relations betweens concepts are navigation links. Conceptual navigation supports different modes of exploration. The most common mode is search by successive refinements, but other supported modes are: direct querying, search by examples, global understanding at-a-glance, and even simple forms of knowledge extraction. The most common approach of conceptual navigation is based on computing and displaying the concept lattice of formal contexts. However, this approach poses serious limits to expressivity (formal contexts), usability (readability of Hasse diagrams), and efficiency (computation of concept lattices).
In this talk, I will show how abstracting over concept lattices for both display (user interfaces) and computation (data structures and algorithms) has enabled the Logical Information Systems (LIS) team to scale conceptual navigation in expressivity, usability, and efficiency. About expressivity, conceptual navigation has successively been extended to logical contexts, RDF graphs, and even OWL-DL ontologies. The kinds of patterns that can now be used to characterize concepts include concrete domains (e.g., intervals, substrings), Boolean operators, graph patterns, and OLAP cubes (i.e., dimensions, measures, and aggregations). All those versions can be presented in an unified framework that lends itself to further extensions. Usability has been improved by crossing our results with those of faceted search, and has been validated to some degree through user studies. Efficiency has been made polynomial instead of exponential, allowing for the exploration of up to 100,000 objects, by computing only what is necessary (local views on concept lattices), and only when necessary (on-demand computation). Two logical information systems have been developed for experiments and actual use: Camelis (for logical contexts) and Sewelis (for RDF graphs).
Finally, I will discuss open issues and challenges to further improve expressivity, usability, and efficiency of conceptual navigation.
Frithjof Dau, SAP, Germany
Title : CUBIST: Combining and Uniting Business Intelligence with Semantic Technologies
CUBIST (Combining and Uniting Business Intelligence with Semantic Technologies) is an EU-funded research project going from September 2010 to September 2013 that investigates the combination of semantic technologies for harvesting and persisting data from a variety of data sources (both unstructured and structured) and FCA-based visual analytics for exploring and analysing the data in a meaningful way. In CUBIST seven partners from different European countries participate. A main activity of CUBIST is the joint development of a CUBIST prototype, carried out by four partners, which is utilized in three different scientific and business scenarios, provided by three use case partners.
In the talk, a) an overview over the CUBIST project will be given, with a focus on the FCA-related activities and scientific results, b) a thorough demonstration of the prototype will be provided. Based on the use cases, the up- and downsides of applying FCA in visual analytics will be scrutinized, and we will discuss the usage of FCA in large-scale enterprise settings.
Jürgen Heller, Universität Tübingen, Germany
Title : Knowledge Space Theory: From Basic Notions to Current Research Questions
Developed since the mid-1980s, knowledge space theory provides a set-theoretical representation of the structure of the knowledge in a particular domain. It offers a framework for adaptively assessing a person’s state of knowledge and for personalizing learning to the individual needs. The theory has lead to numerous successful applications, especially in the context of technology-enhanced learning.
The talk reviews (a) the basics of the approach that at the beginning was developed from a purely behavioristic perspective, (b) its competence-based extension that brings into the picture the underlying psychological constructs, and (c) a probabilistic version of the originally deterministic formulation of the theory. It discusses recent theoretical advances and explores the links to formal concept analysis.