Improving Implicit Recommender Systems with View Data

1 Introduction

Recent research on recommendation has shifted from explicit ratings [Koren, 2010] to implicit feedback, such as purchases, clicks, and watches [Bayer et al., 2017]. Distinct from explicit feedback like ratings, in implicit feedback data, the negative signal about user preference over items is naturally scarce, resulting in a one-class learning problem [Pan et al., 2008; Zhao et al., 2015a]. Therefore, to learn from implicit feedback, it is crucial to account for both observed and missing data. A state-of-the-art MF method for implicit feedback is the eALS [He et al., 2016], which treats all missing data as the negative feedback but with a lower weight. This wholedata based formulation has been shown to be superior to the prevalent sampling-based method [Rendle et al., 2009] that models partial missing data only.

In an online information system, in addition to the primary feedback data that is directly related with the business KPI, there are also other kinds of user feedback data available [Pan et al., 2015; Tang et al., 2016; Ding et al., 2018]. For example, in E-commerce sites, a user must view a product (i.e., click the product page) before purchasing it. This kind of view data provides valuable signal on user preference, which can complement the purchase data in two folds. First, if a user views an item, regardless of whether purchasing or not, it at least reflects that the user is interested in the item (i.e., positive signal, compared to the non-viewed items). Second, if a user views a product but does not purchase it afterward, it means that the item is of less interest to the user (i.e., negative signal, compared to the purchased items). As such, view data can be seen as an intermediate feedback between purchase and missing data, which enriches the two-level implicit feedback with multiple levels that better distinguish user preference. In this work, we aim to integrate the valuable view data into the state-of-the-art eALS method, so to enhance the performance of implicit recommender systems.

Nevertheless, it is non-trivial to integrate such intermediate feedback into eALS, which is designed for learning from binary 0/1 data only. Specifically, it performs regression by treating purchased interactions as having a label of 1, and other missing interactions as having a label of 0. While an intuitive solution to assign the view interactions with an "intermediate label", i.e., a value between 0 and 1, it is difficult to set a proper value for each interaction. Setting a uniform value for all intermediate interactions oversimplifies the problem, which is sub-optimal or may even adversely degrade the performance if the value is set improperly.

In this work, we make a novel technical contribution in integrating intermediate feedback into eALS. Instead of assigning a specific label value to do point-wise learning, we propose a new solution that models the relative preference orders among different interactions. Specifically, to encode the twofold semantics of view data, we consider the pairwise ranking relations between 1) purchased and viewed interactions, and 2) viewed and non-viewed interactions. The idea is to regularize eALS by enforcing that the predictions of a user over purchased items should be larger than that of viewed items; and the same regularization applies to viewed and non-viewed items. Despite soundness, this solution poses strong challenges to the learning efficiency. In particular, the large number of non-viewed interactions (i.e., missing entries) makes even point-wise regression over them become unaffordable [He et al., 2016], not to mention the pairwise comparisons between viewed and non-viewed interactions. To make the learning tractable, we develop a fast algorithm that leverages the bilinear structure of MF to achieve speedups. Through rigorous mathematical analysis, we identify computational bottlenecks in optimization, and resolve the bottlenecks via clever designs of memoization strategies.

We summarize the contributions of the paper as follows.

1. We improve implicit recommender systems by incorporating view data, proposing a View-enhanced eALS (VALS) method that models the pairwise relations among purchased, viewed, and non-viewed interactions.
2. We propose a fast algorithm that solves the challenging VALS problem with a controllable time complexity that is determined by the number of observed interactions only.
3. We conduct extensive experiments on two real datasets, demonstrating that our method outperforms state-of-the-art view-aware recommender systems by a large margin.

2 RelatedWork

To improve implicit recommender systems with multiple feedback, two types of methods have been proposed.

