J Ah-Pine

C Cifarelli

S Clinchant

G Csurka

J M Renders

XRCE's Participation to ImageCLEF 2008

Keywords: H.3 [Information Storage and Retrieval]: H.3.1 Content Analysis and Indexing, H.3.3 Information Search and Retrieval, H.3.4 Systems and Software, H.3.7 Digital Libraries, H.2.3 [Database Managment]: Languages-Query Languages Measurement, Performance, Experimentation Cross-media information retrieval, Trans-media relevance feedback, diversity-based re-ranking

This year, our participation to ImageCLEF 2008 (Photo Retrieval sub-task) was motivated by trying to address three different problems: visual concept detection and its exploitation in a retrieval context, multimedia fusion methods for improved retrieval performance and diversity-based re-ranking methods. From a purely visual perspective, the representation based on Fisher vectors derived from a generative mixture model appeared to be efficient for both visual concept detection and content-based image retrieval. From a multimedia perspective, we used an intermediate fusion approach, based on cross-media relevance feedback that can be seen as a multigraph-based query regularization method with alternating steps. The combination allowed to improve both mono-media systems by more than 50% (relative). Finally, as one of main goals of the organizers was to promote both relevance and diversity in the retrieval outputs, we designed and assessed several re-ranking strategies that turned out to preserve standard retrieval performance (such at precision at 20 or mean average precision) while significantly decreasing the redundancy in the top documents.

Introduction

In ImageCLEFphoto 2007, the issue we wanted to address was the semantic gap between text and image in retrieval tasks. Indeed, the challenges proposed by ImageCLEF these last years and particularly in the context of the Photo retrieval task, are well-adapted to investigate that kind of problems as we have at our disposal images that are particularly well-described from a textual point of view. In the photo retrieval task, the multi-media objects are constituted of some text and some image that correspond to two different kinds of information from a semantic point of view. Thus, the scientific challenge was to exploit in an efficient manner these two types of information in order to improve the search results.

In last year's session, we addressed the question of combining textual and visual information by developing an intermediate fusion approach which allows to go further than late or early fusion methods [START_REF] Clinchant | Xrce's participation to imageclef 2007[END_REF]. The results we obtained showed that our proposal allows to outperform either monomedia-based retrieval or classical late or early fusion-based retrieval.

In ImageCLEFphoto 2008, however, the main goal is to promote diversity among the first search results. We address this issue using a two-step approach. The first step is to ignore the question of diversity. In other words, we first try to find the most relevant objects using the material introduced in [START_REF] Clinchant | Xrce's participation to imageclef 2007[END_REF]. Then, in a second step, we re-rank the first relevant objects by taking into account their mutual similarities in order to avoid redundancy and thus to promote diversity.

The present working note explains the different approaches that we investigated for designing and developing methods that tackle the challenges proposed in ImageCLEFphoto 2008. This was an opportunity to both enhance the system we developed last year and to implement methods which aims at incorporating diversity into the search results.

The document is organized as follows.

Section 2 is devoted to standard retrieval based on the textual part of the photos. In particular, the aim of the experiments reported in this section was to use external resources for enriching the textual description of both the objects and the queries. Two kinds of resources were used: the first one is rather linguistic and consists for example, in adding synonyms of terms; the second one is rather "cross-media oriented" as it aims at adding visual concepts obtained after processing the images. Such visual concepts are typically the categories found by an image categorizer system.

In section 3, we detail the different experiments we made in the context of image retrieval and classification. First we briefly remember the representation of images with Fisher Vectors (subsection 3.1). In subsection 3.2 we describe our image categorization method used in the ImageClef Visual Concept Detection subtask and in subsection 3.3 our image retrieval system applied to the ImageCLEFPhoto task is detailed. In subsection 3.4 we propose different strategies to incorporate diversity (i.e. to reduce redundancy) in the top retrieved photos, and in the last subsection 3.4.3, we give some further precisions concerning the submitted AUTO-IMAGE runs.

In section 4, we present the system we developed for multi-media information retrieval. First, we briefly recall in subsection 4.1 the approach we defined in [START_REF] Clinchant | Xrce's participation to imageclef 2007[END_REF] concerning intermediate fusion between different mono-modal sources. Second, in subsection 4.2, we explain the different methods we implemented for promoting diversity into the multi-media search results, and in subsection 4.2.3 we present the characteristics of the different AUTO-TXTIMG runs we have submitted.

The last section is, as usual, devoted to a set of conclusions we can draw from the experimental results of ImageCLEF 2008.

Text Retrieval

One axis of research that we wanted to investigate in this session of ImageCLEF was the use of external resources (thesauri) for enriching the textual side of the objects (image description / queries) of the task. The idea is to exploit such resource to compensate for:

• the relative sparsity of the textual representation of the photos (even if, this year, the textual part of the photos included a more detailed description of its content);

• the gap between the lexical fields of these descriptions and the queries : queries are expressed in a more abstract way than the factual description of the photos.

Another issue that we wanted to address was the use of the visual concepts provided by the organizers as extra "textual words", refining the original textual representation of the photo by higher-level visual information.

As basic text retrieval engine, we used the LEMUR Toolkit for Information Retrieval [11], adopting the Language Modeling framework [START_REF] Ponte | A language modelling approach to information retrieval[END_REF] to retrieve and rank relevant objects with respect to the textual part of the query. For each photo, the title, location and description fields were simply concatenated to form a single document; these documents were then linguistically preprocessed (lemmatization and stop-word removal), before being indexed by the LEMUR tool. Dirichlet smoothing [START_REF] Zhai | A study of smoothing methods for language models applied to ad hoc to information retrieval[END_REF] was applied in the retrieval phase, with a parameter which is directly related to the average document length (this parameter choice strategy was also adopted when using enriched documents). Documents are ranked by decreasing similarity with respect to the query, the similarity being defined as the cross-entropy between the query model and the document (smoothed) language model.

The first variant we developed consisted in exploiting the English Open Office thesaurus1 to enrich the textual description of the photos and/or the queries. Several strategies can be chosen. We chose the following ones:

• Document enrichment: we added all the synonyms and broader terms to the terms of the original description, when they are covered by some thesaurus entry; as we wanted to give more weight to the original terms, the latter ones are artificially replicated 15 times.

• Query enrichment: we added all the synonyms and narrower terms to the terms of the original description, when available; as we wanted to give more weight to the original terms, the latter ones are artificially replicated 5 times.

Note that we also simultaneously enriched both the queries and the documents, but this resulted in performance deterioration (too much noise introduced).

