nips nips2009 nips2009-230 nips2009-230-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Fen Xia, Tie-yan Liu, Hang Li
Abstract: This paper is concerned with the consistency analysis on listwise ranking methods. Among various ranking methods, the listwise methods have competitive performances on benchmark datasets and are regarded as one of the state-of-the-art approaches. Most listwise ranking methods manage to optimize ranking on the whole list (permutation) of objects, however, in practical applications such as information retrieval, correct ranking at the top k positions is much more important. This paper aims to analyze whether existing listwise ranking methods are statistically consistent in the top-k setting. For this purpose, we define a top-k ranking framework, where the true loss (and thus the risks) are defined on the basis of top-k subgroup of permutations. This framework can include the permutationlevel ranking framework proposed in previous work as a special case. Based on the new framework, we derive sufficient conditions for a listwise ranking method to be consistent with the top-k true loss, and show an effective way of modifying the surrogate loss functions in existing methods to satisfy these conditions. Experimental results show that after the modifications, the methods can work significantly better than their original versions. 1
[1] P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101:138–156, 2006.
[2] C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender. Learning to rank using gradient descent. In Proc. of ICML’05, pages 89–96, 2005.
[3] Z. Cao, T. Qin, T. Y. Liu, M. F. Tsai, and H. Li. Learning to rank: From pairwise approach to listwise approach. In Proc. of ICML’07, pages 129–136, 2007.
[4] S. Clemencon and N. Vayatis. Ranking the best instances. Journal of Machine Learning Research, 8:2671–2699, 2007.
[5] D. Cossock and T. Zhang. Subset ranking using regression. In Proc. of COLT, pages 605–619, 2006.
[6] D. Cossock and T. Zhang. Statistical analysis of bayes optimal subset ranking. Information Theory, 54:5140–5154, 2008.
[7] Y. Freund, R. Iyer, R. E. Schapire, and Y. Singer. An efficient boosting algorithm for combining preferences. In Proc. of ICML’98, pages 170–178, 1998.
[8] R. Herbrich, T. Graepel, and K. Obermayer. Support vector vector learning for ordinal regression. In Proc. of ICANN’99, pages 97–102, 1999.
[9] P. Li, C. Burges, and Q. Wu. Mcrank: Learning to rank using multiple classification and gradient boosting. In Advances in Neural Information Processing Systems 20(NIPS 07), pages 897–904, Cambridge, MA, 2008. MIT Press.
[10] T. Y. Liu, T. Qin, J. Xu, W. Y. Xiong, and H. Li. Letor: Benchmark dataset for research on learning to rank for information retrieval. In LR4IR 2007, in conjunction with SIGIR 2007, 2007.
[11] J. I. Marden, editor. Analyzing and Modeling Rank Data. Chapman and Hall, London, 1995.
[12] R. Nallapati. Discriminative models for information retrieval. In Proc. of SIGIR’04, pages 64–71, 2004.
[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:838–855, 2008.
[14] C. Rudin. Ranking with a p-norm push. In Proc. of COLT, pages 589–604, 2006.
[15] F. Xia, T. Y. Liu, and H. Li. Top-k consistency of learning to rank methods. Technical report, Microsoft Research, MSR-TR-2009-139, 2009.
[16] F. Xia, T. Y. Liu, J. Wang, W. S. Zhang, and H. Li. Listwise approach to learning to rank theory and algorithm. In Proc. of ICML’08, pages 1192–1199, 2008.
[17] T. Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5:1225–1251, 2004. 9