Query enrichment for web-query classification

ABSTRACT

Web-search queries are typically short and ambiguous. To classify these queries into certain target categories is a difficult but important problem. In this article, we present a new technique called query enrichment, which takes a short query and maps it to intermediate objects. Based on the collected intermediate objects, the query is then mapped to target categories. To build the necessary mapping functions, we use an ensemble of search engines to produce an enrichment of the queries. Our technique was applied to the ACM Knowledge Discovery and Data Mining competition (ACM KDDCUP) in 2005, where we won the championship on all three evaluation metrics (precision, F1 measure, which combines precision and recall, and creativity, which is judged by the organizers) among a total of 33 teams worldwide. In this article, we show that, despite the difficulty of an abundance of ambiguous queries and lack of training data, our query-enrichment technique can solve the problem satisfactorily through a two-phase classification framework. We present a detailed description of our algorithm and experimental evaluation. Our best result for F1 and precision is 42.4% and 44.4%, respectively, which is 9.6% and 24.3% higher than those from the runner-ups, respectively.

REFERENCES

• 1: Ethem Alpaydin, Introduction to Machine Learning (Adaptive Computation and Machine Learning), The MIT Press, 2004
• 2: Eric Bauer , Ron Kohavi, An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants, Machine Learning, v.36 n.1-2, p.105-139, July-August 1999 [doi>10.1023/A:1007515423169]
• 3: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 4: 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]
• 5: Cann, A. J. 2003. Maths from Scratch for Biologists. John Wiley & Sons, New York, NY.
• 6: Rich Caruana , Alexandru Niculescu-Mizil , Geoff Crew , Alex Ksikes, Ensemble selection from libraries of models, Proceedings of the twenty-first international conference on Machine learning, p.18, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015432]
• 7: Chia-Hui Chang , Ching-Chi Hsu, Integrating query expansion and conceptual relevance feedback for personalized Web information retrieval, Proceedings of the seventh international conference on World Wide Web 7, p.621-623, April 1998, Brisbane, Australia
• 8: Chekuri, C., Goldwasser, M., Raghavan, P., and Upfal, E. 1997. Web search using automated classification. 6th International World Wide Web Conference (WWW6). Poster presentation.
• 9: Hao Chen , Susan Dumais, Bringing order to the Web: automatically categorizing search results, Proceedings of the SIGCHI conference on Human factors in computing systems, p.145-152, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332418]
• 10: Thomas G. Dietterich, Ensemble Methods in Machine Learning, Proceedings of the First International Workshop on Multiple Classifier Systems, p.1-15, June 21-23, 2000
• 11: Wei Fan , Salvatore J. Stolfo , Junxin Zhang, The application of AdaBoost for distributed, scalable and on-line learning, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.362-366, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312283]
• 12: L. K. Hansen , P. Salamon, Neural Network Ensembles, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.10, p.993-1001, October 1990 [doi>10.1109/34.58871]
• 13: HITEC. http://categorizer.tmit.bmr.hu.
• 14: Hoel, P. G. 1966. Elementary Statistics, 2nd ed. Wiley, New York, NY.
• 15: Howe, A. E. and Dreilinger, D. 1997. SAVVYSEARCH: A metasearch engine that learns which search engines to query. AI Mag. 18, 2, 19--25.
• 16: Jansen, B. J. 2000. The effect of query complexity on web searching results. Inf. Res. 6, 1.
• 17: 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
• 18: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 19: Jones, K. S. 1971. Automatic Keyword Classifications for Information Retrieval. Butterworth, London, UK.
• 20: In-Ho Kang , GilChang Kim, Query type classification for web document retrieval, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860449]
• 21: 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]
• 22: Josef Kittler , Mohamad Hatef , Robert P. W. Duin , Jiri Matas, On Combining Classifiers, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.3, p.226-239, March 1998 [doi>10.1109/34.667881]
• 23: David D. Lewis , William A. Gale, A sequential algorithm for training text classifiers, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.3-12, July 03-06, 1994, Dublin, Ireland
• 24: 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]
• 25: McCallum, A. and Nigam, K. 1998. A comparison of event models for naive Bayes text classification. In Proceedings of the AAAI-98 Workshop on Learning for Text Categorization.
• 26: Meyer, D. A. and Brown, T. A. 1998. Statistical mechanics of voting. Phys. Revei. Lett. 81, 8, 1718--1721.
• 27: Miller, G., Beckwith, R., Fellbaum, C., Gross, D., and Miller, K. 1990. Introduction to wordnet: An on-line lexical database. Int. J. Lexicography 3, 4, 23--244.
• 28: Page, L., Brin, S., Motwani, R., and Winograd, T. 1998. The pagerank citation ranking: Bringing order to the web. Tech. rep., Stanford Digital Library Technologies Project.
• 29: Selberg, E. and Etzioni, O. 1995. Multi-service search and comparison using the MetaCrawler. In Proceedings of the 4th International World-Wide web Conference. Darmstadt, Germany.
• 30: 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]
• 31: 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]
• 32: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 33: Tikk, D., Biró, Gy., and Yang, J. D. 2005. Experiments with a hierarchial text categorization method on WIPO patent collections. In Applied Research in Uncertainty Modelling and Analysis, N. O. Attok-Okine and B. M. Ayyub, Eds. International Series in Intelligent Technologies, vol. 20, Springer-Verlag, 283--302.
• 34: Van, R. C. 1979. Information Retrieval, 2nd ed. Butterworth, London, UK.
• 35: 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]
• 36: 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
• 37: Query clustering using user logs, ACM Transactions on Information Systems (TOIS), v.20 n.1, p.59-81, January 2002 [doi>10.1145/503104.503108]
• 38: 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]
• 39: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Keywords:
KDDCUP2005, Query classification, ensemble learning, query enrichment, synonym-based classifier