Rémi Tournaire
email: remi.tournaire@imag.fr

Jean-Marc Petit

Marie-Christine Rousset

Alexandre Termier

Discovery of Probabilistic Mappings between Taxonomies: Principles and Experiments

In this paper, we investigate a principled approach for defining and discovering probabilistic mappings between two taxonomies. First, we compare two ways of modeling probabilistic mappings which are compatible with the logical constraints declared in each taxonomy. Then we describe a generate and test algorithm which minimizes the number of calls to the probability estimator for determining those mappings whose probability exceeds a certain threshold. Finally, we provide an experimental analysis of this approach. P r(lhs(m)∩rhs(m)) P r(lhs(m))

Introduction

The decentralized nature of the development of Web data management systems makes inevitable the independent construction of a large amount of personalized taxonomies used for annotating data and resources at the Web scale. Taxonomies are hierarchical structures appropriate to data categorization and semantic annotation of resources. They play a prominent role in the Semantic Web since they are central components of OWL [START_REF] Dean | OWL web ontology language reference[END_REF] or RDF(S) [START_REF] Hayes | RDF Semantics. W3C Recommendation[END_REF] ontologies. A taxonomy constrains the vocabulary used to express metadata or semantic annotations to be classes that are related by structural relationships. Taxonomies are easy to create and understand by humans while being machine interpretable and processable thanks to a formal logical semantics supporting reasoning capabilities.

In this setting, establishing semantic mappings between taxonomies is the key to enable collaborative exchange of semantic data.

In this work we focus on discovering mappings between populated taxonomies like Web Directories or folksonomies used for example for organizing musical songs. Web Directories like the Yahoo! Directory3 and the Google directory 4(see Figure 2) can be considered as taxonomies because they are hierarchical structures categories organizing web pages. Folksonomies like those represented in Figure 1 are small taxonomies created by final users and populated with musical files, for example. Providing mappings between two taxonomies makes possible an exchange of documents (instances) by querying one taxonomy with the vocabulary of the other one. For instance, mappings between Yahoo! and Google directories allow to query both of them for pages about "Autos" while covering both the pages indexed by Yahoo! and those indexed by Google. With folksonomies of Figure 1, a local query of songs about "XXth Vocal" may be completed by songs populating the distant class XXth Opera thanks to a provided mapping representing the fact that XXth Opera is included in XXth Vocal. We claim that such an application of joint querying requires a grounded and semantic way for defining the mappings and measuring their degree of confidence.

Manually finding such mappings is clearly not possible at the Web scale. Therefore, the automatic discovery of semantic mappings is the bottleneck for scalability purposes. Many techniques and prototypes have been developed to suggest candidate mappings between several knowledge representations including taxonomies, ontologies or schemas (see [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF][START_REF] Shvaiko | A survey of schema-based matching approaches[END_REF] for surveys).

Particular focus and applications of the proposed approach

Most of the proposed approaches rely on evaluating the degree of similarity between the elements (e.g., classes, properties, instances) of one ontology and the elements of another ontology. Many different similarity measures are proposed and often combined. Most of them are based on several syntactic, linguistic or structural criteria to measure the proximity of the terms used to denote the classes and/or their properties within the ontology. Some of them exploit characteristics of the data declared as instances of the classes (e.g. [START_REF] Doan | Learning to map between ontologies on the semantic web[END_REF][START_REF] David | An interactive, asymmetric and extensional method for matching conceptual hierarchies[END_REF][START_REF] Ichise | Integrating multiple internet directories by instance-based learning[END_REF][START_REF] Doan | Learning mappings between data schemas[END_REF]).

Almost all the existing matching systems return for every candidate pair of elements a coefficient in the range [0,1] which denotes the strength of the semantic correspondence between those two elements ( [START_REF] Euzenat | Similarity-based ontology alignment in owl-lite[END_REF][START_REF] Madhavan | Generic schema matching with cupid[END_REF][START_REF] Castano | H-match: an algorithm for dynamically matching ontologies in peer-based systems[END_REF]). Those coefficients are the basis for yearly international comparative evaluation campaigns [START_REF] Euzenat | Ontology alignment evaluation initiative[END_REF][START_REF] Euzenat | Results of the ontology alignment evaluation initiative[END_REF]. Those approaches usually consider each candidate mapping in isolation. In particular, they do not take into account possible logical implications between mappings, which can be inferred from the logical inclusion axioms declared between classes within each ontology. This raises a crucial issue: the similarity coefficients returned by the existing ontology or schema matching systems cannot be interpreted as probabilities of the associated mappings. On the other hand, some approaches for detecting semantic mappings by logical reasoning have been proposed (e.g., [START_REF] Serafini | An algorithm for matching contextualized schemas via SAT[END_REF]). By construction, such logical methods are limited to discover mappings that are certain.

We claim that uncertainty is intrinsic to mapping discovery. It is first due to the methods employed for detecting them. Another important reason is that the mappings are usually interpreted as simple semantic relations such as subsumption or equivalence relations between classes, which is often an oversimplification of the complex overlapping relation existing in the reality between two classes of different and independenty developed ontologies.

In this article, we focus on inclusion mappings. Inclusion mappings are of primary importance for ontology alignment applications, but they have received only little attention until now. In addition, inclusion mappings with a probabilistic semantics are useful and easily interpretable by human or automatic systems, because they combine several theoretical and practical advantages:

1. Inclusion mappings are more likely to happen than equivalences (theoretically at least twice), and so our method discovers more information than methods based on equivalences. 2. Inclusion mappings are logically weaker than equivalences but have a clear logical semantic that is directly useful for integration and query rewriting settings. For example, the inclusion mapping Google/Software/Games ⊑ Yahoo/Entertainment allows to make a query about Yahoo/Entertainment (or any of its superclasses) and leads to answer this query by considering that all pages in the category Google/Software/Games should be in the answer. In this way, an alignment between Yahoo! and Google directories constituted by inclusion mappings may enable an access to all referenced pages of both Yahoo! and Google with a single query. A large amount of relevant mappings (like the above mapping) could not have been discovered by methods that return only equivalences. 3. The probabilities associated to mappings can be used by others systems that require probabilities, for example in order to know what are the most reliable knowledge. Properly handling uncertainty is a key point for the Semantic Web due to the heterogeneous and unreliable nature of available data. In particular, probabilistic inclusion mappings directly fit the framework of probabilistic databases [START_REF] Dong | Data integration with uncertainty[END_REF] and probabilistic reasoning [START_REF] Adams | A Primer of Probability logic[END_REF]. These works contribute to probabilistic query answering which constitutes a major way to exchange data between heterogeneous schemas and ontologies. 4. In a probabilistic query answering setting, users can obtain probabilistic answers to their queries, thanks to a probabilistic reasoning using probabilistic mappings. From an user point-of-view, a probability has a well-understood meaning when standing for confidence: a probability of 0.5 means there is an even chance the mapping would be correct. 5. Probability theory is quite simple, general, popular and grounded for dealing with uncertainty, and the generality and reusability is a key point in computer science. 6. Finally, from a theoretical point of view in the ontology matching domain, there is a need to better understand the fundations of the uncertainty in data and schema integration ( [START_REF] Shvaiko | Ten challenges for ontology matching[END_REF]).

Main points and organization of this article

In this paper, we propose an approach to discover automatically probabilistic inclusion mappings between classes of taxonomies, in order to query multiple folksonomies or Web Directories in a way that is grounded, robust and easily interpretable.

First, we investigate and compare two instance-based ways of modeling probabilistic mappings which are compatible with the logical constraints declared in each taxonomy. In those two probabilistic models, the probability of a mapping relies on the joint probability distribution of the involved classes. They differ on the property of monotony of the corresponding probability function with respect to the logical implication.

For estimating the mappings probabilities, we follow a Bayesian approach to statistics by exploiting the description of the instances categorized in each taxonomy as observations for the involved classes. The point is that to estimate the joint probability distribution of two classes C 1 and C 2 of different taxonomies, we have to determine among the instances that are declared in C 1 the ones that can be classified in C 2 (based on their description), and similarly for the classification in C 2 of instances that are declared in C 1 . Different classifiers can be used for that purpose.