As pseudo-relevance feedback (PRF) is another way to do query expansion, we systematically ran experiments with and without pseudo-relevance feedback for each setting (baseline, document enrichment, query enrichment). The ten top terms of the ten top documents were used to expand the initial query language model by convex linear combination (coefficient =0.6 for the feedback model); query model updating was based on the mixture model method [START_REF] Zhai | Model-based feedback in the kl-divergence retrieval model[END_REF]. The performance (Mean Average Precision and Precision@20) is given in Table 1 It clearly appears that combining document enrichment by thesaurus and query expansion by PRF (using the thesaurus-enriched documents in the first feedback phase) gives the best results. Doing query semantic enrichment followed by PRF (using the thesaurus-enriched query in the first feedback phase) gives slightly worse results. In any case, the use of this external resource is beneficial with respect to a standard PRF query expansion.

The second variant we developed aimed at assessing the benefits of introducing the Visual Concepts, as produced by two generic Visual Concept Detectors (we refer to the subsection 3.2 of this note and to the Visual Concept Detection sub-task of ImageCLEF 2008 for further information). These two detectors are designated by XRCE's and RWTH's detectors respectively. The approach we adopted was quite simple: we added to the original textual description the terms corresponding to the visual classes (e.g. indoor, outdoor, building, sky, night, animal, etc.) of the query images, if the associated confidence score was above some threshold (0.65 in our case; see subsection 3.2 for more details). We did the same for the photo annotations: both the queries and the documents of the collection were enriched by the concepts of the associated image(s). This could be considered as a very simplistic way of doing multi-media retrieval.

The performances (Mean Average Precision and Precision@20) are given in Table 2.

Clearly, the use of the visual concepts increases the retrieval performance, even if the inclusion of visual concepts is done in a rather simplistic way. But, to anticipate a little bit the results of the multi-media retrieval section, it will turn out that this advantage is lost when we use other, more complex multi-media fusion mechanisms, based on lower-level features than the visual concepts.

Image Retrieval

