Corentin Boidot
email: boidot@enib.fr

Olivier Augereau
email: augereau@enib.fr

Pierre De Loor
email: deloor@enib.fr

Riwal Lefort
email: riwal.lefort@arkea.com

Benefits of using multiple post-hoc explanations for Machine Learning

EXplainable AI (XAI) offers a wide range of algorithmic solutions to the problem of AI's opacity, but ensuring of their usefulness remains a challenge. In this study, we propose an multi-explanation XAI system using surrogate rules, LIME and nearest neighbor on a random forest. Through an experiment in an e-sports prediction task, we demonstrate the feasibility and measure the usefulness of working with multiple forms of explanation. Considering users' preferences, we offer new perspectives for XAI design and evaluation, highlighting the concept of data difficulty and of the idea of prior agreement between users and AI.

I. INTRODUCTION

A. Research context

As AI algorithms continue to permeate various aspects of our lives, the need for transparency and comprehensibility in AI decision-making processes has become increasingly imperative. EXplainable AI (XAI) offers multiple algorithms and approaches to compensate for AI's opacity, such as surrogate models, feature importances (FIs), or example-based explanations [START_REF] Jin | EUCA: A Practical Prototyping Framework towards End-User-Centered Explainable Artificial Intelligence[END_REF]. With numerous libraries and tutorials, an engineer can now easily make an AI "explainable". However, is this new system useful for its users? A lot of evaluations do not even take users into consideration [START_REF] Doshi-Velez | Towards a rigorous science of interpretable machine learning[END_REF], and most of the time, evaluations are done by comparing only different explanations of the same kind: a FI with other FIs [START_REF] Jesus | How can I choose an explainer? An Application-grounded Evaluation of Post-hoc Explanations[END_REF], surrogate rules with other rules [START_REF] Lage | Human evaluation of models built for interpretability[END_REF], etc. Nevertheless, applicationgrounded evaluation can perfectly help to develop benchmarks on diverse forms of explanations [START_REF] Hase | Evaluating Explainable AI: Which Algorithmic Explanations Help Users Predict Model Behavior?[END_REF]. Yet, as the domain is evolving quickly and lacks a unified theoretical framework, the development of benchmarks, evaluations and comparisons of automated explanations seems still hindered. In this study, explainability is considered in a post-hoc scenario where an AI decision is viewed as a recommendation in a decision task including a human in the loop. Inspired by empirical approaches for XAI evaluations [START_REF] Bansal | Does the whole exceed its parts? the effect of ai explanations on complementary team performance[END_REF]- [START_REF] Baudel | ObjectivAIze: Measuring Performance and Biases in Augmented Business Decision Systems[END_REF], we designed an experiment to perform simultaneous evaluations of explanations with varied forms at once with few users, from both task-performance and technology acceptance perspectives. We developed a protocol and an interactive environment, meant to evaluate human-AI interaction on a binary classification task, and evaluate it on a winner prediction task on League of Legends (LoL) games data. The effects of four explanations are compared by means of decision time, subjective feedback and use rates. We also take into account the interactions between explanations, and the adaptation to diverse users and data. Experiment's process for different participants. The red blocks represents predictions series with available AI and explanation, while gray blocks represents series under control condition. During the training, the order of games to predict is randomized. During the evaluation, the order of games is fixed, but their number may vary depending on participants' will.

Our research explores notions of individual preferences and highlights the importance of measuring agreement between experts and AI before any interaction, and the key role of perceived difficulty in explanations' usefulness. In the first part, we will introduce the context of this work, in the second part we will describe the decision system we developed, then we will introduce our experiment's methodology. The fourth part presents our results, and the fifth part will open the discussion about XAI evaluation.

B. Related works

Among all possible way of evaluating explainability [START_REF] Doshi-Velez | Towards a rigorous science of interpretable machine learning[END_REF], [START_REF] Mohseni | A multidisciplinary survey and framework for design and evaluation of explainable AI systems[END_REF], [START_REF] Hoffman | Metrics for Explainable AI: Challenges and Prospects[END_REF], our work is in line with Doshi-Velez and Kim's definition of application-grounded evaluation. We excluded the "proxy-task" approach (ie: human-grouned evaluation) as it uninformative regarding direct performance [START_REF] Buc ¸inca | Proxy tasks and subjective measures can be misleading in evaluating explainable ai systems[END_REF]. In a binary decision problem, task performance is usually measured by accuracy, and the standard research objective is to improve this accuracy through explanations. Some approaches go further and also consider decision time [START_REF] Jesus | How can I choose an explainer? An Application-grounded Evaluation of Post-hoc Explanations[END_REF], [START_REF] Lage | Human evaluation of models built for interpretability[END_REF], [START_REF] Gedikli | How should I explain? A comparison of different explanation types for recommender systems[END_REF]: as a good explanation is asked to be easy to use, the decision should be made faster. Jesus' and Amarasinghe's studies [START_REF] Jesus | How can I choose an explainer? An Application-grounded Evaluation of Post-hoc Explanations[END_REF], [START_REF] Amarasinghe | On the Importance of Application-Grounded Experimental Design for Evaluating Explainable ML Methods[END_REF] reveal a limit of empirical approach using few experts (three fraud detection experts), as their decision times are very different, on data alone but also when reading different explanations. They used in-subject comparative evaluations of several FIs, and two baselines: decision made without AI, and with confidence score only. Bansal et al. [START_REF] Bansal | Does the whole exceed its parts? the effect of ai explanations on complementary team performance[END_REF] suggest that it may be too easy to improve on human accuracy by using AI that is significantly better in terms of precision. They show that in the literature, accuracy of the human-AI team has never really progressed by the means of explanations. They carry between-subject studies on three text-based tasks (two binary sentiment classifications and a question answering task), obtaining cooperative results on accuracy metrics. However, the confidence score alone produced cooperative performance comparable to their best explanations. Baudel et al. [START_REF] Baudel | ObjectivAIze: Measuring Performance and Biases in Augmented Business Decision Systems[END_REF] also achieved such cooperative performance on a prediction task based on the Titanic dataset, by using only the AI's recommendation. However, when using an AI with higher accuracy, the cooperative performance disappeared, suggesting that there is always a performance threshold where human-in-the-loop decision making becomes detrimental in terms of efficiency. In a context where AI is more powerful than humans, explanation can follow a teaching purpose. For our experiment however, we adopt to a cooperative point of view.

