]>
2020-11-28T02:36:23+00:00
An axiomatic approach for result diversification
0
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.
Added on initial load
Cross-sectional
Data source = Wikipedia disambiguation pages
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.
Experiment responses
Wikipedia pages
Yes
Conference paper
Experiment
Mathematical modeling
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).
11128
Undetermined
Design and action
An axiomatic approach for result diversification
Article
Sample data
Live Wikipedia
Not specified
Article
2009Z
2454832.5
2012-03-15T20:02:46Z
2456002.33525
2014-01-30T20:53:47Z
2456688.37068
An axiomatic approach for result diversification