Julien Ah-Pine

Stephane Clinchant

Gabriela Csurka

Yan Liu

XRCE's Participation in ImageCLEF 2009

This paper describes XRCE's participation in Large Scale Visual Concept Detection and Annotation Task [16] and Photo Retrieval Task [17] of ImageCLEF 2009. Those tasks both use a new collection which is different and which is much larger than the ones used in past sessions. Moreover, new kinds of challenge to tackle were designed such as new categories to detect or new types of topic to deal with. Accordingly, our main motivations regarding our participation in this year's session are two fold. First, we wanted to apply ongoing work in our team in image and text processing. Second, we wanted to figure out if our cross-media approach and our diversity re-ranking techniques developped in past sessions, can perform well on a new challenging corpus. It turns out that the material that we describe in this paper both made of new and already well-established techniques allow to perform very well on those two tasks since the results we obtained with the systems we designed are top ranked.

3 Notice that this is systematically done through our cross-media technique. 4 The Cross-Entropy multiplied by -1 actually.

Introduction

This year, we participated in two main tasks: the Large Scale Visual Concept Detection and Annotation Task (detailed in [START_REF] Nowak | Overview of the clef 2009 large scale -visual concept detection and annotation task[END_REF]) and the Photo Retrieval Task (detailed in [START_REF] Paramita | Diversity in photo retrieval: overview of the imageclefphoto task 2009[END_REF]).

For the visual concept detection task, the main research questions were two-fold. First, the focus this year lied on the extension of the task concerning the amount and the diversity of concepts (53) used as types of annotation. There were also different kinds of concept such as abstract categories (landscape, family and friends, party life, ...), seasons, time of day, persons (no, single, big groups), quality (blurred, underexposed) and representation (portrait, macro image, canvas). Secondly, the aim was to assess whether a given ontology of concepts could help in classification or not.

Despite the fact that the concepts were presented in a hierarchy with a given ontology, we have not used neither the hierarchy nor the ontology in the training phase. Indeed we considered the task first as a multi-class multi-label image categorization problem and trained binary one versus all (OVA) classifiers for each concept. To train the classifiers, we used the Fisher Representation of images (as last year). However, we also used the adapted image GMMs which were combined with Fisher Representation by late fusion technique (score averaging). In the test phase and for each image, the classification scores were finally post-processed in order to ensure that the constraints of the ontology were not violated.

Similarly, the Photo Retrieval Task sets two new challenges: the scalability of the methods in order to cope with 500,000 images and the diversity of the top retrieved results. The basic methodologies used -Language Model for text retrieval, Fisher Vector image representation, transmedia fusion based cross-media similarity and clustering based re-ranking of top results -were ones already employed in previous years but with slight modifications and adaptations to better fit the actual task.

Furthermore, we had to design some new strategies to cope with on one hand, the large amount of data; on the other hand, the lack of information concerning the clusters in the second part of queries:

-Regarding the scalability problem, instead of pre-computing the whole cross-media similarity matrix off-line (as was done last year), we compute a cross-media similarity matrix "on-line" for each individual query (sub-)topic. This is actually done in two steps. First, we used a text-based retrieval technique. Then, we used the top list obtained from the latter in order to compute visual similarities and cross-media similarities as well. It is the computation of visual similarities that suffers the most from scalability issues. Accordingly, we abandoned the computation of similarity matrices over the whole collection of size 500, 000 × 500, 000 since that was estimated to be very costly both in speed and storage. -Regarding the second part of queries, no cluster information was available. In that case, this is somehow similar to the approach we experimented for last year task as we did not use the cluster description. Therefore, we re-used some of our last year strategies to promote diversity among the top list namely clustering and KNN density based re-ranking. Furthermore it is worth noticing that if we use only the captions of the images queries 3 , we would get results illustrating only the corresponding sub-topics. Thus, to increase our chances to find new relevant sub-topics, we combined different sources of information. Basically, we combine the query title and the captions of images. This would ensure that the retrieved elements are relevant to the query topic but somehow this would also allow to have more diverse elements. Furthermore, we propose to enrich the query with terms that are the most related in the corpus using some standard term similarities.

The paper is structured as follows. Section 2 described the textual retrieval models. In section 3, we present the Fisher and adapted GMM representation of images. We recall our cross-media similarity measure in section 4 and our diversity seeking methods in 5. Before concluding, a detailed description of our runs in both challenges are presented in section 6.

Text Retrieval

We start from a traditional bag-of-word representation of pre-processed texts: pre-processing includes tokenization, lemmatization, and standard stopword removal. Two information retrieval models were considered: a standard language models (as our previous participation) and an information based model on a log-logistic distribution. We then present a query expansion mechanism that appeared to be relevant to the Photo Retrieval Task.

Language Models

The idea of language models is to represent queries and documents by multinomial distributions [START_REF] Zhai | A study of smoothing methods for language models applied to ad hoc to information retrieval[END_REF][START_REF] Ponte | A language modelling approach to information retrieval[END_REF] .Those distributions are estimated by maximizing the likelihood. Then, documents distributions are smoothed by a Dirichlet Prior [START_REF] Zhai | A study of smoothing methods for language models applied to ad hoc to information retrieval[END_REF] and the Cross-Entropy 4 can be used to rank documents according to:

sim txt (D 1 , D 2 ) = CE(D 1 |D 2 ) = w p(w|D 1 ) log(p(w|D 2 )) (1)
where D 1 and D 2 are two texts and w is a term from the bag-of-word representation. Notice that in the context of information retrieval, D 1 is the query that contains only a few keywords in comparison to a document. However, we also use language models to measure the similarity between pairs of documents in the collection so we rather introduce more general notations.

Log-Logistic Model

We used in this paper a new family of IR models similar in spirit to DFR models [START_REF] Amati | Probabilistic models of information retrieval based on measuring the divergence from randomness[END_REF], which is based on probability distributions fitting well empirical data, and satisfying heuristic retrieval constraints [START_REF] Clinchant | Bridging language modeling & divergence from randomness models: A log-logistic model for ir[END_REF][START_REF] Clinchant | Retrieval constraints and word frequency distributions a log-logistic model for ir[END_REF].

The general idea of this family is the following one: due to different document length, discrete term frequencies are renormalized into continuous values as in [START_REF] Amati | Probabilistic models of information retrieval based on measuring the divergence from randomness[END_REF]. Let m be the mean document length and y D the length of document D, x D w is the raw number of occurrences of term w in document D. Then, the normalized frequencies are:

t D w = x D w log(1 + m y D )
For each term w, we assume that those renormalized values follow a probability distribution P .

In our case, we suppose a log-logistic distribution. The log-logistic distribution is given by:

P LL (X < t; r, β = 1) = t β t β + r β (2)
and the parameter r w is estimated with: r w = Nw N , where N w is the number of document where w occurs in and N is the total number of document in the collection.

Finally, queries and documents are compared through a measure of surprise, or a mean of information of the following form:

sim txt (D 1 , D 2 ) = w∈D1∩D2 -x D1
w log(P LL (X ≥ t D2 w ; r w ))

sim txt (D 1 , D 2 ) = w∈D1∩D2 x D1 w log( t D2 w + r w r w ) (3)

Lexical Entailment / Term Similarity

Textual queries were very short with typical length of 1 or 2 words. In general, single keyword queries can be ambiguous. Query expansion techniques could help in finding several meanings or different contexts of the query word. As one of the goal was to promote diversity for the Photo Retrieval Task, query expansion methods could help in finding new clusters. In fact, if a term has several meanings or different contexts, the most similar words to this term should partially reflect the diversity of related topics associated to it. The Chi-Square statistics was used to measure the similarity between two words [START_REF] Christopher | Review: Foundations of statistical natural language processing, christopher d. manning and hinrich schtze[END_REF], although any other term similarity measure or lexical entailment measure could be used. Recall that for two terms u, v, one can fill in a 2 by 2 contingency table with the number of documents that contains u and v, only u, only v or neither of them.

As the number of clusters were not known before-hand for the second part of queries, we decided to use this Chi-Square measure to only enrich the text queries of the second part. Hence, for each query word q w , we computed the Chi-Square statistics of the latter with all other words (including q w ). We kept only the top ten words and divided the scores by the maximum value (given by the inner statistic of q w with itself). Table 1 displays, for some query terms, the most similar terms with the renormalized Chi-Square statistics. To illustrate that co-occurrence measures can handle diversity of word senses, one can look at the most similar terms of the euro term. The most similar term bear the notion of lottery, currency or football event, which were somehow also indicated in the topic images.

Image Representation

In this section, we first describe briefly our visual vocabulary modeled by Gaussian Mixture Model (section 3.2). Then, we present the Fisher Vector representation (section 3.2) which was used in both Visual Concept Detection Task (section 6.1) and Photo Retrieval Task (section 6.2). Finally, we present an alternative representation of images using adapted GMMs which was only used in the Visual Concept Detection Task (section 6.1).

The Visual Vocabulary

We model the visual vocabulary [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF][START_REF] Csurka | Visual categorization with bags of keypoints[END_REF] with a Gaussian Mixture Model (GMM) where each Gaussian corresponds to a visual word [START_REF] Farquhar | Improving "bag-of-keypoints" image categorisation[END_REF][START_REF] Perronnin | Adapted vocabularies for generic visual categorization[END_REF]. Let λ = {w i , µ i , Σ i , i = 1, ..., N } be the set of parameters of P where w i , µ i and Σ i denote respectively the weight, mean vector and covariance matrix of Gaussian i and where N denotes the number of Gaussians. Let P i be the distribution of Gaussian i so that we have

P (x) = N i=1 w i P i (x) = N i=1 w i N (µ i , Σ i ). ( 4
)
The visual vocabulary is supposed to describe the content of any image and, therefore, it is trained off-line on a varied set of images. Let X = {x t , t = 1, ..., T } be the set of training observations extracted from these images. The estimation of λ is performed by maximizing the log-likelihood function log P (X|λ) under an independence assumption:

log P (X|λ) = T t=1 log P (x t |λ) (5)
as described in [START_REF] Perronnin | Adapted vocabularies for generic visual categorization[END_REF].

Fisher Representation of Images

As image representation, we use the Fisher Vector proposed in [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]. This is an extension of the bag-of-visual-words representation. The main idea is to characterize the image I (represented by a set of samples x t ) with the gradient of the log-likelihood ∇ λ log P (I|λ). In the case of a GMM with isotropic covariance matrix (see section 3.1 and [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]), we have the following formulas:

∂L(I|λ) ∂w i = T t=1 γ t (i) w i - γ t (1) w 1 for i ≥ 2 , ( 6
)
∂L(I|λ) ∂µ d i = T t=1 γ t (i) x d t -µ d i (σ d i ) 2 , ( 7
)
∂L(I|λ) ∂σ d i = T t=1 γ t (i) (x d t -µ d i ) 2 (σ d i ) 3 - 1 σ d i . ( 8
)
where γ t (i) = P (i|x t , λ), the superscript d denotes the d-th dimension of a vector and σ d i are the diagonal elements of Σ i . In practice, we only use the partial derivatives with respect to the means and standard deviations since adding the partial derivative with respect to the mixture weights does not improve accuracy.

The main advantage of this representation, which we will call Fisher vector, is that it transforms a variable length sample (number of local patches in the image) into a class independent fixed length representation whose size is only dependent on the number of parameters in the model (λ).

Before feeding these vectors to a classifier or computing similarities between images, each vector is first normalized using the Fisher Information matrix F λ (see [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF] for the computational details):

f I = F -1/2 λ ∇ λ log P (I|λ) (9)
with

F λ = E XP ∇ λ log P (I|λ)∇ λ log P (I|λ) T .
and then re-normalized to have an L1-norm equal to 1.

In the case of image retrieval, to obtain the similarity between two images I 1 and I 2 , we compute the L1-norm of the two Fisher vectors:

sim img (I 1 , I 2 ) = norm max -||f I1 -f I2 || 1 = norm max - i |f i I1 -f i I2 | (10)
where f i are the elements of the normalized vector f and norm max = 2.

Images as Adapted Mixtures of Gaussian

We adapt here the method proposed in [START_REF] Liu | Similarity measure between unordered vector sets with application to image categorization[END_REF], where each image is represented by a GMM adapted from a common "universal" GMM (λ) using the maximum a posteriori (MAP) criterion. Let I = {x t , t = 1, ..., T } denote the set of "adaptation samples" extracted from one image. The goal of MAP estimation is to maximize the posterior probability P (λ a |I) or equivalently log P (I|λ a ) + log P (λ a ), where λ a is an "adaptation" of λ (see [START_REF] Liu | Similarity measure between unordered vector sets with application to image categorization[END_REF] for details). The advantages of this representation are two fold. MAP provides a more accurate estimate of the GMM parameters compared to standard maximum likelihood estimation (MLE) in the challenging case where the cardinality of the vector set is small. Moreover, there is a correspondence between the Gaussians of two GMMs adapted from a common distribution and one can take advantage of this fact to compute efficiently the probabilistic similarity.

To measure the similarity between two images, we use the Kullback-Leibler Divergence (KLD) between two continuous distributions P and P ′ :

KL(P ||P ′ ) = x P (x) log P (x) P ′ (x) dx (11)
However, there is no closed-form expression for the KLD between two GMMs P (x) = N i=1 α i P i (x) and P ′ (x) = N j=1 β j P ′ j (x). Therefore, we use the KLK approximation proposed by Liu et Perronnin [START_REF] Liu | Similarity measure between unordered vector sets with application to image categorization[END_REF]:

KL(P ||P ′ ) ≈ N i=1 α i KL(P i ||P ′ i ) + log α i β i . ( 12
)
4 Cross-media similarity

Cross-media similarities

This section deals with the intermediate fusion we used in our experiments. It aims at combining visual and textual similarities in an efficient manner.

The method is similar to the one we introduced in the 2007's session [START_REF] Clinchant | Xrce's participation to imageclef[END_REF] and used in last year session [START_REF] Ah-Pine | Xrce's participation to imageclef[END_REF]. This method has proved to significantly leverage multimedia retrieval performances.

Moreover, cross-media similarities that we obtain using this approach will be the basis for diversitybased extensions that will be discussed in the next section. As a result, we recall the basic concepts of this approach in the following.

In general terms, we assume that S t and S i are two similarity matrices over the same set of multimedia objects denoted O i ; i = 1, . . . , K. The former matrix is related to textual based similarities whereas the latter matrix is rather based on visual similarities. Typically, S t is related to Eq. ( 1) or Eq. ( 3) and S i to Eq. [START_REF] Hartigan | Clustering Algorithms[END_REF]. We actually use a linear transformation of the latter matrices in order to normalize the proximity measures distribution of each row so as to obtain a similarity value distribution between 0 and 1.

Then, let κ(S, k) be the thresholding function that, for all rows of S, puts to zero all values that are lower than the k th highest value and keeps all other components to their initial value.

Accordingly, we define the cross-media similarity matrices that combine two mono-media similarity matrices as follows:

Sim img-txt = κ(S i , k i ).S t ( 13
)
Sim txt-img = κ(S t , k t ).S i (14)
where the . symbol designates the standard matrix product.

In that context, this intermediate fusion method can be seen as a graph similarity mixture through a two-step diffusion process, the first step being performed in one mode and the second step being performed in the other one (see [START_REF] Clinchant | Xrce's participation to imageclef[END_REF][START_REF] Ah-Pine | Xrce's participation to imageclef[END_REF][START_REF] Ah-Pine | Crossing textual and visual content in different application scenarios[END_REF] for further details).

Let us precise that in the more specific case of information retrieval, we are given a multimedia query q (q t denoting the text part and q i the image part of q). In that context, as far as the notations are concerned, we rather have the following cross-media score definition:

Score img-txt = κ(s i , k i ).S t (15)
Score txt-img = κ(s t , k t ).S i (16)
where s t is the similarity row vector of a given textual query q t with a set of multimedia objects (their text part) and s i is similarly, the similarity row vector of a given image query q i with the the same set of multimedia objects (but their image part).

Fusing all similarities

Cross-media similarities that we have recalled in the previous subsection, attempt to better fill in the semantic gap between images and texts. They allow to reinforce the mono-media similarities. Therefore, the final similarity we used is a late fusion of mono-media and cross-media similarities. This late combination have proved to provide better results according to our experiments in previous sessions of ImageCLEF Photo Retrieval Task. The final pairwise similarity matrix that evaluates the proximity relationships between multimedia items of a set of elements is given by:

Sim = α t S t + α i S i + α it Sim img-txt + α ti Sim txt-img (17)
where α t , α i , α it , α ti are four weights that sum to 1. In our experiments we used the following distribution:

α t = 5/12, α i = 1/4, α it = 1/4, α ti = 1/12.
Similarly, when we are given a multimedia query, the final relevance score is computed as follows:

Score = α t s t + α i s i + α it Score img-txt + α ti Score txt-img (18)
where the weight distribution is set in the same manner as previously.

One of the aims of ImageCLEFPhoto 2009 is to promote diversity in the top search results so that the first retrieved elements are not redundant. Therefore, we investigated different strategies to promote such diversity:

1. Using different sources of information for the same query: for example the caption of images, the query title and an enriched query. We can combine these different top lists using the Round Robin principle. 2. Using a density based re-ranking of the top elements. 3. Using a clustering based re-ranking of the top elements.

In this section we introduce these latter techniques.

Round Robin Approach

The main idea of Round Robin principle is that each individual (in our case the different top lists) takes its turn to make a single list. We take for each top list the elements with respect to their rank and we update a single list by taking the following element top list after top list. A same item can appear in different top lists. Thus, we first verify whether a coming element is already in the merged list or not. If not it is appended to the latter.

Density Based Re-ranking

This approach consists in identifying among a top list, peaks with respect to some estimated density functions. As density measure d, we used a simple one which is the sum of similarities (or distances) of the k nearest neighbors. Thus, given an object O i , we define:

d(O i ) = k j=1 S(O i , O i j ) (19)
where O i j ; j = 1, . . . , k are the k nearest neighbors of O i and the proximity measure between two multimedia objects can be based on visual similarity5 given by Eq. [START_REF] Hartigan | Clustering Algorithms[END_REF], textual similarity (between their captions6 ) based on Eq. (3) or cross-media similarities (as described in section 4.1).

Finally, we re-rank the objects according to this measure by ranking first the objects that are the most "dense" and by discarding the nearest neighbors7 of these latter elements added to the list.

Clustering Based Re-ranking

Our clustering based re-ranking approach we tested is similar to last year's session so hear we will only briefly recall (see [START_REF] Ah-Pine | Xrce's participation to imageclef[END_REF] for more details).

We assume here that we are given an ordered top list of objects Q and a similarity matrix S between these objects (both Q and S could be visual, textual or cross-modal based). S is normalized such that for each row, the maximal element takes the value 1 and the minimal element the value 0. We apply the Relational Analysis (RA) approach for the clustering step in order to find homogeneous themes among the set of objects [START_REF] Michaud | Optimisation en analyse de données relationnelles[END_REF][START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF][START_REF] Ah-Pine | Xrce's participation to imageclef[END_REF][START_REF] Ah-Pine | Cluster analysis based on the central tendency deviation principle[END_REF].

The clustering function that we want to optimize with respect to X is the following one:

C(S, X) = |Q| i,i ′ =1        S(O i , O i ′ ) - 1 |S + | (Oi,O i ′ )∈S + S(O i , O i ′ ) constant threshold        X(O i , O i ′ ) (20)
where

