Reinforced Negative Sampling for Recommendation with Exposure Data

1 Introduction

The prevalence of implicit feedback has boosted the research and development of implicit feedback-based recommender systems [Bayer et al., 2017; Yang et al., 2018]. The key challenge in learning from implicit feedback lies in the natural scarcity of negative signal, known as one-class problem [Pan et al., 2008]. To address this issue, negative sampling has been widely adopted in previous works [Rendle et al., 2009], where the common approach is to uniformly sample negative instances from the missing data (i.e., the unobserved interactions) [Jiang et al., 2018; He et al., 2018; Lin et al., 2019]. This process, with no doubt, plays a critical role in training recommender models from implicit feedback.

Given the importance of designing a quality negative sampler for implicit recommender models, two types of methods have been proposed in previous works. The first is heuristicbased methods, including dynamic negative sampling (DNS) that oversamples the hard negative instances during the training process [Zhang et al., 2013; Rendle and Freudenthaler,

2014], and frequency-based sampling that subsamples frequent instances [Caselles-Dupr´e et al., 2018]. The other type is auxiliary information-based methods, which focus on choosing more reliable negative instances by leveraging the auxiliary data such as clicked but non-purchased items in Ecommerce websites [Ding et al., 2018a].

In real-world scenarios, platforms can easily collect whether the recommended (i.e., exposed) item has been interacted by a user. These records, also referred to as the exposure data, contain rich information about the negative preference of users. However, due to the inaccessibility of such data by the third parties, previous academic research exploits the interaction data only to build the negative sampler. As a result, the reliability of the generated negative instances is questionable. Nevertheless, it is non-trivial to integrate the exposure data into the negative sampler design because of the following challenges:

• Incompleteness of negative preference in exposure data. The exposed items are typically selected by a recommendation engine. Besides the exposed but non-interacted items, other non-exposed items can also be the negative preference for a user. If the sampler simply generates negative instances according to the exposure data, it will cause selection bias, making the model under-trained and resulting in suboptimal performance [Lian et al., 2017; Ding et al., 2018a].
• Difficulty of optimizing the negative sampler. Due to the discrete sampling process on item IDs, the objective function is non-differentiable. As such, it cannot be optimized with traditional gradient-based techniques that can only deal with continuous functions.

In this work, we design a novel embedding-based sampler model named Reinforced Negative Sampler (RNS) that learns to generate informative and effective negative samples. Specifically, the sampler collaborates with another embedding-based recommender model, supplying negative instances for the recommender to do pairwise learning. The sampler has two goals - generating hard and real negative instances. The hard goal is achieved through adversarial training between the recommender and the sampler. Simultaneously, the sampler is also rewarded to generate negative instances that overlap with the non-interacted instances in the exposure data. Corresponding to aforementioned two challenges, here the "reinforced" has two-fold meaning. First, the generation of real negative instances is reinforced by a feature matching technique, which forces the empirical distribution of the generated and the exposed negative instances to have matched moments in the latent feature space. Second, we consider a reinforcement learning setting in the sampler so as to receive gradient information from the recommender and optimize the non-differentiable exposure-based objective.

We summarize the contributions of this paper as follows.

1. We are the first to consider generating exposure-alike negative instances for implicit recommendation. The proposed RNS model is general in optimizing any recommender models, with the potential of large impact.
2. We propose two specific designs to generate high-quality negative instances, including the adversarial training for hard negatives and the feature matching for generating exposure-alike negatives that are more reliable.
3. We conduct extensive experiments on two real-world datasets to demonstrate the effectiveness of RNS. More ablation studies verify the efficacy of the two designs and the utility of feature matching in leveraging exposure data.

2 Methodology

We start by introducing some basic notations. For a specific user u, Cu denotes the set of items that are interacted by u, while Eu refers to those non-interacted items within u's exposure history. We represent matrices, vectors, and scalars as bold capital letters (e.g., X), bold lower-case letters (e.g., x), and normal lower-case letters (e.g., x), respectively. We use symbols σ and ⊙ to denote the sigmoid function and elementwise production, respectively.

Our proposed recommender-sampler framework is illustrated in Figure 1. The sampler (S) calculates a probability distribution over a set of candidate negative instances, then samples one of them as the output. Next the recommender (R) is optimized to learn the pairwise ranking relation between a ground truth instance and a generated negative one. After receiving the multiple reward signals, S is encouraged to generate both hard (ω1uj ) and real (ω2uj /ω3uj ) negative instances. During training process, R can benefit more from the better quality negative instances and thus perform better on predicating user preference.

2.1 The Recommender Model (R)

To learn recommender models from implicit feedback, Rendle et al. [Rendle et al., 2009] proposed the Bayesian Personalized Ranking (BPR) method, which assumes that a positive instance should be predicted with a much higher score over the negative one. Based on BPR, the training objective of R can be formulated as minimizing the following loss function:

In (1), for each user u, the predicted preference score on items is denoted as ˆ ru·(Θ), where Θ refers to the model parameters. The negative instance j is generated by the sampler (S) according to a conditional distribution ˆΨS(·|u), while the positive instance i is randomly chosen from ground truth set Cu. Minimizing LR is equivalent to maximizing the margin between ˆ rui and ˆ ruj, which encourages R to learn the pairwise ranking relation of user preference between i and j.

To calculate ˆ ru·(Θ), we adopt the Generalized Matrix Factorization (GMF) [He et al., 2017] model that allows different dimensions of the embedding space to have different weights. Specifically, it first uses an element-wise product to obtain an interacted feature vector, and then project the feature vector to an output score with a weight vector as follows, ˆ rui(Θ) = hrT fui = hrT (pru ⊙ qri ), where hr ∈ RK×1 denotes the learnable weight vector and fui denotes the interacted feature vector. The K-dimensional user embedding and item embedding are represented as pru and qri , respectively. Based on GMF, the model parameters Θ is {pru , qri , hr }.

2.2 The Sampler Model (S)

We first introduce two specific design of our proposed reinforced negative sampler (RNS), corresponding to generating hard and real negative samples. Then we train RNS through policy gradient in reinforcement learning (RL) setting.

Adversarial Sampler

Intuitively, S can generate adversarial negative instances that have high scores ˆ ru·, which are hard for R to rank correctly. Therefore, the objective of this adversarial sampler is formulated as maximizing the expectation of j-related part in LR:

Note that we have left out the logarithm to control its values within [-1, 0]. By this means, the generated negative instances are given higher prediction scores by R, being more close to those of positive instances, which provides larger gradients and more information for R.

Exposure-matching Sampler

As both users' interaction and non-interaction are explicitly recorded in the exposure data, it is reasonable to generate real negative samples based on the exposed but not interacted instances. Therefore, our second design of RNS is introducing an exposure-matching sampler that learns a probability distribution to match negative signal in exposure data. Given u's exposed itemset Eu, a direct design is to maximize the overlap between the set of generated instances and Eu. Specifically, we consider the following objective:

where the binary indicator function 1Eu serves as a guiding signal, encouraging S to generate a set of negative instances that has a big overlap with exposed itemset Eu.

However, for the set of generated negative instances and the set of exposed instances, L0ES measures their distance by the size of overlapping set, i.e., a simple scalar, which does not provide information in latent feature level and thus be suboptimal. Consequently, the sampler trained with this objective may tend to choose exactly the same instances from the exposure data, which will harm the performance as not all of the exposed instances are beneficial.

Therefore, we further measure the similarity in the latent feature space. As we adopt GMF to calculate preference scores in R, for a user-item pair denoted as (u, i), the interacted feature vector fui is the corresponding representation in the latent feature space. Consider a subset of generated negative instances Gs, for each (u, j) ∈ Gs, we sample a (u, k) from Eu and group all these sampled instances into a subset denoted as Es. Then, to measure the distance between Gs and Es, we consider the maximum mean discrepancy (MMD) between the empirical distribution of feature vectors in these two subsets [Li et al., 2015; Zhang et al., 2017]. Concisely, MMD measures the mean squared difference between two sets of samples over a universal reproducing kernel Hilbert space. In our case, the MMD for two empirical distributions of f in Gs and Es is given by

where L is the size of two sets and k(·, ·) : RK ×RK ↦→ R is the kernel function. Here we use a universal Gaussian kernel, i.e.,, k(x, x′ ) = exp(-||x - x′ ||2 /2τ ) with bandwidth τ , and minimize MMD to match all moments of two distributions.

From the above considerations, we design the exposurematching sampler with a weighted sum of overlap-based objective and MMD-based objective. Mathematically, it can be formulated as maximizing

where β controls the importance of MMD-based objective M(u, j) that aims to match the feature distribution. As the MMD is calculated between two sets, i.e., Gs and Es, for each u and u's generated negative instance j, M(u, j) only refers to those corresponding terms in (4), which is given by

Training with Reinforcement Learning

Finally, combining the above two specifically designed sampler together, we obtain the following objective for the negative sampler (S):

where {ω1uj , ω2uj , ω3uj } refer to adversarial objective, overlapbased objective and MMD-based objective, respectively (See (2) and (5)). By maximizing LS, S is encouraged to generate both hard and real negative samples with exposure data.