Based on the above probabilistic setting, we have designed, implemented and experimented a generate and test algorithm for discovering the mappings whose probability is greater than a given threshold. In this algorithm, the monotony of the probability function is exploited for avoiding the probability estimation of as many mappings as possible.

We have performed thorough experiments on controlled synthetic data to measure the performances of such a systematic approach in fonction of the number of possible mappings and the number of instances per classes. We have also performed qualitative experiments to measure the impact of the classifiers used to estimate the probabilities on the precision and recall of the mappings returned by our algorithm.

The paper is organized as follows. Section 2 presents the formal background and states the problem considered in this paper. Section 3 is dedicated to the definition and computation of mapping probabilities. In Section 4, we present the algorithm that we propose for discovering mappings with high probabilities (i.e., greater than a threshold). Section 5 surveys the quantitative and qualitative experiments that we have done on synthetic controlled data. Finally, in Section 6, we compare our approach to existing works and we conclude.

Formal background

We first define taxonomies as a graphical notation and its interpretation in the standard first-order logical semantics, on which the inheritance of instances is grounded. Then, we define mappings between taxonomies as inclusion statements between classes of two different taxonomies. Finally, we set the problem statement of matching taxonomies that we consider in this paper.

Taxonomies: classes and instances

Given a vocabulary V denoting a set of classes, a taxonomy T V is a Directed Acyclic Graph (DAG) where each node is labelled with a distinct class name of V, and each arc between a node labelled with C and a node labelled by D represents a specialization relation between the classes C and D.

Each class in a taxonomy can be associated with a set of instances which have an identifier and a content description modeled with an attribute-value language.

By a slight abuse of notation, we will speak of the instance i to refer to the instance identified by i.

Figure 1 shows two samples of taxonomies related to the Music domain. Bold arrows are used for representing specialization relations between classes, and dashed arrows for membership relation between instances and classes. In both taxonomies, some instances, with attribute-value description denoted between brackets, are associated to classes. For example, #102 is an instance identifier and [Wagner, Tristan und Isold, ...] its associated description.

The instances that are in the scope of our data model can be web pages (whose content description is a set of words) identified by their URL, RDF resources (whose content description is a set of RDF triples) identified by a URI, or audio or video files identified by a signature and whose content description may be attribute-value metadata that can be extracted from those files.

We consider only boolean attribute-value description. Such a description could be obtained by discretization of attribute-value pairs given in a more complex language, like in Figure 1 where textual values are used. We consider that, possibly after a preprocessing which is out of the scope of this paper, the instances are described in function of a fixed set of boolean attributes {At 1 , . . . , At m }. Then, for an instance i, its description, denoted descr(i), is a vector [a 1 , . . . , a m ] of size m such that for every j ∈ [1..m], a j = 1 if the attribute At j belongs to the content description of i, and a j = 0 otherwise.

Taxonomies have a logical semantics which provides the basis to define formally the extension of a class as the set of instances that are declared or can be inferred for that class.

Logical semantics

There are several graphical or textual notations for expressing the specialization relation between a class C and a class D in a taxonomy. For example, in RDF(S) [START_REF] Hayes | RDF Semantics. W3C Recommendation[END_REF] which is the first standard of the W3C concerning the Semantic Web, it is denoted by (C rdf s:subclassOf D). It corresponds to the inclusion statement C ⊑ D in the description logics notation.

Similarly, a membership statement denoted by an isa arc from an instance i to a class C corresponds in the RDF(S) notation to (i rdf :type C), and to C(i) in the usual notation of description logics.

All those notations have a standard model-theoretic logical semantics based on interpreting classes as sets: an interpretation I consists of a non empty domain of interpretation ∆ I and a function . I that interprets each class as a non empty subset of ∆ I , and each instance identifier as an element of ∆ I . The classes declared in a taxonomy are interpreted as non empty subsets because they are object containers. According to the unique name assumption, two distinct identifiers a and b have a distinct interpretation (a I = b I ) in any interpretation I.

I is a model of a taxonomy T if:

for every inclusion statement E ⊑ F of T : Let D be the set of the instances associated to a taxonomy T . The extension of a class C in T , denoted by Ext(C, T ), is the set of instances for which it can be inferred from the membership and inclusion statements declared in the taxonomy that they are instances of C:

E I ⊆ F I , - for
Ext(C, T ) = {d ∈ D/ T |= C(d)}

Mappings

The mappings that we consider are inclusion statements involving classes of two different taxonomies T 1 and T 2 . To avoid ambiguity and without loss of generality, we consider that each taxonomy has its own vocabulary: by convention we index the names of the classes by the index of the taxonomy to which they belong. For instance, when involved in a mapping, the class XXth Opera of the taxonomy T 2 of Figure 1 will be denoted by XXth Opera 2 while the class XXth V ocal of the taxonomy T 1 will be denoted by XXth V ocal 1 . Mappings between T 1 and T 2 are of the form A 1 ⊑ B 2 or A 2 ⊑ B 1 where A 1 and B 1 denote classes of T 1 and A 2 and B 2 denote classes of T 2 .

For a mapping m of the form A i ⊑ B j , its left-hand side A i will be denoted lhs(m) and its right-hand side will be denoted rhs(m).

A mapping A i ⊑ B j has the same meaning as a specialization relation between the classes A i and B j , and thus is interpreted in logic in the same way, as a set inclusion. The logical entailment between classes extends to logical entailment between mappings as follows.

Definition 1 (Entailment between mappings). Let T i and T j be two taxonomies. Let m and m ′ be two mappings between T i and T j : m entails m ′ (denoted m m ′ ) iff every model of T i , T j and m is also a model of m ′ .

It is straightforward to show that is a (partial) order relation on the set M(T i , T j ) of mappings between the two taxonomies T i and T j . If m m ′ , we will say that m is more specific than m ′ (also that m entails m ′ ) and that m ′ is more general than m (also that m ′ is an implicate of m).

The following proposition characterizes the logical entailment between mappings in function of the logical entailment between the classes of their left hand sides and right hand sides. For example, two mappings between taxonomies T 1 and T 2 of Figure 1 are illustrated in Figure 3: the mapping XXth Opera 2 ⊑ XXth V ocal 1 is more specific than the mapping XXth Opera 2 ⊑ XXth Century 1 , -and the mapping RecentClassical 2 ⊑ XXth Instrumental 1 is more specific than the mapping Ravel 2 ⊑ Classical M usic 1 .

Problem statement

Among all possible mappings between two taxonomies, we want to determine those that are the most probable given the descriptions of the instances associated to each class of the taxonomies. More precisely, the main problem addressed in this paper is the design of an efficient generate and test algorithm which minimizes the number of calls to the probability estimator for determining those mappings whose probability exceeds a certain threshold. The mappings returned by this algorithm will be said probabilistically valid (valid for short).

Two subproblems are emphasized. The first subproblem to handle is the choice of an appropriate probabilistic model for defining the probability of a mapping. As mentioned in the introduction, a probabilistic semantics of mappings cannot be independent of the logical semantics. In particular, it is expected that a mapping logically entailed by a mapping with a high probability (i.e., whose probability exceed a threshold) will also get a high probability. The second subproblem is then to find a good probability estimator to compute mapping probabilities, given two taxonomies and the description of their instances.

3 Mapping probabilities: models and estimation

Modeling probabilistic mappings

We have considered two relevant probabilistic models for modeling uncertain mappings. They are both based on the discrete probability measure defined on subsets of the sample set representing the set of all possible instances of the two taxonomies. From now on, we will denote P r(E) the probability for an instance to be an element of the subset E.

The first model defines the probability of a mapping A i ⊑ B j as the conditional probability for an instance to be an instance of B j knowing that it is an instance of A i . It is the natural way to extend the logical semantics of entailment to probabilities.

The second model comes directly from viewing classes as subsets of the sample space: the probability of A i ⊑ B j is the probability for an element to belong to the set A i ∪ B j , where A i denotes the complement set of A i in the sample set.

These two models are described in the following definition.

Definition 2 (Two probabilities for a mapping). Let m be a mapping of the form A i ⊑ B j .

-Its conditional probability, denoted P c (m), is defined as: P c (m) = P r(B j |A i ).

-Its union set probability, denoted P u (m), is defined as:

P u (m) = P r(A i ∪ B j ).
The following proposition states the main (comparative) properties of these two probabilistic models. In particular, they both meet the logical semantics for mappings that are certain, and they can both be equivalently expressed using joint probabilities.

Proposition 2. Let m be a mapping between two taxonomies T i and T j . The following properties hold:

1. P u (m) ≥ P c (m). 2. If m is a certain mapping (i.e., T i T j |= m): P c (m) = P u (m) = 1. 3. P u (m) = 1 + P r(lhs(m) ∩ rhs(m)) -P r(lhs(m)) 4. P c (m) =
They differ on the monotony property w.r.t the (partial) order corresponding to logical implication (cf. Definition 1): P u verifies a property of monotony whereas P c verifies a property of weak monotony as stated in the following theorem.

Theorem 1 (Property of monotony). Let m and m ′ two mappings.

1. If m m ′ then P u (m) ≤ P u (m ′ ) 2. If m m ′ and lhs(m) = lhs(m ′ ) then P c (m) ≤ P c (m ′ )
The proof [START_REF] Tournaire | Découverte automatique de correspondances entre taxonomies -internal report[END_REF] results from Proposition 1 and Proposition 2 which relate mappings with the classes of their left hand sides and right hand sides for logical entailment and probabilities respectively, and from considering (declared or inherited) class inclusions within each taxonomy as statements whose probability is equal to 1.

Bayesian estimation of mappings probabilities

As shown in Proposition 2, the computation of P u (m) and P c (m) relies on computing the set probability P r(lhs(m)) and the joint set probability P r(lhs(m) ∩ rhs(m)). These values are unknown and must be estimated. They are the (unknown) parameters of the underlying Bernoulli distributions modeling the membership function to a set as a random variable taking only two possible values 0 or 1. Following the Bayesian approach to statistics [START_REF] Degroot | Optimal Statistical Decisions[END_REF], we model these (unknown) parameters as continuous random variables, and we use observations to infer their posterior distribution from their prior distribution. In the absence of any particular knowledge, the prior distribution is usually set to the uniform distribution. In probability theory, a natural way of estimating the value of a parameter modeled by a random variable is to take its expected value. All this is summarized in the following definition.

Definition 3 (Bayesian estimator of P r(E)).

Let E be a subset of the sample set Ω. Let O be a sample of observed elements for which it is known whether they belong or not to E. The Bayesian estimator of P r(E), denoted P r(E), is the expected value of the posterior distribution of P r(E) knowing the observations on the membership to E of each element in O, and setting the prior probability of a random set to 1 2 , and of the intersection of two random sets to 1 4 . Setting the prior probabilities to 1 2 and 1 4 depending on whether E is a class or a conjunction of classes corresponds to the uniform distribution of instances among the classes.

Let Ext(E, O) be the set of observed instances of O that are recognized to be instances of E. According to a basic theorem in probability theory (Theorem 1, page 160, [START_REF] Degroot | Optimal Statistical Decisions[END_REF]), if the prior distribution of the random variable modeling P r(E) is a Beta distribution of parameters α and β, then its posterior distribution is also a Beta distribution the parameters of which are: α+| Ext(E, O)| and β +|O|.

The Beta distribution is a family of continuous probability distributions parameterized by two parameters α and β which play an important role in Bayesian statistics. If its two parameters are equal to 1, it corresponds to the uniform distribution for the associated random variable. Its expected value is: α α+β . In our setting, the set O is the union of the two (possibly disjoint) sets O i and O j of instances observed in two distinct taxonomies T i and T j . This raises the issue of computing the set Ext(E, O i ∪ O j ), specially when E is the conjonction of a class C i of the taxonomy T i and a class D j of the other taxonomy T j . In this case:

Ext(C i ∩ D j , O i ∪ O j ) = Ext(C i , O i ∪ O j ) ∩ Ext(D j , O i ∪ O j )
Since the two taxomomies have been created and populated independently by different users, the only information that can be extracted from those two taxonomies are the extensions of each class within each taxonomy:

Ext(C i , T i ) and Ext(D j , T j ).
By construction, it is likely that their intersection contains very few instances or even no instance at all. Therefore, we use automatic classifiers to compute Ext(E, O). The machine learning community has produced several types of classifiers that have been extensively (theoretically and experimentally) studied (see [START_REF] Mitchell | Machine Learning[END_REF] for a survey) and have been made available through open source platforms like Weka [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF]. They are based on different approaches (e.g., Naive Bayes learning, decision trees, SVM) but they all need a training phase on two sets of positive and negative examples. Let C be a classifier. Let E be a class of one of the two taxonomies that we denote by T i , the other one being denoted T j . For computing Ext(E, O) we follow the same approach as [START_REF] Doan | Learning to map between ontologies on the semantic web[END_REF]:

-C is trained on the descriptions of the elements of the two sets Ext(E, T i ) and O i \Ext(E, T i ) taken as the sets of of positive and negative examples respectively, -C is then applied to each instance of O j to recognize whether it belongs to E or not.

As a result, the following theorem provides a simple way to compute the Bayesian estimations P u (m) and P c (m) of the two probabilities P u (m) and P c (m) defined in Definition 2.

Theorem 2 (Estimation of mapping probabilities).

Let m : C i ⊑ D j be a mapping between two taxonomies T i and T j . Let O be the union of instances observed in T i and

T j . Let N = |O|, N i = | Ext(C i , O)|, N j = | Ext(D j , O)| and N ij = | Ext(C i ∩ D j , O)|. -P u (m) = 1 + 1+N ij 4+N -1+N i 2+N -P c (m) = 1+N ij 4+N × 2+N 1+N i
It is worth comparing the (Bayesian) ratios 1+Ni 2+N and 1+Nij 4+N appearing in the formulas for computing P u (m) and P c (m) in Theorem 2 with the corresponding ratios Ni N and Nij N that would have been obtained by following the standard (frequency-based) approach of statistics (as it is the case for instance in [START_REF] Doan | Learning to map between ontologies on the semantic web[END_REF]).

The corresponding ratios converge to the same expected value when there are many instances, but the Bayesian ratios are more robust to a small number of instances. In contrast with the frequency-based approach, they are defined even in the case where no instance is observed: their respective values (i.e., 1 2 and 1 4 ) in this particular case correspond to the probability of random sets and the joint probability of of two random sets respectively for a uniform distribution of instances in the sample set.

Discovery process of probabilistic mappings

Given two taxonomies T i and T j (and their associated instances), let M(T i , T j ) be the set of all mappings from T i to T j (i.e., of the form C i ⊑ D j ). The ProbaMap algorithm determines all mappings m of M(T i , T j ) that verify two probabilisticbased criterion of P u (m) ≥ S u and P c (m) ≥ S c , where S u and S c are two thresholds in [0, 1].

Candidate mapping generation

The principle of ProbaMap algorithm is to generate mappings from the two sets of classes in the two taxonomies ordered according to a topological sort [START_REF] Cormen | Introduction to Algorithms[END_REF]. Namely, (see the nested loops (Line 4) in Algorithm 1) it generates all the mappings C i ⊑ D j by enumerating the classes C i of T i following a reverse topological order and the classes D j of T j following a direct topological order. The following proposition is a corollary of Proposition 1.

Proposition 3. Let T i and T j two taxonomies. Let ReverseT opo(T i ) be the sequence of classes of T i resulting from a reverse topological sort of T i . Let T opo(T j ) be the sequence of classes of T j resulting from a topological sort of T i . Let m : C i ⊑ D j and m ′ :

C ′ i ⊑ D ′ j two mappings from T i to T j . If m ′ is an implicant of m (i.e., m ′ m), then C i is before C ′ i in ReverseT opo(T i ) or C i = C ′
i and D j is before D ′ j in T opo(T j ). This proposition ensures that the mappings are generated in an order that respect the logical implication, according to the knowledge of the taxonomies.

Pruning the candidate mappings to test Based on the monotony property of the probability function P u (Theorem 1), every mapping m ′ implicant of a mapping m such that P u (m) < S u verifies P u (m ′ ) < S u . Therefore, in ProbaMap, we prune the probability estimation of all the implicants of every m such that P u (m) < S u . We shall use the notation Implicants(m) to denote the set of all mappings that are implicants of m. Similarly, based on the property of weak monotony of the probability function P c (Theorem 1), when a tested candidate mapping m is such that P c (m) < S c we prune the probability estimation of all the implicants of m having the same left-hand side as m. We shall denote this set: Implicants c (m). Based on Proposition 1, Implicants(m) and Implicants c (m) can be generated from T i and T j .

The ProbaMap Algorithm The resulting ProbaMap algorithm is described in Algorithm 1, in which primitive functions like Implicants and Implicants c returns the implicants of the mapping in argument and the implicants having the same class at the left-hand side. -Topo andReverseTopo return the sequences of classes of a taxonomy that respect the logical implication order (respectively in the direct and reverse directions). -ext i and ext j represent the two maps that store the extension of each class of respectively T i and T j , or the extensions obtained by classification when it is enabled.

Algorithm 1 returns mappings directed from T i to T j . In order to obtain all valid mappings, it must be applied again by swapping its inputs T i and T j . if m ∈ M NV al then 7:

if Pi(m, exti, extj, Ti, Tj ) ≥ Si then 8:

if Pc(m, exti, extj, Ti, Tj) ≥ Sc then 9: The discovered valid mappings are stored in the set M N V al . Mappings that are pruned are stored in the set M N V al . The nested loops in Line 4 in Algorithm 1 generate all the mappings C i ⊑ D j from the most general to the most specific mapping. Based on this, Proposition 3 shows that this algorithm maximizes the number of pruning.

M V al ← M V
When a mapping is generated and if it is not already pruned, it is firstly tested with regard to P i (m) ≥ S i in Line 7, then if it is positive, it is tested with P c (m) > S c in Line 8. In the case P i (m) < S i , all the implicants of m are marked as pruned (Line 14), thanks to the strong monotony property of P i . If P i (m) ≥ S i but P c (m) < S c , then the property of weak monotony conducts to prune all the implicants of m with the same left-hand side, in Line 11 and they are added to M N V al . Hence, M N V al set is kept up to date by containing all the pruning mappings from the beginning.

The general structure for the implementation of ProbaMap is pictured in Figure 4.

1. Computation of the transitive logical closure of the two taxonomies and their instances given as input. (in order to obtain quickly the class extensions and to optimize the pruning process) 2. Automatic classification step in order to merge the instances of the two taxonomies. This step has been detailed in section 3.4. It can be disabled by the user. 3. Core of ProbaMap: generation-and-test of candidate mapping, according to the two thresholds as input parameters.

The output is directly the set of mappings from the first taxonomy to the second one for which P u and P c both exceed their respective thresholds S u and S c . We insist on the fact that, once the parameters are set, the discovery process is fully automatic.

As many matching methods provide equivalences as their results, we can add a postprocessing for ProbaMap in order to obtain equivalences logically implied by the inclusion mappings discovered. In this case, the thresholds S u and S c should be lowered with respect to the discovery of pure implications, because equivalences are stronger relations than implicants, and then less likely to happen.

Experiments

We have performed three series of experiments :

1. on controlled synthetic data 2. on OAEI directory benchmark 3. on Web Directories, with a comparison with the method SBI [START_REF] Ichise | Integrating multiple internet directories by instance-based learning[END_REF] This section is structured according to these three series.

Experiments on synthetic data

For the purpose of systematic testing of our approach in various conditions, we have evaluated Algorithm 1 on synthetic data on which we can control important parameters and guarantee structural or distributional properties.

Different analysis have been conducted. We have measured the impact of the probabilistic models and of the thresholds involved in the validity criteria on the precision of the results and on the pruning ratio. The pruning ratio is the ratio of mappings that are pruned by adding in lines 14 and 11 Implicant(m) (or Implicant c (m)) to the set M N V al of unvalid mappings without estimating their probabilities.

We have also measured the qualitative and quantitative impact of the choice of a classifier. Automatic classification is at the core of the estimation of P u and P c with the computation of Ext(C i ∩ D j , O) (see Theorem 2). For evaluating the quality of our results, we use the standard criteria of precision and recall [START_REF] Van Rijsbergen | Information retrieval[END_REF]. Recall is the ratio of returned results that are expected w.r.t. all expected results. Precision is the ratio of returned results that are expected w.r.t. all returned results.

In order to measure the robustness we have tested the robustness of Algorithm 1 to noisy data.

Finally, we have conducted experiments on real-world data to check the scalability of the Algorithm 1 on large taxonomies and to make qualitative measurements.

We first describe the principles and the process of the data generator on which we have conducted the different experiments. Then we describe the experimental protocol that we have followed. Finally, we summarize the main experimental results that we have obtained on synthetic and real-world data.

Synthetic data generation is divided into three steps : generation of taxonomies with fixed sizes, generation of the expected mappings to discover, and population of each class by generating a fixed number of instances and associated description.

Generation of taxonomies. Given constraints on number of classes n 1 and n 2 , we generate the structure of the two respective taxonomies T 1 and T 2 as a forest of general trees (unconstrained in-degrees) by using a Boltzmann sampler for unlabelled trees described in [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF]. We use a reject method to get random forests with n 1 and n 2 nodes. This method is simple and efficient while guaranteeing an uniform distribution among the trees with the same number of nodes. Then, we label each node by a distinct class name.

In our experiments, we set n 1 = n 2 so the two taxonomies have the same size, which is the unique parameter of the taxonomies generation.

Mappings generation. We initialize the generation of mappings to be discovered M G with a set M S of seed mappings, whose size is either fixed or randomly chosen between 1 and the common size of the taxonomies.

Each mapping m ∈ M S is generated by a random choice for the two classes lhs(m) and rhs(m) in T 1 and T 2 , or in T 2 and T 1 , depending on the mapping direction which is randomly chosen too. We reject mappings which logically entail class inclusions that are not entailed within each taxonomy (i.e., we forbid generated mappings to modify the knowledge of each taxonomy).

The set M G of all mappings to discover will then be the set of mappings that can be logically entailed by M S and the two taxonomies.

Following [START_REF] Euzenat | Semantic precision and recall for ontology alignment evaluation[END_REF], the computation of precision and recall will be based on M G . Let R be the result of Algorithm 1. The recall is the proportion of mappings of M G actually returned by Algorithm 1:

Recall = M G ∩ R M G
The precision is the proportion of returned mappings that are actually in M G :

P recision = M G ∩ R R
Instances and description generation. For this step, we consider the two taxonomies and the mappings between them as a whole DAG of classes. The acyclicity of that graph is guaranteed by the constraints imposed in the production of the set M G of generated mappings described above. We first generate a set of boolean attributes sufficient to associate a minimal intentional description of each class respecting the semantic partial order conveyed by the above DAG structure. Then, we use this intentional knowledge to generate accordingly the description of the instances with which we populate each class in the taxonomies.

Generation of the intentional description of classes:

We traverse the DAG of classes according to a reverse topological order [START_REF] Cormen | Introduction to Algorithms[END_REF] starting from the most general classes that constitute the level 0, and we iterate the following process for generating the intention of classes as sets of attributes:

-For each class C 0 i of level 0, we generate a disjoint set of distinct attributes At 0 i and we set the intention of C 0 i , denoted Int(C 0 i ), to be A 0 i . -For each class C j i of level j (according to the reverse topogical order), we generate a set At j i of novel attributes (disjoint from the set of existing attributes) with a size fixed to the out degree of C j i in the DAG of classes, and we set Int(C j i ) to be At j i ∪ Int(C j-1 i k ), where the C j-1 i k are the successors of C j i in the DAG.

Population of classes:

Let {At 1 , . . . , At m } be the set of attributes generated at the previous step. We populate each class with n P instances, and we associate to them descriptions that respect the corresponding intentional description, as follows: For each class C, each of its instances is described by a boolean vector [a 1 , . . . , a m ] obtained by: -setting to 1 each a i such that the corresponding attribute At i is in the intention of the class C, -randomly setting the other values a j to 0 or 1. This way, by construction, all the instances in the extension of a class have in common that all the attributes in Int(C) are present in their description.

In Section 5.1 we will use an oracle classifier which classifies an instance i in the class C iff all the attributes of the intention Int(C) of the class C are present in the description of i.

The results of data generation can be summarized into a table T data with m + n C columns where m is the number of generated attributes and n C is the number of generated classes, and each tuple [a 1 , . . . a m , c 1 , . . . , c nc ] concatenates the description [a 1 , . . . a m ] of an instance in terms of attributes, and its categorization [c 1 , . . . , c nc ] with respect to the classes: for each i ∈ [1..n C ] c i is equal to 1 if i ∈ Ext(C) and to 0 if it is not the case.

Connection with Armstrong relations. Data generation in our context represents quite challenging issue when compared to other synthetic data generation, such as functional Armstrong relation for functional dependencies5 [START_REF] Beeri | On the structure of armstrong relations for functional dependencies[END_REF], or transactional databases for frequent itemsets [START_REF] Ramesh | Feasible itemset distributions in data mining: theory and application[END_REF].

Roughly speaking, we borrow the same principles than those developed for Armstrong relations [START_REF] Fagin | Horn clauses and database dependencies[END_REF]. Each generated mapping should be satisfied by the generated data, and each mapping that is not generated should be contradicted by the generated data.

With regard to the Armstrong relations, our generation tackles additional issues. Firstly, the structure may be generated whereas Armstrong relations suppose the structure (schemas) given. Secondly, for relational databases, it is enough to generates two tuples that contradict one dependency for ensuring that the dependency is not satisfied. In our case where mapping probabilities are estimated from statistics on class extensions, the amount of instances that contradict a mapping has a strong impact on its validity, then we can not only generate one instance for each mapping to be contradicted.

Experimental protocol

We first explain the goals of the successive experiments that we have performed.

For an overview of the complete setting, the connection between ProbaMap and the generator is pictured in Figure 5. Distinguishing between the parameters of ProbaMap (two thresholds for P c and P u and the kind of classifier) and thoses of the generator is a key point. The first goal is to analyze the impact on the precision of the thresholds S c , S u , with the purpose to fix appropriate thresholds for the next experiments.

The second goal is to analyze the impact of the probabilities P c and P u on the pruning ratio of the algorithm. The purpose is to determine among three validity criteria the one offering the best performances : using P u alone, using P c alone, or using both of them.

The third goal is to analyse and compare the impact both on precision/recall and on total running time of three real classifiers (Naive Bayes, C4.5 and SVM) for estimating the probabilities. The purpose is to determine the classifier offering the best tradeoff between quality of results and running time. Note that we do not take the learning time of classifiers into account because we consider that this task can be precomputed for each taxonomy.

The last goal with synthetic data is to analyse the robustness of the approach to noisy data.

For all the experiments on synthetic data presented in this section, each point is obtained by averaging the results of 100 runs. For each run, a new synthetic dataset is generated with the appropriate parameters. Note that in our experiments we generate taxonomies with few dozens of classes. The number of random taxonomies of such sizes can be counted in billions. Thus, averaging over 100 runs for a point does not prevent from local variations, leading to curves that are not smooth.

Our algorithm is written in Java and compiled using Sun Java version 1.6. We run all the tests on a quad-core Intel Q6700 Xeon at 2.66 GHz with 4 GB of memory. The OS is Ubuntu Linux 8.10. For all the experiments measuring run times, only one instance of our program and the OS are running on the machine, to avoid memory contention effects with other programs that would affect the results.

Experimental results Impact of thresholds on precision

We compare the influence of the thresholds S c and S u associated to probabilities P c and P u on the quality of the results returned by Algorithm 1. For doing so, we run the algorithm with the validity criterion: P c ≥ S c and P u ≥ S u .

In this experiment, the computation of probabilities is performed using the oracle classifier. The parameters in the synthetic generator are defined such that |M(T 1 , T 2 )| = 320. We set the number of seed mappings |M S | = 4. Note that by logical entailment the total number |M G | of mappings to be discover may be much greater. For each couple of threshold (S c , S u ) ∈ [0.78 : 0.995] 2 , we compute the precision and the recall of the results of Algorithm 1. We observed that the recall remains constant at 1.0 independently of values of S c and S u . This is because thanks to the oracle classifier, estimated probabilities for the mappings of M G are very close to 1, and superior to all experimented thresholds, leading to a perfect recall. Thus, we only show the results for precision in Figure 6.

The figure shows the contours of the different precision levels, from a precision of 0.93 to a precision of 0.99. From the shape of these contours, it is clear that both P c and P u have an influence on precision. As the relation P u ≥ P c holds (Proposition 2), under the diagonal P u has no influence on precision. The probability P c is more discriminant than P u . The figure shows that P c influences the precision for a large range of values of the threshold S c , while P u only has an influence for very high values of S u . We have observed the estimated probabilities for different mappings, and found that there is an important gap in the values of P c between valid and invalid mappings. This gap is much smaller for P u . P u giving higher probability values to invalid mappings, this explains why it can only have an influence on precision at very high S u values.

Based on the curve of Figure 3, we fix the thresholds at (S c = 0.83, S u = 0.96) for experiments where the classifier used to estimate the probabilities is the oracle. This gives a good precision of 0.95, and maps to a region where P u has an influence on the quality of results.

For the experiments in which a real classifier is used to estimate the probabilities, we fix the thresholds at (S c = 0.85, S u = 0.90) to be tolerant to classification errors.

Impact of probabilities on pruning ratio

We now study the impact of three probabilistic criteria for testing the validity of a mapping on the pruning ratio performed by Algorithm 1 :

1. using only P u by setting S c = 0 (bypass) 2. using only P c by setting S u = 0 (bypass) 3. using both P u and P c Figure 7 shows the ratio of pruning made by the algorithm using the different validity criteria, w.r.t. a naive approach not doing any pruning.

The validity computation using only P u is the one that prunes the least mappings, computing probabilities for about 40% of all mappings of M(T i , T j ). Both P c and P c and P u does more prunings and obtain a significant reduction of the search space. Combining P u and P c obtains slightly better results than using P c alone, so for the remainder of this experiments section, we use P c ≥ S c and P u ≥ S u as validity criterion. It allows to compute the probabilities for only 20% of the mappings of M(T i , T j ), when the number of candidate mappings is high. For example, a search space of 3500 mappings is pruned up to 22% by combining P c and P u , that implies that there are only 770 examinated mappings for which P u and P c are estimated.

Impact of the classifiers

In this subsection, we replace the oracle classifier with a real classifier. We compare the results given by three well-known classifiers: Naive Bayes [START_REF] Mitchell | Machine Learning[END_REF], C4.5 [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF] and SVM [START_REF] Flake | Efficient svm regression training with smo[END_REF]. We use the Weka implementation of these classifiers and have interfaced it with our code.

The comparisons of running times are shown in Figure 8 and in log scale in Figure 9.

A first conclusion is that the running times are polynomial in the number of mappings, and are very similar, with Naive Bayes being slightly slower than C4.5 and SVM.

Comparisons for precision and recall are shown in respectively Figure 10 and Figure 11.

Naive Bayes has both the worst recall and the worst precision, the choice is thus between C4.5 and SVM. They seem to have similar results. However, the learning time of SVM (not shown here) is much longer than the learning time of C4.5. We thus choose C4.5 for further experiments, and analyse the impact of the number of instances per class on the classification performance of Algorithm 1 with C4.5.

We vary the number of instances per class n P between 10 and 450. The results for computation time, precision and recall are shown in Figures 12,13 In this experiment, the number of classes and of mapping is constant, hence the number of classifications to perform is linear in the number of instances. The C4.5 algorithm takes linear time in the number of instances. In fact, all instances are classified into each class at the beginning of ProbaMap, this is also perfectly coherent. This linearity is also the case for Algorithm 1, as shown by Figure 9. Increasing the number of instances per class only increases slightly precision, whereas it strongly improves recall. The most important point to note is that excellent values of precision and recall are obtained with as few as 50 instances per class, as expected, with a use of Bayesian approach of statistics.

