Christophe Moulin

Christine Largeron

Christophe Ducottet
email: ducottet@univ-st-etienne.fr

Mathias Géry

Cécile Barat

Fisher Linear Discriminant Analysis for Text-Image Combination in Multimedia Information Retrieval

Keywords: Multimedia information retrieval, Textual and visual information, Bag-of-words, Parameters learning, Fischer LDA

  L'archive ouverte pluridisciplinaire

Introduction

The advent of digital cameras, video recorders, smart phones as well as the development of communication networks (e.g. WWW) has led to an explosion of the number of multimedia documents available. Users can easily create, mash and share some documents associating text, image, audio or video. This theoretically infinite amount of data creates a strong desire for efficient multimedia information retrieval systems able to search multimedia documents relevant to an information need. Otherwise, this data is not accessible and thus useless.

Most existing systems consider a single type of information for indexing and searching multimedia documents. Text Based Image Retrieval (TBIR) systems consider only the textual information (e.g. commercial search engines such as Google Images1 , Exalead Images2 or systems specialized in images retrieval such as Picsearch3 , etc.), while Content Based Image Retrieval (CBIR) systems exploit only the visual content (e.g. [START_REF] Smeulders | Contentbased image retrieval at the end of the early years[END_REF], [START_REF] Lew | Content-based multimedia information retrieval: State of the art and challenges[END_REF], QBIC [START_REF] Flickner | Query by image and video content: The qbic system[END_REF], TinEye4 ). Among them, text-based search systems are very popular.

