Diversity of Relevance Feedback

The goal of this project is ensure diversity in the relevance feedback results, to improve quality of the user experience.

The project is suitable for 1-3 well-qualified MSc students.

In many creative tasks, the designer will knowsome stock image is good for a design just stumbling upon the image. This “Aha!” moment requires browsing thousands of images by categories. In other words, it requires labeled and categorized images. Labeling hundreds of millions of images, such as the 99.2M images ofthe YFCC100M, is a daunting task, even whenusing some sort of crowdsourcing.An alternate approach consists of devising a mechanism to quickly explore the collection, presenting potentially relevant images to users who can label them as either relevant or irrelevant. Using the labeled examples, the system then refines the image selection presented to the user; this feedback loop continuesuntil the user is satisfied. An example of such a relevance feedback system is the Exquisitor system picturedabove (based on [1]). The ​choice of images​ to present to the user is a difficult problem, especially for the images that the system believes may interest the user. Finding images similar to a query in a collection is a well-understood problem, well served with simple similarity-based approaches. The challenge resides in finding at the sametime a diverse subset, something that can be thought of as selecting one of each in a collection. In otherwords, the challenge is to ensure ​diversity​ as well as ​proximity. Central to our proposal is the ​Half-Space Proximity (HSP) ​graph [2]. This is a sparse subgraph of the complete graph, where each node (that we call the ​center​) in the HSP is connected to a natural number of similar neighbors (the ​spike​ of neighbors). Every node in the spike acts as a proxy of a ​direction​. There is one spike for each object, and computing each spike is linear using a naïve algorithm, hence it has quadratic complexity for the entire collection. There are several challenges in this project, among them is computing efficiently the HSP, computing the spike of a query and assembling a prototype image browser with the described exploring mechanisms.The project is suitable for 2-3 well-qualified MSc students. The intention is to publish the results ininternational research venues, both as a conference paper and a journal paper. And the presentation of the MSc project should be exceptionally visual and interesting!

References * [1]Jan Zahálka, Stevan Rudinac, Björn Þór Jónsson, Dennis C. Koelma, Marcel Worring. ​Blackthorn:Large-Scale Interactive Multimodal Learning​. IEEE Transactions on Multimedia (TMM), 20(3), March 2018. * [2]Chavez E. et al. (2006) Half-Space Proximal: A New Local Test for Extracting a Bounded Dilation Spanner ofa Unit Disk Graph. In: Anderson J.H., Prencipe G., Wattenhofer R. (eds) Principles of Distributed Systems.OPODIS 2005. Lecture Notes in Computer Science, vol 3974. Springer, Berlin, Heidelberg​. * [3]Gylfi Þór Guðmundsson, Björn Þór Jónsson, Laurent Amsaleg. ​A Large-Scale Performance Study ofCluster-Based High-Dimensional Indexing​. Proceedings of the Workshop on Very-Large-Scale MultimediaCorpus, Mining and Retrieval, Firenze, Italy, October 2010.