In this section, we first describe briefly our image representation based on Fisher Vectors (for more details see [START_REF] Clinchant | Xrce's participation to imageclef 2007[END_REF][START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]). The same representation was used in the Visual Concept Detection sub-task (section 3.2) and ImageCLEFPhoto (section 3.3).

Fisher Vectors for Images

As image representation, we use the Fisher Vector as 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 (BOV) representation; the main idea is to characterize the image with the gradient vector derived from the generative probability model (a visual vocabulary modeled by a GMM in our case). This representation can then be subsequently fed to a discriminative classifier for categorization, or used to compute similarities between images for retrieval.

The generative probability model in our case is the Gaussian Mixture Model (GMM) which approximates the distribution of the low-level features in images, where each Gaussian component can be seen as a visual word.

If we denote the set of parameters of the GMM by Φ = {w i , µ i , Σ i , i = 1...N } (w i , being the mixture's weight), we can compute the gradient vector of the likelihood ∇ Φ log p(I|Φ) that the image was generated by the model Φ. This gradient of the log-likelihood describes the direction in which parameters should be modified to best fit the data (image features). One of its advantages is that it transforms a variable length sample (number of local patches in the image) into a fixed length representation (which we will call Fisher Vector) 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|Φ) (1)
with

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

Note that we used in our experiments two types of low-level local features extracted both on regular grids at different scales (see [START_REF] Clinchant | Xrce's participation to imageclef 2007[END_REF] for further details). The first feature set is based on local histograms of orientations (referred as texture) and the second one is based on local RGB statistics (referred as color). This led to two visual vocabularies, so that we have two Fisher Vectors per image.

Visual Concept Detection

The Visual Concept Detection task of ImageClef had the objective to identify visual concepts in users' photos [START_REF]ImageClef Visual Concept Detection Task[END_REF]. The training images were labeled with 17 visual concepts: indoor, outdoor, person, day, night, water, road or pathway, vegetation, tree, mountains, beach, buildings, sky, sunny, partly cloudy, overcast and animal. The goal was to indicate the presence or the absence of these concepts. In spite of the fact that the concepts were presented in a hierarchy, we have not used it (neither in training nor in testing), but considered the task as a multi-class multi-label image categorization problem. Using the Fisher Vector image representation, we trained linear and non-linear (kernel based) classifiers, where each classifier was designed to detect the presence of one of the 17 concepts.

The binary one-against-all linear classifiers were trained directly on labeled normalized Fisher Vectors. As linear classifier, 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.

In the case of non-linear (kernel-based) classifiers, we use the following kernel:

K(f I , f J ) = T t=1 || fI -ft || 1 • || fJ -ft || 1 (2)
where Note that, as we used two types of low-level local feature vectors (color and texture), we trained two classifiers for each concepts. We transformed the classifier scores s in probabilities with the sigmoid mapping (1 + exp(s)) -1 . To decide about the presence or the absence of a concept, the mean of the two probabilities (color and texture) was compared to a threshold (0.65 in our case).

Both systems, the linear one and the kernel-based one, performed well compared to other systems (see figure 1), the kernel-based system slightly over-performing the linear system.

Content Based Image Retrieval

In the case of image retrieval, we use also the Fisher Vector representation of the images. To obtain the similarity between two images I and J, we first concatenate the color and the texture Fisher vectors before computing the L1-norm of the difference between the concatenated vectors:

sim(I, J) = norm max -||f I -f J || 1 = norm max - i |f i I -f i J | (3)
where f i are the elements of the concatenated vector f and norm max = 2. Given a query image, we can simply rank the images of the database according to this similarity measure. Nevertheless, in the ImageClef Photo Retrieval Task, we have not one but three query images. Therefore, the question is how to combine them for a better retrieval. We investigated three different strategies:

• I1 : We considered the mean of the three Fisher Vectors (this can be seen as the concatenation of the three image in a single one) and used this mean Fisher Vector to query the database.

• I2 : The database images were ranked according to each of the three images independently and the three ranked list was combined using round-robin type selection (i.e. intermixing the three lists), of course eliminating the repetitions of the same images.

• I3 : We combine the three similarity scores (with respect to each image of the query) by averaging the scores after normalisation (by studentization, a.k.a. z-scores).

Incorporating Diversity

One of the aims of ImageCLEFPhoto 2008 is to promote both relevance and diversity into the first retrieved elements. Therefore, in order to introduce diversity at the top level (e.g top k=20 images), we try to find images that are representatives of groups of closely related images (assuming that they contain redundant information). The idea is to bring these representative images to the top of the list and to push down the images which are redundant with respect to images already selected.

To achieve the selection of such representative images, we tested two different strategies. The first one uses explicit image clustering (section 3.4.1) and selects in each cluster the most relevant image according to the original ranking described in section 3.3. The second approach is based on image density estimation (see sub-section 3.4.2), where a number of representative images are automatically detected by seeking for local maximum of the density function.

Explicit Image Clustering

In order to cluster the top N ranked images using the Fisher Vector representation, we proceed as follows. First, we build the K-Nearest Neighbors (K-NN) graph: nodes i and j are connected if the image I j is amongst the K-NN neighbour of the image I i based on the similarity measure defined by [START_REF] Carbonell | The use of MMR, diversity-based reranking for reordering documents and producing summaries[END_REF]. Edges are weighted by the corresponding similarity measure. As the K-NN relationship is not symmetric, the weighted adjacency matrix is asymmetric and the resulting graph is directed.

Then, Probabilistic Latent Semantic Analysis [START_REF] Hofmann | Unsupervised learning by probabilistic latent semantic analysis[END_REF] (PLSA) -some form of discrete Probabilistic Principal Component Analysis -is performed on the weighted adjacency matrix. Note that PLSA is known to be an efficient clustering method to handle sparse matrices (as in our case for K much smaller than N ).

Density Based Representative Image Detection

As an alternative to explicit clustering, we experimented a second approach that relies on direct identification of peaks in some density function estimated from the top N images. Among different possible density estimation methods, we used a modified version of the method proposed in [START_REF] Ester | A density-based algorithm for discovering clusters in large databases with noise[END_REF]. The main idea is to define the density value at each point (image in our case) I i as the number of elements (images) that fall in the hypersphere with center in I i and radius r. Once again, Fisher Vector representation and the L1-norm were used to define the distance between images.

Usually, the density in one point is estimated considering only a fixed radius. We propose here a variant that allows us to obtain a smoother density estimation that better fits our scope. This can be obtained, by considering not only one possible radius of the hypersphere but a predefined set of them {r 1 , . . . , r R } and compute the density by:

d(I i ) = R k=1 n(I i , r k )/V (r k ) (4)
where n(I i , r k ) is the number of images that fall in the hypersphere of radius r k with volume

V (r k ).
The local maxima of the density function are considered "modes" (i.e. local agglomeration of images that generate a local maximum in the density function) and used as representative images.

Description of AUTO-IMAGE runs

As mentioned above, to introduce diversity, we first rank the images according to one of the methods described in section 3.3 and then re-rank the list using either clustering or density estimation on the top N elements of this list.

As the original list is obtained as an answer to a query, the hope is that selected images represent groups of relevant images. Nevertheless this is not necessarily verified. Furthermore, if N gets larger, the probability to get groups of similar but non relevant images2 in the top list increases. Therefore the N parameter was selected relatively small (N=100) trying to reduce maximally these cases.

• N being small, we had to use a small number of clusters (we used C=10) in the first diversification strategy. In each cluster we considered as representative image the one that had the best rank in the list I3 (see section 3.3). The selected ten images were placed at the top of the list keeping the order of the other images unchanged. The name of this run was xrce img cl10 of.

• Using a small C allowed to diversify only the top C=10 elements. Of course we can increase this number by increasing C and N, but as we have not submitted these runs, we have no result for them. As an alternative, we experimented another strategy which is based on the combination of l ranked lists (l is typically 2 or 3 in our particular setting). The main idea is to consecutively cluster the top N elements of each of the lists and concatenate the C <= l • C representative images after eliminating images that occurred more than one time. For example we cluster the top N images in I3 and I2 and concatenate the 20 images selected as above in the 2x20 clusters. If the same image was selected twice, we consider it only once. We ranked them according to their fused similarity score (used to obtain list I3) and place them at the top. The rest of the images in the list I3 is placed after them. This run was submitted under the name xrce img cl10 of rg. Similarly, the runs xrce img cl10 ff of and xrce img cl10 of ff rg were obtained by this strategy.

• In the case of density-based representative image detection, we again used only the top N=100 images which led to relatively few (4-5) local maxima in the density function. Therefore, we consecutively used the three lists Ii and concatenated the modes (representative images) as above into a single set. These images were reordered according to their ranks in I3 and placed at the top, while the remaining images in I3 put just after them. Two such runs were submitted: xrce img knn10 mRm, with R=4 and R=5 corresponding to two different sets of radii (see section 3.4.2).

• Finally xrce img knn10 m5 is an alternative to xrce img knn10 m5m, where we simply replaced the image corresponding to the local maxima by one of its 5 nearest neighbour, if this latter had a better combined relevance score (rank in I3).

Table 4 shows the results obtained with these strategies. Compared to table 3 we can deduce that the CR20 was not always improved, or even where it was improved the improvement was not too big. The reason is probably that the clustering criteria are purely visual and we cannot ensure that the desired cluster diversity source (such as different cities, states, sports, etc) was taken into account. 4 Multimedia Retrieval

Method

Standard Retrieval, without Diversity Seeking Goal

This section deals with the standard retrieval problem, where we don't care about the object redundancy/diversity in the returned ranked list. For the standard problem, the method we adopted this year is quite similar to the one we used last year (see [START_REF] Clinchant | Xrce's participation to imageclef 2007[END_REF]). It will be the basis for diversity-based extensions, as explained in the next section. For completeness and ease of understanding, we describe hereafter the method we used last year. This method can be seen as a graph-based query regularization method (see [START_REF] Diaz | Regularizing query-based retrieval scores[END_REF]), where we simultaneously use two graphs: the one representing visual similarities between objects, and the one representing textual similarities between objects (objects include the query and the annotated photos of the collection). As explained in the previous sections, the cross-entropy between the language models of two objects (possibly expanded by different mechanisms such as thesaurus enrichment and/or pseudo-relevance feedback) is used as textual similarity measure, while a cosinelike norm between the "Fisher Vector" representation of two images is employed as visual similarity measure.

Let us introduce some notations. Let us call w t (q t ) the similarity vector of a given textual query q t with respect to the documents of the collection. This similarity vector is typically obtained by normalizing the retrieval scores obtained by the methods described in the section devoted to the purely textual retrieval (we used z-score normalization). Let us call W t the textual similarity matrix between all documents of the collection, obtained in the same way. Similarly, let us define w i (q i ) and W i , respectively the normalized similarity vector of an image query q i with respect to the images of the collection, and the pair-wise similarity matrix between the images of the collection. They are obtained by the methods explained in the previous section. Let us denote by κ(w, k) the thresholding function that puts to zero all values of the vector w that are lower than the top k values and keeps all other components to their initial value. The cross-media similarity measures that we developed last year could be expressed as follows:

Method

• Sim IM G-T XT (q i ) = κ(w i (q i ), k i ).W t • Sim T XT -IM G (q t ) = κ(w t (q t ), k t ).W i
where the '.' symbol designates the standard matrix product. Note that Sim IM G-T XT does not rely on the textual part of the query, while Sim T XT -IM G does not rely on the visual part of the query. Conversely, Sim IM G-T XT does not rely on the visual part of the documents (photos) of the collection, while Sim T XT -IM G does not rely on the textual part of the images of the collection. This can be understood as query 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.

Note that we could design in the same way mono-media similarity measures that amount to do some pseudo-relevance feedback:

• Sim T XT -T XT (q t ) = κ(w t (q t ), k t ).W t • Sim IM G-IM G (q i ) = κ(w i (q i ), k i ).W i
We could combine all these new similarity measures, for instance by linear combination, with the basic mono-media ones. We tried several combinations, namely:

• C1 : λ 1 w t (q t ) + u w i (u) (what is classically called "late fusion") • C2 : λ 2 w t (q t ) + u Sim IM G-T XT (u) • C3 : λ 3 Sim T XT -IM G (q t ) + u w i (u)
where u iterates over the three query images associated to q t . Note that we used the simple sum to aggregate the normalized scores (z-scores) over the different (3) images associated with the query q t . Table 5 reports the performance (Mean Average Precision and Precision@20) of the different multimedia combinations (including the mono-media baselines). The parameters are set to:

k i =2; k t =25; λ 1 =2; λ 2 =1; λ 3 =1.
The textual baseline (that corresponds to w t ) is the one obtained by thesaurus-based document enrichment and pseudo-relevance feedback. For completeness, we also included the simple late fusion variant where the textual part of the query is augmented by the visual concepts detected by the XRCE detector.

The order in the cross-media similarity appears to be important: identifying the k-visualnearest neighbors of the queries and considering their associated texts as a proxy for the textual part of the query is much more efficient than the converse (identifying the k-textual-nearest neighbors of the queries and considering their associated images as a proxy for the visual part of the query). The linear combination of the purely textual relevance score with the cross-media similarity measure (IMG-TXT) allows the system to still achieve significant improvement: this is not counter-intuitive, as the IMG-TXT cross-media similarity measure does not use the textual part of the query.

As already announced, the introduction of visual concepts as extra features in the textual representation of the query and the documents (photo annotations) appears to loose its efficiency if we take into account the medium-level visual features through the channel of the purely visual similarity, at least in a late fusion context.

Incorporating Diversity

As mentioned in section 3, one of the aims of ImageCLEFPhoto 2008 compared to previous sessions, is to promote diversity in the search results so that the first retrieved elements are not redundant. We investigated two main families of methods: implicit and explicit clustering-based approaches. The first method is commonly known as "Maximal Margin Relevance" (henceforth MMR). It amounts to re-rank the search results so that the element chosen at rank j has to be dissimilar to elements that were already selected at ranks j < j. We give more details on this approach in paragraph 4.2.1. The second method is based on an explicit clustering of the first k elements, followed by a strategy designed to re-rank the elements so that many different clusters are represented among the first elements of the re-ranked list. Within that framework, different clustering algorithms and strategies can be combined. For image retrieval, some combinations have already been proposed in paragraph 3.4. In paragraph 4.2.2, we explain another particular approach that we assessed in the multi-media case.

Implicit clustering based approach

MMR is a re-ranking algorithm which aims at avoiding redundancy among the first elements to be re-ranked [START_REF] Carbonell | The use of MMR, diversity-based reranking for reordering documents and producing summaries[END_REF]. It has been successfully applied in different fields such as active learning in information retrieval [START_REF] Shen | Active feedback in ad hoc information retrieval[END_REF], [START_REF] Huang | Active learning for interactive multimedia retrieval[END_REF] or in document summarizing [START_REF] Lin | NUS at DUC 2007: Using evolutionary models of text[END_REF], [START_REF] Boudin | A scalable MMR approach to sentence scoring for multi-document update summarization[END_REF].

We suppose that we are given a relevance score vector s 1 (for a given query q) as well as an inter-object similarity matrix S 2 (for each pair of annotated photos of the collection). The MMR framework supposes that the elements i should be ranked according to s 1 and S 2 . It is a greedy algorithm: at each step (rank) j we choose the element i that maximizes the following re-ranking criterion:

M M R(i) = β(j)s 1 (i) -(1 -β(j)) max i ∈P j S 2 (i, i ) (5)
where β(j) is a mixture parameter (between 0 and 1) depending on the rank and P j is the set of objects already selected (rank lower than j).

Traditionally, β is kept constant, but we propose here a more efficient variant, where β(j) linearly increases between β(1) = α (< 1) and β(k)=1 for some k (typically k=100), before saturating at value β = 1.

Regarding the choice of s 1 , we adopted the (best) combination of mono-media and cross-media similarity measures (based on the C2 measure introduced in section 4.1). For S 2 , we tested different possibilities. We will give some details on this part in paragraph 4.2.3.

Explicit clustering based approach

In this method, for a topic q, we start by selecting the first k elements according to s 1 . Let us denote by Q k the subset constituted of these selected elements. Next, we cluster objects within Q k in order to find different themes. The similarity measures used in the clustering process are provided by a similarity matrix between multi-media objects, S 2 . From this global matrix, we extract the sub-matrix corresponding to objects in Q k , and we row-normalize it. This row-normalized sub-matrix is denoted S 2 . Then, we use the Relational Analysis (RA henceforth) approach for the clustering stage [START_REF] Michaud | Optimisation en analyse de données relationnelles[END_REF], [START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF].

From a theoretical point of view the RA method allows us to model the clustering problem through an integer linear program. The extended form of the partitioning criterion used in this approach is the following one:

C(S 2 , X) = k i,i (S 2 (i, i ) -m) contribution X(i, i ) (6)
m representing a threshold to which the similarity between two objects is compared. X is called a relational matrix. It is a binary square matrix of dimension k, which represents the partition we are looking for.

In our case, we avoid fixing arbitrarily this parameter by taking a central tendency measure of the similarities [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF]. For our experiments we took the arithmetic means of the strictly positive similarities. We first define

S + 2 = {(i, i ) ∈ Q k × Q k : S 2 (i, i ) > 0}.
Then we have:

m = 1 |S + 2 | (i,i )∈S + 2 S 2 (i, i ) (7)
The more the similarity between two objects exceeds the higher the chance for them to be in the same cluster.

The general term X(i, i ) equals 1 if element i and i are in the same cluster; 0 otherwise. Using this formalism, we can express the relational properties that a partition must respect by linear equations [START_REF] Michaud | Optimisation en analyse de données relationnelles[END_REF]:

• binarity: X(i, i ) ∈ {0, 1}, ∀i, i = 1, . . . , k • reflexivity: X(i, i) = 1, ∀i = 1, . . . , k • symmetry: X(i, i ) -X(i , i) = 0, ∀i = 1, . . . , k • transitivity: X(i, i ) + X(i , i ) -X(i, i ) ≤ 1, ∀i, i , i = 1, . .

. , k

As the partitioning criterion and the constraints are linear with respect to X, we can use integer linear programming in order to solve the clustering problem. Furthermore, we can see that this model doesn't require to fix the number of clusters. However, the integer linear program is NP-hard and in practice, we need to apply an heuristic for dealing with large data-sets.

The heuristic we used in our experiments is quite similar to the leader algorithm introduced in [START_REF] Hartigan | Clustering Algorithms[END_REF]. This approach is based upon transfer operations [START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF], [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF]: at each step, it reassigns an element to the cluster with which its aggregated contribution is maximal. If this last contribution score is negative then it creates a new cluster based on the current element.

We give a sketch of this heuristic in algorithm 1. Using this algorithm, we don't need to fix the number of clusters which can evolve at anytime. It is a property that is important as it allows to obtain pure clusters (as long as the parameter m is strict enough and this is the case when taking the value given by equation ( 7)). However, we need to provide a number of iterations (or a stopping criterion) for having an approximated solution in a reasonable amount of time; the algorithm typically converges in less than 5 iterations for a number of elements (k) smaller than 500. This kind of algorithm is highly dependent on the objects' scanning order. In our context, this order can be given by the relevance score provided by s 1 . In other words, the scanning order of objects Q k used in the RA heuristic is the decreasing order based on s 1 : we first take the most relevant objects then the less relevant ones.

After having clustered Q k , the k most relevant multi-media elements of a topic, 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

• xrce cm qpert 70: explicit clustering based approach where S 2 is constituted of the global similarity measures on textual an visual data. The relevance threshold to stop appending new clusters is given by the 30 th percentile of S 1 .

Our baseline is the basic result we obtained without any diversity goal seeking (such as in paragraph 4.1):

• xrce cm best basic: it is the basic search result based on the global similarity measures C2 using textual and visual data, which doesn't involve any methods for promoting diversity.

Finally, we give in table 6 the results obtained for the best runs we submitted in the EN-EN-AUTO-TXTIMG category. The runs are sorted with respect to the mean between the ranks obtained according to P20 and CR20 among XRCE runs. 6: Precision at 20 (P20) and Cluster Recall at 20 (CR20) measures for the best runs in EN-EN-AUTO-TXTIMG category Our best runs allow us to improve the CR20 measure compared to the baseline xrce cm best basic. Therefore, both the implicit and the explicit clustering based methods allow us to incorporate diversity into the first re-ranked elements. However, we are less precise in terms of P20. Concerning the different kinds of measures we chose to use for representing thematic similarity between annotated photos, we can see that either the pure textual data ("tilo ", constituted of title and location fileds) using cross-entropy measures or the combination of textual and visual data ("cm") using cross-media similarities perform better.

Run

Conclusion

This year, the main lessons we learnt from our participation to ImageCLEF-Photo were:

• in the case of pure text-based retrieval, both document enrichment by thesaurus and query enrichment improve the results, and combining the former with query expansion using PRF improves further the results (Table 1);

• Fisher Vectors are rich image signatures and have state-of-the-art performance both in visual concept detection (see Figure 1) and content based image retrieval (Table 3);

• the use of the visual concepts increases the retrieval performance when combined with pure text, but this advantage is lost when we use other, more complex multi-media fusion mechanisms, based on lower-level features than the visual concepts (Table 2);

• combining the two mono-media information sources (image and text) using cross-media similarities based on transmedia pseudo-relevance feedback improves significantly (by more than 50% relative) the retrieval results (xrce cm best basic with MAP=0.39 and P@20=0.56).

• concerning the diversity, most strategies we proposed succeeded in reducing the redundancy in the top documents. As none of the techniques used explicitly the provided clustering criterion (e.g. diversifying according to cities or states or sports, etc.), the CR20 score was not always significantly increased (or in a few cases it was even decreased). This is not surprising, as we were seeking and improving the diversity in a blind (unsupervised) way, and therefore the "new" documents introduced at top level in many cases were not necessarily different following the criterion the organizers decided. For example, a pure visual content-based system will surely not group pictures of "persons on a beach" into different clusters each corresponding to a different "country" (topic 34). There is more chances that this happens for text or multi-modal system. Obviously, one possible improvement is the explicit integration of the provided "clustering criterion" into the diversification strategy when possible.

Figure 1 :

 1 Figure 1: ImageClef Visual Concept Detection Task results. The red circle represents our linear system and the green square our non-linear system.

  .

		Without PRF	With PRF
	Method	MAP	P20 MAP	P20
	Baseline	0.215 0.259 0.239 0.293
	Document Enrichment 0.231 0.268 0.260 0.308
	Query Enrichment	0.218 0.264 0.257 0.282
	Table 1: Performance (MAP and P@20) of different enrichment strategies

Table 2 :

 2 Performance (MAP and P@20) of the combination with different Visual Concept Detectors

		Without PRF	With PRF
	Method	MAP	P20 MAP	P20
	Baseline	0.215 0.259 0.239 0.293
	XRCE Visual Concepts	0.241 0.297 0.269 0.334
	RWTH Visual Concepts 0.232 0.271 0.258 0.308

Table 3

 3 compares these three strategies. We can see that the early fusion (mean Fisher Vector) performs worse than late score level fusions. The best performance was obtained by the score averaging strategy I3.

	Method	MAP	P20 CR20
	I1 (xrce img ff)	0.119 0.255 0.330
	I2 (xrce img rg) 0.130 0.301 0.351
	I3 (xrce img of) 0.151 0.328 0.352

Table 3 :

 3 Performances (MAP and P@20 and CR@20) of different strategies.

Table 4 :

 4 Performances (P@20 and CR@20) of different strategies.

		P20 CR20
	xrce img cl10 of	0.312 0.353
	xrce img cl10 of rg	0.290 0.360
	xrce img cl10 ff of	0.270 0.349
	xrce img cl10 of ff rg 0.254 0.365
	xrce img knn10 m5m 0.276 0.334
	xrce img knn10 m4m 0.290 0.360
	xrce img knn10 m5	0.300 0.357

Table 5 :

 5 Performance (MAP and P@20) of the different multi-media fusion strategies

	MAP	P20

Available on http://wiki.services.openoffice.org/wiki/Dictionaries

Indeed, even images visually similar to query images can be non relevant according to the complete query, such as churches with one tower for query 2 or straight roads outside USA for query 6.

Algorithm 1 RA heuristic Require: nbitr = number of iterations; S 2 the similarity matrix i = 1 Take the first element i as the first element of the first cluster clu 1 κ = 1 where κ is the current number of cluster for l = 1 to nbitr do for i = 1 to k do for j = 1 to κ do Compute the contribution of i with cluster clu j : cont j = i ∈clu j (S 2 (i, i ) -m) end for j * is the cluster id which has the highest contribution with i and cont j * is the corresponding contribution value

Create a new cluster where i is the first element κ ← κ + 1 else Assign i to cluster clu j * if the cluster where was taken i before its new assignment, is empty then κ ← κ -1 end if end if end for end for Return the partition found which belong to different clusters until a stopping criterion is fulfilled. The strategy employed is described in algorithm 2. In this approach the scanning order of objects in Q k is the same one as previously used, namely we take the most relevant objects first. By doing this, each cluster is represented by its most relevant object according to s 1 .

Algorithm 2 Re-ranking strategy for a topic Require: A topic q; s 1 the relevance score vector between objects in Q k and q; R the clustering results of objects in Q k L1, L2 and CL are empty lists i = 1 Take the first element i as the first element of the re-ranked list L1 Add R(i), the cluster id of element i in the cluster list

We tested different stopping criteria in algorithm 2:

1. the number of different clusters represented among the first results should not exceed a predefined number nbdiv ∈ 1, . . . , κ where κ is the number of clusters found 2. we append different clusters' representatives as long as their relevance scores are not lower than a predefined threshold qpert ∈

Concerning the first stopping criterion, let us assume that nbdiv = 10. Then, this implies that the first 10 elements of the re-ranked 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 k th rank), is constituted of the remaining multi-media objects sorted in the decreasing order with respect to s 1 and without taking into account the cluster membership information.

For illustrating the second stopping criterion, let us take for example k = 100. Q k is sorted according to the decreasing order with respect to s 1 (such as for the scanning order). Then if we take furthermore qpert = s 1 (70), this means that the threshold is the 30 th percentile of the distribution given by s 1 . Accordingly, in the re-ranked list, we append the most relevant element of a cluster that it is not already represented as long as the relevance measure of this chosen element is greater or equal to the 30 th percentile of s 1 . This is an alternative which, unlike the first stopping criterion, avoid fixing a number of clusters.

Description of AUTO-TXTIMG runs

In this paragraph, we give more details about the runs we submitted in the EN-EN-AUTO-TXTIMG category. Our different approaches concerning this sub-task have been described in the previous paragraph. For s 1 , we obviously chose the best multimedia combination as explained in section 4.1. Let us come back to the choice of the pairwise similarity matrix S 2 between the annotated photos of the collection. The kind of similarity coefficient computed in S 2 differs in general from s 1 . The idea is to investigate whether some weighting schemes are more adequate, or whether the use of a single mode or the use of specific fields give better results in diversity-based re-ranking. Let us be more precise in the three alternatives we adopted for S 2 :

1. the cross-entropy measure between texts given by the concatenation of the title and the location fields associated to each multi-media object. This similarity matrix is referred as "tilo" in the title of our runs.

2. the tf idf 3 measure between texts given by the concatenation of the title, the location and the narrative fields associated to each multi-media object. This similarity matrix is referred as "tfidf" in the title of our runs.

3. the (best) cross-media similarity measure which combines textual and visual similarity measures such as described in paragraph 4.1. In other words, it is the extension of s 1 to pairs of elements in the dataset. This similarity matrix is referred as "cm" in the title of our runs.

Clustering -or re-ranking -is limited to the k most relevant elements with respect to a topic q. In all our runs, we took k = 100.

The title of our runs is constituted as follows: "xrce (S2 matrix) (Stopping criterion) (Parameter value)". We give below some examples of the meaning of the titles of our runs:

• xrce tilo nbdiv 15: explicit clustering-based approach where S 2 is constituted of the crossentropy measure using textual data (title and location fields). The number of different clusters is nbdiv = 15.

• xrce cm mmr 07: implicit clustering based approach where S 2 is constituted of the global similarity measures using textual and visual data. The basic mixture parameter in the MMR re-ranking function (for rank 1) is set to α = 0.7 (β is linearly increasing from 0.7 to 1, value achieved for j=k=100).


Julien Ah-Pine

Gabriela Csurka

Jean-Michel Renders

Evaluation of Diversity-focused Strategies for Multimedia Retrieval

In this paper, we propose and evaluate different strategies to promote diversity in the top results of multimedia retrieval systems. These strategies consist in clustering, explicitly or implictly, the elements of the top list of some initial ranking and produce a re-ranking that favours elements belonging to different clusters. We evaluate these strategies in the particular case of ImageCLEFPhoto 2008 Collection. Results show that most of these strategies succeed in increasing a diversity performance measure, while keeping or slightly degrading precision of the top list and, more interestingly, they achieve this in complementary ways.

Introduction

Up to now, many multi-modal retrieval systems have focused on addressing the semantic gap between textual and visual contents of multimedia documents. The scientific challenges are traditionnaly oriented towards exploiting in an efficient manner these two types of information in order to improve the search results. In ImageCLEFPhoto 2008, however, the main goal is to promote diversity among the first search results. We address this issue using a two-step approach. In the first step, we ignore the question of diversity. In other words, we first try to find the most relevant objects using the material introduced in [START_REF] Clinchant | Trans-media pseudo-relevance feedback methods in multimedia retrieval[END_REF]. Then, in a second step, we re-rank the first relevant objects by taking into account their mutual similarities in order to avoid redundancy and thus to promote diversity. These different approaches are described in details in [START_REF] Ah-Pine | XRCE's participation to imageCLEF[END_REF]. Here, we will just briefly remind them, as the main goal of this paper is to perform a deep analysis of the results, as well as to compare and to discuss the strengths and weaknesses of the proposed approaches.

Incorporating Diversity in Retrieval Ranking

As mentioned previously, one of the aims of ImageCLEFPhoto 2008 compared to previous sessions, is to promote diversity in the search results so that the first retrieved elements are not redundant. Nevertheless, let us begin by recalling our basic multimedia retrieval strategy, that does not take into account the redundancy in the returned ranked list. Complete description and rationale can be found in [START_REF] Ah-Pine | XRCE's participation to imageCLEF[END_REF]. Remind that diversity-based extensions will be built on top of this method.

As textual similarity measures, we used the cross-entropy between the language models of two objects [START_REF] Ponte | A language modelling approach to information retrieval[END_REF], the documents of the collection being expanded by thesaurus enrichment 1 , while the query was expanded by pseudo-relevance feedback. As visual similarity measures, a cosine-like norm between the "Fisher Vector" representation of two images was employed [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]. Based on these monomodal similarities, we developed an intermediate fusion method which efficiently combine them in the context of multimedia retrieval. This kind of fusion operator can be understood as query 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] Clinchant | Trans-media pseudo-relevance feedback methods in multimedia retrieval[END_REF]. The ranking obtained with the basis method will be denoted by xrce cm best basic.

