Selective gradient boosting for effective learning to rank
Lucchese C, Nardini F M, Perego R, Orlando S, Trani S
Settore INF/01 - Informatica Learning-to-Rank task Multiple additive regression trees Learning to Rank Boosting Learning to rank Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni Web search production systems Multiple Additive Regression Trees NDCG
Learning an effective ranking function from a large number of query-document examples is a challenging task. Indeed, training sets where queries are associated with a few relevant documents and a large number of irrelevant ones are required to model real scenarios of Web search production systems, where a query can possibly retrieve thousands of matching documents, but only a few of them are actually relevant. In this paper, we propose Selective Gradient Boosting (SelGB), an algorithm addressing the Learning-to-Rank task by focusing on those irrelevant documents that are most likely to be mis-ranked, thus severely hindering the quality of the learned model. SelGB exploits a novel technique minimizing the mis-ranking risk, i.e., the probability that two randomly drawn instances are ranked incorrectly, within a gradient boosting process that iteratively generates an additive ensemble of decision trees. Specifically, at every iteration and on a per query basis, SelGB selectively chooses among the training instances a small sample of negative examples enhancing the discriminative power of the learned model. Reproducible and comprehensive experiments conducted on a publicly available dataset show that SelGB exploits the diversity and variety of the negative examples selected to train tree ensembles that outperform models generated by state-of-the-art algorithms by achieving improvements of NDCG@10 up to 3.2%.
[2] Christopher JC Burges. 2010. From ranknet to lambdarank to lambdamart: An overview. Learning 11, 23-581 (2010), 81.
[3] G. Capannini, C. Lucchese, F. M. Nardini, S. Orlando, R. Perego, and N. Tonellotto. 2016. Quality versus eficiency in document scoring with learning-to-rank models. Information Processing & Management 52, 6 (2016), 1161 - 1177.
[4] Ruey-Cheng Chen, Luke Gallagher, Roi Blanco, and J. Shane Culpepper. 2017. Eficient Cost-Aware Cascade Ranking in Multi-Stage Retrieval. In Proc. SIGIR. ACM, 445-454.
[5] Van Dang, Michael Bendersky, and W Bruce Croft. 2013. Two-Stage Learning to Rank for Information Retrieval.. In ECIR. Springer, 423-434.
[6] D. Dato, C. Lucchese, F.M. Nardini, S. Orlando, R. Perego, N. Tonellotto, and R. Venturini. 2016. Fast ranking with additive ensembles of oblivious and nonoblivious regression trees. ACM TOIS 35, 2 (2016).
[7] Pinar Donmez and Jaime G Carbonell. 2008. Optimizing estimated loss reduction for active sampling in rank learning. In Proc. ICML. ACM, 248-255.
[8] J. H. Friedman. 2002. Stochastic gradient boosting. Computational Statistics & Data Analysis 38, 4 (2002), 367-378.
[9] Muhammad Ibrahim and Mark Carman. 2014. Undersampling Techniques to Rebalance Training Data for Large Scale Learning-to-Rank. Springer International Publishing, Cham, 444-457.
[10] Kalervo Järvelin and Jaana Kekäläinen. 2002. Cumulated Gain-based Evaluation of IR Techniques. ACM Trans. Inf. Syst. 20, 4 (Oct. 2002), 422-446.
[11] Evangelos Kanoulas, Stefan Savev, Pavel Metrikov, Virgil Pavlu, and Javed Aslam. 2011. A Large-scale Study of the Efect of Training Set Characteristics over Learning-to-rank Algorithms. In Proc. SIGIR. ACM, 1243-1244.
[12] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. 2017. LightGBM: A highly eficient gradient boosting decision tree. In Advances in Neural Information Processing Systems. 3149-3157.
[13] Bo Long, Olivier Chapelle, Ya Zhang, Yi Chang, Zhaohui Zheng, and Belle Tseng. 2010. Active Learning for Ranking Through Expected Loss Optimization. In Proc. SIGIR. ACM, 267-274.
[14] Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Rafaele Perego, Fabrizio Silvestri, and Trani Salvatore. 2018. X-CLEaVER: Learning Ranking Ensembles by Growing and Pruning Trees. ACM Transactions on Intelligent Systems and Technology (TIST), to appear (2018).
[15] Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Rafaele Perego, Fabrizio Silvestri, and Salvatore Trani. Post-Learning Optimization of Tree Ensembles for Eficient Ranking. In Proc. SIGIR. ACM, 949-952.
[16] Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Rafaele Perego, and Salvatore Trani. 2017. X-DART: Blending Dropout and Pruning for Eficient Learning to Rank. In Proc. SIGIR. ACM, 1077-1080.
[17] Claudio Lucchese, Franco Maria Nardini, Rafaele Perego, and Salvatore Trani. 2017. The Impact of Negative Samples on Learning to Rank. In Proc. LEARning Workshop co-located with ACM ICTIR. CEUR-WS.org.
[18] Craig Macdonald, Rodrygo LT Santos, and Iadh Ounis. 2013. The whens and hows of learning to rank for web search. Information Retrieval 16, 5 (2013), 584-628.
[19] Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. 2008. Introduction to information retrieval. Cambridge University Press.
[20] M. D. Smucker, J. Allan, and B. Carterette. 2007. A Comparison of Statistical Significance Tests for Information Retrieval Evaluation. In Proc. CIKM. ACM.
[21] Q. Wu, C.J.C. Burges, K.M. Svore, and J. Gao. 2010. Adapting boosting for information retrieval measures. Information Retrieval (2010).
[22] Emine Yilmaz and Stephen Robertson. 2009. Deep Versus Shallow Judgments in Learning to Rank. In Proc. SIGIR. ACM, 662-663.
[23] D. Yin, Y. Hu, J. Tang, T. Daly, M. Zhou, H. Ouyang, J. Chen, C. Kang, and others. 2016. Ranking relevance in yahoo search. In Proc. ACM SIGKDD. ACM, 323-332.
[24] Hwanjo Yu. 2005. SVM Selective Sampling for Ranking with Application to Data Retrieval. In Proc. ACM SIGKDD. ACM, 354-363.
[25] H. Zaragoza, N. Craswell, M.J. Taylor, S. Saria, and S.E. Robertson. 2004. Microsoft Cambridge at TREC 13: Web and Hard Tracks.. In TREC, Vol. 4. 1-1.
Metrics
Back to previous page
@inproceedings{oai:it.cnr:prodotti:401220,
title = {Selective gradient boosting for effective learning to rank},
author = {Lucchese C and Nardini F M and Perego R and Orlando S and Trani S},
doi = {10.1145/3209978.3210048 and 10.5281/zenodo.2668014 and 10.5281/zenodo.2668013},
year = {2018}
}
0000-0002-2545-0425
BigDataGrapes
Big Data to Enable Global Disruption of the Grapevine-powered Industries
MASTER
Multiple ASpects TrajEctoRy management and analysis
SoBigData
SoBigData Research Infrastructure
