nach oben

Discover Computing

Erschienen in:

01.06.2010 | Learning to rank for information retrieval

Efficient algorithms for ranking with SVMs

Erschienen in: Discover Computing | Ausgabe 3/2010

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

RankSVM (Herbrich et al. in Advances in large margin classifiers. MIT Press, Cambridge, MA, 2000; Joachims in Proceedings of the ACM conference on knowledge discovery and data mining (KDD), 2002) is a pairwise method for designing ranking models. SVMLight is the only publicly available software for RankSVM. It is slow and, due to incomplete training with it, previous evaluations show RankSVM to have inferior ranking performance. We propose new methods based on primal Newton method to speed up RankSVM training and show that they are 5 orders of magnitude faster than SVMLight. Evaluation on the Letor benchmark datasets after complete training using such methods shows that the performance of RankSVM is excellent.

Vorheriger Artikel Introduction to special issue on learning to rank for information retrieval

Nächster Artikel Gradient descent optimization of smoothed information retrieval metrics

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

SVMLight uses the hinge loss \(\ell(t) = \hbox{max}(0,1-t).\) Though it is different from the squared hinge loss that we use, this causes little difference in performance; see Sect. 5.

This is only feasible in the linear case.

Available at: http://www.cs.cornell.edu/People/tj/svm_light/svm_rank.html.

available at http://www.research.microsoft.com/en-us/um/beijing/projects/letor/.

In fact Burges et al. (2007) are interested in NDCG and there is an additional normalization factor to add in the formula for δ_ij.

We suppose that dim(E) = n, i.e. that the points are linearly independent in feature space or that K has full rank. The same analysis can be followed when dim(E) < n.

Aizerman, M., Braverman, E., & Rozonoer, L. (1964). Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25, 821–837.MathSciNet

Barrett, R., & Romine, C. (1994). Templates for the solution of linear systems: Building blocks for iterative methods. Society for Industrial Mathematics.

Bottou, L., & Bousquet, O. (2008). The tradeoffs of large scale learning. In J. Platt, D. Koller, Y. Singer, & S. Roweis (Eds.), Advances in neural information processing systems (Vol. 20, pp. 161–168).

Burges, C. J., Le, Q. V., & Ragno, R. (2007). Learning to rank with nonsmooth cost functions. In B. Schölkopf, J. Platt, & T. Hofmann (Eds.), Advances in neural information processing systems (Vol. 19).

Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., et al. (2005). Learning to rank using gradient descent. In Proceedings of the international conference on machine learning.

Cao, Y., Xu, J., Liu, T. Y., Li, H., Huang, Y., & Hon, H. W. (2006). Adapting ranking SVM to document retrieval. In SIGIR.

Cao, Z., Qin, T., Liu, T. Y., Tsai, M. F., & Li, H. (2007). Learning to rank: From pairwise approach to listwise approach. In International conference on machine learning.

Chapelle, O. (2007a). Optimization techniques for support vector machines. Talk at the workshop on Numerical tools and fast algorithms for massive data mining, search engines and applications, UCLA, http://www.ipam.ucla.edu/publications/sews2/sews2_7130.pdf

Chapelle, O. (2007b). Training a support vector machine in the primal. Neural Computation, 19(5), 1155–1178.MATHCrossRefMathSciNet

Cossock, D., & Zhang, T. (2006). Subset ranking using regression. In Proceedings of the 19th annual conference on learning theory. Lecture notes in computer science (Vol. 4005, pp. 605–619). Berlin: Springer.

Dembo, R., & Steihaug, T. (1983). Truncated-newton algorithms for large-scale unconstrained optimization. Mathematical Programming, 26(2), 190–212.MATHCrossRefMathSciNet

Freund, Y., Iyer, R., Schapire, R. E., & Singer, Y. (2003). An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4, 933–969.CrossRefMathSciNet

Grinspan, P. (2007). A connection between DCG and a pairwise-defined loss function, Internal Yahoo! memo.

Herbrich, R., Graepel, T., & Obermayer, K. (2000) Large margin rank boundaries for ordinal regression. In B. Smola & S. Schoelkopf (Eds.), Advances in large margin classifiers. Cambridge, MA: MIT Press.

Joachims, T. (2002). Optimizing search engines using clickthrough data. In Proceedings of the ACM conference on knowledge discovery and data mining (KDD), ACM.

Joachims, T. (2005). A support vector method for multivariate performance measures. In International conference on machine learning (ICML), pp. 377–384.

Joachims, T. (2006). Training linear SVMs in linear time. In ACM SIGKDD International conference on knowledge discovery and data mining (KDD), pp. 217–226.

Keerthi, S. S., & DeCoste, D. M. (2005). A modified finite Newton method for fast solution of large scale linear SVMs. Journal of Machine Learning Research, 6, 341–361.MathSciNet

Keerthi, S. S., & Shevade, S. (2007). A fast tracking algorithm for generalized LARS/LASSO. IEEE Transactions on Neural Networks, 18(6), 1826–1830.CrossRef

Kimeldorf, G. S., & Wahba, G. (1970). A correspondence between bayesian estimation on stochastic processes and smoothing by splines. Annals of Mathematical Statistics, 41, 495–502.MATHCrossRefMathSciNet

Lewis, D., Yang, Y., Rose, T., & Li, F. (2004). Rcv1: A new benchmark collection for text categorization research. Journal of Machine Learning Research, 5, 361–397.

Liu, T. Y., Xu, J., Qin, T., Xiong, W., & Li, H. (2007). Letor: Benchmark dataset for research on learning to rank for information retrieval. In LR4IR 2007, in conjunction with SIGIR 2007.

MSR. (2008). Ranking SVM on LETOR. Microsoft Research Asia, http://www.research.microsoft.com/en-us/um/beijing/projects/letor/Baselines /RankSVM.htm.

Schölkopf, B., & Smola, A. (2002). Learning with Kernels. Cambridge, MA: MIT Press.

Shalev-Shwartz, S., Singer, Y., & Srebro, N. (2007). Pegasos: Primal estimated sub-gradient solver for SVM. In Proceedings of the international conference on machine learning.

Shewchuk, J. R. (1994). An introduction to the conjugate gradient method without the agonizing pain. Tech. Rep. CMU-CS-94-125, School of Computer Science, Carnegie Mellon University.

Tsochantaridis, I., Joachims, T., Hofmann, T., & Altun, Y. (2005). Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6, 1453–1484.MathSciNet

Zheng. Z., Zha, H., Zhang, T., Chapelle, O., Chen, K., & Sun, G. (2008), A general boosting method and its application to learning ranking functions for web search. In Advances in neural information processing systems (Vol. 20, pp. 1697–1704). MIT Press.

Titel: Efficient algorithms for ranking with SVMs
Publikationsdatum: 01.06.2010
Erschienen in: Discover Computing / Ausgabe 3/2010
Print ISSN: 2948-2984
Elektronische ISSN: 2948-2992
DOI: https://doi.org/10.1007/s10791-009-9109-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2010

On the choice of effectiveness measures for learning to rank

Introduction to special issue on learning to rank for information retrieval

Knowledge transfer for cross domain learning to rank

Adapting boosting for information retrieval measures

Gradient descent optimization of smoothed information retrieval metrics

Learning to rank with (a lot of) word features

Premium Partner