Swarming to rank for information retrieval

ABSTRACT

This paper presents an approach to automatically optimize the retrieval quality of ranking functions. Taking a Swarm Intelligence perspective, we present a novel method, Swarm-Rank, which is well-founded in a Particle Swarm Optimization framework.

SwarmRank learns a ranking function by optimizing the combination of various types of evidences such content and hyperlink features, while directly maximizing Mean Average Precision, a widely used evaluation measure in Information Retrieval. Experimental results on well-established Learning To Rank benchmark datasets show that our approach significantly outperformed standard approaches (i.e., BM25) that only use basic statistical information derived from documents collections, and is found to be competitive with Ranking SVM and RankBoost in the task of ranking relevant documents at the very top positions.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: D. Bratton and J. Kennedy. Defining a standard for particle swarm optimization. Swarm Intelligence Symposium, 2007. SIS 2007. IEEE, 2007.
• 3: 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]
• 4: Zhe Cao , Tao Qin , Tie-Yan Liu , Ming-Feng Tsai , Hang Li, Learning to rank: from pairwise approach to listwise approach, Proceedings of the 24th international conference on Machine learning, p.129-136, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273513]
• 5: K. Crammer and Y. Singer. Pranking with ranking. In Advances in Neural Information Processing Systems 14, pages 641--647. MIT Press, 2002.
• 6: Humberto Mossri de Almeida , Marcos André Gonçalves , Marco Cristo , Pável Calado, A combined component approach for finding collection-adapted ranking functions based on genetic programming, 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.1277810]
• 7: R. Eberhart and J. Kennedy. A new optimizer using particle swarm theory. In Proceedings of the Sixth International Symposium on Micro Machine and Human Science, pages 39--43, Nagoya, Japan, 1995. Piscataway, NJ: IEEE Service Center.
• 8: Weiguo Fan , Michael D. Gordon , Praveen Pathak, Personalization of search engine services for effective retrieval and knowledge management, Proceedings of the twenty first international conference on Information systems, p.20-34, December 2000, Brisbane, Queensland, Australia
• 9: Weiguo Fan , Michael D. Gordon , Praveen Pathak, Discovery of Context-Specific Ranking Functions for Effective Information Retrieval Using Genetic Programming, IEEE Transactions on Knowledge and Data Engineering, v.16 n.4, p.523-527, April 2004 [doi>10.1109/TKDE.2004.1269663]
• 10: Weiguo Fan , Michael D. Gordon , Praveen Pathak, Genetic Programming-Based Discovery of Ranking Functions for Effective Web Search, Journal of Management Information Systems, v.21 n.4, p.37-56, Number 4/Spring 2005
• 11: 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
• 12: R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In A. Smola, P. Bartlett, B. Schölkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 115--132, Cambridge, MA, 2000. MIT Press.
• 13: 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]
• 14: 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]
• 15: J. Kennedy and R. Eberhart. Particle swarm optimization. In Proceedings of the 1995 IEEE International Conference on Neural Networks, volume 4, pages 1942--1948. IEEE Press, 1995.
• 16: 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]
• 17: T. Y. Liu, J. Xu, T. Qin, W. Xiong, and H. Li. LETOR: Benchmark dataset for research on learning to rank for information retrieval. In SIGIR '07: Proceedings of the Learning to Rank workshop in the 30th annual international ACM SIGIR conference on Research and development in information retrieval, 2007.
• 18: Lan Nie , Brian D. Davison , Xiaoguang Qi, Topical link analysis for web search, 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.1148189]
• 19: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, November 1999. Previous number = SIDL-WP-1999-0120.
• 20: R. Poli, J. Kennedy, and T. Blackwell. Particle swarm optimization. Swarm Intelligence, 1(1):33--57, 2007.
• 21: Tao Qin , Tie-Yan Liu , Xu-Dong Zhang , Zheng Chen , Wei-Ying Ma, A study of relevance propagation for web search, 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.1076105]
• 22: S. E. Robertson. Overview of the Okapi Projects. Journal of Documentation, 53(1):3--7, 1997.
• 23: A. Shakery and C. Zhai. Relevance propagation for topic distillation uiuc trec 2003 web track experiments. In TREC, pages 673--677, 2003.
• 24: M. Wetter. Generic Optimisation Program - GenOpt. User Manual, version 2.0.0. Technical report LBNL-54199. Lawrence Berkeley National Laboratory. http://gundog.lbl.gov/GO/, 2004.
• 25: Gui-Rong Xue , Qiang Yang , Hua-Jun Zeng , Yong Yu , Zheng Chen, Exploiting the hierarchical structure for link analysis, 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.1076068]
• 26: J.-Y. Yeh, J.-Y. Lin, H.-R. Ke, and W.-P. Yang. Learning to rank for information retrieval using genetic programming. In SIGIR 2007 Workshop on Learning to rank for information retrieval (LR4IR 2007), New York, NY, USA, 2007. ACM.
• 27: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to information retrieval, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.179-214, April 2004 [doi>10.1145/984321.984322]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Experimentation, Performance

Keywords:
learning to rank, particle swarm optimization, ranking function, swarm intelligence