SOLAR: Scalable Online Learning Algorithms for Ranking

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1692–1701, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics SOLAR: Scalable Online Learning Algorithms for Ranking Jialei Wang1, Ji Wan2,3, Yongdong Zhang2, Steven C. H. Hoi3∗ 1 Department of Computer Science, The University of Chicago, USA 2 Key Laboratory of Intelligent Information Processing, ICT, CAS, China 3 School of Information Systems, Singapore Management University, Singapore jialei@cs.uchicago.edu, {wanji,zhyd}@ict.ac.cn, chhoi@smu.edu.sg Abstract Traditional learning to rank methods learn ranking models from training data in a batch and offline learning mode, which suffers from some critical limitations, e.g., poor scalability as the model has to be re- trained from scratch whenever new train- ing data arrives. This is clearly non- scalable for many real applications in practice where training data often arrives sequentially and frequently. To overcome the limitations, this paper presents SO- LAR — a new framework of Scalable On- line Learning Algorithms for Ranking, to tackle the challenge of scalable learning to rank. Specifically, we propose two novel SOLAR algorithms and analyze their IR measure bounds theoretically. We conduct extensive empirical studies by comparing our SOLAR algorithms with conventional learning to rank algorithms on benchmark testbeds, in which promising results vali- date the efficacy and scalability of the pro- posed novel SOLAR algorithms. 1 Introduction Learning to rank [27, 8, 29, 31, 7] aims to learn some ranking model from training data using ma- chine learning methods, which has been actively studied in information retrieval (IR). Specifically, consider a document retrieval task, given a query, a ranking model assigns a relevance score to each document in a collection of documents, and then ranks the documents in decreasing order of rele- vance scores. The goal of learning to rank is to build a ranking model from training data of a set of queries by optimizing some IR performance mea- sures using machine learning techniques. In lit- erature, various learning to rank techniques have ∗ The corresponding author. This work was done when the first two authors visited Dr Hoi’s group. been proposed, ranging from early pointwise ap- proaches [15, 30, 28], to popular pairwise [26, 18, 3], and recent listwise approaches [5, 38]. Learn- ing to rank has many applications, including doc- ument retrieval, collaborative filtering, online ad, answer ranking for online QA in NLP [33], etc. Most existing learning to rank techniques fol- low batch and offline machine learning methodol- ogy, which typically assumes all training data are available prior to the learning task and the rank- ing model is trained by applying some batch learn- ing method, e.g., neural networks [3] or SVM [4]. Despite being studied extensively, the batch learn- ing to rank methodology has some critical limi- tations. One of serious limitations perhaps is its poor scalability for real-world web applications, where the ranking model has to be re-trained from scratch whenever new training data arrives. This is apparently inefficient and non-scalable since training …

Content truncated to 500 words