Giuseppe Pirró
email: giuseppe.pirro@inrialpes.fr

Jérôme Euzenat
email: jerome.euzenat@inrialpes.fr

A Feature and Information Theoretic Framework for Semantic Similarity and Relatedness

Keywords: Semantic Similarity, Feature Based Similarity, Ontologies

Semantic similarity and relatedness measures between ontology concepts are useful in many research areas. While similarity only considers subsumption relations to assess how two objects are alike, relatedness takes into account a broader range of relations (e.g., part-of). In this paper, we present a framework, which maps the feature-based model of similarity into the information theoretic domain. A new way of computing IC values directly from an ontology structure is also introduced. This new model, called Extended Information Content (eIC ) takes into account the whole set of semantic relations defined in an ontology. The proposed framework enables to rewrite existing similarity measures that can be augmented to compute semantic relatedness. Upon this framework, a new measure called FaITH (Feature and Information THeoretic) has been devised. Extensive experimental evaluations confirmed the suitability of the framework.

Introduction

Semantic similarity and relatedness investigates how alike two or more objects are, and plays an important role in many contexts. Generally speaking, similarity allows to infer knowledge and categorize objects into kinds. This is important when either it is not possible to exactly state what properties are salient for an object, or when it is not easy to separate an object into distinct properties [START_REF] Son | The Transfer of Scientific Principles using Concrete and Idealized Simulation[END_REF][START_REF] Watanable | Knowing and Guessing: A Quantitative Study of Inference and Information[END_REF]. Semantic similarity has a long tradition in psychology and cognitive science where different models have been postulated. Among these, the geometric model enables to asses similarity between entities by considering them as points in a dimensionally organized metric space. The feature-based model, leverages features (i.e., characteristics) of the examined objects and assumes that similarity is a function of both common and distinctive features [START_REF] Tversky | Features of Similarity[END_REF]. Recently, findings in information theory have been considered in computing similarity [START_REF] Resnik | Information Content to Evaluate Semantic Similarity in a Taxonomy[END_REF]. From a computer science perspective, similarity measures exploit some source of knowledge such as search engines [START_REF] Danushka | Measuring Semantic Similarity Between Words using Web Search Engines[END_REF] or ontologies such as WordNet [START_REF] Miller | WordNet an on-line Lexical Database[END_REF]. More recently, similarity measures have been defined in Description Logics (DLs) [START_REF] Borgida | Towards Measuring Similarity in Description Logics In Proc. of Description Logics[END_REF][START_REF] D ' Amato | Similarity-based Learning Methods for the Semantic Web[END_REF]. In [START_REF] D ' Amato | Similarity-based Learning Methods for the Semantic Web[END_REF] several similarity measures are described, which take into account ontology instances for assessing the similarity between two concepts. While similarity only considers subsumption relations to assess how two objects are alike, relatedness takes into account a broader range of relations (e.g., part-of). The work presented in this paper focuses on computing similarity and relatedness by exploiting the terminological definition of ontology concepts. We leave the investigation about how this method can be applied to DLs as a future work.

Computing semantic similarity between ontology concepts is an important issue since having many applications in different contexts including: Information Retrieval, to improve the performance of current search engines [START_REF] Hliaoutakis | Information Retrieval by Semantic Similarity[END_REF], ontology matching, to discover correspondences between entities belonging to different ontologies [START_REF] Pirró | SECCO: On Building Semantic Links in Peer to Peer Networks[END_REF], semantic query routing, to choose among the set of possible peers only those relevant, bioinformatics to assess the similarity between proteins [START_REF] Wang | A New Method to Measure the Semantic Similarity of GO Terms[END_REF] just to cite a few. This paper presents a semantic similarity framework, which is based on two main pillars. One is the projection of the feature-based model of similarity into the information theoretical domain. The reason to combine these two models is twofold. On one hand, the feature-based model has a solid theoretical underpinning supported by several psychological studies [START_REF] Tversky | Features of Similarity[END_REF] and is more flexible than other theoretical models (e.g., geometric). On the other hand, the information-theoretic formulation of similarity allows to compare concept features not by simply counting object properties but taking into account the informativeness of the concepts being compared. The second pillar, is a new way to obtain IC values called Extended Information content (eIC ). eIC considers the whole set of semantic relations defined in an ontology and assigns a score of informativeness to each concept without referring to external corpora as usually done by traditional IC-based approaches where time expensive and corpus-dependent occurrence count has to be performed.

The generality of this framework enables to rewrite several existing similarity measures that can be augmented to compute semantic relatedness. This aspect has been investigated and resulted in an improvement of existing similarity measures as will be discussed in Section 4. Finally, a new measure called FaITH (Feature and Information Theoretic) has been designed, which is a versatile tool to compute both similarity and relatedness. Extensive experimental evaluation of similarity and relatedness show the suitability of the proposed framework and FaITH in particular.

The remainder of this paper is organized as follows. Section 2 provides some background and surveys on popular measures. Section 3 presents the new similarity framework and the logical path toward its definition; here the FaITH measure and the eIC are discussed. Section 4 presents an extensive evaluation campaign. Section 5 concludes the paper.

Definitions and Background

We consider an ontology O as a graph, where nodes represent concepts and edges represent relations between concepts. If we consider the hierarchical structure of the ontology, each concept can have a set of sub-concepts (its descendants) in the hierarchy. However, an ontology usually includes a broader set of semantic relation such as part-of. Figure 1 reports an excerpt of an ontology. Hereafter we will consider WordNet as reference ontology even if the same reasoning applies to any other ontology. In WordNet, the definition of a concept consists of its immediate superordinate(s) followed by a relative clause that describes how this concept differs from all others. For example Fortified Wine is distinguished from Wine because "... alcohol (usually grape brandy)" has been added just as the gloss accompanying its definition mentions. An object feature (a concept in our case) can be seen as a property of the object. According to the definition above, concepts in the hierarchy inherit all the features of their superordinate even if they can have their own specific features. As an example, since car and bicycle both serve to transport people or objects, in other words they are both types of vehicles, they share all features pertaining to the concept vehicle. However, each concept has also its specific features as steering wheel for car and pedal for bicycle. Moreover, even if specialization relations constitute the majority in WordNet, there are other kinds of relations accompanying each definition that are useful to identify object features. For instance, car has a relation of type part-of with engine whereas bicycle has a part-of relation with sprocket. The use immediate concept features can be seen as a special case of semantic neighbourhood with radius equals to 1.

Similarity or relatedness measures, by looking at the ontology structure or by exploiting some additional information, address the problem of assessing (typically in terms of a numerical score) how alike two concepts are. As an example of similarity and relatedness, car and bicycle are similar whereas car and wheel are related. The choice to focus either on similarity or relatedness depends on the particular application context, even though many approaches to compute relatedness are extensions of similarity measures [START_REF] Hirst | Lexical Chains as Representations of Context for the Detection and Correction of Malapropisms In[END_REF][START_REF] Rodriguez | Determining Semantic Similarity among Entity Classes from Different Ontologies[END_REF]. The framework presented in this paper can be adopted to compute both similarity and relatedness.

State of the art

Similarity measures can be divided into different and not necessarily disjoint categories. In this work we consider information-theoretic approaches, ontologybased approaches and hybrid approaches. Information Theoretic Approaches. Information theoretic approaches employ the notion of Information Content (IC), which quantifies the informativeness of concepts. Early IC approaches [START_REF] Resnik | Information Content to Evaluate Semantic Similarity in a Taxonomy[END_REF][START_REF] Jiang | Semantic Similarity based on Corpus Statistics and Lexical Taxonomy[END_REF][START_REF] Lin | An Information-theoretic Definition of Similarity[END_REF] obtained IC values by associating probabilities to each concept in an ontology on the basis of its occurrences in large text corpora. In the specific case of hierarchical ontologies, these probabilities are cumulative as we travel up from specific concepts to more abstract ones. This means that every occurrence of a concept in a given corpus is also counted as an occurrence of each concept containing it. IC values are obtained by computing the negative likelihood of encountering a concept in a given corpus. Note that this method ensures that IC is monotonically decreasing as we move from the leaves of the taxonomy to its roots.

Resnik [START_REF] Resnik | Information Content to Evaluate Semantic Similarity in a Taxonomy[END_REF] was the first to leverage IC for the purpose of semantic similarity. The basic intuition behind the use of the negative likelihood is that the more probable a concept is of appearing in a corpus the less information it conveys, in other words, infrequent words are more informative than frequent ones. Once IC values are available for each concept in the considered ontology, semantic similarity can be calculated. Resnik's formula to compute similarity states that similarity depends on the amount of information two concepts c 1 and c 2 share, which is given by the Most Specific Common Abstraction (msca(c 1 , c 2 )), that is, the concept that subsumes the two concepts being compared.