However, unlike the optimization of R that can be achieved by the stochastic gradient descent (SGD), training S has following two problems. First, it involves a discrete sampling step, which makes simple differentiation infeasible. Second, the exposure-aware indicator function 1Eu is nondifferentiable. Therefore, for S with model parameters Φ, we use the policy gradient based RL [Sutton et al., 2000] to derive its gradient:

where we approximate the expectation with sampling in the last step. With the RL terminology, the agent, i.e., the sampler S, follows a policy ˆΨS(j|u) and takes an action as generating a negative instance j for a certain user u. Then, for each action (u, j), the environment, i.e., the recommender R, will return a reward ωuj to S that guides the direction of optimization. In this way, S is iteratively optimized towards maximizing the returned reward, i.e., generating the negative instances that are both hard and real.

To produce the probability distribution for sampling negative instances, i.e., ˆΨS(j|u), S first calculates the scores for a set of negative candidate instances and then obtain their corresponding softmax probability. Similar to R, S also uses GMF to calculate the score with model parameters Φ = {psu , qsi , hs }. Mathematically, ˆΨS(j|u) is modeled as

where ˆ su·(Φ) denotes the score and Nu denotes u's candidate set for the generated negative instances. Intuitively, Nu should contain all the instances that are not interacted by u, i.e., Cu. However, as the hard negative instances are very likely to be those unobserved positive instances, we generate Nu by uniformly preselecting Ns instance from Cu.

The overall training process is summarized in Algorithm 1. Both R and S require pre-training, which is achieved by training the GMF model with BPR objective. The learning process is carried out in mini-batch mode, where R and S alternatively update their parameters.

Algorithm 1: The RNS algorithm.

Data : Interaction data C = {(u, i)}, exposure data E; Input : Pre-trained recommender R0 with parameters Θ, Pre-trained sampler S0 with parameters Φ; Output: The final recommender R for prediction; 1 while Stopping criteria is not met do 2 Sample a mini-batch of data Cs from C 3 for (u, i) ∈ Cs do 4 Uniformly sample Ns negative instances as Nu; 5 Obtain their sampling probability {ˆΨ} by (9); 6 S generate a negative instance j ∈ Nu with {ˆΨ}; 7 GR ← GR + ∇ΘLR(u, i, j); // R's gradients 8 Gs.add((u, j)); // the set of generated instances 9 Sample one exposed instance j ′ from Eu, Es.add((u, j ′ )); // used for calculating MMD 10 end 11 for (u, j) ∈ Gs do 12 Calculate reward ωuj by (2)-(7); 13 GS ← GS + ωuj∇Φ log ˆΨ(j|u); // S's gradients 14 end 15 Θ←Θ+λRGR, Φ←Φ+λSGS; // update R, S 16 end

2.3 Discussion

Our proposed recommender-sampler framework follow the general design of Generative Adversarial Networks [Goodfellow et al., 2014], which contains two parts, the generator and the discriminator. In recommendation fields, the previous GAN-based models, such as IRGAN [Wang et al., 2017], CFGAN [Chae et al., 2018] and AdvIR [Park and Chang, 2019], focuses on training a better generator to deceive the discriminator. In this sense, their generator is optimized to generate the positive instance and thus can predict user preference. However, in our work, the sampler generates the negative instances to train a better recommender as prediction model. The most related work is KBGAN [Cai and Wang, 2018] that generates hard negative instances to train better knowledge graph embeddings. However, our RNS model not only has an adversarial sampler, but also tries to generate real negative instances with exposure data.

3 Experiments

3.1 Experimental Settings

Datasets. We perform experiments on two real-world datasets with both interactions and exposure:

• Beibei 1 is one of the largest Chinese E-commerce websites. We sample a subset of data that contains item clicks and exposure within the time period from 2017/06 to 2017/07.
• Zhihu 2 is the largest question-and-answer website in China, where users click articles of interest to read. Here we use a public benchmark released in CCIR-2018 Challenge 3 .

Preprocessing. In the raw data of Beibei and Zhihu, each user's records are grouped into different sessions, during which the user is recommended with a fixed number of items and only clicks some of them. Therefore, we consider a session-based data preprocessing with three steps. First, we filter out the repetitive clicks after the earliest one, as we aim to recommend novel items. Second, we only retain those unclicked items in the exposure data. Third, we filter out users and items with less than 4 (Beibei) and 6 (Zhihu) sessions to overcome the problem of high sparsity of raw datasets.