II. EVALUATED SYSTEM

We designed a task environment for human-AI collaboration that would be suited to compare different explanations methods. To this end, we chose an e-sport prediction as an application domain, with a tabular dataset from League of Legends, on which we trained a Random Forest model. We developed a decision interface enabling users to make predictions on games, with AI assistance (and without it), and implemented four explanations (including the confidence score) 1 .

A. Task, Data and Model

Tasks from medicine or finance are crucial in XAI, but building a pool of participants with the relevant knowledge is indeed a limiting factor. We looked for a task with analogies to fraud detection, so that comparison could be done with these works; we chose e-sport prediction because students can be relevant "experts", thus enabling a better reproducibility. Both are binary classification tasks on tabular data, using statistical data which require specific domain knowledge to be clearly understood. We chose League of Legends (LoL) winner prediction, a popular online game. This game consists of two teams (red and blue) of five players fighting for the control of the opposing camp. The players' characters may gain experience, gold, kill the enemies, destroy enemy facilities, etc., and most players observe these statistics at the end of a game. Using such statistics at 10 minutes of play, we have a binary prediction task on tabular data, with a level of difficulty adapted to observe both human errors and AI errors.

We chose a LoL dataset containing high-level statistics, collected from real high-ranked games, through the game's API. As the dataset contains redundant columns, we kept only 23 pertinent variables. Some of them, like the "gold" accumulated by each team, are known to be good predictors for the winner, but some victories would still surprise most players. We split our dataset with a 75-25% train-test ratio. Inside this We trained a Random Forest (RF), using the scikit-learn implementation with 200 trees on normalized data. Our model reaches an accuracy of 72% on the test set. We would not seek a better accuracy as it is nearly about human accuracy on this task (71%).

B. Decision interface

All the interface was developed in python using mostly streamlit library. A description of the interface is given in Figure 2. The right part of the screen is dedicated to AI (prediction and explanation) and is blank when not accessing the AI. The left part notably contains the button that will "activate" AI. We displayed the data in the middle, in two columns corresponding to the blue and red team, with the same statistics on each line. A third column contains our global means for these statistics, to give reference values, thus helping users to deal with task uncertainty [START_REF] Wang | Designing theory-driven user-centric explainable AI[END_REF]. The slider allows only to select blue or red victory. Time is recorded when the user clicks the validation button (left part of the screen).

When the AI is activated, a new button enables to select any of the four explanation modes, starting on a the default explanation display: confidence score.

Our four explanations were always referenced as 'A' for the confidence score, 'B' for the surrogate rule (skope-rules), 'C' for LIME and 'D' for the nearest neighbors. These explanations have different forms that may complement one another in order to justify AI's prediction, or to calibrate trust. They also have an increasing intended complexity (which matches their display size).

a) Confidence score: In this explanation we display the confidence score oriented towards the predicted class, so that the score is always higher than 50%. We did not try to calibrate those scores, because their distribution on our experimental data was already satisfying: few errors are done with extreme confidence, they rather accumulate near the 50% confidence score.

b) Skope-rules: We wanted a surrogate model that we could display textually, leading us to choose decision rules. We used skope-rules, an accessible solution that implements this kind of model [START_REF] Friedman | Predictive learning via rule ensembles[END_REF]. We trained two different surrogates in order to justify decisions: one surrogate trained on blue predictions of the RF model, the other on red predictions. This double surrogate solution was motivated by the fact that all learned rules or formulated towards a "positive class" to be detected, which does not fit our task where no team can be said to win a priori. Each of our trained models contained four rules and used only two features, as this configuration gave the best fidelity. Only the first activated rule is displayed to the user, with a conversion to natural language: ie. French. An example Fig. 2. Example of the interface after accessing AI, with explanation C (LIME). Part I. contains the navigation tools including a validation button, AI recommendation button and explanations' radio button once the previous one is pressed. Part II. contains the current game data, with a common column of reference values, and the slider which enables users to make predictions. When AI is accessed, Part III. display the AI's prediction (here: red team) with the selected explanation underneath. User are free to navigate between the four displays, and can confirm when they want.

of such a rule would be: "As blueTotalGold is lower than 17551 and redTotalExperience is higher than 17394, red team should probably win.". If the surrogate is incorrect regarding AI's prediction, we display: "No rule for this case". c) LIME: Since we used SHAP [START_REF] Lundberg | A unified approach to interpreting model predictions[END_REF] in an early experiment on the same task (tree-based interventional implementation [START_REF] Chen | True to the Model or True to the Data?[END_REF]), and it gave no performance gain, we chose the LIME algorithm [START_REF] Ribeiro | Why should i trust you?" Explaining the predictions of any classifier[END_REF]. This method has already obtained good task-based evaluation on other tasks [START_REF] Hase | Evaluating Explainable AI: Which Algorithmic Explanations Help Users Predict Model Behavior?[END_REF], [START_REF] Amarasinghe | On the Importance of Application-Grounded Experimental Design for Evaluating Explainable ML Methods[END_REF]. We used the implementation from the original authors without additional parameters, hiding discretizations' thresholds. We display these FI using a "waterfall plot", that we believe to be more intuitive, using the library shap (an example is visible in Fig. 2). This figure displays the six main FIs plus all the others summed together. Because of their approximations, those explanations could from the the probability displayed in explanation A; for instance if the probability is 55 percent towards the red team, LIME could indicate 45% towards the red team. However, these approximations may in fact help doubt the model when it is useful.

d) Nearest Neighbor+: We now require an examplebased explanation, coming after the confidence score, surrogate rules, and FIs. We preferred the nearest neighbors (NN) approach rather than prototypes or counterfactuals (CF) because they are simple to describe, compared to the complexity of communicating what a CF really is: data that does not exist [START_REF] Jin | EUCA: A Practical Prototyping Framework towards End-User-Centered Explainable Artificial Intelligence[END_REF]. We sampled a thousand examples from our test set in order to build this explanation. We draw the NN from this set, using the L1 distance with normalized features. We display the nearest neighbor in the same manner that we display the match to be analyzed. Because the NN alone would not be helpful enough, we decided to add contextual information in a text under the NN: which team won that match, the associated AI prediction, and how far is a NN with opposite label, measured by the number of neighbors needed to find it.

III. METHODOLOGY

This experiment is designed for a small number of participants, with limited availability (1 hour).With such constraints, each participant has to go through both a control condition and an experimental condition. We interleaved these conditions, so that all the data is processed by a maximum of participants from both conditions. This interleaving should not affect participants overall performance as they all go through a long training phase before (about 30 minutes). Thus our experimental process goes through four stages: presentation of the goals and setting, training on the prediction task, evaluation, and a final survey (see Fig. 1). The explanatory interface is evaluated as a whole, but conclusions can be drawn regarding the explanations used in the interface, thanks to the behavioral and subjective data collected. We assume that by granting the user freedom, we will reach better team performance and system acceptance.

a) Presentation of goals: The participant first receives instructions, with information about context, data, and the different explanations, qualified as "displays" for the AI recommendation, that needs justification. The task objective given to them was to take the better decision in the shortest time, so they can define their own balance between these two goals. It was insisted the users were free to use or not the AI, and encouraged to adapt their use to the game.

b) Training stage:

A training phase is necessary to get stable results during the evaluation, so we designed the following scheme. After each decision, the users are reminded of their total number of errors, and their decision time is also displayed after the tenth game. Every five games, the users could look back to their decisions, see the ground truth and every displays. We expect that with this feedback, participants could adapt towards both good decision times and accuracy. To prevent that the order of training data creates some bias in participants' perception of the system, we randomized the order of the game for each user. We also disabled the AI recommendations for games 16 to 20, so that users also experienced the control condition, and made decisions with data only. The experimenter had to keep track of time. We chose to keep a fixed number of games to analyze for training (25), and to have a variable number of evaluation games. After 20 evaluation games, the experimenter could change the number of remaining games, depending on time and user's convenience.

c) Evaluation stage: Only the predictions done during this evaluation stage are to be analyzed in our results part. As shown in Fig 1, the evaluation goes through two sequences of ten games, and to sequence of variable length, alternating between control and experience conditions. The control condition simply consisted in removing the button that gives access to the AI. The protocol collects behavioral data on decision making, but also multiple subjective feedbacks from the user. After each decision, the participants were asked if they were confident in their decision and if the game was difficult to judge (7-point likert-scales). When the participants had access to the AI interface, they were also asked if they found each of the displays useful (binary answers). d) Questionnaire: We intended to control both perceived use (PU) and perceived ease of use (PEOU) [START_REF] Davis | Perceived usefulness, perceived ease of use, and user acceptance of information technology[END_REF] of our system. As the PU of our explanations are already evaluated thoroughly in evaluation phase, we mostly investigate the PEOU by adapting CSUQ questionnaire [START_REF] Lewis | IBM computer usability satisfaction questionnaires: psychometric evaluation and instructions for use[END_REF], on both the decision system (considering control condition) and the AI interface. All these questions used 7-point Likert scales, and we take the mean of results (using a scale from -3 to 3). We also asked how interpretable were the explanations.

