In recent years approaches for extracting formal definitions from natural language have been developed. These approaches typically use methods from natural language processing, such as relation extraction or syntax parsing. They make only limited use of description logic reasoning. We propose a hybrid approach combining natural language processing methods and description logic reasoning. In a first step description candidates are obtained using a natural language processing method. Description logic reasoning is used in a post-processing step to select good quality candidate definitions. We identify the corresponding reasoning problem and examine its complexity.
Throughout the medical domain the formal representation of knowledge has proven to
be beneficial, allowing for powerful reasoning services for the debugging and querying
of knowledge bases. Among these KR formalisms lightweight Description Logics (DL)
from the E L family such as OWL2EL [
The downside of formal semantics is the cost associated with creating, maintaining and extending ontologies. Since the knowledge is represented using logic based syntax and semantics these tasks require specially trained staff that are both experts in logics and in the application domain. One approach to facilitate the work of these experts is to mine the vast expanse of knowledge that is available in textual form, e.g. in PubMed, textbooks or on the web. A number of natural language based approaches have been proposed to automatically or semi-automatically convert concept descriptions that are available in textual form into formal concept descriptions in DL. The descriptions are obtained through analysis of lexical or linguistic features, without a mechanism that checks if the resulting descriptions are logically sound.
Typically, one sentence in natural language describes only one aspect of a target concept, it hardly ever provides a full definition. To obtain full definitions the partial definitions from different sentences must be compared and the ones with highest quality must be selected. Typically, the NLP formalism will provide a confidence value for each sentence which can provide some indication of its quality. ? Funded by the DFG Research Unit FOR 1513, project B1.
Logic based knowledge representation is not very robust when it comes to errors in concept descriptions. Even less obvious errors can cause an ontology to yield unwanted consequences or even to become inconsistent. In this work we propose to use formal constraints on the target concept in order to ensure at least a certain degree of logical soundness.
The proposed approach is therefore a hybrid approach. In a first step an NLP
formalism is used to obtain candidate definitions from text and in a second step a reasoning
problem is used in order to select a good subset of the candidate definitions. In Section 5
we provide a summary of our text mining algorithm which was first presented in [
For a long time, algorithms for learning ontologies from natural language have focussed
mainly on learning subclass relationships [
The generation of complex terminological axioms using more advanced logical
constructors is clearly a much harder task [
By contrast approaches based on machine learning techniques are easier to adapt.
Some of these [
We consider the lightweight Description Logic E L, whose concept descriptions are built from a set of concept names NC and a set of role names NR using the constructors top concept >, conjunction u, and existential restrictions 9. The semantics of E L is defined using interpretations I = ( I ; I ) consisting of a non-empty domain I and an interpretation function I mapping role names to binary relations on I and concept descriptions to subsets of I according to Table 1. A concept description C is said to be atomic if C 2 NC [ f>g or C = 9r:D for some r 2 NR and some concept description D.
As axioms we allow full definitions and primitive definitions. Full definitions are
statements of the form A C, primitive definitions are statements of the form A v C
where A is a concept name and C is a concept description. A TBox T is a set of
axioms of these two types. We say that the interpretation I is a model of T if AI = CI
(or AI CI ) holds for every full definition A C (primitive definition A v C.
respectively) from T . A concept description C is said to be subsumed by the concept
D with respect to the TBox T (denoted by T j= C v D) if CI DI holds for all
models I of T . It is well-known that subsumption reasoning in E L is tractable, i.e. given
concept descriptions C and D, and a TBox T it can be decided in polynomial time if
T j= C v D [
There are two reasons for our restriction to full definitions and primitive definitions
instead of the more expressive GCIs. In our chosen setting we try to learn concept
descriptions for SNOMED CT, which uses only full definitions and primitive definitions.
Second, this restriction allows us to check subsumption on an atomic level according to
the following lemma from [
Lemma 1 ([
Our approach for learning SNOMED CT-descriptions from text is based on the following observations. When comparing legacy versions of SNOMED CT to the current one, it is obvious that the set of role names has remained relatively stable while the number of concepts has increased. In our approach we therefore assume the set of role names to be fixed.
In our approach the knowledge engineer is allowed to pick a target concept, i.e. a concept name that is not already defined in SNOMED CT. Our goal is, by benefiting from DL reasoning, to facilitate the knowledge engineer’s design task by automatically generating a definition for the target concept from the natural language text corpus.
We proceeds in two steps. First, in the text mining step the text corpus is searched for sentences containing the target concept. A relation mining algorithm then decides for each of these sentences whether it describes a primitive definition of the target concept. For example the sentence “Baritosis is pneumoconiosis caused by barium dust.” describes the primitive definition
The right hand side of the primitive definition, in this case 9causative_agent:Barium_Dust is then added to the set of candidate descriptions. For each candidate description, the text mining algorithm also provides a numerical value, indicating confidence in the correctness of the candidate.
Second, for the reasoning step, a set of formal constraint is obtained beforehand, e.g.
from the SNOMED CT design manual [
The text mining step has been previously presented in [
We use existing knowledge from SNOMED CT to create our training set. In order to make use of implicit knowledge, the set
R = f(A; r; B) j A; B 2 NC ; r 2 NR; SNOMED CT j= A v 9r:Bg is considered. Now, if a sentence is annotated with both A and B for some triple (A; r; B) in SNOMED CT, then the sentence is labelled with the class r. That is, perhaps a bit naively, whenever two concepts A and B occur in the same sentence and SNOMED CT entails the subsumption A v 9r:B then in the training phase the sentence is assumed to describe this relation. An example for the data preparation of a sentence is shown in the first two lines of Table 2.
Annotated Sentence SNOMED CT relationship Features BoW Word 2-grams Char. 2-grams “Baritosis/Baritosis_(disorder) is pneumoconiosis caused by barium dust/Barium_Dust_(substance).” Baritosis_(disorder) | Causative_agent | Barium_Dust_(substance) left type disorder between-words
right type
“is pneumoconiosis caused by” substance
fis, pneumoconiosis, caused, byg
fis, pneumoconiosis, caused, by, is pneumoconiosis,
pneumoconiosis caused, caused by g
fi, s, p, n, e, u, m, o, c, a, d, b, y, is, pn, ne, eu, um, mo, oc, co, on,
ni, io, os, si, ca, au, us, se, ed, byg
Training Phase To train a multiclass classifier features need to be extracted from each
of those sentences that have been assigned a class in the data preparation step. In [
Test Phase Based on the weights learned in the training phase, the multiclass classifier can predict for new annotated sentences whether they describe an existential restriction. These existential restriction are then added to the candidate set. Typically, the classifier will also give a confidence value, indicating how likely it assumes the prediction to be correct. The exact nature of the confidence value depends on the classifier used.
An experimental evaluation of the approach can be found in both [
Both evaluations indicate that while the quality of the results is decent, especially considering the relatively naive generation of the training set, there is still room for improvement. We propose to use DL reasoning in a post-processing step to improve the results. 6
In this section we formally define the reasoning problem used to select a good set of candidate descriptions. We assume that a set of constraints can be obtained as described Section 6.1. In our setting constraints are simply GCIs or negated GCIs where either the left-hand side or the right-hand side is a concept variable X. We distinguish constraints of the following four types:
D v X X v D (1) (2)
D 6v X X 6v D (3) (4)
In these constraints D can be a complex concept description. X must be a concept name not occurring in T , D, or another constraint. For a complex concept description C in which no concept variables occur, we say that C satisfies the positive constraint D v X or X v D of X if T j= D v C or T j= C v D, respectively. C satisfies the negative constraint D 6v X or X 6v D if T 6j= D v C or T 6j= C v D, respectively.
In its simplest form the task is now straightforward: for a given set of description candidates and a given set of constraints, find a subset of the candidates whose conjunction satisfies the constraints. For complexity considerations we restate this as a decision problem.
Problem 1 (Concept Selection (CS)). Input: A set of atomic candidate concept descriptions S, a (possibly empty) ontology T and a set of constraints C of the forms (1)–(4).
Question: Is there a subset S0 of S such that d S0 satisfies all the constraints in C?
In the text mining step, each candidate in S has been assigned a confidence value
between 0 and 1. In practice one would like to give preference to solutions of CS that
contain candidates that have been assigned higher confidence values in the text mining
approach. We therefore need to decide upon a function for accumulating the confidence
values of all the selected candidates. Intuitively, such a function should be associative,
commutative, non-decreasing and have 1 as unit, in other words it should be a triangular
norm or t-norm [
y = min(x; y), In the following we shall only consider t-norms whose computation takes only polynomial time in the size of the inputs x and y. The idea behind the following decision problem is to maximize the accumulated confidence of the selected candidates with respect to a given t-norm .
Problem 2 (Accumulated Confidence Concept Selection ( -CS)). Input: A set of atomic candidate concept descriptions S, a real number m 2 [0; 1], a (possibly empty) ontology T and a set of constraints C of the forms (1)–(4), together with a confidence function wt : C ! [0; 1].
Question: Is there a subset S0 of S such that d S0 satisfies all the constraints in C and Nfwt(S) j S 2 S0g m?
While the minimum t-norm typically has the best computational properties, it can in practice make sense to use one of the other two t-norms. Consider a situation where several candidates have the same confidence value wt(C) = c < 1. For the minimum t-norm it makes no change whether the selection contains one or many of these candidates, while the other two t-norms give preference to smaller selections, thereby likely increasing the precision of the solution. 6.1
In an ideal scenario constraints of types (1)–(4) should come directly from the knowledge engineers. Since this, however, would simply shift the cost from the creation of concept descriptions to the creation of constraints, other ways of obtaining the constraints need to be examined.
In the case of SNOMED CT, a surprisingly large number of constraints can be
found in its design manual, the SNOMED CT User Guide [
Furthermore, a great number of definitions in SNOMED CT are only partial definitions. If the task is to enrich this partial definition using text mining, then the existing definition can be used as type (2) constraints.
Finally, one could also consider an interactive way for obtaining constraints. In a first approximation, one would simply use the conjunction over the complete set of candidates as the definition of the target concept. This definition would be temporarily added to the ontology. Both the original and the extended ontology would then be classified. The user is then presented with a set of subsumptions between concept names that are entailed by the extended ontology but not by the original one. He can then choose to mark each of them as intended or unintended. The former are added as positive constraints, while the latter are added as negative constraints. The concept selection problem is solved again. The entire process is repeated with the new selection of candidates until the user no longer marks any new consequences as unintended.
Example 1. Take Baritosis as the target concept. In an experiment described in [
0:92140 0:97038 0:99999 Due to the high weights returned by the learning approach, it is impossible to exclude any of the candidates based on weights alone. However, the concept selection framework can discard the incorrect candidate 9Causative_agent:Barium_compound, since the SNOMED CT User Guide states that the range of causative_agent is restricted to exclude Chemical, translating to the constraint
Barium_Compound which is subsumed by Chemical can thus be discarded. 7
In [
In Section 7.1, we argue that for min-CS tractability is still maintained if constraints of all four types are allowed but we require that in every type (4) constraint X 6v D the concept D must be atomic. Conversely, in Section 7.2 we show that for the product and Łukasiewicz t-norm -CS is NP-complete even if only (2) constraints are used. 7.1
In [
X 6v D; where D is atomic, (4’) using Lemma 1. Throughout this subsection we assume that full definitions have previously been expanded and the TBox contains only primitive definitions. The reason is, that in the presence of full definitions one could simply add a full definition for D to the TBox and thus emulate type (4) restrictions using type (4’) restrictions.
We first consider the variant that restricts to constraint types (2) and (3). Restriction to (2) and (3): First, let an instance (T ; S; C) of CS be given. Notice that if a concept C satisfies a constraint X v D or D 6v X and E is a concept description satisfying E v C then E also satisfies the constraint. In particular, if d S0 satisfies all constraints for some S0 S then d S also satisfies them. Hence, if only constraint types (2) and (3) occur, then there is a solution to the CS problem iff S itself is a solution. The latter can be verified in polynomial time since subsumption reasoning in E L is tractable. The same argument shows that there is a solution to the min-CS problem (T ; S; k; C; wt) iff fS 2 S j wt(S) kg is a solution. Again, this can be verified in polynomial time. Hence, CS and min-CS are tractable if we restrict to types (2) and (3). Restriction to (1)–(3) + (4’): We now assume T contains primitive definitions only, i.e. all full definitions have been expanded. Consider now a constraint D v X 2 C of type (1). A concept d S0 for S0 S satisfies this constraint if and only if T j= D v S for all S 2 S0.
For a constraint X 6v D 2 C of type (4’) we can use Lemma 1 to exploit the fact that D is atomic and that T only contains primitive definitions. The Lemma then states that a set S0 S satisfies T j= d S0 v D iff there is some S 2 S0 such that T j= S v D. In other words S0 satisfies the constraint X 6v D 2 C iff T 6j= S v D for all S 2 S0.
This shows that there is a solution S0 of (T ; S; C) iff there is a solution S00 of (T ; S0; C0) where
S0 = fS 2 S j 8(D v X) 2 C : T j= D v Sg
\ fS 2 S j 8(X 6v D) 2 C : T 6j= S v Dg C0 = fc 2 C j c of type (2) or (3)g: (5) Notice that C0 can be obtained in linear time and S0 can be computed in polynomial time since subsumption reasoning in E L is tractable. This shows that restrictions of type (1) can be dealt with in a polynomial time preprocessing step. Tractability of CS and min-CS for constraints of types (1)–(3) then follows immediately from this fact and tractability of CS and min-CS when restricted to (2) and (3).
This shows that while constraints of type (4’) may still be problematic in the context of full definitions, tractability is maintained for TBoxes where the expansion of full definitions does not lead to an exponential blowup. 7.2
For all variants of CS and -CS containment in NP is easy to see, since one can simply guess a subset of S and verify in polynomial time if it is a solution (remember that subsumption reasoning in E L is tractable). Notice, that in -CS we require that the t-norm itself can be computed in polynomial time.
In [
In this work, using a reduction from the well-known NP-complete problem Vertex Cover, we show that for the product and Łukasiewicz t-norm -CS is NP-hard, even when restricted to constraints of type (2). jOj Problem 3 (Vertex Cover). Input: A natural number k and an undirected graph G = (V; E) consisting of a set of vertices V and a set of edges E.
Question: Is there a subset O V satisfying O \ e 6= ; for every edge e 2 E and k.
We describe the reduction for the product t-norm. Starting with an instance of Vertex Cover consisting of a graph G and a number k, we construct an instance of -CS as follows. We choose NR = frg, NC = fAe j e 2 Eg. For every node v 2 V we Sv = 9r: l Ae:
v2e
X v 9r:Ae The confidence function wt is set to be constantly 0.5 (any value strictly between 0 and 1 serves the purpose). For every edge e 2 E a constraint (6) (7) (8) is added to the set of constraints. We then define m = 0:5k and we let the TBox T be empty.
Consider a subset S0 fSv j v 2 V g. Since the TBox T is empty the conjunction d S0 satisfies the constraint X v 9r:Ae iff Sv v 9r:Ae holds. From (6) this is equivalent to v 2 e. This shows that d S0 satisfies all constraints iff fv j Sv 2 S0g \ e 6= ; for all e 2 E, i.e. iff fv j Sv 2 S0g is a Vertex Cover of G. Furthermore, since wt is constantly 0.5, we have iff k jS0j = jfv j Sv 2 S0gj. This shows that fv j Sv 2 S0g is a solution cover to the given instance of Vertex Cover iff S0 is a solution to the constructed instance of -CS. Since Vertex Cover is known to be NP-complete this shows that -CS is NP-hard. Since we already know that it is contained in NP we obtain NP-completeness. Lemma 2. If is the product t-norm then -CS is NP-hard, even when restricted to constraints of type (2). m = k +11 . Then again
In the case of the Łukasiewicz t-norm nearly the same reduction can be used. The k only modification that needs to be made is that wt should to be constantly k+1 and m =
Ofwt(Sv) j Sv 2 S0g = maxf0; k +k 1 jS0j introduce a candidate concept description holds iff k
jS0j = jfv j Sv 2 S0gj.
Lemma 3. If is the Łukasiewicz t-norm then -CS is NP-hard, even when restricted to constraints of type (2).
The complexity results are summarized in Table 3. 8
In this paper we have extended the framework from [
In this paper, we have not presented an experimental evaluation. However, in an
earlier work such an evaluation has been performed for the case of the minimum t-norm
[
In the present work, the definition of the target concept was always obtained as a conjunction over the selected candidates. This is a good approach when the candidates are too general to describe the concept. It is, however, also possible that a candidate is too specific. In this case it could make sense to consider the least common subsumer (lcs) of the selected candidates, in order to generalize. For the least common subsumer we do not expect the concept selection problem to be tractable, or even in NP, since even the size of the lcs of a set of concept descriptions can be exponential in the size of the set.
We also plan to investigate, how well the approach performs for ontologies other than SNOMED CT. For the approach to be applicable, these ontologies need to satisfy a number of requirements. For the text mining step it is necessary that – the set of roles is small and stable, and – there is already a large set of concept definitions available, which can be used to train a classifier.
For the reasoning step a source for the constraints, such as a design manual, is required.
Finally, since for many classifiers the confidence values returned by the text mining step are probabilistic in nature, one might investigate the use of probabilistic extensions to E L.