Robustness to noisy data

In order to test the robustness to noise of our algorithm, we define a new parameter θ corresponding to the quantity of noise to inject in the synthetic data. Each dataset produced by the synthetic data generator goes through a step of noise application, where each boolean corresponding to the value of an attribute for an instance can be reversed with a probability θ. The new dataset is then processed as usual by Algorithm 1.

The variations of precision and recall for values of θ ∈ [0; 0.3] are show in Figure 15. The figure shows that recall gracefully degrades when noise increases. At 10% noise, the recall is nearly unaffected, at a value of 0.95. Values of noise superior to 15% have a more significant impact and lead to poor recall. Precision, however, exhibits a different behavior. It first increases with noise, before abruptly decreasing for more than 24% of noise.

In order to understand this phenomenon, we have investigated in details the classifier results and the values of probabilities given to mappings. We found that for 0% noise, there are invalid mappings that are incorrectly given too high probabilities, and that appear as valid. This explains the non-perfect 0.88 precision value. The probability values for these mappings are close to the threshold. Increasing noise makes the classifiers more selective, and tends to decrease the values of all probabilities. So the probabilities of these invalid mappings go below the threshold for a moderate amount of noise, whereas the probabilities of valid mappings remain above the threshold. Thus the precision increases.

Real-world OAEI data

We have made experiments on the directory set of OAEI [START_REF] Euzenat | Ontology alignment evaluation initiative[END_REF][START_REF] Euzenat | Results of the ontology alignment evaluation initiative[END_REF] contest. This set is constituted by two large taxonomies of respectively 2857 and 6628 classes. For the contest, due to scalability issues, the taxonomies are split into the set of their branches, a small subset of which is given to the competitors for mapping alignment. In contrast, our algorithm is able to handle the two whole taxonomies, thus taking advantage of the complete structure of the taxonomies. It is important to note that without pruning, this would lead to a search space of 30 million mappings.

For compensating the absence of available instances for these taxonomies, we use a method inspired by [START_REF] Serafini | An algorithm for matching contextualized schemas via SAT[END_REF] to automatically populate the classes with synsets6 . We follow a similar method to Ctx-Match [START_REF] Serafini | An algorithm for matching contextualized schemas via SAT[END_REF]. Intuitively, the principle of this population is based on associating each class C with a set of WordNet synsets (atomistic semantic unit in this thesaurus) that reflect the right meaning of the label of C in the context where it appears, i.e. the labels of the ancestor classes of C in its taxonomy. This help to disambiguate the meaning of a word: for instance, the label "Arizona" can correspond to a state of the U.S.A. or to a snake. If the Arizona class is a child class of "Animals", the label "Animals" can be used to guess that "Arizona" means the snake species.

On the two whole taxonomies, the population phase produces about 30000 instances and takes 5 hours while the mapping discovery algorithm itself only takes 11 minutes. These are very reasonable computational times for handling 30 million possible mappings.

For evaluating the precision of the set of mappings discovered by our algorithm, we could only compute a lower bound based on the partial reference provided by OAEI. The results are promising, as for the thresholds S u and S c respectively set to 0.9 and 0.8 we obtained a lower bound of precision of 67%7 .

Comparative analysis on collected Web Directories

In this section, we test ProbaMap on part of Internet directories from Yahoo! and Google (actually based on Dmoz) that are rooted with similar or very close label. These sub-directories are considered as taxonomies, and URLs referenced inside each class of the taxonomy as instances.

The main difference with the sequence of experiments in the previous section is that the dataset contains original instances that are collected with their taxonomies, avoiding to process an artificial population.

We compare our approach to the SBI algorithm of Ichise et al. [START_REF] Ichise | Integrating multiple internet directories by instance-based learning[END_REF][START_REF] Ichise | Discovering relationships among catalogs[END_REF], which is dedicated to the discovery of mappings between Internet directories, and the integration of such directories.

Internet directories are trees of categories, which can be seen as taxonomies, categories being the classes. Each category contains a set of links (i.e. URLs to web sites), which can be seen as the instances of the class. Each link comes with a small text summary, whose words can be seen as instance attributes for classification.

Our datasets are corresponding locations in the Yahoo! and Google directories, that have also been used in the experiments of [START_REF] Ichise | Integrating multiple internet directories by instance-based learning[END_REF][START_REF] Ichise | Discovering relationships among catalogs[END_REF]: The data from the directories was collected in June 2010, so is different from the data of [START_REF] Ichise | Discovering relationships among catalogs[END_REF] and [START_REF] Ichise | Integrating multiple internet directories by instance-based learning[END_REF] which was collected in Fall 2001. Table 1 shows for each dataset the number of classes and instances in each class, and the number of instances shared between the Yahoo! and the Google directories. Two instances are considered shared if they correspond to the same URL in both directories. For a fair comparison, we have implemented both ProbaMap and the SBI algorithm in Java. Experimental protocol An overview of the setting used for the comparative experiment is pictured in Figure 16. The complete process is the following: In this way we obtain an unique rule C 1 → C 2 for each class of T 1 , like the SBI system.

-
As there are a good proportion of shared instances for each directory that makes the classification step not mandatory, we can and we will compare SBI against both ProbaMap versions with and without the classification step. For the version without classification, preliminary tests lead to set S c = 0.6 and S u = 0.9. SVM is set to be the default classifier by using the SMO implementation in weka. When using classification, because of the small values of the joint probabilities of classes, we set S u = S c = 0. In this case, the postprocessing step is modified to take into account the probabilities P c and P u of the reverse mappings.

Comparative qualitative evaluation The goal of our experiments is to compare the quality of Internet directories alignment for ProbaMap and SBI.

For the discovery of mappings, ProbaMap and SBI receive a "training" set of instances which is a subset of the shared and annotated instances. The test set used for evaluation of the discovered mappings is constituted by the remaining instances among the shared ones. In the case where ProbaMap is set to use classification, the training set is extended with all the non shared instances. The ratio of the number of shared instances used for training among all shared instances is a controlled variable on the experiments we have conducted.

The classification is performed using the SVM implementation SMO [START_REF] Flake | Efficient svm regression training with smo[END_REF] in Weka [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF], where the classification attributes for an instance are the words of its summary. The experiments on controlled data have shown that SVM and C4.5 are comparable in quality but that C4.5 is faster than SVM. Nevertheless, we have conducted this experiment with SVM which is expected to perform better on sparse data.

The evaluation is done by using the test set of instances. Each instance of this set belongs to a class C s of the source taxonomy. Hence, we can compare:

the class C predicted t of the instance, predicted by the output rule C s → C predicted t the class C t in which the instance is declared in the target taxonomy (each instance of the test set is common to the two taxonomies)

The accuracy measures the ratio of the instances in the test set for which

C predicted t = C t .
Accuracy is a standard micro-averaged evaluation measure which is based on instances, whereas recision and recall are macro-averaged measures based on mappings themselves. As there is no reference of mappings provided for the considered Yahoo! and Google subdirectories, but a sufficient proportion of instances are shared by them, we use the accuracy criterion to evaluate ProbaMap in this experiment. This enables also to fit the evaluation framework of SBI (described in [START_REF] Ichise | Discovering relationships among catalogs[END_REF]). without classification. The average is computed on the four directories of the Table 1 and for each direction of alignment.

In particular, ProbaMap with classification significantly outperforms ProbaMap without Classification (about 10% better) and SBI (about 20% better) for the datasets Autos and Photography, whatever the size of the training set.

For the directories Software and Outdoors, ProbaMap without classification and SBI both provide lower results. SBI performs a little better (no more than 5%). In these two cases, there are initially few instances by class, and then the classification step allows to improve the results : ProbaMap with classification outperforms SBI on the Software directory up to 60% of instances for the training set, whereas ProbaMap without classification does not. For the Outdoors results pictured in Figure 18(a), ProbaMap with classification is better for a small training set (≤ 20% of the shared instances). The reason is that, for this particular dataset, a very small ratio of instances is classified and then the extensions of classes do not change much after the classification step.