X(O i , O i ′ ) = 1 if O i
and O i ′ are in the same cluster and X(O i , O i ′ ) = 0 otherwise; and S + is the set of pairs of objects which similarity measure is strictly positive:

S + = {(O i , O i ′ ) ∈ Q × Q : S(O i , O i ′ ) > 0}.
From Eq. ( 20), we can see that the more the similarity between two objects exceeds the mean average of strictly positive similarities, the greater the chances for them to be in the same cluster. This clustering function is based upon the central tendency deviation principle [START_REF] Ah-Pine | Cluster analysis based on the central tendency deviation principle[END_REF]. In order to find a partition represented by X that maximizes the objective function we used the same clustering algorithm described in [START_REF] Ah-Pine | Xrce's participation to imageclef[END_REF][START_REF] Ah-Pine | Cluster analysis based on the central tendency deviation principle[END_REF]. Notice that this approach doesn't require to fix the number of clusters. This property turns out to be an advantage for finding diverse relevant themes among the objects.

After the clustering step, we have to define a re-ranking strategy which takes into account the diversity provided by the clustering results. The main idea of our approach is to represent, among the first re-ranked results, elements which belong to different clusters until a stopping criterion is fulfilled. The strategy employed is described in Algorithm 1.

Algorithm 1 Re-ranking strategy for a (sub-)topic

Require: A (sub-)topic q, an ordered list Q according to some relevance score between q and Qi; i = 1, . . . , |Q| and R the clustering results of objects in Q. Let L1, L2, L3 and CL be empty lists and i = 2. Add Q1 as first element of the re-ranked list L1 and R(Q1) (the cluster id of Q1) to the cluster list CL while i ≤ |Q| and Stopping criterion is not fulfilled do if R(Qi) ∈ CL then Append Qi to L2 else Append Qi to L1 and add R(Qi) in CL end if i = i + 1 end while Put if not empty the complementary list of objects from Qi to Q |Q| in L3. Extend L1 with L2 then with L3 and return L1.

The stopping criterion in Algorithm 1 we used is related to a parameter denoted nbdiv ∈ 1, . . . , κ8 . It is the maximal number of different clusters that must be represented among the first results. Let us assume that nbdiv = 10. Then, this implies that the first 10 elements of the reranked list have to belong to 10 different clusters (assuming that κ ≥ 10). Once 10 different clusters are appended, the complementary list (from the 11 th rank to the |Q| th rank), is constituted of the remaining multimedia objects sorted in the original list without taking into account the cluster membership information.

Runs description

In this year, we have participated in two tasks of ImageCLEFPhoto 2009: Large Scale Visual Concept Detection and Annotation and Photo Retrieval Tasks. In this section, we describe in more details our runs and show the obtained results.

Large Scale Visual Concept Detection and Annotation Task

The Visual Concept Detection and Annotation Task (described in details in [START_REF] Nowak | Overview of the clef 2009 large scale -visual concept detection and annotation task[END_REF]), had the objective to identify 53 visual concepts in users' photos organized in a hierarchy. The main goal was to indicate the presence or the absence of these concepts ensuring some given ontological constraint between categories (eg. a picture cannot be labeled with summer and spring in the same time, etc).

In spite of the fact that the concepts were presented in a hierarchy with a given ontology, we have not used neither the hierarchy nor the ontology in the training phase but considered the task as a multi-class multi-label image categorization problem and trained binary one versus all classifiers for each concept. Then for each image the classification scores were post-processed in order to ensure that the constraints of the ontology were not violated.

To do this, two types of low-level local features were extracted: SIFT-like features (referred here as texture) and local RGB statistics (referred as color). Both type of features were extracted on a multi-level image grid and the dimensionality of the feature vectors was reduced to 50 through Principal Component Analysis. We built a visual vocabulary in both feature spaces and used these "'universal" vocabularies to define higher level representations (Fisher Vectors and Adapted Mixtures of Gaussian) as described in section 3. Hence, using the training data we built four one-against-all discriminative classifiers for each concept using alternatively color and texture and Fisher Vectors and image-GMMs.

To train the classifiers, we used our own implementation of Sparse Logistic Regression (SLR) [START_REF] Krishnapuram | Sparse multinomial logistic regression: Fast algorithms and generalization bounds[END_REF], (i.e. logistic regression with a Laplacian prior), L1-norm for Fisher Vectors (see section 3.2) and the KLK approximation proposed by Liu et Perronnin [START_REF] Liu | Similarity measure between unordered vector sets with application to image categorization[END_REF] (see section 3.3).

We transformed the classifier scores s in "probabilities" with the sigmoid mapping (1 + exp(s)) -1 and for each concept simply averaged the four scores.

Finally, in order to ensure the constraints of the ontology were not violated, we post-processed the scores as follows:

1. For concepts that were modelled as disjoint to each other, we normalized their "probabilities" to sum to 1. 2. For a parent concept, we ensured that its score is higher or equal than the maximum score of his children. 3. For a concept that implies another concept, we corrected only if their scores were conflicting to each other.

Two measures were used to determine the quality of the annotations. One for the evaluation per concept and the other one for the evaluation per photo. The first one was the Equal Error Rate (EER) and the Area under Curve (AUC). The second measure is the proposed hierarchical measure (HM) that considers the relations between concepts and the agreement of annotators on concepts.

Figure 1 plots in blue all the results submitted to the challenge and in red our results. We can see that our system was among the top performing ones for both types of measure: best score for hierarchical measure (with or without annotator agreements) and second best score for AUC. If we average the HM and the AUC measures we remain at the first position (with a score of 0.8341), while averaging any of HM with (1-EER) we are at third position (with a score of 0.7811 with annotator agreement and 0.7715 without annotator agreement).

Photo Retrieval Task

The Photo Retrieval Task of ImageCLEF 2009 (described in details by [START_REF] Paramita | Diversity in photo retrieval: overview of the imageclefphoto task 2009[END_REF]), was intended to provide a further study of the importance of diversity in image search results. This aspect was already one of the goal of last year's session. However, this years task elevates the research scope by using a new data set containing half a million images.

Participants had to produce a ranking holding both relevant and diverse objects. The definition of what constitutes diversity varied across topics. In the first part of the challenge, the "cluster title" fields, clearly indicated what the clustering criteria were. An additional "Cluster description" tag gave even more precision however, we haven't used it. In the second part of the challenge, only three relevant example images were given with the query title, without any other indication concerning the clustering criteria. Participants were encouraged to decide on how broad the results should be for each of these topics.

Therefore, in our experiments we designed two different strategies to handle the two distinct parts. The steps of the first part are given by Algorithm 2. In the experiments, all runs used the same output for this part 1.

Algorithm 2 Image retrieval part 1

Require: query title and query images with their captions.

for Each topic do for Each sub-topic m do Rank the images according to the text similarity between the "the caption of the query image" (we assume that it is relevant to the query sub-topic) and the captions of all other images. Retain the top M images and compute the M × M cross-media similarity matrix using Eq. ( 17). Re-rank the images according to their cross-media similarity with the query image (using the image and its caption). As the query image belongs to the top M images, this is equivalent to the re-ranking of the row corresponding to the query image in the M × M matrix. end for Merge the m ranked lists corresponding to the different sub-topics using the Round Robin technique (eliminating from the list the query images and the exact duplicates coming from different lists). end for

The second part was more challenging especially from the diversity viewpoint since we had no particular indication either about the number of clusters or about the clustering criteria. Therefore, we experimented different strategies for this part. We considered different sources of information (Table 2) for the query and different ranking criteria (Table 3). The steps of the second part are given by Algorithm 3.

In order to re-rank the retrieved objects, we can use either the density based measure or the clustering algorithm. For the density based, we set k=10 neighbors and the distance used was the visual similarity. However, the clustering methods used the cross-media similarity, such as defined in Eq. ( 17)). Nevertheless, it is worth noticing that any kinds of similarity measures (visual, textual, or cross-modal) could be used in order to assess the diversity in the aforementioned re-ranking techniques.

As it can be seen from Algorithm 3, we can generate a variety of different final lists by using different strategies. In the challenge we submitted 4 of them, summarized in Table 4.

The results were ranked in terms of two measures, the precision at 10 (P10) retrieved items and the cluster recall at 10 (CR10). The two measures were combined using the F1-measure. According to this measure XRCEXKNND strategy was the best with F 1 = 0.8087 followed by XRCECLUST and KNND. XRCE1 got a much lower F1 score (0.7439) which shows that the re-ranking was important to enhance the retrieved list. In fact, XRCE1 is a run without any re-ranking to remove nearduplicate elements. It just used different representations of the query and applied a standard ranking algorithm. Regarding the second part of queries, our re-ranking strategies allow to leverage this baseline run with CR10 equal to 60% to runs with around 80% CR10.

We have not explored yet all the possibilities given by Algorithm 3. Can we reach the same performance with pure text runs ? Is the density measure better than the clustering methods, or are they complementary ?

In order to have final conclusions about the best strategy to be applied, we will compare the different individual and combined lists when the cluster judgements will be available.

Conclusion

We have participated in two tasks, Large Scale Visual Concept Detection and Annotation and Photo Retrieval. In both cases, we kept our leading position in spite of the fact that both tasks presented new challenges.

The basic methodologies used in our systems were mainly those used in previous years with slight modifiations and adaptations to better fit the actual tasks. No particular parameter tuning was necessary to achieve the good performances we obtained, on a new corpus. This shows the robustness of our methods.

However, we would like to better analyze our results and particularly for the Photo Retrieval task. In our approach, text-based retrieval is the cornerstone. To which extent, did the visual information leverage these performances ? Was the query expansion able to find new clusters when seeking to promote diversity ? and so on ... Such investigations could be beneficial in order to better understand the properties of our systems and, in a more general perspective, to better tackle information access problems in large image/text collections.

