nips nips2009 nips2009-136 nips2009-136-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Hamed Valizadegan, Rong Jin, Ruofei Zhang, Jianchang Mao
Abstract: Learning to rank is a relatively new field of study, aiming to learn a ranking function from a set of training data with relevancy labels. The ranking algorithms are often evaluated using information retrieval measures, such as Normalized Discounted Cumulative Gain (NDCG) [1] and Mean Average Precision (MAP) [2]. Until recently, most learning to rank algorithms were not using a loss function related to the above mentioned evaluation measures. The main difficulty in direct optimization of these measures is that they depend on the ranks of documents, not the numerical values output by the ranking function. We propose a probabilistic framework that addresses this challenge by optimizing the expectation of NDCG over all the possible permutations of documents. A relaxation strategy is used to approximate the average of NDCG over the space of permutation, and a bound optimization approach is proposed to make the computation efficient. Extensive experiments show that the proposed algorithm outperforms state-of-the-art ranking algorithms on several benchmark data sets. 1
[1] Kalervo J¨ rvelin and Jaana Kek¨ l¨ inen. Ir evaluation methods for retrieving highly relevant a aa documents. In SIGIR 2000: Proceedings of the 23th annual international ACM SIGIR conference on Research and development in information retrieval, pages 41–48, 2000.
[2] Yisong Yue, Thomas Finley, Filip Radlinski, and Thorsten Joachims. A support vector method for optimizing average precision. In SIGIR 2007: Proceedings of the 30th annual Int. ACM SIGIR Conf. on Research and development in information retrieval, pages 271–278, 2007.
[3] Ping Li, Christopher Burges, and Qiang Wu. Mcrank: Learning to rank using multiple classification and gradient boosting. In Neural Information Processing System 2007.
[4] Ramesh Nallapati. Discriminative models for information retrieval. In SIGIR ’04: Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, pages 64–71, New York, NY, USA, 2004. ACM.
[5] Ralf Herbrich, Thore Graepel, and Klaus Obermayer. Support vector learning for ordinal regression. In Int. Conf. on Artificial Neural Networks 1999, pages 97–102, 1999.
[6] Yoav Freund, Raj Iyer, Robert E. Schapire, and Yoram Singer. An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4:933–969, 2003.
[7] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. Learning to rank using gradient descent. In International Conference on Machine Learning 2005, 2005.
[8] Yunbo Cao, Jun Xu, Tie-Yan Liu, Hang Li, Yalou Huang, and Hsiao-Wuen Hon. Adapting ranking svm to document retrieval. In SIGIR 2006: Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, pages 186–193, 2006.
[9] Ming Feng Tsai, Tie yan Liu, Tao Qin, Hsin hsi Chen, and Wei ying Ma. Frank: A ranking method with fidelity loss. In SIGIR 2007: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, 2007.
[10] Rong Jin, Hamed Valizadegan, and Hang Li. Ranking refinement and its application to information retrieval. In WWW ’08: Proc. of the 17th int. conference on World Wide Web.
[11] Steven C.H. Hoi and Rong Jin. Semi-supervised ensemble ranking. In Proceedings of Association for the Advancement of Artificial Intelligence (AAAI2008).
[12] Tao Qin, Tie yan Liu, Ming feng Tsai, Xu dong Zhang, and Hang Li. Learning to search web pages with query-level loss functions. Technical report, 2006.
[13] Christopher J. C. Burges, Robert Ragno, and Quoc V. Le. Learning to rank with nonsmooth cost functions. In Neural Information Processing System 2006, 2006.
[14] Zhe Cao and Tie yan Liu. Learning to rank: From pairwise approach to listwise approach. In International Conference on Machine Learning 2007, pages 129–136, 2007.
[15] Fen Xia, Tie-Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. Listwise approach to learning to rank: theory and algorithm. In Int. Conf. on Machine Learning 2008, pages 1192–1199, 2008.
[16] Michael Taylor, John Guiver, Stephen Robertson, and Tom Minka. Softrank: optimizing nonsmooth rank metrics.
[17] Maksims N. Volkovs and Richard S. Zemel. Boltzrank: learning to maximize expected ranking gain. In ICML ’09: Proceedings of the 26th Annual International Conference on Machine Learning, pages 1089–1096, New York, NY, USA, 2009. ACM.
[18] Ruslan Salakhutdinov, Sam Roweis, and Zoubin Ghahramani. On the convergence of bound optimization algorithms. In Proc. 19th Conf. in Uncertainty in Artificial Intelligence (UAI 03).
[19] Jen-Yuan Yeh, Yung-Yi Lin, Hao-Ren Ke, and Wei-Pang Yang. Learning to rank for information retrieval using genetic programming. In SIGIR 2007 workshop: Learning to Rank for Information Retrieval.
[20] Jun Xu and Hang Li. Adarank: a boosting algorithm for information retrieval. In SIGIR ’07: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 391–398, 2007.
[21] Zhengya Sun, Tao Qin, Qing Tao, and Jue Wang. Robust sparse rank learning for non-smooth ranking measures. In SIGIR ’09: Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, pages 259–266, New York, NY, USA, 2009. ACM.
[22] Tie-Yan Liu, Tao Qin, Jun Xu, Wenying Xiong, and Hang Li. Letor: Benchmark dataset for research on learning to rank for information retrieval. 9