Ranking refinement and its application to information retrieval

ABSTRACT

We consider the problem of ranking refinement, i.e., to improve the accuracy of an existing ranking function with a small set of labeled instances. We are, particularly, interested in learning a better ranking function using two complementary sources of information, ranking information given by the existing ranking function (i.e., a base ranker) and that obtained from users' feedbacks. This problem is very important in information retrieval where the feedback is gradually collected. The key challenge in combining the two sources of information arises from the fact that the ranking information presented by the base ranker tends to be imperfect and the ranking information obtained from users' feedbacks tends to be noisy. We present a novel boosting framework for ranking refinement that can effectively leverage the uses of the two sources of information. Our empirical study shows that the proposed algorithm is effective for ranking refinement, and furthermore significantly outperforms the baseline algorithms that incorporate the outputs from the base ranker as an additional feature.

REFERENCES

• 1: S. Robertson and D. A. Hull. The trec-9 filtering track final report. In TREC9, pages 25--40, 2000.
• 2: John Lafferty , Chengxiang Zhai, Document language models, query models, and risk minimization for information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.111-119, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383970]
• 3: David M. Pennock , Eric Horvitz , Steve Lawrence , C. Lee Giles, Collaborative Filtering by Personality Diagnosis: A Hybrid Memory and Model-Based Approach, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.473-480, June 30-July 03, 2000
• 4: R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers, pages 115--132, 2000.
• 5: 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]
• 6: 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
• 7: 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]
• 8: Jianfeng Gao , Haoliang Qi , Xinsong Xia , Jian-Yun Nie, Linear discriminant model for information retrieval, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076085]
• 9: Yunbo Cao , Jun Xu , Tie-Yan Liu , Hang Li , Yalou Huang , Hsiao-Wuen Hon, Adapting ranking SVM to document retrieval, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148205]
• 10: 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]
• 11: A. Shashua and A. Levin. Ranking with large margin principle: Two approaches. In NIPS, 2003.
• 12: W. Chu and Z. Ghahramani. Gaussian processes for ordinal regression. Technical report, 2004.
• 13: Donna Harman, Relevance feedback revisited, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.1-10, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133167]
• 14: Mark Montague , Javed A. Aslam, Condorcet fusion for improved retrieval, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584881]
• 15: R. T. Rockafellar. Convex analysis. Princeton University Press, Princeton, N.J., 1970.
• 16: R. E. Steuer. Multiple Criteria Optimization: Theory, Computation and Application. John Wiley, 546 pp, 1986.
• 17: Robert E. Schapire, Theoretical Views of Boosting and Applications, Proceedings of the 10th International Conference on Algorithmic Learning Theory, p.13-25, December 06-08, 1999
• 18: 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 ]
• 19: GroupLens. MovieLens Data sets. http://www.grouplens.org/node/12, 2006.
• 20: Microsoft Research Asia. LETOR: Benchmark Datasets for Learning to Rank. http://research.microsoft.com/users/tyliu/letor/, 2006.
• 21: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Design, Experimentation, Theory

Keywords:
background information, boosting, incremental learning, learning to rank