Evaluation methodology. As the exposure and clicks are grouped into sessions, we adopt an evaluation protocol similar to leave-one-out [Rendle et al., 2009], where the click interactions in the latest session of each user are held out for testing. For hyper-parameters tuning we further hold out the latest session from each user's training data as the validation set. Table 1 summarizes the statistics of experiment datasets. For the metrics, we employ Area Under the Curve (AUC) and Normalized Discounted Cumulative Gain (NDCG) on the ranking of a list of testing items for a user. We fix the list length as L and newly add some unclicked items into a user's list if it is less than L, and it is set as 40 and 160 for Beibei and Zhihu, respectively, which are the same as those in raw data. In this way, both AUC and NDCG equal to 1 when all the clicked items are ranked higher than other unclicked items. Finally we report the average score of all users.

Baselines. We compare our proposed RNS method with three groups of the baselines.

First we consider two common baselines:

• ItemPop. This method ranks items base on their popularity, as judged by the number of click interactions.
• BPR-GMF [Rendle et al., 2009]. BPR optimizes the MF-based model with a pairwise ranking loss to learn from implicit feedback.

For methods related to the adversarial sampler, we choose:

• BPR-DNS [Zhang et al., 2013]. Dynamic Negative Sampling (DNS) selects the item with the highest prediction score among X randomly sampled negatives.
• KBGAN [Cai and Wang, 2018]. With the generator serving as an adversarial sampler, KBGAN can be considered as a soft version of DNS. Here we combine it with BPR objective.

1 http://www.beibei.com/

2 https://www.zhihu.com/

3 https://biendata.com/competition/CCIR2018/

• IRGAN [Wang et al., 2017]. This method is a GANbased IR model that aims to obtain a better generator through adversarial training, which is used to predict user preference.

Finally, we consider two exposure-enhanced samplers:

• BPR-EN. This method selects negatives only from exposure data. We use it to investigate the impact of selecting negatives from an incomplete candidate set.
• EBPR. Similar to [Ding et al., 2018a], we consider to weight those exposed but unclicked items differently (compared with other unexposed items) when choosing negatives.

Parameter settings. For above baselines, we use GMF as scoring model and explore hyper-parameters similarly as the original paper. The mini-batch size and embedding size for all methods are set as 1024 and 32, respectively. We search L2 regularizer and learning rate in [10-6 ,10-5 ,10-4 ,10-3 ,10-2 ] and [0.0001, 0.0005, 0.001, 0.05, 0.1], respectively, and use Adam optimizer for learning. In addition, the size of negative candidate set, i.e., Ns, is set as 100 and 30 in Beibei and Zhihu, respectively, which is optimal among [10, 20, ..., 150].

3.2 Performance Comparison

Table 2 displays the recommendation performance w.r.t. AUC and NDCG on two datasets, where we perform paired t-test between RNS and each of baselines over 10-round results.

From above results, we have the following observations:

• RNS significantly improves the recommendation performance by training with the high quality negative instances. Compared with ItemPop and BPR-GMF, our proposed RNS outperforms the best of them by 1.46% and 2.81% in AUC and NDCG for Beibei and by 2.51% and 2.79% in AUC and NDCG for Zhihu. It demonstrates that generating better quality negative instances is vital for learning user preference among different items.
• RNS further improves the generation of hard negative instances by integrating exposure information. We can observe that our proposed RNS achieves the best performance compared to those using the adversarial sampler. For Beibei, it improves the AUC and NDCG by 0.60% and 1.20%, while the improvement is much larger for Zhihu, i.e., 1.97% and 1.91%. Compared with these baselines that simply choose hard negative instances based on the model's own inference, RNS use previous exposure information as the guiding signal to
• find more reliable negative instances, which explains the above performance improvement. Besides, we observe that BPR-DNS with a rather straightforward design consistently outperforms KBGAN and IRGAN, which may be due to the difficulty of learning an accurate distribution within a large item space (104 ∼ 105 ).
• RNS better leverages negative preference signal in exposure data. Corresponding to our aforementioned challenge, we observe the significant performance degradation with a naive exposure-enhanced sampler. For BPR-EN that, as a common practice in most companies, selects negative instances only from the exposure, RNS outperforms it by 17.55% and 23.74% in AUC and NDCG for Beibei and similarly for Zhihu. As for EBPR, the relative improvement of RNS is 3.02% and 4.24% in AUC and NDCG for Beibei and 1.45% and 1.47% in AUC and NDCG for Zhihu. With our designed feature matching scheme, RNS can generate exposure-alike negatives from a much larger space that are not limited to exposure data, avoiding the incompleteness of negative preference in exposure data. This explains the observed outperformance of RNS.

To summarize, these comparisons verify that our proposed RNS model can effectively generate both hard and real negative instances to train a better implicit recommender model.

