High accuracy retrieval with multiple nested ranker

ABSTRACT

High precision at the top ranks has become a new focus of research in information retrieval. This paper presents the multiple nested ranker approach that improves the accuracy at the top ranks by iteratively re-ranking the top scoring documents. At each iteration, this approach uses the RankNet learning algorithm to re-rank a subset of the results. This splits the problem into smaller and easier tasks and generates a new distribution of the results to be learned by the algorithm. We evaluate this approach using different settings on a data set labeled with several degrees of relevance. We use the normalized discounted cumulative gain (NDCG) to measure the performance because it depends not only on the position but also on the relevance score of the document in the ranked list. Our experiments show that making the learning algorithm concentrate on the top scoring results improves precision at the top ten documents in terms of the NDCG score.

REFERENCES

• 1: E. B. Baum and F. Wilczek. Supervised learning of probability distributions by neural networks. Neural Information Processing Systems, pages 52--61, 1987.
• 2: 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]
• 3: Yoav Freund, Boosting a weak learning algorithm by majority, Information and Computation, v.121 n.2, p.256-285, Sept. 1995 [doi>10.1006/inco.1995.1136]
• 4: 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
• 5: D. He and D. Demner-Fushman. HARD experiment at Maryland: From need negotiation to automated HARD process. In Proceedings of TREC, 2003.
• 6: X. He and P. Niyogi. Locality preserving projections. In Proceedings of NIPS, 2003.
• 7: A. James. HARD track overview in TREC 2003. In Proceedings of TREC, 2003.
• 8: A. James. HARD track overview in TREC 2004. In Proceedings of TREC, 2004.
• 9: B. J. Jansen and A. Spink. An analysis of web documents retrieved and viewed. In Proceedings of the International Conference on Internet Computing, pages 65--69, 2003.
• 10: B. J. Jansen, A. Spink, J. Bateman, and T. Saracevic. Real life information retrieval: A study of user queries on the web. In Proceedings of SIGIR, pages 5--17, 1998.
• 11: 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]
• 12: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Geri Gay, Accurately interpreting clickthrough data as implicit feedback, 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.1076063]
• 13: Yann LeCun , Léon Bottou , Genevieve B. Orr , Klaus-Robert Müller, Effiicient BackProp, Neural Networks: Tricks of the Trade, this book is an outgrowth of a 1996 NIPS workshop, p.9-50, January 1998
• 14: G. Levow and I. Matveeva. University of Chicago at CLEF2004: Cross-language text and spoken document retrieval. In Proceedings of CLEF, 2004.
• 15: Wei-Hao Lin , Rong Jin , Alexander Hauptmann, Web Image Retrieval Re-Ranking with Relevance Model, Proceedings of the IEEE/WIC International Conference on Web Intelligence, p.242, October 13-17, 2003
• 16: J. Ponte. Language models for relevance feedback. In W. Croft, editor, Advances in Information Retrieval, pages 73--96, 2000.
• 17: J. J. Roccio. Relevance feedback in information retrieval. In The SMART Retrieval System: Experiments in Automatic Document Processing, pages 313--323. Prentice Hall, 1971.
• 18: Chirag Shah , W. Bruce Croft, Evaluating high accuracy retrieval techniques, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1008996]
• 19: Libin Shen , Aravind K. Joshi, Ranking and Reranking with Perceptron, Machine Learning, v.60 n.1-3, p.73-96, September 2005 [doi>10.1007/s10994-005-0918-9]
• 20: Ellen M. Voorhees, Evaluation by highly relevant documents, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.74-82, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383963]
• 21: Y. Xiao, R. Luk, K. Wong, and K. Kwok. Some experiments with blind feedback and re-ranking for chinese information retrieval. In Proceedings NTCIR, 2005.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
ad-hoc retrieval, high accuracy retrieval, re-ranking