2
$\begingroup$

In ranking, a commonly used method to evaluate the performance of a ranking algorithm is calculating ranking metrics such as MAP, NDCG. In use cases where there is no ground truth signal, some proxy signals as used for relevance. For example, in a recommendation system, we can use user's interactions (clicks, purchases) with the items as the positive relevance signal to calculate MAP or NDCG.

The problem with this is that the interactions(clicks/purchases in the example) has bias toward the ranker (usually the production ranker) that generates them. Thus it's not fair to compare the production ranker and a new ranker using this kind of signal. Is there a way to de-bias such signals for evaluation so that one can fairly compare new algorithms with the one that produce the evaluation data?

$\endgroup$

migrated from stackoverflow.com Feb 14 '18 at 13:50

This question came from our site for professional and enthusiast programmers.

3
$\begingroup$

This is a great question that people are doing research on. Therefore, part of my answer will be throwing papers at you.

  1. Offline vs. Online. (The get more labels approach)

I assume that you want to correct these labels so you can do an offline evaluation. One of the strategies for dealing with this issue is an "interleaved" evaluation where you present a fusion of results between two systems in order to compare them -- basically it boils down to which system gets more clicks at that point.

Some of this comes down to the "Exploration vs. Exploitation" tradeoff. Could you use your algorithm pool to make sure that users see candidates that will be more informative? (Hofmann, Katja, Shimon Whiteson, and Maarten de Rijke. "Balancing Exploration and Exploitation in Learning to Rank Online.")

  1. Weighting instances by how likely they are to be rank-biased. (Learn better model anyway / re-weight by surprise)

It turns out you can learn weights on queries (clicks) based on how far down they are. Basically, the more they diverge from your production ranker, the more informative they are for learning (under the hypothesis that your prod ranker will get easy queries right). There are sophisticated strategies for this, e.g., (Wang, Xuanhui, Nadav Golbandi, Michael Bendersky, Donald Metzler, and Marc Najork. "Position Bias Estimation for Unbiased Learning to Rank in Personal Search." (2018).) but they cite a paper that used simple weights learned from randomization experiments.

  1. The evaluation-metric way (focus on actual clicks somehow)

Throw out all documents from your rankings that don't have clicks (or views), and calculate MAP only on those. This is fair, but difficult, potentially, with only positive labels (you could infer some negative weight on documents that appeared before a click but were not clicked themselves). There are a number of ways to do this, from the heuristic, to special evaluation signals:

Sakai, Tetsuya. "Alternatives to bpref." Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 2007. + Google Scholar results for "unjudged documents sigir"

Conclusion

The most robust answer will involve an online experiment. We know this from statistics. You're never supposed to use a dataset twice.

However, depending on your position (industry v. academia) it may or may not be possible to simply do another experiment, or to put an untrusted ranker in front of users to get more fair labels. In which case, try to zoom in only on the biased labels (Option 3) or weight them using (Option 2) and use NDCG. These approaches can be justified and are slightly better than reinventing the wheel.

$\endgroup$
  • $\begingroup$ Thanks for the great answer. I actually did some research on option 2: I read a few papers from Thorsten Joachims's group (cs.cornell.edu/people/tj) and some others including the one you linked. But I feel that in real system it's pretty hard to estimate the propensity score. $\endgroup$ – Rainfield Feb 15 '18 at 17:06
  • $\begingroup$ The third method you gave is new to me and I found it's interesting and easy to implement. One question I have is that if I only used click or purchase as signal, then it won't work on condensed lists since there is only one level of relevance. Maybe I can try combine two levels of relevance, one for click and one for purchase. $\endgroup$ – Rainfield Feb 15 '18 at 17:08
  • $\begingroup$ Treating clicks and purchases differently is definitely a good idea, much like clicks in web SERPs are of different value based on dwell-time (i.e. did they spend any time on the page, or click it by accident?) you have the potential to train a better ML model. It might be as easy as calling purchases 2 and clicks 1. $\endgroup$ – John Foley Feb 15 '18 at 17:30
  • $\begingroup$ For a lot of real world use cases, user's interactions are pretty sparse, and in most sessions there might be only a few clicks without purchase. In this case data sparsity could be an issue. $\endgroup$ – Rainfield Feb 15 '18 at 18:14
  • $\begingroup$ Oh, definitely. But data sparsity is always an issue with ranking: you may have billions of documents and only 1 that is really relevant. $\endgroup$ – John Foley Feb 16 '18 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.