We have also checked that all these results both for ProbaMap and ProbaMap with classififcation are rougly better in average than the results of a modified version of SBI using Naive Bayes classification so-called SBI-NB [START_REF] Ichise | Discovering relationships among catalogs[END_REF]. More precisely, both versions of Probamap perform better for 6 of the 8 tested directories. Note however that we are provided results for SBI-NB with an old dataset collected in 2004, so the comparison is not totally fair.

Finally, SBI and ProbaMap (without classification) both take a few seconds on each of the directories of Figure 1). The version of ProbaMap with classification requires additionnal time (several minutes) for classifying each instance into each class, but this significantly improves the quality of the results.

These experiments show that the mapping discovery method that we propose gives good results on real-world datasets, and can take advantage of classification techniques to compensate small training set sizes. This is an important quality for real world taxonomies built by different people, that are unlikely to have many instances in common.

Related work and conclusion

As outlined in the introduction, semantic mappings are the glue for data integration systems. A wide range of methods of schema/ontology matching have been developed both in the database and the semantic web communities [START_REF] Euzenat | Ontology matching[END_REF]. One of the principles widely exploited is terminological comparison of the labels of classes with string-based similarities or lexicon-based similarities (like Word-Net) (e.g., TaxoMap [START_REF] Hamdi | TaxoMap in the OAEI 2008 alignment contest[END_REF], H-MATCH [START_REF] Castano | H-match: an algorithm for dynamically matching ontologies in peer-based systems[END_REF]) . Another widely used principle is structure comparison between labeled graphs representing ontologies (e.g., OLA [START_REF] Euzenat | Similarity-based ontology alignment in owl-lite[END_REF]), based on similarity flooding [START_REF] Melnik | Similarity flooding: A versatile graph matching algorithm and its application to schema matching[END_REF]. The underlying idea is that two elements of two distinct ontologies are similar when their adjacent elements are similar. This is applied by spreading similarities in the spirit of how IP packets flood the network in broadcast communication.

A category of methods (e.g., FCA-merge [START_REF] Stumme | FCA-MERGE: Bottom-Up Merging of Ontologies[END_REF], [START_REF] David | An interactive, asymmetric and extensional method for matching conceptual hierarchies[END_REF]) are called "extensional" because they are instance-based: they rely on instances of classes to compute matches between them. It is shown in [START_REF] Isaac | An empirical study of instancebased ontology matching[END_REF] that the reliability of instance-based methods depends on the applications and on the kind of correspondences that are considered. The instance-based method SBI [START_REF] Ichise | Integrating multiple internet directories by instance-based learning[END_REF] with which we have compared our method is based on the computation of the Fleiss Kappa coefficients that are symmetric and then they cannot be interpreted as probabilities on inclusion mappings.

Most of the instance-based methods make use of classifiers using a corpus of labelled instances (e.g., LSD [START_REF] Doan | Learning mappings between data schemas[END_REF], SemInt [START_REF] Li | Semint: a tool for identifying attribute correspondences in heterogeneous databases using neural networks[END_REF], GLUE [START_REF] Doan | Learning to map between ontologies on the semantic web[END_REF], [START_REF] Nottelmann | Information retrieval and machine learning for probabilistic schema matching[END_REF]). It should be pointed out that GLUE discovers symmetric correspondences that have no formal semantics. The associated confidence value for each discovered correspondence are not real probabilities as they are based on similarities like the Jaccard similarity. In contrast, we consider mappings that denote inclusions between classes of different taxonomies, and we define a formal probabilistic semantics for these inclusion mappings.

sPLmap [START_REF] Nottelmann | Information retrieval and machine learning for probabilistic schema matching[END_REF] is an approach for schema matching, and oPLmap [START_REF] Nottelmann | A probabilistic, logic-based framework for automated web director alignment[END_REF] is a variant for ontology matching, that rely on classifiers and deal with probabilities. sPLMap finds the best set of mappings M between two schemas S, T that maximizes the probability that the tuples in the rewritten schema S using M (denoted S M ) are plausible in T and vice versa. At the end, each returned mapping is associated with a probability based on the conditional probability formula. In contrast with our work, sPLmap computes probabilities by combining scores provided by several weighted classifiers (working on text or data values of tuples).

Other approaches have been investigated with machine learning techniques using a corpus of schema matches (e.g., [START_REF] Madhavan | Corpus-based schema matching[END_REF], [START_REF] Wang | Learning concept mappings from instance similarity[END_REF]). The work introduced in [START_REF] Wang | Learning concept mappings from instance similarity[END_REF] uses classifiers directly on correspondences, by representing each correspondence in a vector space constructed from instances features. A training set of true correspondences should be provided. Then, for a tested correspondence between two classes A and B, the similarities between (i) the instances of A, (ii) the instances of B, and (iii) the instances of all examples correspondences allow to give to the tested correspondence a position in the correspondence space. Hence the classifier can be used to determine if the tested correspondence is relevant or not, according to its position in the correspondence space and the learned examples.

In fact, most of the existing matchers combine these elementary approaches in different ways (e.g., COMA++ [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF] and COMA [START_REF] Do | Coma -a system for flexible combination of schema matching approaches[END_REF], Cupid [START_REF] Madhavan | Generic schema matching with cupid[END_REF], H-MATCH [START_REF] Castano | H-match: an algorithm for dynamically matching ontologies in peer-based systems[END_REF], Lily [START_REF] Wang | Lily: Ontology alignment results for OAEI[END_REF], S-Match [START_REF] Giunchiglia | S-match: an algorithm and an implementation of semantic matching[END_REF], Clio [START_REF] Chiticariu | Semi-automatic schema integration in clio[END_REF]).

In [START_REF] Gal | Managing uncertainty in schema matching with top-k schema mappings[END_REF], an extension of existing matching methods is proposed by considering the k ranked best alignments. The top-k alignment ranking is combined with the schema to match in order to generate the final alignment that globally maximizes its score.

It is standard practice for ontology and schema matchers to associate numbers with the candidate mappings they propose. The uncertainty is intrinsic to correspondences discovery because two classes or properties (for example) independently created are unlikely to exactly match. As stated in [START_REF] Shvaiko | Ten challenges for ontology matching[END_REF], there is still a need to better understand the foundations of modeling uncertainty that is primary important for improving the detection of correspondences causing inconsistencies, e.g., via probabilistic reasoning, or to identify where the user feedback is maximally useful, and for improving the quality of the interpretation of correspondences.

However, those uncertainty coefficients do not have a probabilistic meaning and are just used for ranking. In contrast, our approach promotes a probabilistic semantics for mappings and provides a method to compute mapping probabilities based on the descriptions of instances categorized in each ontology. It is important to note that even if we use similar classification techniques as [START_REF] Doan | Learning to map between ontologies on the semantic web[END_REF], we use them for computing true probabilities and not similarity coefficients.

The most distinguishing feature of our approach is that it bridges the gap between logic and probabilities by providing probabilistic models that are consistent with the logical semantics underlying ontology languages. Therefore, our approach generalizes existing works based on algebraic or logical representation of mappings as a basis for reasoning (e.g., Ctx-Match [START_REF] Serafini | An algorithm for matching contextualized schemas via SAT[END_REF], Clio [START_REF] Chiticariu | Semi-automatic schema integration in clio[END_REF]). The work in [START_REF] Gal | A framework for modeling and evaluating automatic semantic reconciliation[END_REF] introduces a framework for modeling and evaluating automatic semantic reconciliation. It provides a formal model for semantic reconciliation and theoretically analyses the factors that impact the effectiveness of matching algorithms. The proposed formal model borrows from fuzzy set theory for handling uncertainty by combinations of similarity measures and good properties. This work is not connected probability but is complementary to the approach in this thesis.

