IR Guest Lecture by Harrie Oosterhuis on Ranking Systems

  • We have a user query (can also be information about the user)
  • Collection of objects, called "documents" for simplification
  • Output: ranking of documents

One of the main points: noise in the feedback signal from clickthrough data is not the main problem, bias is.

Supervised: Annotated Datasets

Learning to rank is a core task in information retrieval

Different from regression where we want scores to match labels; we only care about the ordering according to ranking function f.

Traditionally, ranking is supervised through annotated datasets. This uses relevance annotations for query-document pairs provided by human judges.

Limitations of annotated datasets

There are several problems:

  • Expensive
  • There are also unethical cases in privacy-sensitive settings
    • we can't show all date to experts
    • we do not simply want our search history and corresponding results to be shown to third parties
    • annotations are also not useful for searching through email, for the same reason
  • Impossible for small scale problems (e.g. we can't annotate taking into account someone's personal preferences since we do not know that person)
  • Stationary: cannot capture future changes in relevancy
    • But redoing all the work is too expensive
  • Expert opinions do not necessarily match actual user preferences

See slide 9 for references.

As a result of these limitations:

  • Unavailable for those without a big budget
  • Impossible for certain ranking problems
  • Often misaligned with true user preferences

So we also need an alternative learning approach to learning ranking.

Learning from user interactions

  • Once you have users, interactions are practically free
  • User behavior is indicative of their preferences
  • But interactions are implicit feedback

Noise:

  • Users click for various reasons, not only because they prefer
  • Clicks do often not occur because of relevancy
    • E.g. if they automatically click on the first ranking without assessing its relevancy
  • Also clicks sometimes do not occur despite something being relevant

But noise is not the biggest problem.

Individual clicks are very noisy, but we have many of them which alleviates this problem.

Main problem: bias

The real problem is bias: interactions affected by factors other than relevancy

  • Position bias: higher ranked documents are treated different by users due to their higher ranking, not necessarily because they are more relevant
    • Eye-tracking studies show a "golden triangle" of attention in the top left corner of Google results.
    • All participants looked at position 1 or 2
    • Due to this effect you can't trust clicks to correspond to relevance; if the most relevant result is on rank 6, most people will still click on 1 or 2, but only half of the people will not even have looked at rank 6 (of course they cannot click there then as well)
  • Item selection bias: interactions are limited to the presented documents
  • Presentation bias: Results that are presented differently will be treated differently
    • E.g. the huge trailer on the Netflix homepage is more likely to be clicked on, just because it's so big

Q: Explain different forms of bias that play a role in clickthrough data.

Q: What's the golden triangle in presentation bias?

Unbiased learning to rank: two approaches

The goal of unbiased learning to rank:

  • Optimize ranker w.r.t. relevance preferences of users from their interactions
  • Avoid being biased by other factors that influence these interactions (i.e. that are not about relevancy)

We can do this online:

  • Learning by directly interacting with users
  • Handles biases by randomization of displayed results

We can do counterfactual learning to rank:

  • Learning from historical interactions
  • Use a model of user behavior to correct for biases

We will focus on the latter.

Q: What are the two main approach to unbiased learning to rank?

Q: How do you deal with bias in an online approach to learning to rank?

Counterfactual Evaluation

TLDR; how to evaluate your system before deploying it and without annotated data?

We first nail the evaluation, because learning follows quite naturally from it.

Usually we want to evaluate our system before deploying it. But if we rely on user interaction instead of annotation, how do we do this? Can we evaluate a ranker without deploying it or using annotated data?

Solution: use counterfactual evaluation using historical interaction data (such as clicks) that were based on a previously deployed ranking function $f_{deploy}$.

