skip to main content
10.1145/1277741.1277791acmconferencesArticle/Chapter ViewAbstractPublication PagesirConference Proceedingsconference-collections
Article

Ranking with multiple hyperplanes

Published:23 July 2007Publication History

ABSTRACT

The central problem for many applications in Information Retrieval is ranking and learning to rank is considered as a promising approach for addressing the issue. Ranking SVM, for example, is a state-of-the-art method for learning to rank and has been empirically demonstrated to be effective. In this paper, we study the issue of learning to rank, particularly the approach of using SVM techniques to perform the task. We point out that although Ranking SVM is advantageous, it still has shortcomings. Ranking SVM employs a single hyperplane in the feature space as the model for ranking, which is too simple to tackle complex ranking problems. Furthermore, the training of Ranking SVM is also computationally costly. In this paper, we look at an alternative approach to Ranking SVM, which we call "Multiple Hyperplane Ranker" (MHR), and make comparisons between the two approaches. MHR takes the divide-and-conquer strategy. It employs multiple hyperplanes to rank instances and finally aggregates the ranking results given by the hyperplanes. MHR contains Ranking SVM as a special case, and MHR can overcome the shortcomings which Ranking SVM suffers from. Experimental results on two information retrieval datasets show that MHR can outperform Ranking SVM in ranking.

References

  1. Baeza-Yates, R., Ribeiro-Neto, B. Modern Information Retrieval, Addison Wesley, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Borda, J. C. Mémoire sur les élections au scrutin. Histoire de l'Académie Royale des Sciences, 1781.Google ScholarGoogle Scholar
  3. Burges, C. J. C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., Hullender, G. Learning to Rank using Gradient Descent, 22nd International Conference on Machine Learning, Bonn, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Cao, Y., Xu, J., Liu, T. Y., Li, H., Huang, Y., Hon, H. W. Adapting ranking SVM to document retrieval. In SIGIR 2006: Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, Seattle, Washington, USA. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. Chirita, P. A., Diederich, J., and Nejdl, W. MailRank: using ranking for spam detection, Proceedings of the 14th ACM international conference on Information and knowledge management, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Chu , W., and S. Sathiya Keerthi, New approaches to support vector ordinal regression, Proceedings of the 22nd international conference on Machine learning, p. 145--152, August 07-11, 2005, Bonn, Germany. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Cohen, W. W., Schapire, R. E., and Singer, Y. Learning to order things, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.451--457, July 1998, Denver, Colorado, United States. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Collins, M. Ranking algorithms for named-entity extraction: boosting and the voted perceptron, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Dave, K., Lawrence, S., Pennock, D. M. Mining the peanut gallery: opinion extraction and semantic classification of product reviews, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Dietterich, T. G. and Bakiri, G. Solving multiclass learning problems via error correcting output codes. Journal of artificial Intelligence Research, 2:263--286, January 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Dwork, C., Kumar, R., Naor, M., and Sivakumar, D. Rank aggregation methods for the web. In Proceedings of the 10th International World Wide Web Conference. 2001, 613--622. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Fagin, R., Kumar, R., and Sivakumar, D. Efficient similarity search and classification via rank aggregation. In Proceedings of the 2003 ACM SIGMOD International Conference on management of data. San Diego, 2003, 301--312. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. Freund, Y., Iyer, R., Schapire, R., & Singer, Y., An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 2003 (4). Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Gyongyi, Z., Garcia-Molina, H., and Pedersen, J. Combating web spam with TrustRank. In Proceedings of the 30th VLDB Conference, Sept. 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Harrington, E. F. Online Ranking/Collaborative filtering using the Perceptron Algorithm. Proceedings of the 20th International Conference on Machine Learning, pages 250--257, 2003.Google ScholarGoogle Scholar
  16. Har-Peled, S. , Roth, D., and Zimak, D. Constraint classification: A new approach to multiclass classification and ranking. In Proc. Advances in Neural Information Processing Systems (NIPS'02), 2002.Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Hersh, W. R., Buckley, C., Leone, T. J., and Hickam, D. H. OHSUMED: An interactive retrieval evaluation and new large test collection for research. Proceedings of the 17th Annual ACM SIGIR Conference, pages 192--201, 1994. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Herbrich, R., Graepel, T., & Obermayer, K. (2000). Large margin rank boundaries for ordinal regression. Advances in Large Margin Classiers, MIT Press, Pages: 115--132.Google ScholarGoogle Scholar
  19. Hsu, C. W., and Lin, C. J. A comparison of methods for multi-class support vector machines. IEEE Transactions on Neural Networks, 13(2):415--425, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Jarvelin, K., & Kekalainen, J. (2000). IR evaluation methods for retrieving highly relevant documents. Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.41--48, July 24-28, 2000, Athens, Greece. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Jarvelin, K., & Kekalainen, J. Cumulated Gain-Based Evaluation of IR Techniques, ACM Transactions on Information Systems, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. Joachims, T. Making large-Scale SVM Learning Practical. Advances in Kernel Methods - Support Vector Learning, B. Schölkopf and C. Burges and A. Smola (ed.), MIT-Press, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. Joachims, T. Optimizing Search Engines Using Clickthrough Data, Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD), ACM, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. Kong, E. B., and Dietterich, T. G. Error-correcting output coding corrects bias and variance. In Proceedings of the Twelfth International Conference on Machine Learning, pages 313--321, 1995.Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. Matveeva, I., Burges, C., Burkard, T., Laucius, A., and Wong, L. High Accuracy Retrieval with Multiple Nested Ranker. In SIGIR 2006: Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, Seattle, Washington, USA. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Nallapati, R. Discriminative models for information retrieval. Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. Pang, B., and Lee, L. Seeing Stars: Exploiting Class Relationships for Sentiment Categorization with Respect to Rating Scales. ACL 2005 Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. Robertson, S. E. Overview of the okapi projects, Journal of Documentation, Vol. 53, No. 1, 1997, pp. 3--7.Google ScholarGoogle ScholarCross RefCross Ref
  29. Shashua, A., and Levin, A. Taxonomy of Large Margin Principle Algorithm for Ordinal Regression Problems. Advances in Neural Information Processing Systems 15. Cambridge, MA: MIT Press, 2000.Google ScholarGoogle Scholar
  30. Weston, J. and Watkins, C. Multi-class support vector machines. Technical Report CSD-TR-98-04, Department of Computer Science, Royal Holloway, University of London, Egham, TW20 0EX, UK, 1998.Google ScholarGoogle Scholar
  31. Xu, J., Cao, Y.B., Li, H., Zhao, M. Ranking definitions with supervised learning methods, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Ranking with multiple hyperplanes

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in
      • Published in

        cover image ACM Conferences
        SIGIR '07: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval
        July 2007
        946 pages
        ISBN:9781595935977
        DOI:10.1145/1277741

        Copyright © 2007 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 23 July 2007

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • Article

        Acceptance Rates

        Overall Acceptance Rate792of3,983submissions,20%

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader