Towards Resolving Propensity Contradiction in Offline Recommender Learning

1 Introduction

In industrial recommender systems, it is essential to obtain a well-performing rating predictor from sparse rating feedback to recommend items relevant to users. An important challenge is that most of the missing mechanisms of real-world explicit rating data are missing-not-at-random (MNAR) [Marlin and Zemel, 2009; Schnabel et al., 2016; Wang et al., 2019; Chen et al., 2020]. There are two main causes behind the MNAR mechanism. The first is the past recommendation policy. Suppose that we rely on a policy that recommends popular items with high probabilities. Then, the observed ratings under that policy include more data of popular items [Bonner and Vasile, 2018]. The second is self-selection by users. It is well-known that the users tend to rate items for which they exhibit positive preferences, and the ratings for items with negative preferences are more likely to be missing [Marlin and Zemel, 2009; Schnabel et al., 2016].

1.1 Open Problem: Propensity Contradiction

Selection bias makes it difficult to learn rating predictors, as naive methods typically result in suboptimal and biased recommendations with MNAR data [Schnabel et al., 2016; Steck, 2010; Wang et al., 2019]. One of the most established solutions to this problem is the propensity-based approach. It defines the probability of each feedback being observed as a propensity score and obtains an unbiased estimator for the true metric via inverse propensity weighting [Liang et al., 2016; Schnabel et al., 2016; Wang et al., 2019]. In general, unbiasedness of IPS is desirable, however, it is valid only when the true propensity score is available. Previous studies utilize some amount of missing-completely-at-random (MCAR) test data to estimate the propensity score and ensure their empirical performance [Schnabel et al., 2016; Wang et al., 2019]. In most real-world recommender systems, however, the true propensity score is unknown, and MCAR data are unavailable as well, resulting in a severe bias in the estimation of the loss function of interest. Thus, there remains a critical contradiction: the performance of the IPS variants relies heavily on mostly inaccessible MCAR data, although they originally aim at training recommenders using only MNAR data.

Two previous methods tackle the challenge of those propensity-based methods. The first one is causal embeddings (CausE) [Bonner and Vasile, 2018]. It introduces a domain regularization term to address the bias. However, CausE requires some amount of MCAR data by its design; it cannot be generalized to a realistic setting with only MNAR training data. Moreover, its domain regularization technique is a heuristic approach and lacks a theoretical guarantee. The other method is to use 1-bit matrix completion (1BitMC) [Ma and Chen, 2019] to estimate propensity scores using only MNAR training data, along with a theoretical guarantee. However, the problem is that these methods presuppose the debiasing procedure with inverse propensity weighting and thus cannot be used when there is a user-item pair with zero observed probability. Furthermore, the experiments on 1BitMC were conducted using only extremely small datasets (Coat and MovieLens 100k) and prediction accuracy measures (MSE); accordingly, its performance on moderate size benchmark datasets (e.g., Yahoo! R3 [Mnih and Salakhutdinov, 2008]) and on a ranking task remain unknown.

1.2 Contributions

To overcome the limitations of the existing methods, we establish a new theory for offline recommender learning inspired by the theoretical framework of unsupervised domain adaptation (UDA) [Ben-David et al., 2010]. UDA aims to obtain a good predictor in settings where the feature distributions between the training and test sets are different. To this end, UDA utilizes distance metrics that measure the dissimilarity between probability distributions and does not depend on the propensity score [Ganin et al., 2016; Saito et al., 2017; Saito, 2020a]. Thus, the framework is usable even when the true propensity score is unknown and is expected to alleviate the issues caused by the propensity estimation bias in the absence of MCAR data. Moreover, the method is valid even when there is a user-item pair with zero observed probability.

To figure out a solution to the propensity contradiction, we first define a novel discrepancy metric to quantify the similarity between two missing mechanisms of rating feedback. Building on our discrepancy measure, we derive a propensity independent generalization error bound for the loss function of interest. We further propose domain adversarial matrix factorization (DAMF), which minimizes the derived theoretical bound in an adversarial manner. Our theoretical bound and algorithm are independent of the propensity score and thus address the contradiction of the previous propensity-based solutions. Finally, we conduct extensive experiments using public real-world datasets. In particular, we demonstrate that the proposed approach outperforms existing propensity-based methods in terms of rating prediction and ranking performance under a realistic situation where the true propensity score is inaccessible.

2 Preliminaries

Let u ∈ [m] be a user and i ∈ [n] be an item in a recommender system. We also define D := [m] × [n] as the set of all useritem pairs. Let R ∈ Rm×n denote a (deterministic) true rating matrix, where each entry Ru,i represents the real-valued true rating of user u for item i.