If we know the true relevance labels we can compute any linearly decomposable IR metric using a machine learning approach (meaning we'll have a weight per rank) See slide 17. Uses a formula with $\lambda$; the point is that lambda is essentially assigning some score based on the rank (e.g. like NDCG does); and that we can rewrite such a function as a linear combination of weighted scores over ranks. (So that we can estimate these weights in a ML-approach)

Problems with click feedback

But we are dealing with the care where do not have the true labels, but only implicit feedback from clicks.

Problem:

  • But clicks are noisy indicators of relevance.
  • Not-clicking does not necessarily indicate non-relevance

So we may have y(d3)=0 and c3=1, and y(d4)=1 and c4=0.

There are various reasons a user may not click on a relevant result. Reasons for not clicking:

  • Relevance: Document may not be relevant
  • Observance: User may not have examined the document
  • Miscellaneous

Some of these reasons are essentially noise, which means they will disappear when averaging over them. Some of them are due to systematic bias, which means that averaging will not remove this biasing effect (e.g. position bias).

Q: What's the difference between noise and bias?

Q: Why is averaging over many click results not effective against bias?

Examination user model

We make some assumptions on how users looks at rankings. We consider examination and relevance: a click is fully determined by whether it is examined and whether it is relevant.

$o_i=1$ means that document $d_i$ is examined in ranking R. The probability of inspection different per ranking (due to position effects etc.):

$P(o_i=1|R,d_i)$

Chance of clicking depends on actually observing the document and the relevance of the document:

$P(c_i|o_i,y(d_i))$

And clicks only occur on examined documents, so probability of a click is probability that someone examines, and then if they examine it, the probability that it's relevant.

Now we want to use clicks as an unbiased relevance signal.

That means, we want the expectation to be independent of the probability of watching, i.e. we need to compensate for bias with the appropriate amount.

Naive Estimator

We have a new undeployed ranking model and click patterns. We replace the relevance function with the click function, and then we take the average times a relevant result is clicked overall queries.

But this naive estimator is biased even without click noise. We can do this by computing the expectation of observation; see slide 23.

The problem is that the biased estimator still weights documents according to their examination probabilities in the ranking R displaying during logging.

Meaning: our estimated probabilities are going to be biased to documents that were already high in the old ranking system. So this evaluation metric leads to a self-reinforcing system.

This position bias causes logging-policy-confirming behavior. So documents displayed higher during logging are incorrectly pushed to the top of the ranking.

Q: Explain why bias leads/ can lead to self-reinforcing learning behavior (logging-policy-confirming behavior)

Countering bias: Inverse propensity scoring

We can counter this bias due to $P(o_i=1|R,d_i)$ by dividing by this probability.

I.e. we weigh clicks inversely proportional to the examination probabilities.

This leads to an unbiased estimate for a linearly decomposable IR metric; if no click noise is present.

Intuition: the IPS estimates does weighting inversely proportional to the examination probabilities. So this way we compensate for the "golden triangle" by penalizing the score of those documents benefiting from position bias.

Robustness of noise

If doc i is more relevant than doc j, the click probability for doc i should be higher when conditioned upon the observation probability. Using this, one can show that noise does not affect the previously shown results.

(We care about ranking; thus noise is not a problem as long as we can show it does not affect the ranking even if it affects relevance scores)

Propensity-weighted learning to rank (LTR)

So we have an unbiased metric. Two problems:

  • This metric is not differentiable because it involved a rank function (=a step function)
  • This is a common problem for all ranking metrics

So how do we optimize for this metric then?

A common strategy is to instead optimize a differentiable upper bound. E.g. using Rank-SVM (Joachims, 2002).

Experiments often use semi-synthetic data: see p.35

Linear hinge-loss.

This you can optimize with stochastic gradient descent.

Review the last math-heavy slides.

Notice in slide 36 that IPS starts out with more variance and worse performance. But this is common for unbiased systems. But if you gather enough clicks, you will convergence on the oracle line.

Estimate the observation propensity

Slide 38: we still need to divide by the probability of observation. In practice this is solved by assuming the observation probability depends on the rank of the document.

Randomization can be used to estimate position bias. (slide 41)

RandTop-n algorithm: if we randomly shuffle documents to create random rankings multiple times, each rank will have a uniform distribution over documents.

If I then examine the clicks on these randomized rankings, we know that any deviation from the expected distribution is going to be due to position bias.

(Downside: users may hate you because the rankings are non-sensical)

Time was up.