Our ICML 2014 paper “Relative upper confidence bound for the K-armed dueling bandit problem” by Masrour Zoghi, Shimon Whiteson, Remi Munos and Maarten de Rijke is available online now.
This paper proposes a new method for the K-armed dueling bandit problem, a variation on the regular K-armed bandit problem that offers only relative feedback about pairs of arms. Our approach extends the Upper Confidence Bound algorithm to the relative setting by using estimates of the pairwise probabilities to select a promising arm and applying Upper Confidence Bound with the winner as a benchmark. We prove a sharp finite-time regret bound of order O(K log T) on a very general class of dueling bandit problems that matches a lower bound proven in (Yue et al., 2012). In addition, our empirical results using real data from an information retrieval application show that it greatly outperforms the state of the art.
Op 24 mei neem ik tijdens de Universiteitsdag deel aan een debat over de rol van intelligente systemen in ons leven. Andere deelnemers zijn Pieter Adriaans en Ben Kröse.
Datum: 24 mei 2014, 13:45-14:45, tijdens de Universiteitsdag in de Oudemanhuispoort. Zie http://alumni.uva.nl/agenda/content/evenementen/2014/05/universiteitsdag-2014.html
Our SIGIR 2014 paper on “Hierarchical multipliable classification of social text streams“ by Zhaochun Ren, Maria-Hendrike Peetz, Shangsong Liang, Willemijn van Dolen and Maarten de Rijke is available online now.
Hierarchical multi-label classification assigns a document to multiple hierarchical classes. In this paper we focus on hierarchical multi-label classification of social text streams. Concept drift, complicated relations among classes, and the limited length of documents in social text streams make this a challenging problem. Our approach includes three core ingredients: short document expansion, time-aware topic tracking, and chunk-based structural learning. We extend each short document in social text streams to a more comprehensive representation via state-of-the-art entity linking and sentence ranking strategies. From documents extended in this manner, we infer dynamic probabilistic distributions over topics by dividing topics into dynamic “global” topics and “local” topics. For the third and final phase we propose a chunk-based structural optimization strategy to classify each document into multiple classes. Extensive experiments conducted on a large real-world dataset show the effectiveness of our proposed method for hierarchical multi-label classification of social text streams.
Our SIGIR 2014 paper “Fusion helps diversification” by Shangsong Liang, Zhaochun Ren and Maarten de Rijke is available online now.
A popular strategy for search result diversification is to first retrieve a set of documents utilizing a standard retrieval method and then rerank the results. We adopt a different perspective on the problem, based on data fusion. Starting from the hypothesis that data fusion can improve performance in terms of diversity metrics, we examine the impact of standard data fusion methods on result diversification. We take the output of a set of rankers, optimized for diversity or not, and find that data fusion can significantly improve state-of-the art diversification methods. We also introduce a new data fusion method, called diversified data fusion, which infers latent topics of a query using topic modeling, without leveraging outside information. Our experiments show that data fusion methods can enhance the performance of diversification and DDF significantly outperforms existing data fusion methods in terms of diversity metrics.
Our SIGIR 2014 paper “A syntax-aware re-ranker for microblog retrieval” by Aliaksei Severyn, Alessandro Moschitti, Manos Tsagkias, Richard Berendsen and Maarten de Rijke is online now.
We tackle the problem of improving microblog retrieval algorithms by proposing a robust structural representation of (query, tweet) pairs. We employ these structures in a principled kernel learning framework that automatically extracts and learns highly discriminative features. We test the generalization power of our approach on the TREC Microblog 2011 and 2012 tasks. We find that relational syntactic features generated by structural kernels are effec- tive for learning to rank (L2R) and can easily be combined with those of other existing systems to boost their accuracy. In particular, the results show that our L2R approach improves on almost all the participating systems at TREC, only using their raw scores as a single feature. Our method yields an average increase of 5% in retrieval effectiveness and 7 positions in system ranks.
Op 18 mei geef ik een Wakker Worden lezing bij NEMO. Het onderwerp is “Hoe werkt Google?” en er zijn twee momenten waarop de lezing wordt gegeven: 11.00u en 13.00u. Continue reading
Our SIGIR paper “Evaluating Intuitiveness of Vertical-Aware Click Models” by Aleksandr Chuklin, Ke Zhou, Anne Schuth, Floor Sietsma and Maarten de Rijke is available online now.
Modeling user behavior on a search engine result page is important for understanding the users and supporting simulation experiments. As result pages become more complex, click models evolve as well in order to capture additional aspects of user behavior in response to new forms of result presentation.
We propose a method for evaluating the intuitiveness of vertical-aware click models, namely the ability of a click model to capture key aspects of aggregated result pages, such as vertical selection, item selection, result presentation and vertical diversity. This method allows us to isolate model components and therefore gives a multi-faceted view on a model’s performance. We argue that our method can be used in conjunction with traditional click model evaluation metrics such as log-likelihood or perplexity. In order to demonstrate the power of our method in situations where result pages can contain more than one type of vertical (e.g., Image and News) we extend the previously studied Federated Click Model such that it models user clicks on such pages. Our evaluation method yields non-trivial yet interpretable conclusions about the intuitiveness of click models, highlighting their strengths and weaknesses.
Our SIGIR 2014 paper “Personalized Document Re-ranking Based on Bayesian Probabilistic Matrix Factorization” by Fei Cai, Shangsong Liang and Maarten de Rijke is available online now.
A query considered in isolation provides limited information about the searcher’s interest. Previous work has considered various types of user behavior, e.g., clicks and dwell time, to obtain a better understanding of the user’s intent. We consider the searcher’s search and page view history. Using search logs from a commercial search engine, we (i) investigate the impact of features derived from user behavior on reranking a generic ranked list; (ii) optimally integrate the contributions of user behavior and candidate documents by learning their relative importance per query based on similar users. We use dwell time on clicked URLs when estimating the relevance of documents for a query, and perform Bayesian Probabilistic Matrix Factorization as smoothing to predict the relevance. Considering user behavior achieves better rankings than non-personalized rankings. Aggregation of user behavior and query-document features with a user-dependent adaptive weight outperforms combinations with a fixed uniform value.
Our SIGIR 2014 paper “Recipient Recommendation in Enterprises using Communication Graphs and Email Content” by David Graus, David van Dijk, Manos Tsagkias, Wouter Weerkamp and Maarten de Rijke is available online now.
We address the task of recipient recommendation for emailing in enterprises. We propose an intuitive and elegant way of modeling the task of recipient recommendation, which uses both the communication graph (i.e., who are most closely connected to the sender) and the content of the email. Additionally, the model can incorporate evidence as prior probabilities. Experiments on two enterprise email collections show that our model achieves very high scores, and that it outperforms two variants that use either the communication graph or the content in isolation.