Starting from Resnik's work, Jiang and Conrath [START_REF] Jiang | Semantic Similarity based on Corpus Statistics and Lexical Taxonomy[END_REF] and the Lin [START_REF] Lin | An Information-theoretic Definition of Similarity[END_REF] proposed two measures, which calculate IC-values in the same manner as proposed by Resnik while correcting some problems with this similarity measure; if one were to calculate sim res (c 1 , c 1 ) one would not obtain the maximal similarity value of 1, but instead the value given by IC(c 1 ). Besides, with Resnik's approach any two pairs of concepts having the same msca have exactly the same semantic similarity; for instance, in the WordNet ontology, sim res (Horse, P lant) = sim res (Animal, P lant) because in each case the msca(Horse, P lant) and msca(Animal, P lant) is Living Thing. However, in this case the semantic leap is not the same.

The Lin measure considers the ratio between the amount of information needed to state the commonality between two concepts and the information needed to describe them as discussed in [START_REF] Lin | An Information-theoretic Definition of Similarity[END_REF]. Ontology based approaches. As for ontology based approaches, the work by Rada et al. [START_REF] Rada | Development and Application of a measure on Semantic Nets[END_REF] is similar to the Resnik measure since it also computes the msca(c 1 , c 2 ), but instead of considering the IC as the value of similarity, it considers the number of links that were needed to attain the msca(c 1 , c 2 ). Obviously, the less the number of links separating the concepts the more similar they are. The work by Hirst et al., which actually measures relatedness, is similar to the previous one but it uses a wider set of relations coupled with rules restricting the way concepts are transversed [START_REF] Hirst | Lexical Chains as Representations of Context for the Detection and Correction of Malapropisms In[END_REF]. Nonetheless, the intuition also in this case is that the number of links separating two concepts is inversely proportional to the degree of similarity.

Hybrid approaches. Hybrid approaches usually combine multiple information sources. Li et al. [START_REF] Li | An Approach for Measuring Semantic Similarity between Words Using Multiple Information Sources[END_REF] proposed to combine structural semantic information in a nonlinear model. The authors empirically defined a similarity measure that uses shortest path length, depth and local density in a taxonomy and combine them.

In [START_REF] Schickel-Zuber | OSS: A Semantic Similarity Function based on Hierarchical Ontologies[END_REF] the OSS distance function, combining a-priori scores of concepts with distance, is proposed. OSS performs the following steps to assess similarity between two concepts c 1 and c 2 : (i) computing the score of the concept c 2 from the concept c 1 ; (ii) computing how much score has been transferred between the concepts; (iii) transforming the transfer of score into a distance measure.

Our previous work [START_REF] Pirró | A Semantic Similarity Metric Combining Features and Intrinsic Information Content[END_REF], defined a similarity measure combining features and information content that adopts Tversky's contrast model. This measure treats similarity between identical concepts as a special case and can give as output negative values, which make difficult the interpretation of results. The differences with the present work are: i) this paper describes a general framework, which can be used to rewrite even existing similarity measures; ii) here a new similarity measure is proposed, which adopts a different representation of the feature-based model; iii) in this paper a new way to compute IC values is proposed, which enables to compute both semantic similarity and relatedness; iv) an extensive evaluation of relatedness is proposed for FaITH and several other measures.

Comparison among measures

Each measure has its limitations. IC-based measures making use of corpora, though having a strong mathematical formalization, may sometimes fail to capture certain aspects of language. For instance, it is possible that corpus such as the British National Corpus, may not even mention certain words. Besides, values of IC are obtained through time intensive analysis of corpora and can heavily depend on the considered corpora (as discussed in Section 4). Ontologybased approaches require to work with consistent ontologies, that is, ontologies where distance between specific and more general concepts have the same interpretation. As an example it is obvious that the semantic leap between Entity and Psychological Feature is higher than that between Canine and Dog even if both couples are separated by one edge. Finally, hybrid approaches require the different information sources to be correctly "weighted". A common limitation of the considered approaches is that they can only compute either similarity or relatedness. The proposed framework, and in particular FaITH, are more flexible as the notion of Extended Information Content (eIC ) can be exploited to compute both similarity and relatedness without depending on external corpora.

A Framework for Semantic Similarity and Relatedness

This section presents a new framework for computing semantic similarity and relatedness. After providing some preliminary definitions, the Tversky's formulation of similarity, which is based on a representation of concepts according to their features, is introduced. This will serve as a basis to motivate the present framework. In more detail, the proposed framework adopts a ratio-based formulation of the Tversky's model of similarity and projects it into the informationtheoretic domain. Section 3.4 describes the Extended Information Content (eIC ), which can be used to compute relatedness between concepts. Note that the generality of this framework enables to rewrite several existing similarity measures, which can be augmented to compute relatedness.

Tversky's feature-based model of similarity

Amos Tversky, in his seminal work, proposed an alternative way to compute similarity by taking into account both common and distinguish "features "of the objects being compared. As an example of Tversky's formulation, car and bicycle both serve to transport people or objects (in other words they are both types of vehicles), then they share all features that pertain to the concept vehicle. However, each concept has also its specific features such as steering wheel for car or pedal for bicycle. Moreover, if we look beyond the hierarchical structure of their definitions we can find different kinds of relations with other concepts such as engine part-of car and sprocket part-of bicycle. The set of all relations can be exploited to further characterize concept features. Fig. 2 depicts an example of such reasoning. Early semantic similarity models, such as the geometric model, Fig. 2. An example of concept features required to respect metric properties such as the triangle inequality or symmetry. Tversky's discussed several examples to support the idea that certain axioms, required by the geometric model, were not necessary in the process of similarity estimation. For instance, since Germany is judged to be more like Austria than Austria is to Germany [START_REF] Tversky | Features of Similarity[END_REF] the symmetry property could not be respected in this case. According to the feature-based model, the similarity of a concept c 1 to a concept c 2 is a function of the features common to c 1 and c 2 , those in c 1 but not in c 2 and those in c 2 but not in c 1 . If we admit a function Ψ (c) that yields the set of features relevant to c, Tversky's similarity model can be represented by the following equation, also known as contrast model :

sim tvr (c 1 , c 2 ) = αF(Ψ (c 1 ) ∩ Ψ (c 2 )) -βF(Ψ (c 1 ) \ Ψ (c 2 )) -γF(Ψ (c 2 ) \ Ψ (c 1 )) . (1)
where F is some function that reflects the salience of a set of features, and α, β and γ are parameters that provide for differences in focus on the different components. According to this model, features in common increase similarity whereas features that are unique to the two objects decrease similarity. However, note that the above formulation is not framed in information theoretic terms since it is based on sets of concept features.

A Ratio-based formulation of Tverky's similarity model

The difficulty with the contrast model described in equation [START_REF] Agirre | A Study on Similarity and Relatedness Using Distributional and WordNet-based Approaches[END_REF] and discussed in our previous study [START_REF] Pirró | A Semantic Similarity Metric Combining Features and Intrinsic Information Content[END_REF] is that the more unique features a concept presents the lower the similarity. Moreover similarity values are not bounded between 0 and 1, which can make interpretation of results difficult. To overcome these issues, therefore, a ratio model is more appropriate since it is bounded between 0 and 1, irrespective of the size of the features being compared. Thus a more useful definition of feature-based similarity is:

simtvr-ratio(c1, c2) = F(Ψ (c1) ∩ Ψ (c2)) βF(Ψ (c1) \ Ψ (c2)) + γF(Ψ (c2) \ Ψ (c1)) + F(Ψ (c1) ∩ Ψ (c2))
.

(

) 2
Note that α = 1 in the ratio model and then common features are maximally important in process of similarity estimation. At this point there are two main tasks we can perform:

1. Assess the degree to which concept c 1 and c 2 are similar to each other. In this case β = γ since the similarity is not intended to be directional. 2. Assess the degree to which concept c 2 is similar to concept c 1 . In this second task, similarity is directional and we are more interested in the features in c 1 than we are in the features unique to c 2 . Here, β and γ do not need to be equal. This latter case is useful in many application contexts such as Information Retrieval (IR)or clustering where starting from a concept we are interested in finding what it is similar to.

Table 1 analyzes different scenarios obtained by manipulating the coefficients β and γ in equation [START_REF] Borgida | Towards Measuring Similarity in Description Logics In Proc. of Description Logics[END_REF]. For the purpose of this paper, we consider β = γ since we want to compute the similarity not directionally. Moreover, for the definition of the ratio based model described in equation (2) α = 1, which maximizes the contribution of common features. We leave as future work the investigation of other values for these parameters in more targeted applications such as IR.

The FaITH similarity measure

This section describes the FaITH measure for semantic similarity and relatedness. The cornerstone of this measure is the msca(c 1 , c 2 ), which reflects the information shared by two concepts c 1 and c 2 in an ontology structure. In the information-theoretic domain, Resnik exploited the msca(c 1 , c 2 ) to assess the similarity between concepts. IC values are obtained by exploiting equation (3):

IC(c) = -log p(c) . (3)
Table 1. Possible scenarios obtained by manipulating equation [START_REF] Borgida | Towards Measuring Similarity in Description Logics In Proc. of Description Logics[END_REF].

Case

Coefficients Description Commonalities between c1 and c2

β = γ = 0
If there exists any commonality then sim tvr (c1, c2) = 1 Given c1 assess to which degree c2 is similar to it

β = 1, γ = 0 When the full set of features of c1 are contained in c2 then sim tvr (c1, c2) = αF(Ψ (c 1 )∩Ψ (c 2 )) βF(Ψ (c 1 )\Ψ (c 2 ))+αF(Ψ (c 1 )∩Ψ (c 2 )) β = 0, γ = 1 When the set of features of c1 contains the features of c2 then simtvr r (c1, c2) = αF(Ψ (c 1 )∩Ψ (c 2 )) γF(Ψ (c 2 )\Ψ (c 1 ))+αF(Ψ (c 1 )∩Ψ (c 2 ))
Given c1 and c2 assess to which degree they are similar to each other

β=γ = 1
Tversky's similarity is represented in terms of Tanimoto index. β=γ = 0.5 Tversky's similarity is represented in terms of Dice index.

where c is a concept and p(c) is the probability of encountering c in a given corpus. Note that this method ensures that IC is monotonically decreasing as we move from the leaves of the taxonomy to its roots. In Fig. 2, the msca(car, bicycle) is wheeled vehicle and these two concepts share all the features belonging to their msca. In a feature-based formulation of similarity, the msca(c 1 , c 2 ) can be seen as the intersection of features from c 1 and c 2 . Therefore, one can speculate that the function F, that reflects the saliency of features, can be substituted by the function IC in the information theoretic domain (this new IC is referred to as IC features ). Starting from this assumption, by looking at Fig. 2, it is immediate to infer that the set of features specific to car (resp. bicycle) is given by IC features (car) -IC features (wheeled vehicle) (resp. IC features (bicycle)-IC features (wheeled vehicle)). These three analogies, generalized in Table 2, are the building blocks of the proposed framework.

Table 2. Mapping between feature-based and information theoretic similarity models.

Description

Feature-based model Information-theoretic model Common features

Ψ (c1) ∩ Ψ (c2) IC(msca(c1, c2)) Features of c1 alone Ψ (c1) \ Ψ (c2) IC(c1) -IC(msca(c1, c2)) Features of c2 alone Ψ (c2) \ Ψ (c1) IC(c2) -IC(msca(c1, c2))
Moreover, as it will be discussed in Section 3.4, the way we compute the IC values for each concept (i.e., eIC ) can take into account the different features of an object defined both in terms of the hierarchical structure and other kinds of semantic relations. By substituting the analogies from Table 2 in equation ( 2) the similarity measure called FaITH, reported in equation ( 4), is obtained.

sim F aIT H (c 1 , c 2 ) = IC(msca(c 1 , c 2 )) β(IC(c 1 ) -IC(msca(c 1 , c 2 ))) + γ(IC(c 2 ) -IC(msca(c 1 , c 2 ))) + IC(msca(c 1 , c 2

))

.

As we are concerned to compute how two concepts c 1 and c 2 are similar to each other we set the values of β and γ to 1 (see Table 1) thus obtaining:

simFaITH(c1, c2) = IC(msca(c1, c2)) IC(c1) + IC(c2) -IC(msca(c1, c2)) . ( 5
)
Note that in the case of ontologies with multiple inheritance, the msca(c 1 , c 2 ) may be unique. In this case, FaITH considers the most informative msca (i.e., the msca with the highest information content).

Extended information Content (eIC)

The proposed framework combines the feature and the information theoretic models of similarity. One of the main difficulty with this model is that IC values have to be derived by analyzing large corpora, which may not even contain certain specific words. In order to overcome this issue, the intrinsic IC formulation proposed in [START_REF] Seco | An Intrinsic Information Content measure for Semantic Similarity in WordNet[END_REF] is adopted. The intrinsic IC (iIC ) for a concept c is defined as:

iIC(c) = 1 - log(sub(c) + 1) log(max con ) . ( 6
)
where the function sub returns the number of subconcepts of a given concept c. Note that concepts representing leaves in the taxonomy will have an IC of one, since they do not have hyponyms. The value of one states that a concept is maximally expressed and is not further differentiated. Moreover max con is a constant that indicates the total number of concepts in the considered taxonomy. However, since an ontology usually contains relations beyond inheritance also useful to assess to what extent two concepts are alike, the Extended Information Content (eIC ) is introduced. eIC by investigating each kind of ontological relation between concepts provides a better indicator about the features of concepts and then can be used to compute relatedness. For instance, by only focusing on isa relations, in the example in Fig. 2 we would lose some important information (e.g., that car has part-of engine or that bicycle has as part-of sprocket ) that can help to further characterize commonalities and differences between two concepts. For each concept, the coefficient EIC is defined as follows:

EIC(c) = m j=1 n k=1 iIC(c k ∈ C Rj )) |C Rj | . (7)
This formula takes into account all the m kinds of relations that connect a given concept c with other concepts. Moreover, for all the concepts at the other end of a particular relation (i.e., each c k ∈ C Rj ) the average iIC is computed. This enables to take into account the expressiveness of concepts to which a given concept is related in terms of their information content. The final value of Extended Information Content (eIC ) is computed by weighting the contribution of the iIC and EIC coefficients thus leading to:

eIC(c) = ζiIC(c) + ηEIC(c) . (8)
The two parameters ζ and η can be settled in order to give more or less emphasis to the hierarchical IC of the two concepts. At this point, we can rewrite equation ( 5) thus obtaining:

simFaITH(c1, c2) = eIC(msca(c1, c2)) eIC(c1) + eIC(c2) -eIC(msca(c1, c2)) . (9)
This similarity measure corrects some drawbacks of existing approaches. First, it exploits features of concepts, expressed in terms of IC, and not only their position in the ontology structure. Second, it corrects the problem with Resnik's measure, in fact, sim F aIT H (c 1 , c 1 ) = 1. Finally, by taking into account relations beyond inheritance, FaITH allows to compute semantic relatedness.

Evaluation

This section discusses the evaluation of the FaITH similarity measure and its comparison w.r.t. the state of the art. In the first experiment we evaluated FaITH as a semantic similarity measure while in the second experiment we evaluated FaITH as a semantic relatedness measure as using the eIC formulation. Finally, in order to have an insight of how FaITH works with more domain-related ontologies, we performed an evaluation using couples of concepts taken from the MeSH biomedical ontology. In each experiment, we evaluated the performance of the different methods in two settings. The first one (denoted as F + eIC) by exploiting the proposed framework along with the eIC while the second one using the classical approach to compute IC without mapping features in the IC domain. In particular, the SemCor (S ) Brown (B ) and BNC (Bnc) text corpora, of increasing size, have been used to obtain IC values. For the Li measure we adopted the same optimal parameter values as indicated by authors in [START_REF] Li | An Approach for Measuring Semantic Similarity between Words Using Multiple Information Sources[END_REF].

In order to have an idea of the improvement using the F + eIC formulation we computed for each measure and corpus the loss (L) in performance, which represents how much the performance of a given measure decrease when using the classical IC formulation. Besides, for each evaluation, as statistical test of significance, we computed the p-value. The analyzed similarity measures have been implemented in the Java WordNet Similarity Library available upon request, along with the datasets, at http://grid.deid.unical.it/similarity.

Experiment 1: evaluating FaITH on similarity

In the first experiment, we evaluate the FaITH measure on a dataset collected by an online similarity experiment described in our previous work [START_REF] Pirró | A Semantic Similarity Metric Combining Features and Intrinsic Information Content[END_REF]. The dataset contains similarity judgments for 65 word pairs [START_REF] Rubenstein | Contextual Correlates of Synonymy[END_REF] (referred to as S R&G ) which are commonly used, along with a subset of 28 word pairs [START_REF] Miller | Contextual Correlates of Semantic Similarity[END_REF] (referred to as S M&C ), to measure accuracy of similarity measures. The word pairs in the dataset have been originally chosen to range from very similar (e.g., carautomobile) to semantically unrelated (e.g., chord-smile) as discussed in [START_REF] Rubenstein | Contextual Correlates of Synonymy[END_REF]. Figure 3 3. The first column indicates the correlation by using the IC formulation introduced in Section 3.4. Each other column considers the correlation according one corpus and the loss as compared to the result in the first column. The second column, for instance, indicates that by using the SemCor(S) corpus, the correlation of the Resnik measure is 0.71, with a loss of 16.4 % . For the Length measure, lower values correspond to higher similarity values. For instance, the two word pairs (i.e., gem-jewel and automobile-car ) have a length equal to zero since belonging to the same WordNet synset respectively and then are maximally similar according to the WordNet's design principle. On the other hand, examples of unrelated words are the couples rooster-voyage and chord-smile having a path length of 30. The Depth measure obtained a value of correlation of about 30% better than the Path measure. This measure assesses similarity by considering the depth of the msca(c 1 , c 2 ). Edge counting approaches reach the lowest correlation w.r.t. human ratings in both datasets. That is because these approaches work well only when the values computed have a "consistent interpretation", that is, when the length of the path (resp. depth of the msca(c 1 , c 2 )) between two general concepts and that between two specific ones express the same semantic leap, which is not the case of WordNet.

As for IC-based approaches, Resnik's measures obtained the lowest value of correlation. However, the usage of the IC(msca(c 1 , c 2 )) brings better results in terms of correlation as compared to path-based measures. The other two ICbased measures (i.e., Lin and J&C) obtained better results since considering the IC of the two concepts as well. As for hybrid approaches, the Li measure, which combines the depth of the msca(c 1 , c 2 ) and the length of the path between two concepts, obtained a higher value of correlation. However, note that this measure to correctly weights the contributions of the different information sources requires the tuning of two coefficients as described in [START_REF] Li | An Approach for Measuring Semantic Similarity between Words Using Multiple Information Sources[END_REF]. The P&S measure, described in [START_REF] Pirró | A Semantic Similarity Metric Combining Features and Intrinsic Information Content[END_REF], obtained a remarkable value of correlation in both S R&G and S M&C . However, the P&S formulation treats the computation of similarity between identical concepts as a special case as discussed in [START_REF] Pirró | A Semantic Similarity Metric Combining Features and Intrinsic Information Content[END_REF]. Moreover, in some cases, sim P &S(c1,c2) < 0, which makes the interpretation of results difficult.

Moreover, this measure is not as flexible as FaITH, which can be adopted to different contexts as discussed in Section 3.2. The FaiTH measure obtained the best value of correlation in both S R&G and S M&C . Note that in all cases the F + eIC formulation brings better results. The loss L can reach the 20% and 15% with the Lin measure in S R&G and S M&C respectively. Moreover, using classical approaches the performance heavily depend on the adopted corpus even if it can be noted that larger corpora bring better results. The p-values in both evaluations are pvalue < 0.001, which indicate that the results are significant. Finally, one note about the couple car-journey. The two words, even if generally related since a car can be the means to do a journey, are not similar. This is because similarity, which is a special case of relatedness, only considers the relations of hypernymy/hyponymy (i.e., isa). The FaITH measure assigned a similarity score of 0.007 to this couple while the J&C, Resnik, Lin and P&S assigned 0.346, 0.009, 0.013 and 0.233 respectively. In this case, the FaITH measure since giving the lowest value of similarity seems to better comply with the definition of similarity. In summary, our intuition to exploit a ratio-based representation of Tversky's similarity model and project it into the information theoretic domain is consistent.

Experiment 2: evaluating FaITH on relatedness

In this experiment, FaITH has been evaluated as a semantic relatedness measure by using the eIC formulation. For the evaluation, the WordSim353 dataset, which is a test collection for measuring word relatedness often used in the literature has been adopted. Further detail on the dataset are available in [START_REF] Agirre | A Study on Similarity and Relatedness Using Distributional and WordNet-based Approaches[END_REF]. Even in this case, for each measure, the Pearson correlation coefficient w.r.t. human ratings of similarity has been computed. In this evaluation we compare FaITH with more relatedness measures. In particular, we also considered the Leacock & Chodorow (referred to as Lch) [START_REF] Leacock | Combining Local Context and WordNet Similarity for Word Sense Identification[END_REF] and the Wu & Palmer (referred to as Wup) [START_REF] Wu | Verb semantics and Lexical Selection[END_REF] measures. We also used a measure of relatedness between two words (referred to as Ovp), which assesses the overlap score between two concepts by augmenting glosses with glosses of related concepts [START_REF] Banerjee | Extended Gloss Overlaps as a Measure of Semantic Relatedness[END_REF]. The optimal values for the parameters ζ and η, experimental determined, are 0.4 and 0.6 respectively. While similarity measures perform extremely well on small similarity datasets such as the M&C and R&G discussed in Section 4.1, their performance drastically decrease when applied to a larger dataset such as WordSim353. The values of correlation reported in Table 4 are related to the word pairs contained in WordNet. Note that for the Lch, W up and Ovp measures the results are the same as they are not based on IC.

As can be observed, FaITH performs clearly better than the other measures, which substantiate our intuition of adopting the F + eIC strategy. Besides, all the similarity measures perform worse when not using F + eIC. The loss (L) in performance is reported in Table 4. In particular, all the IC-based measures take advantage of this formulation, with the Resnik measure improving of about 11%. In the case of not adopting the F + eIC, correlation values heavily depend on the considered corpus. Overall, FaITH and the eIC formulation represent a promising technique to compute similarity and relatedness between words and help to augment and improve existing similarity measures.

Experiment 3: evaluation on the MeSH ontology

The MeSH Medical Subject Headings (MeSH) ontology is mainly a hierarchy of medical and biological terms. It consists of a controlled vocabulary and a Tree. The controlled vocabulary contains several different types of terms such as Descriptors, Qualifiers, Publication Types, Geographics and Entry terms. Entry terms are the synonyms or the related terms to descriptors. MeSH descriptors are organized in a tree, which defines the MeSH Concept Hierarchy. In the MeSH tree there are 15 categories each of which is further divided into subcategories. For each subcategory, its descriptors are arranged in a hierarchy from most general to most specific. This evaluation investigates how FaITH performs with domain related ontologies. Similarly to the first evaluation, a dataset of human similarity judgments has been exploited (refer to [START_REF] Hliaoutakis | Semantic Similarity Measures in MeSH Ontology and their Application to Information Retrieval on Medline[END_REF] for further details). Results obtained by computational methods are compared with those provided by humans in Table 6 whereas, Table 5 reports values of correlations. The P&S measure, which on WordNet similarity was the closest to FaITH, obtained even in this case a lower value of correlation. Note that the Li measure, which on WordNet obtained a remarkable value of correlation, obtained the lowest correlation on MeSH. We hypothesize that this can be due to two reasons. First, the Li measure depends on two parameters to correctly balance the contribution of the path between c 1 and c 2 to be compared and the depth of their msca(c 1 , c 2 ). Hence, it is possible that parameter values that achieved a good correlation in WordNet do not obtain the same (comparable) performance in MeSH. The second reason is related to the structure of the considered ontology. MeSH is a more domain-specific ontology than WordNet and therefore, in MeSH the combination of path and depth in a non linear function as suggested by the Li measure could not have the same consistent interpretation as in WordNet. The three information content measures obtained better correlation, with Resnik's measure showing a slightly higher level of correlation. This trend is in contrast with the results obtained by the same measure on WordNet where it obtained the lowest correlation both on the M &C and R&G datasets. This fact can be justified assuming the in MeSH the msca(c 1 , c 2 ) better expresses the amount of information shared by two terms. Finally, even on this dataset the FaITH measure obtained the highest correlation. In this case the value of correlation is lower than that obtained on WordNet. Results are significant due to the very low value of p-value (i.e., pvalue < 0.001).

Concluding Remarks and Future Work

This paper described a new model of similarity combining features [START_REF] Tversky | Features of Similarity[END_REF] and information-content [START_REF] Resnik | Information Content to Evaluate Semantic Similarity in a Taxonomy[END_REF]. In particular, by exploiting a ratio-based formulation of the feature model a family of similarity measures as reported in Table 2 has been defined. One on these measures, called FaITH, to quantify how two ontology concepts are similar to each other, has been presented. Another contribution of this paper is the definition of Extended Information Content (eIC ) that enables to compute relatedness between concepts by taking into account relations beyond subsumption. The proposed framework enabled to rewrite existing ICbased measures with significant improvement in their performance.

