Applying Diversity Metrics to Improve the Selection of WebSearch Term RefinementsTague [email protected] [email protected] expansion of user queries during web search is atechnique provided by most web search engines. Term ex-pansion helps users to phrase more specific queries, correctmisspellings, and acts as an accelerator for frequently usedqueries. Typically search engines provide five to ten refine-ments. Many of the refinement sets have a high degree ofredundancy which suggests that popularity is the primaryfactor for selecting a refinement. This is particularly evi-dent in terms that have multiple semantic meanings one ofwhich is association with technology. The popularity of thetechnological usage of the word with dwarf the other us-ages, monopolizing the set of refinements. We explore twoapproaches to apply a measure of diversity in the selectionof refinements: using word sense similarity and web seman-tic similarity. We analyze some of the problems with usingdiversity as the sole metric for refinement selection and eval-uate the results of our technique through a human editorialtest.1. INTRODUCTIONSearch term refinements are suggestions offered to a userby a search engine to help formulate a more specific query.As an example, if you search for java on Yahoo! the searchengine will suggest java downloads, java games, mobile javageneral, free java download, and java runtime environmentas follow on queries to find the data you are interested in.(You can also see this feature by typing a search term intothe Firefox search box for most of the major search engines.)All of the major search engines implement some form of termrefinement.If we look at the Google Suggest refinements for the termAmazon in Table 1, we notice that all of the potential queryrefinements are related to the company Amazon. The resultsare tightly clustered around a single concept despite the factthat Amazon river has 4,000,000 results1- over 5 times asmany as Amazon Kindle.This is a pattern we see repeated over and over to vary-ing degrees in all web search engines. The refinements forterms with several distinct clusters, particularly when oneof those senses is technology related, are skewed toward asingle senses cluster.For many applications it makes sense to drive the refine-ment terms using a model of query popularity, but as we seein features like spelling correction, popularity is not always1This data was taken from Google ([8], [9]) via the web APIon May 31, 2008.the best metric for every application. If you are interestedin presenting an exploratory interface to the web, a differenttechnique for selecting search term refinements - one thatchooses a diverse sense of meaning, might make a betterchoice.Diversity can be a difficult concept to apply across a largepopulation. Continuing on with our Amazon example, Ama-zon river makes sense as a refinement with broad applicabil-ity to wide class of the population but using Amazon Womenin the Mood as a refinement2would only be applicable tousers interested in the television series Futurama. AmazonWomen in the Mood would certainly increase the diversityof the refinement set, but since only a small number of re-finements can be displayed to the end user, is it widely ap-plicable enough to warrant displaying it.Looking at some sample suggestions, one immediately no-tices that some of the redundancy could have been easilyidentified by simple lexical means: stemming, stop wordsremoval, spelling corrections, but much of the conceptualredundancy requires deeper analysis.In this paper we propose a mechanism for selecting searchterm refinements based on a linear combination of a diveristyand popularity score. We compare the performance of twodifferent metrics of diversity, one semantic and one informa-tion retrieval, to see their overall performance.2. RELATED WORKIn the field of Information Retrieval, many different tech-niques for automatic query expansion have been investi-gated. One of the classic techniques for query expansion is2Google lists 209,000 results for this query and actually sug-gests it as one of the possible refinements for the searchAmazon Women.Suggestion Result Pagesamazon uk 13,100,000amazon kindle 783,000amazon mp3 12,500,000amazon.fr 62,800,000amazon s3 483,000amazon unbox 5,860,000amazon.ca 64,000,000amazon music 14,600,000amazon.de 103,000,000amazon .com 355,000,000Table 1: Google Suggestions for Amazonrelevance feedback, adding terms from known relevant docu-ments to a user’s query. This technique is used in the TRECwith query term weighting to improve the effective of usersqueries. Experiments with the TREC system show linearimprovements in precision up to about 300 terms. [4].Another classic expansion method, thesaurus lookup, ex-pands a users query with synonyms from a pre-computedthesaurus . This technique, particularly if performed naively,can perform quite poorly. For example if, a query for riverbank is expanded with financial terms, the results will bevery poor.Modern search engines all provide some form of queryexpansion. While the exact implementations of these al-gorithms are proprietary, examining the results3makes itclear that a combination of query popularity and spellingcorrection is used to determine which refinements to sug-gest.The difference between our work and previous work is thatthe goal of these techniques is to increase precision. Ourgoal is to increase recall by eliminating redundancy in theautomatic expansion terms.3. DATA SETOur experimental data was derived from a random selec-tion of popular terms in one month of Yahoo! query logs.4The popular terms were then intersected with semanticallyclustered data from the Wikipedia corpus provided to us byPatrick Pantel ([15]).We randomly selected 100 terms from this set that hadat least two semantic meanings within the Wikipedia cor-pus. In the interest of civility, we manually filtered theseterms for expletives and adult content. After filtering, wewere left with a corpus of 64 words for analysis. For eachof these terms we found approximately 1,000 popular refine-ments (where the term was the first word in a query string)from the Yahoo! search logs.Our term set includes words like java (programming lan-guage/language, island) and amazon (source/website, river)that have a technology and non-technology meaning. Italso includes the names of famous individuals jennifer lopez(artist, george clooney/brad pitt/ben affleck), madonna
View Full Document
Unlocking...