Learning Description Logic Knowledge Bases from Data Using Methods from Formal Concept Analysis [PhD Thesis]

1 Introduction 1
1.1 Description Logics . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Describing Knowledge and Standard Reasoning . . 3
1.1.2 Reasoning Services to Support Ontology Design and Maintenance . . . . . . . . . . . . . . . . . . . 5
1.2 Formal Concept Analysis . . . . . . . . . . . . . . . . . . 7
1.2.1 Foundations . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Implications and Attribute Exploration . . . . . . 8
1.3 Existing Exploration Formalisms . . . . . . . . . . . . . . 10
1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Description Logics 19
2.1 Concept Descriptions in EL . . . . . . . . . . . . . . . . . 19
2.2 Ontologies . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Reasoning in DL . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 EL and its Offspring . . . . . . . . . . . . . . . . . . . . . 29
2.4.1 Extending EL by Terminological Cycles . . . . . . 30
2.4.2 Reasoning in ELgfp . . . . . . . . . . . . . . . . . . 34
3 Formal Concept Analysis 41
3.1 Formal Contexts and Formal Concepts . . . . . . . . . . . 41
3.2 Closure Operators and the Next-Closure Algorithm . . . . 44
3.3 Implications and the Duquenne-Guigues Base . . . . . . . 47
3.4 Attribute Exploration . . . . . . . . . . . . . . . . . . . . 52
4 General Frameworks for Combining FCA and DL 59
4.1 Model-Based Most Specific Concepts . . . . . . . . . . . . 60
4.1.1 General Definition . . . . . . . . . . . . . . . . . . 60
4.1.2 Existence in the EL-family . . . . . . . . . . . . . 63
4.1.3 Classical FCA from a DL Perspective . . . . . . . 69
4.2 Induced Contexts . . . . . . . . . . . . . . . . . . . . . . . 70
5 Axiomatization of Finite Models 77
5.1 Existence of Finite Bases in EL?gfp . . . . . . . . . . . . . 77
5.1.1 A Base in EL?gfp with Only Acyclic Left-Hand Sides 79
5.1.2 Finite Bases . . . . . . . . . . . . . . . . . . . . . . 89
5.2 Reducing the Size of the Base . . . . . . . . . . . . . . . . 97
5.2.1 Removal of Redundancy Using Induced Contexts . 97
5.2.2 Minimal Cardinality . . . . . . . . . . . . . . . . . 102
5.3 Obtaining an EL?-Base from an EL?gfp-Base . . . . . . . . 109
6 Exploration of EL?gfp-Models 113
6.1 A Practical Algorithm for Computing Bases . . . . . . . . 114
6.1.1 A Next-Closure-Algorithm for Growing Sets of Attributes . . . . . . . . . . . . . . . . . . . . . . . . 114
6.1.2 Computing Mi on the Fly . . . . . . . . . . . . . . 121
6.1.3 Acyclic Left-Hand Sides . . . . . . . . . . . . . . . 125
6.2 Model Exploration . . . . . . . . . . . . . . . . . . . . . . 130
7 ABox Exploration 139
7.1 Counterexamples in an EL?-Ontology . . . . . . . . . . . 140
7.1.1 Explicit Counterexamples and Extended Signatures140
7.1.2 Completely Describing the Background Model . . 142
7.1.3 Counterexamples Need not be Explicit . . . . . . . 145
7.2 Minimal Possible Consequences and Their Approximations147
7.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . 147
7.2.2 Existence . . . . . . . . . . . . . . . . . . . . . . . 151
7.2.3 Approximation of Minimal Possible Consequences 164
7.3 ABox Exploration . . . . . . . . . . . . . . . . . . . . . . 170
7.3.1 Exploration Using Minimal Possible Consequences 170
7.3.2 Exploration Using Approximations . . . . . . . . . 177
8 Related Work 181
8.1 Bridging the Gap between FCA and Logics . . . . . . . . 181
8.1.1 Logical Scaling and Terminological Attribute Logic 182
8.1.2 Logic Information Systems . . . . . . . . . . . . . 186
8.2 Exploration Formalisms in DL . . . . . . . . . . . . . . . 188
8.2.1 FCA-based Ontology Completion and OntoComp . 188
8.2.2 Relational Exploration . . . . . . . . . . . . . . . . 191
8.3 EL and Fixpoint Semantics . . . . . . . . . . . . . . . . . 194
8.3.1 EL with Hybrid TBoxes . . . . . . . . . . . . . . . 194
8.3.2 EL and EL+ . . . . . . . . . . . . . . . . . . . . 195
9 Conclusions 197
Bibliography 214