Generalization analysis of listwise learning-to-rank algorithms

ABSTRACT

This paper presents a theoretical framework for ranking, and demonstrates how to perform generalization analysis of listwise ranking algorithms using the framework. Many learning-to-rank algorithms have been proposed in recent years. Among them, the listwise approach has shown higher empirical ranking performance when compared to the other approaches. However, there is no theoretical study on the listwise approach as far as we know. In this paper, we propose a theoretical framework for ranking, which can naturally describe various listwise learning-to-rank algorithms. With this framework, we prove a theorem which gives a generalization bound of a listwise ranking algorithm, on the basis of Rademacher Average of the class of compound functions. The compound functions take listwise loss functions as outer functions and ranking models as inner functions. We then compute the Rademacher Averages for existing listwise algorithms of ListMLE, ListNet, and RankCosine. We also discuss the tightness of the bounds in different situations with regard to the list length and transformation function.

REFERENCES

• 1: Agarwal, S., & Niyogi, P. (2005). Stability and generalization of bipartite ranking algorithms. Proceedings of 18th Annual Conference on Learning Theory (pp. 32--47).
• 2: Peter L. Bartlett , Shahar Mendelson, Rademacher and gaussian complexities: risk bounds and structural results, The Journal of Machine Learning Research, 3, 3/1/2003
• 3: Bousquet, O., Boucheron, S., & Lugosi, G. (2004). Introduction to statistical learning theory. Advanced Lectures on Machine Learning, 169--207.
• 4: Zhe Cao , Tao Qin , Tie-Yan Liu , Ming-Feng Tsai , Hang Li, Learning to rank: from pairwise approach to listwise approach, Proceedings of the 24th international conference on Machine learning, p.129-136, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273513]
• 5: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 6: Herbrich, R., Obermayer, K., & Graepel, T. (1999). Large margin rank boundaries for ordinal regression. Advances in Large Margin Classifiers., 115--132.
• 7: Yanyan Lan , Tie-Yan Liu , Tao Qin , Zhiming Ma , Hang Li, Query-level stability and generalization in learning to rank, Proceedings of the 25th international conference on Machine learning, p.512-519, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390221]
• 8: Li, P., Burges, C., & Wu, Q. (2007). Mcrank: Learning to rank using multiple classification and gradient boosting. Proceedings of 21st Annual Conference on Neural Information Processing Systems (pp. 845--852).
• 9: Liu, T.-Y., & Lan, Y. (2008). Generalization analysis of listwise learning-to-rank algorithms using rademacher average (Technical Report MSR-TR-2008-155). Microsoft Research.
• 10: Mendelson, S. (2001). Rademacher averages and phase transitions in glivenko-cantelli classes. IEEE Transactions on Information Theory, 48(1), 251--263.
• 11: Shahar Mendelson, A few notes on statistical learning theory, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY, 2003
• 12: Tao Qin , Xu-Dong Zhang , Ming-Feng Tsai , De-Sheng Wang , Tie-Yan Liu , Hang Li, Query-level loss functions for information retrieval, Information Processing and Management: an International Journal, v.44 n.2, p.838-855, March, 2008 [doi>10.1016/j.ipm.2007.07.016]
• 13: Fen Xia , Tie-Yan Liu , Jue Wang , Wensheng Zhang , Hang Li, Listwise approach to learning to rank: theory and algorithm, Proceedings of the 25th international conference on Machine learning, p.1192-1199, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390306]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory