To extract terminological knowledge from data, Baader and Distel have proposed an efective method that allows for the extraction of a base of all valid general concept inclusions of a given finite interpretation. In previous works, to be able to handle small amounts of errors in our data, we have extended this approach to also extract general concept inclusions which are “almost valid” in the interpretation. This has been done by demanding that general concept inclusions which are “almost valid” are those having only an allowed percentage of counterexamples in the interpretation. In this work, we shall further extend our previous work to allow the interpretation to contain both trusted and untrusted individuals, i. e. individuals from which we know and do not know that they are correct, respectively. The problem we then want to solve is to find a compact representation of all terminological knowledge that is valid for all trusted individuals and is almost valid for all others.
Constructing description logic knowledge bases is an expensive, time-consuming and often cumbersome task. The main reason for this is that it almost always has to be conducted by human experts, since they provide the means to (more or less) reliably transform informally stated knowledge into a formal reformulation. Thus, methods to assist human experts in constructing these ontologies would be highly helpful. For example, one could provide a first, rough approximation of the desired knowledge base, i. e. a sketch of the ontology, that the expert then could build upon.
The extraction of such first knowledge bases is a widely studied topic.
Interesting approaches in this direction have been proposed by Völker and Niepert [
The latter approach has a particular appeal: since bases are complete in the sense that all valid GCIs expressible in ℰℒK already follow from it, such a base provides * Supported by DFG Graduiertenkolleg 1763 (QuantLA) all the knowledge which is present in the data. However, this approach also has a drawback: since only valid GCIs are considered, even very rare counterexamples could invalidate otherwise correct (and useful) GCIs, leading the algorithm to come up with a lot of special cases to circumvent such errors.
Thus, based upon the approach of Baader and Distel, the author has developed
an extension that allows for finding finite bases of “almost valid” GCIs of a given
ifnite interpretation [
suspected to be erroneous, an assumption which may not be correct in general.
“trust” certain individuals, i. e. that we state a-priori that they are correct as they are. This implies that all GCIs which are invalidated by such trusted individuals are false in our original domain of interest, and should thus not be included in an according knowledge base.
The target description logic we would like to consider is ℰℒK, i. e. we would like
to extract bases of ℰℒK-GCIs which are “almost valid” for untrusted individuals
and valid for trusted individuals. However, due to technical reasons, we have to
take a detour and need to also consider ℰℒgKfp, an extension of ℰℒK by means of
cyclic concept descriptions. More precisely, we shall show in this work how to find
bases of ℰℒgKfp-GCIs in the presence of untrusted individuals. To then obtain from
this base of ℰℒgKfp-GCIs a base of ℰℒK-GCIs we can use results from [
notions from the field of description logics as they are needed in this work. More
precisely, we shall introduce the logics ℰℒK and ℰℒgKfp as well as the notion of
model-based most-specific concept descriptions from [
2
necessary for our further considerations. More precisely, we shall introduce the description logics ℰℒK and ℰℒgKfp in Section 2.1 as well as the notion of general concept inclusions in Section 2.2. In Section 2.3 we shall discuss the notion of model-based most-specific concept descriptions .
according to the rule
:: | J | [ | D. where P and P . An ℰℒK-concept description is either K or an ℰℒ-concept description.
interpretations. An interpretation ℐ p ℐ , ℐ q consists of a set ℐ of individuals and an interpretation function ℐ which maps concept names P to subsets ℐ of ℐ and role name P to subsets ℐ of ℐ ℐ .
descriptions , in the usual way, i. e.
Kℐ
H,
Jℐ ℐ , p [ qℐ ℐ X ℐ , pD.qℐ
t P ℐ | D P ℐ : p, q P ℐ ^ P ℐ u, where P . We shall call the set ℐ the extension of in ℐ. For each P ℐ we shall say that satisfies if and only if P ℐ .
concept descriptions. More formally, let be a set disjoint to both and . We call this set the set of defined concept names . A concept definition is then an expression of the form , where P and is an ℰℒK-concept description which can use in the place of concept names from also concept names from . Let be a finite set of concept definitions where each defined concept names appears exactly once on the left-hand side of a concept definition in . Then is called a cyclic TBox. We define p q as the set of all concept names from that appear in some concept definition in .
cyclic TBox and P appears on the left-hand side of a concept definition p q P . An ℰℒgKfp-concept description is either of the form K or is an ℰℒgfp-concept description.
description , where p, t
Cat [ Dhunts. Mouse [ Dhunts. uq.
common situation in the old cartoon series “Tom and Jerry.” In other words, given an interpretation ℐ, the semantics of can be understood as follows: let ℐ and ℐ be the -maximal subsets of ℐ such that – all individuals in ℐ satisfy Cat and have a hunts-successor in ℐ , and – all individuals in ℐ satisfy Mouse and have a hunts-successor in ℐ .
resolve the cyclic dependencies within ℰℒgKfp-concept descriptions. This is done
using greatest fixpoint semantics [
K of ℰℒgfp exceeds the space available for this publication, we leave out the details and refer the reader to the corresponding publications. 2.2
General Concept Inclusions
(GCIs). These are expressions of the form , where and are concept descriptions. We speak of ℰℒK-GCIs if both and are ℰℒK-concept descriptions, and likewise for other description logics.
interpretation ℐ is a model of a GCI if and only if ℐ ℐ . If ℐ is a model of , then we shall also say that is valid in ℐ. If is valid in every possible interpretation we shall say that is subsumed by . This fact is commonly also denoted by (as a statement, not an expression).
and write ℒ |ù p q, if and only if for every interpretation which is a model of all GCIs in ℒ, is also a model of .
we can ask for the set of all ℰℒgKfp-GCIs for which ℐ is a model. We shall denote this set Thpℐq and call it the theory of ℐ. A base of ℐ is a set ℬ Thpℐq such that every GCI from Thpℐq is already entailed by ℬ. 2.3
Model-Based Most-Specific Concept Descriptions
logical knowledge from ℐ is to consider the set Thpℐq of all valid ℰℒK-GCIs of ℐ.
in general, for if is such a GCI, then D. D. for P is a valid ℰℒK-GCI as well. Therefore, we cannot simply use the set Thpℐq as a TBox for an ontology. Instead, we try to find a finite base ℬ of Thpℐq. Such a base would contain the same information as Thpℐq, and since it is finite it could be used as a
description logic ℰℒK and formal concept analysis is the one of model-based mostspecific concept descriptions . Roughly, for a set ℐ we are looking for a concept description that describes the individuals in in the best way possible.
– ℐ and – for all ℰℒK-concept descriptions such that ℐ , it is true that .
unique up to equivalence. In this case, we shall denote it with ℐ , since computing model-based most-specific concept descriptions is somehow “dual” to computing extensions ℐ of concept descriptions . If is a concept description, we shall write ℐℐ instead of pℐ qℐ , and likewise for ℐℐ pℐ qℐ for ℐ .
in ℰℒK may not exists. To see this, consider the example interpretation
H, t u, ℐ t u, ℐ t p, q u.
extension, but there does not exist a most specific one. On the other hand, it can be
seen quite easily that the ℰℒgKfp-concept description p, t D. uq is a
modelbased most-specific concept description of , if we consider ℰℒgfp instead of ℰℒK in
K
the above definition. Indeed, this not a coincidence, as the following result shows.
Theorem 1 (Lemma 4.5 of [
about model-based most-specific concept descriptions in ℰℒgKfp.
descriptions. Firstly, if is an ℰℒgKfp-concept description, then ℐℐ is always
a valid GCI of ℐ. Furthermore, ℐℐ is subsumed by , again for each ℰℒgKfp-concept
description . Establishing these two facts is not dificult, see [
nological knowledge from ℐ was to consider Thpℐq. However, this approach is not really applicable if we regard this interpretation as somehow faulty, in the sense that for certain individuals we are not quite sure whether their concept names or role successors are correct.
interpretation ℐDBpedia that has been extracted from RDF Triples from the DBpedia data set by considering the child-relation only. This interpretation had 5262 individuals and ThpℐDBpediaq can be axiomatized by 1252 GCIs.
because of the presence of 4 erroneous counterexamples. However, such a GCI would be considered correct, and it would be preferable if it could be learned, too. Furthermore, 2547 individuals in ℐDBpedia were positive examples for this
this GCI should have been learned as well.
that the are correct. These individuals we shall call trusted individuals, whereas the other ones are called untrusted individuals.
Example 3. We consider a classical example here. Suppose that we want to learn terminological knowledge about birds, and we consider all GCIs were the number of counterexamples is “small” compared to the number of positive examples (we shall give a formalization for this shortly). Then, the GCI Birds Flies could be extracted from the data set, as counterexamples to this are quite rare (penguins, ostriches and the like). However, these counterexamples are proper counterexamples, i. e. they are correct.
Definition 4. Let ℐ ℐ is an interpretation p ℐ , ℐ q be a finite interpretation. A subinterpretation of
p , q such that i. ℐ , ii. t P | P u t P | P ℐ u for all P , and iii. t P | p, q P u t P ℐ | p, q P ℐ u for all P and P .
representation of all GCIs of ℐ which hold for all trusted individuals and are “almost valid” for all untrusted ones. To formalize the notion of “almost valid”, we shall make use of the notion of confidence as follows.
Definition 5. Let ℐ be a finite interpretation, and let be an ℰℒgKfp-GCI. Then the confidence of in ℐ is defined as confℐ p q : #1 |p[qℐ| |ℐ| if ℐ
H otherwise
that |p [ qℐ | ¥ |ℐ |.
Definition 6. Let ℐ be a finite interpretation, let be a subinterpretation of ℐ and let P r0, 1s. The set of confident GCIs in ℐ with untrusted individuals is defined to be the following set of ℰℒgKfp-GCIs:
Thpℐ, q : t | ℐ z ℐ z
and |p [ qℐ X | ¥ |ℐ X | u.
q ¥ instead of |p [ qℐ X | ¥ |ℐ X |. This is because ℐ X is not true in general. However, if one restricts one attention to closed subinterpretations , i. e. subinterpretations where no role edges exist between elements from and ℐ z and vice versa, then ℐ X is indeed true, as it has been shown in [10, Lemma 6.12].
Another observation about Thpℐ, q is that this set is not necessarily closed
under entailment. In other words, it is possible that Thpℐ, q |ù p q but
p q R Thpℐ, q. However, we can consider GCIs in Thpℐ, q as valid
in a certain domain of interest, and counterexamples in as erroneous. Then
p q R Thpℐ, q, which just means that the amount of counterexamples in
is too high, indicates that either the data ℐ is not suficiently good enough for
learning (if it is not valid in our domain) or that some GCIs in Thpℐ, q
are actually not valid in our domain. In both cases, further refinement is necessary,
for the first case by checking completeness with respect to the underlying domain
of interest [
We shall now show how to axiomatize Thpℐ, q. To this end, we show in
Sections 4.3 and 4.4 how one can compute finite bases of Thpℐ, q, i. e. finite sets
ℬ Thpℐ, q such that all GCIs in Thpℐ, q are already entailed by ℬ. To this
end, we shall make use of results obtained by Baader and Distel [
Formal Concept Analysis
concerned with investigating diferent representations of complete lattices. However, is has also been used in diferent areas, as in data mining and classification.
context. A formal context is a triple K p, , q where and are sets and . Intuitively, we think of the set as the set of objects, the set as the set of attributes, and of the set as an incidence relation between objects and attributes.
mal context L p, , q is a subcontext of K if and only if , , .
all objects in , i. e. 1 t P | @ P : p, q P u.
1 of all objects satisfying all attributes in .
attributes from a set 1 always also has all attributes from a set 2, i. e. whether it is true that P 11 implies P 12. We can formalize this question as follows: we call a pair p1, 2q with 1, 2 an implication, usually written as 1 Ñ 2.
the set of all valid implications of K is called its theory and is denoted by ThpKq.
for all contexts in which ℒ is true, the implication 1 Ñ 2 is true as well. A set ℒ
that K is finite. We call ℒ ThpKq a base with background knowledge if and only if ℒ Y is a base of K. If H, then bases with background knowledge are just bases of K.
understandable is hardly possible in the given amount of space, and we refer the
reader to [
every set of implications with less elements than CanpK, q cannot be a base of
4.2
Results by Baader and Distel
use of the notion of of model-based most-specific concept descriptions, and define a formal context Kℐ which captures all relevant information on the valid ℰℒgKfp-GCIs of ℐ. For this, we define ℐ : t K u Y Y t D.ℐ | P , ℐ , H u.
descriptions in ℐ are expressible in terms of ℐ [
ℐ. This is the formal context Kℐ p ℐ , ℐ , ∇q, where for all P ℐ and P ℐ , it is true that ∇ if and only if P ℐ .
most-specific concept descriptions are closely related.
Proposition 7. Let ℐ , . Then ℐ the derivations are conducted in Kℐ .
With some more technical machinery it can even be shown that pd qℐℐ d 2 is
true for each ℐ , i. e. model-based most-specific concept descriptions and the
derivation operators in the induced context of ℐ are closely related. This connection
also extends to the canonical base of Kℐ and ℰℒgKfp-bases of ℐ.
d 1 and 1
pd qℐ , where
Theorem 8 (5.13 and 5.18 of [
t t u Ñ t u | , P ℐ , u.
Then the set ℬCan :
t l pl qℐℐ | p Ñ 2q P CanpKℐ , ℐ q u is a finite ℰℒgKfp-base of ℐ of minimal cardinality.
tation, but not necessarily in every formal context. More precisely, if , then we do not need to state this GCI explicitly in a base. However, the corresponding implication t u Ñ t u may not necessarily be valid in every formal context, and therefore bases of K have to contain information to entail such implications.
background knowledge. 4.3
A First Finite Base
ℐ with untrusted individuals . To this end we shall make use of ideas from M.
restrictions, however, we shall not recall his ideas in the original setting here, but shall discuss them in the appropriate reformulation to our setting only.
ℬ of Thpℐq Thpℐ, q.
ℬCan Y will be a finite base of Thpℐ, q.
Thpℐ, qz Thpℐq.
p q P Thpℐ, q ðñ pℐℐ ℐℐ q P Thpℐ, q.
are true for all ℰℒgKfp-concept descriptions , , as can be seen easily from the definition of model-based most-specific concept descriptions. We thus obtain ℐ z ℐ z
ðñ ℐℐℐ z ℐℐℐ z |p [ qℐ X | ¥ |ℐ X | ðñ |pℐℐ [ ℐℐ qℐ X | ¥ |ℐℐℐ X |
ℬ Y t ℐℐ ℐℐ u |ù p q, since ℬ |ù p ℐℐ q, and ℐℐ .
Confpℐ, , q : t ℐℐ ℐℐ | pℐℐ ℐℐ q P Thpℐ, q u,
model-based most-specific concept descriptions up to equivalence. Therefore, we immediately obtain the following result: Theorem 9. Let ℐ be a finite interpretation, be a subinterpretation of ℐ and P r0, 1s. If ℬ is a finite base of ℐ, then the set
ℬ Y Confpℐ, , q is a finite base of Thpℐ, q. 4.4
Computing a Base by means of FCA The result of the previous section provides us with an efective method to compute bases of confident GCIs in the presence of trusted and untrusted individuals. In this section, we shall extend these result to allow us a computation of such a base using methods from formal concept analysis. More precisely, we shall see that we can view our initial data ℐ and as a certain formal context, and computing a base of ℐ with untrusted individuals can then be understood as computing a certain set of implications from this context.
There are two reasons why we are interested in such a transformation. Firstly, the overall goal of our considerations is to adapt the algorithm of attribute exploration from formal concept analysis to our setting of extracting terminological knowledge from interpretations (see also Section 5). Secondly, such a reformulation might allow us to use high performance algorithms from the field of data mining to support us in our task, because the field of formal concept analysis can be understood as a theoretical foundation of data mining [15].
we can define the notion of confidence for implications as well, i. e. if K is a formal context and Ñ an implication then confKp Ñ q : 1 if 1 H and confKp Ñ q |p Y q1|{|1| otherwise. We shall denote with ImppKq the set of all implications from Impp q which have confidence at least in K.
Theorem 10. Let ℐ be a finite interpretation, be a subinterpretation of ℐ and P r0, 1s. Let us denote for ℐ with Kℐ | the subcontext of Kℐ restricted to the object set , and let us define
If then ℒ is complete for , then
ℒ : t l l | p Ñ q P ℒ u
5
In this work we have presented an extension to our previous work of axiomatizing general concept inclusions using confidence, that takes into account the existence of trusted individuals from which we can be sure that their properties in the given data are correct. Essentially, we not only consider general concept inclusions whose confidence is high enough, but we also require for such general concept inclusions that they are not falsified by trusted individuals. For these general concept inclusions we have discussed the existence and the computation of bases. In particular, we have shown that we can utilize methodology from the field of formal concept analysis to obtain such bases. This has the particular appeal that in the long run we might be able to utilize fast data mining algorithms to compute bases of confident general concept inclusions which respect trusted individuals.
The considerations we have presented in this work are part of a larger attempt
to apply the algorithm of attribute exploration from formal concept analysis to
our setting of confident general concept inclusions. This algorithm has been used
before to complete knowledge bases [
An attribute exploration algorithm in the setting of confident general concept inclusions would provide an attempt to solve the issue of rare counterexamples which comes from the heuristic approach of confident general concept inclusions, as it has been indicated in Example 3: if we consider all general concept inclusions whose conifdence is “high enough”, we may neglect certain counterexamples which are appear seldom in the data but are correct otherwise. An attribute exploration algorithm could help to resolve this issue by consulting the expert whether certain confident general concept inclusions are valid or not. If the expert is then asked a general concept inclusion which has rare counterexample, the expert could add (or mark) these counterexamples as trusted individuals, thus prohibiting the algorithm from considering them as errors. Thus, the approach of confident general concept inclusions may benefit from an attribute exploration algorithm, and its design is part of future work.
2011, pp. 124–138. isbn: 978-3-642-21033-4. [15] Mohammed Javeed Zaki and Mitsunori Ogihara. “Theoretical foundation of association rules”. In: SIGMOD’98 Workshop on Research Issues in Data Mining and Knowledge Discovery (SIGMOD-DMKD’98). 1998, pp. 1–8.
The main idea of the proof is to show that set d ℒ satisfies d ℒ |ù ℬCan Y
in this argumentation is the following lemma.
Lemma 11. Let be a set of concept descriptions, and let ℒ Impp q and p Ñ q P Impp q. Then ℒ |ù p Ñ q implies d ℒ |ù pd d q, where l ℒ : t l l | p Ñ q P ℒ u.
Proof. Let p , q be an interpretation such that |ù d ℒ. Let us define a formal context K , p , , ∇q via
∇ ðñ P for all P , P .
We shall show now that K , |ù ℒ. Let p Ñ q P ℒ. Then pd q pd q , since |ù d ℒ. It is not hard to see that pd q 1, where the derivation has been done in K , . Therefore, it is true that 1 1, and thus K , |ù p Ñ q.
Since ℒ |ù p Ñ q, it is true that K , |ù p Ñ q, i. e. 1 1. As pd q 1, it is thus true that pd q pd q , i. e. d ℒ |ù pd d q. Theorem 11. Let ℐ be a finite interpretation, be a subinterpretation of ℐ and P r0, 1s. Let us denote for ℐ with Kℐ | the subcontext of Kℐ restricted to the object set , and let us define If ℒ is complete for , then is a base of Thpℐ, q.
i. d ℒ Thpℐ, q and ii. d ℒ is complete for Thpℐ, q.
: ImppKℐ | q X ThpKℐ | ℐz q.
l ℒ : t l l | p Ñ q P ℒ u
For the first claim we need to show that for every GCI pd d q P d ℒ it is true that i. |pd [ d qℐ X | ¥ |pd qℐ X | ii. pd qℐ z pd qℐ z
|p Y q1 X | ¥ |1 X | Since pd qℐ 1, we obtain
|plp Y qqℐ X | ¥ |pl qℐ X |, and from dp Y q
d [ d it follows immediately that |pl [ l qℐ X | ¥ |pl qℐ X | as required.
valid in the formal context Kℐ | ℐz . Since 1 pd qℐ and 1 pd qℐ the claim follows.
We have therefore shown that d ℒ Thpℐ, q.
We now show that d ℒ is complete for Thpℐ, q. To this end, we shall show that i. d ℒ |ù pd pd qℐℐ q for all ℐ , in particular, d ℒ |ù ℬCan; ii. d ℒ |ù Confpℐ, , q. ℒ |ù p Ñ 2q.
By Lemma 11, it follows that ℒ |ù pd pd 2qq. Since pd 2q obtain the validity of the subclaim.
ℐ , : ℐ . Then ℐ d 1 and ℐ d 1, so pd qℐℐ , we ℒ |ù pl 1 l 1q.
|pℐℐ [ ℐℐ qℐ X | ¥ |pℐℐ qℐ X |
ℐ ℐℐ and d 1 ℐℐ , we obtain |pl 1 [ l 1qℐ X | ¥ |pl 1qℐ X |
|p 1 Y 1q1 X | ¥ | 2 X |, where the derivations are conducted in Kℐ . In other words, it is true that confKℐ| p 1 Ñ 1q ¥ .
Thus, ℒ |ù p 1 Ñ 1q, and Lemma 11 implies d ℒ |ù pd 1 d 1q, thus d ℒ |ù p ℐ ℐ q pℐℐ ℐℐ q, as required.