On direct debugging of aligned ontologies?

Abstract

Modern ontology debugging methods allow efficient identification and localization of faulty axioms defined by a user while developing an ontology. However, in many use cases such as ontology alignment the ontologies might include many conflict sets, i.e. sets of axioms preserving the faults, thus making the ontology diagnosis infeasible. In this paper we present a debugging approach based on a direct computation of diagnoses that omits calculation of conflict sets. The proposed algorithm is able to identify diagnoses for an ontology which includes a large number of faults and for which application of standard diagnosis methods fails. The evaluation results show that the approach is practicable and is able to identify a fault in adequate time.

Motivation and algorithm details

interactive ontology diagnosis algorithm can be described as follows: (1) Generate a set of diagnoses D including at most n diagnoses. (2) Compute a set of queries and select the best one using a predefined measure. (3) Ask the oracle and, depending on the answer, add the query either to P or to N . (4) Update the set of diagnoses D and remove the ones that do not comply with the newly acquired test case. (5) Update the tree and repeat from Step 1 if the tree contains open nodes. (6) Return the set of diagnoses D. The resulting set D includes only diagnoses that are not differentiable in terms of their entailments, but have some syntactical differences. The preferred target diagnosis Dt, in this case, should be selected by the user using some ontology editor such as Prote´ge´.

Most of the debugging approaches, including [ 4 ], follow the standard model-based diagnosis approach [ 3 ] and compute diagnoses using conflict sets CS, i.e. irreducible sets of axioms ax i 2 O that preserve violation of at least one requirement. The computation of one conflict set can be done within a polynomial number of calls to the reasoner, e.g. by QUICKXPLAIN algorithm [ 2 ]. To identify a diagnosis of cardinality jDj = m the hitting set algorithm suggested in [ 3 ] requires computation of m conflict sets. In some practical scenarios, such ontology matching, the number of conflict sets m can be large, thus making the ontology debugging practically infeasible.

In this paper we present two algorithms INV-HS-TREE and INV-QUICKXPLAIN, which inverse the standard model-based approach to ontology debugging and compute diagnoses directly, rather than by means of conflict sets (see [ 5 ] for a detailed description of the algorithms). The main function of the latter algorithm splits recursively the initial diagnosis problem instance into two sub-problems by partitioning the axioms of a given faulty ontology into two subsets. In many cases SPLIT simply partitions the set of axioms into two sets of equal cardinality. The algorithm continues to divide diagnosis problems until it identifies a set D0 such that O n D0 fulfills all the requirements, but O n Di0, where Di0 are partitions of D0, not. In further iterations the algorithm minimizes the D0 by splitting it into sub-problems of the form D0 = D [ O , where O contains only one axiom. In the case when D0 is a diagnosis and D is not, the algorithm decides that O is a subset of the sought diagnosis. Just as the original algorithm, INVQUICKXPLAIN always terminates and returns either a diagnosis D or “no diagnosis”.

In order to enumerate all possible diagnoses we modified the HS-TREE algorithm [ 3 ] to accept diagnoses as node labels instead of conflict sets. The INV-HS-TREE algorithm constructs a directed tree from root to the leaves, where each node nd is labeled either with a diagnosis D(nd) or X (closed) or (pruned). The latter two labels indicate that the node cannot be extended. Each edge outgoing from the open node nd is labeled with an element s 2 D(nd). HS(nd) is a set of edge labels on the path from the root to the node nd. Initially the algorithm creates an empty root node and adds it to the queue, thus, implementing a breadth-first search strategy. Until the queue is empty, the algorithm retrieves the first node nd from the queue and labels it with either: 1. if there is a node nd0, labeled with either X or , such that H(nd0) H(nd) (pruning non-minimal paths), or 2. D(nd0) if a node nd0 exists such that its label D(nd0) \ H(nd) = ; (reuse), or 3. D if D is a diagnosis for the diagnosis problem instance hO; B [ H(nd); P; N i computed by INV-QUICKXPLAIN (compute), or 4. X (closed).

The leaf nodes of a complete tree are either pruned ( ) or closed (X) nodes.

In the diagnosis discrimination settings the ontology debugger acquires new knowledge that can invalidate some of the diagnoses labeling the tree nodes. During the tree update INV-HS-TREE searches for the nodes with invalid labels, removes its label and places it to the list of open nodes. Moreover, the algorithm removes all the nodes of a subtree originating from this node. After all nodes with invalid labels are cleanedup, the algorithm attempts to reconstruct the tree by reusing the remaining valid minimal diagnoses (rule 2, INV-HS-TREE). Such aggressive pruning of the tree is feasible since a) the tree never contains more than n nodes that were computed with INVQUICKXPLAIN and b) computation of a possible modification to the minimal diagnosis, that can restore its validness, requires invocation of INV-QUICKXPLAIN and, therefore, as hard as computation of a new diagnosis. Note also, that in a common diagnosis discrimination setting n is often set to a small number, e.g. 10, in order to achieve good responsiveness of the system. In the direct approach this setting limits the number of calls to INV-QUICKXPLAIN to n and results in a small size of the search tree. The latter is another advantage of the direct method as it requires much less memory in comparison to a debugger based on original HS-TREE. 2

