Ternary compound ontology matching for cognitive green computing

1.   Introduction

Cognitive green computing (CGC) amalgams the properties of cognitive computing ^[1] and green computing ^[2] to deal with such challenging issues like, energy optimization, carbon emission, resource utilization intelligently. In particular, CGC aims at providing efficient mechanisms for the tasks such as maximizing the efficiency of use of computing resources ^[3]. Evolutionary algorithm (EA) ^[4] is a well-known global search algorithm, which has been successfully used to solve various complex optimization problems. EA heuristically explores the decision space by maintaining a population which might contain hundreds of chromosomes. Thus, a run of population-based EA often requires huge memory consumption, which limited their applications in the memory-limited hardware, e.g., mobile systems, industrial robots, etc. To overcome this drawback, in this work, we propose a Compact EA (CEA) ^[5] for the sake of CGC, and use it to address the ternary compound ontology matching problem. CEA uses a Probability Array (PA) to represent a population and execute the evolutionary operations, which is able to reduce the algorithm's memory consumption and searching performance.

Ontology is a cutting-edge knowledge modeling technique, which has been widely used to model various domain knowledge. It is impractical to develop and maintain a top-level ontology that is able to meet all the requirements of different applications, and thus, various domain ontologies are developed independently for different purposes ^[6]. Although they own significant overlapped information, a concept could be described with different granularity, yielding the ontology heterogeneity problem. For instance, describing a patient's record may include using SNOMED-CT for clinical methods employed, LOINC for laboratory analyses and results, ICD-10 for diagnoses and ATC for coding any prescribed antibiotics. Matching ontologies is able to determine semantically identical concepts among heterogenous ontologies, which is a feasible approach to integrate the knowledge in different ontologies. Traditionally, matching ontologies is the procedure that takes input two ontologies, and returns the concept mappings between two ontologies. However, if multiple ontologies are necessary to accurately describe the information and knowledge, to allow their communications, there is a need to establish links among multiple ontologies. This need motivates a new type of complex ontology matching, i.e., compound ontology matching ^[7], which involves more than two ontologies. A common case of the compound matching is the ternary compound matching, where two concepts from two distinct ontologies are mapped with a concept from the third ontology. For instance, the concept "broad forehead" in the human phenotype ontology (HP) is equivalent to the union of the concept "increased width" in phenotypic quality ontology (PATO) and the concept "forehead" in the foundation model of anatomy (FMA) ontology, i.e., "broad forehead" $\equiv$ "increased width" $\cap$ "forehead".

Since 2018, ontology alignment evaluation initiative (OAEI)^* has presented the complex track that evaluates the matching techniques which generate complex correspondences. But there is still no testing case on the compound ontology matching problem, and currently, there are only two compound ontology matching techniques that are proposed by Pesquita and Oliveira ^[7,8]. The former first determines the anchors, i.e., highly similar concept pairs, in two ontologies, and then match them to the third ontology. On the basis of the first work, Oliveira et al. further makes use of agreement maker light (AML) to built for the word matcher, and a weighted Jaccard index to aggregate the similarity values, whose computational complexity is large. Moreover, the completeness and accuracy of the determined compound ontology alignments are not high. Being inspired by the success of EA in the ontology matching domain ^{[9,10,11,12,13]}, this work proposes to make use of EA to address the ternary compound ontology matching problem. However, population-based EA suffers from significant computational complexity, which hampers their application in the real matching tasks. To maximize the utilization of computer hardware and improve the algorithm's efficiency, this work first construct an optimal model for the ternary compound ontology matching problem, and then presents a concept similarity measure to calculate the confidence of a ternary compound correspondence, finally, a CEA with compact encoding and evolving mechanism is proposed to efficiently address this problem.

^* http://oaei.ontologymatching.org/

The rest of the paper is organized as follows: section 2 defines the ternary compound ontology matching problem and the concept similarity measure; section 4 describes the problem-specific CEA in details; section 5 shows the experimental results; and finally, section 6 draws the conclusion.

2.   Ternary compound ontology matching problem

There are many definitions on the Ontology, and in this work, for the convenience, an ontology is defined as a 5-tuple $(C, DP, OP, I, \lambda)$, where $C$ is the concept set, $DP$ and $OP$ are respectively the sets of inner property and outer property, $I$ is the set of instance, and $\lambda$ is the set of axiom ^[14,15]. In particular, an inner property (or datatype property) describes a concept's individual feature, while an outer property (or object property) describes its relationships with other concepts. A ternary correspondence is also a 3-tuple $(c_1, c_2, c_3, \equiv, sim)$, where $c_1$, $c_2$ and $c_3$ are respectively the concepts of the first, second and third ontologies, $\equiv$ is the relationship of equivalence, i.e., $c_1 \equiv c_2 \cap c_3$, and $sim$ is the confidence or similarity value of this correspondence. The ternary compound matching process takes as input three ontologies and an external background knowledge base (e.g., unified medical language system (UMLS) ^[16]), and outputs a set of ternary compound correspondences, i.e., the ternary compound ontology alignment.