Our goal is to develop an algorithm to obtain a better predicted rating matrix (or a hypothesis) ̂R, where each entry ˆRu,i denotes a predicted rating value for (u, i). To this end, we formally define the ideal loss function of interest, which should ideally be minimized to obtain a rating predictor as follows:

where ℓ(·, ·) : R×R → [0, ∆] is a loss function bounded by ∆. For example, when ℓ(x, y) = (x - y)2 , Eq. (1) represents the mean-squared-error (MSE).

In real-life recommender systems, one cannot directly calculate the ideal loss function, as most rating data are missing in nature. To precisely formulate this missing mechanism, we introduce two additional matrices. The first one is the propensity matrix, denoted as P ∈ P, where P represents the space of probability distributions over D. Each of its entries Pu,i ∈ [0, 1] is the propensity score of (u, i), and it represents the probability of the rating feedback being observed. Next, let O ∈ {0, 1}m×n be an observation matrix where each entry Ou,i ∈ {0, 1} is a Bernoulli random variable with its expectation E[Ou,i] = Pu,i. If Ou,i = 1, the rating of the pair is observed, otherwise, it is unobserved. Finally, we use O ∼ P when the entries of O are the realizations of Bernoulli distributions defined by the entries of P . For simplicity and without loss of generality, we assume that M := ∑(u,i)∈D Ou,i hereinafter.

2.1 ExistingMethods

In our formulation, it is essential to approximate the ideal loss function using only observable feedback. Here, we summarize the existing methods to estimate the ideal loss function and discuss their limitations.

Naive Estimator. Given a set of observed rating feedback, the most basic estimator for the ideal loss is the naive estimator, which is defined as follows:

The naive estimator simply averages the loss of user-item pairs with the observed rating feedback (i.e., Ou,i = 1). This is valid when the missing mechanism is MCAR 1 , as it is unbiased against the ideal loss function with MCAR data [Schnabel et al., 2016]. However, several previous studies indicate that this estimator exhibits a bias under general MNAR settings (i.e., E[ ̂ Lℓnaive ] ̸= Lℓideal for some ̂R). This means that the naive estimator does not converge to the ideal loss, even with infinite data. Therefore, one should use an estimator that addresses the bias as an alternative to the naive one [Schnabel et al., 2016].

Inverse Propensity Score (IPS) Estimator. To improve the naive estimator, several previous studies apply the IPS estimation to alleviate the bias of MNAR rating feedback [Liang et al., 2016; Schnabel et al., 2016; Saito et al., 2020; Saito, 2020b; Saito et al., 2021]. In causal inference, propensity scoring estimators are widely used to estimate the causal effects of a treatment from observational data [Imbens and Rubin, 2015]. In our formulation, we can derive an unbiased estimator for the loss function of interest by using the true propensity score as follows:

This estimator is unbiased for the ideal loss (i.e., E[ ̂ LℓIPS ] = Lℓideal for any ̂R) and is more desirable than the naive estimator in terms of bias. However, its unbiasedness is ensured only when the true propensity score is available, and it can have a bias with an inaccurate propensity estimator (see Lemma 5.1 of Schnabel et al. [Schnabel et al., 2016]). The bias of IPS can arise in most real-world recommender systems, because the missing mechanism of rating feedback can depend on user self-selection, which cannot be controlled by analysts and is difficult to estimate [Marlin and Zemel, 2009; Schnabel et al., 2016]. Indeed, most previous studies estimate the propensity score by using some amount of MCAR test data to ensure empirical performance [Schnabel et al., 2016; Wang et al., 2019]. However, this is infeasible owing to the costly annotation process [Joachims et al., 2017]. In addition, this method is valid only when the ratings for some user-item pairs are observed with non-zero probabilities (i.e., Pu,i ∈ (0, 1], ∀(u, i) ∈ D), which is a criterion difficult to verify in practice [Ma and Chen, 2019]. Therefore, we explore a theory and algorithm independent of the propensity score and MCAR data, aiming to alleviate the concurrent issues of the propensity-based methods.

1 A missing mechanism is said to be MCAR if the propenisty score is constant, i.e., Pu,i = C, ∀(u, i) ∈ D. Ensuring that the data is MCAR is extremely difficult, because the users' self-selection as to which items they provide rating feedback is out of our control.

Doubly Robust (DR) Estimator. The DR estimator utilizes the error imputation model and propensity score to decrease the variance of the IPS approach. MF-DR [Wang et al., 2019] optimizes the following DR estimator of the ideal loss.