They capitalize on the significant progress made in text retrieval. To retrieve documents, including those composed of videos or images, they index the main text of documents plus the metadata like image name, tags, speech transcript, etc. Even though these systems are efficient, their performance is limited since they may ignore the different media content. Other retrieval approaches exploiting media content, called content-based approaches, have been actively studied to develop better image, video or sound/speech search engines as presented in several recent surveys [START_REF] Smeulders | Contentbased image retrieval at the end of the early years[END_REF][START_REF] Antani | A survey on the use of pattern recognition methods for abstraction, indexing and retrieval of images and video[END_REF][START_REF] Liu | A survey of content-based image retrieval with high-level semantics[END_REF][START_REF] Datta | Image retrieval: Ideas, influences, and trends of the new age[END_REF]. The question of how to represent the media content is central to these approaches. Most results from state-of-the-art methods in the different media domains are achieved with specific vocabularies and bag-of-Xwords representation, X standing for visual, audio or video [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF][START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Aucouturier | The bag-of-frames approach to audio pattern recognition: A sufficient model for urban soundscapes but not for polyphonic music[END_REF][START_REF] Schuldt | Recognizing human actions: A local svm approach[END_REF]. This model which is adopted from textual document representation processes image, video or audio data with textual information retrieval techniques and so, benefits from prior work in this field.

At present, it has been shown that using multimodal approaches yields better results than text-based systems or content-based systems, either in image, video or audio retrieval [START_REF] Yan | A review of text and image retrieval approaches for broadcast news video[END_REF][START_REF] Moulin | Combining text/image in wikipediamm task[END_REF][START_REF] Atrey | Multimodal fusion for multimedia analysis: a survey[END_REF]. A multimodal approach inevitably implies combining diverse modality information, which is most often accomplished at the feature level (early fusion) or at the decision level (late fusion).

It is important to determine an optimal fusion strategy to improve overall effectiveness. Many fusion strategies have been presented in the literature.

Linear weighted fusion is one of the simplest and most widely used solutions [START_REF] Bartell | Automatic combination of multiple ranked retrieval systems[END_REF][START_REF] Shaw | Combination of Multiple Searches[END_REF][START_REF] Vogt | Fusion via a linear combination of scores[END_REF]. However, weighting appropriately the different modalities remains an open problem.

In this paper, a new method based on Fisher-Linear Discriminant Analysis is presented, to learn automatically weights in a linear combination model for multimedia information retrieval. Our attention is restricted to multime-dia documents containing only text and image modalities, that we model using a bag-of-words approach. Performance of our method is validated on multimedia information retrieval tasks in the imageCLEF challenge.

The organization of the rest of paper is as follows. Section 2 discusses some work related to multimedia fusion. Section 3 presents our prior work on multimedia information retrieval and highlights the remaining key issues. Section 4 describes our new approach. Section 5 presents an experimental protocol applied to get the results of Section 6. Finally in section 7 we present our conclusions and prospects for future work.

Related work

This paper addresses the problem of combining multiple modalities, especially text and image, to increase the effectiveness of multimodal retrieval system. In this section, we briefly present some background information on multimodal fusion and we introduce some related work to provide the context under which our method was developed. See [START_REF] Atrey | Multimodal fusion for multimedia analysis: a survey[END_REF] for a more complete overview of current approaches on multimodal fusion.

Two data fusion strategies are often in opposition: early and late fusion.

Early fusion combines the different unimodal features into a single representation (Figure 1). A simple early fusion approach is to normalize and concatenate features into a unique vector. This has been extensively applied for combining texture, color, and shape information in many image applications, including multimodal biometrics [START_REF] Ross | Information fusion in biometrics[END_REF][START_REF] Rattani | Feature Level Fusion of Face and Fingerprint Biometrics[END_REF], face recognition [START_REF] Fu | Multiple feature fusion by subspace learning[END_REF], image annotation [START_REF] Barnard | Matching words and pictures[END_REF], image classification [START_REF] Depeursinge | Fusing visual and clinical information for lung tissue classification in high-resolution computed tomography[END_REF] or retrieval [START_REF] Macedonas | Improvement of image retrieval by fusing different descriptors[END_REF]. This simple approach suffers from several limitations, including the curse of dimensionality, the data redundancy which may lead to a decrease in the system performance, incompatibility between feature ranges and types. Dimensionality reduction methods as Principal Component Analysis (PCA) [START_REF] Duda | Pattern Classification (2nd Edition)[END_REF] and appropriate normalization are used to solve these problems, as well as more elaborated methods as discussed in [START_REF] Fu | Multiple feature fusion by subspace learning[END_REF].

Late fusion processes each modality independently and fusing the results

arising from all systems (Figure 1). Late fusion approaches are diverse. They are broadly categorized into two methods: similarity scores methods and rank-based methods. Similarity scores methods exploit the similarity value, e.g. the score, between a query and each document. They assign a final relevance score to a document based on all returned relevance scores from the different retrieval systems. In addition, a normalization step may be required to compare the returned relevance scores. In general, linear combination models are simple and effective methods to fuse information. In these methods, the final score is obtained as a weighted sum of the scores from each unimodal system. Several formulas have been suggested, including CombSum [START_REF] Shaw | Combination of Multiple Searches[END_REF], CombMNZ [START_REF] Shaw | Combination of Multiple Searches[END_REF] or standard linear formulations [START_REF] Bartell | Automatic combination of multiple ranked retrieval systems[END_REF][START_REF] Vogt | Fusion via a linear combination of scores[END_REF][START_REF] Wu | Data fusion with estimated weights[END_REF]. For instance, the CombSum approach computes the sum of all returned scores, while CombMNZ weighs the CombSum score by the number of systems which have retrieved a document. Since scores are not always available, a second type of late fusion approaches exploit the rank of retrieved documents to improve the retrieval [START_REF] Nuray | Automatic ranking of information retrieval systems using data fusion[END_REF]. For example, Borda count and Condorcet methods used by Aslam and Montague in [START_REF] Aslam | Models for metasearch[END_REF][START_REF] Montague | Condorcet fusion for improved retrieval[END_REF] are two well-known solutions.

Many papers evaluate early and late fusion strategies by comparing their performances and investigating their pros and cons [START_REF] Snoek | Early versus late fusion in semantic video analysis[END_REF][START_REF] Depeursinge | Fusing visual and clinical information for lung tissue classification in high-resolution computed tomography[END_REF]. When dealing with mixed feature types, such as text, video or image, late fusion appears to perform better than early fusion. It has the advantage to use finely tuned retrieval models specific to each modality. Hereafter we will focus on this kind of approach and, more specifically, on the linear combination model. This linear combination model has been widely used in multimedia information retrieval for combining audio/visual features [START_REF] Aleksic | Audio-visual speech recognition using mpeg-4 compliant visual features[END_REF], audio/video features [START_REF] Iyengar | Audio-visual synchrony for detection of monologues in video archives[END_REF][START_REF] Cheung | A two-level fusion approach to multimodal biometric verification[END_REF] or text/visual features [START_REF] Iskandar | Combining image and structured text retrieval[END_REF][START_REF] Torjmen | Methods for combining content-based and textual-based approaches in medical image retrieval[END_REF][START_REF] Moulin | Combining text/image in wikipediamm task[END_REF]. In all these publications, combining features always leads to improve the retrieval system results. However, obtaining a suitable combination is not straightforward. The principal difficulty is to determine the weights of the different modalities. In some papers, the authors consider equal weights [START_REF] Alexandre | Combining independent 36 and unbiased classifiers using weighted average[END_REF][START_REF] Wang | Combining face and iris biometrics for identity verification[END_REF]. This is evidently the most simple approach, but it does not take into account the strengths and weaknesses of each unimodal retrieval system. Therefore, it would appear pertinent to attribute more or less weight to a system according to its reliability and performance. To accomplish this, some approaches choose to fix values for the different weights and vary them to study their influence on the system [START_REF] Iskandar | Combining image and structured text retrieval[END_REF][START_REF] Torjmen | Methods for combining content-based and textual-based approaches in medical image retrieval[END_REF]. However, in these latter works, no care is taken to use a specific dataset to learn the parameters and another one to evaluate the system. Consequently, the results can be overestimated.

Other works evaluate the reliability of each system and decide weights accordingly [START_REF] Aleksic | Audio-visual speech recognition using mpeg-4 compliant visual features[END_REF][START_REF] Cheung | A two-level fusion approach to multimodal biometric verification[END_REF]. Moreover, some learning approaches to assign weights are proposed. Then, the combination model, or global retrieval system, is first optimized with training data, and then the optimized model is applied on test data [START_REF] Iyengar | Audio-visual synchrony for detection of monologues in video archives[END_REF][START_REF] Moulin | Combining text/image in wikipediamm task[END_REF]. A standard learning approach is to consider a criterion which measures the performance of the combination model and to numerically optimize this criterion to find the optimal weight values which provide the best outcomes. In [START_REF] Moulin | Combining text/image in wikipediamm task[END_REF], to combine text and visual information, some authors apply an exhaustive search of the parameter space in range [0,1] with the training data. Similarly, in [START_REF] Iyengar | Audio-visual synchrony for detection of monologues in video archives[END_REF], to combine audio, visual and synchrony features, other authors perform a grid search in ranges [0,1] to determine the two combination parameters. Such approaches are very time consuming, especially as the number of features increases. From all these publications, the issue of finding the appropriate weights for different modalities remains clearly one of the major drawbacks of the linear combination method and is presented as "an open research issue" in [START_REF] Atrey | Multimodal fusion for multimedia analysis: a survey[END_REF]. Our aim is to introduce a solution to learn weights using Fisher Linear Discriminant Analysis [START_REF] Fisher | The use of multiple measurements in taxonomic problems[END_REF] for multimedia documents composed of text and images.

Textual and visual information retrieval model

In previous work, we developed an Information Retrieval model in order to exploit textual and visual information [START_REF] Moulin | Combining text/image in wikipediamm task[END_REF][START_REF] Moulin | Impact of visual information on text and content based image retrieval[END_REF]. This model was based on late fusion and linearly combines textual and visual scores. It is made up of several modules as illustrated in Figure 2. The first stage (1), consists in indexing textual and visual information, using a bag-of-words based model (e.g. vector space model). At this step, text and image information are processed independently. During the second stage (2), a textual and visual information query is provided by a user. It is also represented using the same bag-of-words approach. Then, the third stage (3) computes a ranking score between the query and every document of the collection, for each modality (text and image). Finally, the last step (4) combines linearly these textual and visual scores in order to retrieve the most relevant documents corresponding to the user's need. In this model, the weight corresponding to each kind of information depends on a parameter α.

Textual representation

Given D, a collection of documents and T = {t 1 , . . . , t j , . . . , t |T | }, an index composed of terms occurring in D, a document d i is represented as a vector of weights d i = (w i,1 , . . . , w i,j , . . . , w i,|T | ) according to the vector space model introduced by Salton et al. [START_REF] Salton | A vector space model for automatic indexing[END_REF][START_REF] Salton | Introduction to modern Information Retrieval[END_REF]. In their model, the importance of a term t j within the specific document d i is measured by the term frequency tf i,j while its importance over the corpus is evaluated with the inverse document frequency idf j . The weight w i,j corresponds to the product of tf i,j by idf j where tf i,j and idf j can be computed according to the version of Okapi formula [START_REF] Robertson | Okapi at trec-3[END_REF] as implemented by the Lemur software [START_REF] Zhai | Notes on the lemur tfidf model[END_REF]:

tf i,j = k 1 n i,j n i,j + k 1 (1 -b + b |d i | davg ) (1)
where n i,j is the number of occurrences of the term t j in the document d i , |d i | the size of the document d i , d avg the average size of all documents in the corpus and, k 1 and b are two constants,

idf j = log |D| + 1 |D j | + 0.5 ( 2
)
where |D| is the size of the corpus and |D j | the number of documents of D where the term t j occurs at least one time.

A query q k , provided by a user, can also be considered as a short document, and therefore, it can also be represented as a vector of weights. A score is then computed between the query q k and a document d i :

score T (q k , d i ) = t j ∈q k tf k,j idf j tf i,j idf j (3)

Visual representation

In order to combine the visual information with textual information, we also represent images as weighted vectors. This requires a visual vocabulary Finally, a visual score score V (q k , d i ), corresponding respectively to a visual vocabulary V (V mstd or V sif t ), is calculated between a query q k and an image document d i :

V = {v 1 , . . . , v j , . . . , v |V | } defined,
score V (q k , d i ) = v j ∈q k tf k,j idf j tf i,j idf j (4)

Textual and visual combination

Using two vocabularies, a textual one T and a visual one V (V mstd or V sif t ), a global score for a document d i and a query q k is defined as a linear combination of the scores corresponding to each modality:

score(q k , d i ) = α score V (q k , d i ) + (1 -α) score T (q k , d i ) (5)
The parameter α permits to add more or less visual information in the overall score used for the ranking of documents.

In the case where more than one visual vocabulary is considered, the final score computation can be generalized as follows:

score(q k , d i ) = j=1,...,|M| α j score j (q k , d i ) (6)
where M = {V j , j = 1, . . . , |M|} denotes a set of multimedia vocabularies containing typically several visual vocabularies and a textual one (e.g. |M| =

3 and M = {V mstd , V sif t , T }) and α j corresponds to the fusion parameter associated to vocabulary V j . In the former two vocabulary case, we had α 1 = α and α 2 = 1 -α.

Learning combination parameters by optimization

It is obvious that the choice of the fusion parameters is very sensitive especially to combine descriptions of different nature (e.g. textual and visual).

It seems that the weight assigned to the text and to the visual information should not be the same because the effectiveness of the model based only on a text descriptor is usually better than those based only on a visual descriptor [START_REF] Tollari | Web image retrieval on imageval: Evidences on visualness and textualness concept dependency in fusion model[END_REF][START_REF] Tollari | Exploiting visual concepts to improve text-based image retrieval[END_REF]. However, it is not easy to set these parameters, even for an expert.

In order to solve this problem, we presented in a previous work [START_REF] Moulin | Combining text/image in wikipediamm task[END_REF][START_REF] Moulin | Impact of visual information on text and content based image retrieval[END_REF],

a method learning the values of the parameters using a set of queries and the corresponding list of relevant documents. This set is divided into training and test sets. Given an evaluation criterion, lets take for instance the Mean Average Precision (MAP) [START_REF] Manning | Introduction to Information[END_REF], the method consists in searching for the combination parameter that optimizes this criterion on the training set of queries. With the obtained value, the effectiveness of the model is then evaluated on the test set of queries.

More precisely, if we consider two descriptions: T based on the text and V based on visual information and if M AP α denotes the MAP obtained on the training set of queries with the value α for the combination parameter, then the optimal value α * is given by:

α * = arg max α∈[0,1] M AP α (7)
We can note that this method is based on the same principle as those detailed in [START_REF] Iskandar | Combining image and structured text retrieval[END_REF][START_REF] Torjmen | Methods for combining content-based and textual-based approaches in medical image retrieval[END_REF] except that it avoids the risk of overestimation. Moreover it generalizes the approach described in [START_REF] Alexandre | Combining independent 36 and unbiased classifiers using weighted average[END_REF][START_REF] Wang | Combining face and iris biometrics for identity verification[END_REF] as it considers not only equal weights but also different weights. For this reason, it can be considered as the state of the art approach to find the best weighting coefficients given a learning dataset. We will further use it in our experiments to evaluate the method introduced in this article over state of art linear combination fusion methods.

Discussion

Although this MAP optimization method has provided good results [START_REF] Moulin | Combining text/image in wikipediamm task[END_REF][START_REF] Moulin | Impact of visual information on text and content based image retrieval[END_REF], it has several drawbacks. Firstly, as the evaluation criterion is not linear in function of the parameter, the optimal parameter can not be calculated analytically. We must therefore use a numerical optimization method such as exhaustive search, gradient descent or Newton's method [START_REF] Nocedal | Numerical optimization[END_REF]. Moreover, depending on the optimization method used, the convergence to the global maximum is not necessarily guaranteed especially when the method is applied to a larger number of descriptors. Finally, the main disadvantage of this approach is that its computational complexity is high. More precisely, given

|M|

Remaining problems

The textual and visual information retrieval model presented in this section can combine a textual modality with one or more visual ones. The optimization method introduced previously to learn the value of the parameters is computational very expensive, especially in the case where several visual modalities are considered. Thus, in the next section, we propose a new approach to learn more efficiently the values of the combination parameters.

Learning combination parameters by Fisher Linear Discriminant

Analysis

To learn efficiently the combination parameters of the Information Retrieval model, we decided to use the Fisher Linear Discriminant Analysis (Fisher-LDA). For that, we first reformulate the learning of the combination parameters as a dimensionality reduction problem in a binary classification context: find the linear combination which best separate relevant and nonrelevant documents for all the queries. This latter problem can be solved using the Fisher-LDA which enables us to derive an analytical method to learn any number of combination parameters for the information retrieval model. Please note that Fisher-LDA is not used to build a classifier but only to find analytically the linear combination, (i.e. the combination parameters) which best separates relevant documents from irrelevant ones.

Reformulation of the learning problem

In our learning problem, each document may be relevant or not relevant with respect to a query. We can thus define a two class problem where objects to classify are couples of document-query and the two classes are relevant or non-relevant. Moreover, each object can be described by a vector of variables corresponding to the scores calculated for each considered description.

More formally, considering the set of documents D and the set of queries Q, the set of objects X is defined as the set D × Q of all the document-query couples x ℓ :

X = {(x ℓ ) ℓ=1,...,|X | , x ℓ = (d i , q k ) i=1,...,|D|, k=1,...,|Q| } (8)
Each of the |X | = |D| × |Q| objects can belong to the set X R of relevant objects or to the set X R of non-relevant objects depending on whether the document is relevant or not for the query:

X R = {x ℓ ∈ X | d i is relevant for q k } (9)
X R = {x ℓ ∈ X | d i is not relevant for q k } (10)
In multimedia information retrieval, each object x ℓ is naturally represented by a vector of variables x ℓ whose components correspond to the scores, for each vocabulary V j in M, between document d i and query q k :

x ℓ = (x ℓ,j ) j=1,...,|M| = (score j (q k , d i )) j=1,...,|M| (11)
where M denotes a set of multimedia vocabularies containing typically several visual vocabularies and a textual one, like for instance |M| = 3 and

M = {V mstd , V sif t , T }.

Resolution by Fisher-LDA

Each object x ∈ X can belong to one of the two classes and it is represented by the vector of scores x = (x j ) j=1,...,|M | corresponding to each vocabulary. Our aim is to determine a linear combination of these scores which best separate the two classes. This problem is equivalent to finding a factor axis which best separates the two populations, considering the class membership of objects. The canonical discriminant analysis provides a solution to this problem by minimizing the Fisher linear discriminant [START_REF] Fisher | The use of multiple measurements in taxonomic problems[END_REF][START_REF] Klecka | Discriminant analysis[END_REF][START_REF] Mika | Fisher discriminant analysis with kernels[END_REF]. Compared to the Principal Component Analysis (PCA) [START_REF] Jolliffe | Principal Component Analysis[END_REF], the advantage of Fisher-LDA is that it takes into account the class membership of objects. Note that within the framework of linear discriminant analysis, Fisher's discriminant can also be used to define an optimal Bayesian classifier under assumptions of normally distributed classes and equal covariances [START_REF] Klecka | Discriminant analysis[END_REF]. However, these more restrictive hypotheses are not required if a canonical analysis is considered.

Given a score vector x = (x j ) j=1,...,|M| and the coefficient vector z = (α j ) j=1,...,|M| , the discriminant function corresponding to the linear combination is given by:

z = t zx = j=1,...,|M| α j x j (12)
Note that with this formulation, variable z is exactly the score corresponding to a query-document couple given in equation 6 and z = (α j ) j=1,...,|M| are the combination coefficients we are looking for.

We can verify that the variance V (z) of variable z is equal to V (z) = t zTz where T is the covariance matrix associated to the scores. Using Huygens theorem, this matrix can be decomposed into an within class covariance matrix W and a between class covariance matrix B. The three |M| × |M| matrices are defined by:

T = 1 |X | |X | ℓ=1 (x ℓ -µ) t (x ℓ -µ) (13)
B = 1 |X | |X R |(µ R -µ) t (µ R -µ) + |X R |(µ R -µ) t (µ R -µ) (14)
W = 1 |X | x ℓ ∈X R (x ℓ -µ R ) t (x ℓ -µ R ) + 1 |X | x ℓ ∈X R (x ℓ -µ R ) t (x ℓ -µ R ) (15)
where µ, µ R and µ R denote the mean data vectors computed respectively over all the set X , over the set X R of relevant documents or over the set X R of non relevant documents. They are defined as:

µ = 1 |X | |X | ℓ=1 x ℓ (16)
µ R = 1 |X R | x ℓ ∈X R x ℓ ( 17
) µ R = 1 |X R | x ℓ ∈X R x ℓ ( 18
)
According to Fisher-LDA, the optimal discriminant function z can be obtained by the maximization of Fisher criterion F (z) defined by:

F (z) = t zBz t zTz (19)
It can be shown that the solution is obtained by calculating the first

eigenvector of matrix T -1 B [52].
In the particular case of a two-class problem, the eigenvector (and thus the combination coefficients) are obtained by the following analytical formula:

z = (α j ) j=1,...,|M| = T -1 (µ R -µ R ) (20)

Learning the combination parameters

The learning strategy is similar to that introduced in section 3. and µ R (equation 18), secondly by calculating the eigenvector z (equation 20) which is, by definition, the desired combination parameter vector.

Utilization of the decision criterion

The aim of the learning step is just to provide an optimal set of combination parameters which are computed according to formula 20. Then, in the test step, these combination parameters are used to process the test queries following the information retrieval model presented in section 3. Firstly, a query provided by a user, is also represented using the bag-of-words model and a document-query score is computed independently for each modality (text and image). Secondly, a global score between the query and each document is computed according to formula 6 using the combination parameters determined in the learning step. Finally the documents are ranked according to this global score and they are returned by the system. The documents with highest scores are considered by the system as the most relevant for the query.

Discussion

It's interesting to note that the two learning methods (MAP optimization and Fisher-LDA) use the maximization of a specific criterion for a training set of queries. In the first one the criterion is the MAP whereas for the new one it is Fisher criterion. Obviously, the two approaches will lead to diverse combination parameters and thus to different evaluation results. If the evaluation measure of the Information Retrieval (IR) system is also the MAP, the first method is expected to give better results.

However, one great advantage of the new method is its efficiency and generality: the combination parameters are obtained analytically from the mean vectors and covariance matrix of data for any number of descriptions.

Its computational cost is low compared to the MAP optimization: it also requires to pre-compute |M|×|Q|×|D| query-document similarities but then, the parameters value estimation only requires the computation of the inverse of the covariance matrix (complexity O(|M| 6 ), with a small |M| value) which is independent on the number of documents and on the precision required for the combination parameters.

Experiments

In order to evaluate our new Fisher LDA learning method, we used the IR test collection ImageCLEF5 . Before presenting the results in section 6, we first describe in this section the ImageCLEF dataset, the system settings and the various experiments that have been made.

Dataset

The ImageCLEFwiki collection was employed for the competition Im- In 2008, the ImageCLEF collection was provided with 75 queries. All queries are not provided with a visual part. Thus, in order to have, for each query, the visual information obtained similarly, we have selected as visual component the two first images ranked by a preliminary textual querying step. These 75 queries will correspond to a training collection for learning the combination parameters.

In ImageCLEF 2009, all the 45 given queries were multimedia. The textual part is composed of few words and the visual part corresponds on average to 1.84 images per query. This second set of queries will be used as a testing collection. Information about the ImageCLEF collection is summarized on

System settings

The lemur software was used with the default parameters as defined in [START_REF] Zhai | Notes on the lemur tfidf model[END_REF]. The k 1 parameter of BM25 formula is set to 1. As |d k | and d avg are not defined for a query q k , b is set to 0 for the tf k,j computation. When tf i,j is estimated for a document d i and a term t j , this parameter b is set to 0.5.

Moreover, stop-words have not been removed and the Porter stemming have been applied. The number of visual words, corresponding to the parameter k of the k-means, has been empirically set to 10 000 for both mstd and sif t descriptions.

Experiments

Evaluation criteria and baseline

In order to evaluate the improvements of the combination of different document descriptions, we firstly run experiments considering only one document description, either textual or visual. The best result obtained will correspond to our baseline.

Only queries of the ImageCLEF 2009 collection are considered. We will use two different evaluation measures: R and M AP (cf. Appendix A). R corresponds to the recall and is obtained by dividing the number of relevant retrieved documents by the number of relevant documents to retrieve. The M AP is the mean average precision which is a common criteria used for example to rank participants in ImageCLEF competition [START_REF] Tsikrika | Overview of the wikipediamm task at imageclef[END_REF][START_REF] Tsikrika | Overview of the wikipediamm task at imageclef[END_REF].

Comparison between the two learning methods

Considering the combination of two descriptions, the goal of this experiment is to compare the new Fisher-LDA method over other linear combination approaches. For that purpose, we use the MAP optimization method introduced in section 3.4 as a reference. Indeed, as explained previously, it can be considered as the state of the art approach to find the best weighting coefficients given a learning dataset.

The two descriptions used are a textual T and a visual (either V mstd or if the Fisher LDA method is as effective as the M AP optimization approach.

V sif t ).

Combining three descriptions with Fisher-LDA

The Fisher LDA method is more efficient than the M AP optimization and can be used to calculate combination parameters for more than two descriptions. Thus, we will then combine T , V mstd and V sif t descriptions using the Fisher LDA learning.

6. Results

Baseline

The first experiments exploit only one textual or visual modality. The results are summarized in table 2. According to the M AP measure, the visual information leads to poor results whatever the description used: for mstd, M AP = 0.0071 and for sif t, M AP = 0.0083. Moreover, only about 10% of the relevant documents have been retrieved when using only the visual information. As for the results when only the textual information is utilized, the M AP reaches 0.1661, and 73% of the relevant documents are retrieved.

The textual results are the best results using only one modality. Thus, we will consider these results as our baseline for comparing the runs combining textual and visual information.

Run

Comparison between the two learning methods

Tables 3 and4 illustrate results combining one textual and one visual description using respectively the M AP optimization and the Fisher LDA learning. Whatever the combined modalities, results are improved compared to the textual baseline. Thus, it confirms the benefit of combining different descriptions of multimedia documents.

For the M AP optimization method, Table 3 shows that the optimal α * parameters, calculated in the training step, differ depending on the description used (α * V mstd = 0.034 and α * V sif t = 0.077). Using these parameters in the test step led to a M AP of 0.1791 (respectively 0.1813) when combining the textual information with the mstd (respectively sif t) description. Compared to the baseline, the M AP is improved while the number of relevant retrieved documents is approximately the same. Thus, it can be concluded that documents are better ranked if a combination of the textual and the visual information is used.

Let's also note that equal weights corresponding to α = 0.5 which have been chosen in other studies [START_REF] Alexandre | Combining independent 36 and unbiased classifiers using weighted average[END_REF][START_REF] Wang | Combining face and iris biometrics for identity verification[END_REF] For the Fisher LDA learning, Table 4 shows that the M AP is increased by 0.1661 to 0.1801 for the mstd description and to 0.1795 for the sif t description. Compared to the M AP optimization, these results are very similar:

on the one hand, the M AP is slightly better for the mstd description (from 0.1791 to 0.1801) and on the other hand, it is a little worse for the sif t description (from 0.1813 to 0.1795). However, notice that for both descriptions, the Fisher LDA learning always leads to a better recall than the one obtained with the M AP optimization approach. Indeed, the recall is 75.09% (respectively 73.67%) for the mstd description and 75.15% (respectively 74.78%)

for the sif t description using the Fisher LDA learning (respectively M AP optimization approach).

Statistically, the M AP obtained after Fisher LDA learning is significantly improved with a p-value of 0.002 (respectively 0.008) for the combination of T and V mstd (respectively T and V sif t ) according to the paired Wilcoxon signed-rank test.

Moreover, if we compute the M AP criteria for α varying from 0 to 0. On figure 6, we have estimated, for the 45 queries, the relative difference between the M AP obtained combining the three descriptions and the one attained with the text only. For about a quarter of queries, results are degraded by the combination of all descriptions. The worst difference (about -50%) is reached for the query building site. However, for most of the queries, the combination leads to an improvement. For half of the queries the difference is higher than 10% and the best improvement is higher than 150% for the query notes on music sheet. For this query, the visual information is intuitively important as for the next best difference queries which are: traffic signs, earth from space and red fruit. Figure 5 presents some examples of relevant images for the queries previously mentioned.

Conclusion and future work

In this paper, we addressed the problem of combining textual and visual information for multimedia information retrieval. Our approach was based on the representation of documents as tf.idf weighted vectors corresponding to several textual and visual vocabularies. Relying on a linear combination of scores from each vocabulary, two methods for learning the combination coefficients were studied.

The first method, already proposed in [START_REF] Moulin | Combining text/image in wikipediamm task[END_REF][START_REF] Moulin | Impact of visual information on text and content based image retrieval[END_REF], can be considered as the

Figure 1 :

 1 Figure 1: Early and late fusion strategies.

Figure 2 :

 2 Figure 2: Multimedia information retrieval model

  in two steps, using a bag of visual words approach[START_REF] Csurka | Visual categorization with bags of keypoints[END_REF]. First, each image is partitioned into a regular grid of 16 × 16 cells with a minimum of 8 × 8 pixels for each cell. This uniform partitioning requires low computational complexity. Next, local features are extracted from each cell to describe its texture properties and color. To this end, we choose to compute two different descriptions: mstd and sif t (Scale-InvariantFeature Transform).The color description, mstd, calculates 6 features equal to the mean and the standard deviation of each normalized color components defined byR/(R + G + B), G/(R + G + B) and (R + G + B)/(3 × 255)where R, G and B are the red, green and blue components of one pixel. The sif t description converts each cell into a 128-dimensional vector which represents the texture information of the image[START_REF] Lowe | Object recognition from local scale-invariant features[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF].In a second step and for each description (mstd and sif t), clustering based on the k-means algorithm is performed over all the cells descriptions to obtain k clusters of features. The center of each cluster corresponds to what we refer to as a visual word. Thus, each description defines a vocabulary (V mstd and V sif t ), the size of which corresponds to the number of clusters.By analogy with the bag of textual words, each visual vocabulary can be used to represent an image, belonging to a document or a query, as a vector of visual terms. This image is decomposed into a 16 × 16 grid and the local mstd or sif t features are computed. The description of each cell is then assigned to the closest visual word using the Euclidean distance and the image is finally represented by a vector of tf.idf weights computed the same way as for text.

  modalities, |D| documents and |Q| queries in the training set, we can first pre-compute |Q| × |D| query-document similarities for each modality. Then, for each iteration of the optimization algorithm, we must evaluate the MAP associated to a given set of parameters which requires a complexity of O(|D| 2 log(|D|)) (sorting and MAP computation). The number of iterations depends on the precision required for the parameters. If n is the number of digits, the number of iterations is polynomial (of order |M|) on n for a grid search.

  [START_REF] Antani | A survey on the use of pattern recognition methods for abstraction, indexing and retrieval of images and video[END_REF]. The combination parameters are first calculated by Fisher-LDA using a training set of queries. Then, the information retrieval model is evaluated with these parameters on a test set of queries. In the training stage, the calculation of the combination parameter is made analytically, firstly by estimating the covariance matrix T (equation 13) and the mean vectors µ R (equation 17)

  ageCLEF 2008 and 2009 [53, 54]. It is one of the few large image retrieval collections with a significant text part. Moreover, the ground truth is available for the two sets of queries proposed in editions 2008 and 2009 of the competition.

Figure 3 :

 3 Figure 3: Images excerpted from ImageCLEF collection.

  For both approaches, we learn the parameters on a training set of queries corresponding to the ImageCLEF 2008 competition. Queries of the ImageCLEF 2009 competition are then used to evaluate the results with the R and M AP measures. The results can be compared to the baseline to verify

Figure 5 :Figure 6 :

 56 Figure 5: The first fifth results for queries red fruit and notes on music sheet using textual information and textual and visual information using the Fisher LDA learning.

  state of the art linear combination method. It is based on the optimization of the MAP and finds the combination parameters that maximizes the MAP on the training set of queries. The second method, which is the new contribution of this article, uses the Fisher-LDA to calculate the optimal linear combination. As shown in section 4.5, it has one great advantage of providing an analytical solution with a low complexity for any number of modalities (typically a text modality and several visual ones).We carried out experiments using ImageCLEF collection extracted from Wikipedia. Considering the combination of two vocabularies (one textual and one visual), we showed that the two previous methods can improve the MAP by about 8% compared to the baseline which used the textual vocabulary only. Considering the combination of three vocabularies (one textual and two visuals), only the second method is relevant and provided an increase of 13% over MAP. A more detailed analysis of the results showed that performance varies depending on the requests. For about a quarter of the queries the results were degraded (down to 50%) as they were improved for other queries (up to a 150% improvement). This work can be extended to other types of multimedia documents and particularly videos. In this context, information from sound, text, image or movement may be used. The textual information may come from different sources as annotation of the video, audio transcription or character recognition in the image part. Given a sampling set of queries for training, Fisher LDA would automatically find the right set of weights corresponding to in-retrieval systems are evaluated on a set of queries Q = {q 1 , . . . , q k , . . . , d |Q| } by the mean average precision:

table 1

 1

	.
		2008 2009
	Number of documents	151 519
	Mean size of documents	33
	Number of queries	75	45
	Mean number of image queries 1.97 1.84
	Mean size of textual queries	2.64 2.93

Table 1 :

 1 Collection ImageCLEF 2008 et 2009.

Table 2 :

 2 Results on the ImageCLEF 2009 collection exploiting textual and visual infor-

		Modalities M AP	R
	Baseline	T	0.1661 0.7336
		V mstd	0.0071 0.0721
		V sif t	0.0083 0.1078
	mation separately.

  provide poor results even lower than text only ones. For that reason, they are not presented here.

	Run	Modalities	M AP	R
	Baseline	T	0.1661 0.7336
	M AP optimization	T +V mstd : α * V mstd : 0.034 0.1791 0.7367 T +V sif t : α * V sif t : 0.077 0.1813 0.7478

Table 3 :

 3 Combination results obtained with the M AP optimization method on Image-CLEF 2009 collection.

  2 using the ImageCLEF 2009 queries, we can compare the learnt Fisher LDA α parameters to optimals as shown by the curves of Figure 4. These curves illustrate that both α V mstd and α V sif t are closed to the optimal results obtained by combining textual and visual information on ImageCLEF 2009.Figure 4: MAP get with ImageCLEF 2009 queries with α varying from 0 to 0.2 for sif t (on the left) and mstd (on the right) descriptors.

		0,19					0,20
		0,18					0,18	V mstd
			V sift				0,14
	MAP	0,16				MAP	0,10
		0,14					0,06
						0,02
		0,12
		0 0,02	0,06	0,1	0,14	0,18 0,2	0 0,02	0,06	0,1	0,14	0,18 0,2
			Run			Modalities			M AP	R
		Baseline			T			0.1661 0.7336
	Fisher LDA learning	T et V

mstd : α V mstd : 0.018730 0.1801 0.7509 T et V sif t : α V sif t : 0.059098 0.1795 0.7515

Table 4 :

 4 Combination results obtained with the Fisher LDA learning on the ImageCLEF

	2009 collection.
	6.3. Combining three descriptions with Fisher-LDA

Table 5

 5 illustrates results combining T , V sif t and V mstd modalities using

	the Fisher LDA learning. Both M AP measure (M AP = 0.1875) and number
	of relevant retrieved documents (R = 0.7614) are improved combining three
	modalities. This M AP improvement is significant with a p-value equals to
	0.0003.

Table 5 :

 5 Fisher LDA learning results on the ImageCLEF 2009 collection combining T , V sif t and V mstd modalities.

Google Images: https://www.google.com/imghp

Exalead Images: www.exalead.com/image

Picsearch: http://www.picsearch.com/

TinEye: http://www.tineye.com/

http://www.imageclef.org

formation sources. Another interesting perspective would be to adjust the weights depending on the queries. This requires to define classes of queries which have the same weighting parameters and to learn both a query model and the corresponding weighting parameters. Given a test query, after determining its class, it would be possible to apply it a particular set of weighting parameters.

Acknowledgement

The authors wish to thank Chris Yukna for his help in proofreading.

Appendix A. Evaluation measures

In order to evaluate the performance of information retrieval systems, there exist different measures based on precision and recall. We consider the recall and the average precision to take into account the ranking of N k documents returned by the system. For a query q k , D k corresponds to the documents of D which are relevant for q k . The recall R is obtained by dividing the number of relevant retrieved documents by the number of relevant documents to retrieve:

The average precision is obtained by:

where rel k (r) is a binary function equals to 1 if the r th returned documents by the system is relevant or 0 otherwise. The performance of information