The traditional evaluation metrics work on the basis of the reference alignment provided by the expert. However, the reference alignment is not always available especially when the entity scale is huge. To overcome this drawback, we propose an approximate metric, which is based on the observation that the more ternary compound alignment correspondences found, the higher probability that it contains more correct correspondences, i.e., the alignment's completeness would be higher; and similarly, the higher mean similarity value of all the correspondences in an alignment, the higher probability that it contains less incorrect correspondences, i.e., the alignment's accuracy would be higher ^[17]. In particular, the approximate metric for evaluating a ternary compound ontology alignment's quality is defined as follows:

where $|A|$, $|C_j|$ are respectively the cardinalities of the alignment $A$ and the $j$th ontology's concept set, $sim_i$ is the confidence value of the $i$th correspondence. Here, $\frac{|A|}{\max \{|C_1|, |C_2|, |C_3|\}}$ measures how many ternary compound alignment correspondences are found, $\frac{\sum_{i = 1}^{|A|} sim_i}{|A|}$ calculates the average similarity measure, and function $f()$ takes both of them into consideration.

On this basis, the mathematical model of ternary compound ontology matching problem can be defined as follows:

where $|C_j|$ is the cardinality of the $j$th ontology's concept set, and $X_i, i = 1, 2, \cdots, |C_1|$ represents the $i$th correspondence. In particular, $x^i_1 = 0$ (or $x^i_2 = 0$) means the $i$th concept in the first ontology is mapped to none in the second (or third) ontology.

3.   Concept similarity measure

Concept similarity measure (CSM) is a function measuring to what extent the concepts in a correspondence are similar, and its effectiveness directly affects the alignment's quality ^[18]. Essentially, CSM used in this work borrows the idea from Oliveira et al. ^[7], but we more focus on the concept's lexical and linguistic features, which are the most commonly used information in the ontology matching domain ^[19]. Given three concepts $c_1$, $c_2$ and $c_3$, and their labels as $label_1$, $label_2$ and $label_3$, we first pre-process these labels by: (1) remove their numbers, punctuations and stop-words; (2) split the labels into words and convert them into lower-case; (3) lemmatizing and stemming the English words. Then, we get the corresponding word set $W_1$, $W_2$ and $W_3$, which are used to calculate $c_1$, $c_2$ and $c_3$'s similarity value in two sequential steps. First, we calculate the similarity of $c_1$, $c_2$ as follows:

where $j = 1, 2, \cdots, |W_2|$. Here, for each word in $W_1$, say $w_{1, i}$, we find its most similar word in $W_2$, say $w_{2, j}$, and calculate their similarity value $sim'(w_{1, i}, w_{2, j})$. After that, we sum all the similarity values with respect to the words in $W_1$, and divide it by the cardinality of $W_1$ to obtain two concepts' similarity value. In particular, $sim'()$ is defined as follows:

where UMLS is first used to determine whether two words $w_1$ and $w_2$ are synonymous terms, and if not, $sim_N()$ will be used to calculate the lexical similarity with N-gram distance ^[20]. If $sim(c_1, c_2) < 0.4$, similarity value among $c_1$, $c_2$ and $c_3$ is set as 0; otherwise, we reduce $W_1$ by removing all the words that have already been matched with $W_2$ to get $W_1'$. After that, $c_1$, $c_2$ and $c_3$'s similarity value is determined by the $sim(W_1', W_3)$. In particular, the threshold for $sim(W_1', W_3)$ is set as 0.8, which is referred to the configurations in Oliveira et al. ^[7].

4.   Compact evolutionary algorithm

This work presents a problem-specific CEA, and use it to solve the ternary compound ontology matching problem. CEA uses the binary encoding mechanism, i.e., Gray code, to encode the ternary compound correspondences in a solution. Supposing $|C_1|$, $|C_2|$ and $|C_3|$ are respectively the number of concepts in three ontologies, the length of a chromosome is $\log{|C_{src}|} \times (\log{|C_{tgt1}|}+\log{|C_{tgt2}|})$. The $i$-th gene bit consists of two parts of information, one for the index of the first target concept and the other for the second. When decoding, the $i$-th source concept is mapped with these two target concepts.

