Catering for ontology summary and reuse, several approaches such as modularisation and forgetting of symbols have been developed in order to provide users smaller sets of relevant axioms of an ontology. We consider di erent module extraction techniques and show how they relate to each other. We also consider the notion of uniform interpolation that is underlying forgetting. We show that signi cant improvements in the performance of forgetting can be obtained by applying a forgetting tool to ontology modules instead of the entire ontology. We investigate combining several module notions with uniform interpolation and provide a preliminary evaluation forgetting signatures based on the European Renal Association subset from SNOMED CT. Possible explanations for why modularity helps forgetting symbols from large-scale ontologies in practice are given. To facilitate the experiments, we develop a signature extension algorithm for the SNOMED CT ontology to additionally include more symbols relevant for users.
SNOMED CT1 is the most comprehensive, precise and widespread clinical ontology in the world with ample clinical specialties and requirements. The logic pro le of SNOMED CT is a subset of the OWL 2 E L pro le.2 Description Logic with its reasoning capabilities plays an important role in the development and maintenance of SNOMED CT. The latest version of SNOMED CT from the year 2019 contains more than 340 000 axioms. The number of axioms increased by about 10% compared to the version from 2016.
SNOMED CT is still being developed and continuously updated. Maintaining and developing an ontology such as SNOMED CT is expensive and timeconsuming. It is often more e cient for the ontology engineer to work with a subset of the ontology that contains all necessary information instead of the entire ontology. For example, the concept kidney disease (disorder) has more than ? This work is partially funded by the EPSRC IAA 228 Project \Comparison and Abstraction of SNOMED CT Ontologies". We would like to thank Dr. Yizheng Zhao for helpful input on system FAME. 1 https://www.snomed.org 2 https://www.w3.org/TR/owl2-profiles/#OWL_2_EL 1 200 sub-concepts. When knowledge engineers redesign the concept model for a sub-hierarchy, it is useful to present developers a succinct sub-ontology to review and design the concept model.
A common use case for SNOMED CT is clinical data analytics. For instance, consider the scenario where the doctor would like to nd diseases that have an in ammatory morphology and a nding site of kidney structure based on morphologies and/or nding sites. Instead of querying the whole of SNOMED CT, it would be more e cient to simply query a small subset of ontology containing the necessary axioms to preserve the relevant information.
Generally speaking, a module of an ontology is a subset of the ontology that
can function in the same way as the original ontology in a speci c context. This
is formalised using a suitable inseparability relation. Model-theoretic and
deductive inseparability relations have been studied. Several module notions based
on inseparability relations have been proposed including plain, self-contained
and depleting modules [
Concepts in the medical domain can be complicated to comprehend. Together with the fact that SNOMED CT contains more than 300 000 medical terms, it becomes clear that it can be very useful for ontology development or clinical data analytics to create an abstraction or summary of the ontology that only uses the terms that the developers are interested in.
Uniform interpolation and forgetting, as techniques of ontology abstraction,
have attracted a lot of attention recently [25, 26]. Algorithms based on
resolution have been developed for expressive description logics [15{17, 28, 30]. It
has been shown that deciding the existence of uniform interpolants is
2-EXPComplete for ALC-TBoxes. Uniform interpolants do not always exist in E L and
ALC-TBoxes [
Given the high complexity result of nding uniform interpolants, in this paper, we are interested in computing uniform interpolants on SNOMED CT in practice. The signature in practice is usually much smaller than the number of symbols in the whole ontology, which means that the forgetting tool has to forget most of the symbols in the ontology. It is especially di cult to forget role names. 3 https://cgi.csc.liv.ac.uk/~konev/software/ Precomputing ontology modules can help to reduce the number of symbols that need to be forgotten and also decrease the size of ontology, which motivates us to consider using modularity to approximate forgetting tools when computing uniform interpolants in practice.
This paper describes on-going work in a collaboration with IHTSDO about abstraction on the core version of SNOMED CT. In particular, we are interested in computing modules and uniform interpolants for smaller sets of concept names and role names. We rst consider three di erent ontology modules and then analyse the relation among these modules. Then we give a brief overview of uniform interpolation/forgetting techniques and show the correctness of the optimization: speed up the forgetting process by precomputing ontology modules. We follow by proposing a signature extension method in SNOMED CT ontology. Our preliminary evaluation shows that precomputing subsumption modules signi cantly improves the performance of forgetting tools. Finally, we analyze the reasons why ontology modules can help optimize forgetting process. 2
We start by recalling the de nition of the description logic E L [
Let NC and NR be mutually disjoint and countably in nite sets of concept names and role names. The signature sig( ) is the set of concept and role names occurring in , where ranges over any syntactic object. The sets of E L-concepts C, E LI-concepts D, and the sets of E LH-axioms , E LI-axioms are built according to the grammar rules:
C ::= A j C u C j 9r:C D ::= A j C u D j 9r:D j 9r :D ::= C v C j C ::= D v D j D
C j r v s D where A 2 NC and r; s 2 NR. An E LH(E LI)-TBox is a nite set of E LH(E LI)axioms. A concept de nition is an axiom of the form C C or D D.
The semantics is de ned as usual in terms of interpretations interpreting
concept/role names and are then inductively extended to complex concepts.
The notions of a model, satisfaction of a concept, axiom and TBox as well as
the logical consequence relation are de ned as usual; see, e.g., [
A terminology T is a TBox consisting of axioms such that the left-hand side of an axiom has to be a concept name, and no concept name occurs more than once on the left-hand side of an axiom.
An E L-terminology T is normalised i it only contains axioms of the forms A v B, A v 9r:C , 9r:C v A and r v s, where A; B 2 NC, r 2 NR and C is an E L concept.
denoted as T1 T2 if fIj j I j= T1g= fIj j I j= T2g [
In this section, we consider three di erent module notions: locality-based
modules [
De nition 1 (Self-contained/Depleting Modules [
In case of acyclic E LI-terminology T , self-contained module and depleting
module coincide, if T does not contain trivial concept de nitions (cf.
Theorem 29 [
Minimal Subsumption Module. A subsumption module is a subset of an
ontology that preserves subsumption queries that a user is interested in.
De nition 2 (Subsumption Module [
The following example with SNOMED CT shows the di erence between the three di erent module notions. To simplify the presentation, we use A1 to denote Neoplasm uncertain whether benign or malignant, A2 to denote Complex mixed AND/OR stromal neoplasm, A to denote Mesoblastic nephroma, B to denote Neoplasm, X to denote Neoplasm and/or hamartoma and Y to denote Tumor.
Example 1. Let = fA; Bg and T = f 1; 2; 3; 4g, where 1 : A v A1 u A2, 2 : A1 v B, 3 : A2 v B and 4 : B v X. There are two subsumption modules of T w.r.t. : f 1; 2g and f 1; 3g. Either f 1; 2g or f 1; 3g is su cient to preserve the entailment A v B that only uses symbols in . The MEX-module and STAR-module of T w.r.t. are each f 1; 2; 3g.
For T 0 = f 1; 2; 3; 5g with 5 := B Y ,4 the STAR-module w.r.t. is T 0 itself. However, the minimal subsumption modules and MEX-module of T 0 w.r.t. coincide with corresponding those of T , respectively.
As mentioned in [
MS
MM
M?.
Proposition 1. Let T be an E L-terminology5 and a signature. Additionally, let M? and MM be the STAR-module and the MEX-module of T w.r.t. , respectively. Let MS be a minimal subsumption module of T w.r.t. . Then:
Note that both module notions, MEX-modules and STAR-modules, each
yield a unique subset of a given TBox w.r.t. a signature. On the other hand, there
might exist several or even exponentially many minimal subsumption modules
of T for a signature (cf. Example 6 in [
There are two approaches for computing minimal subsumption modules: the
glass-box and the black-box approach. In the glass-box approach, minimal
subsumption modules are directly computed by combining subsumption justi
cations for every concept name in the signature [
The task of forgetting symbols from an ontology is also known as uniform
interpolation. It can be used to reduce the amount of symbols in an ontology or hide
certain con dential symbols without changing the meaning of the remaining
symbols in the ontology. LETHE [
De nition 3 (Uniform Interpolation). Let T be an E L-terminology and a signature. U is a uniform interpolant of T w.r.t. if the following conditions are satis ed: 4 Neoplasm (B) and Tumor (Y ) are treated as synonyms in SNOMED CT and they share the same identi er. In order to illustrate the di erence between MEX-module and STAR-module, we add 5 in this example. 5 Since MEX works for ELI-terminologies and minimal subsumption modules are restricted to ELH-terminologies, we consider EL-terminologies here. { sig(U ) ; { for every E L-axiom where sig( ) , T j= i U j= .
As computing uniform interpolants is a di cult task especially for largescale ontologies, the size and complexity of the input ontology in uences the computation time directly. Instead of computing uniform interpolants on the whole ontology, we may be able to speed up the computation by computing uniform interpolants on ontology modules instead. The following proposition guarantees the correctness of this approach.
Proposition 2. Let T be an E L-TBox and a signature. of T w.r.t. . If U is a uniform interpolant of MS (MM or M?) w.r.t. , then U is a uniform interpolant of T w.r.t. .
From De nition 2 and De nition 3, we can see that if U is a uniform interpolant of MS w.r.t. , then U is a uniform interpolant of T w.r.t. . As MS MM by Proposition 1, we have that for every where sig( ) , if MS j= , then MM j= . Therefore, if U is a uniform interpolant of MS , then U is also a uniform interpolant of MM . Similarly, we have that if U is a uniform interpolant of MS , then U is a uniform interpolant of M?. 5
We have evaluated the performance of the module extraction and forgetting tool on SNOMED CT. Considering that MEX only works on E LI-terminologies and r the module extraction tool of minimal subsumption module works on E LH terminologies, we choose to do the evaluation on an E L-terminology fragment of SNOMED CT (version Jan 2016).6 All the experiments were conducted on the machines equipped with Intel(R) Xeon(R) CPU E5-2640 v3 running at 2.60GHz and with 32GB RAM. The execution timeout was 1 hour. The forgetting tools we used in this experiment were FAME7 and LETHE.8 5.1
Signature Extension For the evaluation, we used the European Renal Association (ERA) subset of symbols from SNOMED CT which has been provided by IHTSDO (SNOMED International). The ERA-subset contains a list of primary renal diseases, which is designed speci cally for use in renal centres and registries [23].
Previous evaluation of modularisation and forgetting tools on SNOMED CT
typically involved computing random signatures, genuine seed signatures [24], or
directly used SNOMED CT subsets [
For example, the ERA-subset only contains a list of renal disorders. In order to relate symbols in the ERA-subset with symbols representing diseases, body structure, role names, etc., it is necessary to extend the signature. Intuitively, one could simply extend a signature based on the axioms in SNOMED CT. However, in practice the issue arises as to which axioms to choose and how much a signature should be extended. Based on discussion with developers from IHTSDO, we propose Algorithm 1 to extend a signature. In this algorithm, the function role depth() for E L-concepts is recursively de ned as follows: >80 < role depth(C) := max(role depth(D); role depth(E)) >:1 + role depth(D)
C 2 NC; C = D u E; C = 9r:D: In version Jan 2016 of SNOMED CT, the deepest role depth of any complex concept is 2.
Algorithm 1 extends the original signature in three di erent ways. Brie y speaking, for every concept name A 2 T , i+ includes all A's direct superconcepts C where role depth of C is less than i, where 0 i 2.
As we can see in Table 1, the size of signature increases from 152 (j T j) to 275 (j 0T j). However, neither a concept name nor a role name was added when extended signature from 0T to 1T . Another 10 role names and 94 con
) Input: Normalised Terminology T , Signature Output: 0+, 1+, 2+ 1: T := \ sig(T ) \ NC 2: 0+ := 1+ := 2+ := T 3: for A v C 2 T with A 2 T do 4: if C 2 NC then 5: 0+ := 0+ [ fCg 6: if role depth(C) = 1 then 7: 1+ := 1+ [ sig(C) T Min.
Max.
Avg.
Med.
Succ. cept names were further included in 2T . About the size of modules, the size of STAR-modules stays the same. This is due to the fact that the signature is extended when computing STAR-modules. The size of MEX-module stays almost the same. But the signature extension causes an impact on the size of minimal subsumption modules. The second experiment is designed to mimic the scenario where a user queries the ontology. In this case, only a rather small number of closely related concept and role names are expected to be contained in the signature. To obtain such small signatures, we devised Algorithm 2 performing signature partitioning. Function ExtractStarModule( ; T ) in Line 1 is provided by the OWL API9 for computing STAR-modules. Even though the function accepts general TBoxes T formulated in OWL2, we only use it as a convenient way to compute the module M? of SNOMED CT for the ERA concept names as a signature. The function Classify(M?) in Line 2 then calls the reasoner ELK10 to classify M?. In a subsequent step, we reduce the computed class hierarchy to the symbols in the input signature. We obtain a classi cation H0 of the ERA concept names. The method Partition(M?) in Line 3 involved user interaction at the time of its conceptualisation. Later it became clear that this step could also be automated. We rst display H0 using an ontology visualisation tool, e.g., WebVOWL.11 Then we partition H0 by identifying di erent sets Hi0 of concept inclusions such that every pair of concept names from the same set Hi0 are connected via a chain of concept inclusions from Hi0, and every pair of concept names taken from different sets Hi0 and Hj0 with i 6= j are not connected in this sense. This results in 14 disjoint sub-hierarchies: H10; H20; :::; H104. The loop from Line 4 to 6, rst computes the signature i of hierarchy Hi0 and then extends i to i+ using function Signature-Extension(M?; i) presented in Algorithm 2. The resulting 14 signatures consist of 5 to 40 concept names and 0 to 8 role names. 9 http://owlapi.sourceforge.net/ 10 https://www.cs.ox.ac.uk/isg/tools/ELK/ 11 http://vowl.visualdataweb.org/webvowl.html
)
Output: extended signatures
(ERA subset) 1+; :::; n + 1: M? := ExtractStarModule( ; T ) 2: H0 := Reduce( ; Classify(M?)) 3: hH10; :::; Hn0i := Partition(H0) 4: for i 2 f1; :::; ng do 5: 6: i := sig(Hi0) i+ := Signature-Extension(M?; i)
For each of the 14 signatures, we computed three di erent types of modules of SNOMED CT: STAR-module, MEX-module and the minimal subsumption modules. These modules together with their respective producing signatures were then taken as input for the systems FAME and LETHE to compute uniform interpolants. The resulting computation times are summarised in Table 2 in terms of the mininal, maximal, average, and median time taken to compute a uniform interpolant. Only the successful cases that nished within a timeout of 1 hour were counted. For example, the min/max/avg/med values in Column 5 are the same since LETHE managed to compute a uniform interpolant for only one out of 14 signatures.
It becomes evident in Table 2 that precomputing MEX-modules and minimal subsumption modules signi cantly reduces the computation time and, thus, increases the success rate of computing uniform interpolants for both tools to more than 90%. In particular in the case of minimal subsumption modules, the uniform interpolant for any signature can be computed within 2.6 seconds by LETHE. Contrast this with the fact that LETHE takes for all but one signature more than one hour when using STAR-modules as an input.
However, we need to keep in mind that computing minimal subsumption modules can be computationally expensive as well. The time needed to compute the minimal subsumption modules for the 14 signatures ranged from 1 to 939 seconds. The alternative seems to be the use of MEX-modules as they can be computed even more e ciently. On the other hand, not all MEX-modules reduced the computation time for uniform interpolants to less than one hour, cf. Table 2. Hence, depending on the timeout constraint, the use of minimal subsumption modules can enable the computation of uniform interpolants. The results in Section 5 show that precomputing minimal subsumption modules and MEX-modules can signi cantly speed up the process of computing uniform interpolants. In this section, we analyse the reasons why module extraction techniques can help to approximate forgetting tools.
Smaller module. Table 5 shows that, on average, the size of minimal subsumption modules is almost 2 times smaller than MEX-modules, and 5 times smaller than STAR-modules (even 13 times smaller than STAR-module according to median value). Example 1 illustrates why minimal subsumption modules are smaller than MEX-modules and STAR-modules.
Fewer symbols to forget. As we can see from Table 3, the number of
concept names that occur in minimal subsumption modules is 53% less than
MEXmodules and almost 3 times less than STAR-modules. As the interpolation
signature is the same for all modules, forgetting on subsumption modules has much
fewer concept names to forget, the same as MEX-modules. Although forgetting
role names is more di cult than forgetting concept names, the number of role
names does not vary much on average for the di erent modules, cf. Table 4.
Special role \RoleGroup". In SNOMED CT, a special role name, called
\RoleGroup", maintains correct inferences and semantic meaning for complex
concept expressions that relate to, e.g., multiple sites and morphologies [
In our preliminary research, it is found that the presence of \RoleGroup" makes the forgetting problem harder. However, inspection has revealed that \RoleGroup" is occurred less frequently in minimal subsumption modules. In uence of new types of axiom. Although precomputing MEX-modules and minimal subsumption modules can remarkably speed up the forgetting process, these techniques apply to terminologies with few operators.
The latest version of SNOMED CT (Version Jan 2019) included new types of axioms compared with Version Jan 2016, which is beyond E LH-terminologies. That is, property chain of the form r s v r, re exive property(r ), transitive property(r+), concept inclusion where the left-hand side is a complex concept. Another type of axiom we also have to consider is property inclusion that MEX cannot deal with.
With the purpose of guring out how these axioms in uence the subsumption result in SNOMED CT, we conducted the following experiment. First, we got the E LH-Terminology fragment of SNOMED CT (Version Jan 2019), denoted as TELH, by removing axioms of property chain, re exive property, transitive property and subClass axioms in the form of C v A. The E L-fragment of SNOMED CT, denoted as TEL, is extracted by further removing property inclusion from TELH. We then employed the ELK reasoner to classify on the original SNOMED CT, TEL, HELH and get classi cation ontologies O, OELH and OEL. The function Di (H; H0) compares the set di erence between two classi ed ontologies. As shown in Table 7, the entailment di erence between H and HEL is 25973. There is around 2500 entailments di erence between H and HELH. This means role inclusions do have a considerable e ect on SNOMED CT. Although MEX is very e cient at extracting modules, MEX-modules are likely to lose some relevant information about the signature when extracting modules only on E L-fragment of SNOMED CT, similar as extracting minimal subsumption modules just on E LH-fragment of SNOMED CT. 7
In this paper, we rst brie y described current techniques on ontology modularization and uniform interpolation. We provided the preliminary evaluation of current techniques on comprehensive medical ontology SNOMED CT for a set of meaningful signatures in practice. In future, we plan to further investigate the performance of these techniques on real-world signatures. We also expect to evaluate the quality of modules and uniform interpolants we obtained with the developers of SNOMED CT and, ideally, also with doctors and nurses. For better use of current module extraction and uniform interpolation techniques in real-world situation, we will update current module/UI techniques according to feedback from SNOMED CT developers. Besides, the algorithm for computing minimal subsumption modules is also expected to be updated in order to deal with logic pro les that are outside its current scope. 23. Venkat-Raman, G., Boeschoten, E., Casino, F., Collart, F., De Meester, J., Zurriaga, O., Kramar, R., Simpson, K., Tomson, C.R., Gao, Y., Cornet, R., Jager, K.J., Stengel, B., Gronhagen-Riska, C., Reid, C., Jacquelinet, C., Schae ner, E.: New primary renal diagnosis codes for the ERA-EDTA. Nephrology Dialysis Transplantation 27(12), 4414{4419 (2012) 24. Vescovo, C.D., Klinov, P., Parsia, B., Sattler, U., Schneider, T., Tsarkov, D.: Empirical study of logic-based modules: Cheap is cheerful. In: Proc. of DL'13. pp. 144{155 (2013) 25. Wang, K., Wang, Z., Topor, R., Pan, J.Z., Antoniou, G.: Eliminating concepts and roles from ontologies in expressive description logics. Computational Intelligence 30(2), 205{232 (2014) 26. Zhang, X., Lin, Z., Wang, K.: A tableau algorithm for paraconsistent and nonmonotonic reasoning in description logic-based system. In: Proc. of APWeb'11. pp. 345{356 (2011) 27. Zhao, Y., Alghamdi, G., Schmidt, R.A., Feng, H., Stoilos, G., Juric, D., Khodadadi, M.: Tracking logical di erence in large-scale ontologies: A forgetting-based approach. In: Proc. of AAAI'19 (2019) 28. Zhao, Y., Schmidt, R.A.: Forgetting Concept and Role Symbols in
ALCOIH +(O; u)-Ontologies. In: Proc. of IJCAI'16. pp. 1345{1352 (2016) 29. Zhao, Y., Schmidt, R.A.: FAME: an automated tool for semantic forgetting in expressive description logics. In: Proc. of IJCAR'18. pp. 19{27 (2018) 30. Zhao, Y., Schmidt, R.A.: On Concept Forgetting in Description Logics with Quali ed Number Restrictions. In: Proc. of IJCAI'18. pp. 1984{1990 (2018)