Learning Noun Phrase Query Segmentation

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 819–826, Prague, June 2007. c⃝2007 Association for Computational Linguistics Learning Noun Phrase Query Segmentation Shane Bergsma and Qin Iris Wang Department of Computing Science University of Alberta Edmonton, Alberta, Canada, T6G 2E8 {bergsma,wqin}@cs.ualberta.ca Abstract Query segmentation is the process of tak- ing a user’s search-engine query and di- viding the tokens into individual phrases or semantic units. Identification of these query segments can potentially improve both document-retrieval precision, by first returning pages which contain the exact query segments, and document-retrieval re- call, by allowing query expansion or substi- tution via the segmented units. We train and evaluate a machine-learned query segmenta- tion system that achieves 86% segmentation- decision accuracy on a gold standard set of segmented noun phrase queries, well above recently published approaches. Key en- ablers of this high performance are features derived from previous natural language pro- cessing work in noun compound bracketing. For example, token association features be- yond simple N-gram counts provide power- ful indicators of segmentation. 1 Introduction Billions of times every day, people around the world communicate with Internet search engines via a small text box on a web page. The user provides a sequence of words to the search engine, and the search engine interprets the query and tries to return web pages that not only contain the query tokens, but that are also somehow about the topic or idea that the query terms describe. Recent years have seen a widespread recognition that the user is indeed providing natural language text to the search engine; query tokens are not inde- pendent, unordered symbols to be matched on a web document but rather ordered words and phrases with syntactic relationships. For example, Zhai (1997) pointed out that indexing on single-word symbols is not able to distinguish a search for “bank terminol- ogy” from one for “terminology bank.” The reader can submit these queries to a current search engine to confirm that modern indexing does recognize the effect of token order on query meaning in some way. Accurately interpreting query semantics also de- pends on establishing relationships between the query tokens. For example, consider the query “two man power saw.” There are a number of possible interpretations of this query, and these can be ex- pressed through a number of different segmentations or bracketings of the query terms: 1. [two man power saw] 2. [two man] [power saw] 3. [two] [man] [power saw] 4. [two] [man power] [saw], etc. One simple way to make use of these interpretations in search would be to put quotation marks around the phrasal segments to require the search engine to only find pages with exact phrase matches. If, as seems likely, the searcher is seeking pages about the large, mechanically-powered two-man saws used by lum- berjacks and sawyers to cut big trees, then the first segmentation is correct. Indeed, a phrasal search for “two man power saw” on Google does …

Content truncated to 500 words