Minimally Invasive Randomization for Collecting Unbiased Preferences
  from Clickthrough Logs
  Clickthrough data is a particularly inexpensive and plentiful resource to
obtain implicit relevance feedback for improving and personalizing search
engines. However, it is well known that the probability of a user clicking on a
result is strongly biased toward documents presented higher in the result set
irrespective of relevance. We introduce a simple method to modify the
presentation of search results that provably gives relevance judgments that are
unaffected by presentation bias under reasonable assumptions. We validate this
property of the training data in interactive real world experiments. Finally,
we show that using these unbiased relevance judgments learning methods can be
guaranteed to converge to an ideal ranking given sufficient data.