where ˆ ℓu,i is the imputation model, which estimates ℓ(Ru,i, ˆRu,i). As discussed in [Wang et al., 2019], this estimator satisfies the unbiasedness with the true propensity (i.e., E[ ̂ LℓDR] = Lℓideal ) and often achieves a tighter estimation error bound compared to IPS. MF-DR obtains the final prediction ( ̂R) and the imputation model simultaneously via a joint learning procedure.

However, the proposed joint learning algorithm still requires a pre-estimated propensity score [Wang et al., 2019]. Furthermore, the estimation performance of the DR estimator is significantly degraded when the error imputation model and the propensity model are both misspecified [Dud´ık et al., 2011]. In fact, in the empirical evaluations of [Wang et al., 2019], MCAR test data are used to estimate the propensity score. In the experiments, we validate the performance of the DR estimator in a more practical setting where only MNAR data are available (without any MCAR data).

Causal Embeddings (CausE) The work most closely related to ours is [Bonner and Vasile, 2018], which proposed CausE, a domain adaptation-inspired method to address the selection bias in rating feedback. The loss function of CausE is given as follows:

where β ≥ 0 is a trade-off hyper-parameter. Two prediction matrices ( ̂RMCAR and ̂RMNAR) are for the MCAR and MNAR data, respectively, where ̂RMNAR is used to make the final predictions. The last term represents the regularizer between tasks and penalizes the divergence between the predictions for the MCAR and MNAR data.

This method empirically outperforms propensity-based methods in a binary rating feedback setting [Bonner and Vasile, 2018]. A problem is that this algorithm requires some MCAR data, which are generally unavailable. Moreover, it uses the idea of domain adaptation in a heuristic manner by myopically adding Ωdomain(·); there is no theoretical guarantee for its loss function. Therefore, we explore an algorithm that is preferable to CausE in the following ways: (i) Our algorithm does not use any MCAR data during training, and thus is feasible in a realistic situation having no MCAR training data, (ii) Our proposed method is theoretically refined in the sense that it minimizes the propensity-independent upper bound of the ideal loss function.

3 Proposed Framework and Algorithm

This section derives a propensity-independent generalization error bound for the ideal loss and an algorithm to minimize the bound using only MNAR data.

3.1 Theoretical Bound

First, we define a discrepancy measure to quantify the similarity between two different propensity matrices.

Definition 1. (Propensity Matrix Divergence (PMD)) Let H be a set of real-valued predicted rating matrices and ̂R ∈ H be a specific prediction. The PMD between any two given propensity matrices P and P ′ is defined as follows:

Note that the PMD is well defined because ψ̂R,H(P , P ) = 0, ∀P ∈ P, and it satisfies nonnegativity and subadditivity. Moreover, it is independent of the true rating matrices and can be calculated for any given pair of propensity matrices without true rating information.

We now use ψ̂R,H and derive a propensity-independent generalization error bound for the ideal loss function. 2

Theorem 1. (Propensity Independent Generalization Error Bound) Suppose two observation matrices with MCAR and MNAR mechanisms (OMCAR ∼ PMCAR and OMNAR ∼ PMNAR) are given. For any prediction matrix ̂R ∈ H and

2 Note that the theoretical bounds of all existing studies depend on the cardinality of the hypothesis space |H| [Schnabel et al., 2016; Wang et al., 2019]. This is unrealistic, as |H| is infinite in almost all cases (as the parameter space is continuous). Under a realistic setting with infinite H, therefore, the existing analysis becomes invalid. Thus, we use the Rademacher complexity to consider a realistic situation with infinite hypothesis spaces.

Algorithm 1 Domain Adversarial Matrix Factorization

Input: MNAR observation matrix OMNAR; set of user-item pairs D; trade-off parameter β; regularization parameter λ; batch size B; number of steps k

Output: learnt prediction matrix ̂R= UV ⊤

• 1: Randomly initialize U, V , U ′ , and V ′
• 2: repeat
• 3: Sample mini-batch data of size B fromOMNAR
• 4: for 1, . . . , k do
• 5: Update U and V by gradient descent according to Eq. (9) with fixed ̂R∗ = U ′ (V ′ )⊤
• 6: end for
• 7: Uniformly sample user-item pairs of size B fromD to construct OMCAR
• 8: for 1, . . . , k do
• 9: Update U ′ and V ′ by gradient ascent according to Eq. (8) with fixed ̂R = UV ⊤
• 10: end for
• 11: until convergence;

for any δ ∈ (0, 1), the following inequality holds with a probability of at least 1- δ:

where L is the Lipschitz constant of the loss function and RP,M(H) is the Rademacher complexity of H, which is defined in Appendix A. See also Appendix A for the proof.

The theoretical bound consists of the following four factors: (i) Naive loss on MNAR data, (ii) Empirical PMD, (iii) Complexity of the hypothesis class, (iv) Confidence term that depends on δ. Note that (i) and (ii) can be optimized with only observable data, and (iii) can be controlled by adding a regularization term, as described in the next section. Morevoer (iv) converges to zero as M increases. We will empirically show that the bound is informative in the sense that optimizing (i) and (ii) results in a desired value of the ideal loss function.

3.2 Algorithm

Here, we describe the proposed algorithm. Building on the theoretical bound derived in Theorem 1, we aim at minimizing the following objective:

where β ≥ 0 is the trade-off hyper-parameter between the naive loss and discrepancy measure. Ω(·) is a regularization function that penalizes the complexity of ̂R, and λ ≥ 0 is the regularization hyper-parameter. In addition, we can obtain OMCAR by uniformly sampling unlabeled user-item pairs from D. The objective in Eq. (7) builds on the two controllable terms of the theoretical bound in Eq. (6). Thus, it is independent of the propensity score, and we need not estimate the propensity score to optimize this objective. Note that we add the regularization term to our objective to control the complexity of the hypothesis class H, as it is impossible to minimize the Rademacher complexity directly.

To solve Eq. (7), we empirically approximate ψ̂R,H by solving

This optimization corresponds to accurately estimating PMD from observable data.

Given the aforementioned details, Eq. (7) is now reduced to:

where ̂R∗ is the solution of Eq. (8).

Algorithm 1 describes the detailed procedure of our DAMF, which is based on the matrix factorization (MF) model, where a prediction matrix is defined as the product of user-item latent factors U ∈ Rm×d and V ∈ Rn×d . Given that the predictions are modelled by MF, a possible regularization is Ω( ̂R) := ∥U∥22 + ∥V ∥22 , where ∥ · ∥2 is the L2 norm.

4 Experiments

This section empirically evaluates the proposed method on public real-world datasets. Appendix B describes detailed experimental settings such as dataset description, evaluation metrics, and hyper-parameter tuning. Our code is available at https://github.com/usaito/ijcai2022-adversarial-mf.

4.1 Experimental Setups

Datasets. We use Yahoo! R3 3 and Coat 4 , which separately contain MNAR and MCAR datasets. We randomly selected 10% of the MNAR training set as the validation set, which is used to perform hyper-parameter tuning.

Baseline Methods and Propensity Estimators. We compare our proposed algorithm with the following baselines:

• MF [Koren et al., 2009], which optimizes its model parameters by minimizing the naive loss in Eq. (2) and does not depend on the propensity score.

3 http://webscope.sandbox.yahoo.com/

4 https://www.cs.cornell.edu/˜schnabts/mnar/

Note: The bold font indicates the best performance in each metric and dataset among methods using only MNAR data.

• MF-IPS [Schnabel et al., 2016], which optimizes its model parameters by minimizing the IPS loss in Eq. (3).
• MF-DR [Wang et al., 2019], which optimizes its model parameters by minimizing the DR loss in Eq. (4).
• CausE [Bonner and Vasile, 2018], which minimizes the sum of the naive loss and the domain regularization term Ωdomain(·), which measures the divergence between the MNAR and MCAR data. To calculate its loss function, we sample 5% of the MCAR test data. MCAR data are in general unavailable in real-world settings, and thus we report the results of CausE as a reference.

For MF-IPS and MF-DR, we use user propensity, item propensity, user-item propensity, and 1BitMC [Ma and Chen, 2019] as the variants of the propensity estimator and report the results with the best estimator for each dataset. Note that these four propensity estimators (formally defined in the Appendix) are usable in real-world recommender systems because they use only MNAR data.

We also report the results of MF-IPS and MF-DR with the true propensity score. We follow previous studies [Schnabel et al., 2016; Wang et al., 2019] and calculate this true propensity using 5% of the MCAR test data. Note that the true propensity is unavailable in real-world situations, as it requires MCAR explicit feedback. Therefore, we report the results of MF-IPS and MF-DR with the true propensity score as a reference.

4.2 Results and Discussion

Here, we report and discuss the experimental results with respect to four research questions (RQ1-RQ4). We run the experiments 10 times with different random seeds and report the averaged results in Tables 1-4.

