Adaptive Relevance Feedback for Large-scale Image Retrieval

Our research addresses the need for an efficient, effective, and interactive access to large-scale image collections. Image retrieval needs are evolving beyond the capabilities of the traditional indexing based on manual annotation, and the most desirable characteristic of any image retrieval system is to be able to deal with automatically-extracted visual indexing features, while providing an intuitive and simple interaction with users. In this thesis, we investigate an innovative query-free retrieval approach that was proposed by Ferecatu and Geman. Starting from an heuristic sampling of the collection, this approach does not require any explicit query, neither keywords nor image-examples. It relies solely on an iterative relevance feedback mechanism driven by the user's subjective judgments of image similarities. At each iteration, the system displays a small set of images and the user is asked to choose the image that best matches in her opinion what she is searching for. The system updates an internal state based on automatically-extracted indexing features, and it displays a new set of images accordingly. The idea is that the system converges towards what the user is searching for, and iteratively it displays more and more relevant images. Our contributions are related to four complementary aspects of the iterative relevance feedback mechanism. First, we formalize a large-scale approach based on a hierarchical tree-like organization of the images computed off-line. Second, we propose a versatile modulation of the exploration/exploitation trade-off based on the consistency of the system internal states between successive iterations. Third, we elaborate a long-term optimization of the similarity metric based on the user searching session logs accumulated off-line. Forth, we propose a dynamic short-term adaptation of the similarity metric based on the relevance feedback events accumulated on-the-fly at each iteration. Furthermore, we round up our research by integrating all our contributions together into one comprehensive retrieval system. Experimental validation was carried out by implementing a web-application which includes all our contributions. This software is distributed to the public under the AGPL Version 3 open-source license. We carried out plenty of user-based evaluation campaigns, and we analyzed systematically all our contributions. We show empirically that each of them improves significantly the retrieval performance of the original framework. Moreover, we show that they are complementary to each other, and their overall integration is consistently beneficial. We foresee that our contributions, along with our open-source web-application, will motivate further investigations and facilitate further experiments. We hope that our research brings the iterative relevance feedback mechanism one step closer to commercial applications.

Adaptive relevance feedback for large-scale image retrieval

François Fleuret, Nicolae Suditu

Content-based image retrieval aims at substituting traditional indexing based on manual annotation by using automatically-extracted visual indexing features. Novel techniques are needed however to efficiently deal with the semantic gap (i.e. the partial match between the low-level features and the visual content). Here, we investigate a query-free retrieval approach first proposed by Ferecatu and Geman. This approach relies solely on an iterative relevance feedback mechanism that drives a heuristic sampling of the collection, and aims to take explicitly into account the semantic gap. Our contributions are related to three complementary aspects. First, we formalize a large-scale approach based on a hierarchical tree-like organization of the images computed off-line. Second, we propose a versatile modulation of the exploration/exploitation trade-off based on the consistency of the system internal states between successive iterations. Third, we elaborate a long-term optimization of the similarity metric based on the user searching session logs accumulated off-line. We implemented a web-application that integrates all our contributions, and distribute it under the AGPL Version 3 free software license. We organized user-based evaluation campaigns using ImageNet dataset, and show empirically that our contributions significantly improve the retrieval performance of the original framework, that they are complementary to each other, and that their overall integration is consistently beneficial.

2016

Exploitation de connaissances sémantiques externes dans les représentations vectorielles en recherche documentaire

Florian Seydoux

The work presented in this thesis deals with several problems met in information retrieval (IR), task which one can summarise as identifying, in a collection of "documents", a subset of documents carrying a sought information, i.e.. relevant for a request expressed by a user. In the case of textual documents, to which we limited ourselves within the framework of this thesis, a significant part of the difficulty lies in ambiguity inherent to human languages. The interaction with the user is also approached in our work, by studying a tool enabling a natural language access to a database. Finally, some techniques which permit the visualisation of large collections of documents are also presented. In this document we first of all describe the principal models of IR by highlighting the relations which exist with some manual technics of IR and document retrieval, developed during the past centuries. We present the principle of document indexing, allowing us to represent documents in a multidimensional space, and the use of this representation by a vectorial model. After having reviewed the principal improvements made these last years with vectorial research systems, including the preprocessings of collections, the indexing mechanism and measurements of similarities between documents, we detail some recent usecases of additional semantic resources (semantic dictionaries, thesaurus, networks, ontologies) reported in scientific literature for the indexing task. We then present more in detail the semantic indexing principle of textual documents by using a thesaurus, consisting in integrating in the document's representation space at least part of the informational contents of hierarchical semantic resources. We propose a general framework allowing us to describe and position various possible techniques to carry out the semantic indexing by adapting, if possible, the specificity of the descriptions resulting from the semantic resources to the data to be represented. We use this framework to describe three families of criteria usable for semantic indexing, each one having its own characteristics. For each of these families, we give the specific algorithms allowing the computation of the criteria. The first two families allow us to consider several criteria already known in feature selection. Moreover we show that, unfortunately, many of these criteria are in fact not very effective for the considered task. The third family allows us to introduce a completely new criterion, the Minimum Redundancy Cut criterion (MRC), built on the basis of the information theory and allowing us to obtain index terms having a probability of occurrence in the collection of documents as well balanced as possible. Finally, we treat the case of semantic index independent of the data (statically choosen), allowing a parameterisation of the level of generality of the index terms. Some of the criteria suggested for semantic indexing has been empirically evaluated. To judge their relevance, we used a well known vectorial system (the Smart IR system) and measured the performances of IR obtained with various reference collections. Those collections was indexed on the basis of the studied criterion, by taking into account the strongly structuring semantic relation of hyper/hyponymy ("is-a" relation), given by two different semantic resources. By comparing results obtained with the performances of a traditional indexing (using the lemmas of the words as representation space), we can show on one hand the relevance of the semantic indexings (in RD) and on the other hand the quality of the proposed criterion (MRC). Concerning man-machine interaction, we present a general outline allowing to build in a relatively fast and systematic way systems with mixed initiative, giving the human user a large (and natural) latitude in the control of the dialogue. This outline is usable in typical database research-task applications (where the database is hidden to the user, but the latter knows exactly which information they wish to find) as well as advice-task applications, for which the users does not necessarily have a precise idea of their needs, and uses the system not only for specifing their wishes, but also a set of propositions as a final result. We particularly stress the techniques allowing us to obtain a robust system, able to deal with speech recognizer failures. Concerning the visualisation of large textual data collections, we present an application of the correspondences analysis (allowing to highlight similarities and oppositions for various groups of entity, built on the basis of additional features present in the DB) to the case of patents data. In addition, we propose a method (based on the bootstrap replication principle) allowing us to determine a confidence interval for relative positionings of various groups, thus permit to immediately judge the reliability of the visually apparent similarities or oppositions.

EPFL2006

Selection and Aggregation of Ranking Criteria for Retrieval from Scientific Publication Databases

Martin Veselý

Selection and aggregation of ranking criteria became an important topic in information retrieval as search is getting more specialized and as volume of electronically available information grows. In this context, document ranking has undergone a shift from purely content-based ranking criteria to combined ranking schemes, integrating additional fea- tures, such as document popularity or impact, or link-based techniques that were widely applied after the success of the PageRank algorithm. In this thesis we experiment with selection and aggregation of ranking criteria, aiming at increasing performance of a specialized scientific search engine. Based on theoretical foundations across several research fields including social choice theory, information re- trieval and digital libraries, we focus on ranking in databases of scientific publications in the field of High Energy Physics, identifying criteria that are pertinent for ranking scientific publications and selecting and aggregating them within a unified framework. The first issue that we address is thus identification and selection of ranking criteria for scientific documents in High Energy Physics. The criteria include the traditional information retrieval relevance that is based on the word similarity, but also the document usage, citation counts and links. In this context we present a novel ranking criterion combining the Hirsch index and the download counts, that we call the d-Hirsch index, taking into account counts of document downloads and assigning the corresponding Hirsch index directly to a document. Criteria selection is then based on correlation analysis between ranked lists of documents. We propose that correlations of entire document listings should be replaced by measuring an overlap on the top-k of the resulting list that should better reflect the independence in terms of ranking. To this end we proposed a new measure for the overlap, the Mean Average Overlap (MeanO). The second issue that we address is the aggregation framework for ranked lists of documents, where we focus on applying linear combination and models trained with ma- chine learning techniques based on logistic regression. As individual scores that are used for ranking are not necessarily comparable to each other, we describe a unified model for normalizing ranking scores before their aggregation, based on statistical properties of the underlying ranking criteria. Another contribution of our work is related to creation of a referential of relevance judgments for information retrieval experimentation in databases of scientific publications in the domain of High Energy Physics. Until now there has been no such resource avail- able that would allow to carry out evaluation of specialized information retrieval in this domain. We propose a method for automated generation of referentials, assuming that document relevance is determined by the document usage. Our approach corresponds to a modification of the pooling method, where validating of relevance judgments is not done by experts in the domain, but is inferred from previous document usage as observed in past user behaviors. The developed ranking models, methods and algorithms were validated in the frame- work of the d-Rank prototype developed in collaboration between EPFL and CERN, aiming at the design of document retrieval mechanisms and interfaces combining a multi- tude of individual specialized ranking criteria. This prototype has been integrated within the CERN institutional repository of scientific publications. We carried out several experiments to support the thesis that rank aggregation pro- vides a superior performance for specialized information retrieval than ranking with single criteria. We experimented with the CERN document server document repository, as well as with artificially generated data showing that rank aggregation can contribute to increased performance of a specialized information retrieval system, as compared to a baseline of the best individually performing ranking criteria. We showed on an experiment done with artificially generated data that if scores of individual ranking criteria follow a comparable distribution skewed to the right, then ag- gregating such ranking criteria can lead to an improvement of the ranking performance in terms of the Mean Average Precision. We reproduced this result on an experiment carried out on a real-world data set created from the CERN database of scientific publications showing that aggregating freshness and the download frequency yielded better ranking results as compared to rankings done with the download frequency and freshness sepa- rately, based on the Mean Reciprocal Rank and S@10 evaluation measures. We observed that local aggregates obtained from documents that were part of the result set performed significantly better than global aggregates, obtained through involving all documents in a collection. These results were confirmed by a 10-fold randomized cross-validation test for both the Mean Reciprocal Rank and the S@10 evaluation measure. We compared performance of the d-Hirsch index with existing ranking criteria at the CERN document server and with aggregates obtained through linear combination of individual scores and through logistic regression. We did not observe significantly better ranking results when ranking documents with the d-Hirsch index or its aggregates as compared to other ranking criteria in the test set. We suggested that selecting ranking criteria based on a novel selection criterion, the mean average overlaps between ranked lists, provides a justified basis for criteria selection.