Unsupervised query segmentation using generative language models and wikipedia

ABSTRACT

In this paper, we propose a novel unsupervised approach to query segmentation, an important task in Web search. We use a generative query model to recover a query's underlying concepts that compose its original segmented form. The model's parameters are estimated using an expectation-maximization (EM) algorithm, optimizing the minimum description length objective function on a partial corpus that is specific to the query. To augment this unsupervised learning, we incorporate evidence from Wikipedia.

Experiments show that our approach dramatically improves performance over the traditional approach that is based on mutual information, and produces comparable results with a supervised method. In particular, the basic generative language model contributes a 7.4% improvement over the mutual information based method (measured by segment F1 on the Intersection test set). EM optimization further improves the performance by 14.3%. Additional knowledge from Wikipedia provides another improvement of 24.3%, adding up to a total of 46% improvement (from 0.530 to 0.774).

REFERENCES

• 1: Rie Kubota Ando , Lillian Lee, Mostly-unsupervised statistical segmentation of Japanese Kanji sequences, Natural Language Engineering, v.9 n.2, p.127-149, June 2003 [doi>10.1017/S1351324902002954]
• 2: Peter G. Anick , Shivakumar Vaithyanathan, Exploiting clustering and phrases for context-based information retrieval, ACM SIGIR Forum, v.31 n.SI, p.314-323
• 3: A. T. Arampatzis , T. Tsoris , C. H. A. Koster , Th. P. Van Der Weide, Phase-based information retrieval, Information Processing and Management: an International Journal, v.34 n.6, p.693-707, Nov. 1998 [doi>10.1016/S0306-4573(98)00030-2]
• 4: S. Bergsma and Q. I. Wang. Learning Noun Phrase Query Segmentation. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 819--826, 2007.
• 5: M. R. Brent and T. A. Cartwright. Distributional regularity and phonotactic constraints are useful for segmentation. Cognition, 61:93--125, 1996.
• 6: Eric Brill , Grace Ngai, Man vs. machine: a case study in base noun phrase learning, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.65-72, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034698]
• 7: R. Bunescu and M. Pasca. Using Encyclopedic Knowledge for Named Entity Disambiguation. In Proceedings of 11th Conference of European Chapter of the Association for Computational Linguistics (EACL), pages 9--16, 2006.
• 8: Youjin Chang , Iadh Ounis , Minkoo Kim, Query reformulation using automatically generated query concepts from a document space, Information Processing and Management: an International Journal, v.42 n.2, p.453-468, March 2006 [doi>10.1016/j.ipm.2005.03.025]
• 9: S. Cucerzan. Large-Scale Named Entity Disambiguation Based on Wikipedia Data. In Proceedings of EMNLP-CoNLL 2007, pages 708--716, 2007.
• 10: D. Ahn and V. Jijkoun and G. Mishne and K. Muller and M. de. Rijke. Using Wikipedia at the TREC QA Track. In The Thirteenth Text Retrieval Conference (TREC 2004), 2005.
• 11: David A. Evans , Chengxiang Zhai, Noun-phrase analysis in unrestricted text for information retrieval, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.17-24, June 24-27, 1996, Santa Cruz, California [doi>10.3115/981863.981866]
• 12: E. Gabrilovich and S. Markovitch. Overcoming the Brittleness Bottleneck using Wikipedia: Enhancing Text Categorization with Encyclopedic Knowledge. In Proceedings of the Twenty-First National Conference on Artificial Intelligence (AAAI), pages 1301--1306, 2006.
• 13: Peter Grünwald, A minimum description length approach to grammar inference, Connectionist, Statistical, and Symbolic Approaches to Learning for Natural Language Processing, p.203-216, January 1996
• 14: Rosie Jones , Benjamin Rey , Omid Madani , Wiley Greiner, Generating query substitutions, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135835]
• 15: Hang Li , Naoki Abe, Clustering words with the MDL principle, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark [doi>10.3115/992628.992633]
• 16: Carl G. De Marcken , Robert C. Berwick, Unsupervised language acquisition, Massachusetts Institute of Technology, 1996
• 17: Greg Pass , Abdur Chowdhury , Cayley Torgeson, A picture of search, Proceedings of the 1st international conference on Scalable information systems, p.1-es, May 30-June 01, 2006, Hong Kong [doi>10.1145/1146847.1146848]
• 18: Fuchun Peng , Fangfang Feng , Andrew McCallum, Chinese segmentation and new word detection using conditional random fields, Proceedings of the 20th international conference on Computational Linguistics, p.562-es, August 23-27, 2004, Geneva, Switzerland [doi>10.3115/1220355.1220436]
• 19: Fuchun Peng , Dale Schuurmans, Self-Supervised Chinese Word Segmentation, Proceedings of the 4th International Conference on Advances in Intelligent Data Analysis, p.238-247, September 13-15, 2001
• 20: Simone Paolo Ponzetto , Michael Strube, Exploiting semantic role labeling, WordNet and Wikipedia for coreference resolution, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.192-199, June 04-09, 2006, New York, New York [doi>10.3115/1220835.1220860]
• 21: Yonggang Qiu , Hans-Peter Frei, Concept based query expansion, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.160-169, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160713]
• 22: L. Ramshaw and M. Marcus. Text Chunking Using Transformation-Based Learning. In Proceedings of the Third Workshop on Very Large Corpora, pages 82--94, 1995.
• 23: K. M. Risvik, T. Mikolajewski, and P. Boros. Query Segmentation for Web Search. In The Twelfth International World Wide Web Conference (WWW), 2003.
• 24: J. I. Serrano and L. Araujo. Statistical Recognition of Noun Phrases in Unrestricted Text. In IDA ?05: Proceedings of the 6th International Conference on Advances in Intelligent Data Analysis, pages 397--408, 2005.
• 25: Richard Sproat , William Gale , Chilin Shih , Nancy Chang, A stochastic finite-state word-segmentation algorithm for Chinese, Computational Linguistics, v.22 n.3, p.377-404, September 1996
• 26: Chengxiang Zhai, Fast statistical parsing of noun phrases for document indexing, Proceedings of the fifth conference on Applied natural language processing, p.312-319, March 31-April 03, 1997, Washington, DC [doi>10.3115/974557.974603]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
concept discovery, query segmentation