Evaluation

We evaluated the direct ontology debugging technique using aligned ontologies generated in the framework of OAEI 2011 [ 1 ]. These ontologies represent a real-world scenario in which a user generated ontology alignments by means of (semi-)automatic tools. All ontologies used in the experiments are available online, together with detailed evaluation results1.

In the first experiment we applied the debugging technique to the set of aligned ontologies resulting from “Conference” set of problems, which is characterized by lower precision and recall of the applied systems (the best F-measure 0.65) in comparison, for instance, to the “Anatomy” problem (average F-measure 0.8). The Conference test suite includes 286 ontology alignments generated by 14 ontology matching systems including: a) 140 ontologies are consistent and coherent; b) 122 ontologies are incoherent; c) 26 ontologies are inconsistent; and in 8 cases a reasoner was unable to classify in two hours2. Note that only two systems CODI and MaasMtch out of 14 were able to generate consistent and coherent alignments. This observation confirms the importance of high-performance ontology debugging methods.

The 146 ontologies of the cases b) and c) were analyzed with both HS-TREE and INV-HS-TREE. The results of the experiment show that for 133 ontologies out of 146 both approaches were able to compute the required amount of diagnoses. HT-TREE required 49, 61 and 80 sec. on average to find 1, 9 and 30 leading minimal diagnoses. The direct algorithm required less time and returned the requested number of diagnoses on average in 27, 52 and 72 sec. respectively. In the 13 cases HS-TREE was unable to find all requested diagnoses in each experiment. Within 2 hours the algorithm calculated only 1 diagnosis for csa-conference-ekaw and for ldoa-conference-confof it was able to find 1 and 9 diagnoses, whereas INV-HS-TREE required 9 sec. for 1, 40 sec. for 9 and 107 sec. for 30 diagnoses on average.

Moreover, in the first experiment we evaluated the efficiency of the interactive direct debugging approach applied to the cases listed in Table 1. We selected the target diagnosis randomly among all diagnoses of the following diagnosis problem instance hMf ; Oi [ Oj [ Mt; ;; ;i, where Mf and Mt are the sets of false and true positive 1 http://code.google.com/p/rmbd/wiki/DirectDiagnosis 2 Core-i7 (3930K) 3.2Ghz, 32GB RAM running Ubuntu 11.04, Java 6 and HetmiT 1.3.6. alignments computed from the set of correct alignments Mc, provided by the organizers of OAEI 2011, and the set Mij generated by a ontology matching system. In the experiment the used the Entropy scoring function [ 4 ] with prior fault probabilities of axioms corresponding to aliments set to 1 v, where v is the confidence value of the matcher for an axiom. All axioms of Oi and Oj were assumed to be correct and were assigned small probabilities. The results presented in Table 1 were computed for the diagnosis problem instance hMij ; Oi [ Oj ; ;; ;i. The experiment shows that the system was able to identify the target diagnosis efficiently with small reaction times. The system’s performance decreased only in the cases when a reasoner required much time to verify the consistency of an ontology.

In the second scenario we applied the direct method to unsatisfiable and classifiable within 2 hours ontologies, generated for the Anatomy problem. The source ontologies O1 and O2 include 11545 and 4838 axioms correspondingly, whereas the size of the alignments varies between 1147 and 1461 axioms. The target diagnosis selection process was performed in the same way as in the first experiment. The results of the experiment show that the target diagnosis can be computed within 40 second in an average case. Moreover, INV-HS-TREE slightly outperformed HS-TREE.

References

1. Euzenat , J. , Ferrara , A., van Hage , W.R. , Hollink , L. , Meilicke , C. , Nikolov , A. , Ritze , D. , Scharffe , F. , Shvaiko , P. , Stuckenschmidt , H. , Sva´b- Zamazal , O. , dos Santos , C.T.: Final results of the Ontology Alignment Evaluation Initiative 2011 . In: Proceedings of the 6th International Workshop on Ontology Matching . pp. 1 - 29 . CEUR-WS.org ( 2011 )

2. Junker , U. : QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems . In: Proc. 19th National Conference on Artificial Intelligence . pp. 167 - 172 ( 2004 )

3. Reiter , R.: A Theory of Diagnosis from First Principles. Artificial Intelligence 32 ( 1 ), 57 - 95 ( 1987 )

4. Shchekotykhin , K. , Friedrich , G. , Fleiss , P. , Rodler , P. : Interactive ontology debugging : two query strategies for efficient fault localization . Web Semantics: Science, Services and Agents on the World Wide Web 12-13 , 88 - 103 ( 2012 )

5. Shchekotykhin , K. , Friedrich , G. , Fleiss , P. , Rodler , P. : Direct computation of diagnoses for ontology debugging . arXiv 1- 16 ( 2012 ) http://arxiv.org/abs/1209.0997