Modeling Dynamic User Preference via Dictionary Learning for Sequential Recommendation

Dictionary learning aims to learn a set of vectors capable of succinct expression of the targeted events, i.e., a linear combination of the rows of the dictionary learned from the data can succinctly represent any piece of the input data [32, 39]. In this paper, we try to learn a dictionary that can construct sufficient representations of user dynamic preferences and meanwhile embed user dynamic preferences into the same latent space of user static preferences.

More formally, we propose to learn a feature dictionary $D\in\mathbb{R}^{d_{\mathrm{dict}}\times d_{\mathrm{user}}}$ such that the dynamic user preference of user $i$ at time $t$ — $\overline{u}_{i|t}$ can be constructed by a linear combination of the rows in $D$ using the non-negative coefficients $p_{i|t}$ as follows:

Here, $d_{\mathrm{dict}}$ denotes the number of rows in the dictionary $D$ and $d_{\mathrm{user}}$ denotes the number of hidden units to represent user preferences. The dictionary $D$ can be regarded as a collection of basis which is capable of modeling the changes of user preference vector according to his/her sequential behavior. Then, the combined preference vector of user $i$ at time $t$ can be modelled as follows:

where $u_{i}^{\ast}$ is the static user preference vector.

To learn the optimal dictionary $D$ for modeling user dynamic preferences, we can define a optimization objective as follows:

Here, $r_{i}$ is the rating vector of user $i$ and $\hat{r}_{i|t}$ is the predicted rating vector at time $t$. $\mathcal{D}$ is the distance function between two vectors. Let $r_{i}^{\mathrm{res}}=r_{i}-u_{i}^{\ast}V^{\top}$ and $D^{\prime}=DV^{\top}$ and $\mathcal{D}$ be the F-norm. The above Eqn. 4 means that minimizing the discrepancy between the true ratings and predicted ratings is equivalent to minimizing the discrepancy between the residual error (true rating minus predicted rating from static user preferences) and the dynamic rating (computed from dynamic user preferences). Based on this idea, the above optimization objective can be reformulated as follows:

Therefore, modeling the dynamic user preferences can be formulated as a supervised dictionary learning problem, in which the dictionary D is randomly initialized and then optimized by gradient-based learning techniques. Note that the above Eqn. 4 only illustrates our main idea that the goal of the dictionary learning is to minimize the residual error of the predictions. More specifically, we use an end-to-end training for the whole model instead of training each part of the model individually. The final loss functions are presented in Section 3.3.

In the above dictionary learning problem, the posterior distribution $p_{i|t}$ should not be obtained via point estimations which are not feasible in test time. Therefore, different from standard dictionary learning problem [39], we propose to learn a state function $\phi$, which allows us to accurately obtain $p_{i|t}$ from the user rating vector as follows:

$r_{i_{\leq t}}$ denotes the complete rating history of user $i$ before time $t$. Note that the learning of $\phi$ is challenging because (1) it should accurately capture the sequential dependencies within the rating sequence of each user and (2) it needs to embed the sequential dependencies into the same latent space as the downstream score estimator. To this end, we propose to use a RNN-based autoregressive model to capture the sequential dependencies, and then feed the learned information to the latent space via minimizing the loss $\mathcal{D}(r_{i},\hat{r}_{i|t}|\theta)$.

This paper adopts GRU [10] with attention to learn user dynamic preferences. GRU can adaptively capture the sequential dependencies with different time scales which is more suitable to model the users with different rating time scales in recommendation problem. The neural attention mechanism permits learning an adaptive nonlinear weighting function, which allows the more (less) related dependency patterns to make more (less) contributions in the predictions.

Given the historical ratings of a user $\{x_{1},\dots,x_{T}\}$¹¹1When training the model, we use the entire sequence without slicing, so that the length $T$ is variable for each user in a batch., we first put them into an embedding layer which outputs continuous vectors, then we feed these vectors to GRU to learn the sequential representations $\{g_{1},\dots,g_{T}\}$. Each hidden state $g_{t}$ after the $t$-th historical item can be formally described as follows:

In Eqn. 6, GRU is used as a recurrent activation function which we refer to as a recurrency. Meanwhile, $h_{t-1}\in\mathbb{R}^{d_{\mathrm{GRU}}}$ is the ($t$-1)-th hidden state of GRU, and $\alpha_{t}\in\mathbb{R}^{T}$ is a vector of the attention weights. Eqn. 7 describes a content-based multiplicative attention mechanism [11] which scores each element in $h$ separately and normalizes the scores using softmax as follows:

Here, we use a weighted mapping $W_{h}\in{\mathbb{R}^{d_{\mathrm{rnn}}\times{d_{\mathrm{rnn}}}}}$ in stead of an identity mapping due to better empirical performance.

After encoding the sequential dependencies in a rating sequence, we decode and embed these information into the same latent space of user static preference. More specifically, we learn a multi-layer perceptron (MLP) to approximate the posterior distribution $p_{i|t}$ in Eqn. 2, i.e., the output of the MLP is used as $p_{i|t}$ in Eqn. 2. Formally, we estimate the posterior distribution $p_{i|t}$ for the $t$-th item rated by user $i$ as follows:

Here, the operator $\circ$ is the element-wise product and $h_{t}\circ{g_{t}}$ in Eqn. 11 can capture the second-order interactions between the learned sequential dependencies because $g_{t}$ is a linear combination of $h_{1},\dots,h_{T}$. In this way, $z_{t}$ can be more informative due to containing high-order interactions among $h_{t}$ and can potentially improve model performance [45, 56]. $\psi$ in Eqn. 12 is the activation function, such as sigmoid, tanh and ReLU [42]. The term $\mathrm{sign}(\mathrm{abs}(c_{t,k}))$ is the masking function²²2Note that $sign(abs(c_{t,k}))$ is a non-differentiable function, of which the gradients are ignored for simplicity. Alternatively, we have also tried the differentiable masking function: $c^{\prime}_{t,k}=\exp(c_{t,k})-\exp(0)$, but the performance differences are negligible., which equals to $0$ if $c_{t,k}$ is $0$ and $1$ otherwise. This design allows for a sparse $p_{i|t}$. Eqn. 13 poses a non-negative constraint on $p_{i|t}(k)$ and Eqn. 14 normalizes the probabilities. This non-negative constraint forces the rows of $D^{\prime}$ in Eqn. 3.1.1 to combine, not to cancel out, which can yield more interpretable features and improve the downstream prediction performance [35].

After obtaining $p_{i|t}$, we compute the final dynamic user preferences by interpolating the dictionary $D$ with the weights $p_{i|t}$ as follows:

Two widely adopted real-world datasets are used in the experiments: (1) Netflix Prize³³3https://www.netflixprize.com/ [4] for rating prediction task, and (2) Amazon dataset⁴⁴4http://jmcauley.ucsd.edu/data/amazon/ [17] for item ranking task. For the Netflix dataset, we split it into training and test sets by chronological order to simulate the real scenarios, and we set the ratio of training and test sets as 9:1. For the Amazon dataset, we use two product categories including Instant Video and Baby Care. To achieve sequential recommendation, we select users with at least 10 purchasing records in the experiments. Each user’s purchasing history is ordered by purchasing time, and the first 70% items of each user are used for training while the remaining items are used for test. The statistics of the final datasets are shown in Table II.

To train S2PNM, we adopt the adaptive learning rate algorithm – Adam [27] with $\beta_{1}=0.9$, $\beta_{2}=0.98$ and $\epsilon=10^{-9}$. We also decay the learning rate over 5 full data passes with a rate of $0.9$. Meanwhile, all the weight matrices are initialized from a Glorot uniform distribution [12], and recurrent weights are furthermore orthogonalized. We also employ dropout [53] as regularization during training RNNs with a dropout rate of $p_{\mathrm{drop}}=0.02$, and $\ell_{2}$-norm as regularization to penalize the user and item embeddings. The historical items of each user are batched together with a batch size of 16. We train S2PNM with 20 epochs and measure the performance after each epoch. Then, we report the results on the test set using the best performing model on the validation set. We found that S2PNM is quite robust to hyper-parameters, therefore we adopt the same hyper-parameter setting across both datasets. In addition, pretraining the static user/item preferences can achieve higher accuracy and faster convergence speed. Therefore, in the experiments, we use the BiasedMF method [43] to initialize the static user/item preference vectors. Training details of the compared methods can be found below.

