Robust classification of rare queries using web knowledge

ABSTRACT

We propose a methodology for building a practical robust query classification system that can identify thousands of query classes with reasonable accuracy, while dealing in real-time with the query volume of a commercial web search engine. We use a blind 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 aggregation 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 , 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]
• 2: 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]
• 3: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 4: E. Efthimiadis and P. Biron. UCLA-Okapi at TREC-2: Query expansion experiments. In TREC-2, 1994.
• 5: E. Gabrilovich and S. Markovitch. Feature generation for text categorization using world knowledge. In IJCAI'05, pages 1048--1053, 2005.
• 6: 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]
• 7: 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
• 8: 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]
• 9: 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]
• 10: P. Kowalczyk, I. Zukerman, and M. Niemann. Analyzing the effect of query class on document retrieval performance. In Proc. Australian Conf. on AI, pages 550--561, 2004.
• 11: 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]
• 12: 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]
• 13: 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
• 14: S. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gatford. Okapi at TREC-3. In TREC-3, 1995.
• 15: G. Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 16: G. Salton and C. Buckley. Improving retrieval performance by relevance feedback. JASIS, 41(4):288--297, 1990.
• 17: T. Santner and D. Duffy. The Statistical Analysis of Discrete Data. Springer-Verlag, 1989.
• 18: 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]
• 19: 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]
• 20: 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]
• 21: 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]
• 22: 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
• 23: 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]

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
blind relevance feedback, query classification, web search