Unbiased Recommender Learning from Missing-Not-At-Random Implicit Feedback

Yuta Saito; Suguru Yaginuma; Yuta Nishino; Hayato Sakata; Kazuhide Nakata

Source-linked AI summary

Unbiased Recommender Learning from Missing-Not-At-Random Implicit Feedback

Yuta Saito, Suguru Yaginuma, Yuta Nishino, Hayato Sakata, Kazuhide Nakata

arXiv:1909.03601v3Sep 9, 2019stat.MLcs.IRcs.LG

TL;DR

Implicit feedback is abundant but ambiguous: non-clicks can be unobserved positives, while exposure makes popular items more likely to receive clicks. The paper defines a relevance-based ideal loss, derives an unbiased estimator and a clipped variance-reduction variant, and reports stronger ranking performance, particularly for rare items.

Problem
Implicit feedback does not distinguish negative responses from unobserved positives and is subject to MNAR exposure bias toward popular items.
Method
The paper defines an ideal relevance-maximizing loss, derives an unbiased estimator from observable feedback, and proposes a clipped estimator to reduce variance.
Results
The proposed method largely improves ranking metrics over baselines and improves prediction for less popular items.
Takeaways & Limitations
The method better targets recommendations with the highest relevance rather than the highest click probability.
Takeaways & Limitations
The unbiased estimator relies on true propensity scores, and the paper identifies better exposure-probability estimation as a next step.

Abstract

from arXiv · show

Recommender systems widely use implicit feedback such as click data because of its general availability. Although the presence of clicks signals the users' preference to some extent, the lack of such clicks does not necessarily indicate a negative response from the users, as it is possible that the users were not exposed to the items (positive-unlabeled problem). This leads to a difficulty in predicting the users' preferences from implicit feedback. Previous studies addressed the positive-unlabeled problem by uniformly upweighting the loss for the positive feedback data or estimating the confidence of each data having relevance information via the EM-algorithm. However, these methods failed to address the missing-not-at-random problem in which popular or frequently recommended items are more likely to be clicked than other items even if a user does not have a considerable interest in them. To overcome these limitations, we first define an ideal loss function to be optimized to realize recommendations that maximize the relevance and propose an unbiased estimator for the ideal loss. Subsequently, we analyze the variance of the proposed unbiased estimator and further propose a clipped estimator that includes the unbiased estimator as a special case. We demonstrate that the clipped estimator is expected to improve the performance of the recommender system, by considering the bias-variance trade-off. We conduct semi-synthetic and real-world experiments and demonstrate that the proposed method largely outperforms the baselines. In particular, the proposed method works better for rare items that are less frequently observed in the training data. The findings indicate that the proposed method can better achieve the objective of recommending items with the highest relevance.

1 INTRODUCTION

Implicit feedback is easy to collect but conflates unobserved positives with negatives and overrepresents popular items. The paper targets relevance rather than click probability with an unbiased, variance-aware estimator that improves ranking, especially for rare items.

Motivation: Implicit click data are widely used because they are easier to collect than explicit ratings.Ratings require active user participation, whereas clicks represent behavior logs.
Problem: Unclicked items may be either irrelevant or positive items that users were never exposed to.This creates the positive-unlabeled problem.
Problem: Exposure-driven clicks create an MNAR problem because popular or frequently recommended items are more likely to be clicked, even without strong interest.Existing exposure weighting can therefore bias predictions toward popular items and hurt rare-item accuracy.
Approach: The paper defines an ideal relevance-maximizing loss and derives an unbiased estimator from observable feedback, then analyzes variance and proposes a clipped estimator.The clipped estimator is designed to improve the bias-variance trade-off.
Findings: The proposed method largely improves ranking metrics over baselines and performs better for less popular items.Experiments use both semi-synthetic and real-world datasets.

2 NOTATION AND PROBLEM FORMULATION

The formulation separates observed clicks from latent relevance and exposure, then evaluates rankings using relevance rather than clicks. It defines an ideal pointwise loss whose minimizer is expected to optimize the relevance-based top-N metric.