We tune the learning rate $lr\in$ {0.001, 0.002, 0.005, 0.01, 0.02, 0.05, 0.1$\}$, the regularization strength $\lambda\in\{0.001,0.01,0.1\}$ and the latent factor dimension $d\in\{20,50,100,150,200,300\}$ via grid search for all compared methods. Other implementation details are as follows:

• •

  SVD++ [28] is one of the most popular hybrid collaborative filtering based approach. We use the cpp implementation in GraphChi ⁵⁵5https://github.com/GraphChi/graphchi-cpp [31], and we have found that the optimal results on both MovieLens 10M and Netflix data can be achieved when we use factor size $200$, learning rate $0.002$ with decay rate $0.99$ and regularizer $0.01$.

• •

  GLOMA [5] achieves robust results on many benchmarks by enhancing local models based on submatrix with a unified global model. We use StableMA ⁶⁶6https://github.com/ldscc/StableMA provided by the authors which is implemented in Java, and adopt the default setting in [5] which shows the best RMSEs in both idealistic and realistic scenarios, i.e., learning rate $0.0008$, regularization $0.06$, and the latent factor dimension $300$. Notably, we introduce biases into GLOMA following the same idea in BiasMF [30] for improved accuracy, particularly in realistic scenario it helps improve the model performance from 0.96302 to 0.89326 on Netflix data.

• •

  MRMA [34] is so far among the best ensemble based recommendation algorithm. We use the program provided by the authors, and the default setting in [34] produces the best RMSEs in both scenarios. That is factor size ranging in $\{10,20,50,100,150,200,250,300\}$, learning rate $0.001$ and regularizer $0.02$. As the same with GLOMA, we modify MRMA in a fashion of BiasMF, which reduces the RMSE on Netflix from 0.94780 to 0.89150 in realistic scenario.

• •

  TimeSVD++ [29] is one of the most successful models which are able to capture dynamic nature of the recommendation data. We test the implementation in LibRec [14]⁷⁷7https://github.com/guoguibing/librec, in addition to GraphChi [31] of which the implementation is slightly different from the original paper (See lines 162 - 167 in timesvdpp.cpp for more details). This explains why the result of LibRec i.e., RMSE 0.90 on Netflix is better than that from GraphChi i.e., RMSE 0.92 in realistic scenario, where noticeably our results for GraphChi are comparable to [62]. While for LibRec it takes $\geq$24 hours per iteration on Netflix data, by rewriting the data structure to store each user’s data and refining the model update procedure we reduce it to nearly 2 mins per iteration. Although we tuned this model very carefully, it is still worse than SVD++, and the best results are observed by using factor size $200$, learning rate $0.002$ for latent factors and $0.00003$ for bias parameters, regularizer $0.01$.

• •

  AutoRec [51] is among the best neural network models so far in terms of rating prediction. We use the program provided by the authors ⁸⁸8https://github.com/mesuvash/NNRec, which indeed reproduces the results shown in the paper. However, we fail in performing it on Netflix data due to the requirement of memory more than 150 GBs. Therefore, we have to implement it in modern deep learning platform - Tensorflow, whereby we achieve RMSE 0.78056 on MovieLens 10M which is much better than 0.78463 produced by the authors’ code. More specifically, we adopt the latent state dimension as $500$ to yield the best performance and use Adam [27] with batch size $512$, learning rate $0.0005$ with decayed rate $0.9$ every $10$ full data passes to train the model.

• •

  NADE [68] learns the ordinal nature of the user preference and achieves the best results among all baselines. We use the program provide by the authors ⁹⁹9https://github.com/Ian09/CF-NADE to evaluate U-CF-NADE-S, and meanwhile we also test the program based on Chainer ¹⁰¹⁰10https://github.com/dsanno/chainer-cf-nade which produces similar results on MovieLens 10M. The Chainer version requires much less memory as a result of storing data in sparse matrix, in contrast to dense matrix in authors’ code. For computational time, it takes 15 mins per iteration but requires 500 iterations to converge. After fine-tuning the model with 8 GTX-1080Ti, we have found that the optimal setting varies in different datasets, but the configurations with hidden unit size of $500$ in original paper always produce the best results.

