Stochastic Top-k ListNet

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 676–684, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Stochastic Top-k ListNet Tianyi Luo1, Dong Wang1,2, Rong Liu1,3, Yiqiao Pan1,4 1CSLT, RIIT, Tsinghua University, China 2Tsinghua National Lab for Information Science and Technology 3Huilan Limited, Beijing, China 4Beijing University of Posts and Telecommunications, China {lty, lr, pyq}@cslt.riit.tsinghua.edu.cn wangdong99@mails.tsinghua.edu.cn Abstract ListNet is a well-known listwise learning to rank model and has gained much atten- tion in recent years. A particular problem of ListNet, however, is the high computa- tion complexity in model training, main- ly due to the large number of object per- mutations involved in computing the gra- dients. This paper proposes a stochastic ListNet approach which computes the gra- dient within a bounded permutation sub- set. It significantly reduces the computa- tion complexity of model training and al- lows extension to Top-k models, which is impossible with the conventional imple- mentation based on full-set permutation- s. Meanwhile, the new approach utilizes partial ranking information of human la- bels, which helps improve model quality. Our experiments demonstrated that the s- tochastic ListNet method indeed leads to better ranking performance and speeds up the model training remarkably. 1 Introduction Learning to rank aims to learn a model to re- rank a list of objects, e.g., candidate documents in document retrieval. Recent studies show that listwise learning delivers better performance in general than traditional pairwise learning (Liu, 2009), partly attributed to its capability of learning human-labelled scores as a full rank list. A poten- tial disadvantage of listwise learning, however, is the high computation complexity in model train- ing, which is mainly caused by the large number of permutations of the objects to rank. A typical listwise learning method is the List- Net model proposed by Cao et al. (2007). This model has been utilized to tackle many ranking problems, e.g. modeling the hiring behavior in on- line labor markets (Kokkodis et al., 2015), rank- ing sentences in document summarization (Jin et al., 2010), improving detection of musical con- cepts (Yang et al., 2009) and ranking the results in video search (Yang and Hsu, 2008). Basical- ly, ListNet implements the rank function as a neu- ral network (NN), with the objective function set to be the cross entropy between two probability distributions over the object permutations, one de- rived from the human-labelled scores and the other derived from the model prediction (network out- put). In order to deal with the high computation complexity associated with the large number of permutations, Cao et al. (2007) proposed a Top-k approach, which clusters the permutations by the first k objects, so the number of distinct probabili- ties that need to evaluate in model training reduces from n! to n! in the list.(n−k)!, where n is the number of objects To ensure efficiency, k = 1 was selected in the seminal paper (Cao et al., 2007) and in the open source implementation of RankLib (Dang, 2013). This Top-1 approach is a …

Content truncated to 500 words