Although the notion of a concept as a collection of objects sharing certain properties, and the notion of a conceptual hierarchy are fundamental to both Formal Concept Analysis and Description Logics, the ways concepts are described and obtained differ significantly between these two research areas. Despite these differences, there have been several attempts to bridge the gap between these two formalisms, and attempts to apply methods from one field in the other. The present work aims to give an overview on the research done in combining Description Logics and Formal Concept Analysis.
Formal Concept Analysis (FCA) [
There are several differences between these approaches. First, in FCA one starts with a purely extensional description of the application domain, and then derives the formal concepts of this specific domain, which provide a useful structuring. In a way, in FCA the intensional knowledge is obtained from the extensional part of the knowledge. On the other hand, in DLs the intensional definition of a concept is given independently of a specific domain (interpretation), and the description of the individuals is only partial. Second, in FCA the properties are atomic, and the intensional description of a formal concept (by its intent) is just a conjunction of such properties. DLs usually provide a richer language for the intensional definition of concepts, which can be seen as an expressive, yet decidable sublanguage of first-order predicate logic.
Despite these differences, there have been several attempts to bridge the gap
between these two formalisms, and attempts to apply methods from one field to
the other. For example, there have been efforts to enrich FCA with more complex
properties similar to concept constructors in DLs [
Description Logics (DLs) [
Syntax In DLs, one formalizes the relevant notions of an application domain by concept descriptions. A concept description is an expression built from atomic concepts, which are unary predicates, and atomic roles, which are binary predicates, by using the concept constructors provided by the particular DL language in use. DL languages are identified with the concept constructors they allow. For instance the smallest propositionally closed language allowing for the constructors ⊓ (conjunction), ⊔ (disjunction), ¬ (negation), ∀ (value restriction) and ∃ (existential restriction) is called ALC.
Typically, a DL knowledge base consists of a terminological box (TBox ), which defines the terminology of an application domain, and an assertional box (ABox ), which contains facts about a specific world. In its simplest form, a TBox is a set of concept definitions of the form A ≡ C that assigns the concept name A to the concept description C. We call a finite set of general concept inclusion (GCI) axioms a general TBox. A GCI is an expression of the form C ⊑ D, where C and D are two possibly complex concept descriptions. It states a subconcept/superconcept relationship between the two concept descriptions. An ABox is a set of concept assertions of the form C(a), which means that the individual a is an instance of the concept C, and role assertions of the form R(a, b), which means that the individual a is in R-relation with individual b.
For instance the following TBox contains the definition of a landlocked country, which is a country that only has borders on land, and the definition of an ocean country that has a border to an ocean.
T := {LandlockedCountry ≡ Country ⊓ ∀hasBorderTo.Land
The following ABox states the facts about the individuals P ortugal, Austria, and Atlantic Ocean.
A := {LandlockedCountry(Austria), Country(P ortugal), Ocean(Atlantic Ocean), hasBorderTo(P ortugal, Atlantic Ocean)} Semantics The meaning of DL concepts is given by means of an interpretation I, which is a tuple consisting of a domain ΔI and an interpretation function ·I . The interpretation function maps every concept occurring in the TBox to a subset of the domain, every role to a binary relation on the domain, and every individual name occurring in the ABox to an element of the domain. The meaning of complex concept descriptions is given inductively based on the constructors used in the concept description.
For instance, the concept description Country ⊓ ∃hasBorderTo.Ocean is interpreted as the intersection of the set of countries and the set of elements of the domain that have a border to an ocean. We say that an interpretation I is a model of a TBox T if it satisfies all concept definitions in T , i.e., for every concept definition A ≡ C in T , it maps A and C to the same subset of the domain. Similarly, we say that I is a model of an ABox A, if it satisfies all concept and role assertions in A, i.e., for every concept assertion A(a) in A, the interpretation of a is an element of the interpretation of A, and for every role assertion r(a, b) the interpretation of r contains the pair consisting of the interpretations of a and b. The semantics of DL ABoxes is the open-world semantics, i.e., absence of information about an individual is not interpreted as negative information, but it only indicates lack of knowledge about that individual.
Inferences In an application, once we get a description of the application domain using DLs as described above, we can make inferences, i.e., deduce implicit consequences from the explicitly represented knowledge. The basic inference on concept descriptions is subsumption. Given two concept descriptions C and D, the subsumption problem C ⊑ D is the problem of checking whether the concept description D is more general than the concept description C. In other words, it is the problem of determining whether the first concept always, i.e., in every interpretation denotes a subset of the set denoted by the second one. We say that C is subsumed by D w.r.t. a TBox T , if in every model of T , D is more general than C, i.e., the interpretation of C is a subset of the interpretation of D. We denote this as C ⊑T D. For instance, in the example above, the concepts LandlockedCountry and OceanCountry are both trivially subsumed by the concept
The typical inference problem for ABoxes is instance checking, which is
the problem of deciding whether the interpretation of a given individual is an
element of the interpretation of a given concept in every common model of
the TBox and the ABox. For instance, from T and A given above it follows
that P ortugal is an ocean country, although A does not contain the assertion
OceanCountry(P ortugal). Modern DL systems like FaCT++ [
The existing work done by other researchers towards bridging the gap between
FCA und DLs, and attempts to apply methods from one field to the other can
roughly be collected under two categories:
– efforts to enrich the language of FCA by borrowing constructors from DL
languages [
Enriching FCA with DL constructors
Theory-driven logical scaling In [
Relational concept analysis In [
Applying FCA methods in DLs
Subsumption hierarchy of conjunctions of DL concepts In [
To this purpose, Baader defined a formal context whose attributes were the
defined DL concepts, and whose objects were all possible counterexamples to
subsumption relationships, i.e., interpretations together with an element of the
interpretation domain. This formal context has the property that its concept
lattice is isomorphic to the required subsumption hierarchy, namely the
subsumption hierarchy of conjunctions of the defined DL concepts. However, this
formal context has the disadvantage that a standard subsumption algorithm can
not be used as expert for this context within attribute exploration. In order to
overcome this problem, the approach was reconsidered in [
Subsumption hierarchy of conjunctions and disjunctions of DL
concepts In [
Subsumption hierarchy of least common subsumers In [
Relational exploration In his Ph.D thesis [
In [
In order to obtain complete knowledge about the subsumption relationships
in the given model between arbitrary F LE concepts, Rudolph gives a multi-step
exploration algorithm. In the first step of the algorithm, he starts with an F LE
context whose attributes are the atomic concepts occurring in a knowledge base.
In exploration step i + 1, he defines the set of attributes as the union of the set
of attributes from the first step and the set of concept descriptions formed by
universally quantifying all attributes of the context at step i w.r.t. all atomic
roles, and the set of concept descriptions formed by existentially quantifying all
concept intents of the context at step i w.r.t all atomic roles. Rudolph points out
that, at an exploration step, there can be some concept descriptions in the
attribute set that are equivalent, i.e., attributes that can be reduced. To this aim,
he introduces a method that he calls empiric attribute reduction. In principle,
it is possible to carry out infinitely many exploration steps, which means that
the algorithm will not terminate. In order to guarantee termination, Rudolph
restricts the number of exploration steps. After carrying out i steps of exploration,
it is then possible to decide subsumption (w.r.t. the given model) between any
F LE concept descriptions up to role depth i just by using the implication bases
obtained as a result of the exploration steps. In addition, he also characterizes
the cases where finitely many steps are sufficient to acquire complete information
for deciding subsumption between F LE concept descriptions with arbitrary role
depth. Rudolph argues that his method can be used to support the knowledge
engineers in designing, building and refining DL ontologies. This method has
been implemented in the tool Relexo.3
Exploring Finite Models in the DL ELgfp In [
Our contribution to the DL research by means of FCA methods falls mainly under two topics: 1) supporting bottom-up construction of DL knowledge bases, 2) completing DL knowledge bases. In Section 4.1 we briefly describe the use of FCA in the former, and in Section 4.2 we briefly describe the use of FCA in the latter contribution. 4.1
Supporting bottom-up construction of DL Ontologies Traditionally, DL knowledge bases are built in a top-down manner, in the sense that first the relevant notions of the domain are formalized by concept descriptions, and then these concept descriptions are used to specify properties of the individuals occurring in the domain. However, this top-down approach is not
always adequate. On the one hand, it might not always be intuitive which
notions of the domain are the relevant ones for a particular application. On the
other hand, even if this is intuitive, it might not always be easy to come up
with a clear formal description of these notions, especially for a domain expert
who is not an expert in knowledge engineering. In order to overcome this, in [
The methods for computing the least common subsumer are restricted to
rather inexpressive descriptions logics not allowing for disjunction (and thus not
allowing for full negation). In fact, for languages with disjunction, the lcs of a
collection of concepts is just their disjunction, and nothing new can be learned
from building it. In contrast, for languages without disjunction, the lcs extracts
the “commonalities” of the given collection of concepts. Modern DL systems
like FaCT++ [
To make this more precise, consider a background terminology (TBox) T
defined in an expressive DL L2. When defining new concepts, the user employs
only a sublanguage L1 of L2, for which computing the lcs makes sense. However,
in addition to primitive concepts and roles, the concept descriptions written in
the DL L1 may also contain names of concepts defined in T . Let us call such
concept descriptions L1(T )-concept descriptions. Given L1(T )-concept descriptions
C1, . . . , Cn, we want to compute their lcs in L1(T ), i.e., the least L1(T )-concept
description that subsumes C1, . . . , Cn w.r.t. T . In [
Unfortunately, the proof of this result does not yield a practical algorithm. Due
to this, in [
Example 1. As a simple example, consider the ALC-TBox T :
and the ALE-concept descriptions
C := ∃has-child.(NoSon ⊓ DaughterHappyDoctor),
D := ∃has-child.(NoDaughter ⊓ SonRichDoctor).
By ignoring the TBox, we obtain the ALE(T )-concept description ∃has-child.⊤ as a common subsumer of C, D. However, if we take into account that both
by the concept ChildrenDoctor, then we obtain the more specific common subsumer ∃has-child.ChildrenDoctor. The gcs of C, D is even more specific. In fact, the least conjunction of (negated) concept names subsuming both NoSon ⊓
and thus the gcs of C, D is
∃has-child.(ChildrenDoctor ⊓ DaughterHappyDoctor ⊓ SonRichDoctor). The conjunct ChildrenDoctor is actually redundant since it is implied by the remainder of the conjunction. ⋄
In order to implement the gcs algorithm, we must be able to compute the smallest conjunction of (negated) concept names that subsumes two such conjunctions C1 and C2 w.r.t. T . In principle, one can compute this smallest conjunction by testing, for every (negated) concept name whether it subsumes both C1 and C2 w.r.t. T , and then take the conjunction of those (negated) concept names for which the test was positive. However, this results in a large number of (possibly expensive) calls to the subsumption algorithm for L2 w.r.t. (general or (a)cyclic) TBoxes. Since, in our application scenario (bottom-up construction of DL knowledge bases w.r.t. a given background terminology), the TBox T is assumed to be fixed, it makes sense to precompute this information.
This is where FCA comes into play. By using the attribute exploration
method [
Completing DL Ontologies
The standardization of OWL [
As already mentioned, a DL knowledge base (nowadays often called ontology) usually consists of two parts, the terminological part (TBox), which defines concepts and also states additional constraints (GCIs) on the interpretation of these concepts, and the assertional part (ABox), which describes individuals and their relationship to each other and to concepts. Given an application domain and a DL knowledge base describing it, we can ask whether the knowledge base contains all the relevant information about the domain: – Are all the relevant constraints that hold between concepts in the domain captured by the TBox? – Are all the relevant individuals existing in the domain represented in the ABox?
As an example, consider the OWL ontology for human protein phosphatases
that has been described and used in [
Such questions cannot be answered by an automated tool alone. Clearly, to check whether a given relationship between concepts—which does not follow from the TBox—holds in the domain, one needs to ask a domain expert, and the same is true for questions regarding the existence of individuals not described in the ABox. The roˆle of the automated tool is to ensure that the expert is asked as few questions as possible; in particular, she should not be asked trivial questions, i.e., questions that could actually be answered based on the represented knowledge. In the above example, answering a non-trivial question regarding human protein phosphatases may require the biologist to study the relevant literature, query existing protein databases, or even to carry out new experiments. Thus, the expert may be prompted to acquire new biological knowledge.
The attribute exploration method of FCA has proved to be a successful
knowledge acquisition method in various application domains. One of the earliest
applications of this approach is described in [
Although this sounds very similar to what is needed in our case, we cannot directly use this approach. The main reason is the open-world semantics of description logic knowledge bases. Consider an individual i from an ABox A and a concept C occurring in a TBox T . If we cannot deduce from the TBox T and A that i is an instance of C, then we do not assume that i does not belong to C. Instead, we only accept this as a consequence if T and A imply that i is an instance of ¬C. Thus, our knowledge about the relationships between individuals and concepts is incomplete: if T and A imply neither C(i) nor ¬C(i), then we do not know the relationship between i and C. In contrast, classical FCA and attribute exploration assume that the knowledge about objects is complete: a cross in row g and column m of a formal context says that object g has attribute m, and the absence of a cross is interpreted as saying that g does not have m.
There has been some work on how to extend FCA and attribute exploration
from complete knowledge to the case of partial knowledge [
In [
Syria Turkey
France
Germany Switzerland
USA
+
+
+
+
+
+
+
+
+
+
+
+
+
+
finding completing DL knowledge bases. As a result of running this algorithm
on a DL knowledge base, the knowledge base is complete w.r.t. an intended
interpreation, i.e., if an implication holds in this interpreation then it also follows
from the TBox, and if not then the ABox contains a counterexample to this
implication. For details of the attribute exploration on partial contexts and its
application to DL ontologies we refer the reader to [
Example 2. Let our TBox Tcountries contain the following concept definitions:
Moreover, let our ABox Acountries contain the individuals Syria, Turkey, France, Germany, Switzerland, USA and assume we are interested in the subsumption relationships between the concept names AsianCountry, EUmember, European
induced by Acountries, and Table 2 shows the questions asked by the completion algorithm and the answers given to these questions. In order to save space, the names of the concepts are shortened in both tables. The questions with positive answers result in extension of the TBox with the following GCIs:
Moreover, the questions with negative answers result in extension of the ABox with the individuals Russia, Cyprus, Spain and Japan. The partial context ′ induced by the resulting ABox Acountries is shown in Table 3. The resulting Answer Counterex.
yes no Russia no Cyprus yes no Spain no Japan yes yes knowledge base (Tc′ountries, A′countries) is complete w.r.t. the initially selected concept names.
Based on on the described approach, we implemented a first experimental version of a DL knowledge base completion tool as an extension for the Swoop ontology editor using Pellet as the underlying reasoner. A first evaluation of this tool on the OWL ontology for human protein phosphatases with biologists as experts, was quite promising, but also showed that the tool must be improved in order to be useful in practice. In particular, we have observed that the experts sometimes make errors when answering queries. Thus, the tool should support the expert in detecting such errors, and also make it possible to correct errors without having to restart the completion process from scratch. Another usability issue on the wish list of our experts was to allow the postponement of answering certain questions, while continuing the completion process with other questions.
In a follow-up paper [
We have summarized the work done in combining DLs and FCA. The research done in this field mainly falls under two categories: 1) efforts to enrich the language of FCA by borrowing constructors from DL languages, and 2) efforts to employ FCA methods in the solution of problems encountered in knowledge representation with DLs. For each of these categories we have given pointers and shortly described the relevant work in the literature. We have also described our own contributions, which are mainly under the second category.
Recent developments in information technologies like social networks, Web 2.0 applications and semantic web applications are bringing up new challenges for representing vast amounts of knowledge and analyzing huge amounts of data rapidly generated by these applications. The two research areas we have discussed here, namely DLs and FCA, are lying at the core of representing knowledge, and analyzing data, respectively. We are confident that these new challenges will enable new fruitful cooperations between these two research fields.