A combined component approach for finding collection-adapted ranking functions based on genetic programming

ABSTRACT

In this paper, we propose a new method to discover collection-adapted ranking functions based on Genetic Programming (GP). Our Combined Component Approach (CCA)is based on the combination of several term-weighting components (i.e.,term frequency, collection frequency, normalization) extracted from well-known ranking functions. In contrast to related work, the GP terminals in our CCA are not based on simple statistical information of a document collection, but on meaningful, effective, and proven components. Experimental results show that our approach was able to outper form standard TF-IDF, BM25 and another GP-based approach in two different collections. CCA obtained improvements in mean average precision up to 40.87% for the TREC-8 collection, and 24.85% for the WBR99 collection (a large Brazilian Web collection), over the baseline functions. The CCA evolution process also was able to reduce the overtraining, commonly found in machine learning methods, especially genetic programming, and to converge faster than the other GP-based approach used for comparison.

REFERENCES

• 1: J. Allan, J. P. Callan, F. Feng, and D. Malin. INQUERY and TREC-8. In Proceedings of TREC-8, pages 637--644, Gaithersburg, MD, 1999. NIST Special Publication 500-246.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Brian T. Bartell , Garrison W. Cottrell , Richard K. Belew, Automatic combination of multiple ranked retrieval systems, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.173-181, July 03-06, 1994, Dublin, Ireland
• 4: C. Buckley, A. Singhal, and M. Mitra. New retrieval approaches using smart: TREC 4. In Proceedings of TREC-4, pages 25--48, Gaithersburg, MD, 1996. NIST Special Publication 500-236.
• 5: Weiguo Fan , Edward A. Fox , Praveen Pathak , Harris Wu, The effects of fitness functions on genetic programming-based ranking discovery for Web search: Research Articles, Journal of the American Society for Information Science and Technology, v.55 n.7, p.628-636, May 2004 [doi>10.1002/asi.v55:7]
• 6: Weiguo Fan , Michael Gordon , Praveen Pathak, On linear mixture of expert approaches to information retrieval, Decision Support Systems, v.42 n.2, p.975-987, November 2006 [doi>10.1016/j.dss.2004.11.014]
• 7: 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
• 8: 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]
• 9: Weiguo Fan , Michael D. Gordon , Praveen Pathak, A generic ranking function discovery framework by genetic programming for information retrieval, Information Processing and Management: an International Journal, v.40 n.4, p.587-602, May 2004 [doi>10.1016/j.ipm.2003.08.001]
• 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: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 12: Anísio Lacerda , Marco Cristo , Marcos André Gonçalves , Weiguo Fan , Nivio Ziviani , Berthier Ribeiro-Neto, Learning to advertise, 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.1148265]
• 13: Nir Oren, Reexamining tf.idf based information retrieval with genetic programming, Proceedings of the 2002 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technology, September 16-18, 2002, Port Elizabeth, South Africa
• 14: P. Pathak, M. Gordon, and W. Fan. Effective information retrieval using genetic algorithms based matching functions adaptation. In Proceedings of the 33rd HICSS, Hawaii, 2000.
• 15: Bruno Pôssas , Nivio Ziviani , Wagner Meira, Jr. , Berthier Ribeiro-Neto, Set-based vector model: An efficient approach for correlation-based ranking, ACM Transactions on Information Systems (TOIS), v.23 n.4, p.397-429, October 2005 [doi>10.1145/1095872.1095874]
• 16: S. E. Robertson and K. S. Jones. Relevance weighting of search terms. Journal of the American Society for Information Science, 27(3):129--146, 1976.
• 17: S. E. Robertson and S. Walker. Okapi/keenbow at TREC-8. In Proceedings of TREC-8, pages 151--162, Gaithersburg, MD, 1999. NIST Special Publication 500-246.
• 18: S. E. Robertson, S. Walker, S. Jones, M. M. Hancock-Beaulieu, and M. Gatford. Okapi at TREC-3. In Proceedings of TREC-3, pages 109--126, Gaithersburg, MD, 1995. NIST Special Publication 500-226.
• 19: G. Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 20: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 21: Amit Singhal , Chris Buckley , Mandar Mitra, Pivoted document length normalization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-29, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243206]
• 22: Andrew Trotman, Learning to Rank, Information Retrieval, v.8 n.3, p.359-381, May 2005 [doi>10.1007/s10791-005-6991-7]
• 23: Christopher C. Vogt , Garrison W. Cottrell, Fusion Via a Linear Combination of Scores, Information Retrieval, v.1 n.3, p.151-173, October 1999 [doi>10.1023/A:1009980820262]
• 24: E. M. Voorhees and D. Harman. Overview of the eighth Text REtrieval Conference (TREC-8). In Proceedings of TREC-8, pages 1--24, Gaithersburg, MD, 1999. NIST Spec.Publ. 500-246.
• 25: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 26: Justin Zobel , Alistair Moffat, Exploring the similarity space, ACM SIGIR Forum, v.32 n.1, p.18-34, Spring 1998 [doi>10.1145/281250.281256]

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
genetic programming, information retrieval, machine learning, ranking functions, term-weighting