Ming Tan
ABSTRACT
We present a novel learning algorithm, DirectRank, which directly and exactly optimizes ranking measures without resorting to any upper bounds or approximations. Our approach is essentially an iterative coordinate ascent method. In each iteration, we choose one coordinate and only update the corresponding parameter, with all others remaining fixed. Since the ranking measure is a stepwise function of a single parameter, we propose a novel line search algorithm that can locate the interval with the best ranking measure along this coordinate quite efficiently. In order to stabilize our system in small datasets, we construct a probabilistic framework for document-query pairs to maximize the likelihood of the objective permutation of top-$\tau$ documents. This iterative procedure ensures convergence. Furthermore, we integrate regression trees as our weak learners in order to consider the correlation between the different features. Experiments on LETOR datasets and two large datasets, Yahoo challenge data and Microsoft 30K web data, show an improvement over state-of-the-art systems.
- M. Bazaraa, H. Sherali and C. Shetty. Nonlinear Programming: Theory and Algorithms, 3rd Edition. Wiley-Interscience, 2006.Google Scholar
Cross Ref
- D. Bertsimas, A. Chang and C. Rudin. Integer Optimization Methods for Supervised Ranking. Technical Report, 388--11, 2011.Google Scholar
- S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University, 2004. Google ScholarCross Ref
- C. Burges, R. Ragno and Q. Le. Learning to Rank with Nonsmooth Cost Functions. NIPS, 19:193--200, 2007.Google Scholar
- C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender. Learning to Rank Using Gradient Descent. ICML, 89--96, 2005. Google ScholarDigital Library
- C. Burges. From RankNet to LambdaRank to LambdaMART: An Overview. Microsoft Research Technical Report, MSR-TR-2010-82.Google Scholar
- C. Calauzenes, N. Usunier, P. Gallinari. On the (Non-)existence of Convex, Calibrated Surrogate Losses for Ranking. NIPS, 197--205, 2012Google Scholar
- Z. Cao, T. Qin, T. Liu, M. Tsai and H. Li. Learning to Rank: From Pairwise to Listwise Approach. ICML, 129--136, 2007 Google ScholarDigital Library
- S. Chakrabarti, R. Khanna, U. Sawant, and C. Bhattacharyya. Structured Learning for Non-smooth Ranking Losses. KDD, 88--96, 2008 Google ScholarDigital Library
- O. Chapelle and Y. Chang. Yahoo! Learning to Rank Challenge Overview. JMLR-Proceedings Track, 14:1--24, 2011Google Scholar
- O. Chapelle and M. Wu. Gradient Descent Optimization of Smoothed Information Retrieval Metrics. Information Retrieval, 13(3):216--235, 2010 Google ScholarDigital Library
- W. Cohen, R. Schapire, and Y. Singer. Learning to Order Things. JAIR, 10:243--270, 1999. Google ScholarDigital Library
- K. Crammer and Y. Singer. Pranking with Ranking. NIPS, 14:641--647, 2001.Google Scholar
- Y. Freund, R. Iyer, R. Schapire and Y. Singer. An Efficient Boosting Algorithm for Combining Preferences. JMLR, 4:933--969, 2003. Google ScholarDigital Library
- J. Friedman. Greedy Function Approximation: A Gradient Boosting Machine. The Annals of Statistics, 29(5):1189--1232, 2001.Google ScholarCross Ref
- E. Harrington. Online Ranking/Collaborative Filtering Using the Perceptron Algorithm. ICML Workshop then Conference, 20(1):250, 2003.Google Scholar
- R. Herbrich, T. Graepel, and K. Obermayer. Support Vector Learning for Ordinal Regression. ICANN, 97--102, 1999.Google Scholar
- T. Joachims. Optimizing Search Engines Using Clickthrough Data. KDD, 1:7--102, 2002.Google Scholar
- J. Kuo, P. Cheng, and H. Wang. Learning to Rank from Bayesian Decision Inference. CIKM, 827--836, 2009. Google ScholarDigital Library
- Q. Le and A. Smola. Direct Optimization of Ranking Measures. NICTA Tech report, 2007.Google Scholar
- T. Liu. Learning to Rank for Information Retrieval. Springer, 2011.Google ScholarCross Ref
- D. McAllester, T. Hazan, and J. Keshet. Direct loss minimization for structured prediction. ICML, 23:1594--1602, 2010.Google Scholar
- D. Metzler and W. Croft. Linear Feature-Based Models for Information Retrieval. Information Retrieval, 10(3):257--274, 2007. Google ScholarDigital Library
- F. Och. Minimum Error Rate Training in Statistical Machine Translation. ACL, 311--318, 2003.Google Scholar
- R. Plackett. The Analysis of Permutations. Applied Statistics, 193--202, 1975.Google Scholar
- T. Qin, T. Liu, and H. Li. A General Approximation Framework for Direct Optimization of Information Retrieval Measures, Information Retrieval, 13(4):375--397, 2010. Google ScholarDigital Library
- T. Qin, T. Liu, J. Xu, and H. Li. LETOR: A Benchmark Collection for Research on Learning to Rank for Information Retrieval. Information Retrieval, 13(4):346--374, 2010. Google ScholarDigital Library
- T. Qin, X. Zhang, M. Tsai, D. Wang, T. Liu, and H. Li. Query-level Loss Functions for Information Retrieval. Information Processing and Management, 44(2):838--855, 2008. Google ScholarDigital Library
- P. Ravikumar, A. Tewari, and E. Yang. On NDCG Consistency of Listwise Ranking Methods. AISTATS, 618--626, 2011.Google Scholar
- C. Rudin. The P-Norm Push: A Simple Convex Ranking Algorithm that Concentrates at the Top of the List. JMLR, 10:2233--2271, 2009. Google ScholarDigital Library
- R. Schapire and Y. Freund. Boosting: Foundations and Algorithms. MIT Press, 2012. Google ScholarCross Ref
- A. Shashua and A. Levin. Ranking with Large Margin Principle: Two Approaches. NIPS, 937--944, 2003.Google Scholar
- M. Tan, T. Xia, L. Guo and S. Wang. Direct Optimization of Ranking Measures for Learning to Rank Models. Technical Report, 2013.Google Scholar
- M. Taylor, J. Guiver, S. Robertson and T. Minka. Softrank: Optimizing Non-smooth Rank Metrics. WSDM, 77--86, 2008. Google ScholarDigital Library
- M. Tsai, T. Liu, Q. Tao, H. Chen and W. Ma. Frank: A Ranking Method with Fidelity Loss. SIGIR, 383--390, 2007. Google ScholarDigital Library
- S. Tyree, K. Weinberger, K. Agrawal, and J. Paykin. Parallel boosted regression trees for web search ranking. WWW, 387--396, 2011. Google ScholarDigital Library
- H. Valizadegan, R. Jin, R. Zhang, and J. Mao. Learning to Rank by Optimizing NDCG Measure. NIPS, 1883--1891, 2009.Google Scholar
- V. Vapnik. Statistical Learning Theory. John Wiley, 1998.Google ScholarDigital Library
- F. Xia, T. Liu, J. Wang, W. Zhang, and H. Li. Listwise Approach to Learning to Rank: Theory and Algorithm. ICML, 1192--1199, 2008. Google ScholarDigital Library
- J. Xu, T. Liu, M. Lu, H. Li, and W. Ma. Directly Optimizing Evaluation Measures in Learning to Rank. SIGIR, 107--114, 2008. Google ScholarDigital Library
- J. Xu and H. Li. AdaRank: A Boosting Algorithm for Information Retrieval. SIGIR, 391--398, 2007. Google ScholarDigital Library
- Y. Yue, T. Finley, F. Radlinski, and T. Joachims. A Support Vector Method for Optimizing Average Precision. SIGIR, 271--278, 2007. Google ScholarDigital Library
- Q. Wu, C. Burges, K. Svore, and J. Gao. Adapting Boosting for Information Retrieval Measures. Information Retrieval, 13(3):254--270, 2010. Google ScholarDigital Library
Index Terms
- Direct optimization of ranking measures for learning to rank models
Recommendations
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 ...
Learning to rank code examples for code search engines
Source code examples are used by developers to implement unfamiliar tasks by learning from existing solutions. To better support developers in finding existing solutions, code search engines are designed to locate and rank code examples relevant to user'...
Learning to Rank with Ensemble Ranking SVM
In this paper, we propose a novel learning to rank method using Ensemble Ranking SVM. Ensemble Ranking SVM is based on Ranking SVM which has been commonly used for learning to rank. The basic idea of Ranking SVM is to formulate the problem of learning ...
Comments