Fidelity, Soundness, and Efficiency of Interleaved Comparison Methods

By Katja Hofmann, Shimon Whiteson, Maarten de Rijke. 2013

55 citations recorded by the source corpus.

Ranker evaluation is central to the research into search engines, be it to compare rankers or to provide feedback for learning to rank. Traditional evaluation approaches do not scale well because they require explicit relevance judgments of document-query pairs, which are expensive to obtain. A promising alternative is the use of interleaved comparison methods, which compare rankers using click data obtained when interleaving their rankings. In this article, we propose a framework for analyzing interleaved comparison methods. An interleaved comparison method has fidelity if the expected outcome of ranker comparisons properly corresponds to the true relevance of the ranked documents. It is sound if its estimates of that expected outcome are unbiased and consistent. It is efficient if those estimates are accurate with only little data. We analyze existing interleaved comparison methods and find that, while sound, none meet our criteria for fidelity. We propose a probabilistic interleave method, which is sound and has fidelity. We show empirically that, by marginalizing out variables that are known, it is more efficient than existing interleaved comparison methods. Using importance sampling we derive a sound extension that is able to reuse historical data collected in previous comparisons of other ranker pairs.

Subfields: Information Systems, Statistical and Nonlinear Physics, Evaluation & Benchmarks

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Statistical and Nonlinear Physics

In Evaluation & Benchmarks

Citations in the corpus

Contextual Dueling Bandits (2015, methodology): “However, unlike the experiments in Zoghi et al. (2014a), we use an informational click model, rather than a perfect one Hofmann et al. (2013): the former simulates the behavior of a user who is seeking general information about a broad topic, while the former represents an idealized user, who…”
MergeRUCB: A Method for Large-Scale Online Ranker Evaluation (2015, methodology): “Finally, all experiments other than those in §6.4 used the navigational click model (cf. Table II of [15]) to simulate user click behavior.”
Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem (2015, methodology): “The valueµi,j is the probability that the rankeri beats rankerj based on the navigational click model (Hofmann et al., 2013).”
Copeland Dueling Bandits (2015, methodology): “The informational click model is one of the three click models utilized in the ranker evaluation literature, along with the perfect and navigational click models [37].”
Learning to Rank (2005, unknown): “• Close connection with online and logged based IR Evaluation [9, 14], because in both settings one needs to make the connection between observed user feedback and the hidden quality of the system.”
MergeDTS (2018, methodology): “These are standard setups in online ranker evaluation [4, 21, 24, 41, 54, 55].”
Relative confidence sampling for efficient on-line ranker evaluation (2014, methodology): “As explained in Section 5, we based our experiments on the perfect click model; in future experimental work we will conﬁrm our experimental ﬁndings with alternative click models [15].”
Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem (2013, unknown): “…in which one has a choice between applying a K -armed bandit al-gorithm to an unreliable quantity, such as Click Through Rate, or using a K -armed dueling bandit algorithm to conduct direct comparisons, which are known to be more reliable when dealing with humans (Hofmann et al., 2013b, §2.1).”