Let us go back to the objective of promoting diversity in the first elements of the ranked retrieval list. To this end, we investigate two main families of methods: implicit and explicit clustering-based approaches. Both approaches use a pair-wise similarity matrix (designated by Sim) between objects of the collection in order to model the diversity. In ImageCLEFPhoto 2008, we tested two kinds of similarities. The first one, designated by tilo is purely textual and is computed by the cross-entropy measures between pairs of smoothed language models of the documents restricted to their ti tle and location fields. The second one, denoted by cm, is a pair-wise cross-media similarity matrix that takes into account both textual and visual content in the same way that we did for computing the similarity between a query and an element of the collection.

The first method to avoid redundancy is commonly known as "Maximal Margin Relevance" (MMR) [START_REF] Carbonell | The use of MMR, diversity-based reranking for reordering documents and producing summaries[END_REF]. It amounts to re-rank the search results so that the element chosen at rank j has to be dissimilar to elements that were already selected at ranks j < j. More concretely, given an initial relevance score vector Score(q) (for a given query q, this is typically our xrce cm best basic ranking), as well as a pair-wise similarity matrix Sim, the MMR framework supposes that the elements should be ranked by greedily choosing at each step (rank) j the element o i that maximizes the following re-ranking criterion:

M M R(o i ) = β(j)Score(q, o i ) -(1 -β(j)) max o i ∈P j Sim(o i , o i ) (1)
where β(j) is a mixture parameter2 (between 0 and 1) depending on the rank and P j is the set of objects already selected (ranks lower than j). 1 Using the English Open Office thesaurus available on http://wiki.services.openoffice.org/wiki/Dictionaries, giving 15 times more weights to the original words.

