An axiomatic approach for result diversification
Publication (help) | |
---|---|
An axiomatic approach for result diversification | |
Authors: | Sreenivas Gollapudi, Aneesh Sharma [edit item] |
Citation: | WWW '09 Proceedings of the 18th international conference on World wide web : . 2009. |
Publication type: | Conference paper |
Peer-reviewed: | Yes |
Database(s): | |
DOI: | Define doi. |
Google Scholar cites: | Citations |
Link(s): | Paper link |
Added by Wikilit team: | Added on initial load |
Search | |
Article: | Google Scholar BASE PubMed |
Other scholarly wikis: | AcaWiki Brede Wiki WikiPapers |
Web search: | Bing Google Yahoo! — Google PDF |
Other: | |
Services | |
Format: | BibTeX |
Contents
[edit] Abstract
Understanding user intent is key to designing an effective ranking system in a search engine. In the absence of any explicit knowledge of user intent, search engines want to diversify results to improve user satisfaction. In such a setting, the probability ranking principle-based approach of presenting the most relevant results on top can be sub-optimal, and hence the search engine would like to trade-off relevance for diversity in the results. In analogy to prior work on ranking and clustering systems, we use the axiomatic approach to characterize and design diversification systems. We develop a set of natural axioms that a diversification system is expected to satisfy, and show that no diversification function can satisfy all the axioms simultaneously. We illustrate the use of the axiomatic framework by providing three example diversification objectives that satisfy different subsets of the axioms. We also uncover a rich link to the facility dispersion problem that results in algorithms for a number of diversification objectives. Finally, we propose an evaluation methodology to characterize the objectives and the underlying axioms. We conduct a large scale evaluation of our objectives based on two data sets: a data set derived from the Wikipedia disambiguation pages and a product database.
[edit] Research questions
"In this work, we initiate an axiomatic study of result diversification. We propose a set of simple properties that any diversification system ought to satisfy and these properties help serve as a basis for the space of objective functions for result diversi cation. Generally, a diversi cation function can be thought of as taking two application speci c inputs viz, a relevance function that speci es the relevance of document for a given query, and a distance function that captures the pairwise similarity between any pair of documents in the set of relevant results for a given query. In the context of web search, one can use the search engine's ranking function1 as the relevance function. The characterization of the distance function is not that clear. In fact, designing the right distance function is key for having e ective result diversification. For example, by restricting the distance function to be a metric by imposing the triangle inequality d(u;w) d(u; v)+d(v;w) for all u; v;w 2 U, we can exploit efficient approximation algorithms to solve certain class of diversification objectives (see Section 3)."
Research details
Topics: | Ranking and clustering systems [edit item] |
Domains: | Computer science [edit item] |
Theory type: | Design and action [edit item] |
Wikipedia coverage: | Sample data [edit item] |
Theories: | "Undetermined" [edit item] |
Research design: | Experiment, Mathematical modeling [edit item] |
Data source: | Experiment responses, Wikipedia pages [edit item] |
Collected data time dimension: | Cross-sectional [edit item] |
Unit of analysis: | Article [edit item] |
Wikipedia data extraction: | Live Wikipedia [edit item] |
Wikipedia page type: | Article [edit item] |
Wikipedia language: | Not specified [edit item] |
[edit] Conclusion
"This work presents an approach to characterizing diversication systems using a set of natural axioms and an empirical analysis that qualitatively compares the choice of axioms, relevance and distance functions using the well-known measures of novelty and relevance. The choice of axioms presents a clean way of characterizing objectives independent of the algorithms used for the objective, and the speci c forms of the distance and relevance functions. Speci cally, we illustrate the use of the axiomatic framework by studying three objectives satisfying di erent subsets of axioms. The empirical analysis on the other hand, while being dependent on these parameters, has the advantage of being able to quantify the trade-o s between novelty and relevance in the diversi cation objective. In this regard, we explore two applications of web search and product search, each with di erent notions of relevance and distance. In each application, we compare the performance of the three objectives by measuring the trade-o in novelty and relevance."
[edit] Comments
"Data source = Wikipedia disambiguation pages"