nips nips2009 nips2009-199 nips2009-199-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Wei Chen, Tie-yan Liu, Yanyan Lan, Zhi-ming Ma, Hang Li
Abstract: Learning to rank has become an important research topic in machine learning. While most learning-to-rank methods learn the ranking functions by minimizing loss functions, it is the ranking measures (such as NDCG and MAP) that are used to evaluate the performance of the learned ranking functions. In this work, we reveal the relationship between ranking measures and loss functions in learningto-rank methods, such as Ranking SVM, RankBoost, RankNet, and ListMLE. We show that the loss functions of these methods are upper bounds of the measurebased ranking errors. As a result, the minimization of these loss functions will lead to the maximization of the ranking measures. The key to obtaining this result is to model ranking as a sequence of classification tasks, and define a so-called essential loss for ranking as the weighted sum of the classification errors of individual tasks in the sequence. We have proved that the essential loss is both an upper bound of the measure-based ranking errors, and a lower bound of the loss functions in the aforementioned methods. Our proof technique also suggests a way to modify existing loss functions to make them tighter bounds of the measure-based ranking errors. Experimental results on benchmark datasets show that the modifications can lead to better ranking performances, demonstrating the correctness of our theoretical analysis. 1
[1] R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison Wesley, May 1999.
[2] C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender. Learning to rank using gradient descent. In ICML ’05: Proceedings of the 22nd International Conference on Machine learning, pages 89–96, New York, NY, USA, 2005. ACM.
[3] Z. Cao, T. Qin, T.-Y. Liu, M.-F. Tsai, and H. Li. Learning to rank: from pairwise approach to listwise approach. In ICML ’07: Proceedings of the 24th International Conference on Machine learning, pages 129–136, New York, NY, USA, 2007. ACM.
[4] W. Chen, T.-Y. Liu, Y. Lan, Z. Ma, and H. Li. Essential loss: Bridge the gap between ranking measures and loss functions in learning to rank. Technical report, Microsoft Research, MSRTR-2009-141, 2009.
[5] D. Cossock and T. Zhang. Statistical analysis of bayes optimal subset ranking. Information Theory, 54:5140–5154, 2008.
[6] Y. Freund, R. Iyer, R. E. Schapire, and Y. Singer. An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4:933–969, 2003.
[7] R. Herbrich, K. Obermayer, and T. Graepel. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers, pages 115–132, Cambridge, MA, 1999. MIT.
[8] K. J¨ rvelin and J. Kek¨ l¨ inen. Cumulated gain-based evaluation of ir techniques. ACM Transa aa actions on Information Systems, 20(4):422–446, 2002.
[9] T. Joachims. Optimizing search engines using clickthrough data. In KDD ’02: Proceedings of the 8th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 133–142, New York, NY, USA, 2002. ACM.
[10] P. Li, C. Burges, and Q. Wu. Mcrank: Learning to rank using multiple classification and gradient boosting. In NIPS ’07: Advances in Neural Information Processing Systems 20, pages 897–904, Cambridge, MA, 2008. MIT.
[11] T.-Y. Liu, J. Xu, T. Qin, W.-Y. Xiong, and H. Li. Letor: Benchmark dataset for research on learning to rank for information retrieval. In SIGIR ’07 Workshop, San Francisco, 2007. Morgan Kaufmann.
[12] Q. L. Olivier Chapelle and A. Smola. Large margin optimization of ranking measures. In NIPS workshop on Machine Learning for Web Search 2007, 2007.
[13] T. Qin, X.-D. Zhang, M.-F. Tsai, D.-S. Wang, T.-Y. Liu, , and H. Li. Query-level loss functions for information retrieval. Information Processing and Management, 44(2):838–855, 2008.
[14] M. Taylor, J. Guiver, S. Robertson, and T. Minka. Softrank: optimizing non-smooth rank metrics. In Proceedings of the International Conference on Web search and web data mining, pages 77–86, Palo Alto, California, USA, 2008. ACM.
[15] M.-F. Tsai, T.-Y. Liu, T. Qin, H.-H. Chen, and W.-Y. Ma. Frank: a ranking method with fidelity loss. In SIGIR ’07: Proceedings of the 30th annual ACM SIGIR conference, pages 383–390, Amsterdam, The Netherlands, 2007. ACM.
[16] F. Xia, T.-Y. Liu, J. Wang, W. Zhang, and H. Li. Listwise approach to learning to rank - theory and algorithm. In ICML ’08: Proceedings of the 25th International Conference on Machine learning, pages 1192–1199. Omnipress, 2008.
[17] J. Xu and H. 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.
[18] Y. Yue, T. Finley, F. Radlinski, and T. Joachims. A support vector method for optimizing average precision. In SIGIR ’07: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 271–278, New York, NY, USA, 2007. ACM.
[19] Z. Zheng, H. Zha, T. Zhang, O. Chapelle, K. Chen, and G. Sun. A general boosting method and its application to learning ranking functions for web search. In NIPS ’07: Advances in Neural Information Processing Systems 20, pages 1697–1704. MIT, Cambridge, MA, 2008. 9