Model-based. A typical method of this type is collective matrix factorization (CMF), which performs multiple relational learning by sharing information between models of different feedback [Singh and Gordon, 2008; Cheng et al., 2014; Yuan et al., 2014]. While CMF is originated for explicit rating prediction, it has been extended for implicit recommender systems as well [Krohn-Grimberghe et al., 2012; Zhao et al., 2015b; Cao et al., 2017]. However, as CMFbased model generates different user-item relations, i.e., latent factors, for each type of feedback, it is hard to differentiate their preference levels. In contrast, our VALS method learns the same user-item relation to indicate relative preference order among purchase and view data, which is more effective.

Learning-based. Several other methods integrate multiple types of feedback in the negative sampler of BPR [Lerche and Jannach, 2014]. Specifically, Multi-channel BPR (MCBPR) assigns different preference levels to different types of user feedback. Then, in the training process, it samples the item pairs based on these preference orders [Loni et al., 2016]. A recent proposal also performs biased sampling from viewed but non-purchased items and observes significant performance improvements [Ding et al., 2018]. However, these BPR-based solutions still suffer from the shortcomings of sampling-based methods, i.e., degradation on both performance and fidelity, as well as an expensive tuning on learning rate. Our VALS method differs from them by integrating different preference levels based on whole-data based learning strategy. To our knowledge, VALS is the first attempt to exploit different preference levels of implicit feedback in whole-data based MF methods.

3 Preliminaries

We start by introducing some basic notations. For a user-item interaction matrix R ∈ RM×N , M and N denote the number of users and items, respectively, R denotes the set of useritem pairs that have interactions. For a specific user u, vector pu ∈ RK denotes the K-dimensional latent feature vector, and set Ru denotes the set of items that are interacted by u. Similarly, for an item i, notations qi and Ri are used. Matrices P ∈ RM×K and Q ∈ RN×K denote the latent factor matrix for users and items. The standard MF is used as the predictive model. Mathematically, each entry rui of R is estimated as ˆ rui =< pu , qi >= pTu qi .

To learn user/item latent factors, [He et al., 2016] developed an eALS method that introduces a weighted regression function, which assigns a zero rui value to missing entries with a confidence variable:

where ωui denotes the weight of entries (u, i) ∈ R. Determined by an item popularity-aware weighting strategy, si denotes the confidence that item i missed by users is a true negative assessment.

The above problems can be solved using ALS-based technique by iteratively optimizing each coordinate of the latent vector, while leaving others fixed [Liu et al., 2016]. The time complexity is O((M + N)K2 + |R|K) for one iteration, which approaches SGD method ∼ O(|R|K) when (M +N)K and |R| are close. Due to space limit, we leave out the update rule for user/item factors [He et al., 2016].

Since eALS learns latent factors from the whole missing data, it not only can retain model's fidelity but also achieves higher accuracy than the sampling-based methods that sample negative instances from missing data. Considering these advantages, we choose to develop a view-enhanced whole-data based method based on this framework (details in Section 4).

4 Our View-enhanced eALSMethod

Based on eALS, we consider how to effectively learn user preference from both purchase and view data. First of all, in order to differentiate their preference levels using the same user-item relation, we consider the pairwise ranking order between a viewed item and purchased (or non-viewed) item in the objective function. More specifically, we use two margins to describe the intermediate preference level of user's viewed interactions, which is lower than purchased ones but higher than non-viewed ones. On the other hand, introducing the above pairwise relationship in view-enhaced objective function makes the original eALS learning elgorithm become N times slower, which is unsuitable for large-scale data. Therefore, we further develop a fast VALS learning algorithm to efficiently optimize the view-enhanced objective function. For readability, we summarize the major notations throughout the paper in Table 1.

4.1 View-enhanced Objective Function

In E-commerce recommender systems, besides the purchases as the primary feedback that is directly related to optimizing the conversion rate, the view logs of users can be intuitively treated as the intermediate feedback between the purchased and missing data. Therefore, for user u's viewed item v, it should have an intermediate value of prediction ˆ ruv between those of non-viewed item j (i.e., missing entry) and purchased item i, i.e., ˆ ruj and ˆ rui. However, it is difficult to choose an appropriate ˆ ruv for different users. To solve this problem, instead of assigning a uniform value ruv for ˆ ruv to optimize, like the normally used squared loss (ruv-ˆ ruv)2 , we consider the pairwise ranking between the ˆ ruv and the predictions over other items, including ˆ ruj and ˆ rui. By this means, we are able to differentiate the preference levels between view feedback and others, in a more accurate and flexible way.

Our view-enhanced objective function is then designed as:

Note that this objective function can be divided into three terms, where the first two represent the prediction error and regularizer in the former eALS solution, while the last Lview term describes the intermediate preference level of the view signal. For u's viewed item v, the pairwise ranking between v and another purchased item i or non-viewed item j is achieved through a margin-based loss. More specifically, prediction ˆ ruv is optimized to be lower than ˆ rui with a margin namely γ1, as indicated by (γ1 - (ˆ rui - ˆ ruv))2 term. Similarly, ˆ ruv is optimized to be higher than ˆ ruj with another margin namely γ2. For each (u, v), N - |Vu| terms are considered in pairwise ranking loss, which has a total time cost of O(|V|(N-|Vu|)). The sum of each (u, v)'s loss is aggregated with an v-dependent weight namely cv, which indicates the weight of view data in L. By varying margin values (γ1,γ2), we are able to control possible scoring range of predictions over viewed items, and thus search the best preference level for view signal. Without loss of generality, we only consider those viewed but not purchased items, indicating R∩V = φ.

4.2 Fast Learning Algorithm

As we mentioned above, the pairwise ranking loss between a viewed item and another one introduces nearly |V| · N terms in Lview of Eq. (2), making the time cost become N times more if we directly use the original eALS method [He et al., 2016]. To overcome this efficiency challenge, we develop a fast VALS learning algorithm that can speed-up this learning process by avoiding massive repeated computations in Lview. We detail this for user latent factors, while the counterpart for item factors can be achieved likewise and thus is omitted due to space limitation.

First, following the idea of ALS technique, the user u's f th latent factor is updated by setting ∂L/∂puf to 0, while the others are fixed. Since L = LeALS + LReg + Lview and the speed-up strategies of LeALS and LReg have been discussed in [He et al., 2016], we only present the speed-up of Lview term. According to Eq. (2), we obtain the derivative of Lview w.r.t. puf :

where ˆ rfu· = ˆ ru· - pufq·f , i.e., the prediction without the component of latent factor f. Clearly, the bottleneck lies in the (4), (6) and (8) terms that contain summations over item pairs (v, j), introduced by the pairwise ranking between viewed items and non-viewed items. It takes O(|Vu|(N - |RVu|)) time for a raw implementation. To solve this inefficiency issue, we first break down the summations over item pairs into two independent summations over one item index only, which reduces the time complexity into O(N-|RVu|). Then, we further apply memoization strategy to avoid the massive repeated computations on non-viewed item j, achieving an efficient learning in O(|RVu|+K) time.

We detail above process by focusing on the (6) term in ∂Lview/∂puf , as the rest can be done likewise. More specifically, we can obtain

By this reformulation, we observe that each term above can be factorized as two parts that are only dependent on one item index, i.e., viewed item v or non-viewed item j. Then, the original summation over item pairs (v, j) can be broken down into two independent summations. As the summation over v takes O(|Vu|) time, the current bottleneck falls onto those jdependent summations, which require a traversal of the whole negative space, taking near O(N) time. Therefore, we move forward to speed up the calculation of these terms,

As shown above, the major computation lies in ∑Nj=1 qjk and ∑Nj=1 qjkqjf terms, which are independent of u. Therefore, when updating the latent factors for different users, it is unnecessary to repeatedly compute these terms.