The mappings that are returned by our algorithm can be exploited for mapping validation by probabilistic reasoning in the line of what is proposed in [START_REF] Castano | Mapping validation by probabilistic reasoning[END_REF]. More generally, our approach is complementary of the recent work that has been flourishing on probabilistic databases [START_REF] Benjelloun | Uldbs: Databases with uncertainty and lineage[END_REF][START_REF] Dalvi | Answering queries from statistics and probabilistic views[END_REF]. In particular, it fits into the general framework set in [START_REF] Dong | Data integration with uncertainty[END_REF] for handling uncertainty in data integration, for which it provides an effective way for computing mapping probabilities. ProbaMap can be generalized to perform without instances at all, by using techniques that lead to correctly estimate P (A 1 ) and P (A 1 ∩ B 2 ) (for a mapping A 1 ⊑ B 2 ). Such a generalization should take care that the distributions of A and of A ∩ B are considered and estimated in a probabilistic framework. For example, a linguistic resource can be used for estimating thoses probabilities by taking the labels of A and B and returning probabilities for A and A ∩ B, not only coefficients. This requires that the techniques to obtain such probabilities from the linguistic resource should respect some properties that fit with the probability theory.

The experiments that we have conducted on both real-world and controlled synthetic data have shown the feasibility and the scalability of our approach. In contrast with our approach that prunes the search space by an appropriate ordering for generating and testing the mappings, a lot of existing approaches compute a similarity matrix for all pairs of classes. The ordering used in SBI is not logically consistent. Several complex matching system use the logical consis-tency as a filter or a way to check their results, but not for pruning the search space. Up to now, the OAEI context does not focus on scalability, except for isolate cases like the anatomy 20068 dataset which contains large ontologies in the anatomy domain. Methods like PRIOR [START_REF] Mao | PRIOR system: Results for OAEI[END_REF] and H-MATCH [START_REF] Castano | Results of the HMatch ontology matchmaker in OAEI[END_REF] has shown good performances on this dataset. The PRIOR system makes use of information retrieval techniques, by indexing a profile for each class (or any ontology entity), and by using a query answering algorithm to rank and find the best matches for a particular class by making a query about its own profile. Note that the anatomy dataset does not contain any instance.

Another possible approach investigated in [START_REF] Hamdi | Alignment-based Partitioning of Large-scale Ontologies[END_REF] for handling large taxonomies is based on partitioning. Our approach is scalable while keeping the whole logical structure, which can be potentially lost by partitioning taxonomies.

Perspectives

We envision two main perspectives. First, we will study a setting for probabilistic query answering, in the spirit of probabilistic databases [START_REF] Dong | Data integration with uncertainty[END_REF]. In such a setting, probabilities of mappings will be used by the query answering algorithm to give some probability values for each answer. In particular, it should be interesting to focus on reasoning-based query algorithm like in the Somewhere [START_REF] Adjiman | Distributed reasoning in a peer-to-peer setting: Application to the semantic web[END_REF] setting. There are existing works on introducing probabilities in logic and inference process. Probability Logic [START_REF] Adams | A Primer of Probability logic[END_REF] fits our proposed model in the way that the classical implication and the conditional are both present in the language. Probabilistic description logics ( [START_REF] Koller | P-CLASSIC: a tractable probablistic description logic[END_REF], [START_REF] Castano | Mapping validation by probabilistic reasoning[END_REF]) are also based on conditional formulas too. Based on inference rules and their properties about probabilities, such probabilistic and logical framework can be extended to do probabilistic reasoning involving probabilistic mappings.

Our second pespective tackles the central issue in ontology matching (see [START_REF] Shvaiko | Ten challenges for ontology matching[END_REF]), that is to provide a formal semantics to coefficients returned as output of existing alignment methods. The idea is to design and implement a post-processing step in order to transform the returned coefficients into coefficients that can be interpreted as probabilities, i.e. that respect the property of monotony (Theorem 1). For this purpose, we plan to use the similarity flooding principle [START_REF] Melnik | Similarity flooding: A versatile graph matching algorithm and its application to schema matching[END_REF], in the spirit of N2R [START_REF] Saïs | Combining a logical and a numerical method for data reconciliation[END_REF] and OLA [START_REF] Euzenat | Similarity-based ontology alignment in owl-lite[END_REF]. Coefficients for mappings are initialized by those returned by the existing method to postprocess. The properties of monotony are then translated into strong influences between coefficients of mappings connected by an entailment relation. These influences between mappings coefficients are finally modeled by (non-linear) equations involving the maximum function. Like in N2R, the main issue would be to find an iterative algorithm ensured to converge towards a fixpoint that is the solution of the equation system.

Fig. 1 .

 1 Fig. 1. 2 Taxonomies and associated instances

  (a) Sample directory from Yahoo! (b) Sample directory from Google

Fig. 2 .

 2 Fig. 2. Top levels of Yahoo! and Google directories

  every membership statement C(a) of T : a I ∈ C I . An inclusion G ⊑ H is inferred by a taxonomy T (denoted by T |= G ⊑ H) iff in every model I of T , G I ⊆ H I . A membership C(e) is inferred by T (denoted by T |= C(e)) iff in every model I of T , e I ∈ C I .

Proposition 1 .Fig. 3 .

 13 Fig. 3. 2 mappings between T1 and T2

Algorithm 1

 1 ProbaMap Require: Taxonomies (DAG) Ti, Tj , thresholds Sc, Si, Instances maps exti, extj Ensure: return {m ∈ M(Ti, Tj ) such that Pi(m) ≥ Si and Pc(m) ≥ Sc} 1: M V al ← ∅ 2: M NV al ← ∅ 3: for all Ci ∈ ReverseTopo(Ti) do 4: for all Dj ∈ Topo(Tj ) do 5: let m = Ci ⊑ Dj 6:

Fig. 4 .

 4 Fig. 4. Structure of ProbaMap

Fig. 5 .

 5 Fig. 5. Structure of ProbaMap

Fig. 7 .

 7 Fig. 7. Pruning factor for validity computation with Pc, Pu and Pc and Pu

Fig. 8 . 5 SVMFig. 9 .Fig. 10 . 5 SVMFig. 11 .

 85910511 Fig. 8. Computation time (s) for different classifiers

Fig. 13 .

 13 Fig. 12. C4.5 -Computation time (s) -impact of number of inst/class

Fig. 15 .

 15 Fig. 15. C4.5 -Precision and recall -impact of noise level

  Yahoo! : Recreation / Automotive & Google : Recreation / Autos -Yahoo! : Recreation / Outdoors & Google : Recreation / Outdoors -Yahoo! : Computers and Internet/Software & Google : Computers/Software -Yahoo! : Arts / Visual Arts / Photography & Google : Arts / Photography

Fig. 16 .

 16 Fig. 16. Setting used for the comparative experiment between SBI and ProbaMap

Table 1 .

 1 Statistics on data collected from subdirectories on Yahoo! and Google

		Yahoo!	Google	shared
		classes instances classes instances	instances
	Autos	947	4406	967	6425	837
	Outdoors	2428	5511	1441	13863	623
	Software	323	2390	2395	30140	572
	Photography	168	1851	321	3852	286

  1. Application of ProbaMap on T 1 and T 2 2. For each class C 1 of T 1 , among all C 2 for which the two mappings C 1 ⊑ C 2 and C 2 ⊑ C 1 have been discovered, select the class C 2 for which min( P c (C 1 ⊑ C 2 ), P c (C 2 ⊑ C 1 )) has the highest value. 3. For each class C 1 of T 1 , if there is no rule for C 1 , associate to C 1 the rule of its closest ancestor in T 1

Table 2 .

 2 Averaged accuracy for SBI and ProbaMapResultsThe averaged results in Table2show that ProbaMap outperforms SBI in average, and that ProbaMap with classification outperforms ProbaMap

	Ratio of shared instances provided for training	SBI ProbaMap ProbaMap + classif
	0.5	0.23	0.28	0.36
	0.9	0.29	0.33	0.40

dir.yahoo.com

dir.google.com

An Armstrong relation for a set of functional dependencies is a relation that satisfies each dependency implied by the set and does not satisfy any dependency that is not implied by it.

In WordNet, a synset is a semantic unit, 2 synonyms correspond to the same synset.

Fore more details, see http://disi.unitn.it/~pane/OAEI/2009/directory/result/

http://oaei.ontologymatching.org/2006/anatomy/