=Paper=
{{Paper
|id=Vol-1350/paper-54
|storemode=property
|title=Incremental
Learning of TBoxes from Interpretation Sequences with Methods of
Formal Concept Analysis
|pdfUrl=https://ceur-ws.org/Vol-1350/paper-54.pdf
|volume=Vol-1350
|dblpUrl=https://dblp.org/rec/conf/dlog/Kriegel15
}}
==Incremental
Learning of TBoxes from Interpretation Sequences with Methods of
Formal Concept Analysis==
https://ceur-ws.org/Vol-1350/paper-54.pdf
Incremental Learning of TBoxes
from Interpretation Sequences
with Methods of Formal Concept Analysis
Francesco Kriegel
Institute for Theoretical Computer Science, TU Dresden, Germany
francesco.kriegel@tu-dresden.de
http://lat.inf.tu-dresden.de/˜francesco
Abstract. Formal Concept Analysis and its methods for computing minimal
implicational bases have been successfully applied to axiomatise minimal EL-
TBoxes from models, so called bases of GCIs. However, no technique for an
adjustment of an existing EL-TBox w.r.t. a new model is available, i.e., on a model
change the complete TBox has to be recomputed. This document proposes a
method for the computation of a minimal extension of a TBox w.r.t. a new model.
The method is then utilised to formulate an incremental learning algorithm that
requires a stream of interpretations, and an expert to guide the learning process,
respectively, as input.
Keywords: description logics, formal concept analysis, base of GCIs, implica-
tional base, TBox extension, incremental learning
1 Introduction
More and more data is generated and stored thanks to the ongoing technical develop-
ment of computers in terms of processing speed and storage space. There is a vast
number of databases, some of them freely available on the internet (e.g., dbpedia.org
and wikidata.org), that are used in research and industry to store assertional know-
ledge, i.e., knowledge on certain objects and individuals. Examples are databases
of online stores that besides contact data also store purchases and orders of their
customers, or databases which contain results from experiments in biology, physics,
psychology etc. Due to the large size of these databases it is difficult to quickly derive
conclusions from the data, especially when only terminological knowledge is of interest,
i.e., knowledge that does not reference certain objects or individuals but holds for all
objects or individuals in the dataset.
So far there have been several successful approaches for the combination of de-
scription logics and formal concept analysis as follows. In [5, 6, 28] Baader, Ganter,
and Sertkaya have developed a method for the completion of ontologies by means of
the exploration algorithm for formal contexts. Rudolph has invented an exploration
algorithm for FLE -interpretations in [26, 27]. Furthermore, Baader and Distel presented
in [3, 4, 12] a technique for the computation of bases of concept inclusions for finite
interpretations in EL that has been extended with error-tolerance by Borchmann in
[7, 8]. Unfortunately, none of these methods and algorithms provide the possibility
of extension or adaption of an already existing ontology (or TBox). Hence, whenever
a new dataset (in form of an interpretation or description graph) is observed then
the whole base has to be recomputed completely which can be a costly operation,
and moreover the changes are not explicitely shown to the user. In this document
we propose an extension of the method of Baader and Distel in [3, 4, 12] that allows
for the construction of a minimal extension of a TBox w.r.t. a model. The technique is
then utilised to introduce an incremental learning algorithm that requires a stream of
interpretations as input, and uses an expert to guide to exploration process.
In Sections 2 and 3 we introduce the neccessary notions from description logics, and
formal concept analysis, respectively. Section 4 presents the results on bases of GCIs
for interpretations relative to a TBox. Section 5 defines experts and adjustments that
are neccessary to guide the incremental learning algorithm that is shown in Section
6. Finally, Section 7 compares the incremental learning approach with the existing
single-step learning approach.
2 The Description Logic EL⊥
At first we introduce the light-weight description logic EL⊥ . Let ( NC , NR ) be an
arbitrary but fixed signature, i.e., NC is a set of concept names and NR is a set of role
names. Every concept name A ∈ NC , the top concept >, and the bottom concept ⊥ are
EL⊥ -concept descriptions. When C and D are EL⊥ -concept descriptions and r ∈ NR
is a role name then also the conjunction C u D and the existential restriction ∃ r. C are
EL⊥ -concept descriptions. We denote the set of all EL⊥ -concept descriptions over
( NC , NR ) by EL⊥ ( NC , NR ).
The semantics of EL⊥ are defined by means of interpretations. An interpretation I
over ( NC , NR ) is a pair (∆I , ·I ) consisting of a set ∆I , called domain, and an extension
I I I
function ·I : NC ∪ NR → 2∆ ∪ 2∆ ×∆ that maps concept names A ∈ NC to subsets
AI ⊆ ∆I and role names r ∈ NR to binary relations rI ⊆ ∆I × ∆I . Furthermore, the
extension function is then canonically extended to all EL⊥ -concept descriptions:
(C u D)I := CI ∩ DI
n o
(∃ r. C)I := d ∈ ∆I ∃e ∈ ∆I : (d, e) ∈ rI ∧ e ∈ CI
EL⊥ allows to express terminological knowledge with so called concept inclusions.
A general concept inclusion (abbr. GCI) in EL⊥ over ( NC , NR ) is of the form C v D
where C and D are EL⊥ -concept descriptions over ( NC , NR ). An EL⊥ -TBox T is a
set of EL⊥ -GCIs. An interpretation I is a model of an EL⊥ -GCI C v D, denoted as
I |= C v D, if the set inclusion CI ⊆ DI holds; and I is a model of an EL⊥ -TBox T ,
symbolized as I |= T , if it is a model of all its EL⊥ -concept inclusions. An EL⊥ -GCI
C v D follows from an EL⊥ -TBox T , denoted as T |= C v D, if every model of T is
also a model of C v D.
3 Formal Concept Analysis
This section gives a brief overview on the basic definitions of formal concept analysis
and the neccessary lemmata and theorems cited in this paper.
The basic structure of formal concept analysis is a formal context K = (G, M, I ) that
consists of a set G of objects, a set M of attributes, and an incidence relation I ⊆ G × M.
Instead of (g, m) ∈ I we rather use the infix notation g I m, and say that g has m. For
brevity we may sometimes drop the adjective "formal". From each formal context K
two so-called derivation operators arise: For subsets A ⊆ G we define A I as a subset of
M that contains all attributes which the objects in A have in common, i.e.,
A I := {m ∈ M | ∀g ∈ A : g I m} .
Dually for B ⊆ M we define B I as the set of all objects that have all attributes in B, i.e.,
B I := {g ∈ G | ∀m ∈ B : g I m}. An intent is a subset B ⊆ M such that B = B II holds.
A formal implication over M is of the form X → Y where X, Y ⊆ M. It holds in the
context (G, M, I ) if all objects having all attributes from X also have all attributes from
Y, i.e., iff X I ⊆ Y I is satisfied. An implication set over M is a set of implications over
M, and it holds in a context K if all its implications hold in K. An implication X → Y
follows from an implication set L if X → Y holds in all contexts in which L holds, or
equivalently iff Y ⊆ XL where XL is defined as the least superset of X that satisfies
the implication A ⊆ XL ⇒ B ⊆ XL for all implications A → B ∈ L.
Stumme has extended the notion of implicational bases as defined by Duquenne
and Guigues in [20] and by Ganter in [13] towards background knowledge in form of
an implication set. We therefore skip the original definitions and theorems and just cite
those from Stumme in [29]. If S is an implication set holding in a context K, then an
implicational base of K relative to S is defined as an implication set L, such that L holds
in K, and furthermore each implication that holds in K follows from S ∪ L.
A set P ⊆ M is called a pseudo-intent of K relative to S if P = PS , P 6= P II , and for
/ P of K relative to S it holds that Q ⊆ P. Then the following
each pseudo-intent Q ⊆ II
set is the canonical implicational base of K relative to S :
n o
P → P II P is a pseudo-intent of K relative to S .
4 Relative Bases of GCIs w.r.t. Background TBox
In this section we extend the definition of a base of GCIs for interpretations as intro-
duced by Baader and Distel in [3, 4, 12] towards the possibility to handle background
knowledge in form of a TBox. Therefore, we simply assume that there is already a set
of GCIs that holds in an interpretation, and are just interested in a minimal extension
of the TBox such that the union of the TBox and this relative base indeed entails all GCIs
which hold in the interpretation.
In the following text we always assume that I is an interpretation, and T is a TBox
that has I as a model, and both are defined over the signature ( NC , NR ).
Definition 1 (Relative Base w.r.t. Background TBox). An EL⊥ -base for I relative to
T is defined as an EL⊥ -TBox B that fulfills the following conditions:
(sound) All GCIs in T ∪ B hold in I , i.e., I |= T ∪ B.
(complete) All GCIs that hold in I also follow from T ∪ B, i.e., I |= C v D implies
T ∪ B |= C v D.
Furthermore, we call B irredundant, if none of its concept inclusions follows from the others,
i.e., if (T ∪ B) \ {C v D} 6|= C v D holds for all C v D ∈ B; and minimal, if it has
minimal cardinality among all EL⊥ -bases for I relative to T . Of course all minimal bases are
irredundant but not vice versa.
The previous definition is a straightforward generalization of bases of GCIs for
interpretations since in case of an empty TBox T = ∅ both definitions coincide.
The term of a model-based most-specific concept description has been introduced by
Baader and Distel in [3, 4, 12]. The next definition extends their notion to model-based
most-specific concept descriptions relative to a TBox.
Definition 2 (Relative model-based most-specific concept description). An EL⊥ -
concept description C over ( NC , NR ) is called relative model-based most-specific concept
description of X ⊆ ∆I w.r.t. I and T if the following conditions are satisfied:
1. X ⊆ CI .
2. If X ⊆ DI holds for a concept description D ∈ EL⊥ ( NC , NR ) then T |= C v D.
The definition implies that all relative model-based most-specific concept descrip-
tions of a subset X ⊆ ∆I are equivalent w.r.t. the TBox T . Hence, we use the symbol
XIT for the relative mmsc of X w.r.t. I and T .
However, as an immediate consequence from the definition it follows that the
model-based most-specific concept description of X ⊆ ∆I w.r.t. I is always a relative
model-based most-specific concept description of X w.r.t. I and T .
There are situations where the relative mmsc exists but not the standard mmsc.
Consider the interpretation I described by the following graph:
A
I: d r
Then d has no model-based most specific concept in EL⊥ but has a relative mmsc
w.r.t. T := { A v ∃ r. A}, in particular it holds dIT = A. Of course, d has a role-depth
⊥
bounded mmsc, and a mmsc in ELgfp with greatest fixpoint semantics, respectively.
For the following statements on the construction of relative bases of GCIs we
strongly need the fact that all model-based most-specific concept descriptions exist. If
computability is neccessary, too, then we further have to enforce that there are only
finitely many model-based most-specific concept descriptions (up to equivalence) and
that the interpretation only contains finitely many individuals; of course the second
requirement implies the first.
The model-based most-specific concept description of every individual x w.r.t. I
clearly exists if the interpretation I is finite and acyclic. Relative model-based most-
specific concept descriptions exist if we can find suitable synchronised simulations
on a description graph constructed from the interpretation and the TBox. A detailed
characterisation and appropriate proofs will be subject of a future paper.
In case we cannot ensure the existence of mmscs for all individuals of the interpreta-
tion we may also adopt role-depth bounds. Further details are given in [10]. Then we
modify the definition of a relative base of GCIs to only involve GCIs whose subsumee
and subsumer satisfy the role-depth bound. This is both applied to the GCIs in the
base and the GCIs that must be entailed. As a consequence we are able to treat cyclic
interpretations whose cycles are not already modeled in the background TBox.
As in the default case without a TBox, the definition of relative model-based most-
specific concept descriptions yields a quasi-adjunction between the powerset lattice
I
(2∆ , ⊆) and the quasiordered set (EL⊥ ( NC , NR ), vT ).
Lemma 1 (Properties of Relative mmscs). For all subsets X, Y ⊆ ∆I and all concept
descriptions C, D ∈ EL⊥ ( NC , NR ) the following statements hold:
1. X ⊆ CI if and only if T |= XIT v C
2. X ⊆ Y implies T |= XIT v YIT 3. T |= C v D implies CI ⊆ DI
4. X ⊆ XIT I 5. T |= CIIT v C
6. T |= XIT ≡ XIT IIT 7. CI = CIIT I
In order to obtain a first relative base of GCIs for I w.r.t. T we can prove that it
suffices to have mmscs as the right-hand-sides of concept inclusions in a relative base.
More specifically, it holds that the set
n o
C v CIIT C ∈ EL⊥ ( NC , NR )
is a relative of GCIs for I w.r.t. T . This statement is a simple
consequence of the fact
that a GCI C v D only holds in I if it follows from T ∪ C v CIIT .
In the following text we want to make a strong connection to formal concept analysis
in a similar way as Baader and Distel did in [3, 4, 12]. We therefore define a set MI ,T
of EL⊥ -concept descriptions such that all relative model-based most-specific concept
descriptions can be expressed as a conjunction over a subset of MI ,T . We use similar
techniques like lower approximations and induced contexts but in an extended way to
be explicitly able to handle background knowledge in a TBox. d d
For an EL-concept description in its normal form C ≡ A∈U A u (r,D)∈Π ∃ r. D
we define its lower approximation w.r.t. I and T as the EL-concept description
l l
bCcI ,T := Au ∃ r. DIIT .
A∈U (r,D)∈Π
As a consequence of the definition we get that T entails the concept inclusion
bCcI ,T v C. The explicit proof uses Lemma 1 5 and the fact that both conjunction
and existential restrictions are monotonic. This also justifies the name of a lower
approximation of C.
Furthermore, it is readily verified that all lower approximations can be expressed in
terms of the set MI ,T which is defined as follows:
n o
MI ,T := {⊥} ∪ NC ∪ ∃ r. XIT r ∈ Nr , ∅ 6= X ⊆ ∆I
In order to prove that also each model-based most-specific concept description is
expressible in terms of MI ,T it suffices to show that every model-based most-specific
concept description is equivalent to its lower approximation. We already know from
Lemma 1 5 that T entails the concept inclusion CIIT v C. Furthermore, for all concept
descriptions C, D ∈ EL⊥ ( NC , NR ) and all role names r ∈ NR it may be easily shown
by means of Lemma 1 7 that the following two statements hold:
1. (C u D)I = (C u DIIT )I .
2. (∃ r. C)I = (∃ r. CIIT )I .
As a consequence it follows that both the mmsc CIIT and the lower approximation
bCcI ,T have the same extensions w.r.t. I , and then Lemma 1 1 yields that T entails
CIIT v bCcI ,T . In summary, it follows that T entails the concept inclusions
CIIT ≡ CIIT IIT v bCIIT cI ,T v CIIT ,
and hence each relative model-based most-specific concept description is equivalent to
its lower approximation w.r.t. T , and thus is expressible in terms of MI ,T .
Now we are ready to use methods of formal concept analysis to construct a minimal
base of GCIs for I w.r.t. T . We therefore first introduce the induced context w.r.t. I and
T which is defined as KI ,T := ∆I , MI ,T , I where (d, C) ∈ I if and only if d ∈ CI
holds. Additionally, the background knowledge is defined as the implication set
SI ,T := {{C} → {D} | C, D ∈ MI ,T and T |= C v D} .
One the one hand we need this background implications to skip the computation of
trivial GCIs C v D where the implication {C} → {D} is not neccessarily trivial in
KI ,T , and on the other hand it is needed to avoid the generation of GCIs that are
already entailed by T .
As an immediate consequence of the definition it follows that ( U)I = U I holds
d
for all subsets
d Ud⊆ MI ,T , and hence we infer that for all subsets U, V ⊆ MI ,T
the GCI U v V holds in I if and only if the implication U → V holds in the
induced context KI ,T . Furthermore, it is true that conjunctions of intents of KI ,T
are exactly the mmscs w.r.t. I and T , i.e., T |= U II ≡ ( U )IIT holds for all
d d
subsets U ⊆ MI ,T . Eventually, the previous statements allow for the transformation
of a minimal implicational base of the induced context KI ,T w.r.t. the background
knowledge SI ,T into a minimal base of GCIs for I relative to the background TBox T .
Theorem 1 (Minimal Relative Base of GCIs). Assume that all model-based most-specific
concept descriptions of I relative to T exist. Let L be a minimal
d implicational base of the induced
context KI ,T w.r.t. the background knowledge SI ,T . Then U v U II U → U II ∈ L
d
is a minimal base of GCIs for I relative to T .
Eventually, the following set is the (minimal) canonical base for I relative to T :
nl l o
BI ,T := Pv P II P is a pseudo-intent of KI ,T relative to SI ,T .
All of the results presented in this section are generalisations of those from Baader
and Distel in [3, 4, 12], and for the special case of an empty background TBox T = ∅
the definitions and propositions coincide. In particular, the last Theorem 1 constructs
the same base of GCIs as [12, Theorem 5.12, Corollary 5.13] for T = ∅.
5 Experts in the Domain of Interest
We have seen how to extend an existing TBox T with concept inclusions holding in
an interpretation I that is a model of T . However, there might be situations where
we want to adjust a TBox T with information from an interpretation I that is not a
model of T . In order to use the results from the previous section on relative bases it
is neccessary to adjust the interpretation or the TBox such that as much knowledge
as possible is preserved and the adjusted interpretation models the adjusted TBox.
However, an automatic approach can hardly decide whether counterexamples in the
interpretation are valid in the domain of interest, or whether concept inclusions hold in
the domain of interest. We therefore need some external information to decide whether
a concept inclusion should be considered true or false in the domain of interest.
Beforehand, we define the notion of adjustments as follows.
Definition 3 (Adjustment). Let I be an interpretation that does not model the GCI C v D.
1. An interpretation J is called an adjustment of I w.r.t. C v D if it satisfies the following
conditions:
(a) J |= C v D.
(b) ∆I \ X ⊆ ∆J .
(c) AI \ X ⊆ AJ holds for all concept names A ∈ NC .
(d) rI \ (∆I × X ∪ X × ∆I ) ⊆ rJ holds for all role names r ∈ NR .
The set X := CI \ DI denotes the set of all counterexamples in I against C v D.
We call an adjustment J minimal if the value ∑ A∈NC AI 4 AJ + ∑r∈NR rI 4 rJ
is minimal among all adjustments of I w.r.t. C v D.
2. A general concept inclusion E v F is called an adjustment of C v D w.r.t. I if it satisfies
the following conditions:
(a) I |= E v F.
(b) E v C.
(c) D v F.
An adjustment E v F is called minimal if there is no adjustment X v Y such that E v X
and Y v F holds.
As next step we introduce the definition of an expert that is used to guide the
incremental exploration process, i.e., it ensures that the new interpretation is always
adjusted such that it models the adjusted TBox.
Definition 4 (Expert). An expert is a mapping from pairs of interpretations I and GCIs
C v D where I 6|= C v D to adjustments. We say that the expert accepts C v D if it
adjusts the interpretation, and that it declines C v D if it adjusts the GCI.
Furthermore, the following requirements must be satisfied:
1. Acceptance must be independent of I , i.e., if χ accepts C v D w.r.t. I then χ must also
accept C v D w.r.t. any other interpretation J .
2. Adjusted interpretations must model previously accepted GCIs and must not model previ-
ously declined GCIs.
3. Adjustments of declined GCIs must be accepted.
An expert is called minimal if it always returns minimal adjustments.
5.1 Examples for Experts
Of course, we may use a human expert who is aware of the full knowledge holding in
the domain of interest. However, the problem of the construction of automatically acting
experts is left for future research. We will only present some first ideas.
An expert may be defined by means of the confidence measure that has been
introduced by Borchmann in [7, 8]. For a GCI C v D and an interpretation I it is
defined by
(C u D)I
conf I (C v D) := ∈ [0, 1].
CI
Note that conf I (C v D) = 1 iff I |= C v D. This confidence can give a hint whether
an expert should accept or decline the GCI. Assume that c ∈ [0, 1) is a confidence
threshold. In case 1 > conf I (C v D) ≥ c, i.e., if there are some but not too many
counterexamples against C v D in I , the expert accepts the GCI and has to adjust I ,
and otherwise declines the GCI and returns an adjustment of it.
Another approach is as follows. Let I = It ] Iu be a disjoint union of the trusted
subinterpretation It (which is assumed to be error-free) and the untrusted subinterpretation
Iu . Then the expert accepts C v D if it holds in It , and declines otherwise.
Of course, the automatic construction of adjustments is not addressed with both
approaches as they only provide methods for the decision whether the expert should
accept or decline. The next section presents possibilities for adjustment construction.
5.2 Construction of Adjustments
Adjusting the general concept inclusion Consider a general concept inclusion
C v D that does not hold in the interpretation I . The expert now wants to decline
the GCI by adjusting it. According to the definition of adjustments of GCIs it is both
possible to shrink the premise C and to enlarge the conclusion D to construct a GCI
that holds in I but is more general than C v D. Of course, it is always simply possible
to return the adjustment ⊥ v > but this may not be a good practise since then no
knowledge that is enclosed in C v D and holds in I would be preserved.
In order to adjust the GCI more carefully the expert has the following options:
1. Add a conjunct to C, or choose an existential restriction ∃ r. E in C and modify E
such that the resulting concept description is more specific than E, e.g., by adding a
conjunct, or by adjusting an existential restriction.
2. Choose a conjunct in D and remove it, or choose an existential restriction ∃ r. E in
D and modify E such that the resulting concept description is more general than E,
e.g., by removing a conjunct, or adjusting an existential restriction.
In order to obtain a minimal adjustment the expert should only apply as few changes
as possible.
Adjusting the interpretation To generate an adjustment of I w.r.t. C v D the expert
may either remove or modify the counterexamples in I , or introduce new individuals,
to enforce the GCI. The simplest solution is to just remove all counterexamples against
C v D from I , and this may always be done by automatic experts. Of course, the
removal of a counterexample from the interpretation is an impractical solution since
in most cases there will only be few errors in the dataset. A more intelligent solution
involves the modification of the concept and role name extensions occuring in the
premise or conclusion of the GCI at hand.
Let x ∈ CI \ DI be a counterexample. Then the expert may proceed as follows:
1. Remove x from the interpretation.
2. For a modification of the premise it suffices to choose one conjunct E of C and modify
its extension such that x 6∈ EI holds. The expert may choose either a concept
name A in C and remove the element x from the extension AI , or an existential
restriction ∃ r. E in C and modify the interpretation such that x is not in the extension
(∃ r. E)I anymore. This may either be done by removing all r-successors of x that
are elements of EI , or by modifying all r-successors such that they are not elements
of the extension EI anymore.
3. For a modification of the conclusion the expert has to modify all conjuncts E of D with
x 6∈ EI . If E = A is a concept name in D then the expert simply has to add x to the
extension of A. If E = ∃ r. F is an existential restriction in D then the expert has the
following choices:
(a) Choose an existing r-successor y of x and modify y such that y ∈ EI holds. In
case of E containing an existential restriction as a subconcept a modification or
introduction of further successors may be neccessary.
(b) Introduce a new r-successor y of x such that y ∈ EI holds. If E contains an
existential restriction as a subconcept then this action requires the introduction
of further new elements in the interpretation.
6 An Incremental Learning Algorithm
By means of experts it is possible to adjust an interpretation I and a TBox T such
that I |= T . This enables us to use the techniques for the computation of relative
bases as described in Section 4. Based on these results and definitions, we now want
to formulate an incremental learning algorithm which takes a possibly empty initial
TBox T0 and a sequence (In )n≥1 of interpretations as input, and iteratively adjusts
the TBox in order to compute a TBox of GCIs holding in the domain of interest. This
is modeled as a sequence (Tn )n≥0 of TBoxes where each TBox Tn is defined as the
base of the adjustment of In relative to the adjustment of Tn−1. Of course, we also
have to presuppose an expert χ that has full knowledge on the domain of interest
and provides the neccessary adjustments during the algorithm’s run. The algorithm is
briefly described as follows and also given in pseudo-code in Algorithm 1.
(Start) Assume that the TBox Tn−1 has been constructed and a new interpretation In
is available. In case In |= Tn−1 we may skip the next step, and otherwise we first
have to adjust both the TBox and interpretation in the next step.
(Adjustment) For each GCI C v D ∈ Tn−1 ask the expert χ whether it accepts it. If
yes then set In to the returned adjustment χ(C v D, In ). If it otherwise declines it
then replace the GCI C v D with the returned adjustment χ(C v D, In ) in Tn . After
all GCIs have been processed then we have that In |= Tn holds.
(Computation of the Relative Base) As a next step we compute the base Bn of In
relative to Tn−1 and set Tn := Tn−1 ∪ Bn . Set n := n + 1 and goto (Start).
It may occur that a previously answered question is posed to the expert again during
the algorithm’s run. Of course, we may apply caching techniques, i.e., store a set
of accepted GCIs and a set of declined GCIs but this will raise the problem how an
adjustment of the interpretation (for acceptance), or of the GCI (for decline), respectively,
can be constructed, when it is not returned from the expert itself. Some simple solutions
are given in the previous section, e.g., one may just remove all counterexamples for an
accepted GCI from the interpretation, or replace the GCI with the adjusted one that
has been previously returned by the expert. For this purpose the algorithm may build
a set Tχ of accepted GCIs to avoid a second question for the same concept inclusion,
and a set Fχ of pairs of declined GCIs and their adjustments.
Algorithm 1 Incremental Learning Algorithm
Require: a domain expert χ, a TBox T (initial knowledge)
1 Let Tχ := ∅ and Fχ := ∅.
2 while a new interpretation I has been observed do
3 while I 6|= T do
4 for all C v D ∈ T do
5 if I 6|= C v D then
6 if C v D ∈ Tχ then
7 Remove all counterexamples against C v D from I .
8 else if (C v D, E v F) ∈ Fχ then
9 Remove C v D from T .
10 else if χ accepts C v D then
11 Set I := χ(C v D, I).
12 Set Tχ := Tχ ∪ {C v D}.
13 else
14 Let E v F := χ(C v D, I) be the adjustment of the GCI.
15 Set T := (T \ {C v D}) ∪ {E v F}.
16 Set Fχ := Fχ ∪ {(C v D, E v F)}.
17 Set Tχ := Tχ ∪ {E v F}.
18 Let T := T ∪ B where B is a base of I relative to T .
19 return T .
With slight restrictions on the expert and the interpretations used as input data
during the algorithm’s run we may prove soundness (w.r.t. the domain of interest)
and completeness (w.r.t. the processed input interpretations) of the final TBox that is
returned after no new interpretation has been observed.
Proposition 1 (Soundness and Completeness). Assume that I is the domain of interest,
and T0 is the initial TBox where I |= T0. Furthermore, let χ be an expert that has full
knowledge of I , i.e., does not decline any GCI holding in I ; and let I1, . . . , In be a sequence of
sound interpretations, i.e., each Ik only models GCIs holding in I . Then the final TBox Tn is
sound for I , i.e., only contains GCIs holding in I , and is complete for the adjustment of each
Ik , i.e., all GCIs holding in the adjustment of any Ik are entailed by Tn .
Proof. We prove the claim by induction on k. Since we have that Tk holds in I the
expert does not adjust Tk but constructs an adjustment Ik0 +1 of Ik+1 that is a model
of Tk . Then the next TBox is obtained as Tk+1 := Tk ∪ Bk+1 where Bk+1 is a base of
Ik0 +1 relative to Tk . By assumption, I is a model of Bk+1, i.e., also of Tk+1, and by
construction Tk+1 is complete for Ik0 +1. Finally, T` ⊆ Tk holds for all ` ≤ k, and thus we
conclude that Tk+1 must be complete for all adjusted interpretations I10 , . . . , Ik0 +1. t
u
7 Comparison with the existing single-step-learning approaches
In comparisonUwith a single-step approach that explores the canonical base of the
disjoint union Ik there are several drawbacks. The first problem is to store all the
observed interpretations. Secondly, upon input of a new interpretation there is no
output of the refuted old GCIs, and newly obtained GCIs, respectively. Thirdly, a major
disadvantage is the computational complexity. In order to iteratively compute the
relative bases the model-based most-specific concept descriptions of each interpretation
Ik are neccessary, and their number can be exponential in the size of the domain of Ik .
I In
Hence for n input interpretations up to m := (2|∆ 1 | − 1) + . . . + (2|∆ | − 1) mmscs
have to be constructed. In order to compute the canonical base of the disjoint sum Ik
U
I I
we have to compute up to m0 := 2|∆ 1 |+...+|∆ | − 1 mmscs. Obviously, m is much
n
0
smaller than m for a sufficently large number n of input interpretations.
Furthermore, the upper bound for the size of the induced context KIk is |∆Ik | · (1 +
I
| NC | + | NR | · (2|∆ k | − 1)), and the number of implications may be exponential in the
size of the context, i.e., double-exponential in the size of the interpretation Ik , hence in
the iterative approach we get an upper bound of
I |∆I1 | −1)) In |·(1+| N |+| N |·(2|∆In | −1))
2|∆ 1 |·(1+|NC |+|NR |·(2 + . . . + 2|∆ C R
GCIs, and in the single-step approach the upper bound is given as
I In |)·(1+| N |+| N |·(2|∆I1 |+...+|∆In | −1))
2(|∆ 1 |+...+|∆ C R .
I
|∆Ik | ∑ |∆ k |
It is easy to see that ∑k 22 is much smaller than 22 k .
8 Conclusion
We have presented a method for the construction of a minimal extension of a TBox
w.r.t. a model, and utilised it to formulate an algorithm that learns EL⊥ -concept
inclusions from interpretation streams with external support by means of an expert in
the domain of interest. The approach can be applied to a wide range of input data as
there are various cryptomorphic structures for interpretations, like description graphs,
binary power context families, RDF-graphs (with some effort for a transformation) etc.
It may be extended towards more expressive description logics, e.g., FLE , or ALE , or
to include the construction of RBoxes in DLs allowing for role hierarchies or complex
role inclusions. Another direction for future research is the construction of bases for
temporal terminological knowledge.
This document has not considered the problem of the computation of relative model-
based most-specific concept descriptions. However, it is possible to use synchronised
simulations for their construction, and a detailed characterisation of the existence and
construction will be subject of a future paper.
Bibliography
[1] Baader, F.: Least common subsumers and most specific concepts in a description
logic with existential restrictions and terminological cycles. In: IJCAI-03, Proceed-
ings of the Eighteenth International Joint Conference on Artificial Intelligence,
Acapulco, Mexico, August 9-15, 2003. pp. 319–324 (2003)
[2] Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.):
The Description Logic Handbook: Theory, Implementation, and Applications.
Cambridge University Press, New York, NY, USA (2003)
[3] Baader, F., Distel, F.: A finite basis for the set of EL-implications holding in a finite
model. In: Formal Concept Analysis, 6th International Conference, ICFCA 2008,
Montreal, Canada, February 25-28, 2008, Proceedings. pp. 46–61 (2008)
[4] Baader, F., Distel, F.: Exploring finite models in the description logic ELgfp. In:
Formal Concept Analysis, 7th International Conference, ICFCA 2009, Darmstadt,
Germany, May 21-24, 2009, Proceedings. pp. 146–161 (2009)
[5] Baader, F., Ganter, B., Sattler, U., Sertkaya, B.: Completing description logic
knowledge bases using formal concept analysis. LTCS-Report 06-02, Chair for
Automata Theory, Institute for Theoretical Computer Science, Dresden University
of Technology, Dresden, Germany (2006)
[6] Baader, F., Sertkaya, B.: Applying formal concept analysis to description logics. In:
Concept Lattices, Second International Conference on Formal Concept Analysis,
ICFCA 2004, Sydney, Australia, February 23-26, 2004, Proceedings. pp. 261–286
(2004)
[7] Borchmann, D.: Towards an error-tolerant construction of EL⊥ -ontologies from
data using formal concept analysis. In: Formal Concept Analysis, 11th Interna-
tional Conference, ICFCA 2013, Dresden, Germany, May 21-24, 2013. Proceedings.
pp. 60–75 (2013)
[8] Borchmann, D.: Learning Terminological Knowledge with High Confidence
from Erroneous Data. Ph.D. thesis, Dresden University of Technology, Dresden,
Germany (2014)
[9] Borchmann, D., Distel, F.: Mining of EL-gcis. In: Data Mining Workshops
(ICDMW), 2011 IEEE 11th International Conference on, Vancouver, BC, Canada,
December 11, 2011. pp. 1083–1090 (2011)
[10] Borchmann, D., Distel, F., Kriegel, F.: Axiomatization of General Concept Inclu-
sions from Finite Interpretations. LTCS-Report 15-13, Chair for Automata Theory,
Institute for Theoretical Computer Science, Technische Universität Dresden, Dres-
den, Germany (2015)
[11] Cohen, W.W., Hirsh, H.: Learning the classic description logic: Theoretical and
experimental results. In: Proceedings of the 4th International Conference on
Principles of Knowledge Representation and Reasoning (KR’94). Bonn, Germany,
May 24-27, 1994. pp. 121–133 (1994)
[12] Distel, F.: Learning Description Logic Knowledge Bases from Data using Methods
from Formal Concept Analysis. Ph.D. thesis, Dresden University of Technology,
Dresden, Germany (2011)
[13] Ganter, B.: Two basic algorithms in concept analysis. Preprint 831, Darmstadt
University of Technology (1984)
[14] Ganter, B.: Attribute exploration with background knowledge. Theor. Comput.
Sci. 217(2), 215–233 (1999)
[15] Ganter, B.: Begriffe und Implikationen. Preprint, Chair for Algebraic Structure The-
ory, Institute for Algebra, Dresden University of Technology, Dresden, Germany
(2000)
[16] Ganter, B.: Two basic algorithms in concept analysis. In: Formal Concept Analysis,
8th International Conference, ICFCA 2010, Agadir, Morocco, March 15-18, 2010.
Proceedings. pp. 312–340 (2010)
[17] Ganter, B., Kuznetsov, S.O.: Pattern structures and their projections. In: Delugach,
H.S., Stumme, G. (eds.) Conceptual Structures: Broadening the Base, Lecture
Notes in Computer Science, vol. 2120, pp. 129–142. Springer Berlin Heidelberg
(2001)
[18] Ganter, B., Wille, R.: Contextual attribute logic. In: Conceptual Structures: Stan-
dards and Practices, 7th International Conference on Conceptual Structures, ICCS
’99, Blacksburg, Virginia, USA, July 12-15, 1999, Proceedings. pp. 377–388 (1999)
[19] Ganter, B., Wille, R.: Formal Concept Analysis - Mathematical Foundations.
Springer (1999)
[20] Guigues, J.-L., D.V.: Familles minimales d’implications informatives résultant
d’un tableau de données binaires. Mathématiques et Sciences Humaines 95, 5–18
(1986)
[21] Kriegel, F.: Concept Explorer FX (2010-2015), https://github.com/
francesco-kriegel/conexp-fx, Software for Formal Concept Analysis
[22] Kriegel, F.: Visualization of Conceptual Data with Methods of Formal Concept
Analysis. Diploma thesis, Dresden University of Technology, Dresden, Germany
(2013)
[23] Kriegel, F.: Incremental computation of concept diagrams. In: Formal Concept
Analysis - 12th International Conference, ICFCA 2014, Cluj-Napoca, Romania,
June 10-13, 2014. Supplemental Proceedings. pp. 45–61 (2014)
[24] Kriegel, F.: Next closures – parallel exploration of constrained closure operators.
LTCS-Report 15-01, Chair for Automata Theory, Institute for Theoretical Computer
Science, Dresden University of Technology, Dresden, Germany (2015)
[25] Küsters, R., Molitor, R.: Structural subsumption and least common subsumers in
a description logic with existential and number restrictions. Studia Logica 81(2),
227–259 (2005)
[26] Rudolph, S.: Exploring relational structures via FLE . In: Conceptual Structures
at Work: 12th International Conference on Conceptual Structures, ICCS 2004,
Huntsville, AL, USA, July 19-23, 2004. Proceedings. pp. 196–212 (2004)
[27] Rudolph, S.: Relational Exploration - Combining Description Logics and Formal
Concept Analysis for Knowledge Specification. Ph.D. thesis, Dresden University
of Technology, Dresden, Germany (2006)
[28] Sertkaya, B.: Formal Concept Analysis Methods for Description Logics. Ph.D.
thesis, Dresden University of Technology, Dresden, Germany (2007)
[29] Stumme, G.: Attribute exploration with background implications and exceptions.
In: Bock, H.H., Polasek, W. (eds.) Data Analysis and Information Systems, pp.
457–469. Studies in Classification, Data Analysis, and Knowledge Organization,
Springer Berlin Heidelberg (1996)
[30] Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134–1142 (1984)
[31] Zickwolff, M.: Rule Exploration: First Order Logic in Formal Concept Analysis.
Ph.D. thesis, Technische Hochschule Darmstadt, Germany (1991)