The second family of methods are based on an explicit clustering of the first k elements, followed by a strategy designed to re-rank the elements so that many different clusters are represented among the first elements of the re-ranked list. In this method, for a topic q, we start by selecting the first k elements according to Score(q), which we denote by P k . Next, we cluster objects within P k in order to find different themes, using the Sim pair-wise similarity matrix as basic material. This is realized using the Relational Analysis approach [START_REF] Michaud | Modeles d'optimisation en analyse des données relationnelles[END_REF][START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF], which has particular advantages in this framework because it does not impose to fix a priori the number of clusters and because it can deal with strongly unbalanced cluster size distributions (by isolating very small, but significant clusters).

After having clustered the elements within P k , the top elements of the initial list are re-ranked by the following strategy: we go top down through the elements of this list and, if the cluster id of the current object is not yet represented by other objects previously considered, it is put in the priority list; otherwise, it is put in the non-priority list; we iterate this operation until the number of different clusters represented in the priority list reaches nbdiv; after this, we naturally build a new list by taking the priority list, followed by the non-priority list (in each list, objects are ranked following their original relevance scores).

As far as nomenclature is concerned, to designate our ranking methods, the tilo suffix indicates that we used the purely textual (title + location) similarity measure to cluster the objects of the collection. The cm suffix refers to the use of the pair-wise cross-media similarity measure. Implicit and explicit clustering are differentiated by the mmr and nbdiv suffixes respectively; in the latter case, the maximum number of clusters represented in the top list is indicated just after.

