Unbiased Recommender Learning from
Missing-Not-At-Random Implicit Feedback
Yuta Saito, Suguru Yaginuma, Yuta Nishino,
Hayato Sakata, and Kazuhide Nakata
Web Search and Data Mining (WSDM20)
February 4th, 2020 (Tue)Introduction &Problem SettingObjective of Recommendation
Recommend Relevant (R) Items to Each User!!!
example) Top-3 Recommendation
Ranking

Recommender A

Recommender B

1

R=1

R=0

2

R=1

R=1

3

R=1

R=0ーーーーーーーーー

9

R=0

R=110

R=0

R=1

Recommender A
is better thanRecommender B
simply because
Recommender A
recommends
more relevant items

Ideal Loss function of Interest (Pointwise)
To maximize relevance, the following loss should be optimizedDeﬁnition) Ideal Pointwise Loss Function

Binary Relevance Indicatorof u and i

Ideal Loss function of Interest (Pointwise)
To maximize relevance, the following loss should be optimizedDeﬁnition) Ideal Pointwise Loss Function

Prediction for relevance levelof u and i

Ideal Loss function of Interest (Pointwise)
To maximize relevance, the following loss should be optimizedDeﬁnition) Ideal Pointwise Loss Function

Example) Cross-entropy loss

Arbitrary loss function(e.g., cross-entropy, squared loss)

Challenge: Relevance Label is hard to collect
It is desirable to optimize ideal loss function
for our objective of relevance maximization

Challenge: Relevance Label is hard to collect
It is desirable to optimize ideal loss function
for our objective of relevance maximization
However, it is often Expensive or Time Consuming
to use relevance information as the label●Explicit Rating Feedback (Time Consuming)●Expert Annotation (Expensive, Time Consuming)●Crowdsourcing (Time Consuming, Noisy)

Alternative Solution: Implicit Feedback

Implicit Feedback is Cheap and Easy to collectand used as an alternative for the Relevance LabelImplicit Feedback● Natural user behaviour(clicks, views, log-in)● Easily collected in real-world
recommender systems● Used by many Tech companies

Why not use Implicit Feedback as Relevance Label ???
One possible way to use implicit feedback is direct imputation
ideal loss

imputed loss

Neural Collaborative Filtering (He et al.) optimizes the imputed loss function by DNN

Why not use Implicit Feedback as Relevance Label ???
One possible way to use implicit feedback is direct imputation
ideal loss

imputed loss

Question: Is this direct imputation valid?

Implicit Feedback ≠ Relevanceexample) Top-2 recommendation by most-popular policy
Item
Ranking

Recomme Relvancended?
(R)???

Click(Y)

1

Yes!

R=1

Y=1

2

Yes!

R=0

Y=0ーーー

ーーー

ーーー

99

No...

R=1

Y=0

100

No...

R=0

Y=0ーーーーーー

It seemes
Implicit Feedback
is not equal toRelevance LabelExposure Model (Liang et al., WWW’16)
Exposure model assumes the following
connection between implicit feedback and relevance label

Implicit Feedback(e.g., click)Exposure Variable( unobserved )Relevance Variable( unobserved )Item is clicked = Item is exposed & Item is relevantExposure Model (Liang et al., WWW’16)
Exposure model also assumes the following decomposition

This assumption is equivalent to the Unconfoundedness in causal inferenceImplicit Feedback ≠ Relevance
example) Top-2 recommendation by most-popular policy
ItemRanking

Recomme Relvance Exposurended?
(R)(O)

Click(Y)

1Yes!

R=1

O=1

Y=1

2

Yes!

R=0

O=1

Y=0ーーー

ーーー

ーーー

ーーー

ーーー

99

No...

R=1

O=0

Y=0100

No...

R=0

O=0

Y=0Exposure Modelcan clearly explain
the situation

Implicit Feedback ≠ Relevanceexample) Top-2 recommendation by most-popular policy
ItemRanking

Recomme Relvance Exposure
nded?
(R)
(O)

Click(Y)

1Yes!

R=1

O=1

Y=1

2

Yes!

R=0

O=1

Y=0ーーー

ーーー

ーーー

ーーー

ーーー

99

No...

R=1

O=0

Y=0100

No...

R=0

O=0

Y=0Unobserved

The problem ishow to optimize R
using only Y
Exposure Modelcharacterizes
the diﬃculties

Challenge 1: Positive-Unlabeled (PU)
Only positive-side feedback is observed,
and the negative feedback is always unobserved

The lack ofimplicit feedback

doesn’t imply

Irrelevance
between u and i

Challenge 2: Missing-Not-At-Random (MNAR)

The positive-labels of some items are much
more frequently observed (popularity bias)

Exposure probability is not uniform

among user-item pairs

In summary,● We want to maximize relevance in recsys
using only available implicit feedback● How to deﬁne theoretically justiﬁed loss function
with implicit feedback is the critical problem● We aimed to statistically estimate the ideal loss func
using only implicit feedback in our workSolutions &Experiments

Our Approach: Unbiased Estimation of Ideal Loss Function
We propose the ﬁrst unbiased estimator combining the inverse
propensity weighting & positive-unlabeled learning
ideal loss

unbiased loss

Our Approach: Unbiased Estimation of Ideal Loss Function
We propose the ﬁrst unbiased estimator combining theinverse propensity weighting & positive-unlabeled learning

The basic idea is to weight each implicit feedback by
the inverse of the exposure parameter (the propensity score)Our Approach: Unbiased Estimation of Ideal Loss Function

This estimator is proved to be theoreticallyunbiased for the ideal loss function