We recorded information about students' backgrounds at the end of the experiment, to check their degree of expertise. We also recorded information about participants' sociological profile, and especially about their knowledge in AI, as it could be an important factor in AI's perception [START_REF] Ehsan | The Who in Explainable AI: How AI Background Shapes Perceptions of AI Explanations[END_REF].

A. Who are our participants?

The experiment took place inside our laboratory, and inside an office associated with our work. We recruited 27 participants, mostly through internal channels (collective mails or chat). We recruited among students and young engineers, some of them had a background in data science: most of them had at least a license degree in informatics. The main prerequisites for participation were knowledge of League of Legends (a minimum of having played a few games). Regarding the expertise on LoL, 12 participants out of 27 had reported that they do not play ranked games, and 9 participants reported they did not care about the meta-game (ie: the strategic discussions surrounding the game and its updates). This "low implication" with the game did not resolve into lower performances, as the level of analysis required here is rather abstract, so we did not add any filters a posteriori to reduce this diversity of profiles. The age of the participants ranges from 19 to 37 y.o.; 96% of participants were males. All of them were able to correctly use the AI interface: we measured a mean PEOU of 1.83 (with Likert scales going from -3 to 3) for the control condition, and 1.0 for the PEOU of the AI itself (worst cases: respectively 0.14 and -0.6). The majority of our participants used the AI assistance during the evaluation: 2 of them did not use it at all, and 2 others would use it only once and twice.

IV. RESULTS

A. Explanations' comparison

In order to compare an explanation's effect in an open system, we must observe its regular users. For each of our four explanations, we consider a participant that used it more than once as a "user of the explanation". For each explanation, the use rate could vary a lot: only explanation A (confidence score) was guaranteed to be seen by any participant who wants to access the AI (thus leading to the highest use rate). Comparative results are reported in Table I. Usefulness is the mean percentage of positive PU answers to post-decision forms; along with use rate and time per use, it is computed only on the users of the explanation, while interpretability (asked in the exit survey) is a mean from all participants' answers. We see that LIME is perceived as more useful than the confidence score -and NN+ find similar success. It is to be noted that only the confidence is universally perceived as interpretable. The less efficient explanations tested are our surrogate rules (B): only a few participants occasionally use them, and use, with a low perceived utility.

The recorded times per use meet our expectations for the explanations different designs: confidence score (A) is quick and easy to read, followed by skope-rules (B), LIME (C) and finally NN+ (D) as it adds a second table to read. The overall agreement between PU, interpretability and the use rates of B, C and D matches what is expected of rational users.

B. Behaviors with multiple explanations

For each game, we classify a user's decision into 9 possible strategies: no explanation (referred as 'No'), confidence score alone ('A') and all possible combinations of A and the other displays. Participants had diverse behaviors, and only strategies using B can be seen as marginal (see Fig. 3). Fig. 3. We recorded the decision path of all predictions under experimental condition. The numbers refers to the numbers of decisions relying on the interface state, all decisions starting with the "no AI" state. The right end of the chart figures the proportions of the nine strategies using explanations or not.

These behaviors can be analyse in the light of participants' characteristics or data characteristics. Links with data will be analyzed in Section IV-C. On average, more than 85% of a participant's usage is accounted for by the "No" strategy (default option) and his two favorite combinations of explanations. This confirms that each participant had preferences rather than a random behavior. Specifically, three users chose a pure strategy (ie: using the same strategy on each game), two 'No' and one AC, but the others changed their behavior on different games. We would not find any link between participants' profiles (expertise with LoL, AI, etc.) and their preference. Preferences could be partially explained by different levels of engagement with the interface rather than rational optimisation, as the more users tend to use AI, the more they tend to also use multiexplanation strategies. Only their natural decision-making speed can explain their engagement, as some participants said they didn't use the explanations because they were too timeconsuming.

We grouped our participants by preferred explanation, (the four participants having more than 80% of "No" strategy being another group), leading to groups of 3 to 5 participants. The results of the different groups may be seen in Table II. Because we do not control when each participant will effectively access the AI or not, we do not have one "mean accuracy" of the AI they observe, but it keeps between 70% and 75%. The main effects of the experiment interface on interacting groups is the rise in decision time, and a higher variance in accuracy. Surprisingly, user accuracy remained stable between the control and experimental conditions. This can be explained by a hidden problem of our experimental setting: natural compliance between AI's and humans' decisions. The participants followed the AI 91% of time during the experimental condition, whether using the AI or not, and 93% of time during the control condition. Under such conditions, accuracy gains cannot be a good measure of explanations goodness. To our knowledge, this parameter is rarely controlled in similar user studies. We find no correlation between accuracy and compliance: groups 'ACD' and 'ABCD' both had slightly worse accuracy in experimental conditions while their compliance respectively rise and fall under this condition.