3.3 Hard Negative v.s. Real Negative

In RNS, we combine the adversarial sampler (AS) and exposure-matching sampler (ES) together so as to improve the quality of generated negative instances. An intuitive question is whether the designed two parts can really help?

To answer it, we conduct experiments on two degenerative methods of RNS, in which only the adversarial objective LAS and the exposure-matching objective LES are considered in sampler, respectively. We adopt the same evaluation method with above experiments, and the performance comparison is shown in Table 3, along with the value of weighting parameters for LES and MMD-based objective, i.e., α and β. By comparing with BPR-GMF, we observe that both AS part and ES part play an essential role in RNS. Comparatively, generating negative instances that matches the exposure data (RNSES) is more helpful than generating hard negative instances through adversarial learning (RNS-AS). As these two samplers capture different signals, our experiments demonstrate that unifying them can achieve further improvement.

3.4 Impact of Feature Matching Scheme

Here we investigate whether the designed feature matching scheme helps generating exposure-alike instances, by conducting experiments on RNS-ES that only retain the exposure-matching objective. Figure 2 shows the recommendation performance with respect to different β. We can clearly observe that increasing β from 0.0 to 0.9 can effectively improve the NDCG. More specifically, it increases from 0.3986 to 0.4060 (+1.86%) and 0.6555 to 0.6605 (+0.76%) on Beibei and Zhihu, respectively. As β denotes the weight of MMD-based objective for the feature matching, a peak with large value (0.8∼0.9) highlights the advantage of our proposed feature matching scheme.

To further illustrate its advantage, we randomly select two subsets of generated and exposed instances on Beibei, 1000 each, and visualize their interacted feature vectors before (β = 0.0) and after (β = 0.9) feature matching in Figure 3(a) and (b), respectively, via t-SNE. With red points as the exposed instances, blue points as the generated instances and green points as those overlapped ones, we observe a much more similar distribution in Figure 3(b) . On the one hand, the generated negatives (blue) are much closer to exposed ones (red) when β = 0.9, while they are densely gathered in a small area near (0, 0) when β = 0.0. On the other hand, the number of overlapped instances (green) decreases significantly with β increasing from 0.0 to 0.9. To measure the similarity between two sets of generated and exposed instances, we calculate two metrics of overlap and MMD and illustrate them in Figure 3(c) and (d), where the smaller value of both overlap and MMD can be observed with β = 0.9. This finding is interesting and insightful, implying that the proposed feature matching scheme encourages the sampler to focus on generating the negative instances that are similar to exposed instances in the feature space, rather than choosing exposed instances directly. By this means, although the overlap between generated negatives and exposure data is small, they are more similar in the distribution perspective (small MMD).

4 RelatedWork

Generating adversarial samples for recommendation. A typical approach is the dynamic negative sampling strategy that generates hard negative instances to construct informative item pairs during the training process [Zhang et al., 2013; Zhang et al., 2019a]. Recently, GAN-based approach has also been adopted in training better recommender models with adversarial instances [Wang et al., 2017; Chae et al., 2018; Park and Chang, 2019]. As we discussed in methodology section, our RNS model differs from them by generating both hard and real negative instances with exposure data.

Recommendation with exposure data. There exists no previous work on training a better negative sampler with user exposure. Most works use probabilistic approach to model user exposure as a latent variable and infer its value from interaction data [Liang et al., 2016] or social relationship [Chen et al., 2019]. Previous recommendation works using exposure data are not related to user preference learning. Lee et al. [2014] propose a re-ranking approach based on items' historical exposure. Zhao et al. [2018] investigate reasons behind user inaction. In contrast, our RNS improves the performance by leveraging the negative preference information existed in exposure data, which cannot be simply integrated like other auxiliary information in multiple feedback recommendation [Ding et al., 2018b; Gao et al., 2019].

5 Conclusion and FutureWork

We study the problem of learning to sample negative instances for recommendation from exposure data, rather than manually designing sampling heuristics. To generate both hard and real negatives, we propose a RNS model that combines adversarial training and feature matching together, which is trained with RL method. With these designs, RNS can not only achieve higher accuracy, but also be applied to any recommender systems with negative sampling. In the future, we plan to learn more general negative samplers for social-aware or context-rich recommender systems [Lin et al., 2019; Zhang et al., 2019b], and other related fields such as network embedding and NLP.

Acknowledgements

This work was supported in part by the National Nature Science Foundation of China under 61861136003, 61621091 and 61673237, Beijing National Research Center for Information Science and Technology under 20031887521, and research fund of Tsinghua University - Tencent Joint Laboratory for Internet Innovation Technology.