In this report, we present the results of Optima+ in the Ontology Alignment Evaluation Initiative (OAEI) 2012. We mainly foucused on three tracks Benchmark, Conference, and Anatomy. However we were eavluated in all the tracks of the campaign offered in SEALS platform: Benchmark, Conference, Anatomy, Multifarm, Library, and LargeBioMed. We present the new and improved implementation of the Optima algorithm, Optima+ and its results for all the tracks offered within SEALS platform. Optima+ is the latest version of Optima , aimed to perform faster and better. Importantly, we match the highest f-measure (0.65) obtained for the conference track in last year's campaign. Moreover, this year we debut in large ontology tracks: Anatomy and Library aided by a naive divide and conquer approach.
1.1 The ontology alignment problem is to find a set of correspondences between two ontologies O1 and O2. Because ontologies may be modeled as labeled graphs (though with some possible loss of information), the problem is often cast as a matching problem between such graphs. An ontology graph, O, is defined as, O = hV, E, Li, where V is the set of labeled vertices representing the entities, E is the set of edges representing the relations, which is a set of ordered 2-subsets of V , and L is a mapping from each edge to its label. Let M be the standard |V1| × |V2| matrix that represents the match between the two graphs O∞ = hV1, E1, L1i, O∈ = hV2, E2, L2i:
M =
Where f (·) represents the correspondence between the two ontology graphs.
Consequently, M is a binary matrix representing the match.
Optima formulates the problem of inferring a match between two ontologies as a
maximum likelihood problem, and solves it using the technique of expectation-maximization
(EM) originally developed by Dempster et al. [
1 X|V1| P r(yα|xa, M i−1) |V1| a=1 The generalized maximization step involves finding a match matrix, M∗i, that improves on the previous one:
M∗i = M i ∈ M : Q(M i|M∗i−1) ≥ Q(M∗i−1|M∗i−1)
(3)
1.3
Optima+ is a new and improved redesign of Optima to achieve a better alignment,
yet in significantly less time. It adopts the block coordinate descent (BCD) technique
for iterative ontology alignment proposed by us [
The generalized maximization step now involves finding a match matrix block, MSi c,∗, that improves on the previous one:
MSi c,∗ = MSi c ∈ MSc : QS (MSi c,∗|M∗i−1) ≥ QS (MSi −c,1∗|M∗i−1) (5) Here, MSi −c,1∗ is a part of M∗i−1. At iteration i, the best alignment matrix, M∗i, is formed by combining the block matrix, MSi c,∗, which improves the QS function as defined in Eq. 5 with the remaining from the previous iteration, MSi˜−c,1∗, unchanged.
An important heuristic, which has proven highly successful in ontology alignment,
matches parent entities in two ontologies if their respective child entities were
previously matched. This motivates grouping together those variables, maα in M , into a
coordinate block such that the xa participating in the correspondence belong to the
same height leading to a partition of M . The height of an ontology node is the length of
the shortest path from a leaf node. Let the partition of M into the coordinate blocks be
{MS0 , MS1 , . . . , MSC }, where C is the height of the ontology O1. Thus, each block is
a submatrix with as many rows as the number of entities of O1 at a height and number
of columns equal to the number of all entities in O2. For example, the correspondences
between the leaf entities of O1 and all entities of O2 will form the block, MS0 .
Similarity measures Similarity has become a classical tool for ontology matching.
Similarity measure between ontological concepts such as classes and properties, is
commonly a measure in the range of [
SimLex(Label-C1, Label-C2), Sim(C1, C2) = M ax SimLex(N ame-C1, N ame-C2), Cos(Comment-C1, Comment-C2) (6)
Where Label-C1,N ame-C1, and Comment-C1, are the label, name and comment of the concept C1. As shown in Eq. 7 below the lexical similarity between the phrases P1 and P2 is,
LinSim(P1, P2), CosSim(P1, P2), SimLex(P1, P2) = M ax SW Sim(P1, P2), N W Sim(P1, P2), LevSim(P 1, P 2) (7)
Here, LinSim is the popular similarity measure introduced by Lin [
Alignment Extraction Alignment extraction is the process of pruning a set of correspondences in an alignment to achieve a minimal and consistent alignment. A minimal alignment is achieved by removing the correspondences which can be inferred by an existing correspondence. A consistent alignment is achieved by resolving conflicting correspondences. Optima+ adopts a simple heuristic based alignment extraction process, which is described below, – For each class-correspondence (N1, N2) in the alignment, any correspondence among the children of N1 and children of N2 is removed. – For each class-correspondence (N1, N2) in the alignment, any correspondence which maps children of N1 to parent of N2 or children of N2 to parent of N1 is removed if its similarity is less than the similarity of N1 and N2. – If a concept is mapped to more than one concept then, we select the correspondence with highest similarity (M axSim) and remove all other correspondences which are less than a predefined threshold T1. We also remove all other correspondences with similarity less than the M axSim − δ. Here δ is a user configurable value in the range of [0, 0.5].
Large Ontology Matching The time complexity of Optima to align Ontology O1 of
size |O1| and O2 of size |O2| is (|O1| × |O2|)2 [
State, purpose, general statement Optima+ is a general purpose ontology alignment tool capable of matching English language ontologies described in OWL, RDFS/RDF, and N3. 1.5
Specific techniques used As described earlier, Optima+ employs a variety of similarity measures, a simple alignment extraction and large ontology matching using a naive divide and conquer approach. 1.6
Adaptations made for the evaluation We made couple of changes to the alignment extraction process for this campaign. First, we filtered the correspondences between imported concepts even though they have been directly used within the ontologies. Second, we implemented the heuristics mentioned in the sub-section 1.3 to make the alignment minimal. The default alignment extraction of optima is not as strict as the one configured for this campaign. 1.7
Link to the system and parameters file A detail presentation of the system, its configuration and parameters used for this campaign and results can be found at http://thinc.cs.uga.edu/thinclabwiki/ index.php/OAEI_2012. 2
Optima+ is evaluated in all the six tracks under SEALS platform in OAEI 2012 though, we only focused in benchmark, conference and anatomy tracks. For this report the results for all these tracks are summarized except for large biomedical track. Optima+ could not successfully finish aligning the large biomedical track due to a fatal error. Detailed results for individual tracks and test cases can be found at http://thinc. cs.uga.edu/thinclabwiki/index.php/OAEI_2012. 2.1
benchmark
The Benchmark test library consists of 5 different test suites [
conference
For this track, Optima+ achieves recall of 0.68 and precision of 0.62. Both the recall
and the precision are improved compared to the performance of Optima in OAEI 2011.
Overall there is 81% increase in F-Measure compared to OAEI 2011. This makes
Optima+ , to tie the top performer in OAEI 2011[
The performance improvement in conference track arises from the improved similarity measure and the alignment extraction (Section 1.3). Optima+ also utilizes improved design and optimization techniques to reduce the runtime. The runtimes reported in the Table 2 cannot be compared directly as the underlying systems used for evaluations differ. However, the runtime improvement from 15+ hours to around 23 minutes is perspicuous.
Year Precision (H-mean) Recall (H-mean) F-Measure (H-mean) Total Runtime 2011 0.26 0.60 0.36 15hrs 2012 0.62 0.68 0.65 1349sec Since Optima+ focus only on English language ontologies, it gives low performance in this track as expected. However it is interesting to notice that Optima+ yields an average recall of 1.0 with an average precision of 0.01.
Library is another large ontology matching track in OAEI 2012. Optima+ attains a precision of 0.321 and a recall of 0.072 in 37,457 seconds. 3
Last year Optima debuted the OAEI campaign with promising results. However it took too long to finalize the alignment process. This year we redesigned the Optima algorithm to complete the alignment process faster and were able to speed it from minutes to seconds. Additionally, we implemented a naive divide and conquer approach to tackle the large ontology matching problem.
Optima+ matches the last year’s best f-measure (0.65) in conference track, and gives 0.87 f-measure on average for benchmark track excluding the scrambled labeled test cases. However, as revealed in benchmark track Optima+ heavily relies on lexical features of ontologies to align them. In large ontology tracks (anatomy and library) Optima+ struggles to perform well as it performed in other tracks (conference and benchmark). We suppose that a dedicated alignment extraction is needed to merge the results of blocks in large ontology matching process.
We are aiming to improve our f-measure for large ontology matching by improving the entire large ontology matching process. Specifically, we would like to introduce an exclusive alignment extraction process for large ontology matching. Further, we want to find an optimum partition strategy for BCD technique which yields better alignment yet faster. On top of these, extending the current similarity measure calculation with more useful similarity measures and lexical databases would help Optima+ to improve its fmeasure. Though there is an inherent means to align instances using Optima algorithm, Optima+ implementation is not yet fully capable of matching instances. In its next versions, we expect it to be able to match instances as well.
In this report we present the results of Optima+ in OAEI 2012 campaign in six tracks including Benchmark, Conference, Anatomy, Multifarm, Library, and LargeBioMed. We also present the new and redesigned implementation of Optima , Optima+ . Optima+ shows impressive performance in benchmark track, but struggles to align ontologies with scrambled labels. However, it matches the top f-measure of last year’s conference track. It debuted in large ontology tracks (anatomy and library) with promising results. In future we want to participate in more tracks, especially instance matching tracks. More importantly, we wish to leverage our performance in large ontology tracks to attain a higher f-measure.