Jun Xu
Hang Li
Wei-Ying Ma
ABSTRACT
One of the central issues in learning to rank for information retrieval is to develop algorithms that construct ranking models by directly optimizing evaluation measures used in information retrieval such as Mean Average Precision (MAP) and Normalized Discounted Cumulative Gain (NDCG). Several such algorithms including SVMmap and AdaRank have been proposed and their effectiveness has been verified. However, the relationships between the algorithms are not clear, and furthermore no comparisons have been conducted between them. In this paper, we conduct a study on the approach of directly optimizing evaluation measures in learning to rank for Information Retrieval (IR). We focus on the methods that minimize loss functions upper bounding the basic loss function defined on the IR measures. We first provide a general framework for the study and analyze the existing algorithms of SVMmap and AdaRank within the framework. The framework is based on upper bound analysis and two types of upper bounds are discussed. Moreover, we show that we can derive new algorithms on the basis of this analysis and create one example algorithm called PermuRank. We have also conducted comparisons between SVMmap, AdaRank, PermuRank, and conventional methods of Ranking SVM and RankBoost, using benchmark datasets. Experimental results show that the methods based on direct optimization of evaluation measures can always outperform conventional methods of Ranking SVM and RankBoost. However, no significant difference exists among the performances of the direct optimization methods themselves.
- R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison Wesley, May 1999. Google Scholar
Digital Library
- W. Banzhaf, F. D. Francone, R. E. Keller, and P. Nordin. Genetic programming: an introduction: on the automatic evolution of computer programs and its applications. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1998. Google ScholarDigital Library
- C. Burges, R. Ragno, and Q. Le. Learning to rank with nonsmooth cost functions. In Advances in Neural Information Processing Systems 18, pages 395--402. MIT Press, Cambridge, MA, 2006.Google ScholarDigital Library
- C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender. Learning to rank using gradient descent. In Proceedings of the 22nd international conference on Machine learning, pages 89--96, New York, NY, USA, 2005. Google ScholarDigital Library
- Y. Cao, J. Xu, T.-Y. Liu, H. Li, Y. Huang, and H.-W. Hon. Adapting ranking SVM to document retrieval. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, pages 186--193, New York, NY, USA, 2006. Google ScholarDigital Library
- Z. Cao, T. Qin, T.-Y. Liu, M.-F. Tsai, and H. Li. Learning to rank: from pairwise approach to listwise approach. In Proceedings of the 24th international conference on Machine learning, pages 129--136, New York, NY, USA, 2007. Google ScholarDigital Library
- D. Cossock and T. Zhang. Subset ranking using regression. In Proceedings of the 19th Annual Conference on Learning Theory, pages 605--619, 2006. Google ScholarDigital Library
- H. M. de Almeida, M. A. Gonçalves, M. Cristo, and P. Calado. A combined component approach for finding collection-adapted ranking functions based on genetic programming. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 399--406, New York, NY, USA, 2007. Google ScholarDigital Library
- W. Fan, P. Pathak, and L. Wallace. Nonlinear ranking function representations in genetic programming-based ranking discovery for personalized search. Decis. Support Syst., 42(3):1338--1349, 2006. Google ScholarDigital Library
- Y. Freund, R. D. Iyer, R. E. Schapire, and Y. Singer. An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4:933--969, 2003. Google ScholarDigital Library
- Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119--139, 1997. Google ScholarDigital Library
- G. Fung, R. Rosales, and B. Krishnapuram. Learning rankings via convex hull separation. In Advances in Neural Information Processing Systems 18, pages 395--402. MIT Press, Cambridge, MA, 2006.Google ScholarDigital Library
- R. Herbrich, T. Graepel, and K. Obermayer. Large Margin rank boundaries for ordinal regression. MIT Press, Cambridge, MA, 2000.Google Scholar
- K. Jarvelin and J. Kekalainen. IR evaluation methods for retrieving highly relevant documents. In Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, pages 41--48, New York, NY, USA, 2000. Google ScholarDigital Library
- T. Joachims. Optimizing search engines using clickthrough data. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 133--142, New York, NY, USA, 2002. Google ScholarDigital Library
- J. Lafferty and C. Zhai. Document language models, query models, and risk minimization for information retrieval. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, pages 111--119, New York, NY, USA, 2001. Google ScholarDigital Library
- Q. Le and A. Smola. Direct optimization of ranking measures. Technical report, 2007.Google Scholar
- T.-Y. Liu, J. Xu, T. Qin, W. Xiong, and H. Li. Letor: Benchmark dataset for research on learning to rank for information retrieval. In Proceedings of SIGIR 2007 Workshop on Learning to Rank for Information Retrieval (LR4IR 2007), 2007.Google Scholar
- D. Metzler. Direct maximization of rank-based metrics. Technical report, CIIR Technical Report, 2005.Google Scholar
- J. M. Ponte and W. B. Croft. A language modeling approach to information retrieval. In Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, pages 275--281, New York, NY, USA, 1998. Google ScholarDigital Library
- T. Qin, X.-D. Zhang, D.-S. Wang, T.-Y. Liu, W. Lai, and H. Li. Ranking with multiple hyperplanes. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 279--286, New York, NY, USA, 2007. Google ScholarDigital Library
- S. E. Robertson and D. A. Hull. The TREC-9 filtering track final report. In Proceedings of the 9th Text REtrieval Conference, 2000.Google Scholar
- M. Taylor, J. Guiver, S. Robertson, and T. Minka. Softrank: Optimising non-smooth rank metrics. In Proceedings of SIGIR 2007 Workshop on Learning to Rank for Information Retrieval (LR4IR 2007), 2007. Google ScholarDigital Library
- A. Trotman. Learning to rank. Inf. Retr., 8(3):359--381, 2005. Google ScholarDigital Library
- M.-F. Tsai, T.-Y. Liu, T. Qin, H.-H. Chen, and W.-Y. Ma. Frank: a ranking method with fidelity loss. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 383--390, New York, NY, USA, 2007. Google ScholarDigital Library
- I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun. Large margin methods for structured and interdependent output variables. J. Mach. Learn. Res., 6:1453--1484, 2005. Google ScholarDigital Library
- J. Xu and H. Li. Adarank: a boosting algorithm for information retrieval. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 391--398, New York, NY, USA, 2007. Google ScholarDigital Library
- J.-Y. Yeh, J.-Y. Lin, H.-R. Ke, and W.-P. Yang. Learning to rank for information retrieval using genetic programming. In Proceedings of SIGIR 2007 Workshop on Learning to Rank for Information Retrieval (LR4IR 2007), 2007.Google Scholar
- H. Yu. SVM selective sampling for ranking with application to data retrieval. In Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 354--363, New York, NY, USA, 2005. Google ScholarDigital Library
- Y. Yue, T. Finley, F. Radlinski, and T. Joachims. A support vector method for optimizing average precision. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 271--278, New York, NY, USA, 2007. Google ScholarDigital Library
- 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 Advances in Neural Information Processing Systems 20, pages 1697--1704. MIT Press, Cambridge, MA, 2008.Google Scholar
Index Terms
- Directly optimizing evaluation measures in learning to rank
Recommendations
Learning to rank by optimizing expected reciprocal rank
AIRS'11: Proceedings of the 7th Asia conference on Information Retrieval TechnologyLearning to rank is one of the most hot research areas in information retrieval, among which listwise approach is an important research direction and the methods that directly optimizing evaluation metrics in listwise approach have been used for ...
Direct Optimization of Evaluation Measures in Learning to Rank Using Particle Swarm
DEXA '10: Proceedings of the 2010 Workshops on Database and Expert Systems ApplicationsOne of the central issues in Learning to Rank (L2R) for Information Retrieval is to develop algorithms that construct ranking models by directly optimizing evaluation measures used in IR such as Precision at n, Mean Average Precision and Normalized ...
Directly optimizing evaluation measures in learning to rank based on the clonal selection algorithm
CIKM '10: Proceedings of the 19th ACM international conference on Information and knowledge managementOne fundamental issue of learning to rank is the choice of loss function to be optimized. Although the evaluation measures used in Information Retrieval (IR) are ideal ones, in many cases they can't be used directly because they do not satisfy the ...
Comments