Learning to rank with partially-labeled data

ABSTRACT

Ranking algorithms, whose goal is to appropriately order a set of objects/documents, are an important component of information retrieval systems. Previous work on ranking algorithms has focused on cases where only labeled data is available for training (i.e. supervised learning). In this paper, we consider the question whether unlabeled (test) data can be exploited to improve ranking performance. We present a framework for transductive learning of ranking functions and show that the answer is affirmative. Our framework is based on generating better features from the test data (via KernelPCA) and incorporating such features via Boosting, thus learning different ranking functions adapted to the individual test queries. We evaluate this method on the LETOR (TREC, OHSUMED) dataset and demonstrate significant improvements.

REFERENCES

• 1: Shivani Agarwal, Ranking on graph data, Proceedings of the 23rd international conference on Machine learning, p.25-32, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143848]
• 2: Rie Kubota Ando , Tong Zhang, A Framework for Learning Predictive Structures from Multiple Tasks and Unlabeled Data, The Journal of Machine Learning Research, 6, p.1817-1853, 12/1/2005
• 3: S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira. Analysis of representations for domain adaptation. In Neural Information Processing Systems, 2006.
• 4: C. Burges, R. Ragno, and Q. Le. Learning to rank with nonsmooth cost functions. In NIPS, 2006.
• 5: Chris Burges , Tal Shaked , Erin Renshaw , Ari Lazier , Matt Deeds , Nicole Hamilton , Greg Hullender, Learning to rank using gradient descent, Proceedings of the 22nd international conference on Machine learning, p.89-96, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102363]
• 6: W. Chu and Z. Ghahramani. Extensions of gaussian processes for ranking: semi-supervised and active learning. In NIPS Wksp on Learning to Rank, 2005.
• 7: K. Crammer and Y. Singer. Pranking with ranking. In Neural Information Processing Systems (NIPS), 2001.
• 8: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 9: Xiubo Geng , Tie-Yan Liu , Tao Qin , Hang Li, Feature selection for ranking, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277811]
• 10: Jingrui He , Mingjing Li , Hong-Jiang Zhang , Hanghang Tong , Changshui Zhang, Manifold-ranking based image retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027531]
• 11: R. Herbrich, T. Graepel, and K. Obermayer. Advances in Large Margin Classifiers, chapter Large margin rank boundaries for ordinal regression. MIT Press, 2000.
• 12: Kalervo Järvelin , Jaana Kekäläinen, 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 [doi>10.1145/345508.345545]
• 13: 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]
• 14: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 15: Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
• 16: Joon Ho Lee, Analyses of multiple evidence combination, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.267-276, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 17: P. Li, C. Burges, and Q. Wu. McRank: Learning to rank using classification and gradient boosting. In NIPS, 2007.
• 18: T.-Y. Liu, T. Qin, J. Xu, W. Xiong, and H. Li. LETOR: Benchmark dataset for research on learning to rank for information retrieval. In SIGIR Workshop on Learning to Rank for IR (LR4IR), 2007.
• 19: L. Mason, J. Baxter, P. Bartless, and M. Frean. Boosting as gradient descent. In NIPS, 2000.
• 20: D. Metzler. Direct maximization of rank-based metrics. Technical report, University of Massachusetts, Amherst CIIR, 2005.
• 21: Rajat Raina , Alexis Battle , Honglak Lee , Benjamin Packer , Andrew Y. Ng, Self-taught learning: transfer learning from unlabeled data, Proceedings of the 24th international conference on Machine learning, p.759-766, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273592]
• 22: S. Robertson. Overview of the Okapi projects. Journal of Documentation, 53(1), 1997.
• 23: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901]
• 24: Bernhard Schölkopf , Alexander Smola , Klaus-Robert Müller, Nonlinear component analysis as a kernel eigenvalue problem, Neural Computation, v.10 n.5, p.1299-1319, July 1, 1998 [doi>10.1162/089976698300017467]
• 25: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 26: A. Smola, O. Mangasarian, and B. Schölkopf. Sparse kernel feature analysis. Technical Report 99-03, University of Wisconsin, Data Mining Institute, 1999.
• 27: T. Truong, M.-R. Amini, and P. Gallinari. Learning to rank with partially labeled training data. In Int'l Conf. on Multidisciplinary Info Sci/Tech, 2006.
• 28: Ming-Feng Tsai , Tie-Yan Liu , Tao Qin , Hsin-Hsi Chen , Wei-Ying Ma, FRank: a ranking method with fidelity loss, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277808]
• 29: J. Wang, M. Li, Z. Li, and W.-Y. Ma. Learning ranking function via relevance propagation. Technical report, Microsoft Research Asia, 2005.
• 30: J. Weston, R. Kuang, C. Leslie, and W. S. Noble. Protein ranking by semi-supervised network propagation. BMC Bioinformatics, 7, 2006.
• 31: Jinxi Xu , W. Bruce Croft, Query expansion using local and global document analysis, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.4-11, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243202]
• 32: Jun Xu , Hang Li, AdaRank: a boosting algorithm for information retrieval, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277809]
• 33: Yisong Yue , Thomas Finley , Filip Radlinski , Thorsten Joachims, A support vector method for optimizing average precision, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277790]
• 34: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to Ad Hoc information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.334-342, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384019]
• 35: Zhaohui Zheng , Keke Chen , Gordon Sun , Hongyuan Zha, A regression framework for learning ranking functions using relative relevance judgments, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277792]
• 36: D. Zhou, J. Weston, A. Gretton, O. Bousquet, and B. Schökopf. Ranking on data manifolds. In NIPS, 2004.
• 37: X. Zhu. Semi-supervised learning literature survey. Technical Report 1530, University of Wisconsin, Madison, Computer Science Dept., 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

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

General Terms:
Algorithms, Experimentation

Keywords:
boosting, information retrieval, kernel principal components analysis, learning to rank, transductive learning