Fig. 1 .

 1 Fig. 1. ImageClef Large Scale Visual Concept Detection and Annotation Task results, the red star represents our system

Table 1 .

 1 Query Terms and their most similar terms

	1	obama 1	strike 1	euro 1
	2	barack 0.98	hunger 0.04	million 0.05
	3 springfield 0.16 protest 0.02	billion 0.05
	4	illinois 0.16	worker 0.01	currency 0.03
	5	senator 0.09	caracas 0.01	2004 0.03
	6	freezing 0.08	led 0.01	coin 0.02
	7	formally 0.08 venezuela 0.01	devil 0.02
	8	ames 0.07	chavez 0.001	qualify 0.02
	9 democrat 0.06 nationwide 0.001 qualification 0.02
	10 paperwork 0.04 retaliatory 0.001	profit 0.01

Table 2 .

 2 Source of Information

	Type	Acronym
	Captions of Image Query	ICPT
	Query Title	QRW
	Enriched Query with most similar Terms ENT

Table 3 .

 3 Ranking Criterion Simply Apply the Cross Media Similarity Measure Density based Re-ranking Clustering based Re-ranking

Table 4 .

 4 List of the combinations used for official runs and their F1-measure

	Run Name		List Used for Round Robin		F1
	XRCE1	ICPT xsim rank	ENT txt rank	QRW txt rank	74.4
	KNND	ICPT xsim rank	ENT knndens rerank		76.2
	XRCECLUST ICPT cluster rerank ENT cluster rerank		79.4
	XRCEXKNND	ICPT xsim rank	QRW knndens rerank ENT knndens rerank. 80.9

In that case, we use the image part Ii of the multimedia object Oi.

In that case, it is the text part Di of the multimedia object Oi.

2 nearest neighbors.

κ is the number of clusters found during the clustering process.

Acknowledgments

This work was partially supported by the French National Project Omnia ANR-06-CIS6-01.

Algorithm 3 Image retrieval part 2

Require: query title and query images with their captions for Each topic do Create three top lists using different text queries: if ICPT (image captions) then for Each query image i = 1 to 3 do Rank the images according to the text similarity between the "the caption of the query image" (we assume that it is relevant to the query sub-topic) and the captions of all other images (see section 2 for details).

Retain the top M images and compute the M × M cross-media similarity matrix using Eq. [START_REF] Paramita | Diversity in photo retrieval: overview of the imageclefphoto task 2009[END_REF]. Re-rank the images according to one of the following strategies: if ICPT xsim rank then Rank according to their cross-media similarity with the query image using Eq. ( 18). else {ICPT cluster rerank} Rank according to their cross-media similarity with the query image such as for ICPT xsim rank. Re-rank the images of the top list of ICPT xsim rank using the clustering based re-ranking method described in section 5.

(using cross-modal similarities). else {ICPT knndens rerank}

Rank according to their cross-media similarity with the query image such as for ICPT xsim rank. Re-rank the top list of ICPT txt rank using density based re-ranking described in section 5.

(using cross-modal similarities). end if end for Merge the 3 ranked lists corresponding to the 3 images using the Round Robin technique (eliminating from the list the query images and the exact duplicates coming from different lists). else {QRW (query title)}

Rank the images according to one of the following strategies: if QRW txt rank then Rank the images according to the text similarity between the query title and the captions of all other images and consider the top M . else {QRW cluster rerank} Rank the images according to the text similarity between the query title and the captions of all other images and consider the top M such as for QRW txt rank.

Re-rank the top list of QRW txt rank using the clustering based re-ranking method (using crossmodal similarities). else {QRW knndens rerank}

Rank the images according to the text similarity between the query title and the captions of all other images and consider the top M such as for QRW txt rank. Re-rank the top list of QRW txt rank using the density based re-ranking method (using crossmodal similarities). end if else {ENT (enriched query)} Rank the images according to one of the following strategies: if ENT txt rank then Rank the images according to the text similarity between the query enriched with lexical entailment (as described in Eq. ( 3) and the captions of all other images and consider the top M . else {ENT cluster rerank} Rank the images according to the text similarity between the query enriched with lexical entailment and the captions of all other images and consider the top M such as for ENT txt rank Re-rank the top list of ENT txt rank using the clustering based re-ranking method (with visual or textual or cross-modal similarities). else {ENT knndens rerank} Rank the images according to the text similarity between the query enriched with lexical entailment and the captions of all other images and consider the top M such as for ENT txt rank. Re-rank the top list of ENT txt rank using the density based re-ranking method (with visual or textual or cross-modal similarities). end if end if Optionally, merge several of the above mentioned ranked lists using the Round Robin approach described in 5.1. end for


Julien Ah-Pine

Stephane Clinchant

Gabriela Csurka

Comparison of Several Combinations of Multimodal and Diversity seeking Methods for Multimedia Retrieval

. We evaluate and compare different mono and multimedia retrieval methods and two distinct diversityseeking strategies as well. Our analysis allows us to better understand which combinations of basic approaches are the best ones. It appears that taking advantage of the multimodal nature of the data by means of our cross-modal similarities technique and leveraging different text representations of the topics in the goal of covering distinct related subtopics, allow us to tackle the Photo Retrieval Task effectively.

Introduction

Given a collection of text/image objects and a set of multimedia topics and subtopics, the aim of the challenge was to produce for each topic, a ranked list of images holding both relevant and diverse objects. However, the definition of what constitutes diversity varied across topics. Basically there are two kinds of topics with respect to this aspect: part 1 and part 2. In the first part, for each subtopic of a topic, in addition to the query title, the "cluster title" field, clearly indicated what the clustering criteria and the "cluster description" field gave even more precision. However, we did not use either of them. In the second part of the challenge, only three relevant illustrative images were given with the query title of the topic, without any other indication concerning the clustering criteria. In that case, participants were encouraged to decide on how broad the results should be for each of these topics.

In what follows, we first briefly introduce the underlying technologies that we used to find relevant and diverse multimedia objects for each topic, then we perform an analysis of the results and a comparison of different strategies as well.

Image representation. As image representation, we use the Fisher Vector1 proposed in [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]. This is an extension of the bag-of-visual-words representation. The main idea is to represent the visual vocabulary with a Gaussian Mixture Model (GMM) λ = {w i , µ i , Σ i , i = 1, ..., N } where each Gaussian corresponds to a visual word and to characterize the image I with the gradient of the normalized log-likelihood according to the GMM model:

f I = F -1/2 λ
∇ λ log P (I|λ); where F λ is the Fisher Information matrix. The similarity between two images I 1 and I 2 , is computed as follows: 2 -||f I1 -f I2 || 1 ; where the f are first normalized to 1.

Text representation. Two information retrieval models were considered: a standard language model and an information based model with a log-logistic distribution, after lemmatization of the texts. We refer to the working notes paper [START_REF] Ah-Pine | XRCE's participation to ImageCLEF 2009[END_REF] for more information. Furthermore, we decided to use query expansion or enrichment, in order to find new clusters in addition to those represented by the example images for topics in part 2. The Chi-Square statistic was used to enrich the query title words with their top ten most similar terms.

Cross-media similarity. The information fusion technique used to combine textual and visual similarities can be understood as a score regularization through a two-step diffusion process, the first step being performed in one mode and the second step being performed in the other one [START_REF] Ah-Pine | XRCE's participation to ImageCLEF 2008[END_REF][START_REF] Ah-Pine | XRCE's participation to ImageCLEF 2009[END_REF]. Let S t and S i respectively be the textual and the visual similarity matrices over the same set of multimedia objects, that are normalized to obtain a similarity value distribution between 0 and 1 for each row. The cross-media similarity matrices that combine two monomedia similarity matrices are defined as follows:

Sim img-txt = κ(S i , k i )S t and Sim txt-img = κ(S t , k t )S i ;

(

where κ(S, k) is a thresholding function that, for all rows of S, puts to zero all values that are lower than the k th highest value and keeps all other components to their initial value (see [START_REF] Ah-Pine | XRCE's participation to ImageCLEF 2009[END_REF] for more details). Let us precise that in the more specific case of information retrieval, given a multimedia query q (q t denoting the text part and q i the image part of q), we similarly have the following cross-media scores: Score img-txt (q i ) = κ(s i , k i ).S t and Score txt-img (q t ) = κ(s t , k t ).S i ; where s t is the similarity row vector of a given textual query q t with a set of multimedia objects (their text part) and s i is respectively, the similarity row vector of a given image query q i with the same set of multimedia objects (but their image part). Finally, given a multimedia query, the final relevance score can be computed as follows:

Score(q) = α t s t + α i s i + α it Score img-txt (q i ) + α ti Score txt-img (q t ) (2)
where the weight distribution was set heuristically to α t = 5/12, α i = 1/4, α it = 1/4, α ti = 1/12.

Since part 1 and part 2 constitute two different kinds of topics, we designed two slightly different approaches that we briefly describe2 before analysing the results they can provide.

Part 1

Description. For each topic in part 1, we start by analyzing its subtopics individually as if they were independent. To this end, we first used text similarity to retrieve relevant multimedia objects. More precisely, we used the image's caption (ICPT) of the subtopic as a text query. This allows us to find a set of M relevant objects based on textual similarities between the text query (image's caption of the subtopic) and the captions of images in the database. Note that since the image subtopic is itself within the database, it is also retrieved in the top M list. From these M retrieved multimedia objects we can compute three similarity matrices (textual, visual and cross-modal) as described in section 2. Based on those matrices, the top M retrieved objects can be re-ranked using either textual, visual or cross-modal similarities. Indeed, given a similarity matrix, we extract from the latter the row similarity corresponding to the subtopic and we re-rank the retrieved objects according to this similarity distribution. In that case, we can see that using only visual and cross-modal similarities actually result in a re-ranking of the top M list since the original ranking was produced by text similarities.

We thus obtain three top M lists from the three subtopics. We finally combine the latter into a single list using a Round Robin merging technique3 .

Analysis. Table 1 shows the results4 with the three modalities: textual (T), visual (I) and cross-modal (X). In this part the diversity (cluster recall measure) was in principle ensured by the fact that each cluster was represented by a subtopic. Therefore we did not apply any additional diversity-seeking re-ranking strategy to the topics of part 1. As far as the notations are concerned, this is denoted by a no in a run's name.

From Table 1, we see that even if the cross-media run ICPT no X reaches the best performance, the improvement over the pure text run, ICPT no T is rather weak. The main reason might be that using the subtopics' image caption and merging the resulting subtopics' top M list with a Round Robin procedure, is already an effictive strategy to address both the precision and the cluster recall.

Part 2 -basic runs

Description. For topics in part 2, we assumed that the three image queries represented three different subtopics. As a consequence, we first applied the same technique as for part 1. It is worth mentioning here that, similarly to part 1, neither the cluster title nor the cluster description were exploited. Therefore, we can obtain the runs ICPT no T, ICPT no I and ICPT no X by considering the Round Robin fusion of the three (re-)ranked lists (using textual, visual or cross-modal similarities), in the same manner as we described previously.

Assuming that the three image subqueries were relevant, we can expect that their lists lead to high precision measures (P10). However, there might be other subtopics that are related to the topic but which are not conveyed by the image subqueries we were given5 . To tackle such an issue, our main idea was to enrich the above obtained lists with objects that remain relevant to the general topic but which are distinct from the given image subqueries. To this end, we proposed to use different sources of information in order to have different aspects of the topic and thus to promote diversity. Accordingly, we used, in addition to the images captions (ICPT), two other query types: the query title (QRW) and the query title enriched with the most similar words (ENT). Again, for these extra queries, the textual information was employed as a pre-filter before using any visual information. In both cases, we first build a top list of M objects by using textual similarities6 : ENT no T and QRW no T respectively.

Aiming to bring further diversity, we can also use different diversity reranking strategies on any of the above lists similarly to our last year's participation in the task. We mainly experimented with two different methods (see [START_REF] Ah-Pine | XRCE's participation to ImageCLEF 2008[END_REF][START_REF] Ah-Pine | XRCE's participation to ImageCLEF 2009[END_REF] for more details):

• A density based re-ranking of the top elements (kdens). The main idea is to select elements that have high density (similar elements) around them as representatives. We used the sum of k nearest neighbors distances as an example measure.

• A clustering based re-ranking of the top elements (clust). Similarly to the previous method, we search images that represent a group of images, except that we use clustering techniques. Indeed, considering the M retrieved multimedia objects, we can first compute three similarity matrices (T, I and X) and then, re-rank the top list with either the density based method (kdens) or the clustering based method (clust) described above. This leads to six additional runs for each query type (see for example Figure 1).

Analysis. While these extra lists (ENT and QRW) were designed to be combined with the ICPT list in order to bring new clusters at the top of the final list, it is interesting to analyze and compare them individually in a first time. Accordingly, Figure 1 shows the performances of all the basic models we used (called basic runs). In the five first rows of Table 2, we recall some of the best basic runs we obtained. Let us analyze these results from different point of views:

• QRW vs ENT: Surprisingly, we can see that query enrichment mostly benefits precision rather than cluster recall. Query enrichment does benefit cluster recall, but to a lesser extent that we would have expected. Besides, re-ranking techniques for query title runs (clust, kdens) do not significantly improve the F1 measure over the baseline run (QRW no T ). On the other hand, a larger improvement is obtained when the same techniques are applied to ENT runs. For example ENT kdens I obtains a large improvement in F1 measure, increasing both precision and cluster recall measures. Overall, we observe that enriching the query allows us to improve the performances in most cases since ENT runs are in general better than QRW ones.

• ICPT: The cross-media ICPT no X is the best of our basic runs, largely outperforming any of the other runs. Another important observation is that no re-ranking techniques (clust, kdens) actually help when using ICPT. In fact. using the Round Robin fusion between subtopics, there may be already enough diversity represented such that the re-ranking techniques bring more noise than useful information • ENT vs ICPT: Overall, enriched queries based runs are precision oriented. On the contrary, images' caption based runs are rather recall oriented. As a result, since those runs are complementary, we could expect their combination to be promising. • Multimodal Runs: There are evidences that taking advantage of the multimodal nature of the objects allows us to outperform monomedia based retrieval. As mentioned previously, the cross-media ICPT no X is a good example but there are more ones. For example, the run ENT clust I, first retrieves a top list of objects on the basis of textual similarities and then uses the visual similarities between those objects and a clustering technique in the goal of avoiding redundancy. We can actually observe that this run performs better than the monomedia run ENT no T in terms of F1. Overall, these observations demonstrate that multimedia and cross-modal techniques are valuable and effective.

• kdens vs clust Regarding the comparison between the two re-ranking techniques, we observe on the one hand that density and clustering are comparable when image similarity is used, but on the other hand, with text similarity or cross-media similarity, clustering generally gives better results. Those re-ranking techniques are really effective on the enriched queries however, as mentioned beforehand, none of these techniques helps the ICPT runs.

Part 2 -combined runs

Description. As mentioned previously, our aim when designing different runs based on different information sources, was to better promote diversity by combining several kinds of results. In that perspective, we used again the Round Robin method to combine several runs. There are many possible combinations among the basic runs that we described previously and no room for an exhausted study. Therefore we selected some of them to be analyzed and compared.

Analysis. Table 2 shows the results of our best basic runs, and some of their combinations. Since we observed that ENT basic runs are generally better than QRW ones, we thus rather consider the use of the ENT runs than the latter ones in the combinations. The best basic ICPT no X run reaches a 74.6% F1 value. The combination of this run with others leads to roughly 80% F1 runs. The run ICPT no X ENT no T is particularly interesting because it is high performing and does not use any re-ranking techniques. Our best combination is ICPT no X ENT kdens I (F1=82%). Therefore, we analyze these two basic runs and their combination at the topic level.

In the top chart of Figure 2, we show the F1 measures of ICPT no X, ENT kdens I and their combination. In the bottom chart we show the cluster recall at 20 (CR20) of the combination against the CR10 of the two basic runs. Our motivation is to analyze whether the retrieved subtopics in the basic runs complement each other7 . We can make the following observations:

• Our system seems to fail on topic 43 but the relevance judgment reveals that there are only 2 relevant images for this topic and only one cluster. We actually found one relevant image so the failure is not really dramatic.

• On average, ICPT no X gets better results than the ENT kdens I, as their respective F1 scores are 74.6% and 71.4%. However, for topics where ENT kdens I results are better, they are much better than ICPT no X ones. In other words, there are a few topics where ENT kdens I makes a real difference over ICPT no X. As we already noticed above enriching queries does not help cluster recall so often. Thus, only queries 27, 29, 35, 37, 40, 45, 48, 49, after fusion, show some improvements in terms of cluster recall. If we look8 at the precision of the different topics of part 2, enriched queries get often better precision than the crossmedia ICPT results. We introduced query enrichment with the hope to find new clusters, but it turns out that most of the time the images' caption and the cross-media are already able to find most of the clusters9 .

• Lastly, our fusion strategy seems robust: the combination does worst than the worst basic run only for one query (query 26). Otherwise, the combination does better than the worst run. This actually confirms that those runs, ICPT no X and ENT kdens I, are complementary. Nevertheless, as far as the combination of basic runs is concerned, we could expect to obtain better results by giving more weight to the cross-media runs than other basic runs, since the former runs are better than the latter ones most of the time.

Conclusion

In this paper we briefly recalled the technologies we used in order to address the Photo retrieval task of ImageCLEF 2009. We then presented a detailed analysis of the different results that our methods can provide. We generated a lot of different basic runs, by varying the type of the initial query text representation and the use or not of a re-ranking technique to increase diversity. We showed that query enrichment benefits more precision than cluster recall, which was somehow unexpected. Moreover, the diversity re-ranking techniques we used, clustering and density, increase the results of enriched queries, but not the results of other text representations query title and images' caption. However, these improvements do not outperform the basic run which uses the images' caption and cross-media measures without any re-ranking method. The latter run is actually our best basic run which shows again that our cross-media technique is effective. Finally, textual similarities, using the images' caption particularly, allow us to obtain a first interesting baseline, that we can significantly improve in a second step, by integrating visual and cross-modal similarities. These basic runs can further be improved by combining some of them in order to increase the F1 measure. In that perspective, combining basic runs that use different information sources and media is very beneficial.

Fig. 1 .

 1 Fig. 1. Basic Runs for topics in part 2.

Fig. 2 .

 2 Fig. 2. F1 and cluster recall performances by topic for part 2.

Table 1 .

 1 Results for part 1 using different modalities.

	Modality	CR10 P10 F1
	ICPT no T	83.9 78.4 81.0
	ICPT no I	75.2 60.8 67.2
	ICPT no X	83.7 79.6 81.6
	(Old) ICPT no X 82.9 76.8 79.7

Table 2 .

 2 Best basic runs and some of their combinations for part 2 topics.

	Run name	CR10 P10 F1
	ENT clust I	65.8 78.0 71.4
	ENT clust T	63.4 79.6 70.6
	ENT kdens I	62.6 83.2 71.4
	ENT no T	58.5 78.4 67.0
	ICPT no X	76.8 72.4 74.6
	ICPT no X ENT clust X 84.0 78.0 80.9
	ICPT no X ENT clust I 82.4 78.8 80.6
	ICPT no X ENT kdens I 82.5 81.6 82.0
	ICPT no X ENT no T 83.1 78.8 80.9

The authors also want to thank Florent Perronin for his code allowing to compute the Fisher Vectors and to Yan Liu for his help in preprocessing the visual data.

For a more detailed description, see Algorithm 1 and Algorithm 2 in the working notes paper[START_REF] Ah-Pine | XRCE's participation to ImageCLEF 2009[END_REF].

The images of the subtopics and their exact duplicates are first removed from the different lists.

The results are slightly better than the official runs. This is due to the correction of a small bug in the code.

As an example, in topic 37, images about Paris Hilton, Paris-Brest and Paris-Nice clearly did not address all the aspects of the topic Paris.

Note that we have a single topic list for ENT and QRW as no subtopic is assumed.

If we only considered the CR10 of the combined list, this would take into account only the top 5 elements of each individual lists.

Figure omitted due to space limitation.

For 11 out of 25 topics we have CR10=1 for ICPT no X.

Acknowledgments This work was partially supported by the french projects Omnia ANR-06-CIS6-01 and Fragrances ANR-08-CORD-008.


Julien Ah-Pine
email: julien.ah-pine@xrce.xerox.com

Guillaume Jacquet
email: guillaume.jacquet@xrce.xerox.com

Clique-Based Clustering for improving Named Entity Recognition systems

Clique-based clustering for improving named entity recognition systems

Julien Ah-Pine, Guillaume

Introduction

In Information Extraction domain, named entities (NEs) are one of the most important textual units as they express an important part of the meaning of a document. Named entity recognition (NER) is not a new domain (see MUC1 and ACE2 conferences) but some new needs appeared concerning NEs processing. For instance the NE Oxford illustrates the different ambiguity types that are interesting to address:

• intra-annotation ambiguity: Wikipedia lists more than 25 cities named Oxford in the world • systematic inter-annotation ambiguity: the name of cities could be used to refer to the university of this city or the football club of this city. This is the case for Oxford or Newcastle • non-systematic inter-annotation ambiguity:

Oxford is also a company unlike Newcastle.

The main goal of our system is to act in a complementary way with an existing NER system, in order to enhance its results. We address two kinds of issues: first, we want to detect and correctly annotate corpus-specific NEs3 that the NER system could have missed; second, we want to correct some wrong annotations provided by the existing NER system due to ambiguity. In section 3, we give some examples of such corrections.

The paper is organized as follows. We present, in section 2, the global architecture of our system and from §2.1 to §2.6, we give details about each of its steps. In section 3, we present the evaluation of our approach when it is combined with other classic NER systems. We show that the resulting hybrid systems perform better with respect to F-measure. In the best case, the latter increased by 4.84 points. Furthermore, we give examples of successful correction of NEs annotation thanks to our approach. Then, in section 4, we discuss about related works. Finally we sum up the main points of this paper in section 5.

Description of the system

Given a corpus, the main objectives of our system are: to detect potential NEs; to compute the possible annotations for each NE and then; to annotate each occurrence of these NEs with the right annotation by analyzing its local context.

We assume that this corpus dependent approach allows an easier NE annotation. Indeed, even if a NE such as Oxford can have many annotation types, it will certainly have less annotation possibilities in a specific corpus.

Figure 1 presents the global architecture of our system. The most important part concerns steps 3 ( §2.3) and 4 ( §2.4). The aim of these subprocesses is to group NEs which have the same annotation with respect to a given context. On the one hand, clique-based methods (see §2.3 for Figure 1: General description of our system details on cliques) are interesting as they allow the same NE to be in different cliques. In other words, cliques allow to represent the different possible annotations of a NE. The clique-based approach drawback however, is the over production of cliques which corresponds to an artificial over production of possible annotations for a NE. On the other hand, clustering methods aim at structuring a data set and such techniques can be seen as data compression processes. However, a simple NEs hard clustering doesn't allow a NE to be in several clusters and thus to express its different annotations. Then, our proposal is to combine both methods in a clique-based clustering framework. This combination leads to a soft-clustering approach that we denote CBC system. The following paragraphs, from 2.1 to 2.6, describe the respective steps mentioned in Figure 1.

Detection of potential Named Entities

Different methods exist for detecting potential NEs. In our system, we used some lexicosyntactic constraints to extract expressions from a corpus because it allows to detect some corpusspecific NEs. In our approach, a potential NE is a noun starting with an upper-case letter or a noun phrase which is (see [START_REF] Ehrmann | Vers une double annotation des entités nommées[END_REF] for similar use):

• a governor argument of an attribute syntactic relation with a noun as governee argument (e.g. president attribute ----→ George Bush) • a governee argument of a modifier syntactic relation with a noun as a governor argument (e.g.

company modifier

← ----Coca-Cola). The list of potential NEs extracted from the corpus will be denoted NE and the number of NEs |NE|.

Distributional space of NEs

The distributional approach aims at evaluating a distance between words based on their syntactic distribution. This method assumes that words which appear in the same contexts are semantically similar [START_REF] Harris | Structural Linguistics[END_REF].

To construct the distributional space associated to a corpus, we use a robust parser (in our experiments, we used XIP parser [START_REF] Aït | Robustness beyond shallowness: incremental dependency parsing[END_REF]) to extract chunks (i.e. nouns, noun phrases, . . . ) and syntactic dependencies between these chunks. Given this parser's output, we identify triple instances. Each triple has the form w 1 .R.w 2 where w 1 and w 2 are chunks and R is a syntactic relation [START_REF] Lin | Using collocation statistics in information extraction[END_REF], [START_REF] Kilgarriff | The sketch engine[END_REF].

One triple gives two contexts (1.w 1 .R and 2.w 2 .R) and two chunks (w 1 and w 2 ). Then, we only select chunks w which belong to NE. Each point in the distributional space is a NE and each dimension is a syntactic context. CT denotes the set of all syntactic contexts and |CT| represents its cardinal.

We illustrate this construction on the sentence "provide Albania with food aid". We obtain the three following triples (note that aid and food aid are considered as two different chunks): We also use an heuristic in order to reduce the over production of chunks and contexts: in our experiments for example, each NE and each context should appear more than 10 times in the corpus for being considered.

D is the resulting (|NE| × |CT|) NE-Context matrix where e i : i = 1, . . . , |NE| is a NE and c j : j = 1, . . . , |CT| is a syntactic context. Then we have:

D(e i , c j ) = Nb. of occ. of c j associated to e i (1)

Cliques of NEs computation

A clique in a graph is a set of pairwise adjacent nodes which is equivalent to a complete subgraph. A maximal clique is a clique that is not a subset of any other clique. Maximal cliques computation was already employed for semantic space representation [START_REF] Ploux | Construction d'espaces sémantiques à l'aide de dictionnaires de synonymes[END_REF]. In this work, cliques of lexical units are used to represent a precise meaning. Similarly, we compute cliques of NEs in order to represent a precise annotation.

For example, Oxford is an ambiguous NE but a clique such as <Cambridge, Oxford, Edinburgh University, Edinburgh, Oxford Univer-sity> allows to focus on the specific annotation <organization> (see [START_REF] Ehrmann | Vers une double annotation des entités nommées[END_REF] for similar use).

Given the distributional space described in the previous paragraph, we use a probabilistic framework for computing similarities between NEs. The approach that we propose is inspired from the language modeling framework introduced in the information retrieval field (see for example [START_REF] Lavrenko | Relevance models in information retrieval[END_REF]). Then, we construct cliques of NEs based on these similarities.

Similarity measures between NEs

We first compute the maximum likelihood estimation for a NE e i to be associated with a context c j :

P ml (c j |e i ) = D(e i ,c j ) |e i | , where |e i | = |CT| j=1 D(e i , c j ) is the total occurrences of the NE e i in the corpus.
This leads to sparse data which is not suitable for measuring similarities. In order to counter this problem, we use the Jelinek-Mercer smoothing method: D (e i , c j ) = λP ml (c j |e i ) + (1λ)P ml (c j |CORP) where CORP is the corpus and P ml (c j |CORP) = P i D(e i ,c j ) P i,j D(e i ,c j ) . In our experiments we took λ = 0.5.

Given D , we then use the cross-entropy as a similarity measure between NEs. Let us denote by s this similarity matrix, we have:

s(e i , e i ) = - c j ∈CT D (e i , c j ) log(D (e i , c j )) (2)

From similarity matrix to adjacency matrix

Next, we convert s into an adjacency matrix denoted ŝ. In a first step, we binarize s as follows. Let us denote {e i 1 , . . . , e i |NE| }, the list of NEs ranked according to the descending order of their similarity with e i . Then, L(e i ) is the list of NEs which are considered as the nearest neighbors of e i according to the following definition:

L(e i ) =
(3)

{e i 1 , ..., e i p : p i =1 s(e i , e i i ) |NE| i =1 s(e i , e i ) ≤ a; p ≤ b} where a ∈ [0, 1] and b ∈ {1, . . . , |NE|}. L(e i )
gathers the most significant nearest neighbors of e i by choosing the ones which bring the a most relevant similarities providing that the neighborhood's size doesn't exceed b. This approach can be seen as a flexible k-nearest neighbor method. In our experiments we chose a = 20% and b = 10. Finally, we symmetrize the similarity matrix as follows and we obtain ŝ:

ŝ(e i , e i ) =
1 if e i ∈ L(e i ) or e i ∈ L(e i ) 0 otherwise (4)

Cliques computation

Given ŝ, the adjacency matrix between NEs, we compute the set of maximal cliques of NEs denoted CLI. Then, we construct the matrix T of general term:

T (cli k , e i ) = 1 if e i ∈ cli k 0 otherwise (5)
where cli k is an element of CLI. T will be the input matrix for the clustering method.

In the following, we also use cli k for denoting the vector represented by (T (cli k , e 1 ), . . . , T (cli k , e |NE| )).

Figure 2 shows some cliques which contain Oxford that we can obtain with this method. This figure also illustrates the over production of cliques since at least cli8, cli10 and cli12 can be annotated as <organization>. This clustering technique must be able to construct "pure" clusters in order to have precise annotations. In that case, it is desirable to avoid fixing the number of clusters. That's the reason why we propose to use the Relational Analysis approach described below.

The Relational Analysis approach

We propose to apply the Relational Analysis approach (RA) which is a clustering model that doesn't require to fix the number of clusters [START_REF] Michaud | Optimisation en analyse de données relationnelles[END_REF], [START_REF] Bédécarrax | Relational analysis and dictionnaries[END_REF]. This approach takes as input a similarity matrix. In our context, since we want to cluster cliques of NEs, the corresponding similarity matrix S between cliques is given by the dot products matrix taken from T : S = T • T . The general term of this similarity matrix is: S(cli k , cli k ) = S kk = cli k , cli k . Then, we want to maximize the following clustering function:

∆(S, X) = (6) |CLI| k,k =1 S kk - (k ,k )∈S + S k k |S + | cont kk X kk where S + = {(cli k , cli k ) : S kk > 0}.
In other words, cli k and cli k have more chances to be in the same cluster providing that their similarity measure, S kk , is greater or equal to the mean average of positive similarities.

X is the solution we are looking for. It is a binary relational matrix with general term: X kk = 1, if cli k is in the same cluster as cli k ; and X kk = 0, otherwise. X represents an equivalence relation. Thus, it must respect the following properties:

• binarity: X kk ∈ {0, 1}; ∀k, k , • reflexivity: X kk = 1; ∀k, • symmetry: X kk -X k k = 0; ∀k, k , • transitivity: X kk + X k k -X kk ≤ 1; ∀k, k , k .
As the objective function is linear with respect to X and as the constraints that X must respect are linear equations, we can solve the clustering problem using an integer linear programming solver. However, this problem is NP-hard. As a result, in practice, we use heuristics for dealing with large data sets.

The Relational Analysis heuristic

The presented heuristic is quite similar to another algorithm described in [START_REF] Hartigan | Clustering Algorithms[END_REF]) known as the "leader" algorithm. But unlike this last approach which is based upon euclidean distances and inertial criteria, the RA heuristic aims at maximizing the criterion given in (6). A sketch of this heuristic is given in Algorithm 1, (see [START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF] for further details). We have to provide a number of iterations or/and a delta threshold in order to have an approximate solution in a reasonable processing time. Besides, it is also required a maximum number of clusters but since we don't want to fix this parameter, we put by default κ max = |CLI|.

Basically, this heuristic has a O(nbitr × κ max × |CLI|) computation cost. In general terms, we can assume that nbitr << |CLI|, but not κ max << |CLI|. Thus, in the worst case, the algorithm has a O(κ max × |CLI|) computation cost.

Figure 3 gives some examples of clusters of cliques 5 obtained using the RA approach. Now, we want to exploit the clusters of cliques in order to annotate NE occurrences. Then, we need to construct a NE resource where for each pair (NE x syntactic context) we have an annotation. To this end, we need first, to assign a cluster to each pair (NE x syntactic context) ( §2.5.1) and second, to assign each cluster an annotation ( §2.5.2).

Cluster assignment to each pair (NE x syntactic context)

For each cluster clu l we provide a score F c (c j , clu l ) for each context c j and a score 5 We only represent the NEs and their frequency in the cluster which corresponds to the number of cliques which contain the NEs. Furthermore, we represent the most relevant contexts for this cluster according to equation ( 7) introduced in the following.

F e (e i , clu l ) for each NE e i . These scores6 are given by:

F c (c j , clu l ) = (7) e i ∈clu l D(e i , c j ) |NE| i=1 D(e i , c j ) e i ∈clu l 1 {D(e i ,c j ) =0}
where 1 {P } equals 1 if P is true and 0 otherwise.

F e (e i , clu l ) = #(clu l , e i ) (8)
Given a NE e i and a syntactic context c j , we now introduce the contextual cluster assignment matrix A ctxt (e i , c j ) as follows: A ctxt (e i , c j ) = clu * where: clu * = Argmax {clu l :clu l e i ;Fe(e i ,clu l )>1} F c (c j , clu l ).

In other words, clu * is the cluster for which we find more than one occurrence of e i and the highest score related to the context c j .

Furthermore, we compute a default cluster assignment matrix A def , which does not depend on the local context: A def (e i ) = clu • where:

clu • = Argmax {clu l :clu l {cli k :cli k e i }} |cli k |.
In other words, clu • is the cluster containing the biggest clique cli k containing e i .

Clusters annotation

So far, the different steps that we have introduced were unsupervised. In this paragraph, our aim is to give a correct annotation to each cluster (hence, to all NEs in this cluster). To this end, we need some annotation seeds and we propose two different semi-supervised approaches (regarding the classification given in [START_REF] Nadeau | A survey of Named Entity Recognition and Classification[END_REF]). The first one is the manual annotation of some clusters. The second one proposes an automatic cluster annotation and assumes that we have some NEs that are already annotated.

Manual annotation of clusters This method is fastidious but it is the best way to match the corpus data with a specific guidelines for annotating NEs. It also allows to identify new types of annotation. We used the ACE2007 guidelines for manually annotating each cluster. However, our CBC system leads to a high number of clusters of cliques and we can't annotate each of them. Fortunately, it also leads to a distribution of the clusters' size (number of cliques by cluster) which is similar to a Zipf distribution. Consequently, in our experiments, if we annotate the 100 biggest clusters, we annotate around eighty percent of the detected NEs (see §3).

Automatic annotation of clusters

We suppose in this context that many NEs in NE are already annotated. Thus, under this assumption, we have in each cluster provided by the CBC system, both annotated and non-annotated NEs. Our goal is to exploit the available annotations for refining the annotation of a cluster by implicitly taking into account the syntactic contexts and for propagating the available annotations to NEs which have no annotation.

Given a cluster clu l of cliques, #(clu l , e i ) is the weight of the NE e i in this cluster: it is the number of cliques in clu l that contain e i . For all annotations a p in the set of all possible annotations AN, we compute its associated score in cluster clu l : it is the sum of the weights of NEs in clu l that is annotated a p .

Then, if the maximal annotation score is greater than a simple majority (half) of the total votes 7 , we assign the corresponding annotation to the cluster. We precise that the annotation <none> 8 is processed in the same way as any other annotations. Thus, a cluster can be globally annotated <none>. The limit of this automatic approach is that it doesn't allow to annotate new NE types than the ones already available.

In the following, we will denote by A clu (clu l ) the annotation of the cluster clu l .

The cluster annotation matrix A clu associated to the contextual cluster assignment matrix A ctxt and the default cluster assignment matrix A def introduced previously will be called the CBC system's NE resource (or shortly the NE resource).

NEs annotation processes using the NE resource

In this paragraph, we describe how, given the CBC system's NE resource, we annotate occurrences of NEs in the studied corpus with respect to its local context. We precise that for an occurrence of a NE e i its associated local context is the set of syntactical dependencies c j in which e i is involved. 7 The total votes number is given by P e i ∈clu l #(clu l , ei). 8 The NEs which don't have any annotation.

NEs annotation process for the CBC system

Given a NE occurrence and its local context we can use A ctxt (e i , c j ) and A def (e i ) in order to get the default annotation A clu (A def (e i )) and the list of contextual annotations {A clu (A ctxt (e i , c j ))} j . Then for annotating this NE occurrence using our NE resource, we apply the following rules:

• if the list of contextual annotations {A clu (A ctxt (e i , c j ))} j is conflictual, we annotate the NE occurrence as <none>, • if the list of contextual annotations is nonconflictual, then we use the corresponding annotation to annotate the NE occurrence • if the list of contextual annotations is empty, we use the default annotation A clu (A def (e i )).

The NE resource plus the annotation process described in this paragraph lead to a NER system based on the CBC system. This NER system will be called CBC-NER system and it will be tested in our experiments both alone and as a complementary resource.

NEs annotation process for an hybrid system

We place ourselves into an hybrid situation where we have two NER systems (NER 1 + NER 2) which provide two different lists of annotated NEs. We want to combine these two systems when annotating NEs occurrences. Therefore, we resolve any conflicts by applying the following rules:

• If the same NE occurrence has two different annotations from the two systems then there are two cases. If one of the two system is CBC-NER system then we take its annotation; otherwise we take the annotation provided by the NER system which gave the best precision. • If a NE occurrence is included in another one we only keep the biggest one and its annotation. For example, if Jacques Chirac is annotated <person> by one system and Chirac by <person> by the other system, then we only keep the first annotation. • If two NE occurrences are contiguous and have the same annotation, we merge the two NEs in one NE occurrence.

Experiments

The system described in this paper rather target corpus-specific NE annotation. Therefore, our ex-periments will deal with a corpus of recent news articles (see [START_REF] Shinyama | Named Entity Discovery using comparable news articles[END_REF] for motivations regarding our corpus choice) rather than well-known annotated corpora. Our corpus is constituted of news in English published on the web during two weeks in June 2008. This corpus is constituted of around 300,000 words (10Mb) which doesn't represent a very large corpus. These texts were taken from various press sources and they involve different themes (sports, technology, . . . ). We extracted randomly a subset of articles and manually annotated 916 NEs (in our experiments, we deal with three types of annotation namely <person>, <organization> and <location>). This subset constitutes our test set.

In our experiments, first, we applied the XIP parser [START_REF] Aït | Robustness beyond shallowness: incremental dependency parsing[END_REF] to the whole corpus in order to construct the frequency matrix D given by (1). Next, we computed the similarity matrix between NEs according to (2) in order to obtain ŝ defined by (4). Using the latter, we computed cliques of NEs that allow us to obtain the assignment matrix T given by ( 5). Then we applied the clustering heuristic described in Algorithm 1. At this stage, we want to build the NE resource using the clusters of cliques. Therefore, as described in §2.5, we applied two kinds of clusters annotations: the manual and the automatic processes. For the first one, we manually annotated the 100 biggest clusters of cliques. For the second one, we exploited the annotations provided by XIP NER [START_REF] Brun | Intertwining deep syntactic processing and named entity detection[END_REF] and we propagated these annotations to the different clusters (see §2.5.2).

The different materials that we obtained constitute the CBC system's NE resource. Our aim now is to exploit this resource and to show that it allows to improve the performances of different classic NER systems.

The different NER systems that we tested are the following ones:

• CBC-NER system M (in short CBC M) based on the CBC system's NE resource using the manual cluster annotation (line 1 in Table 1), • CBC-NER system A (in short CBC A) based on the CBC system's NE resource using the automatic cluster annotation (line 1 in Table 1), • XIP NER or in short XIP [START_REF] Brun | Intertwining deep syntactic processing and named entity detection[END_REF] ner-eng-ie.crf-3-all2008-distsim.ser.gz [START_REF] Finkel | Incorporating non-local information into information extraction systems by gibbs sampling[END_REF] (line 3 in Table 1), • GATE NER or in short GATE [START_REF] Cunningham | GATE: A framework and graphical development environment for robust NLP tools and applications[END_REF] (line 4 in Table 1), • and several hybrid systems which are given by the combination of pairs taken among the set of the three last-mentioned NER systems (lines 5 to 7 in Table 1). Notice that these baseline hybrid systems use the annotation combination process described in §2.6.1.

In Table 1 we first reported in each line, the results given by each system when they are applied alone (figures in italics). These performances represent our baselines. Second, we tested for each baseline system, an extended hybrid system that integrates the CBC-NER systems (with respect to the combination process detailed in §2.6.2).

The first two lines of Table 1 show that the two CBC-NER systems alone lead to rather poor results. However, our aim is to show that the CBC-NER system is, despite its low performances alone, complementary to other basic NER systems. In other words, we want to show that the exploitation of the CBC system's NE resource is beneficial and non-redundant compared to other baseline NER systems.

This is actually what we obtained in Table 1 as for each line from 2 to 7, the extended hybrid systems that integrate the CBC-NER systems (M or A) always perform better than the baseline either in terms of precision9 or recall. For each line, we put in bold the best performance according to the F-measure.

These results allow us to show that the NE resource built using the CBC system is complementary to any baseline NER systems and that it allows to improve the results of the latter.

In order to illustrate why the CBC-NER systems are beneficial, we give below some examples taken from the test corpus for which the CBC system A had allowed to improve the performances by respectively disambiguating or correcting a wrong annotation or detecting corpus-specific NEs.

First, in the sentence "From the start, his parents, Lourdes and Hemery, were with him.", the baseline hybrid system Stanford + XIP annotated the ambiguous NE "Lourdes" as <location> whereas Stanford + XIP + CBC A gave the correct annotation <person>.

Second, in the sentence "Got 3 percent chance of survival, what ya gonna do?" The back read, "A) Fight Through, b) Stay Strong, c) Overcome Because I Am a Warrior.", the baseline hybrid system Stanford + XIP annotated "Warrior" as <organization> whereas Stanford + XIP + CBC A corrected this annotation with <none>.

Finally, in the sentence "Matthew, also a favorite to win in his fifth and final appearance, was stunningly eliminated during the semifinal round Friday when he misspelled "secernent".", the baseline hybrid system Stanford + XIP didn't give any annotation to "Matthew" whereas Stanford + XIP + CBC A allowed to give the annotation <person>.

Related works

Many previous works exist in NEs recognition and classification. However, most of them do not build a NEs resource but exploit external gazetteers [START_REF] Bunescu | Using encyclopedic knowledge for named entity disambiguation[END_REF], [START_REF] Cucerzan | Large-scale named entity disambiguation based on wikipedia data[END_REF].

A recent overview of the field is given in [START_REF] Nadeau | A survey of Named Entity Recognition and Classification[END_REF]. According to this paper, we can classify our method in the category of semi-supervised approaches. Our proposal is close to [START_REF] Cucchiarelli | Unsupervised Named Entity Recognition using syntactic and semantic contextual evidence[END_REF] as it uses syntactic relations ( §2.2) and as it relies on existing NER systems ( §2.6.2). However, the particularity of our method concerns the clustering of cliques of NEs that allows both to represent the different annotations of the NEs and to group the latter with respect to one precise annotation according to a local context.

Regarding this aspect, [START_REF] Lin | Using collocation statistics in information extraction[END_REF][START_REF] Lin | Induction of semantic classes from natural language text[END_REF][START_REF] Ngonga | Signum a graph algorithm for terminology extraction[END_REF] also use a clique computation step and a clique merging method. However, they do not deal with ambiguity of lexical units nor with NEs. This means that, in their system, a lexical unit can be in only one merged clique.

From a methodological point of view, our proposal is also close to [START_REF] Ehrmann | Vers une double annotation des entités nommées[END_REF] as the latter proposes a system for NEs finegrained annotation, which is also corpus dependent. However, in the present paper we use all syntactic relations for measuring the similarity between NEs whereas in the previous mentioned work, only specific syntactic relations were exploited. Moreover, we use clustering techniques for dealing with the issue related to over production of cliques.

In this paper, we construct a NE resource from the corpus that we want to analyze. In that context, [START_REF] Pasca | Acquisition of categorized named entities for web search[END_REF] presents a lightly supervised method for acquiring NEs in arbitrary categories from unstructured text of Web documents. However, Pasca wants to improve web search whereas we aim at annotating specific NEs of an analyzed corpus. Besides, as we want to focus on corpus-specific NEs, our work is also related to [START_REF] Shinyama | Named Entity Discovery using comparable news articles[END_REF]. In this work, the authors found a significant correlation between the similarity of the time series distribution of a word and the likelihood of being a NE. This result motivated our choice to test our approach on recent news articles rather than on well-known annotated corpora.

Conclusion

We propose a system that allows to improve NE recognition. The core of this system is a cliquebased clustering method based upon a distributional approach. It allows to extract, analyze and discover highly relevant information for corpusspecific NEs annotation. As we have shown in our experiments, this system combined with another one can lead to strong improvements. Other applications are currently addressed in our team using this approach. For example, we intend to use the concept of clique-based clustering as a soft clustering method for other issues.

Figure 2 :

 2 Figure 2: Examples of cliques containing Oxford

Algorithm 1

 1 RA heuristicRequire: nbitr = number of iterations; κmax = maximal number of clusters; S the similarity matrixm ← P (k,k )∈S + S kk |S + |Take the first clique cli k as the first element of the first cluster κ = 1 where κ is the current number of cluster for q = 1 to nbitr do for k = 1 to |CLI| do for l = 1 to κ do Compute the contribution of clique cli k with cluster clu l : cont l = P cli k ∈clu l (S kk -m) end for clu l * is the cluster id which has the highest contribution with clique cli k and cont l * is the correspondingcontribution value if (cont l * < (S kk -m)) ∧ (κ < κmax) thenCreate a new cluster where clique cli k is the first element and κ ← κ + 1 else Assign clique cli k to cluster clu l * if the cluster where was taken cli k before its new assignment, is empty then κ ← κ -1 end if end if end for end for

Figure 3 :

 3 Figure 3: Examples of clusters of cliques (only the NEs are represented) and their associated contexts

  (line 2 in Table 1), • Stanford NER (or in short Stanford) associated to the following model provided by the tool and which was trained on different news

		Systems	Prec.	Rec.	F-me.
	1	CBC-NER system M CBC-NER system A	71.67 23.47 35.36 70.66 32.86 44.86
		XIP NER	77.77 56.55 65.48
	2	XIP + CBC M	78.41 60.26 68.15
		XIP + CBC A	76.31 60.48 67.48
		Stanford NER	67.94 68.01 67.97
	3	Stanford + CBC M	69.40 71.07 70.23
		Stanford + CBC A	70.09 72.93 71.48
		GATE NER	63.30 56.88 59.92
	4	GATE + CBC M	66.43 61.79 64.03
		GATE + CBC A	66.51 63.10 64.76
		Stanford + XIP	72.85 75.87 74.33
	5	Stanford + XIP + CBC M	72.94 77.70 75.24
		Stanford + XIP + CBC A	73.55 78.93 76.15
		GATE + XIP	69.38 66.04 67.67
	6	GATE + XIP + CBC M	69.62 67.79 68.69
		GATE + XIP + CBC A	69.87 69.10 69.48
		GATE + Stanford	63.12 69.32 66.07
	7	GATE + Stanford + CBC M	65.09 72.05 68.39
		GATE + Stanford + CBC A	65.66 73.25 69.25
	Table 1: Results given by different hybrid NER
	systems and coupled with the CBC-NER system
		corpora (CoNLL, MUC6, MUC7 and ACE):

http://www-nlpir.nist.gov/related projects/muc/

http://www.nist.gov/speech/tests/ace

In our definition a corpus-specific NE is the one which does not appear in a classic NEs lexicon. Recent news articles for instance, are often constituted of NEs that are not in a classic NEs lexicon.

In the context 1.VERB:provide.I-OBJ, the figure 1 means that the verb provide is the governor argument of the Indirect OBJect relation.

For data fusion tasks in information retrieval field, the scoring method in equation (7) is denoted CombMNZ[START_REF] Fox | Combination of multiple searches[END_REF]. Other scoring approaches can be used see for example[START_REF] Cucchiarelli | Unsupervised Named Entity Recognition using syntactic and semantic contextual evidence[END_REF].

Except for XIP+CBC A in line 2 where the precision is slightly lower than XIP's one.