2.1 Notation: The framework represents users, items, and all user-item pairs with sets U, I, and D, while clicks form a binary matrix Y.Each click entry is modeled as a Bernoulli random variable.
2.1 Notation: A click indicates positive feedback, but a non-click may be either negative feedback or an unlabeled positive.This distinction motivates separate latent relevance and exposure variables.
2.1 Notation: Relevance R and exposure O are latent matrices, whereas only the click matrix Y is observable.R denotes whether a user and item are relevant; O denotes whether the item was exposed.
2.1 Notation: The model assumes exposure and relevance parameters are non-zero for every user-item pair.The parameters are defined as θu,i = P(Ou,i = 1) and γu,i = P(Ru,i = 1).
2.1 Notation: Clicks are generated when an item is both exposed and relevant, so a click does not always signify relevance.The formulation separates the conditions producing an observed click from relevance itself.
2.1 Notation: Exposure and relevance probabilities can vary by user-item pair, allowing the formulation to represent MNAR feedback.The model permits click probability and relevance level to be non-proportional.
2.2 True Performance Metric: Standard top-N metrics such as MAP, recall, and DCG use predicted item rankings and a scoring function over rank positions.For DCG@K, the scoring function is I{bZu,i ≤ K}/log(bZu,i + 1).
2.2 True Performance Metric: Because clicks do not directly signify relevance, the paper evaluates rankings with a relevance-based metric and optimizes a corresponding ideal loss.The loss is pointwise; with log loss, it uses relevance labels and predicted relevance values.

3 ANALYSIS ON EXISTING BASELINES

The section shows that WMF and ExpoMF optimize loss functions biased against the ideal relevance loss. WMF uses uniform click weighting, while ExpoMF reweights exposed data but can underpredict low-exposure items.

3.1 Weighted Matrix Factorization: WMF uniformly upweights clicked data relative to unclicked data using a confidence hyperparameter c.Without side information, c is uniform across clicked data.
3.1 Weighted Matrix Factorization: WMF is biased against the ideal loss because unclicked feedback can be unlabeled positive feedback and propensity values vary across user–item pairs.The required unbiasedness conditions are not generally satisfied.
3.2 Exposure Matrix Factorization: ExpoMF models clicks as depending on both exposure and relevance, then uses posterior exposure probabilities to reweight exposed data.Its EM-like procedure estimates posterior exposure probabilities in the E-step and updates model parameters in the M-step.
3.2 Exposure Matrix Factorization: ExpoMF’s M-step loss is also biased against the ideal loss because its pair-specific exposure reweighting does not satisfy unbiasedness for all pairs.This conclusion is stated when posterior exposure probabilities are given.
3.2 Exposure Matrix Factorization: ExpoMF’s emphasis on frequently observed, high-exposure data can reduce prediction accuracy for low-exposure tail items.The section therefore identifies handling both MNAR feedback and unlabeled implicit feedback as necessary for a desirable estimator.

4 PROPOSED METHOD

The proposed method estimates an ideal relevance loss from observable implicit feedback using propensity-based debiasing, then reduces estimator variance through clipping. The clipped estimator trades bias for lower variance and interpolates between naive and unbiased estimators.

4.1 Proposed Estimator: The method defines an ideal relevance loss and proposes an unbiased estimator using propensity scores, extending IPS and positive-unlabeled learning.The estimator is designed to address both MNAR exposure and the unlabeled nature of implicit feedback.
4.1 Proposed Estimator: The propensity score is the exposure probability θu,i = P(Ou,i = 1) = P(Yu,i = 1 | Ru,i = 1).The estimator uses this score despite the exposure indicator being unobserved.
4.1 Proposed Estimator: The unbiased estimator applies both positive and negative losses to clicked data and is unbiased against the ideal loss.Proposition 4.3 validates propensity reweighting for MNAR implicit recommendation.
4.2 Variance Reduction Technique: The unbiased estimator can have high variance because its variance depends on inverse propensity scores, which may be large for tail items.Small exposure probabilities increase the variance in implicit recommendation settings.
4.2 Variance Reduction Technique: As M approaches 1, the clipped estimator approaches naive WMF with c = 1; as M approaches 0, it approaches the unbiased estimator.Thus, clipping provides a general form spanning these two estimators.
4.2 Variance Reduction Technique: The clipped estimator clips small propensity scores, always reducing variance while introducing bias dependent on the clipping constant M.M is tuned as a validation-set hyperparameter.

5 SEMI-SYNTHETIC EXPERIMENT

