Patent Publication Number: US-9852374-B2

Title: Ontological concept expansion for improved similarity measures for description logic

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of the filing date of U.S. provisional application No. 61/938,714, filed on Feb. 12, 2014, the teachings of which are incorporated herein by reference in their entirety. 
     The subject matter of this application is related to the subject matter of Ser. No. 13/869,364, filed on Apr. 24, 2013, the teachings of which are incorporated herein by reference in their entirety. 
    
    
     BACKGROUND 
     Field of the Invention 
     The present invention relates to computer network-based structured data and, more specifically but not exclusively, to semantic similarity measures for structured data. 
     Description of the Related Art 
     This section introduces aspects that may help facilitate a better understanding of the invention. Accordingly, the statements of this section are to be read in this light and are not to be understood as admissions about what is prior art or what is not prior art. 
     Data on a computer-based network, such as the World Wide Web, can be linked using structured meta-data. In general, structured data enables many applications to be developed and to interact using machine-readable and machine-understandable vocabularies. For instance, in the case of network management, structured data of different equipment can be compared to detect failure and to propose recovery solutions. In a banking context, so-called “structured big data” can represent banking transactions and user profiles that an analysis can turn into assets such as proposing targeted products or advertisements to customers. 
     In the context of data structured using Semantic Web principles, data is annotated by concepts and properties having been formally defined in an ontology, i.e., defined using logical constructors of a given description logic. The comparison of such semantically enriched structures is usually done by applying one or more similarity measures that attempt to characterize how different structures are similar or how they relate to each other. A plethora of similarity measures applied to ontological data have been designed that rely on different points of view to interpret data descriptions (e.g., based on the main concept that they embody, taking into account all their features, etc.). 
     The problem with existing similarity measures is that the methodology used to compute similarities may easily lead to poor results when complex semantic descriptions are based on highly expressive description logics. In particular, either the similarity measures ignore most of the semantics (i.e., the logical constructs used to represent concepts and properties mapped on data) or they take such semantics into account too strongly, leading to weak similarity measurements for two concepts that would be considered close from a human point of view. 
     SUMMARY 
     U.S. patent application Ser. No. 13/869,364 (“the &#39;364 application”), filed Apr. 24, 2013, the teachings of which are incorporated herein by reference in their entirety, describes a similarity-measurement process that takes into account all or most of the semantics of an expressive description logic, but without taking a too-strong approach when comparing formally defined concepts. According to this process, a concept-expansion mechanism is applied to an original ontology to generate an expanded ontology having the original ontological concepts and one or more pseudo-concepts. 
     This disclosure describes the design and implementation of a similarity-measurement process that improves upon the technique described in the &#39;364 application by applying the concept-expansion mechanism to ontologies, like SHOQ ontologies, having concepts defined using a hierarchy of (possibly transitive) properties. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Other embodiments of the invention will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which similar or identical reference numerals identify similar or identical elements. 
         FIG. 1  shows Table 1, which summarizes the semantics of the SHOQ description logic; 
         FIG. 2  graphically represents an algorithm for computing the semantic similarity between different concepts having been defined in an ontology underlied by the SHOQ description logic, according to one embodiment of the disclosure; 
         FIG. 3  shows pseudo-code for a procedure that generates pseudo-concepts that are subsumed by a concept C in an ontology O, while  FIG. 4 . shows pseudo-code for a procedure that generates pseudo-concepts that subsume a concept C in ontology O; 
         FIG. 5  shows a flow diagram of the concept-expansion mechanism of  FIG. 2 ; 
         FIG. 6  shows an example of two “branches” linking concepts A and C in an exemplary graph Eo; and 
         FIG. 7  shows a flow diagram of the similarity measure computation of  FIG. 2 , according to certain embodiments of the disclosure. 
     
    
    
     DETAILED DESCRIPTION 
     This disclosure relates to a technique for accurately computing the semantic similarity between different concepts having been defined in an ontology underlied by the SHOQ description logic. The SHOQ description logic is described by Ian Horrocks and Ulrike Sattler in “Ontology Reasoning in the SHOQ(D) Description Logic,”  Proc. of IJCAI  2001, pp. 199-204, Morgan Kaufmann, 2001, the teachings of which are incorporated herein by reference in their entirety. 
     Determining the semantic similarity or relatedness of different data (or services) is an important concept in information systems. Usually based on topological or statistical analysis, it is, for instance, used in information retrieval to expand a query with similar terms or to return ranked results. In information fusion, it is used to reduce uncertainty when merging data from different sources, allowing, for instance, the creation of an ontology using a bottom-up approach. Finally, in data or service maintenance, it allows failure recovery by analyzing which data (resp. service) can be replaced by others. This disclosure addresses the problem of comparing raw data having been associated to concepts or properties defined in ontologies underlied by the expressive DL SHOQ. Usually, these ontologies contain the definitions of a domain of expertise (e.g. automotive, biology, wine, etc.) and may embed few instances of concepts mostly to set up the definition of other concepts (so-called nominals). 
     Generally, designing a semantic similarity assessment process able to compare different ontological concepts consists of defining a measure whose objective is to quantify the common (and, in some cases, the different distinguishing) features among each pair of compared concepts. Up to now, a plethora of such measures have been designed and applied on elements of an ontology, referring to different point of views that one can have about how elements should be compared. Initially, most of the existing methods were based on an adaptation of measures defined for different and less expressive representations (e.g., feature vectors or trees). However, such measures are unable to convey the underlying semantics of most ontological representations. Later on, other measures coping with more expressive ontologies were developed. However, none of those measures truly address ontologies underlied by a DL allowing the use of additional operators other than the ones defined in the ALCHN (Attributive Concept Language with Complements with hierarchy and cardinal restrictions that are not qualified) DL (e.g., use of transitive properties, nominals, and qualified cardinal restrictions). Finally, most of the recent approaches have considered using the extensions of concepts to compute semantic similarity measurements. This assumption, however, is problematic when considered ontologies solely define the concepts of a domain (and consequently do not intend to embed instances). Moreover, these methods tend to place any defined concept under the ClosedWorld Assumption (as in these approaches, the concept is assimilated as equal to using an annotation mechanism such as Semantic Annotations for Web Resources (SA-REST). In some cases, an ontology represents an entire domain of interest, i.e., its concepts and instances (e.g. in an automotive context). In some other cases, it may focus on representing the concepts and include very few (even none) instances (e.g., the OWL-S ontology) its set of instances, which, by definition, is a wrong assumption when representing concepts in OWL (the Web Ontology Language). 
     To the best of the inventor&#39;s knowledge, no works have been done in the specific case of ontologies underlied by the expressive DL SHOQ, where roles can be transitive and organized in a hierarchy and where concepts can be defined with instances (nominals). Especially, no works were done in the context of ontologies primarily focused on representing concepts more than their instances. This disclosure presents a novel semantic similarity measure for such ontologies. The method relies on an algorithm that expands the classification graph of any ontology underlied by a DL up to SHOQ and that weights all the concepts of this expanded graph. Based on these weights, we define a measure that solely relies on the semantics of the concept definitions (i.e., that can work on ontologies devoid of instances) and that is able to respect the set of behaviors one can expect from a “good” semantic similarity measure. The measure is finally assessed through different data sets and compared with existing approaches to emphazise the benefits of considering the transitivity and hierarchical organization of roles as well as nominals when computing semantic similarity measurements in SHOQ-based ontologies. 
     Preliminaries 
     Background 
     As usual, for C and D (possibly complex) concepts, C ⊂  D is called a General Concept Inclusion (GCI). A finite set of GCI forms the terminology T (or TBox) of the ontology. A role inclusion axiom is of the form R ⊂ S, where R and S are two roles defined in the ontology. The set of all roles in an ontology is named N R  while we denote the set of all transitive roles with N R+ . The finite set of role inclusion axioms represents a role hierarchy named R. Note that the terms “property” and “role” are considered as equivalent throughout the disclosure. 
     In the case of ontologies underlied by the DL SHOQ, the pair (T,R) is called a knowledge base (KB) associated with the type of ontology to be processed. The ABox is not included in the definition of the KB. 
     The formal semantics of SHOQ is defined with respect to an interpretation I=(Δ I ,• I ). I consists of (i) a non-empty set Δ I  called the domain of interpretation and (ii) an interpretation function • I  mapping each concept C to a set of individuals C I  (such that C I   ⊂  Δ I ) and each role R to a set of pairs of individuals R I  (such that R I   ⊂  Δ I ×Δ I ). 
     With respect to I, the DL SHOQ allows the creation of atomic concepts (A such that A I   ⊂  Δ I ) and atomic roles (R such that R I   ⊂  Δ I ×Δ I ). Complex concepts can be written using the operators disjunction, conjunction, full existential qualification, qualified value restriction, qualified cardinal restriction, and negation. Concepts can also be nominals, i.e., defined as an enumeration of instances. Finally, roles can be organized hierarchically and can also be transitive. Table 1 ( FIG. 1 ) summarizes the semantics of the DL SHOQ. In this table, x, y, z, α 1  . . . α n  denote individuals of Δ I . n is a positive integer, while the symbol # denotes the cardinality of a set. Note that, throughout the disclosure, the symbol T denotes the absolute truth (as well as the top concept of the ontology) and ⊥ denotes the absurdity (as well as the bottom concept of an ontology). 
     The least common subsumer (LCS) of two concepts C and D is defined as the least common concept that subsumes both C and D. In such definition, the LCS results from a computation procedure and may lead to generating a new concept (potentially added in the ontology). The least common ancestor (LCA) denotes the most-specific named concept that subsumes two concepts. Unlike the LCS, the LCA is obtained by solely using the subsumption graph of the ontology and never leads to the generation of a new concept. 
     Considering a set of axioms forming the terminology T of an ontology O, the term “primitive concepts” denotes the set of concepts of T that occur only on the right-hand side of axioms. If concepts appear in the left-hand side of an axiom, then the term “defined concepts” is used. As an example, in the following axiom C≡R.A B,C is a defined concept, while A and B are primitive concepts (and R, a role). 
     Notations and Definitions 
     For a given ontology O, we use the notation W O  to define the set of all possible SHOQ expressions that can be written by coupling the defined concepts and properties of O with the different SHOQ operators. As a consequence, T ⊂ W O . The term “pseudo-concepts” is used to denote the set of concepts that do not exist in the ontology but that are extracted by the present algorithm (i.e., these concepts have not been defined by an ontologist). The set of pseudo-concepts is written PS and contains expressions formed by concepts and logical operators of the DL SHOQ. As a consequence, PS ⊂ W O . 
     G O  refers to the classification graph of O before it has been expanded by the present algorithm, while E O  accounts for the expanded classification graph. G O  contains concepts of T, while E O  contains concepts of T∪PS. 
     In order to elicit the semantics of concepts in T, the concepts are normalized. Towards this goal, a SHOQ Normal Form is defined as follows. (Note that, as defined herein, the SHOQ Normal Form involves neither hierarchy nor transitivity of roles and consequently could be seen as an ALCOQ Normal Form.) 
     Definition 1. A defined concept C D  is in SHOQ Normal Form iff C D ≡⊥ then C D :=⊥ or if C D ≡T then C D :=T or if C D ≡D 1 ␣ . . . ␣ D n (∇i=1 . . . n, D i ≠⊥) then each D i  is such that: 
               D   i     :=       (     Prim   ⁡     (     D   i     )       )     ⋂     (     Nom   ⁡     (     D   i     )       )     ⋂     (       ⋂     R   ∈     N   R         ⁢     Rest   ⁡     (     R   ,     D   i       )         )             
with:
         Prim(C), the intersection of all (possibly negated) primitive concepts at the top-level of C,   Nom(C), the intersection of all (possibly negated) nominals at the top-level of C,   Rest (R,C)≡Exist(R,C) Univ(R,C) Atleast(R,C) Atmost(R,C) Exactly(R,C) with:       

     
       
         
           
             
               
                 Exist 
                 ⁡ 
                 
                   ( 
                   
                     R 
                     , 
                     C 
                   
                   ) 
                 
               
               ≡ 
               
                 
                   ⋂ 
                   
                     
                       C 
                       ′ 
                     
                     ∈ 
                     
                       ex 
                       ⁡ 
                       
                         ( 
                         
                           R 
                           , 
                           C 
                         
                         ) 
                       
                     
                   
                 
                 ⁢ 
                 
                   ∃ 
                   
                     R 
                     · 
                     
                       C 
                       ′ 
                     
                   
                 
               
             
             , 
           
         
       
         
         
           
             with ex(R,C) being the set of all C′ such that ∃R.C′ appears at the top level of C (C′ is a singleton in the case of ∃R.α restrictions, with α being an individual).
 
Univ( R,C )≡∇ R .val( R,C ),
 
             with val(R,C) being the conjunction C i    . . .  C n  in the value restriction of role R (here again, C i  is a singleton in the case of ∇R.α restrictions, with α being an individual). 
           
         
       
    
     
       
         
           
             
               
                 Atleast 
                 ⁡ 
                 
                   ( 
                   
                     R 
                     , 
                     C 
                   
                   ) 
                 
               
               ≡ 
               
                 
                   ⋂ 
                   
                     
                       C 
                       ′ 
                     
                     ∈ 
                     
                       al 
                       ⁡ 
                       
                         ( 
                         
                           R 
                           , 
                           C 
                         
                         ) 
                       
                     
                   
                 
                 ⁢ 
                 
                   ≥ 
                   
                     
                       n 
                       max 
                     
                     ⁢ 
                     
                       R 
                       · 
                       
                         C 
                         ′ 
                       
                     
                   
                 
               
             
             , 
           
         
       
         
         
           
             with al(R,C) being the set of all C′ such that ≧nR.C′ appears at the top level of C and with n max  being the highest n if more than one minimal cardinality exists for the same C′. 
           
         
       
    
     
       
         
           
             
               
                 Atmost 
                 ⁡ 
                 
                   ( 
                   
                     R 
                     , 
                     C 
                   
                   ) 
                 
               
               ≡ 
               
                 
                   ⋂ 
                   
                     
                       C 
                       ′ 
                     
                     ∈ 
                     
                       am 
                       ⁡ 
                       
                         ( 
                         
                           R 
                           , 
                           C 
                         
                         ) 
                       
                     
                   
                 
                 ⁢ 
                 
                   ≤ 
                   
                     
                       n 
                       min 
                     
                     ⁢ 
                     
                       ∃ 
                       
                         R 
                         · 
                         
                           C 
                           ′ 
                         
                       
                     
                   
                 
               
             
             , 
           
         
       
         
         
           
             with am(R,C) being the set of all C′ such that ≦nR.C′ appears at the top level of C and with n min  being the smallest n if more than one maximal cardinality exists for the same C′. 
           
         
       
    
     
       
         
           
             
               
                 
                   Exactly 
                   ⁡ 
                   
                     ( 
                     
                       R 
                       , 
                       C 
                     
                     ) 
                   
                 
                 ≡ 
                 
                   ⋂ 
                   
                     
                       C 
                       ′ 
                     
                     ∈ 
                     
                       exact 
                       ⁡ 
                       
                         ( 
                         
                           R 
                           , 
                           C 
                         
                         ) 
                       
                     
                   
                 
               
               = 
               
                 R 
                 · 
                 
                   C 
                   ′ 
                 
               
             
             , 
           
         
       
         
         
           
             with exact(R,C) being the set of all C′ such that =R.C′ appears at the top level of C. 
             Any sub-description C′ in ex(R,C), al(R,C), am(R,C), or exact(R,C) and any C i εval(R,C) is in Normal Form except if such C′ has already been rewritten (allow handling cyclic definitions of concepts such that C≡(∃R.C)). 
           
         
       
    
     Note that computing the SHOQ Normal Form of a concept requires writing it in Disjunctive Normal Form (DNF). Such operation is always possible by pushing negation inwards, using De Morgan laws and the duality between existential and universal ( ∃A ∇ A) as well as between atmost and atleast numbers restrictions. 
     As a convention, the set of direct subsumers of any concept CεE O  will be written  S D   (C), while its set of direct subsumees will be written  S D   (C). 
     In the current state of the art, although a lot of semantic similarity measures have been designed, none of them takes into account the peculiarities of the SHOQ logic where concepts can, for example, be defined using a hierarchy of (possibly transitive) properties. Moreover, in the SHOQ description logic, concepts can be defined using “nominals,” another specificity that has not been taken into account in the state of the art. 
     The following acronyms or definitions are used in this disclosure:
         DL: Description logic.   ALE: A particular description logic comprising a set of logical operators.   ALC: Another description logic containing logical operators that are not in ALE.   SHI: Yet another description logic containing logical operators that are not in ALE or ALC.   LCS: Least common subsumer. The LCS of two concepts C and D is defined as the least common concept that subsumes both C and D. In such definition, the LCS results from a computation procedure and may lead to generating a new concept (potentially added in the ontology).   LCA: Least common ancestor. The LCA denotes the most-specific named concept that subsumes two concepts. Unlike the LCS, the LCA is obtained solely by using the subsumption graph of the ontology and never leads to the generation of a new concept.   The “root” concept of an ontology refers to the concept that subsumes all others.   GCS: Good common subsumer of two concepts.   RCS: Relevant common subsumer of two concepts.   IC: Information content function.       

     Many different semantic similarity measures using the topology of an ontology have already been developed. These approaches can be classified as being based on two different types of semantic similarity measures: extentional measures and intentional measures. Extentional similarity measures use extensions of the concepts that they compare (i.e., their instances) to determine a similarity value, while intentional similarity measures focus on the structure of the concept definitions in order to evaluate their similarity. Both types of measures have limitations when used in the context of SHOQ-based ontologies. 
     The present disclosure defines a new semantic similarity measure that relies on an algorithm that (i) expands the classification graph of any ontology underlied by the SHOQ description logic and (ii) weights the nodes of such graph. Based on a SHOQ normal form (explained below) and a family of generative functions, the algorithm uses various subsumption properties (also explained below) taking into account the specifics of the SHOQ DL to generate a set PS of pseudo-concepts allowing a semantic Web engine to determine additional inferences when reclassifying the ontology. 
     Although useless from the domain definition point of view, these pseudo-concepts are useful when computing semantic similarity by making explicit the underlied semantics implied by the concepts originally defined. All the concepts (including the pseudo-concepts) of the expanded graph are further weighted using their outdegree as well as the weight of their children (0 if the node is a leaf). In a graph made of nodes and node-connecting edges, the outdegree of a node is the number of outgoing edges at that node. These weights are further used when computing the semantic similarity of any two concepts, in the case of such concepts having dissimilar fragments of semantics in their descriptions. 
       FIG. 2  graphically represents an algorithm for computing the semantic similarity between different concepts having been defined in an ontology underlied by the SHOQ description logic, according to one embodiment of the disclosure. As shown in  FIG. 2 , an original ontology  210  containing a number of inter-related complex concepts  212  is input to system  200 , which performs concept expansion  220  that generates an expanded ontology  230  containing the original complex concepts  212  plus a number of pseudo-concepts  232 . Concept expansion  220  generates pseudo-concepts based on the specificities of the SHOQ description logic, for example, where ontological concepts can be defined using hierarchically (potentially) transitive roles. 
       FIG. 3  shows pseudo-code for a procedure that generates pseudo-concepts that are subsumed by a concept C in an ontology O, while  FIG. 4 . shows pseudo-code for a procedure that generates pseudo-concepts that subsume a concept C in ontology O. Note that the pseudo-code of  FIG. 3  calls the procedure “SUBSUMERS,” which is defined in  FIG. 4 , while the pseudo-code in  FIG. 4  calls the procedure “SUBSUMEES,” which is defined in  FIG. 3 . 
     After generating the pseudo-concepts  232 , the system  200  applies similarity measure computation  240  to the resulting expanded ontology  230  to generate one or more measures of the semantic similarity between different pairs of concepts. For a given pair of concepts in the expanded ontology  230  (e.g., two original concepts, two pseudo-concepts, or one original concept and one pseudo-concept), similarity measure computation  240  generates a single measure characterizing the semantic similarity between the two concepts. The semantic similarity measure is based on the common and dissimilar semantics in the concept descriptions for each pair of compared concepts. Note that, although it is possible to generate a semantic similarity measure for any given pair of concepts in the expanded ontology  230 , the interest is on generating semantic similarity measurements for any pair of concepts in the original ontology  210 . 
     Concept-Expansion Mechanism 
       FIG. 5  shows a flow diagram of the concept-expansion mechanism  220  of  FIG. 2 . As shown in  FIG. 5 , in step  502 , the original ontology  210  is loaded into the system  200  of  FIG. 2  that performs similarity computation. This step creates a knowledge base that a semantic engine can analyze to perform inference tasks. As such, this step can be implemented using a suitable standard API, such as the OWL API available at http://owlapi.sourceforge.net/. 
     In step  504 , the system  200  classifies the original concepts by computing inferences using the original ontology. This step can be performed using tools found in the state of the art, such as Fact++ available at http://owl.man.ac.uk/factplusplus/, Hermit available at http://hermit-reasoner.com/, or Pellet available at http://clarkparsia.com/pellet/. 
     In step  506 , whenever possible, the system rewrites a concept definition (e.g., C) by replacing any defined concept (e.g., A) appearing on the right-hand side of the concept definition by its expression 
             (       e   .   g   .     ,     {                 A   =     B   ⋂   D                 C   =     ∃     R   ·   A                           ⇒   C     =     ∃     R   ·     (     B   ⋂   D     )           )     .                     
This rewriting step enables the system  200  to detect cyclic definitions (e.g., a concept C defined such as: C=∃R.C) and to compute SHOQ normal forms.
 
     In step  508 , the system  200  rewrites sub-class axioms by replacing all defined concepts appearing in subsumption axioms (e.g., C ⊂ D) by their expression computed in step  506 . A consequence of this rewriting is that any subsumption axiom may become a General Concept Inclusion (GCI). For example, an axiom such as C ⊂ D may be rewritten as the GCI (A∩B) ⊂ (E∩F). 
     In step  510 , the system  200  rewrites each concept in the original ontology (that is not already written in its SHOQ normal form) into its SHOQ normal form, extending the concept of ALC normal form used in C. d&#39;Amato, N. Fanizzi, and F. Esposito, “A dissimilarity measure for ALC concept descriptions,”  Proceedings of the  2006  ACM Symposium on Applied Computing , pages 1695-1699, ACM, New York, 2006, the teachings of which are incorporated herein by reference in their entirety. This step enables the system  200  to elicit the semantics of concepts. 
     Step  510  consists of rewriting concepts in disjunctive normal form. Each disjunct of this form is in conjunctive normal form (CNF). The conjuncts composing the CNF are gathered according to their types, such as primitives (i.e., concepts that are not complex), nominals (i.e., concepts defined by a set of one or more instances), universal restrictions (i.e., conjuncts expressed with qualified values), existential restrictions (i.e., conjuncts expressed with full existential qualification), minimal cardinality restrictions (i.e., conjuncts expressed with qualified minimal cardinality), maximal cardinality restrictions (i.e., conjuncts expressed with qualified maximal cardinality), and exact cardinality restrictions (i.e., conjuncts expressed with qualified exact cardinality). Note that this formula for rewriting concepts in disjunctive normal form relies on logical operators found only in ALCOQ (a sub-logic of SHOQ). 
     In step  512 , the system  200  generates zero, one, or more pseudo-concepts for each original concept defined in the original ontology and having been rewritten in SHOQ normal form. This step takes into account the specific case of existential restrictions with a transitive property on a domain defined through nominals. 
     For each original concept found in the ontology being studied, a set of pseudo-concepts can be generated using a family of generative functions. In particular, these functions analyze each conjunct of each disjunct of the SHOQ normal form of each original concept. For a given conjunct, the generative functions make use of subsumption relations that can be found with operators of the DL SHOQ (see Appendix). The generative functions try to apply the subsumption relations to each conjunct that is expressed as a set of restrictions. In particular, the generative functions make use of subsumption relations involving qualified value restrictions (P.2 of Appendix), full existential qualification (P.4), and qualified cardinal restrictions (P.6 and P.8). Additionally, the generative functions also derive pseudo-concepts based on the subsumption properties that can be determined when conjuncts are expressed with properties having either super- or sub-properties (P.1 if such properties are applied in a universal qualification, P.3 in the case of an existential qualification, P.5 in the case of minimal cardinality, and P.7 in the case of maximal cardinality). Finally, the generative functions can determine additional subsumption relations when concepts are expressed with transitive properties (P.9). 
     After the pseudo-concepts have been generated in step  512 , in step  514 , the system  200  updates the knowledge base by performing a classification task (e.g., similar to step  504 ) for the resulting expanded ontology  230 . 
     Similarity Measure Computation 
     As described previously, following concept expansion  220  of  FIGS. 2 and 5 , the system  200  performs similarity measure computation  240  on the resulting expanded ontology  230 . In order to describe this function, the following notations are introduced:
         Go refers to the original classification graph (i.e., the graph without any pseudo-concepts, such as the classification graph for the original ontology  210  of  FIGS. 2 and 5 ).   Eo refers to the expanded classification graph (i.e., the graph with all pseudo-concepts, such as the classification graph for the expanded ontology  230  of  FIGS. 2 and 5 ).       

     Based on Eo, a semantic similarity measure can be proposed for any two concepts of Go. In one embodiment, this measure focuses on evaluating both the common and the different semantics that these two concepts share. Towards this goal, and for any two concepts in Go, their common semantics are based on the number of semantically equivalent pseudo-concepts that they share in their descriptions. A relevant common subsumer (RCS) in Eo subsuming (at least) the union of the dissimilar semantics of these two concepts can also be determined. 
     Computing the RCS of the dissimilar semantics of any two concepts is explained hereafter. Since this method is computationally expensive, it might be applied only for relatively small ontologies. For large ontologies, the RCS may be represented simply by the union of the dissimilar semantics of the two concepts. 
     The following presents the concepts and definitions that underlie the determination of the RCS, which, in some embodiments, is a pre-requisite in order to get semantic similarity measurements. 
     First, a concept weight ω is associated with each concept C of Eo. In some embodiments, the concept weight ω can be given by the following formula: 
                 ω   ⁡     (   C   )       =           ∑     α   ∈         S   D     ⁡     (   C   )       _                 ⁢     ω   ⁡     (   α   )         +   1                S   D     _     ⁡     (   C   )                ,         
where:
 
       S D   (C) refers to the set of direct subsumees of concept C in Eo; and 
     | S D   (C)| refers to the set of direct subsumees of concept C in Eo. 
     Along with the concept weight ω, a branch weight Ω is associated with each branch that links two concepts in Eo. In general, any two concepts in Eo may be linked by one or more branches due to the one or more subsumers that any given concept may have in Eo.  FIG. 6  shows an example of two “branches” linking concepts A and C in an exemplary graph Eo: one branch involving concept B 1  and the other branch involving concepts B 2 -B 5 . In some embodiments, for two concepts E and F, the branch weight Ω can be given as the sum of the concept weights ω of the concepts in the branch (including the concepts E and F) by the following formula: 
                 Ω   ⁡     (     B   ⁡     (     E   →   F     )       )       =       ∑       C   i     ∈     B   ⁡     (     E   →   F     )           ⁢     ω   ⁡     (     C   i     )           ,         
where:
 
     B(E→F) refers to a branch between concepts E and F in Eo; and 
     C i  is a concept in that branch. 
     Note that concepts C i  are represented in  FIG. 6  by labels A, C, B 1 , B 2 , B 3 , etc. 
     Based on one or more different branch weights Ω having been computed (i.e., one weight Ω per branch, where there can be multiple branches resulting from the fact that nodes may have multiple subsumers, as in the example of  FIG. 6 ), the RCS of two concepts E, F is the direct subsumer (or one of the direct subsumers taken arbitrarily) of E∪F minimizing the sum of the weights of the two branches B(E→C) and B(F→C). Formally,
 
 C   0 εarg minψ( C ),
 
where function ψ is defined as follows:
 
                         Ψ   ⁢     :     ⁢               ⁢         S   D     _     ⁡     (     E   ⊔   F     )         C           →       R                       →             min       ℬ   i     ∈           ⁢     ⁢           ⁢     (     E   →   C     )           ⁢     (     Ω   ⁡     (       ℬ   i     ⁡     (     E   →   C     )       )       )       ⁢                                         min       ℬ   i     ∈           ⁢     ⁢           ⁢     (     F   →   C     )           ⁢       (     Ω   ⁡     (       ℬ   i     ⁡     (     F   →   C     )       )       )     .                                   
In other words, determining the RCS of concepts E and F accounts for finding the most-appropriate direct subsumer (DS) amongst the set of direct subsumers (DSi) of the union of the semantics of E and F (E∪F). To achieve this, the following procedure is performed.
 
     For each direct subsumer DSi, two set of weights (S1(DSi) and S2(DSi)) are computed. S1(DSi) refers to all weights Ω being computed between concepts E and DSi (recall that there is one weight Ω per branch, while there can be several branches between two concepts). S2(DSi) refers to all weights Ω being computed between concepts F and DSi. The application of function ψ on DSi returns the sum of the lowest number in S1(DSi) and the lowest number in S2(DSi). For N direct subsumers of the union of the semantics of concepts E and F (N DSi), N numbers are provided by the application of function ψ, leading to a set S3. The RCS of concepts E and F is the one having generated the lowest number by function ψ (provided by the arg min function). If several DSi lead to the same value, then one of them is arbitrarily chosen. 
     With all these definitions, the semantic similarity sim of any two concepts A, B can be computed according to the following formula: 
                 sim   ⁡     (     A   ,   B     )       =         2   ×       n   c     ⁡     (     A   ,   B     )             n   t     ⁡     (     A   ,   B     )         +     [       (     1   -       2   ×       n   c     ⁡     (     A   ,   B     )             n   t     ⁡     (     A   ,   B     )           )     ×     (       2   ×   I   ⁢           ⁢     C   ⁡     (     R   ⁢           ⁢   C   ⁢           ⁢   S   ⁢           ⁢     (       δ   ⁡     (     A   ,   B     )       ,     δ   ⁡     (     B   ,   A     )         )       )             I   ⁢           ⁢     C   ⁡     (     δ   ⁡     (     A   ,   B     )       )         +     I   ⁢           ⁢   C   ⁢           ⁢     (     δ   ⁡     (     B   ,   A     )       )           )       ]         ,         
where:
 
     n c (A,B) refers to the number of semantically equivalent concepts in  S D   (A) and  S D   (B); 
     n t (A,B) refers to the number of direct subsumers of concepts A and B and is equal to | S D   (A)+ S D   (B)|; and 
     IC is the information content function. 
     In some embodiments, the information content function IC is defined by the following formula: 
                 I   ⁢           ⁢     C   ⁡     (   A   )         =     -     log   ⁡     (       1   +       n   s     ⁡     (   A   )           1   +       n   s     ⁡     (   Top   )           )           ,         
where:
 
     Top refers to the root concept in the ontology where concept A is defined; and 
     n S (A) is the total number of subsumers of concept A in the expanded graph Eo. 
     Finally, the semantic function δ(A,B) is used in order to evaluate the different semantics of two concepts and, in some embodiments, is defined as follows: 
                   δ   ⁢     :               ??   O     ×     ??   O           →         ??   O                           (     A   ,   B     )         →         {               ⊓   i     ⁢       C   i     ⁢           ⁢   such   ⁢           ⁢   that   ⁢           ⁢     C   i         ∈           S   D     _     ⁡     (   A   )       ⊓     ⫬         S   D     _     ⁡     (   B   )                         A   ⁢           ⁢   if   ⁢           ⁢     ∀       C   i     ∈         S   D     _     ⁡     (   A   )             ,       C   i     ∈         S   D     _     ⁡     (   B   )                             
The semantic function δ(A,B)) returns the piece of semantics that is covered by the definition of A and not by the definition of B. Note that, if the definition of A is included in B, then δ returns A.
 
     The similarity formula sim(A,B) given above computes the similarity of two ontological concepts A and B by relying on two intermediate similarity results (i.e., the two expressions summed in the formula). The first one results from the analysis of the common semantics found in both concepts, while the second one accounts for quantifying the partial similarity of the dissimilar semantics found in both concepts. 
     In particular, both intermediate results take into account the number n t (A,B) of direct subsumers of both concepts. In addition, the second intermediate result takes into account the relevant common subsumer (e.g., RCS(δ(A,B),δ(B,A))) of the dissimilar semantics of both concepts. Note that alternative versions of the similarity formula may utilize the least common subsumer, the good common subsumer, or any other suitable definition of a subsumer, instead of the relevant common subsumer. 
     Furthermore, the second intermediate result relies on a quantification of the information content (IC) conveyed by a concept, where the IC is quantified as a negative log likelihood (e.g., IC=−log X). While the IC function IC(A) given above relies on a particular expression of X, other suitable expressions may be used in alternative versions of this function. See, e.g., P. Resnik, “Using information content to evaluate semantic similarity in a taxonomy,” IJCAI, pages 448-453, Morgan Kaufmann, 1995, the teachings of which are incorporated herein by reference in their entirety. 
       FIG. 7  shows a flow diagram of similarity measure computation  240  of  FIG. 2 , according to certain embodiments of the disclosure. In particular,  FIG. 7  shows the process of system  200  of  FIG. 2  computing a similarity measure between one or more different pairs of concepts in exemplary expanded ontology  230  of  FIG. 2 . In the flow diagram of  FIG. 7 , each pair of concepts is generically labeled A and B. The steps in  FIG. 7  are based on the math presented above. 
     In step  702 , the system  200  computes the weight ω for each concept (including each pseudo-concept) in the expanded graph Eo. 
     In step  704 , the system  200  selects a (next) pair of concepts A and B. 
     In step  706 , the system  200  computes (i) the number n c (A,B) of semantically equivalent concepts in the direct subsumer sets  S D   (A) and  S D   (B) and (ii) the number n t (A,B) of direct subsumers of concepts A and B. 
     In step  708 , the system  200  determines whether or not the number n t (A,B) of direct subsumers of concepts A and B is twice as big as the number n c (A,B) of semantically equivalent concepts in the direct subsumer sets  S D   (A) and  S D   (B). If so, then the similarity measure between the concepts A and B is set to 1 (step  710 ), and, if the similarity measure between another pair of concepts is to be computed, then processing returns to step  704 . Although the processing of step  708  is based on a factor of 2 between n t (A,B) and n c (A,B), other factors can be used in other implementations. 
     If the comparison of step  708  is not true, then processing continues to step  712  if the user wants (possibly less-accurate) results sooner or to step  716  if the user wants more-accurate results. If the user indicates that results need to be obtained as quickly as possible, then the system  200  generates the semantic functions δ(A,B) and δ(B,A) in step  712 , and, in step  714 , the system  200  sets the relevant common subsumer (RCS) for concepts A and B equal to the union of the semantic functions δ(A,B) and δ(B,A). Processing then continues to step  724 , which will be explained below. 
     If, instead, the user indicates that more-accurate results are needed, then processing proceeds to step  716 , where the system  200  generates the semantic functions δ(A,B) and δ(B,A). 
     In step  718 , the system  200  determines the set {Ci} of direct subsumers of the union of δ(A,B) and δ(B,A) in the expanded graph Eo. 
     In step  720 , the system  200  computes the weight ω of each branch B(δ(A,B)→C i ) and each branch B(δ(B,A)→C i ). 
     In step  722 , the system  200  generates the RCS for concepts A and B using the function ψ. 
     In step  724 , the system  200  computes the information content functions IC for the RCS of step  714  or step  722  and for the individual semantic functions δ(A,B) and δ(B, A) of step  712  or  716 . 
     In step  726 , the system  200  computes the semantic similarity measure sim for the concepts A and B. If the similarity measure between another pair of concepts is to be computed, then processing returns to step  704 . 
     APPENDIX—SUBSUMPTION RELATIONS IN SHOQ 
     The following presents the different subsumption relations that ground the definition of the generative function family F G . These properties involve the role hierarchy   of a knowledge base as well as the logical operators of the DL SHOQ given previously. 
     For a given role Rε , S +  denotes any of its superproperties and S −  denotes any of its subproperties. With these conventions, the following subsumption properties exist: 
     Subsumption Properties on Universal Restrictions:
         P.1: ∇S + .X ⊂ ∇R.X ⊂ ∇S − .X.   P.2: X ⊂ Y→∇R.X ⊂ ∇R.Y       

     Subsumption Properties on Existential Restrictions:
         P.3: ∃S − .X ⊂ ∃R.X ⊂ ∃S + .X   P.4: X ⊂ Y→∃R.X ⊂ ∃R.Y       

     Subsumption Properties on Cardinal Restrictions:
         P.5: ≧nS − .X ⊂ ≧nR.X ⊂ ≧nS + .X   P.6: X ⊂ Y→≧nR.X ⊂ ≧nR.Y   P.7: ≦nS+.X ⊂ ≦nR.X ⊂ ≦nS − .X   P.8: X ⊂ Y≦nR.Y≦nR.X       

     Subsumption Properties on Existential Restrictions Involving a Transitive Property and Nominals:
         P.9: RεN R     +     C ≡∃R.{a 0 , . . . , a n } ∇εε{a 0 , . . . a n }, ∃ηεD≡{b 0 , . . . b p } such that it holds R(ε,η)├∃R.{a n , . . . , a n } ⊂ ∃R.{b O , . . . , b p }       

     Although the disclosure has been described in the context of a process that computes a similarity measure after performing concept expansion on an original ontology, there may be other contexts in which concept expansion may be applied. 
     Although the disclosure has been described in the context of SHOQ ontologies, other contexts involving other ontologies are also possible, such as other ontologies having concepts defined using a hierarchy of (possibly transitive) properties. 
     Furthermore, the semantic similarity function sim(A,B) can be applied to other ontologies, including those that do not have concepts defined using a hierarchy of properties. 
     Embodiments of the invention may be implemented as (analog, digital, or a hybrid of both analog and digital) circuit-based processes, including possible implementation as a single integrated circuit (such as an ASIC or an FPGA), a multi-chip module, a single card, or a multi-card circuit pack. As would be apparent to one skilled in the art, various functions of circuit elements may also be implemented as processing blocks in a software program. Such software may be employed in, for example, a digital signal processor, micro-controller, general-purpose computer, or other processor. 
     Embodiments of the invention can be manifest in the form of methods and apparatuses for practicing those methods. Embodiments of the invention can also be manifest in the form of program code embodied in tangible media, such as magnetic recording media, optical recording media, solid state memory, floppy diskettes, CD-ROMs, hard drives, or any other non-transitory machine-readable storage medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. Embodiments of the invention can also be manifest in the form of program code, for example, stored in a non-transitory machine-readable storage medium including being loaded into and/or executed by a machine, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code segments combine with the processor to provide a unique device that operates analogously to specific logic circuits. 
     Any suitable processor-usable/readable or computer-usable/readable storage medium may be utilized. The storage medium may be (without limitation) an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device. A more-specific, non-exhaustive list of possible storage media include a magnetic tape, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM) or Flash memory, a portable compact disc read-only memory (CD-ROM), an optical storage device, and a magnetic storage device. Note that the storage medium could even be paper or another suitable medium upon which the program is printed, since the program can be electronically captured via, for instance, optical scanning of the printing, then compiled, interpreted, or otherwise processed in a suitable manner including but not limited to optical character recognition, if necessary, and then stored in a processor or computer memory. In the context of this disclosure, a suitable storage medium may be any medium that can contain or store a program for use by or in connection with an instruction execution system, apparatus, or device. 
     It should be appreciated by those of ordinary skill in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudo-code, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer or processor, whether or not such computer or processor is explicitly shown. 
     It will be further understood that various changes in the details, materials, and arrangements of the parts which have been described and illustrated in order to explain embodiments of this invention may be made by those skilled in the art without departing from embodiments of the invention encompassed by the following claims. 
     The use of figure numbers and/or figure reference labels in the claims is intended to identify one or more possible embodiments of the claimed subject matter in order to facilitate the interpretation of the claims. Such use is not to be construed as necessarily limiting the scope of those claims to the embodiments shown in the corresponding figures. 
     It should be understood that the steps of the exemplary methods set forth herein are not necessarily required to be performed in the order described, and the order of the steps of such methods should be understood to be merely exemplary. Likewise, additional steps may be included in such methods, and certain steps may be omitted or combined, in methods consistent with various embodiments of the invention. 
     Although the elements in the following method claims, if any, are recited in a particular sequence with corresponding labeling, unless the claim recitations otherwise imply a particular sequence for implementing some or all of those elements, those elements are not necessarily intended to be limited to being implemented in that particular sequence. 
     Reference herein to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment can be included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments necessarily mutually exclusive of other embodiments. The same applies to the term “implementation.” 
     The embodiments covered by the claims in this application are limited to embodiments that (1) are enabled by this specification and (2) correspond to statutory subject matter. Non-enabled embodiments and embodiments that correspond to non-statutory subject matter are explicitly disclaimed even if they fall within the scope of the claims.