RQ1. How well does the proposed algorithm perform on the rating prediction task? We evaluate and compare the prediction performance of DAMF and the baselines on Yahoo! R3 and Coat. Table 3.2 provides the MSEs and their standard deviations (StdDev). For Yahoo! R3, DAMF reveals the best rating prediction performance among the methods using only MNAR data. Specifically, it outperforms MF-IPS by 26.3% and MF-DR by 26.7% in terms of MSE. For Coat, DAMF outperforms MF-IPS by 5.59% and MF-DR by 6.08%, even though the distributional shift of Coat is significantly smaller than that of Yahoo! R3. Note that it is reasonable to assume that there exists a user-item pair with zero observed probability on Coat. This is because the training set was collected via workers' self-selection, and male workers did not provide the ratings of women's coats and vice versa. Thus, the results also suggest the stability and adaptability of the proposed method to the data with a user-item pair with Pu,i = 0. In contrast, the performance of the propensity-based methods on Coat is not theoretically grounded, as the training and test sets may not overlap.

RQ2. How do propensity-based methods perform with different propensity estimators? Here, we evaluate the sensitivity of MF-IPS and MF-DR to the choice of the propensity estimator. First, consistent with previous studies [Schnabel et al., 2016; Wang et al., 2019], Table 3.2 shows that MF-IPS and MF-DR with the true propensity exhibit better rating prediction performance compared to the other methods. However, Table 3.2 shows that they perform poorly with other propensity estimators, including 1BitMC, and especially for Yahoo! R3. In some cases, they even underperform MF, which is based on the naive loss. Therefore, although propensity-based methods are potentially high-performing with the true propensity, their prediction performances are highly sensitive to the choice of propensity estimator and negatively affected by the propensity estimation bias. These empirical observations imply the propensity contradiction of the previous methods.

RQ3. How well does the proposed algorithm perform on the ranking task? Next, we test the ranking performance of DAMF on Yahoo! R3 and Coat. Tables 3.2 and 3.2 describe the ranking metrics computed on the MCAR test data.

For Yahoo! R3, DAMF demonstrates the best ranking performance among all methods, including the methods with the true propensity score. It outperforms MF-IPS by 3.39% and MF-DR by 4.15%, MF-IPS (true) by 6.04%, and MF-DR (true) by 3.61% in NDCG. The results suggest that DAMF is powerful and useful for improving the recommendation quality and user experience with only biased rating data. Moreover, DAMF is the best in Coat, improving MF-IPS by 3.48%, MFDR by 1.94%, MF-IPS (true) by 1.10%, and MF-DR (true) by 1.32% in NDCG. These results demonstrate that the proposed method works satisfactorily in the ranking task even when the dataset size is small and the degree of bias is not significant.

RQ.4 Does adversarial learning really minimize the ideal

loss? Finally, we investigate the validity of minimizing the propensity-independent upper bound in Eq. (6) as a solution to minimize the ideal loss function in Eq. (1) using only MNAR data. Figure 1 depicts the sum of the first two terms of the upper bound (blue) and ideal loss (orange) during the training of DAMF on Yahoo! R3 and Coat. First, it is evident from the figures that our adversarial learning procedure effectively minimizes the upper bound of the ideal loss during training. Moreover, the figures suggest that the ideal loss function is Note: Performances relative to the true propensity score are in parentheses. The result suggests that the performances of MF-IPS and MF-DR using only MNAR data are significantly worse than the performances of those using the true propensity.

Note: The bold font indicates the best performance in each metric and dataset among methods using only MNAR data.

also minimized well by our method. These results demonstrate that minimizing the theoretical upper bound in Eq. (6) is a valid approach for improving the recommendation quality on the MCAR test set.

5 Conclusion

We explored the problem of offline recommender learning from only MNAR explicit rating feedback. To this end, we derived the propensity independent generalization error bound of the loss function and proposed an algorithm to minimize the bound via adversarial learning. Our algorithm enables an accurate rating prediction without estimating the propensity score, thereby resolving the propensity contradiction of the existing literature. Extensive experiments demonstrate the advantages of the proposed framework in terms of rating prediction and ranking measures when true propensities are inaccessible.

Our work represents an initial attempt for offline recommender learning via adversarial training, and there are still many problems to study in this direction. For example, our theory leads to a propensity-independent upper bound of the (ideal) rating prediction loss. It would be valuable to construct a corresponding theory for the ranking task, such as showing the propensity-independent upper bound of the additive

(b) Coat

Figure 1: Theoretical Upper Bound and Ideal Loss Function during DAMF Training.

ranking metrics. Moreover, testing our method in an online experiment will support the reliability of our framework. We leave the investigation of these directions for future studies.