Probabilistic Interleaving

Probabilistic interleaving compares two rankers by building the blended list from probability distributions derived from each ranking rather than from the fixed lists. Hofmann et al. (2011) propose it as a method that is both unbiased and sensitive to differences between rankings, after finding that earlier methods were either biased or insensitive to some differences.

Softmax distributions over rankings

For each ranker, a softmax function gives every document a nonzero probability of being selected, with higher-ranked documents more likely. The probability of selecting document d from ranker x’s list depends on its rank \(r_x(d)\): \(P_x(d) = r_x(d)^{-\tau} / \sum_{d’} r_{x}(d’)^{-\tau}\). The parameter \(\tau\) controls how quickly the probability falls as rank worsens. The authors used \(\tau = 3\) in their experiments.

The blended list is generated similarly to team draft interleaving. Instead of randomizing which ranker picks first in each pair of positions, the method selects one of the two softmax functions at random at each position and draws a document without replacement from it. After selection, remove that document from both distributions and renormalize the probabilities over the remaining documents before the next position. Because every document has a nonzero probability under both distributions, every ordering of the documents is possible.

A worked example

This example was constructed for this entry. With \(\tau = 3\) and four documents, the selection probabilities by rank are 0.849, 0.106, 0.031, and 0.013. Let the first ranker return (a, b, c, d) and the second return (b, c, d, a). The probability that the first position holds each document is the average of its probabilities under the two rankings:

A document that one ranker places first and the other places last (a) keeps a substantial probability of appearing at the top, while a document that both rankers place low (d) rarely does. Rankers that put a document at similar ranks give it similar probabilities, so they receive similar credit in expectation, and the difference in expected credit reflects how different the rankings are.

Estimating the outcome

Each impression records which ranker’s distribution produced each document. Averaging the per-impression outcomes gives an unbiased estimate of the comparison. The authors also derive a second unbiased estimator that marginalizes over all assignments consistent with the observed list, weighting them by their probability by Bayes’ rule, which is more reliable than using only the observed assignments. They note that assignments need to be computed only up to the lowest observed click.

In their simulation experiments, which used simulated clicks and not real users, the marginalized estimator identified the better ranker for 91.4% of the ranker pairs, against 89.8% for team draft and 88.1% for balanced interleaving. Those figures depend on their simulation setup and ranker pairs.

Costs

• The blended list is sampled, so some impressions will place documents higher or lower than either ranker would, which can affect what users see.
• The assignment probabilities must be recorded or recomputable to apply the estimators.
• The decay parameter is a design choice.

See Team Draft Interleaving, Balanced Interleaving, and Interleaving Tests for the methods it builds on.

References:

• Hofmann, Whiteson, and de Rijke, A Probabilistic Method for Inferring Preferences from Clicks (CIKM 2011)