The semi-synthetic experiments evaluate relevance prediction and ranking under varying exposure bias using ground-truth relevance and exposure parameters. The proposed unbiased model consistently outperforms the naive model, especially when exposure bias is limited.

5.1 Dataset and Models: The experiment uses MovieLens 100K ratings to construct semi-synthetic data with known relevance and exposure parameters.Ratings are modeled to approximate true relevance and observation behavior before generating click variables.
5.1 Dataset and Models: Exposure bias is controlled by p, with larger values introducing greater skew in the exposure distribution.The experiment uses p values of 0.5, 1, 2, 3, and 4, with ϵ = 5.
5.1 Dataset and Models: MF-Naive uses observable clicks, whereas MF-Unbiased estimates the ideal relevance loss and MF-Oracle trains on ground-truth relevance.MF-Naive becomes biased under exposure bias, while MF-Unbiased is affected by propensity-weighting variance.
5.2.1 RQ1: Both MF-Naive and MF-Unbiased decline in performance as exposure bias increases, but MF-Unbiased consistently outperforms MF-Naive.The results attribute MF-Naive’s degradation to bias and MF-Unbiased’s degradation to variance in propensity weighting.
5.2.2 RQ2: MF-Unbiased outperforms MF-Naive in DCG@K across all tested settings and approaches MF-Oracle when p = 0.5.At p = 4, the benefit of unbiased estimation is relatively small, consistent with the relevance-prediction results.

6 REAL-WORLD EXPERIMENT

The real-world experiment evaluates WMF, ExpoMF, and the proposed Rel-MF on Yahoo! R3 using ranking metrics for all and rare items. Rel-MF outperforms the baselines in almost all settings, including for less-frequently observed items.

6.1 Dataset and Evaluation: Yahoo! R3 provides ratings for randomly selected test items, enabling evaluation against users’ true relevance judgments.Ratings of at least 4 are treated as relevant, while lower ratings are treated as irrelevant.
6.1 Baselines and Model: The experiment compares WMF, ExpoMF, and Rel-MF, the proposed model based on the implicit-feedback latent-factor framework.Rel-MF uses the proposed relevance-oriented estimator.
6.1 Evaluation: DCG, Recall, and MAP are reported at K ∈ {1, 3, 5} to evaluate ranking performance.Hyperparameters are tuned using the SNIPS estimator of DCG@5 because validation and test item distributions differ.
6.2 Results: Rel-MF significantly outperforms the baselines on almost all metrics, improving DCG@5 by 20.4%, Recall@5 by 9.6%, and MAP@5 by 26.6% over ExpoMF.The comparison covers both rare and all items.
6.2 Results: For rare items, Rel-MF improves DCG@5 by 11.8%, Recall@5 by 6.4%, and MAP@5 by 11.2% over the best baseline.ExpoMF outperforms Rel-MF for rare items at K = 1 across all reported metrics.
6.2 Results: ExpoMF outperforms WMF in all settings, while Rel-MF outperforms the other baselines in most cases.The paper attributes Rel-MF’s rare-item gains to its treatment of MNAR feedback rather than downweighting low-exposure items.

7 CONCLUSION

The paper defines relevance-oriented objectives, derives an unbiased estimator for implicit feedback, and introduces clipping to reduce variance. Experiments show stronger relevance maximization, particularly for low-exposure items, while exposure estimation remains an important limitation.

7 Conclusion: The paper defines an ideal loss function for maximizing relevance and analyzes bias in WMF and ExpoMF relative to that objective.The objective is framed around improving user experience through relevance-oriented recommendation.
7 Conclusion: An unbiased estimator is derived from observable feedback using ideas from causal inference and positive-unlabeled learning.The estimator targets the ideal loss despite implicit feedback’s exposure and labeling issues.
7 Conclusion: A clipped estimator introduces a small bias to reduce variance and improve the bias-variance trade-off.The clipped estimator includes the unbiased estimator as a special case.
7 Conclusion: Experiments show that the proposed method significantly outperforms existing methods for relevance maximization, especially on low-exposure items.The authors present this finding as empirical evidence that the approach can maximize the user-experience objective.
7 Limitations and Future Work: The estimator’s unbiasedness relies on true propensity scores, making improved exposure-probability estimation an important next step.The paper also identifies extension to pairwise algorithms as an open direction.