• •

  RRN [62] is one of the most closely related works which takes temporal dynamics into consideration, and offers excellent prediction accuracy. We use the program provided by the authors, which is relied on a late-2016 version of MXNET. We rewrite part of the code to make it work with the dependency mxnet-cu80 of version 0.9.5. Different from its original paper, we use $200$-dimensional stationary factors, extra $120$-dimensional dynamic factors, and a single-layer LSTM with $100$-hidden neurons, pursuing better results. Notably, we use BiasMF to initiate RRN model instead of PMF [41] and Autorec [51] for improved performance – RMSE reducing from 0.91823 to 0.89014.

• •

  BPR [46] is the most famous pairwise matrix approximation based model for ranking prediction. We use the implementation in LibRec [14]. By experiments, we found large learning rates lead to accelerated convergence rate so that we chose $0.25$ on Baby Care dataset. In addition, we also found that decayed learning rates can significantly improve the prediction accuracies, perhaps we decayed the learning rate by 0.9 every epoch. After grid search, we use the factor size $128$ and the regularizer $0.01$ on Baby Care dataset.

• •

  eALS [20] is one of the most successful pointwise recommendation approaches. We use the implementation in LibRec [14]. We select factor size over $\{16,32,\dots,256\}$ and regularization parameter over $\{0.1,0.2,\dots,1.0\}$. To be specific, we use the factor size $64$ for all datasets, and $c_{0}$=$256$, learning rate $0.01$ and regularizer $0.1$ on Baby Care dataset.

• •

  NeuMF [19] is among the best neural models for ranking prediction. We use the program provided by the authors ¹¹¹¹11https://github.com/hexiangnan/neural_collaborative_filtering , where we search by grid the learning rate over {1e-1, 5e-2,$\dots$,1e-4}, batch size over {$256$, $512$, $\dots$, $4096$}. The batch size of $2048$ is the optimal for all datasets. And the best performance is achieved when we use learning rate 1e-3.

• •

  RUM [9] is one of state-of-the-art sequential recommendation models based on memory networks, and also most closely related to our work. We note that the comparisons to the classic FPMC [47] and DREAM [65] are omit, since RUM excels them by a large margin. We search by grid the embedding dimension $D$ in the range of {32, 64, $\dots$, 256}. By experiments, we found the number of memory slots $20$ and embedding size $64$ produce the best results.

• •

  SHAN [64] introduces hierarchical attention networks for temporal modelling and achieves state-of-the-art results on many benchmarks. We search by grid the embedding size over {$50$, $100$, $\dots$, $300$} and regularization strength over {$0.001$, $0.01$, $\dots$, $1$}. Experiments show that embedding size $300$ and regularizer $0.01$ for user/item factors and regularizer $1$ for transformation matrix yield the best results.

• •

  SASRec [26] adapts the transformer [57] to recommender systems and is among the best sequential recommendation algorithm. We use the implementation provided by the authors ¹²¹²12https://github.com/kang205/SASRec, and select the embedding size over {$50$, $100$, $\dots$, $300$} and the number of blocks up to $4$. By experiments, the best results can be obtained by using $250$-dimensional embedding size and $4$ blocks with dropout rate $0.2$.

We study the performance of the proposed S2PNM model for both rating prediction task and item ranking task by using the popular evaluation metrics in the literature of recommender systems. For the rating prediction task, we use root mean square error (RMSE) which is defined as $\mathrm{RMSE}=\sqrt{1/|\mathcal{I}_{\mathrm{test}}|\sum_{(i,j,t)\in{\mathcal{I}_{\mathrm{test}}}}(r_{ij}-\hat{r}_{ij|t})^{2}}$ where $\mathcal{I}_{\mathrm{test}}$ stands for the set of test examples.