There are at least two interesting strands for future research. One is how to extend the framework to Description Logics (DLs). The main aspect that should be addressed is how to express Extended Information Content values for concepts defined in DLs. Moreover, investigating how similarity depends on the expressiveness of the considered DL is another interesting concern.

The second aspect we want to address is how this strategy, and in particular FaITH, works in more targeted applications such as document clustering, information retrieval and query answering across ontologies.

Fig. 1 .

 1 Fig. 1. An excerpt of ontology

Fig. 3 .

 3 Fig. 3. Results for similarity measures and human ratings

  reports the ratings of similarity provided by both human participants and computational methods. Values of correlation (ρ) for the different measures

		1	FaITH (Features and IC)
			P&S (Features and IC)
			Li (Multisource)
		0.8	Resnik (IC-based) Lin (IC-based)
			J&C (IC-based)
	Similarity value	0.4 0.6	Human
		0.2
		0
			gem-jewel midday-noon automobile-car cemetery-graveyard cushion-pillow boy-lad cock-rooster implement-tool forest-woodland coast-shore autograph-signature journey-voyage serf-slave grin-smile glass-tumbler cord-string hill-mound magician-wizard furnace-stove asylum-madhouse brother-monk food-fruit bird-cock bird-crane oracle-sage sage-wizard brother-lad crane-implement magician-oracle glass-jewel cemetery-mound car-journey hill-woodland crane-rooster furnace-implement coast-hill bird-woodland shore-voyage cemetery-woodland food-rooster forest-graveyard lad-wizard mound-shore automobile-cushion boy-sage monk-oracle shore-woodland grin-lad coast-forest asylum-cemetery monk-slave cushion-jewel boy-rooster glass-magician graveyard-madhouse asylum-monk asylum-fruit grin-implement mound-stove automobile-wizard autograph-shore fruit-furnace noon-string rooster-voyage cord-smile

Table 3 .

 3 Correlation values with F + eIC (ρ) and different corpora

			Correlation on S M &C		Correlation on S R&G
		ρ ρS/L(%) ρB/L(%) ρBnc/L(%) ρ ρS/L(%) ρB/L(%) ρBnc/L(%)
	Lenght 0.61	0.61	0.61	0.61	0.58	0.58	0.58	0.58
	Depth 0.84	0.84	0.84	0.84	0.80	0.80	0.80	0.80
	Li	0.91	0.91	0.91	0.91	0.90	0.90	0.90	0.90
	Resnik 0.85 0.71/16.4 0.73/14.5 0.75/11.8 0.87 0.83/5.1 0.84/4.1	0.85/2.4
	Lin 0.87 0.69/20.2 0.74/15.0 0.75/14.2 0.89 0.75/15.0 0.79/10.9 0.80/9.8
	J&C 0.88 0.72/17.8 0.80/9.3	0.81/8.1 0.87 0.82/6.3 0.83/5.4	0.84/4.0
	P &S 0.91 0.86/4.7 0.87/4.2	0.89/2.3 0.90 0.87/3.7 0.88/3.0 0.89/1.8
	F aIT H 0.92 0.87/5.5 0.88/4.6 0.90/2.4 0.91 0.88/3.3 0.88/2.9 0.90/1.0

Table 4 .

 4 Evaluation on relatedness

	Measure ρ	ρS/L% ρB/L% ρBnc/L%
	Lch	0.36	0.36	0.36	0.36
	W up	0.32	0.32	0.32	0.32
	Ovp	0.21	0.21	0.21	0.21
	Resnik 0.40 0.36/11.1 0.36/9.9 0.38/5.4
	Lin	0.404 0.37/7.9 0.378/6.4 0.38/5.7
	J&C	0.40 0.38/4.0 0.38/2.8 0.39/1.8
	P &S	0.41 0.38/5.4 0.38/5.1 0.39/4.7
	F aIT H 0.43 0.40/7.0 0.40/6.3 0.40/5.8

Table 5 .

 5 Correlation with F + iIC

	Measure ρ
	Resnik 0.72
	Lin	0.71
	J&C	0.71
	Li	0.70
	P &S	0.72
	FaITH 0.74

Table 6 .

 6 Evaluation on MeSH

	Word 1	Word 2	Human Resnik [19] Lin [12] J&C [9] Li [11] P&S [17] FaITH
	Antibiotics	Antibacterial Agents	0.93	1.00	1.00	1.00	0.99	1.00	1.00
	Measles	Rubeola	0.91	0.92	1.01	1.00	0.99	1.03	1.00
	Chicken Pox	Varicella	0.97	1.00	1.00	1.00	0.99	1.00	1.00
	Down Syndrome	Trisomy 21	0.87	1.00	1.00	1.00	0.99	1.00	1.00
	Seizures	Convulsions	0.84	0.88	1.04	0.90	0.81	1.10	0.99
	Pain	Ache	0.87	0.86	1.00	1.00	0.99	1.00	0.95
	Malnutrition	Nutritional Deficiency	0.87	0.62	1.00	1.00	0.98	1.00	0.87
	Myocardial Ischemia	Myocardial Infarction	0.75	0.59	0.92	0.89	0.80	0.85	0.83
	Hepatitis B	Hepatitis C	0.56	0.65	0.82	0.86	0.66	0.70	0.79
	Pulmonary Valve Stenosis Aortic Valve Stenosis	0.53	0.65	0.78	0.81	0.66	0.64	0.76
	Psychology	Cognitive Science	0.59	0.68	0.77	0.81	0.80	0.63	0.75
	Asthma	Pneumonia	0.37	0.51	0.79	0.87	0.52	0.66	0.75
	Diabetic Nephropathy	Diabetes Mellitus	0.50	0.61	0.76	0.79	0.77	0.61	0.74
	Hypothyroidism -	Hyperthyroidism	0.41	0.62	0.73	0.75	0.63	0.57	0.72
	Sickle Cell Anemia	Iron Deficiency Anemia	0.44	0.60	0.72	0.79	0.36	0.56	0.71
	Carcinoma	Neoplasm	0.75	0.25	0.68	0.85	0.45	0.46	0.65
	Urinary Tract Infection	Pyelonephritis	0.65	0.47	0.58	0.67	0.42	0.42	0.60
	Hyperlipidemia	Hyperkalemia	0.15	0.33	0.48	0.47	0.51	0.32	0.56
	Lactose Intolerance	Irritable Bowel Syndrome	0.47	0.47	0.47	0.40	0.30	0.30	0.47
	Adenovirus	Rotavirus	0.44	0.27	0.33	0.45	0.35	0.20	0.40
	Vaccines	Immunity	0.59	0.00	0.00	0.52	0.00	0.00	0.34
	Migraine	Headache	0.72	0.23	0.24	0.37	0.17	0.14	0.80
	Bacterial Pneumonia	Malaria	0.15	0.00	0.00	0.20	0.13	0.00	0.22
	AIDS	Congenital Heart Defects	0.06	0.00	0.00	0.27	0.10	0.00	0.18
	Sarcoidosis	Tuberculosis	0.40	0.00	0.00	0.25	0.07	0.00	0.17
	Anemia	Appendicitis	0.03	0.00	0.00	0.19	0.13	0.00	0.13
	Meningitis	Tricuspid Atresia	0.03	0.00	0.00	0.19	0.13	0.00	0.13
	Failure to Thrive	Malnutrition	0.62	0.00	0.00	0.18	0.13	0.00	0.12
	Sinusitis	Mental Retardation	0.03	0.00	0.00	0.36	0.13	0.00	0.11
	Hypertension	Kidney Failure	0.50	0.00	0.00	0.21	0.13	0.00	0.11
	Breast Feeding	Lactation	0.84	0.00	0.00	0.04	0.08	0.00	0.03
	Dementia	Atopic Dermatitis	0.06	0.00	0.00	0.16	0.10	0.00	0.00
	Osteoporosis	Patent Ductus Arteriosus	0.15	0.00	0.00	0.03	0.10	0.00	0.00
	Amino Acid Sequence -	AntiBacterial Agents	0.15	0.00	0.00	0.15	0.00	0.00	0.00
	Otitis Media	Infantile Colic	0.15	0.00	0.00	0.07	0.08	0.00	0.00
	Neonatal Jaundice	Sepsis	0.19	0.00	0.00	0.19	0.16	0.00	0.00


Cássia Trojahn
email: cassia.trojahn@inrialpes.fr

Jérôme Euzenat
email: jerome.euzenat@inrialpes.fr

Consistency-driven Argumentation for Alignment Agreement

