Mathematical concepts of order and ordering relations play multiple roles in semantic technologies. Discrete totally ordered data characterize both input streams and top-k rank-ordered recommendations and query output, while temporal attributes establish numerical total orders, either over time points or in the more complex case of startend temporal intervals. But also of note are the fully partially ordered data, including both lattices and non-lattices, which actually dominate the semantic strcuture of ontological systems. Scalar semantic similarities over partially-ordered semantic data are traditionally used to return rank-ordered recommendations, but these require complementation with true metrics available over partially ordered sets. In this paper we report on our work in the foundations of order measurement in ontologies, with application to top-k semantic recommendation in workflows. We conclude that true ordered set metrics are strongly preferable to traditional semantic similarities.
Order and sequence occur frequently in the semantic web and semantic technologies, but in different contexts and manners. First, data themselves can be ordered, for example in a time sequence or order of arrival to a data stream. When time stamps are available, a mathematical “total” (or “linear”) order arises. If events can occur simultaneously, then a “weak order” is needed so as to allow “ties”. And if event occurences can extend over time, then “interval orders” are needed to reflect the interactions between start and stop times of possibly overlapping events with different durations.
But data can be ordered from other ways and sources. In fact, the heart of semantic technology may be considered to be class structures, which sit at the cores of ontologies as taxonomic semantic categorization hierarchies. Such structures are mathematically “partial orders”, that is tree-like hierarchies supporting multiple inheritance, including lattices. Note that this is the most general case, as all total orders are weak orders, which are all interval orders, which are all partial orders. Also, all lattices are partial orders.
Whether input data or semantic categories are totally, weakly, intervally, or
partially ordered, in any semantic selection task there is a need to rank-order the
resulting calculations, in order to recommend particular choices to the user. And
the algorithmic methods used to make such recommendations must measure the
data in a way which acccommodates and respects its underlying mathematically
ordered nature, perhaps up to and including being fully partially ordered.
Our interest is 1) the proper use of metrics in partially-ordered data in order to
2) make top-k rank-ordered recommendations in semantic systems. We report
on the performance of order metrics in a test analytic semantic recommendation
task within multi-domain scientific workflows as part of the Signature
Discovery Initiative1 (SDI) [
We now introduce our test knowledgebase and use case within which we make
recommendations. Our use case concerns identifying signatures within generic
sequential data objects from multiple domains. While alignment of biosequences
has been in use for decades, it has only been recently recognized as a significant
method for analyzing non-biological sequences [
Domain Subdomain Symbols
SA-KB statistics are shown in Table 2. Note that we regard the class hierarchy, the core of the ontology, as a (partially) ordered data object of 157 classes organized into nine levels. But it’s not a tree, with an average of 1.68 parents per class. Thus methods in order theory are necessary to properly measure it.
FASTAs_Linux is connected to other individuals (shown in boxes), representing data objects on which it depends semantically, by object properties. For
# Classes (asserted) # Classes (inferred) Average # children/class Average # parents/class Class hierarchy height # Object properties # Individuals
Value 157 168 2.02 1.68 9 31 116 example, FASTAs_Linux was encoded with a particular mapfile represented by MapFile_Executables, of class Map_File, and is thus linked to it by Depends_On. MapFile_Executables effects a mapping from opcode symbols to tokens, and so is itself related by File_Constructed_Using to two individuals: Opcodes, of class Symbol_Set, representing the symbols of opcodes; and Cyber_Alphabet of class Alphabet, representing the token set used by the cyber domain. Recommendation proceeds when, given a fixed target individual (e.g. the FASTA file FASTAs_Linux) at a particular point in the workflow (e.g. as input to the BLASTer), calling for an object of a given type (e.g. scoring matrix), which of many candidates are recommended? We wish to see recommendations rank ordered by being most semantically similar, for example the matrix SM_Executable used for executable files being highly ranked, while SM_Genetics used for genetic sequences loweest ranked. 3
We now describe our semantic annotation metric methodology. Given a class
hierarchy, we have a number of metrics to measure pairwise distances between
classes. We collect the sets of classes associated with individuals, and can then
measure the overall extent of those sets of classes within the ontology, and using
a Hausdorff set distance can measure the overall metric similarity between them.
This supports the rank-ordered recommendation of the most closely related
objects of the same data type otherwise.
3.1 Distances in Ordered Semantic Structures
Real-world semantic hierarchies such as subsumption and composition are
usually cast as Directed Acyclic Graphs (DAGs) on a finite set of classes P . They
are typically bounded above with a top element > ∈ P , with ∀a ∈ P, a ≤ >;
can have (a moderate amount of) multiple inheritance; and branch downward
very strongly. These are best represented mathematically as partially ordered
sets (posets) P = hP, ≤i [
The first thought towards a metric in a graphical structure such as a semantic hierarchy is as the length of the minimum undirected path dMP (a, b) =
min p∈undirected paths(a↔b) |p|.
But such a distance ignores both the directional nature and the level structure of
the semantic hierarchy. Instead, the knowledge systems literature has focused on
semantic similarities [
M (a, b) : =
max IC(c).
c∈↑ a∩↑ b where ↑ a is defined analogously to ↓ a as the upset of a.
This then allows us to define the first of three standard semantic similarity-based
(SS-based) distances, the Jiang-Conrath distance [
dJC (a, b) = IC(a) + IC(b) − 2M (a, b).
The other two follow from the Resnik and Lin similarity measures [
M (a, b) log2(π)
, dR(x, y) = 1 + dL(x, y) = 1 −
2M (a, b) IC(a) + IC(b)
While all of these, including dMP , are somewhat standard metrics, our purpose
is more general, since we may not have such a weighting function available,
and semantic similarities are not required to be metrics satisfying the triangle
inequality. In seeking out the proper mathematical grounding, we turn to
order metrics [
We need to normalize distance to the size of the structure, so that we are
measuring the relative proportion of the overall structure two nodes are apart, or
in other words, what proportion of their potential maximum distance. These
normalized forms are (all ∈ [
, d¯T H(a, b) = dl(a, b) |P | − 1 dT H(a, b) |P | − 2 The metrics above measure distances between classes in an ontology, and in particular, for any two individuals x, y in our KB, it can measure the distance between its classes C(x), C(y). But in order to compare the entire semantic context of an individual x, we need to identify not just its classes C(x), but additionally the classes C(z), C(w) of any individuals z, w which x is related to, that is, to which x is connected via object properties. We may not wish to invoke all object properties in such connections, but perhaps particular ones. And these should be transitive, so that through transitive closure we can find both directly and indirectly related individuals. The SAO has two transitive object relations , sao:depends on and sao:has part, to play this role. But we don’t wish to restrict ourselves to just sao:depends on and sao:has part proper, but rather all of their sub-relations as well, for example sao:has corpus, which inherits from sao:depends on. So, for an individual x, let A(x) be the class annotations of x, defined as: A(x) is the set of all classes which either x or some other individual y, to which x is either directly or indirectly linked by a particular, transitive object property, or some sub-relation of one, are members of. From our example from Fig. 2, we have: A(FASTAs Linux) = { sao:alphabet, sao:corpus, sao:cyber sequence, sao:executable file, sao:FASTA file set, sao:linux executable file, sao:map file, sao:opcode, sao:symbol set } Consider an individual x with classes C(x) and full set of class annotations A(x). We wish to have measures of A(x) for various x, and to compare A(x) and A(y) for different individuals x, y. We first wish to capture the “spread” of A(x) within the ontology. Given a distance d, we use
Ed(x) =
PC1∈A(x) PC2∈A(x) d¯(C1, C2)
|A(x)|
2
∈ [
C∈A(x) D∈A(y) D∈A(y) C∈A(x) If d is a true distance function on P (positive definite, symmetric, satisfies triangle inequality) then Hd is also a distance function. 4
The left side of Fig. 3 shows distributions of the 1629 = 14, 196 distances d(C1, C2) between the 168+1 (for the bottom node) classes in the SA-KB. The right side shows the distributions of the 1126 = 6, 670 Hausdorff distances Hd(x, y) between the individuals. The left side of Fig. 4 shows the distribution of the extents E(x) of the individuals, while the right side shows the distribution of |A(x)|, the number of classes annotating each individual. We note the following:
– In Figs. 3 and 4, the distributions shown are not mutually correlated, rather each is sorted separately in descending order, and then overlaid in the figure. – The SS-based distances are convex, and of the SS-based distances, JC is likely the best in the sense of the most discriminative, although it has large regions in the high distances where it fails to distinguish class pairs. – For the poset distances, lower dominates upper (as discussed above), and is concave. When combined with lower, the resulting hourglass distance dT H is less concave and more linear, providing a wide range of discriminatory values, although less in the lower values. Below we will show that SS-based distances provide poor rank orderings for recommendations, wo while we will return to this issue, in the sequel dT H will be considered preferentially. – The Hausdorff distances are a “selection” of the values appearing in the class distances, in virtue of its max-min composition, effectively acting as a coarsened representation. – Extents Ed(x) and counts |A(x)| are shown separately, and our normalization factor is effective, with generally small correlations coefficients between Ed and |A|, especially for the poset distances, with Pearson correlation ρ(ET H (x), |A(x)|) = 0.23, while for the SS-based distances ρ > 0.5.
In our example in Fig. 2, from Equ. 1 we have that FASTAs_Linux is annotated by |A(x)| = 9 classes and, which are marked by ‘FL’ in blue in Fig. 5, and has extent ET H(x) = .0381. This is relatively low extent, but a relatively high count, as can be seen in Fig. 4.
Referring back to Fig. 1, consider that we are at the portion of the workflow where a BLASTer component has been identified, and connected to its input FASTA file using the output of the upstream encoder component. In order to complete the instantiation of the BLASTer component, we need to identify its one lacking input, namely a scoring matrix, and we need one which is as semantically compatible as possible. The five available scoring matrices are shown in Table 3, each of which has its own set of annotations, as shown in Table 4, which is arranged with gaps to show where annotations sets overlap and differ. Consider the one example scoring matrix SM_Executable. On the one hand, it differs from FASTAs_Linux in that it is annotated to sao:scoring_matrix, since it is a scoring matric, but to neither sao:FASTA_file_set, since it is not a FASTA file, nor to sao:linux_executable_file, since it can be used with any executable, not being specific to any particular operating system. The right side of Fig. 5 shows this annotation set in the dual ‘FL SM’ markings. In measuring the difference in the annotation sets A(FASTAs Linux) and A(SM Executable), the first thought is to cast them as sets X, Y and measure their symmetric difference |XΔY | = |(X \ Y ) ∪ (Y \ X)|, the number of different elements. We have |A(FASTAs Linux)ΔA(SM Executable)| = 3 for these three differing classes. Table 4 shows Δ for all the scoring matrices, along with HT H, the Hausdorff for the hourglass measure. But we actually observe that HT H is strongly preferred to Δ, in that it not only gets the correct rank ordering, but can also distinguish SM_Server_Logfiles as being preferable to SM_Logfile, in virtue of the fact that it doesn’t just count the differences, it can weight them by semantic distance, in this case that server_log_file is more specific y=SM Logfiles y =SM Genetics 0.059 0.148
8 12 0.041 0.076 8 9
edam:data 2976 sao:alphabet sao:alphabet sao:codon sao:corpus sao:alphabet
sao:alphabet sao:corpus sao:cyber sequence sao:executable file
sao:corpus sao:corpus sao:cyber sequence sao:cyber sequence sao:map file sao:opcode sao:scoring matrix sao:symbol set sao:log event sao:map file sao:log event sao:log file sao:map file
sao:file sao:gene sequence
sao:map file sao:scoring matrix sao:scoring matrix sao:scoring matrix sao:server log file sao:symbol set sao:symbol set sao:symbol set x =FASTAs Linux HT H (x, y) A(x)ΔA(y) E(y) |A(y)| sao:alphabet sao:corpus sao:cyber sequence sao:executable file sao:FASTA file set sao:linux executable file sao:map file sao:opcode sao:symbol set than log_file. Finally SM_Genetics is the least recommended scoring matrix, coming from another domain entirely, it is most divergent in both Δ and HT H . Considering the other metrics available, and referring back to Table 3, we can see the Hausdorffs for other distances, and that HT H is preferable to any of the SSbased measures, in that it can distinguish all of these examples, and rank-orders them correctly, where the SS-based distances cannot.
Broadening from our one example, we can consider an evaluation of the performance of order metrics relative to SS-based distances. To accomplish this, we considered all possible recommendations of a candidate individual against a fixed source individual in the four cases implied by the upper parts of our workflow in Fig. 1, specifically: 1) recommend symbol sets (candidates) against a mapfile (target); 2) recommend a map file against a fixed symbol set; 3) a scoring matrix against a FASTA file; and finally 4) a FASTA file against a scoring matrix. There were 33 targets across all four groups, and for each we independently established a “ground truth” for the ordering of the candidates. For example, in Table 3, ground truth for candidate scoring matrices against the FASTAs Linux target is the rank ordering shown, but with Server_Logfiles and Logfiles reversed. Then for each recommendation, we measured the Spearman rank correlation rs (averaging ranks over ties) for ground truth using each of the metrics. Results are shown in Fig. 6. Note that rs = 1 indicates complete agreement on rank order, while rs = −1 is a complete reversal of that order. Also, rs does not exist when all scores are the same, as exemplified by the SS-based metrics in Table 3. This was always true for minpath dMP , which was thereby eliminated, and was frequently true for the SS-based distances, as can be seen in Fig. 3.
While our results only hold within our test use case and KB, these were constructed independently of our evaluation. Poset metrics, especially lower and hourglas, provided strong performance for top-k semantic ranking, with high rank correlations above 80%. They were almost always preferable to SS-based metrics, and sometimes remarkably so, including negative rs values for some SS-based metrics.
This research is part of the Signature Discovery Initiative (http://signatures.pnnl.gov) at Pacific Northwest National Laboratory. It was conducted under the Laboratory Directed Research and Development Program at PNNL, a multi-program national laboratory operated by Battelle for the U.S. Department of Energy.