A PA is used to represent a population and execute the evolving process. In particular, the length of a PA is equal to that of a chromosome, where each element inside is the probability of being one with respect to the corresponding gene bit. Here is an example of generating a new solution through PA $(0.3, 0.7, 0.6, 0.9)^T$. First, generate four random numbers, such as 0.4, 0.5, 0.8 and 0.1. Then compare the numbers with the elements in PA accordingly to determine the new generated individual's gene values, e.g., since $0.4 > 0.3$, the first gene bit's value of the new solution is 0, and similarly, the remaining gene bits' values are 1, 0 and 1, respectively. In this way, the new solution we obtain is 0101. By repeating this procedure, we can obtain various individuals. In each generation, PA is updated to move towards the best solution found so far, which is implemented by increasing the elements' values in PA when the best solution's corresponding element's value is 1, and decreasing the values when 0. Given the $step = 0.1$, if the gene value of the elite is 1 (or 0), the corresponding element of PA will increase (or decrease) by $st$, and the updated PA is $(0.2, 0.8, 0.5, 1.0)^T$. When PA's elements are all approach 1 or 0, CEA converges, and thus, the step length affects the algorithm's searching performance. When the step length is large, the algorithm will converge quicker but tends to get stuck in the local optima; and when it is too small, the algorithm's learning ability is lower, which makes it converges slower. This work set the step length is $\sqrt{n} \log{n}$ by referring to Sudholt et al. ^[21]. Given the length of a chromosome (or PA) $len$, the step length for updating PA $st$ and the maximum generation for CEA $maxGen$, the pseudo-code of CEA is shown in Algorithm 1.

5.   Experiment

5.1.   Experimental configuration

To test the performance of CEA, we use six testing cases that consists of nine ontologies, which are suggested by Oliveira et al. ^[7]. Table 1 shows a brief descriptions on these ontologies. We denote a testing case with the pattern "source ontology-the first target ontology-the second target ontology", e.g., "MP-CL-PATO".

The alignment's quality are evaluated with the traditional recall, precision and f-measure ^[31], which are defined as follows:

where $|A|$ and $|RA|$ are respectively the cardinalities of the alignment $A$ and reference alignment $RA$. In particular, recall and precision respectively measure the coverage of correct correspondences by referring to $RA$ and $A$, and f-measure is their harmonic mean value. The experiment is carried out with an Intel Core i9-8950HK CPU @ 2.90GHz x 12 and 25GB allocated RAM.

5.2.   Comparison on alignment's quality and matching efficiency

First, we compare CEA with EA based matching technique ^[32], Memetic algorithm (MA) based matching technique ^[33], Differential Evolution Algorithm (DE) based matching technique ^[34], whose configurations are referred to their literatures. Table 2 shows their mean f-measure and standard deviation of the alignments obtained by EA based matching techniques, and Table 3 presents the T-Test statistical analysis ^[35] of the values in Table 2. The results of all the meta-heuristics based matching techniques are the mean value of 30 independent runs.

In our experiment, a level of significance $\alpha = 0.05$ is chosen. Data analysis of Tables 2 and 3 depicts that CEA statistically outperforms other meta-heuristics based matching techniques on f-measure at 5% significance level. In addition, CEA does not need to tune any parameters except for the maximum generation 3000, which makes it more stable than other meta-heuristics based matching techniques.

Tables 4 compares CEA with two state-of-the-art ternary compound ontology matching techniques, i.e., AML based matching techniques with top-one ranked selector and top-two ranked selector ^[7], in terms of recall, precision and f-measure. As shown in Table 4, CEA's recall outperforms the other two competitors in all testing cases, which show that the compact evolving mechanism is able to effectively search in large searching space. Next, CEA's precision values also rank the first in all matching tasks, which show the proposed similarity measure's effectiveness. Finally, the f-measure of CEA based matching technique show that it is able to effectively optimize the alignment's quality.

From Table 5, we can see that, in all testing cases, CEA dramatically improves EA's memory consumption and runtime per generation. Specifically, the highest improvement degree is on average by 82.95% and 80.93%, respectively. These gains are due to that CEA introduces the compact encoding mechanism, which is able to significantly save the memory consumption, and the simplified evolving mechanism, which is able to improve the algorithm's runtime per generation. To conclude, CEA is able to improve the quality of ternary compound ontology alignment, and significantly reduce the memory consumption and runtime per generation.

6.   Conclusions

For the sake of the cognitive green computing, this work proposes a CEA to efficiently address the ternary compound ontology matching problem, which is able to bridge the sematic gap among three heterogeneous ontologies. In particular, we use the compact encoding and evolving mechanisms to reduce the algorithm's memory consumption and runtime when searching for the global optima. We construct an optimal model for the problem, and present a concept similarity measure to calculate a ternary compound correspondence's similarity value. The experimental results show that CEA-based matching technique is able to efficiently determine ternary compound ontology alignments.

When facing a very large-scale matching task, e.g., an ontology owns tens of thousands of concepts, a pre-screening method should be introduced. In the future, we will be interested in partitioning the ontologies into several semantic segments, which is of help to reduce the search space of CEA. In addition, a parallel matching mechanism would be of help to further improve the matching efficiency.

Acknowledgments

This work is supported by the National Key Research and Development Program of China (No. 11974373) and Natural Science Foundation of Fujian Province (No. 2020J01875).

Conflict of interest

All authors declare no conflicts of interest in this paper.