SVM selective sampling for ranking with application to data retrieval

ABSTRACT

Learning ranking (or preference) functions has been a major issue in the machine learning community and has produced many applications in information retrieval. SVMs (Support Vector Machines) - a classification and regression methodology - have also shown excellent performance in learning ranking functions. They effectively learn ranking functions of high generalization based on the "large-margin" principle and also systematically support nonlinear ranking by the "kernel trick". In this paper, we propose an SVM selective sampling technique for learning ranking functions. SVM selective sampling (or active learning with SVM) has been studied in the context of classification. Such techniques reduce the labeling effort in learning classification functions by selecting only the most informative samples to be labeled. However, they are not extendable to learning ranking functions, as the labeled data in ranking is relative ordering, or partial orders of data. Our proposed sampling technique effectively learns an accurate SVM ranking function with fewer partial orders. We apply our sampling technique to the data retrieval application, which enables fuzzy search on relational databases by interacting with users for learning their preferences. Experimental results show a significant reduction of the labeling effort in inducing accurate ranking functions.

REFERENCES

• 1: Klaus Brinker, Active learning of label ranking functions, Proceedings of the twenty-first international conference on Machine learning, p.17, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015331]
• 2: Amelie Marian, Evaluating Top-k Queries over Web-Accessible Databases, Proceedings of the 18th International Conference on Data Engineering, p.369, February 26-March 01, 2002
• 3: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 4: Simon Tong , Edward Chang, Support vector machine active learning for image retrieval, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500159]
• 5: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 6: William W. Cohen , Robert E. Schapire , Yoram Singer, 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
• 7: J. Furnkranz and E. Hullermeier. Pairwise preference learning and ranking. In Proc. European Conf. Machine Learning (ECML'03), 2003.
• 8: S. Har-Peled, D. Roth, and D. Zimak. Constraint classification: A new approach to multiclass classification and ranking. In Proc. Advances in Neural Information Processing Systems (NIPS'02), 2002.
• 9: R. Herbrich, T. Graepel, and K. Obermayer, editors. Large margin rank boundaries for ordinal regression. MIT-Press, 2000.
• 10: Vagelis Hristidis , Nick Koudas , Yannis Papakonstantinou, PREFER: a system for the efficient execution of multi-parametric ranked queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.259-270, May 21-24, 2001, Santa Barbara, California, United States
• 11: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 12: Greg Schohn , David Cohn, Less is More: Active Learning with Support Vector Machines, Proceedings of the Seventeenth International Conference on Machine Learning, p.839-846, June 29-July 02, 2000
• 13: Simon Tong , Daphne Koller, Support Vector Machine Active Learning with Application sto Text Classification, Proceedings of the Seventeenth International Conference on Machine Learning, p.999-1006, June 29-July 02, 2000
• 14: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 15: Hwanjo Yu , Seung-won Hwang , Kevin Chen-Chuan Chang, RankFP: A Framework for Supporting Rank Formulation and Processing, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.514-515, April 05-08, 2005 [doi>10.1109/ICDE.2005.120]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.m MISCELLANEOUS

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms

Keywords:
active learning, ranking, selective sampling, support vector machine