We define Dq cache as Dq = ∑Ni=1 qi , and Eq cache as Eq = ∑Ni=1 qiqTi , which can be pre-computed and used in updating the latent factors for all users. Based on these two caches, Eq. (10) can be further evaluated as:

which can be done in O(K + |RVu|) time.

Overall, Eq. (9) can be calculated efficiently with the help of Dq and Eq caches. As for the rest terms of ∂Lview/∂puf , we can apply the same strategy of breaking down and memoizing summations to calculate them in O(K + |RVu|) time. Combining with previous solution of ∂(LeALS+LReg)/∂puf , the time complexity for updating puf is still O(K + |RVu|).

Similarly, for updating item latent factors, we can also achieve the time complexity of O(K + |RVi|) by applying the above speed-up strategy. Algorithm 1 summarizes the accelerated algorithm for our VALS learner. Note that solving ∂(LeALS+LReg)/∂puf and ∂(LeALS+LReg)/∂qif uses the original eALS method. Overall, one VALS iteration takes O((M + N)K2 + (|R| + |V|)K) time, which only depends on the number of observed interactions.

Note that some previous works [Tak´acs and Tikk, 2012; Zhang et al., 2017] have also used the squared form of loss function and learning method based on ALS or coordinate descent technique. However, compared to VALS, they only solve a sub-problem with only one feedback type and no tunable margin to control pairwise ranking relations. Also, the update of user vectors is embarrassingly parallel, while that of item vectors can influence with each other and thus introduce approximate loss in parallel. Thus we plan to solve this issue in future work.

5 Experiments

5.1 Experimental Settings

Datasets and Preprocessing. We perform experiments on two real-world datasets of Beibei and Tmall:

Algorithm 1: Fast VALS Learning algorithm.

Beibei 1 : Beibei is the largest E-commerce platform for maternal and infant products in China. We sample a subset of user interactions that contain views and purchases within the time period from 2017/05/25 to 2017/06/28.

Tmall 2 : Tmall is the largest E-commerce platform in China. To make our results reproducible, we use a public benchmark released in IJCAI-2015 challenge 3 .

We take three steps for data preprocessing. First, we merge the repetitive purchases into one purchase with the earliest timestamp, as we aim to recommend novel items for a user to purchase. Second, we filter out users' views on those purchased items to avoid information leaking. Third, we filter out users and items with less than 12 and 16 purchase interactions, respectively, to alleviate the data sparsity issue. Table 2 summarizes the data statistics.

Evaluation Methodology. In the evaluation, we adopt the leave-one-out protocol [Rendle et al., 2009; He et al., 2016], where the latest purchase interaction of each user is held out for testing and the models are trained on the remaining data. For the metrics, we employ Hit Ratio (HR) and Normalized Discounted Cumulative Gain (NDCG) on the ranking of all non-purchased items for a user. We truncate the ranked list at the position of 100 and report the average score of all users.

1 http://www.beibei.com/

2 https://www.tmall.com/

3 The dataset is downloaded from https://tianchi.aliyun.com/ datalab/dataSet.htm?id=5

Baselines. We compare with two types of methods. For methods that only use primary purchase feedback, we choose:

• eALS [He et al., 2016]. This is a state-of-the-art MF method for implicit recommender systems. We tuned the weight of missing data si.
• BPR [Rendle et al., 2009]. BPR optimizes the MF model with a pairwise ranking loss and learns model parameters with Stochastic Gradient Descent (SGD) method. We tuned the learning rate εBPR.

For the second type of methods that integrate both purchase and view feedback, we choose the following methods,

• MR-BPR [Krohn-Grimberghe et al., 2012]. Applying CMF method to BPR, this method exerts the impact of viewing behavior on predicting purchases with a weight α.
• MC-BPR [Loni et al., 2016]. This method samples both positive and negative instances from viewed items. Two parameters control this process: 1) β1 denotes relative weight of viewed items when sampling positive instances; 2) β2 denotes possibility of sampling a viewed item as a negative instance.
• MFPR [Liu et al., 2017]. This is a most recent method that integrates multiple types of implicit feedback. We adapt it to our case by generating training item pairs in the same way as BPR, and use a fixed learning rate εMFPR in SGD.

Parameter settings. For the above baselines, we have carefully explored the corresponding parameters and listed the result in Table 3. Note that we uniformly set the weight of missing data as si = s0/N, as the effectiveness of popularitybiased weighting strategy is beyond the scope of this paper. The score of purchased interactions rui and its weight ωui are both uniformly set to 1, which are the suggested values in the eALS implementation. For regularization, we set λ as 0.001 for all methods for a fair comparison. Since the findings are consistent across the number of latent factors K, we report the results of K = 32 only.

Efficiency. Our experiment on the same machine (Intel Xeon 2.10 GHz CPU) shows that the actual training time per iteration for VALS on Beibei dataset is about 75s. When training set reduces to (1/4, 1/2, 3/4) of the original size, the time is (15s, 35s, 55s), corresponding to our theoretical analysis of linearity with the size of observed data.

5.2 Hyper-parameter Investigation

Our VALS has two parameters: {γ1, γ2}, which are the margin values to control pairwise ranking between viewed items and other items, and ci that determines the weight of view data. Without loss of generality, we set margin values {γ1, γ2} uniformly as γ1 = γ2 = γ. Similar to weight of missing data si, we set a uniform weight distribution (i.e., ci = c0/N) and leave the item-dependent weighting strategy to the future work. To find the best setting for (γ, c0), we conduct a grid search over these two parameters and report the mean values of both HR and NDCG in last 10 iterations.

Figure 1 plots the prediction accuracy of VALS with different γ and c0. First, we study the impact of margin value γ. For Beibei (Figure 1a and b), we observe that the best γ values are between 0.25 and 0.35 under different values of weight c0. Since the prediction is optimized to indicate the preference level, this highlights the necessity of using an appropriate margin γ so as to control the preference level of viewed interactions, which is lower than purchased ones but higher than non-viewed ones. Surprisingly, for Tmall (Figure 1c and d), we observe that a relative large margin value (λ = 3 ∼ 5) achieves better performance. According to our definition in Eq. (2), purchased items are optimized to be predicted as 1 while optimized predictions for non-viewed items are 0. When the margin γ between a viewed item and a purchased/non-viewed item is large, it is more likely for a viewed item to be predicted outside the (0, 1), while the optimized prediction should be inside. Therefore, a large γ observed on Tmall dataset indicates higher possibility that the preference level of viewed interactions is close to purchased ones or non-viewed ones.

Then, we investigate the best setting of weight c0. For Beibei (Figure 1a and b), the peak performance is achieved when c0 is 1.6; similarly for Tmall (Figure 1c and d), the optimal c0 is 0.5. When c0 becomes smaller or too large, the performance decreases in both cases, indicating the necessity to account for viewed interactions carefully.

According to above parameter exploration, we fix γ and c0 according to the best performance evaluated by HR, i.e., γ=0.3, c0=1.6 for Beibei and γ=3.5, c0=0.5 for Tmall.

5.3 Performance Gain of ViewData

Table 4 displays the performance of our VALS method compared with eALS, w.r.t. HR@100 and NDCG@100. We report their mean values in last 10 iterations. Clearly, after integrating view data as the intermediate feedback, our method significantly outperforms the original eALS that only leverages purchase data. For Beibei, the relative improvement in terms of HR and NDCG are 3.96% and 5.22%, respectively. Moreover, for Tmall, we observe an improvement of over 100% on both two metrics. This indicates that users' viewing behaviors in Tmall are much more valuable for learning a more accurate preference order among different items.

To further clarify the distinct performance gain on two datasets, we compare the predictions over viewed items between two datasets, using both eALS and VALS method to train the model. Figure 2 plots the distribution quantiles (5%, 25%, 50%, 75%, 95%) and means of viewed item scores, where the results of two methods are presented together. Clearly, the viewed items are both predicted to have a near 0 score on two datasets when trained with eALS, as they are considered as negative instances. However, compared to that on Beibei (Figure 2a), VALS generates much higher scores for viewed items on Tmall (Figure 2b), i.e., 0.72 v.s. 0.15 and 0.91 v.s. 0.16 in terms of median and mean value, respectively. These higher scores of viewed items correspond to the fact that viewing behavior is more related to purchasing behavior in Tmall, which is the main reason behind the over 100% improvement of VALS method. Moreover, this also verifies our previous discussion of γ that the VALS model with a large γ is more likely to generate large predictions outside (0, 1), as γ is set as 3.5 for Tmall.

5.4 Performance Comparison

Figure 3 shows the prediction accuracy of each method in each training iteration. Note that we only run VALS for 200 iterations on two datasets and run other methods except MC-BPR for 1500 iterations on Beibei dataset, which are enough for them to converge. We have the following three key observations. First, we see that VALS achieves the best performance after convergence. All improvements are statistically significant evidenced by the one-sample paired t-test (p < 0.01). The best baseline is MC-BPR. Except for a close HR metric on Beibei, VALS outperforms it by a large margin (on average, the relative improvement for Beibei and Tmall is 10.0% and 28.4%). Compared with MC-BPR, VALS mainly benefits from 1) margin-based design that controls the pairwise ranking between predictions of different feedback and 2) the whole-data based strategy of handling missing data. Second, MR-BPR and MFPR achieve higher performance over the vanilla BPR that only leverages purchase data, while the relative improvement is quite insignificant when compared with MC-BPR and VALS. This highlights the necessity of exploiting different preference levels between purchase and view data, which is lacked in MR-BPR and MFPR. Finally, VALS maintains both accuracy and fidelity, which is an inherent advantage of using whole-data based learning strategy. Comparatively, although MC-BPR outperforms the vanilla BPR on the Beibei dataset evaluated by both metrics, we find it obtains a higher HR but a lower NDCG score when compared to eALS that does not integrate view data (i.e., 0.0330 v.s. 0.0345). It means that whole-data based strategy is a better candidate compared to samplingbased one when improving implicit recommender systems.

We notice that BPR-based methods show unusual spike in early iterations and performance degradation with more iterations on Beibei dataset, which might be caused by some regularities in the data. For example, Beibei dataset is highly popularity-skewed - the top-1% items contributed almost 50% of purchases. This may cause unstable performance because these popular items are ranked high in early iterations.

6 Conclusion

We study the problem of improving implicit recommender systems by integrating both purchase and view data. Based on the state-of-the-art eALS method we model user's viewed interactions as an intermediate feedback between purchased and non-viewed interactions. To address the key efficiency challenge in optimization, we further develop a fast learning algorithm which efficiently learns parameters from the whole data instead of sampling negative instances. With these designs, our VALS method not only achieves higher accuracy, but also becomes practical for large-scale data.

This work has focused on collaborative filtering setting, which only leverages the feedback data and is mostly used in the candidate selection stage of industrial recommender systems. In future, we will focus more on the ranking stage, integrating view data into generic feature-based models, such as the expressive neural factorization machines [He and Chua, 2017]. In addition, our VALS method can also be applied to other domains of implicit recommender systems where various additional user feedback can be leveraged, like news [Agarwal et al., 2012], online videos [Covington et al., 2016] and social networks [Hong et al., 2013].

Acknowledgments

This work was supported in part by the National Nature Science Foundation of China under 6171101425, 61621091 and 61673237, and research fund of Tsinghua University - Tencent Joint Laboratory for Internet Innovation Technology. This project is also part of NExT, supported by the National Research Foundation, Prime Minister's Office, Singapore under its IRC@SG Funding Initiative. The corresponding author is Xiangnan He.