For the item top-k ranking task, we evaluate the proposed S2PNM model by using Precision@$k$, Hit-Rate@k (HR@$k$) and Normalized Discounted Cumulative Gain@k (NDCG@$k$): 1) $\mathrm{Precision@k}=\frac{1}{|\mathcal{I}_{\mathrm{test}}|}\sum_{i\in\mathcal{I}_{\mathrm{test}}}|R_{i}\cap T_{i}|/|R_{i}|$ where $R_{i}$ is defined as the $k$-size generated recommendation list for user $i$ and $T_{i}$ is the grand-truth; 2) $\mathrm{HR@k}=\frac{1}{|\mathcal{I}_{\mathrm{test}}|}\sum_{i\in\mathcal{I}_{\mathrm{test}}}\mathbf{1}|R_{i}\cap T_{i}|$, in which $\mathbf{1}|x|$ is an indicator function whose value is $1$ when $x>0$ and $0$ otherwise; 3) $\mathrm{NDCG@k}=\frac{1}{|\mathcal{I}_{\mathrm{test}}|}\sum_{i\in\mathcal{I}_{\mathrm{test}}}\mathrm{DCG@k}_{i}/\mathrm{iDCG@k}_{i}$, in which $\mathrm{DCG_{i}@k}=\sum_{j=1}^{k}(\mathbf{1}|R_{i}^{j}\cap T_{i}|-1)/\log_{2}(j+1)$ and $\mathrm{iDCG_{i}@k}$ is a normalized constant which is the maximum possible value of $\mathrm{DCG_{i}@k}$.

S2PNM-stat and S2PNM-dynm denote the S2PNM model with solely using static user preferences and dynamic users preferences, respectively. Figure. 2 - 5 show that S2PNM-dynm outperforms S2PNM-stat in all cases, and S2PNM (with both static and dynamic user preferences) achieves much higher accuracy than both S2PNM-dynm and S2PNM-stat. These results confirm that (1) S2PNM is effective to capture user dynamic preferences and (2) static user preferences are also necessary for predicting user future ratings without which the performance will be suboptimal. In addition, we can see that S2PNM-dynm and S2PNM have comparable results in terms of Precision@5 and HR@5, whereas S2PNM significantly outperforms S2PNM-dynm in NDCG@5. This indicates that users’ static preferences can help to put right recommendations in higher positions.

The leftmost figures of Fig. 2 - 5 show the accuracy with different dictionary sizes, i.e., $d_{\mathrm{dict}}$ varies in $\{64,128,256,512,1024\}$. In Fig. 2 (left), we set user embedding size $d_{\mathrm{user}}$ = 50 and the number of hidden units in GRU $d_{\mathrm{GRU}}$ = 32. In Fig. 3 (left), we set $d_{\mathrm{user}}$ = 250 and $d_{\mathrm{GRU}}$ = 256. As shown in the results, increasing the dictionary size can increase accuracy when $d_{\mathrm{dict}}$ varies in $\{64,128,256,512,1024\}$. This makes sense because a large dictionary can increase the capacity of S2PNM. Therefore, we choose $d_{\mathrm{dict}}$ = 1024 for the accuracy comparison.

The middle figures of Fig. 2 - 5 show the recommendation accuracy with varying number of hidden units in GRU ($d_{\mathrm{GRU}}$). In Fig. 2 (middle), we set $d_{\mathrm{user}}=50$ and $d_{\mathrm{dict}}=64$. In Fig. 3 (middle), we set $d_{\mathrm{user}}=250$ and $d_{\mathrm{dict}}=512$. As shown in the results, increasing the GRU size can improve the model performance when $d_{\mathrm{GRU}}\leq 256$. However, all ranking metrics dropped when $d_{\mathrm{GRU}}=512$, which suggests that overfitting happens with $d_{\mathrm{GRU}}=512$. Therefore, we choose $d_{\mathrm{GRU}}=256$ for the accuracy comparison.

The rightmost figures of Fig. 2 - 5 show the recommendation accuracy with the embedding size $d_{\mathrm{user}}$ varying in $\{50,100,200,250,300\}$. In Fig. 2 (right), we set $d_{\mathrm{dict}}=64$ and $d_{\mathrm{GRU}}=32$. In Fig. 3, we set $d_{\mathrm{dict}}=512$ and $d_{\mathrm{GRU}}=256$. We can see from the results that higher accuracy can be achieved with larger user embedding size, which is consistent with existing methods [43, 28]. Therefore, we choose $d_{\mathrm{user}}=300$ in the following accuracy comparison although higher $d_{\mathrm{user}}$ could further improve the performance of S2PNM.

