Ontology classifier

Ontologies are based on the idea of axioms, which are statements about things made by humans that are said to be probably true, and represent the current knowledge of the authors that make them. The statements do not require proof, but are used by systems, as if they were true and are unchallenged.

Ontology reasoners test the contents of an ontology to assure their consistency. As part of that process a reasoner categorises or "classifies" the concepts such that a concept that appears in a tree view below another concept, is said to be subsumed by that concept. For example, type II diabetes is a subclass of Diabetes Mellitus.

A reasoner will take a set of objects of certain types and classify them into the appropriate category. The classifier does this within the T-Box of the ontology as well as the A-Box i.e. undertakes a subsumption test of one concept against another. In practice this process occurs during authoring but is also used to generate and output that can be used in more straightforward conventional query engines.

Axioms and classifier

Two styles of axioms are used:

1. Simple subtype axioms, such as a subclass or sub property statement, which explicitly state that concept C is a subtype of concept S. This means that the set of objects described by concept S includes the set of objects described by C. Sometimes a concept C is said to be a subclass of an intersection of concepts S1 and S2. A Venn diagram illustrated this. This means that concept C describes a set of objects with all of the properties of concept S1 AND all of the properties of concept S2. These types of axioms imply less than complete information, in that subclass C may have other properties not explicitly articulated. It is not possible to mathematically infer that another concept c-sub is a subclass of C, if C is itself a subclass because of the potential of other properties not yet stated. Subclass axioms provide the bare minimum and are said to be "necessary but not sufficient" to define a concept. The second style of axiom represents a more complete approach.
2. Equivalent class axioms. These state that concept A is equivalent to concept B. Usually concept B is defined by being a combination of concept C and a set of properties P. These types of axioms imply more complete information in that A, being equivalent, will not have more properties than B. They are said to be "sufficiently defined". From A, further subclasses can be inferred.

Classes are further defined by their properties and the type of values (ranges) of those properties. Not all properties are explicitly listed (indeed, all objects have an infinite number of properties) and only those of relevance to the current use of the the knowledge base are articulated. The use of properties enables a reasoner to infer that another concept may be a subtype of a concept by using a combination of stated axioms and their properties.

A source of confusion is the fact that many classes have names. Whilst this helps humans understand the meaning of the class, (e.g. Diabetes) from a computable perspective, these names are meaningless. It is the properties of these classes that are used in subsumption testing, aided somewhat when a human has specifically stated, via an axiom, that a class is a subclass of, or equivalent to, another class.

In order to enable an ontology to be used in practice, the general approach is to generate inferred subtype relationships from the ontological source. An inferred view is a view of these relationships as a hierarchy of concepts, from the top level down of the kind used by Snomed-CT browsers. The inferred output contains all of the necessary constructs to be able to perform standard queries such as subsumption testing or queries across post coordinated expressions. Queries do not require inferred views to work, but they are substantially simpler to implement when an inferred view is used.

The approach in this article can be considered as a simplified subset of an OWL2 reasoner, focusing on classification. A classifier essentially creates a set of statements that link concepts together by an "is a" relationship i.e. "is a" means that concept C is "either the same as, or a subtype of", concept S . The 'is a' relationships are further pruned to make the view simpler by making sure that if concept A -> is a subtype of -> concept B, and if concept A-> is a subtype of -> Concept C, and if concept B -> is a subtype of -> concept C, then the statement that concept A-> is a subtype of -> concept C is removed, as it can be inferred from the A-> B relationship. Thus the view is less messy to navigate as a result.

The algorithm described in this article assumes certain constrained editorial policies, namely:

1. 'Object Union of' are rarely used. Use of object unions can result in exponential times for subsumption testing.
2. 'Object complement of' is not supported. It is assumed that negation is considered only in the concept of closed world query e.g. for generating value sets whereby concepts are automatically filtered out, whereas the use of object complement often rules everything else out also as the reasoner does not know whether an otherwise included concept is negated or not.
3. General concept inclusion axioms (GCI axioms) are ignored in generating the inferred view. This is based on the assumption that if these axioms are to be used then a reasoner would know how o use them without creating an "is a" relationship.

The classifier is NOT a reasoner in that it does not check for inconsistencies

Working example

The working example used in this article is a simple ontology of amoxicillin 500 mg presented in two syntaxes. The example contains only the main class axioms for brevity

Manchester syntax:

Class: im:AmoxicillinProduct
    EquivalentTo: 
        im:MedicinalProduct
         and (im:hasRoleGroup some (im:hasIngredient some im:Amoxicillin))
 
Class: im:Amoxicillin500mg
    EquivalentTo: 
        im:MedicinalProduct
         and (im:hasRoleGroup some 
            ((im:hasIngredient some im:Amoxicillin)
             and (im:hasStrength some im:Fivehundredmg)))
 

In Discovery json syntax this can be represented as

Discovery syntax:

{"Class" : [ {
      "iri" : "im:AmoxicillinProduct",
      "EquivalentTo" : [ {
        "Intersection" : [ {
          "Class" : "im:MedicinalProduct"
        }, {
          "ObjectSome" : {
            "Property" : "im:hasRoleGroup",
            "ObjectSome" : {
              "Class" : "im:Amoxicillin",
              "Property" : "im:hasIngredient"
            }
          }
        } ]
      } ]
    }, {
      "iri" : "im:Amoxicillin500mg",
      "EquivalentTo" : [ {
        "Intersection" : [ {
          "Class" : "im:MedicinalProduct"
        }, {
          "ObjectSome" : {
            "Property" : "im:hasRoleGroup",
            "Intersection" : [ {
              "ObjectSome" : {
                "Class" : "im:Amoxicillin",
                "Property" : "im:hasIngredient"
              }
            }, {
              "ObjectSome" : {
                "Class" : "im:Fivehundredmg",
                "Property" : "im:hasStrength"
              }
            } ]
          }
        } ]
      } ]
    }
}

The two main classes are defined by their properties, the names being assigned for readability purposes. In this case the drugs are said to have a property referred to as a "role group".

A 'role group' is a naming convention for an anonymous property whose value is an object from an anonymous class. in this case the different role group's have class with different properties.

As defined the two classes appear independent i.e.

• Amoxcillin product is equivalent to a product, that has a role group, that has an ingredient of the substance amoxicillin

• Amoxicillin 500mg is equivalent to a product, that has a role group ,that has an ingredient of the substance amoxicillin AND a strength of 500mg.

Intuitively, it is easy to see a relationship between them. It is reasonable to infer that the second product appears to be a sub type of the first. However, that is a human inference. A computer has to rely on logical inference.

A classifier generates the "is a" relationship by testing whether the second product is subsumed by the first.

Classifier algorithm

To put it simply the algorithm is in two steps:

1. For each class 'S' in the ontology, find all the classes C1,C2.....Cn that are subsumed by S
2. Organise the subtypes into the most efficient tree structure so that if class C1 is subsumed by S1 and S2, and if S2 is subsumed by S1, then the downward tree view is S1-> S2- > C1

The ISA relationship

If C-> ISA> S then this means that C is a subtype of S, or the set of C is a subset of the set of S.

The algorithms use logical inference to infer that C -> is a - > S via a number of mechanisms.

In addition, in Discovery "is a like" relationships are also generated as a result of semantically inexact mappings "mapped to" as well as the properties "replaced by", and its reciprocal "replaced". These are not strictly 'is a' relationships as they may or may not be subtypes, but they are optionally used in subsumption query to find related concepts in records.

The 'is a' relationship is transitive. This means that if A ISA B, and B ISA C, then A ISA C. This is used in subsumption testing.

Algorithm Steps

Step 1 indexing of ontology and anonymous class generation

In order to improve efficiency, it is useful to have an index of all properties and ranges to the class definitions so that for any property, or property range pair, the set of classes that have that property explicitly modelled can easily and quickly be found. In effect this is a simple inverted index.

Account must be taken of nested or complex ranges in class expressions. In the working example, the property "role group" appears in two different classes, each with a different range. Each range is further defined by a complex class expression consisting in one case of a property/ class pair, and in the other as an intersection of 2 property/class pairs.

The indexer may at this point creates two anonymous classes:

_a1 which has property of ingredient with a range of amoxicillin

_a2 which is an intersection of an ingredient with a range of amoxicillin, and a strength with a range of 500 mg

Thus amoxicillin 500 mg product would have a property of "role group" with a range of a2. As far as the computer is concerned _a1, _a2 is of the same significance as amoxicillin product.

Step 2 - Initial inference tree

A very large proportion of an inference tree already exists, via the axioms stated by humans, which are:

• C : 'SubclassOf ' S they are both named classes then C -> is A > S and S -> infers -> C

• C  :'EquivalentTo' S then C-> is a -> S, and S-> subsumes- >C

• P: 'SubObjectPropertyOf' PS then P -> is a >PS and PS-> subsumes -> P (likewise sub data property)

It does not matter whether the subclass or equivalent axioms use intersections or unions with additional properties in their definitions. They are still "is a" relationships.

Creation of an inferred tree results in performance improvements as an already stated 'is a' relationship need not be examined. In addition, the resulting inferred view can also be used when testing for subsumption of properties and property ranges used in the rest of the algorithm.

For example:

Amoxicillin product is Equivalent to a Medicinal product AND property X and Y , therefore Amoxicillin -> is a> Medicinal product , or to put it another way: Medicinal product -> subsumes> Amoxicillin

Amoxicillin 500 mg product is equivalent to a medicinal product AND property Y and X, therefore Amoxicillin 500mg -> is a> medicinal product, or the other way round: Medicinal Product -> subsumes -> Amoxicillin 500 mg product.

IsA function

The isa function - isa(sub, super) is a function used throughout that steps up the populated inferred tree to indicate whether sub is the same as, or a subtype of, super.

It should be noted for this function to work it assumes both sub, and super have already been processed as subtypes. In other words the 'isa' function only works after a particular class and super-class has already been processed. This means that eventually the system falls back on primitive concepts authored as equivalent or subclasses by a human i.e. without a human stating that something is the same as or a subclass of, something else then the classifier can rely ONLY on properties to produce an inference tree. In practice, most classes and properties are placed somewhere in a subclass hierarchy so the reasoner tends to have a leg up when operating.

Step 3 - Property expression subsumption testing

Subsumption can be inferred from the testing of a class's properties and the property ranges, against other classes that also have the properties and ranges.

Account must be taken of the boolean logic of Intersection and Union e.g. via the use of a truth tree. When testing intersections (AND) all the expressions must be true. When testing union (OR) at least one of the expressions must be true. A truth tree branches on union and goes back to try again on another branch if one branch ends up as untrue.

In theory each expression could be tested against all other classes in the ontology, (except the ones that have already been subsumed as above). However, this results in poor performance. One means of improving performance is to use the property indexes to identify candidate concepts to test.

The subsumption testing can thus be divided into two steps for each concept:

a) Look for at least one of properties to access the property index with

