Classifying search queries using the Web as a source of knowledge

ABSTRACT

We propose a methodology for building a robust query classification system that can identify thousands of query classes, while dealing in real time with the query volume of a commercial Web search engine. We use a pseudo relevance feedback technique: given a query, we determine its topic by classifying the Web search results retrieved by the query. Motivated by the needs of search advertising, we primarily focus on rare queries, which are the hardest from the point of view of machine learning, yet in aggregate account for a considerable fraction of search engine traffic. Empirical evaluation confirms that our methodology yields a considerably higher classification accuracy than previously reported. We believe that the proposed methodology will lead to better matching of online ads to rare queries and overall to a better user experience.

REFERENCES

• 1: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , David Grossman , Ophir Frieder, Hourly analysis of a very large topically categorized web query log, 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.1009048]
• 2: Steven M. Beitzel , Eric C. Jensen , Ophir Frieder , David Grossman , David D. Lewis , Abdur Chowdhury , Aleksandr Kolcz, Automatic web query classification using labeled and unlabeled training data, 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.1076138]
• 3: Steven M. Beitzel , Eric C. Jensen , Ophir Frieder , David D. Lewis , Abdur Chowdhury , Aleksander Kolcz, Improving Automatic Query Classification via Semi-Supervised Learning, Proceedings of the Fifth IEEE International Conference on Data Mining, p.42-49, November 27-30, 2005 [doi>10.1109/ICDM.2005.80]
• 4: Steven M. Beitzel , Eric C. Jensen , David D. Lewis , Abdur Chowdhury , Ophir Frieder, Automatic classification of Web queries using very large unlabeled query logs, ACM Transactions on Information Systems (TOIS), v.25 n.2, p.9-es, April 2007 [doi>10.1145/1229179.1229183]
• 5: Andrei Z. Broder , Peter Ciccolo , Marcus Fontoura , Evgeniy Gabrilovich , Vanja Josifovski , Lance Riedel, Search advertising using web relevance feedback, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458217]
• 6: Andrei Broder , Peter Ciccolo , Evgeniy Gabrilovich , Vanja Josifovski , Donald Metzler , Lance Riedel , Jeffrey Yuan, Online expansion of rare queries for sponsored search, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain [doi>10.1145/1526709.1526778]
• 7: Andrei Z. Broder , Marcus Fontoura , Evgeniy Gabrilovich , Amruta Joshi , Vanja Josifovski , Tong Zhang, Robust classification of rare queries using web knowledge, 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.1277783]
• 8: Duda, R. and Hart, P. 1973. Pattern Classification and Scene Analysis. John Wiley and Sons, New York, NY.
• 9: Efthimiadis, E. and Biron, P. 1994. UCLA-Okapi at TREC-2: Query expansion experiments. In Proceedings of the Text REtrieval Conference (TREC-2). National Institute of Standards and Technology (NIST).
• 10: Evgeniy Gabrilovich , Shaul Markovitch, Harnessing the Expertise of 70,000 Human Editors: Knowledge-Based Feature Generation for Text Categorization, The Journal of Machine Learning Research, 8, p.2297-2345, 12/1/2007
• 11: Stephen C. Gates , Wilfried Teiken , Keh-Shin F. Cheng, Taxonomies by the numbers: building high-performance taxonomies, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099703]
• 12: Luis Gravano , Vasileios Hatzivassiloglou , Richard Lichtenstein, Categorizing web queries according to geographical locality, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956925]
• 13: Eui-Hong Han , George Karypis, Centroid-Based Document Classification: Analysis and Experimental Results, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.424-431, September 13-16, 2000
• 14: 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]
• 15: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 16: Zsolt T. Kardkovács , Domonkos Tikk , Zoltán Bánsághi, The Ferrety algorithm for the KDD Cup 2005 problem, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.111-116, December 2005 [doi>10.1145/1117454.1117468]
• 17: Kowalczyk, P., Zukerman, I., and Niemann, M. 2004. Analyzing the effect of query class on document retrieval performance. In Proceedings of the Australian Conference on Artificial Intelligence. Springer, 550--561.
• 18: Ying Li , Zijian Zheng , Honghua (Kathy) Dai, KDD CUP-2005 report: facing a great challenge, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.91-99, December 2005 [doi>10.1145/1117454.1117466]
• 19: Yumao Lu , Fuchun Peng , Xin Li , Nawaaz Ahmed, Coupling feature selection and machine learning methods for navigational query identification, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183711]
• 20: Christopher D. Manning , Prabhakar Raghavan , Hinrich Schtze, Introduction to Information Retrieval, Cambridge University Press, New York, NY, 2008
• 21: McCallum, A. and Nigam, K. 1998. A comparison of event models for naive Bayes text classification. In AAAI/ICML Workshop on Learning for Text Categorization. 41--48.
• 22: Mandar Mitra , Amit Singhal , Chris Buckley, Improving automatic query expansion, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.206-214, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290995]
• 23: Mike Moran , Bill Hunt, Search Engine Marketing, Inc.: Driving Search Traffic to Your Company's Web Site, Prentice Hall PTR, Upper Saddle River, NJ, 2005
• 24: Robertson, S., Walker, S., Jones, S., Hancock-Beaulieu, M., and Gatford, M. 1995. Okapi at TREC-3. In Proceedings of the Text REtrieval Conference (TREC-3). NIST, Gaithersburg, MD.
• 25: Rocchio, J. 1971. Relevance feedback in information retrieval. In The SMART Retrieval System: Experiments in Automatic Document Processing. Prentice Hall, Englewood Cliffs, NJ, 313--323.
• 26: Sahami, M., Mittal, V., Baluja, S., and Rowley, H. 2004. The happy searcher: Challenges in web information retrieval. In Proceedings of the 8th Pacific Rim International Conference on Artificial Intelligence. Springer-Verlag.
• 27: 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]
• 28: Salton, G. and Buckley, C. 1990. Improving retrieval performance by relevance feedback. J. Am. Soc. Inform. Sci. 41, 4, 288--297.
• 29: Santner, T. and Duffy, D. 1989. The Statistical Analysis of Discrete Data. Springer-Verlag.
• 30: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 31: Dou Shen , Rong Pan , Jian-Tao Sun , Jeffrey Junfeng Pan , Kangheng Wu , Jie Yin , Qiang Yang, Q²C@UST: our winning solution to query classification in KDDCUP 2005, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.100-110, December 2005 [doi>10.1145/1117454.1117467]
• 32: Dou Shen , Rong Pan , Jian-Tao Sun , Jeffrey Junfeng Pan , Kangheng Wu , Jie Yin , Qiang Yang, Query enrichment for web-query classification, ACM Transactions on Information Systems (TOIS), v.24 n.3, p.320-352, July 2006 [doi>10.1145/1165774.1165776]
• 33: Dou Shen , Jian-Tao Sun , Qiang Yang , Zheng Chen, Building bridges for web query classification, 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.1148196]
• 34: David Vogel , Steffen Bickel , Peter Haider , Rolf Schimpfky , Peter Siemen , Steve Bridges , Tobias Scheffer, Classifying search engine queries using the web as background knowledge, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.117-122, December 2005 [doi>10.1145/1117454.1117469]
• 35: Ellen M. Voorhees, Query expansion using lexical-semantic relations, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.61-69, July 03-06, 1994, Dublin, Ireland
• 36: Jinxi Xu , W. Bruce Croft, Improving the effectiveness of information retrieval with local context analysis, ACM Transactions on Information Systems (TOIS), v.18 n.1, p.79-112, Jan. 2000 [doi>10.1145/333135.333138]
• 37: Yiming Yang, An Evaluation of Statistical Approaches to Text Categorization, Information Retrieval, v.1 n.1-2, p.69-90, 1999 [doi>10.1023/A:1009982220290]
• 38: Tong Zhang , Frank J. Oles, Text Categorization Based on Regularized Linear Classification Methods, Information Retrieval, v.4 n.1, p.5-31, April 2001 [doi>10.1023/A:1011441423217]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation; Relevance feedback; Search process

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
Pseudo relevance feedback, Web search, query classification