Analysis of Experimental Results

Analysis of Retrieval Results

For details about the task and the collection, we refer to the overview paper [START_REF] Arni | Overview of the ImageCLEFphoto 2008 photographic retrieval task[END_REF]. Before analysing the effects of the diversity-focused strategies, it is interesting to analyse the basic ranking algorithm (xrce cm best basic), in order to understand the strengths and weaknesses of the underlying method. That is the goal of this sub-section. Clearly, this algorithm outperforms very significantly the monomodal strategies, as well as the late fusion approach (see our results in [START_REF] Clinchant | Trans-media pseudo-relevance feedback methods in multimedia retrieval[END_REF]). Let us have a deeper look on results query by query (see Figure 5).

First, we recall (see also [START_REF] Ah-Pine | XRCE's participation to imageCLEF[END_REF]) that the only linguistic analyses made on the text or the query were lemmatization and stop-word removal.

Even if the lemmatization was in most cases beneficial, (e.g. for topic 3 55/35 Peru and Peruvian), we also noticed a negative effect in the case of the topics 39/24 and 40/25 where "bad weather" and the adjective "weathered" were considered as identical words after lemmatization. For this reason, texts containing words like "rain, hail, fog, wind, storm, etc" (making reference to bad weather, Fig. 1. We can obviously see the visual similarity (apart weather conditions) between the query images of topic 39/24 (first three images) and three of the four top images retrieved by our system. The missing top retrieved image contained was one of the top ranked 'weathered sandstone" images. but not using explicitely the word "weather") had much lower relevance scores than images containing "weathered sandstone", even if the word "weather" was added by thesaurus enrichment (but with a low weight by construction). Moreover, from a purely visual viewpoint, "bad weather" is a concept rather difficult to be detected at least with our visual similarity measures as we can see in Figure 1. Indeed, top images look very similar to the query images apart from some small umbrella's that could be interpreted as a sign of bad weather.

The lack of semantic or linguistic analyses of queries made some of the queries quite difficult to be handled by our approach. We can mention here the topic 2/1, "church with more than two towers" where the notion of "more than two" would require a semantic analysis and a possible transformation to "three", "four", etc. Furthermore, visually, even if we retrieve the same building as present in a given query (e.g. the St Patrick Cathedral in Melbourne as shown in Figure 2 4 from different points of view), it is difficult to ensure that all towers are visible in the image (the assessor appeared to rely more on the image than on her prior knowledge about the building). For buildings that are not in the query images, the task becomes even more difficult.

Similarly, for topic 18/12 entitled "sport stadium outside Australia", as we removed "outside" as a stopword and did no semantic analysis of the query, texts mentioning "Australian sport stadiums" get higher textual ranks than any "sport stadiums" from other countries.

The failures in the above examples were rather due to the lack of semantic analysis or logical reasoning about the query content. Another cause of failure stems from the cross-media pseudo-relevance feedback mechanism that is the basis for our cross-media similarity measure. The real limitation (and therefore risk) of the proposed cross-media similarity can be seen through the analysis of the topic 20/14, "close-up of animals". As shown in Figure 3, the results were really poor and suprising. Trying to understand why, we realized that due to high visual similarity between the "golden eagle" close-up query image and some close-up "mummies" images (top 2), the textual query was enriched by the words related to "Nazca grave's mummies" images. This resulted in pushing at the top similar "mummies" images. This was possible because there were no stronger candidates, as the original query virtually shared no textual content (for most animal images, the word "animal" does not appear explicitly) and no visual content with the documents of the collection.

Fortunately, this was a rare case, and in most cases the system was able to take advantage either from textual or from visual similarities (or both) and to successfully combine them. We can mention the excellent results obtained for queries 6/4 or 44/28 (see Figure 4) where the top results show alternatively documents that are visually similar or textually similar.

Analysis of Diversity Results

In this sub-section we focus our analysis on the different strategies we proposed for avoiding redundancy in the top lists. These comments are made on the basis of the Figure 5 given previously and the Table 1. The latter represents some of the best results we obtained for ImageCLEFPhoto 2008 (incidentally, they were also the best ones when compared to the other Particularly, we will pay more attention to the methods denoted by xrce tilo nbdiv 10 and xrce cm mmr 07 that are respectively the best results we obtained with explicit and implicit clustering approaches.

The analysis we give below takes into account the P20 and CR20 measures, following the criteria that were chosen to evaluate the results during Image-CLEFPhoto 2008.

When seeking to promote diversity departing from the basic run xrce cm best basic, we can observe in Table 1, that any diversity-focused method fails to increase, on average, the P20 measure. However, all methods perform better than the basic run regarding the CR20 measure. In other words, by trying to eliminate redundancy among the first retrieved objets, unfortunately, we might push relevant objects out of the 20 first re-ranked elements and on the contrary, we might put into this final top list some irrelevant objects. Nevertheless, this is an average trend. Indeed, according to Figure 5, it happens, that seeking for diversity also leads to improved precision.

Next, if we compare the results given by the two kinds of method (implicit and explicit clustering), we can notice, according to Table 1, that the former has, on average, a better P20 than the latter. On the contrary, with respect to CR20, explicit clustering method generally performs better.

Then, let us look at Figure 5 more closely. The explicit clustering strategy exhibits a consistent, stable behaviour, where it systematically gives slightly lower or equal P20 performance than the basic ranking, while offering CR20 performance that are superior or equal to the baseline. In that context, Figure 4 that illustrates the results of topic 11/6 is a good example that demonstrates the benefits of the explicit clustering method for avoiding redundancy. Implicit clustering does not offer such a stability in its behaviour. In fact, the implicit clustering method seems to "take more risk" in the re-ranking process with a diversity seeking goal than the explicit clustering method, with a consequence of increased variance in the performance. In that context, the topic 20/14 illustrated in Figure 3, is a good example that shows the benefits of the implicit clustering. Indeed, in that case neither the basic run nor the clustering explicit runs allow to find a single relevant object in their top lists. Despite this fact, the implicit clustering had allowed to find a relevant objects in its top 10.

Finally, we illustrate in Figure 6 another issue, related to the fact that the clustering process can result in a totally different thematic than the one intended by the organizers. For the topic 3/2, entitled "religious statue in the foreground", the ranking xrce tilo nbdiv 10 (based on purely textual information) offers diversity (in terms of location), but different from what was expected (types of religious statues).

From a pure relevance-based assessment, our method based on cross-media relevance feedback was able to adequately combine and leverage textual and visual information in the query and the documents. Incapacity to give good results was in general due to the lack of deeper logical and semantic analysis of the query content. When considering diversity-focused strategies, three main lessons can be learned. First of all, these strategies are very dependent on the results of the basic ranking (they often fail to capture relevant elements that are low in the list). Secondly, implicit and explicit clustering strategies are often complementary (they are not beneficial for the same type of queries). Finally, implicit clustering strategies favour more exploration than explicit clustering strategies, with the consequence of exhibiting larger variance in the performance results. Clearly, deeper linguistic processings that lead to better document or query enrichment and understanding would certainly allow to leverage the results both from a purely textual viewpoint as well as from a cross-media viewpoint.

Fig. 2 .

 2 Fig. 2. Top 10 images for the topic topic 2/1 with the xrce cm best basic (top row) and xrce cm mmr 07 (bottom row).

Fig. 3 .

 3 Fig. 3. The first line represents the top 10 results provided by the xrce cm best basic method for the query 20/14. The second line shows the top 10 results of the diversityfocused approach xrce cm mmr 07. Compared to the former, the latter was able to bring a relevant image to the 5th position from 70th (in the first case).

Fig. 4 .

 4 Fig. 4. The method xrce tilo nbdiv 10 introduced diversity for the query 6/4 within the top 10 results (second line) compared to the xrce cm best basic method keeping the same P10 performance.

Fig. 5 .

 5 Fig. 5. P20 and CR20 results per query for xrce cm best basic (blue), xrce cm mmr 07 (green) and xrce tilo nbdiv 10 (red).

Fig. 6 .

 6 Fig.6. The method xrce tilo nbdiv 10 introduced diversity for the query 3/2 within the top 10 results (second line) compared to the xrce cm best basic method but decreasing the P10 performance.

Table 1 .

 1 Some Best results among XRCE's runs

	Rank	Run	P10 CR10 P20 CR20 P100 CR100
	1 xrce tilo nbdiv 10 0.5103 0.3636 0.5423 0.4146 0.2831 0.6374
	2	xrce cm nbdiv 10 0.4923 0.3608 0.5474 0.4111 0.2831 0.6374
	4	xrce cm mmr 07 0.6538 0.3012 0.5500 0.4015 0.2790 0.6407
	7	xrce tilo mmr 07 0.6462 0.3076 0.5385 0.4006 0.2751 0.6492
	12 xrce cm best basic 0.6846 0.2816 0.5731 0.3727 0.2831 0.6374

Traditionally, β is kept constant, but we propose here a more efficient variant, where β(j) linearly increases between β(1) = α (< 1) and β(k)=1 for some k (typically k=100), before saturating at value β = 1.

We will refer to topics by t/n, where t refers to the topic number provided and n to its order in the topic list. In the figures the topics' orders appear from 1 to 39.

In all figures, a colored box around an image means that the image is relevant and different colors make reference to different ground truth clusters.

Acknowledgments. This work was partly funded by the French National Agency under the OMNIA project (OMNIA ANR-07-MDCO-009-01) and under the Infomagic project, part of the Pole CAP DIGITAL (IMVN) de Paris