This experiment compares the rating prediction accuracy of S2PNM against state-of-the-art factorization methods [28, 29, 5, 34] and neural methods [51, 62, 68]. Note that SVD++ , GLOMA and MRMA are factorization models which assume that user preferences are static, while TimeSVD++ [29] used a time-dependent bias term to capture the temporal effects. RRN [62] and NADE [68] both leverage the neural autoregressive model to extract the patterns of how user future actions are affected by his/her historical behaviors. For S2PNM, we use a single-layer RNN with $256$ GRU units, the dimension of user embedding $d_{\mathrm{user}}$ ranges in $\{50,200,300\}$, and set the dictionary size as $d_{\mathrm{dict}}=1000$.

Table III compares the RMSE of all the methods on the Netflix prize dataset. We can see that S2PNM with $d_{\mathrm{user}}$ = 50 can outperform SVD++[28], TimeSVD++ [29], GLOMA [5] and MRMA [34] with the rank of 300, I-AutoRec [51] and NADE [68] with 1000-dimension embeddings, RRN [62] with 300-dimension embeddings. This demonstrates that S2PNM is more effective to predict user ratings than the compared methods. In addition, compared with NADE, S2PNM achieves $0.43\%$ performance gain and over 5X efficiency improvement. The main reasons why S2PNM can improve the recommendation accuracy are: 1) the learned dictionary which maximizes the use of the GRU outputs enriches the expressive capacity of the S2PNM model, 2) the neural network-based distribution approximator that attentively reads the dictionary atoms can accurately capture the dynamic preferences of users, and 3) both the static and dynamic preferences of users are modelled by S2PNM instead of only modeling the static preferences in SVD++, GLOMA, MRMA and I-AutoRec.

To understand how sequential information help in recommendation, we conduct a detailed comparison with the MRMA method which only learns static preferences of users. As shown in Fig. 6, S2PNM achieves consistent improvements ($\geq 1.5\%$) over MRMA for all kinds of users and the largest improvement is $3.3\%$ on users with less than $5$ ratings. The fact that users with less ratings benefit more from S2PNM indicates that (1) the sequential information captured by S2PNM are indeed helpful when little information of users are obtained from ratings (not enough ratings), and (2) S2PNM may be applied to address the on long-tail user issue where many existing CF methods may fail [63].

Here, we evaluate S2PNM in item ranking task. Differing from rating prediction experiment, this study uses $d_{\mathrm{dict}}$ = 5000 and $d_{\mathrm{GRU}}$ = 256 with batch size as 128. Beside SVD++, we compare S2PNM with four ranking-based methods including BPR [46], eALS [20], NeuMF [19], RUM [9], SHAN [64] and SASREC [26]. Note that NeuMF is a neural method that is designed to utilize implicit feedback with non-linear interactions to improve performance and RUM is a state-of-the-art sequential recommendation method based on external memory network to capture the dynamic user preferences.

Table IV shows the recommendation accuracy of S2PNM and the four compared methods on the Amazon Baby Care dataset. We can see from the results that the four neural methods (NeuMF, RUM, SHAN and SASREC) significantly outperform all factorization methods (SVD++, BPR, and eALS), which confirms that neural methods are indeed more powerful than factorization methods in sequential recommendation. As shown in the table, SASREC achieved the best performance among all the compared method. However, S2PNM outperforms SASREC by 0.99%, 2.54% and 6.10% in terms of Precision5, HR5 and NDCG@5, respectively. This indicates that S2PNM can better capture the sequential interactions between users and items for more accurate recommendation.

As mentioned previously, S2PNM bears some similarities with RUM [9]. The main difference lies in that RUM directly combines user preferences and sequential patterns, while S2PNM translates sequential patterns to dynamic part of user preferences. Fig. 7 compares S2PNM with RUM by HR@5 (results of NDCG and Precision show the same trend thus omitted for space). It is clear that S2PNM consistently outperforms RUM for all kinds of users and the largest improvement is $17.0\%$ on users with less than $10$ ratings. This highlights the importance of translating sequence to preference, especially for sparse users that have few history in training.