Inducing Word Senses to Improve Web Search Result Clustering

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 116–126, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Inducing Word Senses to Improve Web Search Result Clustering Roberto Navigli and Giuseppe Crisafulli Dipartimento di Informatica Sapienza Universit`a di Roma navigli@di.uniroma1.it, crisafulli.giu@gmail.com Abstract In this paper, we present a novel approach to Web search result clustering based on the au- tomatic discovery of word senses from raw text, a task referred to as Word Sense Induc- tion (WSI). We first acquire the senses (i.e., meanings) of a query by means of a graph- based clustering algorithm that exploits cycles (triangles and squares) in the co-occurrence graph of the query. Then we cluster the search results based on their semantic similarity to the induced word senses. Our experiments, conducted on datasets of ambiguous queries, show that our approach improves search result clustering in terms of both clustering quality and degree of diversification. 1 Introduction Over recent years increasingly huge amounts of text have been made available on the Web. Popular search engines such as Yahoo! and Google usually do a good job at retrieving a small number of rel- evant results from such an enormous collection of Web pages (i.e. retrieving with high precision, low recall). However, current search engines are still fac- ing the lexical ambiguity issue (Furnas et al., 1987) – i.e. the linguistic property owing to which any particular word may convey different meanings. In a recent study (Sanderson, 2008) – conducted us- ing WordNet (Miller et al., 1990) and Wikipedia as sources of ambiguous words – it was reported that around 3% of Web queries and 23% of the most frequent queries are ambiguous. Examples include: “buy B-52” (a cocktail? a bomber? a DJ worksta- tion? tickets for a band?), “Alexander Smith quotes” (the novelist? the poet?), “beagle search” (dogs? the Linux search tool? the landing spacecraft?). Ambiguity is often the consequence of the low number of query words entered on average by Web users (Kamvar and Baluja, 2006). While average query length is increasing – it is now estimated at around 3 words per query1 – many search engines such as Google have already started to tackle the query ambiguity issue by reranking and diversify- ing their results, so as to prevent Web pages that are similar to each other from ranking too high on the list. In the past few years, Web clustering engines (Carpineto et al., 2009) have been proposed as a solution to the lexical ambiguity issue in Web In- formation Retrieval. These systems group search re- sults, by providing a cluster for each specific aspect (i.e., meaning) of the input query. Users can then se- lect the cluster(s) and the pages therein that best an- swer their information needs. However, many Web clustering engines group search results on the ba- sis of their lexical similarity. For instance, consider the following snippets returned for the beagle search query: 1. Beagle is a search tool that ransacks your... …

Content truncated to 500 words