This extended abstract gives an overview of our work [9], published at AAAI 2021. We propose an approach for automatically extracting concept inclusions (CIs) from data. This data can be, for instance a collection of facts from a database or from a knowledge graph. For example, in the DBpedia knowledge graph [14], one can represent the relationship between a city ' a' and the region 'b' it belongs to with the facts city(a), region(b), partof(a; b), and capital(b; a). One can then mine a CI expressing that a capital is a city that is part of a region. For mining such CIs, we apply methods from Formal Concept Analysis (FCA) [8]. Several other works in the literature have applied FCA for similar purposes. In [2, 7] the authors use FCA for mining an ELg?fp-base of the CIs that hold in an interpretation. A base is a set of CIs that entail every valid implication of the interpretation. Fixpoint semantics of ELgfp is used here to overcome ? the diculty of mining CIs from cyclic relationships in the data, which however comes with practical drawbacks. Based on the approach by Distel et al. [7], Borchmann et al. proposed a more practical method for mining EL?-bases with a predened and xed role depth for concept expressions [4]. As a consequence, this base is sound and complete only w.r.t. the CIs containing concepts with bounded role depth. For work on applying FCA methods in the DL context see [1, 3, 1820]. For more work on mining CIs using FCA see [5, 6, 12, 13, 15], for work on learning DL ontologies see [11, 17] and for a survey comparing different approaches for learning DL ontologies see [16]. Our work [9] brings the best of the approaches by Distel et al. [7] and Borchmann et al. [4] together: we directly compute a nite EL?-base (without a detour over ELgfp) that captures the whole language (not only until a certain role ? depth). In particular, we present a new approach that computes an adaptable role depth based only on the objects that are considered during the computation of CIs. To dene an EL? base, we use the notion of a model-based most specic concept (MMSC) up to a certain role depth [4, 7]. The MMSC plays a key rle in the computation of a base from a given nite interpretation. Denition 1. cept of X Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
An EL? concept expression C is a model-based most specic con
I with role depth d 0 i (1) X CI , (2) C has role depth at most d, and (3) for all EL? concept expressions D with role depth at most d, if X DI then ; j= C v D.
A straightforward (and inecient) way of computing mmsc (fXg; I; d), for a xed d, would be conjoining every EL? concept expression C (over NC [ NR) such that X CI and the depth of C is bounded by d. A more elegant method for computing MMSCs is based on the product of description graphs and unravelling cyclic concept expressions up to a sucient role depth. The interesting challenge is how to identify the smallest d that satises the property: if x 2 mmsc (X; I; d)I , then x 2 mmsc (X; I; k)I for every k > d.
We have developed a method for computing MMSCs with a role depth that
is suitable for building an EL? base of the given interpretation [
I ; X 6= ;g We also dene
I = fd U j U
MI g.
Building the base mostly relies on the fact that, given a nite interpretation I, for any EL? concept expression C, there is a concept expression D 2 I such that CI = DI .
B(I) =fC mmsc CI ; I j C 2 fC v D j C; D 2 I g [ I and I j= C v Dg is a nite
The base computed this way is complete for all CIs of any depth holding in
I. Unfortunately, it is not guaranteed to have minimal cardinality. In plain FCA
and in the works [
As future work, we are going to work on constructing a base that satises the minimality condition. Additionally, we are going to investigate the problem of mining CIs in the presence of noise in the dataset by making use of the support and condence measures from association rule mining. [15] Monnin, P., Lezoche, M., Napoli, A., Coulet, A.: Using formal concept analysis for checking the structure of an ontology in LOD: the example of dbpedia. In: ISMIS. pp. 674683. Springer (2017) [16] Ozaki, A.: Learning description logic ontologies: Five approaches. where do they stand? KI - Knstliche Intelligenz (04 2020) [17] Ozaki, A.: On the complexity of learning description logic ontologies. In: Manna, M., Pieris, A. (eds.) Reasoning Web. Declarative Articial Intelligence - 16th International Summer School 2020, Oslo, Norway, June 24-26, 2020, Tutorial Lectures. Lecture Notes in Computer Science, vol. 12258, pp. 3652. Springer (2020) [18] Rudolph, S.: Exploring relational structures via F LE . In: Wol, K.E., Pfeiffer, H.D., Delugach, H.S. (eds.) ICCS. pp. 196212. Springer-Verlag (2004) [19] Rudolph, S.: Relational exploration: Combining Description Logics and Formal Concept Analysis for knowledge specication. Ph.D. thesis, Fakultt Mathematik und Naturwissenschaften, TU Dresden, Germany (2006) [20] Sertkaya, B.: A survey on how description logic ontologies benet from formal concept analysis. In: Kryszkiewicz, M., Obiedkov, S. (eds.) CLA. CEUR Workshop Proceedings, vol. 672, pp. 221 (2010)