Robust sparse rank learning for non-smooth ranking measures

ABSTRACT

Recently increasing attention has been focused on directly optimizing ranking measures and inducing sparsity in learning models. However, few attempts have been made to relate them together in approaching the problem of learning to rank. In this paper, we consider the sparse algorithms to directly optimize the Normalized Discounted Cumulative Gain (NDCG) which is a widely-used ranking measure. We begin by establishing a reduction framework under which we reduce ranking, as measured by NDCG, to the importance weighted pairwise classification. Furthermore, we provide a sound theoretical guarantee for this reduction, bounding the realized NDCG regret in terms of a properly weighted pairwise classification regret, which implies that good performance can be robustly transferred from pairwise classification to ranking. Based on the converted pairwise loss function, it is conceivable to take into account sparsity in ranking models and to come up with a gradient possessing certain performance guarantee. For the sake of achieving sparsity, a novel algorithm named RSRank has also been devised, which performs L1 regularization using truncated gradient descent. Finally, experimental results on benchmark collection confirm the significant advantage of RSRank in comparison with several baseline methods.

REFERENCES

• 1: M.R. Asia. Letor3.0: benchmark datasets for learning to rank. Microsoft Corporation, December 2008.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Maria-Florina Balcan , Nikhil Bansal , Alina Beygelzimer , Don Coppersmith , John Langford , Gregory B. Sorkin, Robust reductions from ranking to classification, Machine Learning, v.72 n.1-2, p.139-153, August 2008 [doi>10.1007/s10994-008-5058-6]
• 4: A. Beygelzimer, V. Dani, T. Hayes, and J. Langford. Reductions between classification tasks. Electronic Colloquium on Computational Complexity, 11, 2004.
• 5: Alina Beygelzimer , Varsha Dani , Tom Hayes , John Langford , Bianca Zadrozny, Error limiting reductions between classification tasks, Proceedings of the 22nd international conference on Machine learning, p.49-56, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102358]
• 6: C. Burges, R. Ragno, and Q. Le. Learning to rank with nonsmooth cost functions. In Advances in Neural Information Processing Systems 19, pages 193--200. MIT Press, 2007.
• 7: 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]
• 8: Soumen Chakrabarti , Rajiv Khanna , Uma Sawant , Chiru Bhattacharyya, Structured learning for non-smooth ranking losses, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401906]
• 9: O. Chapelle, Q. Le, and A. Smola. Large margin optimization of ranking measures. In NIPS Workshop on Machine Learning for Web Search, 2007.
• 10: John Guiver , Edward Snelson, Learning to rank with SoftRank and Gaussian processes, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390380]
• 11: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 12: J. Langford and A. Beygelzimer. Sensitive error correcting output codes. Lecture Notes in Computer Science, 3559:158--172, June 2005.
• 13: J. Langford, L. Li and T. Zhang. Sparse online learning via truncated gradient. CoRR, abs/0806.4686, 2008.
• 14: Q. Le and A. Smola. Direct optimization of ranking measures. CoRR, abs/0704.3359, 2007.
• 15: T. Qin, T.-Y. Liu, and H. Li. A general approximation framework for direct optimization of information retrieval measures. MSR-TR-2008-164, Microsoft Research, 2008.
• 16: Michael Taylor , John Guiver , Stephen Robertson , Tom Minka, SoftRank: optimizing non-smooth rank metrics, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341544]
• 17: E. Voorhees. Overview of the TREC 2002 question answering track. In Proceedings of the Eleventh Text Retrieval Conference(TREC), pages 115--123, 2002.
• 18: Jun Xu , Hang Li, AdaRank: a boosting algorithm for information retrieval, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277809]
• 19: J.-Y. Yeh, J.-Y. Lin, H.-R. Ke, and W.-P. Yang. Learning to rank for information retrieval using genetic programming. In LR4IR, 2007.
• 20: Y. Yue and C. Burges. On using simultaneous perturbation stochastic approximation for learning to rank, and the empirical optimality of lambdarank. MSR-TR-2007-115, Microsoft Research, 2007.
• 21: T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annuals of Statistics, 32:56--85, 2004.
• 22: T. Zhang. Some sharp performance bounds for least squares regression with L₁ regularization. Technical Report TR-2007-005, Rutgers Statistics Department, 2007.
• 23: Peng Zhao , Bin Yu, On Model Selection Consistency of Lasso, The Journal of Machine Learning Research, 7, p.2541-2563, 12/1/2006

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
information retrieval, learn to rank, rsrank, truncated gradient