Ontology alignment agreement aims at overcoming the problem that arises when different parties need to conciliate their conflicting views on ontology alignments. Argumentation has been applied as a way for supporting the creation and exchange of arguments, followed by the reasoning on their acceptability. Here we use arguments as positions that support or reject correspondences. Applying only argumentation to select correspondences may lead to alignments which relates ontologies in an inconsistent way. In order to address this problem, we define maximal consistent sub-consolidations which generate consistent and argumentation-grounded alignments. We propose a strategy for computing them involving both argumentation and logical inconsistency detection. It removes correspondences that introduce inconsistencies into the resulting alignment and allows for maintaining the consistency within an argumentation system. We present experiments comparing the different approaches. The (partial) experiments suggest that applying consistency checking and argumentation independently significantly improves results, while using them together does not bring so much. The features of consistency checking and argumentation leading to this result are analysed.

Introduction

Due to the diverse ways of exploring the ontology matching problem, matching systems generally differ in the alignments generated between two ontologies. Some approaches may be better suited for some ontologies, or some tasks, than others. Ontology alignment agreement aims at overcoming the problem of allowing different parties to conciliate their conflicting points of view on alignments. There may be different ways to perform alignment agreement, such as voting or weighting. In this paper, we consider argumentation which offers a more reasoned way to decide which correspondences to preserve.

Argumentation theory has been exploited as a way to support the comparison and selection of correspondences within an alignment process. Correspondences are represented as arguments and argumentation frameworks support the reasoning on their acceptability. This approach has been used in different scenarios. [START_REF] Laera | Argumentation over ontology correspondences in mas[END_REF] propose an approach for supporting the creation and exchange of different arguments, that support or reject correspondences in the context of agent communication. In [START_REF] Trojahn | A cooperative approach for composite ontology mapping[END_REF], different matchers work on the basis of particular approaches achieving distinct results that are compared and agreed via an argumentation process.

An open issue in alignment agreement is related to the inconsistency in the agreed alignment. Indeed, some selected sets of correspondences may relate the ontology in an inconsistent way. Most matching systems do not consider logic-based semantics in their algorithms. As a result, almost all matching systems produce incoherent alignments [START_REF] Meilicke | An efficient method for computing alignment diagnoses[END_REF]. Although argumentation aims at resolving conflicts on the alignments generated by these systems, this process does not guarantee that the agreed alignment is consistent even if the initial alignments were consistent.

In this paper, we propose a model that involves both argumentation and logical inconsistency detection. We focus on the scenario where matchers working on the basis of different matching approaches try to reach a consensus on their alignments. First, matchers generate their correspondences, representing them as arguments. Next, they exchange their arguments and interpret them under argumentation frameworks based on their individual preferences. The arguments in every individual set of acceptable arguments are considered as an agreed alignment. Then, the inconsistent correspondences in such sets are removed, in order to generate a maximal consistent agreed alignment. This allows for maintaining the consistency within an argumentation system. We evaluate our proposal on a standard set of alignments. Though theoretically grounded, the consistency step does not improve argumentation alone. For some test cases, the argumentation process is incidentally able to provide consistent agreed alignments. We describe the features of consistency checking and argumentation which cause this result.

The rest of the paper is organised as follows. First, we introduce alignments and inconsistency of alignments ( §2). We then present the argumentation approach for alignment agreement ( §3). Next, the consistency-driven argumentation protocol is presented ( §4) and its evaluation is discussed ( §5). Finally, we discuss related work ( §6) and conclude the paper ( §7).

Alignments and Inconsistency

An alignment (A) is a set of correspondences from a pair of ontologies (o and o ′ ). Each correspondence is a quadruple: e, e ′ , r, n , where e ∈ o, e ′ ∈ o ′ , r is the relation between e and e ′ , taken from set of alignment relations (e.g., ≡, ⊑, ⊒ or ⊥), and n ∈ [0 1] is a confidence level (e.g., measure of confidence in the fact that the correspondence holds). For instance, given the two ontologies of Figure 1, one can consider the following correspondences, meaning that (1) the two classes Person in both ontologies are the same, and that (2) DepartmentHead in the first ontology is subsumed by Department in the second ontology.

Person o , Person o ′ , ≡, 1.0 (1) DepartmentHead o , Department o ′ , ⊑, 0.8 (2)
The semantics of alignments provides a definition of how alignments must be interpreted. It is related to the semantics of the aligned ontologies, which is given by their sets of models M(o) and M(o ′ ). The main effect of alignments is to select compatible pairs of models of the two related ontologies [START_REF] Euzenat | Ontology matching[END_REF]. We rely here on a basic semantics in which models are directly compatible. It considers that a correspondence is satisfied by a pair of models if the interpretation of the entities by these models satisfy the relation of the correspondence. For instance, in the language used as example, if m and m ′ are respective models of o and o ′ :

Definition 1 (Satisfied correspondence).

m, m ′ |= c, c ′ , ≡ iff m(c) = m ′ (c ′ ) m, m ′ |= c, c ′ , ⊑ iff m(c) ⊆ m ′ (c ′ ) m, m ′ |= c, c ′ , ⊒ iff m(c) ⊇ m ′ (c ′ ) m, m ′ |= c, c ′ , ⊥ iff m(c) ∩ m ′ (c ′ ) = ∅

Definition 2 (Models of aligned ontologies). Given two ontologies o and o ′ and an alignment A between these ontologies, a model of these aligned ontologies is a pair

m, m ′ ∈ M(o) × M(o ′ ), such that each correspondence of A is satisfied by m, m ′ .
The alignment acts as a model filter for the ontologies: it selects the interpretation (here the models) of ontologies which are coherent with the alignments. This allows for transferring information from one ontology to another since reducing the set of models will entail more consequences in each aligned ontology.

The notion of models of aligned ontologies is also useful for defining the usual notions of consistency or consequence.

Definition 3 (Consistent alignment). Given two ontologies o and o ′ and an alignment

A between these ontologies, A is consistent if there exists a model of A. Otherwise A is inconsistent.

For instance, under the classical ontology interpretation, the alignment A presented in Figure 1 is inconsistent as soon as there exists a DepartmentHead because any model would require to satisfy the following equations:

m(Person o ) = m ′ (Person o ′ ) A m(DepartmentHead o ) ⊆ m ′ (Department o ′ ) A m(DepartmentHead o ) ⊆ m(Person o ) o m ′ (Department o ′ ) ∩ m ′ (Person o ′ ) = ∅ o ′
and the DepartmentHead would need to be in both the interpretation of Department o ′ and in that of Person o ′ .

In this paper we will only consider inconsistency, however, the same applies to incoherence: the fact that a class or relation may necessarily be empty, i.e., which would cause inconsistency if instantiated.

Argumentation Approach

In alignment agreement, arguments can be seen as positions that support or reject correspondences. Such arguments interact following the notion of attack and are selected according to the notion of acceptability. These notions were introduced by [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. In Dung's model, the acceptability of an argument is based on a reasonable view: an argument should be accepted only if every attack on it is attacked by an accepted argument. Dung defines an argumentation framework as follows. In Dung's model, all arguments have equal strength, and an attack always succeeds (or successfully attacks). [START_REF] Amgoud | On the acceptability of arguments in preference-based argumentation[END_REF] has introduced the notion of preference between arguments, where an argument can defend itself against weaker arguments. This model defines a global preference between arguments. In order to relate preferences to different audiences, [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF] proposes to associate arguments to the values which supports them. Different audiences can have different preferences over these values. This leads to the notion of successful attacks, i.e., those which defeat the attacked argument, with respect to an ordering on the preferences that are associated with the arguments. This allows for accommodating different audiences with different interests and preferences.

Definition 4 (Argumentation framework [6]). An Argumentation Framework (AF) is a pair A, ⋉ , such that A is a set of arguments and ⋉ (attacks) is a binary relation on

Bench-Capon's framework acknowledges the importance of preferences when considering arguments. However, in the specific context of ontology matching, an objection can still be raised about the lack of complete mechanisms for handling persuasiveness [START_REF] Isaac | Using quantitative aspects of alignment generation for argumentation on mappings[END_REF]. Indeed, many matchers output correspondences with a strength that reflects the confidence they have in the fact that the correspondence between the two entities holds. These confidence levels are usually derived from similarity assessments made during the matching process. They are therefore often based on objective grounds.

For associating an argument to a strength, which represents the confidence that an agent has in some correspondence, [START_REF] Trojahn | A cooperative approach for composite ontology mapping[END_REF] has proposed the strength-based argumentation framework, extending Bench-Capon's model: Definition 5 (Strength-based argumentation framework (SVAF) [START_REF] Trojahn | A cooperative approach for composite ontology mapping[END_REF]). A SVAF is a sextuple A, ⋉, V, v, , s such that A, ⋉ is an AF, V is a nonempty set of values, v : A → V, is the preference relation over V (v 1 v 2 means that, in this framework, v 1 is preferred over v 2 ), and s : A → [0, 1] represents the strength of the argument.

Each audience α is associated with its own argumentation framework in which only the preference relation α differs. In order to accommodate the notion of strength, the notion of successful attack is extended: Definition 6 (Successful attack [START_REF] Trojahn | A cooperative approach for composite ontology mapping[END_REF]). An argument a ∈ A successfully attacks (or defeats, noted a † α b) an argument b ∈ A for an audience α iff

a ⋉ b ∧ (s(a) > s(b) ∨ (s(a) = s(b) ∧ v(a) α v(b)))
Definition 7 (Acceptable argument [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF]). An argument a ∈ A is acceptable to an audience α with respect to a set of arguments S, noted acceptable α (a, S), iff ∀x ∈ A, x † α a ⇒ ∃y ∈ S; y † α x.

In argumentation, a preferred extension represents a consistent position within a framework, which defends itself against all attacks and cannot be extended without raising conflicts:

Definition 8 (Preferred extension). A set S of arguments is conflict-free for an audience

α iff ∀a, b ∈ S, ¬(a ⋉ b) ∨ a † α b. A conflict-
free set of arguments S is admissible for an audience α iff ∀a ∈ S, acceptable α (a, S). A set of arguments S in the VAF is a preferred extension for an audience α iff it is a maximal admissible set (with respect to set inclusion) for α.

In order to determine preferred extensions with respect to a value ordering promoted by distinct audiences, objective and subjective acceptance are defined [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF]. An argument is subjectively acceptable if and only if it appears in some preferred extension for some specific audience. An argument is objectively acceptable if and only if it appears in all preferred extension for every specific audience. We will call objective consolidation the intersection of objectively acceptable arguments for all audiences and subjective consolidation the union of subjectively acceptable arguments for all audiences.

Arguments on correspondences

A way of representing correspondences as arguments within an AF is as follows: Definition 9 (Argument [START_REF] Laera | Argumentation over ontology correspondences in mas[END_REF][START_REF] Trojahn | Conjunctive queries for ontology based agent communication in mas[END_REF]). An argument a ∈ A is a triple a = c, v, h , such that c is a correspondence,v ∈ V is the value of the argument and h is one of +,depending on whether the argument is that c does or does not hold.

The notion of attack is then defined as follow: Definition 10 (Attack [START_REF] Laera | Argumentation over ontology correspondences in mas[END_REF][START_REF] Trojahn | Conjunctive queries for ontology based agent communication in mas[END_REF]). An argument c, v, h ∈ A attacks an argument

c ′ , v ′ , h ′ ∈ A iff c = c ′ and h = h ′ .
For instance, if a = c, v 1 , + and b = c, v 2 , -, a ⋉ b and vice-versa (b is the counter-argument of a, and a is the counter-argument of b).

The way arguments are generated differs in each scenario. The strategy in [START_REF] Trojahn | A cooperative approach for composite ontology mapping[END_REF], negative arguments as failure, relies on the assumption that matchers return complete results. Each possible pair of ontology entities which is not returned by the matcher is considered to be at risk, and a negative argument is generated (h=-).

In this paper, different matchers argue with each others in order to obtain an agreement on their alignments. To do this, each matcher is a different audience. The values in V correspond to the different matching approaches and each matcher m has a preference ordering m over V such that its preferred values are those it associates to its arguments. For instance, consider V = {l, s, w}, i.e., lexical, structural and wordnet-based approaches, respectively, and three matchers m l , m s and m w , using such approaches. The matcher m l has as preference order l m l s m l w.

To illustrate the agreement process, consider the alignment A Figure 1 and two matchers i and j. Both i and j generate the correspondence (1) and j correspondence (2). The following arguments are then created by i and j:

a i,1 : Person o , Person o ′ , ≡, 1.0 , w, + a i,2 : DepartmentHead o , Department o ′ , ≡, 0.5 , w, - a j,1 : Person o , Person o ′ , ≡, 1.0 , l, + a j,2 : DepartmentHead o , Department o ′ , ⊑, 0.8 , l, +
After generating their arguments, the matchers exchange their arguments with each other. The matcher i sends to j its arguments a i,1 and a i,2 , and vice-versa. i has a preference ordering w i l, while j has l j w. Having the complete set of arguments, the matchers generate their preferred extensions p i and p j . For both p i and p j , the arguments a i,1 , a j,1 and a j,2 are acceptable: a i,1 and a j,1 are not attacked, while a j,2 successfully attacks a i,2 because both arguments have opposite values of h but a j,2 has highest strength than a i,2 . So, the set of globally acceptable correspondences, A, contains both (1) and (2). It is the alignment associated with the objective consolidation.

Definition 11 (Alignment associated with an extension). Given an extension S in a SV AF , the alignment associated with this extensions is:

A(S) = {c; ∃ c, v, + ∈ S}.
However, this set is not consistent. Due to the fact that DepartmentHead is subsumed by Person in o, and Person and Department are disjoint concepts in o ′ , A is inconsistent as soon as there exists one Department.

Consistency-driven Argumentation

Resolving the inconsistency problem in alignment agreement has two possible alternatives: (a) express the inconsistency within the argumentation framework, as in [START_REF] Amgoud | Bridging the gap between abstract argumentation systems and logic[END_REF][START_REF] Besnard | Argumentation based on classical logic[END_REF]; or (b) deal alternatively with the logical and argumentative parts of the problem. Integrating the logic within the argumentation framework seems a more elegant solution and it can be achieved straightforwardly when correspondences are arguments and incompatible correspondences can mutually attack each others. However, this works only when two correspondences are incompatible. When the set of incompatible correspondences is larger, the encoding is not so straightforward and may lead to generation of an exponential amount of argument and attacks.

For that purpose, we define the consistency associated with an extension.

Definition 12 (Consistency). An extension S is said consistent iff its associated alignment A(S) is consistent.

There are different ways to account for consistency in SVAF. The first one retains only consistent preferred extensions. However, the set of preferred consistent extensions may be empty. A fallback would be to consider maximal preferred consistent sub-extensions.

Definition 13 (Maximal preferred consistent sub-extensions).

A consistent extension S is a maximal preferred consistent sub-extension iff there exists a preferred extension S ′ such that S ⊆ S ′ and ∀S ′′ ; S ⊂ S ′′ ⊆ S ′ , S ′′ is not consistent.

There may be several such sub-extensions. Another approach, considered here, is to work on consolidations, i.e., the set of objective or subjective arguments.

Definition 14 (Maximal consistent sub-consolidations).

A consistent extension S is a maximal consistent sub-consolidation of an (objective or subjective) consolidation S ′ iff S ⊆ S ′ and ∀S ′′ ; S ⊂ S ′′ ⊆ S ′ , S ′′ is not consistent.

We propose a consistency-driven protocol that computes the maximal consistent objective sub-consolidations. The algorithm removes the correspondences that introduce inconsistencies into the resulting alignment, for maintaining the coherence within the argumentation system. First, as in Section 3.1, the matchers compute their preferred extension from which the objective consolidation, O, is obtained. Based on O, the maximal consistent sub-consolidations is then determined. It can be generalised to consider subjective consolidation or each preferred extension separately. If the objective consolidation is consistent, then the algorithm returns it. If not, the maximal consistent sub-consolidation S is computed.

For computing S we have used the algorithm proposed by [START_REF] Meilicke | An efficient method for computing alignment diagnoses[END_REF] which identifies the minimal sets of incoherent correspondences and removes them from the original alignment. The algorithm is based on the theory of diagnosis, where a diagnosis is formed by the correspondences with lowest confidence degrees that introduce incoherence in the alignment. It partially exploits incomplete reasoning techniques to increase runtime performance, preserving the completeness and optimality of the solution.

Dataset, matchers and argumentation frameworks

The proposed approach is evaluated on a group of alignments from the conference track of the OAEI1 2009 campaign. The data set consists of 15 ontologies in the domain of conference organisation. They have been developed within the OntoFarm project 2 We use the subset of these test cases where a reference alignment is available (21 alignments, which corresponds to the alignment between 7 ontologies) 3 . We focus on equivalence correspondences, which are taken into account in the reference alignment, and filter out subsumption correspondences.

We have chosen the alignments generated by the four best matchers that have participated in the 2009 OAEI conference track [START_REF] Euzenat | Results of the ontology alignment evaluation initiative[END_REF]: AMaker, Aflood, AMext and Asmov.

Each matcher has a SVAF and a private preference order, which is based on the f-measure ordering for all matchers -AMaker (0.57), Aflood (0.52), AMext (0.51) and Asmov (0.47). The highest preferred value of each matcher is the value that it associates to its arguments. For instance, AMaker has as preference ordering: v amaker amaker v af lood amaker v amext amaker v asmov , while Asmov has the ordering: v asmov asmov v amaker asmov v af lood asmov v amext .

For negative arguments (h = -), we use two different strength values. First, we consider that the strength can vary according to the matcher quality (conformance with the reference alignment). We assume that this strength is inversely proportional to the probability that a false positive correspondence is retrieved by the matcher. Such probability can be measured by the fallout of the alignment A, given the reference alignment R. Then, we define str for the matcher m:

f allout(A, R) = | A \ R | | A | , str m = 1 -f allout(A m , R)
Second, we use str=1.0, assuming that matchers strongly reject correspondences that they do not found (it could be the case when the information about the matcher quality is not available).

Results and discussion

We measure precision and recall of the maximal consistent sub-consolidation, S, with respect to the reference alignments. First, we present the results from our approach and next we compare them with the results from each matcher. Figure 2 presents the results from the objective consolidations, O, and from the maximal consistent subconsolidation, S, for SVAFs with str = 1 and fallout-based str.

For SVAF with str = 1, argumentation (O) is sufficiently selective for generating consistent objective consolidations. We obtain high precision but low recall. This behaviour is due to several reasons. First, we are using objective consolidations and only arguments present in every preferred extension are considered (what leads to an increase in precision). Correspondences being accepted by all matchers have high probability to be consistent. Second, we use str = 1 for negative arguments (h = 1) and thus a true positive (correct) correspondence with strength lower than 1.0 is successfully attacked by a false negative correspondence with strength 1.0 (what decreases the recall).

Using fallout-based str (Figure 2), we have an opposite behaviour. Argumentation is not able to filter out all inconsistent correspondences. We have low precision and high recall. This occurs because negative arguments are not strong enough for successfully attacking all positive arguments (including the incorrect ones). As a result, many correspondences are selected, what increases the probability for selecting inconsistent correspondences. When applying consistency checking, S, in average, precision slightly increases, while recall decreases. This effect is due the way the algorithm for removing the inconsistencies works. An incorrect (but consistent) correspondence might cause the removal of all conflicting correspondences with lower confidence, and thus some correct correspondences are filtered out. Second, we compare the results from O and S with the results from each matcher. Figure 2 shows the matcher results with and without consistency checking. In the majority of the test cases, the precision increases when filtering out the inconsistent correspondences, while recall decreases (in the case of Aflood, for some tests, the precision decreases while Amaker maintains its recall). As stated before, this is due to the fact that some correspondences are incorrect with respect to the reference alignment but consistent, as well as some correct correspondences are not included in the consistent set because together with some incorrect (but consistent) correspondences, they introduce inconsistencies into the set. Asmov is the only system able to check the consistency in its alignments. In terms of f-measure, apart Asmov, consistency checking improves the results from Amaker and Amext.

Comparing the results from SVAFs with the results from each matcher, for str=1 (Figure 2), argumentation outperforms all matchers in terms of precision, but recall is below all matchers. For fallout-based str, we find an opposite behaviour. All matchers outperform argumentation in terms of precision, but recall is better with argumentation. Looking for argumentation and consistency checking together, although consistency checking slightly improves the precision, both precision and recall are below every matcher. Consistency or argumentation improves results, while contrary to the intuition, we do not observe that the combination of both of these provide more improvements.

Following our (partial) experiments, we can observe that the behaviour of argumentation highly depends on the strength of the arguments. Argumentation is more or less selective when using strong or weak strengths for negative arguments, respectively. Thus, an important issue in the argumentation model is related with the choice of strengths of negative arguments.

Using logical consistency checking alone has positive effects in terms of f-measure for the majority of matchers. On the other hand, combining argumentation and consistency checking slightly improves the precision, when argumentation is not sufficiently selective for generating consistent alignments, but in terms of f-measure, this combination has some negative effects. It is due particularly to the decrease in recall.

Related Work

Few ontology matching systems have been developed using semantic-based techniques. Examples of systems using some kind of logical verification are S-Match [START_REF] Giunchiglia | S-Match: an algorithm and an implementation of semantic matching[END_REF] and AS-MOV [START_REF] Jean-Mary | Ontology matching with semantic verification[END_REF]. S-Match explores propositional satisfiability techniques (SAT) for generating correspondences between graph-like structures. ASMOV semantically verifies the alignments for filtering inconsistencies. However, ASMOV lacks a well defined alignment semantics and notions as correctness or completeness are thus not applicable [START_REF] Meilicke | An efficient method for computing alignment diagnoses[END_REF].

In the field of alignment agreement based on argumentation, few approaches have been proposed. In [START_REF] Laera | Argumentation over ontology correspondences in mas[END_REF], Bench-Capon's model is used to deal with arguments that support or oppose candidate correspondences between ontologies. Both Bench-Capon's and SVAFs frameworks fail at rendering the fact that sources of correspondences often agree on their results, and that this agreement may be meaningful. [START_REF] Isaac | Using quantitative aspects of alignment generation for argumentation on mappings[END_REF] have adapted the SVAF in order to consider the level of consensus between the sources of the correspondences, by introducing the notions of support and voting into the definition of successful attacks. The work from [START_REF] Doran | Efficient argumentation over ontology correspondences[END_REF] aims at identifying subparts of ontologies which are sufficient for interpreting messages. This contributes to reduce the consumed time, at a minimal expense in accuracy.

In the field of alignment inconsistency, [START_REF] Meilicke | Reasoning support for mapping revision[END_REF] and [START_REF] Ruiz | Ontology integration using mappings: Towards getting the right logical consequences[END_REF] considered correcting inconsistent alignments. Revision is obtained exclusively by suppressing correspondences from the alignment through minimising the impact of this suppression. In [START_REF] Meilicke | Reasoning support for mapping revision[END_REF], the goal is to feed the consistent alignment back to a matcher so that it can find new correspondences. This process can be iterated until an eventual fix-point is reached. Similarly, [START_REF] Qi | A conflict-based operator for mapping revision[END_REF] provides a revision operator by modifying one alignment between two ontologies such that the result be consistent. Consistency and consequences are given by merging both ontologies and alignments within the same standard theory. Operators are provided based on the notion of minimal conflict sets.

Concluding Remarks

We have defined consistency-driven argumentation for alignment agreement. This fills a gap between argumentation-based matching and consistency-based alignment repairs. We have experimented our strategy on a set of alignments from expressive ontologies. The conclusion is that though theoretically grounded, the extra consistency step does not improve argumentation alone. At least in our experimental setting the argumentation process is incidentally able to provide near consistent extensions. We have analysed the features of consistency checking and argumentation which cause this result.

Hence from these (partial) experiments we can conclude that applying inconsistency recovery and argumentation independently improves results, while using them together does not improve significantly the results. If this does not discard the validity of the approach, it reveals that it should not be applied without care, especially given its complexity.

Further study is required to know better in which context matching and argumentation leads to inconsistency. One source of improvement would be to take into account several such alignments between several ontologies (a network of ontologies). Indeed, these could raise inconsistency within networks of ontologies which would have to be considered as well.

Fig. 1 .

 1 Fig. 1. Fragments of ontologies o and o ′ with alignment A.

  A correspondence c = e, e ′ , r is satisfied by two models m, m ′ of o, o ′ on a common domain D if and only if m ∈ M(o), m ′ ∈ M(o ′ ) and m(e), m ′ (e ′ ) ∈ r U such that r U ⊆ D×D is the interpretation of the relation. This is denoted as m, m ′ |= c.

  A. a ⋉ b means that the argument a attacks the argument b. A set of arguments S attacks an argument b iff b is attacked by an argument in S.

Fig. 2 .

 2 Fig. 2. SVAF with str = 1 and fallout-based str: objective consolidation (O) -intersection of objectively acceptable arguments for all audiences, without consistency-checking -and maximal consistent sub-consolidation (S) -consistent subset of objectively acceptable arguments; and individual results for each matcher.

Ontology Alignment Evaluation Initiative: http://oaei.ontologymatching.org/

http://nb.vse.cz/ ˜svatek/ontofarm.html

As in[START_REF] Euzenat | Results of the ontology alignment evaluation initiative[END_REF], the ontology Iasted is filtered out of our experiments because it causes reasoning problems when combined with other ontologies. Thus, we have 15 test cases.

Acknowledgements

We are grateful to Christian Meilicke for letting us use his consistent sub-alignment software.