C. Reactions towards difficulty of prediction

Fig. 4 shows that the more participants find a game difficult to predict, the more likely they would use our explanatory displays. Such trends can also be found with perceived usefulness, and with time spent on each explanation. This trend also matches the following result: on difficult games participants had a tendency to look at more explanations. This results also reminds us that an AI user does not always need an explanation. Perceived difficulty is likely to be affected by the interaction with AI: we used the model score to have a reference for games difficulty, and we found higher correlations with the participants' mean perceptions in experimental condition (respectively Pearson's R=79% and 85% in control and experimental conditions). As we asked our participants their confidence in their own decision, we found a strong negative correlation between perceived difficulty and confidence (Pearson's R=-80%). However, these variables may have causal connections in both directions, so we retained perceived difficulty as the main variable to consider. We are therefore unable to see if explanations really helped participants being more confident in their decisions: this would require a measure of decision change, with intermediate confidence feedback.

V. DISCUSSION

Even if we still lack capabilities to anticipate people's preferences, this problem can be mitigated easily by letting users change the default explanation. This experiment and analyzes present numerous limits. First of all, refinements are possible on our chosen methods, and especially our surrogate rules: coverage and precision could be added, for instance. However, the main problem remains the strong correlation of results between human and AI: we may find another task to evaluate, or conversely use the feedback from this experiment to sort data, and test participants only on "difficult" data. The existence of individual preferences among explanations open the door to numerous questions about evaluation protocols: do these preferences match their formats? Then we should use several explanations of each form, and subgroups of participants might indicate which is the best among each form. Do these preference match some hidden cognitive strategies, like confirmation or doubt [START_REF] Bansal | Does the whole exceed its parts? the effect of ai explanations on complementary team performance[END_REF], independently of their form? Some participants indeed reported that they use the AI to confirm the a priori they made with data only. At last, we chose not to analyze learning stage results: explanations may find different effects in a didactic perspective. New interactions could easily be developed then, based on users confidence feedback, on their errors, etc.

VI. CONCLUSION

In this study, we developed a multi-explanation interface and demonstrated its usefulness through empirical evaluation on an e-sport prediction task. Even if there is no benefit to use multiple explanations on each case, as they bring additive time costs and no accuracy gain, the different formats could be complementary regarding users, uncovering a need for diversity of explanations. Future research should focus on dynamically adapting such interfaces to user preferences, particularly by estimating the current case difficulty.

Fig. 1 .

 1 Fig.1. Experiment's process for different participants. The red blocks represents predictions series with available AI and explanation, while gray blocks represents series under control condition. During the training, the order of games to predict is randomized. During the evaluation, the order of games is fixed, but their number may vary depending on participants' will.

Fig. 4 .

 4 Fig. 4. Use rates of the different explanations, depending on perceived difficulty. The background histogram represents the distribution of perceived difficulty.

TABLE I AVERAGE

 I USE AND PERCEPTION OF THE EXPLANATORY DISPLAYS.

	A	24	0.76	0.66	3.23	2.99
	B	10	0.19	0.44	4.56	-0.97
	C	21	0.49	0.88	6.50	1.38
	D	19	0.42	0.75	7.07	0.27

A: MODEL'S SCORE, B: SURROGATE RULE, C: LIME, D: NN+ users use rate usefulness time per use interp.

TABLE II PERFORMANCES

 II BY PREFERENCES: COMPLIANCE (CPL), ACCURACIES (ACC) AND DECISION TIMES (DT) FROM CONTROL CONDITION (CTRL) AND EXPERIMENTAL CONDITION (XP).

		Acc (ctrl) Acc (xp) Cpl (ctrl) Cpl (xp) DT (ctrl) DT (xp)
	preference
	A (n=4)	0.71	0.69	0.94	0.92	13.67	17.05
	ABCD (n=3)	0.72	0.70	0.87	0.95	17.52	23.79
	AC (n=4)	0.73	0.72	0.98	0.89	14.64	19.53
	ACD (n=5)	0.70	0.69	0.95	0.86	11.93	19.88
	AD (n=5)	0.70	0.76	0.93	0.91	11.27	16.33
	No (n=4)	0.72	0.72	0.88	0.96	10.24	9.58

code is available on github.com/CBoidot/benefits multi XAI test set, we selected a sample of 80 games to be used for the human experiment. Among those, 30 would be dedicated to human training on the task, and 50 would be used for human evaluation, but because of experimental timing constraints, only

were used for the training, and the evaluation could use a variable number of games (see section III).

ACKNOWLEDGMENT

This research has been supported by the group Crédit Mutuel Arkéa. We would like to thank members of the Data Office of Crédit Mutuel Arkéa for their collaboration.


Fayc ¸al Hamdi

Brigitte Safar

Nobal B Niraula
email: nobal.niraula@inria.fr

Chantal Reynaud

TaxoMap in the OAEI 2009 alignment contest

TaxoMap is an alignment tool which aims to discover rich correspondences between concepts. It performs an oriented alignment (from a source to a target ontology) and takes into account labels and sub-class descriptions. This new implementation of TaxoMap reduces significantly runtime and enables parameterization by specifying the ontology language and different thresholds used to extract different mapping relations. It improves terminological techniques, with a better use of TreeTagger and introduces new structural techniques which take into account the structure of ontology. Special effort has been made to handle large-scale ontologies by partitioning input ontologies into modules to align. We conclude the paper by pointing out the necessary improvements that need to be made.

Introduction

TaxoMap was designed to retrieve useful alignments for information integration between different sources. The alignment process is then oriented from ontologies that describe external resources (named source ontology) to the ontology (named target ontology) of a web portal. The target ontology is supposed to be well-structured whereas source ontology can be a flat list of concepts.

TaxoMap makes the assumption that most semantic resources are based essentially on classification structures. This assumption is confirmed by large scale ontologies which contain rich lexical information and hierarchical specification without describing specific properties or instances.

To find mappings in this context, we can only use the following available elements: labels of concepts and hierarchical structures.

The new implementation of TaxoMap proposes a better morpho-syntactic analysis and new techniques. Moreover, the methods to partition large ontologies into modules which TaxoMap can handle easily were refined.

We take part to five tests. We hope we perform better in terms of precision of mappings generated and runtime. Tests on library data sets allow us to experiment our algorithm on large multilingual ontologies (English, French, and German).

Presentation of the System

State, Purpose and General Statement

We consider an ontology as a pair (C, H C ) consisting of a set of concepts C arranged in a subsumption hierarchy H C . A concept c is defined by two elements: a set of labels and subclass relationships. The labels are terms that describe entities in natural language and which can be an expression composed of several words. A subclass relationship establishes links with other concepts.

Our alignment process is oriented; from a source (O S ) to a target (O T ) ontology. It aims at finding one-to-many mappings between single concepts and establishing three types of relationships, equivalence, subclass and semantically related relationships defined as follows.

Equivalence relationships An equivalence relationship, isEq, is a link between a concept in O S and a concept in O T with labels assumed to be similar.

Subclass relationships Subclass relationships are usual

isA class links. When a concept c S of O S is linked to a concept c T of O T with such a relationship, c T is considered as a super concept of c S .
Semantically related relationships A semantically related relationship, isClose, is a link between concepts that are considered as related but without a specific typing of the relation.

Techniques Used

The different techniques are based on the use of the moropho-syntactic analysis tool TreeTagger [START_REF] Schmid | Probabilistic Part-of-Speech Tagging Using Decision Trees[END_REF], and a similarity measure which compares the trigrams of the concept labels [START_REF] Lin | An Information-Theoretic Definition of Similarity[END_REF]. TreeTagger is a tool for tagging text with part-of-speech and lemma information, enables to take into account the language, lemma and an use word categories in an efficient way. The words are classified as functional (verbs, adverbs or adjectives) and stop words (articles, pronouns). Once classified by TreeTagger, the words are divided into two classes, full words and complementary words, according to their category and their position in the label. In principle, all names are full words except if they are placed after a determiner, all other words are complementary words. This classification is then used to give more weight to the full words in the calculation of similarity between labels.

The main methods used to extract mappings between a concept c s in O S and a concept c t in O T are:

-Label equivalence: An equivalence relationship, isEq, is generated if the similarity between one label of c s and one label of c t is greater than a threshold (Equiv.threshold).

-High lexical similarity: Let c tmax be the concept in O T with the highest similarity measure with c s . If the similarity measure is greater than a threshold (High-Sim.threshold) and if one of the labels of c tmax shares at least two full words in common with one of the labels of c s , the heuristic generates the relationship < c s isA c tMax > if the label of c tmax is included in the c s one, otherwise it generates < c s isClose c tMax >. -Label inclusion (and its inverse): If one of the labels of c tmax is included in one of the labels of c s , and if all words of included label are full words, we propose a subclass relationships < c s isA c tmax >. Inversely, if one of the labels of c s is included in one of the labels of c tmax , we propose a semantically related relationships < c s isClose c tmax >. -Reasoning on similarity values: Let c tMax and c t2 be the two concepts in O T with the highest similarity measure with c s , the relative similarity is the ratio of c t2 similarity on similarity c tMax . If the relative similarity is lower than a threshold (isA.threshold), one of the three following techniques can be used:

• the relationship < c s isClose c tMax > is generated if one of the labels of c s is included in one of the labels of c tMax , and the words of the included label are complementary words. • the relationship < c s isClose c tMax > is generated if the similarity of c tMax is greater than a threshold (isClose.thresholdMax). • an isA relationship is generated between c s and the father of c tMax if the similarity of c tMax is greater than a second threshold (isA.thresholdMax). -Reasoning on structure:

• an isA relationship < c s isA c t > is generated if the subclass relation < c s isSubClassOf X > appears in O S and if the equivalence mapping < X isEq c t > have been identified.

• the relationship < c s isClose c t > is generated if c t is the concept in O T which

Partitioning of large scale ontologies

We propose a method of ontology partitioning [START_REF] Hamdi | Alignment-based Partitioning of Large-scale Ontologies[END_REF], that relies on the implementation of PBM [START_REF] Hu | Partition-based block matching of large class hierarchies[END_REF] algorithm. PBM partitions large ontologies into small blocks (or modules) and constructs mappings between the blocks, using predefined matched class pairs, called anchors to identify related blocks. We reuse the partitioning part and the idea of anchors, but the originality of our method, called PAP (Partition, Anchor, Partition), is that it is alignment oriented, that means that the partitioning process is influenced by the mapping process.

The PAP method consists of:

-decompose the most structured ontology, that will be called the target, O T , into several blocks B T i , according to the PBM algorithm. -force the partitioning of the other ontology, called the source O S , to follow the pattern of O T . To achieve this, the method identifies for each block B T i constructed from O T all the anchors belonging to it. Each of these sets of anchors will constitute the kernel or center CB Si of a future block B Si which will be generated from the source O S . -reuse the PBM algorithm to partition the source O S around the centers CB Si .

-align each block B Si built from a center CB Si with the corresponding block B T i . The tests show that the maximum size of the blocks has to be fixed for the target ontology. If the themes covered by both ontologies are of the same importance, i.e. if the source ontology corresponds to a representation of the same importance than the representation of the target one, a maximum size for the blocks in the source ontology is not needed. Their size will become close to the size of the blocks of the target ontology. This phenomenon allows to avoid obtaining a lot of small isolated blocks which appear when the maximum size of the blocks of the source ontology is fixed. So, on the example of Fig2, the B S3 block remains isolated because the size of of the source blocks was fixed. Without limitation of the size, the B S3 block can be merged with B S2 . The only blocks which will remain isolated will be the blocks built when the source ontology will be partitioned, independently of the kernels identified in the decomposition of the target ontology, i.e. concepts with no relation with those of the target ontology. So, the fact that the concepts belonging to these isolated blocks are not aligned should not damage our results.

Adaptations made for the Evaluation

Unlike in previous years, we have made some specific adaptations for the OAEI 2009 campaign.

For Anatomy task, we did not use the techniques which generate isA relationship. All the alignments outputted by TaxoMap are uniformly based on the same parameters. We had, however, fixed confidence values depending on relation types.

For library test, data sets consist of multilingual ontologies. In order to use lexical comparison, we translated non-English labels of all of the concepts of the vocabularies into English. The translation is done by using Googles translation APIs.

Link to the system and parameters file

TaxoMap requires:

-Mysql3 -Java (Version 1.5 and above )4 -Google's Java Client API for Translation5 -TreeTagger with its language parameter files 6The version of TaxoMap (with parameter files) used in 2009 contest can be downloaded from:

-http://www.lri.fr/˜hamdi/TaxoMap.jar: a parameter lg has to be specified it denotes the language of the ontology. For example TaxoMap.jar fr to perform alignment on ontologies in French. If no language is specified, it is supposed to be English. -http://www.lri.fr/˜hamdi/TaxoMap.properties: a parameter file which specifies:

• The command to launch TreeTagger.

• TreeTagger word categories that has to be considered as functional, stop words and prepositions.

• The RDF output file.

• Different thresholds of similarity, depending on the method used. -http://www.lri.fr/˜hamdi/dbproperties.properties: a parameter file which contains the user and password to access to MySql.

Results

Benchmark Tests

Since our algorithm only considers labels and hierarchical relations and only provides mapping for concepts, the recall would have been low even for the reference alignment.

The overall results would have been similar -with no surprise-to those of last year.

Anatomy Test

The anatomy real world case is to match the Adult Mouse Anatomy (denoted by Mouse) and the NCI Thesaurus describing the human anatomy (tagged as Human). Mouse has 2,744 classes, while Human has 3,304 classes. As last year, we considered Human as the target ontology as is it well structured and larger than Mouse.

TaxoMap performs the alignment (with no need to partition) in about 8 minutes which is better than last year [START_REF] Hamdi | TaxoMap in the OAEI 2008 alignment contest[END_REF] where TaxoMap took about 25 minutes to align the two ontologies.

As only equivalence relationships will be evaluated in the alignment contest, we did not use this year the techniques which generate isA relationship (except in the Task 3) and we change isClose mapping to equivalence. As a result, we found fewer mappings than last year but we hope that the precision will be better.

-For the first task, TaxoMap discovers 1274 mappings, 973 Equivalence relations and 301 Proximity relations. -For the second task, we got only 1084 mappings, 973 Equivalence relations and 111 Proximity relations, using only the heuristic which identifies the relation < c s isClose c tMax > when one of the labels of c s is included in one of the labels of c tMax . -For the third task, we used, in addition of the techniques ot the first task, the heuristic which identifies subsumption links with "High Lexical Similarity". This allows to discover 1451 mappings and to slightly increase the recall, but reduce the precision. In fact, many mappings like <hand blood vessel isA Blood Vessel > or <iris blood vessel isA Blood Vessel > are semantically correct but become false when the subsumption relation isA is automatically replaced by an Equivalence relation.

-For the fourth task, we used the partial reference mapping in our partitioning method and we obtained 1131 mappings. This lower number of mapping is explained by two facts. The first one is that the structural heuristic based on the Semantic Cotopy is the only one of which the results can be improved by the use of the partial mapping. The second one is that the partitioning method increases the precision but reduces the recall.

Directory Test

The directory task consists of Web sites directories like Google, Yahoo! or Looksmart.

To date, it includes 4,639 tests represented by pairs of OWL ontologies. TaxoMap takes about 40 minutes to complete all the tests.

Library Test

In order to use lexical comparison in library data sets, which consist of multilingual ontologies, we used Google translation API [7] to translate non-English labels into English. With our current configuration, we cannot partition the large sized library ontologies. However, we used just a part of its data set to partition and then to find the mappings among concepts.

As skos relations will be evaluated, we change different mapping types to skos ones with these confidence values:

-(type1) isEq relations become skos:exactMatch with a confidence value set to 1. -(type2) isA relations become skos:narrowMatch with a confidence value set to 1 for label inclusion, 0.5 for relations generated by structural technique or by relative similarity method. -(type3) isGeneral relations become skos:broadMatch with a confidence value set to 1. -(type4) isClose relations become skos:relatedMatch with a confidence value set to 1.

Generated mappings are as follows:

-LCSH-RAMEAU: 5074 type1 relations, 48817 type2 relations, 116789 type3 relations and 13205 type4 relations. -RAMEAU-SWD: 1265 type1 relations, 6690 type2 relations, 17220 type3 relations and 1317 type4 relations. -LCSH-SWD: 38 type1 relations.

Benchmark-Subs Test

Benchmark-Subs tests aims to evaluate alignments which contain other mapping relations than equivalence. Two tasks are available in this test: Gold-standard based evaluation concerning the evaluation of subsumption relations and open-ended task concerning the evaluation of equivalence and non-equivalence mappings. In our tool, for the first task, we use lexical methods to obtain subsumption relations.

Results

The new version of TaxoMap improves significantly the results on the previous version of TaxoMap in terms of runtime and precision of generated mappings. The new implementation offers extensibility and modularity of code. TaxoMap can be parameterized by the language used in ontologies, the choice of used techniques and different thresholds. Our partitioning algorithms allow us to participate to tests with large ontologies.

Future Improvements

The following improvements can be made to obtain better results:

-To take into account all concepts properties instead of only the hierarchicals ones.

-Use of WordNet as a dictionary of synonymy. The synsets can enrich the terminological alignment process if an a priori disambiguation is made. -To develop the remaining structural techniques which proved to be efficient in last experiments [8] [9].

Conclusion

This paper reports our participation to OAEI campaign with the new implementation of TaxoMap. Our algorithm proposes an oriented mapping between concepts. Due to partitioning, it is able to perform alignment on real-world ontologies. Our participation in the campaign allows us to test the robustness of TaxoMap, our partitioning algorithms and new structural techniques.

  have the most number of children in O T with the same label as the children of c s in O S . More details of this approach are given at the end of this sub-section. • an isA relationship < c s isA p > is generated if the three concepts in O T with the highest similarity measure with c s have similarity greater than a threshold (Struct.threshold), and have a common father p in O T . As we mentioned above, we use a structural heuristic based on the Semantic Cotopy measure of a concept, proposed by Maedche and Staab [3]. The Semantic Cotopy is based on the intentional semantics of a concept c in an ontology O, SC(c, O), defined as the set of all its super-and sub-concepts in O. When a concept c belongs to two ontologies, one can define the taxonomic overlap (T O) between O 1 and O 2 for this concept, denoted T O(C, O 1 , O 2 ) and defined as the ratio between the number of common elements in the intentional semantics of c in O 1 and in O 2 and the total number of elements belonging to the union of these two sets. If a concept c is in O 1 but not in O 2 , an optimistic approximation of T O(c, O 1 , O 2 ) is defined as the maximum overlap obtained by comparing SC(c, O 1 ) to the intentional semantics of all the concepts in O 2 . Our heuristic uses SC D (c) which includes only the concept and its descendants instead of the original Semantic Cotopy. If a concept c is in O 1 but not in O 2 , we propose as candidate mapping for this concept c, the concept c Max of O 2 which maximizes the T O, if c and c Max have at least two descendants in common.

Fig. 1 .Fig. 2 .

 12 Fig. 1. The centers CBSi identified from BT i Fig. 2. Partition of OS around the centers CBSi

http://www.mysql.com

http://java.sun.com

http://code.google.com/p/google-api-translate-java

http://www.ims.uni-stuttgart.de/projekte/corplex/TreeTagger

Link to the Set of Provided Alignments

The alignments produced by TaxoMap are available at the following URLs: http://www.lri.fr/˜hamdi/benchmarks/ http://www.lri.fr/˜hamdi/anatomy/ http://www.lri.fr/˜hamdi/directory/ http://www.lri.fr/˜hamdi/library/ http://www.lri.fr/˜hamdi/benchmark-subs/