b) Test each class that has the property (or a subproperty), and optionally narrow down further by range testing also.

In essence this uses the following pseudo code logic:

For each class C in the ontology 
          InferClass(C)

InferClass(c class)                  //Looks for classes to subsume
   IF equivalentClass is Object Intersection (or single) then
      For the FIRST c.property              // No Branch in truth tree
       for each c.p.range r
          if r not inferred then
             Infer(r)
          else null
           
          SubClasstest (c, p, r)           //found candidate
          SubRangetest (c,p,r)            //looks for candidates with subranges
          SubPropertytest(c,p,r)      //looks for candidates with subproperties

   ELSE
    IF Equivalent class is Object Union then
      for EACH c.property                   //Branching OR truth tree
       for each c.p.range r
         if r not inferred then
            Infer(r)
         else null
                
         SubClasstest (c, p, r)           //found candidate
         SubRangetest (c,p, r)            //looks for candidates with subranges
         SubPropertytest(c,p,r)      //looks for candidates with subproperties

---

The above provides a property to use against the property index to find other classes to test. As well as using the property index, potential candidates may have sub properties, or properties with ranges that are subtypes of the range. All need to be examined and therefore the above takes 3 approaches: The property and the range, a set of subclasses of the range, and a set of sub properties and the range. As follows:

SubRangeTest(s superclass, op operator, p property, c candidate)
  For each subtype of c  sub
        SubclassTest(s,op, p, sub)  // finding a subtype index
        SubRangeTest(s, op, p, sub)  // steps down the sub types of the range

SubPropertyTest(s superclass, op operator, p property, c candidate)
  For each subproperty of p  subprop
        SubclassTest(s,op, subprop, sub)  // finding a subtype index
        SubRangeTest(s,op, subprop, sub)  //Looks for subtypes of the range
        SubPropertyTest(s, op, subprop,sub)  //Steps down the sub properties

Having found a property and range to find in the index, find all of the classes that have that property and range and for each of them, test whether it is subsumed or not.

SubClassTest (s superclass, op operator, p property r range)
  for each class c with property p and range r
      SubTest(s, c)                    //Is c a subsumed by s?

SubTest (s superclass, c candidate)    //Gets to do a subsumption test
   if s not defined as equivalent then
           END test                     // cannot subsume from a subclass
                                        // unless already stated as such

    If class defined by intersection or single then
   (
      For each equivalent class e of s 
        if e not yet inferred 
           infer(e)                       //e must be processed first
        if c is not a subtype of s then 
            END TEST   // tests           // c must also be a subclass of 

      For each property p of s
         for each property p1 of c
            if isa(p1,p) then 
               for each range r of s.p
                 if r not yet inferred infer(r)
                 for each range r1 of c.p1
                   if isa(r1,r) then
                   IS SUBTYPE
                 NOT SUBTYPE
        NOT SUBTYPE

    )
    else (must be union)
     Logic as above but only one of the properties must match

Removal of redundant super classes

The algorithm described above would result in the following tree entries

Medicinal Product
      Amoxicillin Product
         Amoxicillin 500 mg
      Amoxicillin 500 mg

Because amoxicillin 500 mg is a subtype of amoxicillin it can now be removed from the tree as it is subsumed by both the medicinal product and the amoxicillin product.

The IsA axiom

The OWL language explicitly seperates a sub class from a sub property from an equivalent property.

However, for convenience it is often easier to treat these all the same.

Therefore in Discovery information modelling language, the inferred axiom 'IsA' is created as part of the language to be used in tree views, subsumption testing, or generation of transitive closure tables.