The proposed loss function

The ideal loss function

Summary of Solutions to the Challenges
Our main contribution is to develop the ﬁrst unbiased loss
func for the ideal loss func using only implicit feedbackApproach

Unbiased?
No...

(Hu et al., ICDM’08)Positive sample
weightingExpoMFEM Algorithm

No...

Inverse Propensity
Weighting

Yes!

WMF

(Liang et al., WWW’16)

Rel-MF(saito et al., WSDM’20)

Real-World Experiment (with Yahoo! R3 dataset)
We conduct performance comparisons using Yahoo data
Yahoo! R3 dataset● contains ground-truth relevance label (5 star-rating)● contains train-test data with diﬀerent item distributions
This dataset is convenient for the evaluation of
Implicit feedback recommenders with MNAR formulation

Real-World Experiment (with Yahoo! R3 dataset)
The unbiased Rel-MF generally outperforms the others
For all items

WMF

DCG@5

Recall@5

MAP@50.363

0.502

0.277

0.402

0.530

0.321

0.485

0.582

0.407

(Hu et al., ICDM’08)

ExpoMF(Liang et al., WWW’16)

Rel-MF(saito et al., WSDM’20)

Real-World Experiment (with Yahoo! R3 dataset)
Ours also outperforms for the rare items
For rare items

WMF

DCG@5

Recall@5

MAP@5

0.329

0.526

0.242

0.382

0.557

0.307

0.428

0.593

0.345

(Hu et al., ICDM’08)

ExpoMF(Liang et al., WWW’16)

Rel-MF(saito et al., WSDM’20)

Conclusions● Implicit feedback is often used but is biased( positive-unlabeled & missing-not-at-random )● Previous solutions are biased for the ideal loss function● We proposed the ﬁrst unbiased loss function forunbiasedly learning recsys from biased implicit feedback
Thank you for Listening & Please Come to the Poster !!!

Appendix

How to estimate the propensity score?
We used the simple relative item popularity as the propensityscore

A more sophisticated way of estimating propensities is afuture work

Previous Solutions to the Challenges
Weighted Matrix Factorization (WMF) and Exposure Matrix
Factorization (ExpoMF) are the most basic methods
Approach

Unbiased?
No...

(Hu et al., ICDM’08)

Positive sample
weightingExpoMFEM Algorithm

No...

WMF

(Liang et al., WWW’16)

Previous Solutions are biased for the ideal loss func

In the paper, the loss function of the previousmethods are proved to be biased, i.e.,

Future Work
● Propensity score estimation● Unbiased estimator for the pairwise method(e.g., unbiased version of bayesian personalized ranking)● Theoretical Analysis on the Learnability●Possible connection with other types of feedbackReferences(Liang et al., WWW’16): Dawen Liang, Laurent Charlin, James McInerney, and David M Blei. 2016. Modeling user exposure inrecommendation. In Proceedings of the 25th International Conference on World Wide Web. International World Wide Web Conferences
Steering Committee, 951–961.
(Saito et al., WSDM’20): Yuta Saito, Suguru Yaginuma, Yuta Nishino, Hayato Sakata, and Kazuhide Nakata. 2020. Unbiased
Recommender Learning from Missing-Not-At-Random Implicit Feedback. In The Thirteenth ACM International Conference on Web Searchand Data Mining (WSDM’20), February 3–7, 2020, Houston, TX, USA. ACM, New York, NY, USA.
(Hu et al., ICDM’08): Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative ﬁltering for implicit feedback datasets. In 2008
Eighth IEEE International Conference on Data Mining. Ieee, 263–272.
(Schnabel et al., ICML’16) : Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. 2016.
Recommendations as Treatments: Debiasing Learning and Evaluation. In International Conference on Machine Learning. 1670–1679(Rendle et al., UAI’09) : Steﬀen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009. BPR: Bayesian
personalized ranking from implicit feedback. In Proceedings of the twenty-ﬁfth conference on uncertainty in artiﬁcial intelligence. AUAIPress, 452–461.

References(Yang et al., RecSys’18): Longqi Yang, Yin Cui, Yuan Xuan, Chenyang Wang, Serge Belongie, and Deborah Estrin. 2018. Unbiased oﬄine
recommender evaluation for missing-not-atrandom implicit feedback. In Proceedings of RecSys ’18. ACM, 279–287.
(Wang et al., WSDM’18): Xuanhui Wang, Nadav Golbandi, Michael Bendersky, Donald Metzler, and Marc Najork. 2018. Position Bias
Estimation for Unbiased Learning to Rank in Personal Search. In Proc. of the 11th ACM International Conference on Web Search and Data
Mining (WSDM). 610–618.
(Ai et al., SIGIR’18): Qingyao Ai, Keping Bi, Cheng Luo, Jiafeng Guo, and W Bruce Croft. 2018. Unbiased Learning to Rank with Unbiased
Propensity Estimation. In Proc. of the 41st International ACM SIGIR Conference on Research & Development in Information Retrieval(SIGIR). 385–394.
(Marlin et al., RecSys’09): Benjamin M Marlin and Richard S Zemel. 2009. Collaborative prediction and ranking with non-random missing
data.
(Wang et al., ICML’19): Xiaojie Wang, Rui Zhang, Yu Sun, and Jianzhong Qi. 2019. Doubly robust joint learning for recommendation on
data missing not at random. In International Conference on Machine Learning, pages 6638–6647.
(Liang et al., UAI’16 Causal WS): Dawen Liang, Laurent Charlin, and David M Blei. 2016. In Causation: Foundation to Application,Workshop at UAI.