Overcoming bias
in search and recommendations
metarank.ai | github.com/metarank/metarank | Grebennikov Roman | 2022
This is me
- Long ago: PhD in CS, quant trading, credit scoring
- Past: Search & personalization for ~7 years
- Now:
Unemployed Full-time open-source contributor
Metarank
a swiss army knife of re-ranking
Ranking around us
Sort by # of clicks
![](img/yolo.jpg)
- Pros: easy to implement
- Cons: new items are never on top
Self-degrading ranking
![](img/selfdegrade.png)
- People are lazy: top items get more clicks
- Popular items become even more popular
Behavioral biases
- Position: top items clicked more often
- Presentation: grid/pagination affects click probability
- Popularity: snickers vs no-name chocolate
- Model: train ML model on it's own output
Position bias
![](img/bias-monster.jpg)
- We click on first items because they're on top
- Click on #1 - is it relevant or just first?
Experiment: movie search
- top-10k TMDB movies
- Top-30k movie-related queries from Google
- Crowdsourced with toloka.ai
- 650k labels: 8% relevant
Shooting yourself in the foot
- Toloka has unbiased "search relevance" template
- Made it biased with explicit item ordering
The trick: shuffled results
- Top-24 results by BM25 score, but randomly ranked
- relevance should be independent from position *
![](img/click-bias.png)
* - after outlier removal
Not only position
![](img/presentation-bias.png)
- presentation affects clicks
Presentation bias
- click % drop on a second row
Bias & search function
- Movie search: navigational function => low bias
- Ecommerce: discovery function => high bias
![](img/jeans2.png)
Not so independent
In practice you observe relevance + bias together
Learning-to-Rank 101
![](img/dummies.png)
- Implicit feedback: clicks on items
- Item metadata as ranking factors
- Loss function: pairwise, NDCG
Not all clicks were made equal
![](img/ltr-table.png)
Clicks as relevance labels?
![](img/observed.png)
- if observed_label = bias * true_label
- then true_label = observed_label / bias
![](img/sus3.jpg)
IPW: Inverse Propensity Weighting
![](img/ipw.png)
- How can we estimate the bias?
IPW in 10 seconds
- Shuffle ranking for small % of traffic
- Estimate the bias
- De-bias the remaining data
![](img/ipw-perf.png)
Estimating the bias
![](img/bias-est.png)
Less costly IPW
- Top-N shuffle: only top-3 positions are affected
- Pairwise swaps: over all traffic
- Multi-ranker: exploit ongoing a/b tests
ML model to predict bias?
- Only biased ranking factors: popularity, cost, position
- Predicted click probability == bias
![](img/em.png)
![](img/no-idea.jpg)
- Weighting: prefer bottom-position clicks
- Sampling: drop some top-position clicks
A story of IPW
![](img/reverse.png)
|
- "Too many unpopular items on top"
- IPW ranking = inverse of non-IPW ranking
- Training data is popularity biased
- Low popularity = ML's high reward
|
Bias is context dependent, hard to estimate precisely
Bias-aware ML
Can we learn the relevance AND bias influence at once?
![](img/pal.png)
Bias-aware ranking
![](img/PAL.png)
- Training: Use biased ranking factors as-is
- Inference: Replace these with constants
Ranklens dataset
![](img/ranklens.png)
- Also crowd-sourced with toloka.ai
- ~3k people labelled favourite movies in ~100 categories
Metarank
![](img/reranking.png)
- Take a stream of historical/realtime events
- Re-rank top-N candidates for better NDCG
Why PAL?
- Shuffling: complicated and costly
- Can learn context
- Can be adapted to popularity/presentation biases
Results
- Biased: NDCG=0.6002
- De-biased: NDCG=0.6060, +1%
![](img/position-mr.png)
Should you de-bias?
- Navigation vs discovery: it depends
- There are better algos than PAL
Extra
![](img/qr.png)