Large scale max-margin multi-label classification with priors

Dr. Manik Varma
Microsoft Research India. Sept. 17, 2010 @ 02:00 pm
BSB 361, Dept. of CSE, IIT Madras

Abstract
We propose a max-margin formulation for the multi-label classification problem where the goal is to tag a data point with a set of pre-specified labels. Given a set of $L$ labels, a data point can be tagged with any of the $2^L$ possible subsets. The main challenge therefore lies in optimising over this exponentially large label space subject to label correlations.

Existing solutions take either of two approaches. The first assumes, {\it a priori}, that there are no label correlations and independently trains a classifier for each label (as is done in the 1-vs-All heuristic). This reduces the problem complexity from exponential to linear and such methods can scale to large problems. The second approach explicitly models correlations by pairwise label interactions. However, the complexity remains exponential unless one assumes that label correlations are sparse. Furthermore, the learnt correlations reflect the training set biases.

We take a middle approach that assumes labels are correlated but does not incorporate pairwise label terms in the prediction function. We show that the complexity can still be reduced from exponential to linear while modelling dense pairwise label correlations. By incorporating correlation priors we can overcome training set biases and improve prediction accuracy. We provide a principled interpretation of the 1-vs-All method and show that it arises as a special case of our formulation. We also develop efficient optimisation algorithms that can be orders of magnitude faster than the state-of-the-art.

Learning to re-rank: Query-dependent image re-ranking using click data

Dr. Manik Varma
Microsoft Research India. Sept. 17, 2010 @ 02:30 pm
BSB 361, Dept. of CSE, IIT Madras
Abstract
Our objective is to improve the performance of keyword based image search engines by re-ranking their baseline results. We address three limitations of existing search engines in this paper. First, there is no straight-forward, fully automated way of going from textual queries to visual features. Image search engines are therefore forced to rely on static and textual features alone for ranking. Visual features are used only for secondary tasks such as finding similar images. Second, image rankers are trained on query-image pairs labeled with relevance judgements determined by human experts. Such labels are well known to be noisy due to various factors including ambiguous queries, unknown user intent and subjectivity in human judgements. This leads to learning a sub-optimal ranker. Finally, a static ranker is typically built to handle disparate user queries. The ranker is therefore unable to adapt its parameters to suit the query at hand which again leads to sub-optimal results. All these problems can be mitigated by incorporating a second re-ranking stage leveraging user click data.

We hypothesise that images clicked in response to a query are mostly relevant to the query. We therefore aim to re-rank the original search results so as to promote images that are likely to be clicked to the top of the ranked list. This is achieved by using Gaussian Process regression to predict the normalised click count for each image. Re-ranking is then carried out based on the predicted click counts and the original ranking scores. It is demonstrated that the proposed algorithm can significantly boost the performance of a baseline search engine such as Bing image search.

Bio

Dr Manik VarmaI received a bachelor's degree in Physics from St. Stephen's College, University of Delhi in 1997 and another one in Computation from the University of Oxford in 2000 on a Rhodes Scholarship. I then stayed on at Oxford on a University Scholarship and obtained a DPhil in Engineering in 2004. Before joining Microsoft Research I was a Post-Doctoral Fellow at MSRI Berkeley. My research interests lie in the areas of machine learning and computer vision.